MD5

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

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

Содержание

1 История
2 Алгоритм MD5
3 MD5-хеши
4 Криптоанализ
- 4.1 Атаки переборного типа
- 4.2 Коллизии MD5
  - 4.2.1 Метод Ван Сяоюня и Юй Хунбо
5 Примеры использования
6 См. также
7 Примечания
8 Ссылки

История

MD5 — один из серии алгоритмов по построению дайджеста сообщения, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института. Разработан в 1991 году, как более надёжный вариант предыдущего алгоритма MD4.^[1] Позже Гансом Доббертином были найдены недостатки алгоритма 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

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

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

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

Сначала дописывают единичный бит в конец потока (байт 0x80), затем необходимое число нулевых бит. Входные данные выравниваются так, чтобы их новый размер был сравним с 448 по модулю 512 (). Выравнивание происходит, даже если длина уже сравнима с 448.

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

В оставшиеся 64 бита дописывают 64-битное представление длины данных (количество бит в сообщении) до выравнивания. Сначала записывают младшие 4 байта. Если длина превосходит , то дописывают только младшие биты. После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 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 раунд .

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

Шаг 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, это и есть хеш. Если выводить побайтово, начиная с младшего байта A и закончив старшим байтом D, то мы получим 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 сек	37 359 Кб/с	2,574 сек	37 940 Кб/с
OpenSSL	1,152 сек	84 771 Кб/с	0,891 сек	109 603 Кб/с

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

MD5-хеши

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

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

 MD5("md5") = 1bc29b36f623ba82aaf6724fd3b16718

Даже небольшое изменение входного сообщения (в нашем случае на один бит: ASCII символ «5» с кодом 0x35₁₆ = 000110101₂ заменяется на символ «4» с кодом 0x34₁₆ = 000110100₂) приводит к полному изменению хеша. Такое свойство алгоритма называется лавинным эффектом.

 MD5("md4") = c93d3bf7a7c4afe94b64e30c2ce39f4f

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

 MD5("") = d41d8cd98f00b204e9800998ecf8427e

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

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

Атаки переборного типа

Для полного перебора или перебора по словарю можно использовать программы PasswordsPro^[4], MD5BFCPF^[5], John the Ripper. Для перебора по словарю существуют готовые словари.^[6]

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

Коллизии MD5

Коллизия хеш-функции — это получение одинакового значения функции для разных сообщений и идентичного начального буфера. В отличие от коллизий, псевдоколлизии определяются как равные значения хеша для разных значений начального буфера, причём сами сообщения могут совпадать или отличаться. В 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 (англ.)) находить коллизии.^[7]^[8]

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

`d131dd02c5e6eec4693d9a0698aff95c`	`2fcab58712467eab4004583eb8fb7f89`
`55ad340609f4b30283e488832571415a`	`085125e8f7cdc99fd91dbdf280373c5b`
`d8823e3156348f5bae6dacd436c919c6`	`dd53e2b487da03fd02396306d248cda0`
`e99f33420f577ee8ce54b67080a80d1e`	`c69821bcb6a8839396f9652b6ff72a70`

`d131dd02c5e6eec4693d9a0698aff95c`	`2fcab50712467eab4004583eb8fb7f89`
`55ad340609f4b30283e4888325f1415a`	`085125e8f7cdc99fd91dbd7280373c5b`
`d8823e3156348f5bae6dacd436c919c6`	`dd53e23487da03fd02396306d248cda0`
`e99f33420f577ee8ce54b67080280d1e`	`c69821bcb6a8839396f965ab6ff72a70`

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

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

Метод Ван Сяоюня и Юй Хунбо использует тот факт, что MD5 построен на итерационном методе Меркла-Дамгарда. Поданный на вход файл сначала дополняется, так чтобы его длина была кратна 64 байтам, после этого он делится на блоки по 64 байта каждый M₀,M₁,…,M_n-1. Далее вычисляется последовательность 16-байтных состояний s₀,…,s_n по правилу s_i+1=f(s_i,M_i), где f некоторая фиксированная функция. Начальное состояние s₀ называется инициализирующим вектором.

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

