Хэш-функция MD5
Много на просторах интернета, в том числе на хабре, написано о различный хэш-функциях, однако, в данном топике я дам свой взгляд на алгоритм и реализацию MD5.
Однако чаще всего хэш-функции используются для проверки уникальности пароля, файла, строки и тд. К примеру, скачивая файл из интернета, вы часто видите рядом с ним строку вида b10a8db164e0754105b7a99be72e3fe5 — это и есть хэш, прогнав этот файл через алгоритм MD5 вы получите такую строку, и, если хэши равны, можно с большой вероятностью утверждать что этот файл действительно подлинный (конечно с некоторыми оговорками, о которых расскажу далее).
Алгоритм состоит из пяти шагов:
1)Append Padding Bits
В исходную строку дописывают единичный байт 0х80, а затем дописывают нулевые биты, до тех пор, пока длина сообщения не будет сравнима с 448 по модулю 512. То есть дописываем нули до тех пор, пока длина нового сообщения не будет равна [длина] = (512*N+448),
где N — любое натуральное число, такое, что это выражение будет наиболее близко к длине блока.
2)Append Length
Далее в сообщение дописывается 64-битное представление длины исходного сообщения.
3)Initialize MD Buffer
На этом шаге инициализируется буффер
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Как можно заметить буффер состоит из четырех констант, предназначенный для сбора хэша.
4)Process Message in 16-Word Blocks
На четвертом шаге в первую очередь определяется 4 вспомогательные логические функции, которые преобразуют входные 32-битные слова, в, как ни странно, в 32-битные выходные.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
Также на этом шаге реализуется так называемый «белый шум» — усиление алгоритма, состоящее 64 элементного массива, содержащего псевдослучайные числа, зависимые от синуса числа i:
T[i]=4,294,967,296*abs(sin(i))
Далее начинается «магия». Копируем каждый 16-битный блок в массив X[16] и производим манипуляции:
AA = A
BB = B
CC = C
DD = D
Затем происходят «чудесные» преобразования-раунды, которых всего будет 4. Каждый раунд состоит из 16 элементарных преобразований, которые в общем виде можно представить в виде [abcd k s i], которое, в свою очередь, можно представить как A = B + ((A + F(B,C,D) + X[k] + T[i]) <<< s), где
A, B, C, D — регистры
F(B,C,D) — одна из логических функций
X[k] — k-тый элемент 16-битного блока.
T[i] — i-тый элемент таблицы «белого шума»
<<< s — операция циклического сдвига на s позиций влево.
Приводить все раунды не имеет смысла, все их можно посмотреть тут
Ну и в конце суммируем результаты вычислений:
A = A + AA
B = B + BB
C = C + CC
D = D + DD
5) Output
Выводя побайтово буффер ABCD начиная с A и заканчивая D получим наш хэш.
Также у MD5, как у любой хэш-функции, существует такое понятие как коллизии — это получение одинаковых хэшей для разных исходных строк. В 1996 году Ганс Доббертин нашёл псевдоколлизии в MD5, используя определённый инициализирующий буффер (ABCD). Также в 2004 году китайские исследователи Ван Сяоюнь, Фен Дэнгуо, Лай Сюэцзя и Юй Хунбо объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии. Однако в 2006 году чешский исследователь Властимил Клима опубликовал алгоритм, позволяющий находить коллизии на обычном компьютере с любым начальным вектором (A,B,C,D) при помощи метода, названного им «туннелирование».
Прилагаю собственный пример реализации функции на C#:
md5.rar
Что такое хэш-функция и чем её едят?
Хэш-функция предназначена для свертки входного массива любого размера в битовую строку, для MD5 длина выходной строки равна 128 битам. Для чего это нужно? К примеру у вас есть два массива, а вам необходимо быстро сравнить их на равенство, то хэш-функция может сделать это за вас, если у двух массивов хэши разные, то массивы гарантировано разные, а в случае равенства хэшей — массивы скорее всего равны.Однако чаще всего хэш-функции используются для проверки уникальности пароля, файла, строки и тд. К примеру, скачивая файл из интернета, вы часто видите рядом с ним строку вида b10a8db164e0754105b7a99be72e3fe5 — это и есть хэш, прогнав этот файл через алгоритм MD5 вы получите такую строку, и, если хэши равны, можно с большой вероятностью утверждать что этот файл действительно подлинный (конечно с некоторыми оговорками, о которых расскажу далее).
Конкретнее о MD5
Не буду углубляться в историю создания, об этом можно почитать в википедии, однако отмечу что алгоритм был создан профессором Р. Риверстом в 1991 году на основе алгоритма md4. Описан этот алгоритм в RFC 1321Алгоритм состоит из пяти шагов:
1)Append Padding Bits
В исходную строку дописывают единичный байт 0х80, а затем дописывают нулевые биты, до тех пор, пока длина сообщения не будет сравнима с 448 по модулю 512. То есть дописываем нули до тех пор, пока длина нового сообщения не будет равна [длина] = (512*N+448),
где N — любое натуральное число, такое, что это выражение будет наиболее близко к длине блока.
2)Append Length
Далее в сообщение дописывается 64-битное представление длины исходного сообщения.
3)Initialize MD Buffer
На этом шаге инициализируется буффер
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Как можно заметить буффер состоит из четырех констант, предназначенный для сбора хэша.
4)Process Message in 16-Word Blocks
На четвертом шаге в первую очередь определяется 4 вспомогательные логические функции, которые преобразуют входные 32-битные слова, в, как ни странно, в 32-битные выходные.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
Также на этом шаге реализуется так называемый «белый шум» — усиление алгоритма, состоящее 64 элементного массива, содержащего псевдослучайные числа, зависимые от синуса числа i:
T[i]=4,294,967,296*abs(sin(i))
Далее начинается «магия». Копируем каждый 16-битный блок в массив X[16] и производим манипуляции:
AA = A
BB = B
CC = C
DD = D
Затем происходят «чудесные» преобразования-раунды, которых всего будет 4. Каждый раунд состоит из 16 элементарных преобразований, которые в общем виде можно представить в виде [abcd k s i], которое, в свою очередь, можно представить как A = B + ((A + F(B,C,D) + X[k] + T[i]) <<< s), где
A, B, C, D — регистры
F(B,C,D) — одна из логических функций
X[k] — k-тый элемент 16-битного блока.
T[i] — i-тый элемент таблицы «белого шума»
<<< s — операция циклического сдвига на s позиций влево.
Приводить все раунды не имеет смысла, все их можно посмотреть тут
Ну и в конце суммируем результаты вычислений:
A = A + AA
B = B + BB
C = C + CC
D = D + DD
5) Output
Выводя побайтово буффер ABCD начиная с A и заканчивая D получим наш хэш.
Надежность
Существует мнение что взломать хэш MD5 невозможно, однако это неправда, существует множество программ подбирающих исходное слово на основе хэша. Абсолютное большинство из них осуществляет перебор по словарю, однако существуют такие методы как RainbowCrack, он основан на генерировании множества хэшей из набора символов, чтобы по получившейся базе производить поиск хэша.Также у MD5, как у любой хэш-функции, существует такое понятие как коллизии — это получение одинаковых хэшей для разных исходных строк. В 1996 году Ганс Доббертин нашёл псевдоколлизии в MD5, используя определённый инициализирующий буффер (ABCD). Также в 2004 году китайские исследователи Ван Сяоюнь, Фен Дэнгуо, Лай Сюэцзя и Юй Хунбо объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии. Однако в 2006 году чешский исследователь Властимил Клима опубликовал алгоритм, позволяющий находить коллизии на обычном компьютере с любым начальным вектором (A,B,C,D) при помощи метода, названного им «туннелирование».
Прилагаю собственный пример реализации функции на C#:
md5.rar
0 комментариев