Контроль Разума
Advertisement
Криптографическая хеш-функция
Название MD5
Разработчик Рональд Ривест
Создан 1991
Опубликован Апрель 1992
Размер хеша 128 бит
Число раундов 4
Тип хеш-функция

MD5 (англ. Message Digest 5) — 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского Технологического Института (MIT, Massachusetts Institute of Technlogy) в 1991 году. Предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. Пришёл на смену MD4, который был несовершенен. Работает на 32-битных машинах. Зная MD5 невозможно восстановить входное сообщение, так как разным сообщениям может соответствовать один MD5. Используется для проверки подлинности опубликованных сообщений, путем сравнения дайджеста сообщения с опубликованным. Эту операцию называют «проверка хеша» (hashcheck). Описан в RFC 1321.[1]

История[]

MD5 один из серии алгоритмов по построению дайджеста сообщения, разработанный профессором Рональдом Л. Ривестом из Массачусетского Технологического Института. Когда аналитическая работа показала что предшественник MD5 — MD4 — не безопасен, в 1991 году был разработан новый алгоритм, как надежная замена. Недостатки алгоритма MD4 были позже найдены Гансом Доббертином.

В 1993 году Берт ден Боер (Bert den Boer) и Антон Босселарис (Antoon Bosselaers) показали, что в алгоритме возможны псевдоколлизии, когда разным инициализирующим векторам соответсвуют одинаковые дайджесты для входного сообщения.

В 1996 году Ганс Доббертин (Hans Dobbertin) объявил о коллизии в алгоритме и уже в то время было предложено использовать другие алгоритмы хеширования, такие как Whirlpool, SHA-1 или RIPEMD-160.

Из-за небольшого размера хеша в 128 бит, можно рассматривать birthday атаки. В марте 2004 года был запущен проект MD5CRK с целью обнаружения уязвимостей алгоритма, используя birthday атаки.

Проект MD5CRK закончился после 17 августа 2004, когда Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) обнаружили уязвимости в алгоритме.

1 марта 2005, Arjen Lenstra, Xiaoyun Wang, и Benne de Weger продемонстрировали построение двух X.509 документов с различными открытыми ключами и одинаковым хешем MD5.

18 марта 2006 исследователь Властимил Клима (Vlastimil Klima) опубликовал алгоритм, который может найти коллизии за одну минуту на обычном компьютере, метод получил название «туннелирование».

Алгоритм MD5[]

Файл:MD5.png

Cхема работы алгоритма MD5

На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Длина сообщения может быть любой (в том числе нулевой). Запишем длину сообщения в L. Это число целое и не отрицательное. Кратность каким-либо числам не обязательна. После поступления даных идет процесс подготовки потока к вычислениям.

Ниже приведены 5 шагов алгоритма:

Шаг 1. Выравнивание потока[]

Входные данные выравниваются так, чтобы их размер был сравним с 448 по модулю 512 (L’ = 512 × N + 448). Сначала дописывают единичный бит в конец потока, затем необходимое число нулевых бит (выравнивание происходит, даже если длина уже конгруэнтна — сравнима с 448).

Шаг 2. Добавление длины сообщения[]

В оставшиеся 64 бита дописывают 64-битное представление длины данных до выравнивания. Если длина превосходит , то дописывают только младшие биты. После этого длина потока станет кратной степеням двойки — 16, 32. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.

Шаг 3. Инициализация буфера[]

Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения шестнадцатеричными числами:

А = 01 23 45 67;
В = 89 AB CD EF;
С = FE DC BA 98;
D = 76 54 32 10.

В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется инициализирующим вектором.

Определим еще функции и константы, которые нам понадобятся для вычислений.

  • Потребуются 4 функции для четырех раундов. Введем функции от трех параметров — слов, результатом также будет слово.
1 раунд .
2 раунд .
3 раунд .
4 раунд .
  • Определим таблицу констант T[1..64] — 64-элементная таблица данных, построенная следующим образом: и s — циклический сдвиг влево на s бит полученого 32-битного аргумента.
  • Выравненные данные разбиваются на блоки (слова) по 32 бита, и каждый блок проходит 4 раунда из 16 операторов. Все операторы однотипны и имеют вид: [abcd k s i], определяемый как , где X — блок данных. X[k] = M [n * 16 + k], где k — номер 32-битного слова из n-го 512-битного блока сообщения.