Эта атака является разновидностью дифференциальной атаки, которая, в отличие от других атак этого типа, использует целочисленное вычитание а не XOR в качестве меры разности. При поиске коллизий используется метод модификации сообщений: сначала выбирается произвольное сообщение M₀, далее оно модифицируется по некоторым правилам, сформулированным в статье, после чего вычисляется дифференциал хеш-функции, причём с вероятностью 2⁻³⁷. К и применяется функция сжатия для проверки условий коллизии; далее выбирается произвольное , модифицируется, вычисляется новый дифференциал, равный нулю с вероятностью 2⁻³⁰, а равенство нулю дифференциала хеш-функции как раз означает наличие коллизии. Оказалось, что найдя одну пару и , можно менять лишь два последних слова в , тогда для нахождения новой пары и требуется всего около 2³⁹ операций хеширования.

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

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

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

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

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

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

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

Пароли хранятся как есть. При взломе такой базы все пароли станут известны.
Хранятся только хеши паролей (с помощью MD5, SHA). Найти пароли можно только полным перебором. Но при условии использования несложного, популярного или просто несчастливого пароля (который встречался ранее и занесён в таблицу) такая задача решается за доли секунды. Пароль из таблицы был найден всего за 0,036059 сек.^[12]
Хранятся хеши паролей и несколько случайных символов. К каждому паролю добавляется несколько случайных символов (их ещё называют «salt» или «соль») и результат ещё раз хешируется. Например, md5(md5(pass)+word). Найти пароль с помощью таблиц таким методом не получится.

Пример базы данных
способ	id	login	password
1	5	anton	mydata
2	5	anton	md5(mydata)
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.

См. также

Md5sum (программа)

Примечания

↑ What are MD2, MD4, and MD5? (англ.). RSA Laboratories (2000). Архивировано из первоисточника 24 августа 2011. Проверено 11 июля 2009.
The MD5 Message-Digest Algorithm (рус.) (апрель 1992). Архивировано из первоисточника 24 августа 2011. Проверено 19 ноября 2008.

↑ Иными словами, в таблице представлены по 32 бита после десятичной запятой от значений функции sin.

PasswordsPro. InsidePro Software. — Программа для восстановления паролей к хешам различных типов. Архивировано из первоисточника 24 августа 2011. Проверено 19 ноября 2008.

Проект MD5 на сайте SourceForge.net

↑ CERIAS — Security Archive. Center for Education and Research in Information Assurance and Security (июнь 2000). Проверено 19 ноября 2008.

Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (англ.) (17 августа 2004). Архивировано из первоисточника 24 августа 2011. Проверено 19 ноября 2008.

Musings on the Wang et al. MD5 Collision (англ.) (13 октября 2004). Архивировано из первоисточника 24 августа 2011. Проверено 19 ноября 2008.

Tunnels in Hash Functions: MD5 Collisions Within a Minute (англ.) (17 апреля 2006). Архивировано из первоисточника 24 августа 2011. Проверено 19 ноября 2008.

MD5 collisions (англ.). Архивировано из первоисточника 24 августа 2011. Проверено 19 ноября 2008.

Руководство FreeBSD (DES, MD5 и шифрование) (2006). Архивировано из первоисточника 24 августа 2011. Проверено 20 ноября 2008.

An Online MD5 Hash Database. Архивировано из первоисточника 24 августа 2011. Проверено 20 ноября 2008.

Ссылки

RFC 1321

API и известные библиотеки для генерации MD5

Си: Reference Implementation в стандарте RFC 1321 от RSA Security (англ.)

http://java.sun.com/j2se/1.4.2/docs/api/java/security/MessageDigest.html — Java Cryptography Architecture

Реализация MD5 от Пола Джонсона

Cryptographic Services

Digest::MD5

md5() function

реализация функции для получения md5 хэша

MD5 Homepage (unofficial) — Неофициальный ресурс по MD5 содержащий реализации под большое количество различных языков и платформ

Хеш-функции

Хеш-функции общего назначения

Adler-32 • CRC • FNV • Murmur2 • PJW-32 • TTH • Jenkins hash

Криптографические хеш-функции

JH • HAVAL • Keccak • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94

Lt304888.ru

Туристические услуги

Рекомендуем

MD5