Кратко о хеше

Я уже затрагивал данную тему в статье про брут пароля с помощью hashcat.
Сегодня же хотелось бы кратко разобрать эту тему и ответить на основные вопросы по ней.

Слово хеш происходит от английского «hash», одно из значений которого трактуется как путаница или мешанина. Собственно, это довольно полно описывает реальное значение этого термина.

Вообще, хешем мы называем для простоты хеш-функцию... Итак, хеш(хеш-фунция) - функция, преобразовывающая входную последовательность данных произвольного размера в выходную последовательность фиксированного размера. Еще проще говоря, это функция которая способна по объекту из заранее выбранного большого множества вернуть объект из какого-то ограниченного множества.

Зачем нужен хеш?!

Хеширование используется для индексации и извлечения элементов в базах данных для быстрого поиска элементов в них, тк используя более короткий хешированный ключ поиск занимает гораздо меньше времени, чем с использованием исходного значения. Оно также используется во многих алгоритмах шифрования .

Для нас с вами, простых пользователей, наиболее распространенная область применения хеширования — хранение паролей.

В дополнение к более быстрому изъятию данных хеширование также используется для определения подлинности "цифрового" объекта(его цифровой подписи). После скачивания какого-либо объекта пользователь может проверить значение его хеш-функции с приведенным значением хеш-фунции продукта перед скачиванием, если оно будет совпадать, то значит, при скачивании все прошло нормально. Так же можно проверить на подлинность(на лицензию) используемое ПО и тд.

Был случай, когда популярный облачный сервис Dropbox заблокировал одного из своих пользователей за распространение контента, защищенного авторскими правами. Герой истории тут же написал об этом в твиттере, запустив волну негодования среди пользователей сервиса, ринувшихся обвинять Dropbox в том, что он якобы позволяет себе просматривать содержимое клиентских аккаунтов, хотя не имеет права этого делать.

Впрочем, как вы понимаете, Dropbox не лез в просматривание личного контента пользователей. Дело в том, что владелец защищенного копирайтом контента имел на руках хеш-коды определенных аудио и видеофайлов, запрещенных к распространению, и данные хеши были занесены в черный список на сервисе. Поэтому, когда пользователь предпринял попытку незаконного распространения данного контента, сканер Dropbox автоматически засекли данные файлы и заблокировали возможность их распространения.

Свойства хеш-функций

Для того, чтобы формируемое хеш-функцией значение уникально идентифицировало сообщения, и всякая попытка изменения сообщения при передаче была обнаружена путем выполнения хэширования, необходимо, чтобы хеш-функция обладала следующими свойствами:

на вход хэш-функции подается сообщение произвольной длины;

• на выходе хэш-функции формируется блок данных фиксированной длины;
• значения на выходе хэш-функции распределены по равномерному закону;
• при изменении одного бита на входе хэш-функции существенно изменяется выход.

Для обеспечения устойчивости хэш-функции к атакам она должна удовлетворять следующим требованиям:

• если мы знаем значение хэш-функции h, то задача нахождения сообщения M такого, что Н(М) = h, должна быть вычислительно трудной;
• при заданном сообщении M задача нахождения другого сообщения M’, такого, что Н(М) = H(M’), должна быть вычислительно трудной.

Методы хеширования

(Разберу реализацию наиболее простого хеширования на примере метода усножения)

Сама функция будет иметь вид:

h(k)=[N*({k*A})] , где:

k – ключ (тот, что необходимо хешировать);
N – максимально возможное число хеш-кодов;
A – рациональное число, по модулю меньшее единицы (0<A<1).

{ } – скобки для взятия дробной части;
⌊ ⌋ – скобки для взятия целой части.

Аргумент хеш-функции k (k≥0) в результате даст значение хеш-кода h(k)=x, лежащие в диапазоне 0…N-1.

От выбора A и N зависит то, насколько оптимальным окажется хеширование умножением на определенной последовательности. Не имея сведений о входящих ключах, в качестве N следует выбрать одну из степеней двойки, т. к. умножение на 2m равносильно сдвигу на m разрядов, что компьютером производиться быстрее. Неплохим значением для A (в общем случае) будет (√5-1)/2≈0,6180339887. Оно основано на свойствах золотого сечения (отношение большей части к меньшей равно отношению всей величины к ее большей части).

Для демонстрации работы данного метода возьмем N = 32, A = 0,618033. В качестве ключей возьмем числа: 21, 33 и 45, и подставим их в функцию:

h(k) = [32*({21*0,618033})] = [32*{12,978693}] = [32*0,978693] = [31,318176] = 31

h(k) = [32*({33*0,618033})] = [32*{20,395089}]= [32*0,395089] = [12,642848] = 12

h(k) = [32*({45*0,618033})] = [32*{27,811485}] = [32*0,811485] = [25,96752]= 25

Пример реализации данного метода на c++

#include <iostream>
using namespace std;

int HashFunction(int k)
{
int N = 32; 
double A = 0.618033;
int h = N * fmod((k * A), 1);
return h;
}

void main()
{
setlocale(0, "rus");
int key;
cout << "Введите ключ" << endl; 
cin >> key;
cout << "Hash(" << key << ")=" << HashFunction(key) << endl;
}

Также есть такие методы, как:

• Метод деления-остатка: оценивается размер количества элементов в таблице. Затем это число используется как делитель при делении ключа для извлечения частного и остатка. Остаток будет хешированным значением. 
• Метод сложения: этот метод делит исходное значение на несколько частей, складывает части, а затем использует (обычно) последние четыре цифры в качестве хэшированного значения.
• Метод преобразования основания системы счисления: если ключ является числовым значением, то изменяется основание системы счисления. (Например, ключ с десятичным номером может быть преобразован в шестнадцатеричный нумерованный ключ.) Знаки высокого порядка могут быть отброшены, чтобы соответствовать хеш-значению одинаковой длины.
• Метод перегруппировки цифр: тут просто осуществляется вход в исходный ключ, в каких-либо позициях, изменяя их порядок, а затем эта последовательность цифр используется в качестве значения хеша.
• Метод сдвига: все разряды числа, являющегося ключом, разбиваются на две части: старшие и младшие разряды. Обе эти части сдвигаются по направле-нию друг к другу так, чтобы число перекрывающихся разрядов со-ответствовало длине адреса. Цифры, содержащиеся в пе-рекрывающихся разрядах, суммируются, и результат, как и в первом методе, выравнивается в соответствии с диапазоном адресов участков
• Анализ отдельных разрядов ключа: Для достижения равномерного распределения адресов участков можно использовать анализ распределения значений чисел и симво-лов в каждом ключе. Выбросив из ключа разряды, имеющие распре-деление, сильно отличающееся от равномерного, и преобразуя только оставшиеся разряды, мы сможем достичь более равномерного распре-деления адресов на выходе алгоритма хеширования.

Ну, и напоследок порекомендую программку для вычисления хеша для любых файлов на вашем компьютере - HashTab. Она подойдет тем, кто совсем не любит пользоваться консолью:)