Шаг 4. Вычисление в цикле[]

Заносим в блок данных элемент n из массива. Сохраняются значения A, B, C и D, оставшиеся после операций над предыдущими блоками (или их начальные значения, если блок первый).

AA = A
BB = B
CC = C
DD = D

Раунд 1

/*[abcd k s i] a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  0 7  1][DABC  1 12  2][CDAB  2 17  3][BCDA  3 22  4]
[ABCD  4 7  5][DABC  5 12  6][CDAB  6 17  7][BCDA  7 22  8]
[ABCD  8 7  9][DABC  9 12 10][CDAB 10 17 11][BCDA 11 22 12]
[ABCD 12 7 13][DABC 13 12 14][CDAB 14 17 15][BCDA 15 22 16]

Раунд 2

/*[abcd k s i] a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  1 5 17][DABC  6 9 18][CDAB 11 14 19][BCDA  0 20 20]
[ABCD  5 5 21][DABC 10 9 22][CDAB 15 14 23][BCDA  4 20 24]
[ABCD  9 5 25][DABC 14 9 26][CDAB  3 14 27][BCDA  8 20 28]
[ABCD 13 5 29][DABC  2 9 30][CDAB  7 14 31][BCDA 12 20 32]

Раунд 3

/*[abcd k s i] a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  5 4 33][DABC  8 11 34][CDAB 11 16 35][BCDA 14 23 36]
[ABCD  1 4 37][DABC  4 11 38][CDAB  7 16 39][BCDA 10 23 40]
[ABCD 13 4 41][DABC  0 11 42][CDAB  3 16 43][BCDA  6 23 44]
[ABCD  9 4 45][DABC 12 11 46][CDAB 15 16 47][BCDA  2 23 48]

Раунд 4

/*[abcd k s i] a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  0 6 49][DABC  7 10 50][CDAB 14 15 51][BCDA  5 21 52]
[ABCD 12 6 53][DABC  3 10 54][CDAB 10 15 55][BCDA  1 21 56]
[ABCD  8 6 57][DABC 15 10 58][CDAB  6 15 59][BCDA 13 21 60]
[ABCD  4 6 61][DABC 11 10 62][CDAB  2 15 63][BCDA  9 21 64]

Суммируем с результатом предыдущего цикла:

A = AA + A
B = BB + B
C = CC + C
D = DD + D

После окончания цикла необходимо проверить, есть ли еще блоки для вычислений. Если да, то изменяем номер элемента массива (n++) и переходим в начало цикла.

Шаг 5. Результат вычислений[]

Результат вычислений находится в буфере ABCD, это и есть хеш. Если вывести слова в обратном порядке DCBA, то мы получим наш MD5 хеш.

Сравнение MD5 и MD4[]

Алгоритм MD5 происходит от MD4. В новый алгоритм добавили еще один раунд, теперь их стало 4 вместо 3 в MD4. Добавили новую константу для того, чтобы свести к минимуму влияние входного сообщения, в каждом раунде на каждом шаге и каждый раз константа разная, она суммируется с результатом F и блоком данных. Изменилась функция G = XZ v (Y not(Z)) вместо (XY v XZ v YZ). Результат каждого шага складывается с результатом предыдущего шага, из-за этого происходит более быстрое изменение результата. Изменился порядок работы с входными словами в раундах 2 и 3.

Различия в скорости работы представлены в таблице:

Таблица сравнения скоростей
MD5 MD4
RFC 2,614 сек 37359 Кб/сек 2,574 сек 37940 Кб/сек
OpenSSL 1,152 сек 84771 Кб/сек 0,891 сек 109603 Кб/сек

Необходимо было вычислить 10 000 хешей для сообщения длиной 10 000 байт. В качестве реализаций использовались OpenSSL и RFC 1321.

MD5 хеши[]

Хеш содержит 128 бит (16 байт) и обычно представляется как последовательность из 32 шестнадцатеричных чисел.

Несколько примеров хеша:

 MD5("md5") = 1bc29b36f623ba82aaf6724fd3b16718

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

 MD5("md4") =  c93d3bf7a7c4afe94b64e30c2ce39f4f

Пример MD5 хеша для «нулевой» строки:

 MD5("") = d41d8cd98f00b204e9800998ecf8427e

Криптоанализ[]

На данный момент существуют несколько видов «взлома» хешей MD5 — подбора сообщения с заданным хешем:

Для перебора по словарю или брутфорса можно использовать программы PasswordsPro[2], MD5BFCPF[3], John the Ripper. Словари для Brute-force также можно найти.[4]

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

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

В 1996 году Ганс Доббертин, нашел псевдоколлизии в MD5, используя определенные инициализирующие векторы, отличные от стандартных. Оказалось, что можно для известного сообщения построить второе, такое что оно будет иметь такой же хеш как и исходное. C точки зрения математики это означает MD5(IV,L1) = MD5(IV,L2), где IV начальное значение буфера, а L1 и L2 различные сообщения. Ханс Доббертин нашел такие значения. Например если взять начальное значение буфера:

A = 0x12AC2375
В = 0x3B341042
C = 0x5F62B97C
D = 0x4BA763ED

и задать входное сообщение

AA1DDABE D97ABFF5 BBF0E1C1 32774244
1006363E 7218209D E01C136D 9DA64D0E
98A1FB19 1FAE44B0 236BB992 6B7A779B
1326ED65 D93E0972 D458C868 6B72746A

то, добавляя число к определенному 32-разрядному слову в блочном буфере, можно получить второе сообщение с таким же хешем. Ханс Доббертин представил такую формулу:

Тогда MD5(IV, L1) = MD5(IV, L2) = BF90E670752AF92B9CE4E3E1B12CF8DE.

В 2004 году китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии.[5][6]

В 2005 году исследователи Сяоюнь Ван и Хунбо Ю из университета Шандонг в Китае, опубликовали алгоритм, который может найти две различные последовательности 128 байт, которые дают одинаковый MD5 хеш. Одна из таких пар:

d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70

и

d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70

Каждый их этих блоков дает MD5 хеш равный 79054025255fb1a26e4bc422aef54eb4.

Метод Сяоюнь Вана и Хунбо Ю[]

Метод Сяоюнь Вана и Хунбо Ю использует тот факт, что MD5 построен на итерационном методе Меркле-Дамгарда. Поданный на вход файл, сначала дополняется, так чтобы его длина была кратна 64 байтам, после этого он делится на блоки по 64 байта каждый M0,M1,…,Mn-1. Далее вычисляется последовательность 16-ти байтных состояний s0,…,sn по правилу si+1=f(si,Mi), где f некоторая фиксированная функция. Начальное состояние s0 называется инициализирующим вектором.

Сяоюнь Вана и Хунбо Ю позволяет для заданного инициализирующего вектора найти две пары и , такие что . Важно отметить, что этот метод работает для любого инициализирующего вектора, а не только для вектора используемого по стандарту.

Эта атака является разновидностью дифференциальной атаки, которая, в отличие от других атак этого типа, использует целочисленное вычитание а не XOR в качестве меры разности. При поиске коллизий используется метод модификации сообщений: сначала выбирается произвольное сообщение M0, далее оно модифицируется по некоторым правилам, сформулированным в статье, после чего вычисляется дифференциал хеш-функции, причем с вероятностью 2-37. К и применяется функция сжатия для проверки условий коллизии; далее выбирается произвольное , модифицируется, вычисляется новый дифференциал, равный нулю с вероятностью 2-30, а равенство нулю дифференциала хеш-функции как раз означает наличие коллизии. Оказалось, что найдя одну пару и , можно менять лишь два последних слова в , тогда для нахождения новой пары и требуется всего около 239 операций хеширования.

Применение этой атаки к MD4 позволяет найти коллизию меньше чем за секунду. Она также применима к другим хеш-функциям, таким как RIPEMD и HAVAL.

В 2006 году чешский исследователь Властимил Клима опубликовал алгоритм, позволяющий находить коллизии на обычном компьютере с любым начальным вектором (A,B,C,D) при помощи метода, названного им «туннелирование».[7][8]

Примеры использования[]

MD5 позволяет получать относительно надежный идентификатор для блока данных. Такое свойство алгоритма широко применяется в разных обастях. Оно позволяет искать дублирующиеся файлы на компьютере, сравнивая MD5 файлов, а не их содержимое. Как пример, dupliFinder — графическая программа под Windows и Linux. Такой же поиск может работать и в интернете.

С помощью MD5 проверяют целостность скачанных файлов — так, некоторые программы идут вместе со значением хеша. Например, диски для инсталляции.

MD5 используется для хеширования паролей. В системе UNIX каждый пользователь имеет свой пароль и его знает только пользователь. Для защиты паролей используется хеширование. Получить настоящий пароль можно только полным перебором. При появлении UNIX единственным способом хеширования был DES (Data Encryption Standard), но им могли пользоваться только жители США, потому что исходные коды DES нельзя было вывозить из страны. Во FreeBSD решили эту проблему. Пользователи США могли использовать библиотеку DES, а остальные пользователи имеют метод, разрешенный для экспорта. Поэтому в FreeBSD стали использовать MD5 по умолчанию.[9]

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

  1. Пароли хранятся как есть. При взломе такой базы все пароли станут известны.
  2. Хранятся только хеши паролей (с помощью MD5, SHA). Найти пароли можно только полным перебором. Но сейчас такая задача решается за доли секунды. Пароль из таблицы был найден всего за 0,036059 сек.[10]
  3. Хранятся хеши паролей и несколько случайных символов. К каждому паролю добавляется несколько случайных символов и результат ещё раз хешеруется. Например, md5(md5(pass)+word). Найти пароль с помощью таблиц таким методом не получится.
Пример базы данных
способ id login password
1 5 anton mydata
2 5 anton 39e0e72ad44377f39b9769a8cc4c2d69
3 5 anton md5(md5(mydata)+word) и word

Существует несколько надстроек над MD5 для усиления криптостойкости.

  • MD5 (HMAC) — HMAC — Keyed-Hashing for Message Authentication (хеширование с ключом для аутентификации сообщения) — алгоритм позволяет хешировать входное сообщение L с некоторым ключём K, такое хеширование позволяет аутентифицировать подпись.
  • MD5 (Base64) — здесь полученный MD5 хеш кодируется алгоритмом Base64.
  • MD5 (Unix) — алгоритм вызывает тысячу раз стандартный MD5.

Примечания[]

  1. R. Rivest. (апрель 1992) The MD5 Message-Digest Algorithm (русск.)Проверено 19 ноября 2008.
  2. PasswordsPro. InsidePro Software. — Программа для восстановления паролей к хешам различных типов.  Проверено 19 ноября 2008.
  3. Проект MD5 на сайте SourceForge
  4. CERIAS — Security Archive. Center for Education and Research in Information Assurance and Security (июнь 2000).  Проверено 19 ноября 2008.
  5. Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu. (17 августа 2004) Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (англ.)Проверено 19 ноября 2008.
  6. Philip Hawkes, Michael Paddon, Gregory G. Rose. (13 октября 2004) Musings on the Wang et al. MD5 Collision (англ.)Проверено 19 ноября 2008.
  7. Vlastimil Klima. (17 апреля 2006) Tunnels in Hash Functions: MD5 Collisions Within a Minute (англ.)Проверено 19 ноября 2008.
  8. Vlastimil Klima. MD5 collisions (англ.)Проверено 19 ноября 2008.
  9. Bill Swingle. (2006) Руководство FreeBSD (DES, MD5 и шифрование)Проверено 20 ноября 2008.
  10. An Online MD5 Hash DatabaseПроверено 20 ноября 2008.

См. также[]

Алгоритмы хеширования
Программы

Ссылки[]

Программы и исходные коды для генерации MD5 на разных языках и платформах.

Ошибка: неверное или отсутствующее изображение

Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на странице Википедия:Статьи для рецензирования.

ar:إم دي5 ca:MD5 cs:Message-Digest algorithm da:MD5 de:Message-Digest Algorithm 5 en:MD5 es:MD5 eu:MD5 fa:ام‌دی۵ fi:MD5 fr:MD5 he:MD5 hu:MD5 id:MD5 it:MD5 ja:MD5 ko:MD5 lt:MD5 ms:MD5 nl:MD5 no:MD5 pl:MD5 pt:MD5 ro:MD5 sk:MD5 sl:Algoritem MD5 sr:MD5 sv:MD5 tg:MD5 tr:MD5 uk:MD5 vi:MD5 zh:MD5

Advertisement