Просмотр кода страницы MD5

{{Карточка хеш-функции
|название      = MD5
|изображение   = 
|создатель     = [[Ривест, Рональд|Рональд Ривест]]
|создан        = [[1991]] г.
|опубликован   = апрель [[1992]] г.
|стандарты     = RFC 1321
|преемник      = [[SHA-2]]
|размер хеша   = 128 бит
|число раундов = 4
|тип           = [[хеш-функция]]
}}

'''MD5''' ({{lang-en|Message Digest 5}}) — {{s|128-битный}} алгоритм [[хеширование|хеширования]], разработанный профессором [[Ривест, Рональд|Рональдом Л. Ривестом]] из [[Массачусетский технологический институт|Массачусетского технологического института]] (Massachusetts Institute of Technology, MIT) в [[1991 год]]у. Предназначен для создания «отпечатков» или [[дайджест сообщения|дайджестов сообщения]] произвольной длины и последующей проверки их подлинности. Широко применялся для проверки [[Целостность информации|целостности информации]] и хранения хешей паролей.

== История ==
MD5 — один из серии алгоритмов по построению [[Дайджест сообщения|дайджеста сообщения]], разработанный профессором [[Ривест, Рональд|Рональдом Л. Ривестом]] из Массачусетского технологического института. Был разработан в 1991 году как более надёжный вариант предыдущего алгоритма [[MD4]]<ref name="rsa faq">{{cite web
 |publisher   = RSA Laboratories
 |date        = 2000
 |url         = http://www.rsa.com/rsalabs/node.asp?id=2253
 |title       = What are MD2, MD4, and MD5?
 |lang        = en
 |accessdate  = 2009-07-11
 |archiveurl  = https://www.webcitation.org/61AADFziE?url=http://www.rsa.com/rsalabs/node.asp?id=2253
 |archivedate = 2011-08-23
 |deadurl     = yes
}}</ref>. Описан в RFC 1321{{sfn|Rivest|1992}}. Позже [[Доббертин, Ганс|Гансом Доббертином]] были найдены недостатки алгоритма MD4.

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

В 1996 году Ганс Доббертин (Hans Dobbertin) объявил о коллизии в алгоритме<ref name=":2" />, и уже в то время было предложено использовать другие алгоритмы хеширования, такие как [[Whirlpool (хеш-функция)|Whirlpool]], [[SHA-1]] или [[RIPEMD-160]].

Из-за небольшого размера хеша в 128 бит можно рассматривать [[Атака «дней рождения»|birthday-атаки]]. В марте 2004 года был запущен проект MD5CRK с целью обнаружения уязвимостей алгоритма, при помощи [[Атака «дней рождения»|birthday-атаки]]. Проект MD5CRK закончился 17 августа 2004 года, когда [[Ван Сяоюнь]] (Wang Xiaoyun), Фэн Дэнго (Feng Dengguo), [[Лай Сюэцзя]] (Lai Xuejia) и Юй Хунбо (Yu Hongbo) обнаружили уязвимости в алгоритме<ref name=":0" />.

1 марта 2005 года [[Ленстра, Арьен|Арьен Ленстра]], Ван Сяоюнь и Бенне де Вегер продемонстрировали построение двух документов [[X.509]] с различными открытыми ключами и одинаковым хешем MD5<ref>{{Cite web|url = http://eprint.iacr.org/2005/067.pdf|title = Colliding X.509 Certificates|author = Arjen Lenstra, Xiaoyun Wang and Benne de Weger|work = eprint.iacr.org|date = 2005-03-01|publisher = |access-date = 2015-12-04|archive-date = 2016-03-04|archive-url = https://web.archive.org/web/20160304205816/http://eprint.iacr.org/2005/067.pdf|deadlink = no}}</ref>.

18 марта 2006 года исследователь [[Клима, Властимил|Властимил Клима]] (Vlastimil Klima) опубликовал алгоритм, который может найти коллизии за одну минуту на обычном компьютере, метод получил название «туннелирование»<ref name=":3" />.

В конце 2008 года [[US-CERT]] призвал разработчиков программного обеспечения, владельцев веб-сайтов и пользователей прекратить использовать MD5 в любых целях, так как исследования продемонстрировали ненадёжность этого алгоритма<ref name="USCERT">{{cite web
 |url          = https://www.kb.cert.org/vuls/id/836068
 |title        = CERT Vulnerability Note VU#836068
 |date         = 2008-12-30
 |publisher    = kb.cert.org
 |accessdate   = 2015-10-10
 |lang         = en
 |archive-date = 2011-07-26
 |archive-url  = https://web.archive.org/web/20110726144513/http://www.kb.cert.org/vuls/id/836068
 |deadlink     = no
}}</ref>.

24 декабря 2010 года Тао Се (Tao Xie) и Фэн Дэнго (Feng Dengguo) впервые представили коллизию сообщений длиной в один блок (512 бит)<ref>{{cite web
|url=http://eprint.iacr.org/2010/643
|title=Construct MD5 Collisions Using Just A Single Block Of Message
|date=2010-12-16
|format=PDF
|author=Tao Xie, Dengguo Feng
|accessdate=2015-10-16
|archive-date=2017-05-14
|archive-url=https://web.archive.org/web/20170514185806/http://eprint.iacr.org/2010/643
|deadlink=no
}}</ref>.
Ранее коллизии были найдены для сообщений длиной в два блока и более. Позднее Марк Стивенс (Marc Stevens) повторил успех, опубликовав блоки с одинаковым хешем MD5, а также алгоритм для получения таких коллизий<ref>{{cite web 
|url= http://marc-stevens.nl/research/md5-1block-collision/ 
|title= Marc Stevens – Research – Single-block collision attack on MD5 
|publisher= Marc-stevens.nl 
|date= 2012 
|accessdate= 2015-10-16 
|archive-date= 2017-05-15 
|archive-url= https://web.archive.org/web/20170515070731/http://marc-stevens.nl/research/md5-1block-collision/ 
|deadlink= no 
}}</ref>.

В 2011 году был опубликован информационный документ RFC 6151. Он признаёт алгоритм хеширования MD5{{sfn|Rivest|1992}} небезопасным для некоторых целей и рекомендует отказаться от его использования в пользу SHA-2.

== Алгоритм MD5 ==
[[Файл:MD5.png|thumbnail|300px| Схема работы алгоритма MD5. F — нелинейная функция. ''M<sub>i</sub>'' обозначает 32-битный блок входного сообщения, а ''K<sub>i</sub>'' — 32-битную константу. <<<<sub>''s''</sub> обозначает [[Битовый сдвиг#Циклический сдвиг|циклический сдвиг влево]] на ''s'' бит. <math>\boxplus</math> обозначает сложение по модулю 2<sup>32</sup>. F зависит от раунда, ''K<sub>i</sub>'' и ''s'' меняются каждую операцию''.'']]
На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Длина сообщения измеряется в битах и может быть любой (в том числе нулевой). Запишем длину сообщения в ''L''. Это число целое и неотрицательное. Кратность каким-либо числам необязательна. После поступления данных идёт процесс подготовки потока к вычислениям.

Ниже приведены 5 шагов алгоритма{{sfn|Rivest|1992}}:

=== Шаг 1. Выравнивание потока ===
Сначала к концу потока дописывают единичный бит.

Затем добавляют некоторое число нулевых бит такое, чтобы новая длина потока <math>L'</math> стала [[Сравнение по модулю натурального числа|сравнима]] с 448 по модулю 512, (<math>L' = 512 \times N + 448</math>).
Выравнивание происходит в любом случае, даже если длина исходного потока уже сравнима с 448.

=== Шаг 2. Добавление длины сообщения ===
В конец сообщения дописывают 64-битное представление длины данных (количество бит в сообщении) до выравнивания. '''Сначала записывают младшие 4 байта, затем старшие.''' Если длина превосходит <math>2^{64}-1</math>, то дописывают только младшие биты (эквивалентно взятию по модулю <math>2^{64}</math>). После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.

=== Шаг 3. Инициализация буфера ===
Для вычислений инициализируются четыре переменные размером по 32 бита, начальные значения которых задаются шестнадцатеричными числами (порядок байтов [[Порядок байтов#Порядок от младшего к старшему|little-endian]]):
 А = 01 23 45 67; // 67452301h
 В = 89 AB CD EF; // EFCDAB89h
 С = FE DC BA 98; // 98BADCFEh
 D = 76 54 32 10. // 10325476h
В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется инициализирующим вектором.

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

* Для каждого раунда потребуется своя функция. Введём функции от трёх параметров — слов, результатом также будет слово:

: 1-й этап: <math>\operatorname{Fun F}(X,Y,Z) = (X \wedge Y) \vee (\neg X \wedge Z)</math>,
: 2-й этап: <math>\operatorname{Fun G}(X,Y,Z) = (X \wedge Z) \vee (\neg Z \wedge Y)</math>,
: 3-й этап: <math>\operatorname{Fun H}(X,Y,Z) = X \oplus Y \oplus Z</math>,
: 4-й этап: <math>\operatorname{Fun I}(X,Y,Z) = Y \oplus (\neg{Z} \vee X)</math>,
: где <math>\oplus, \wedge, \vee, \neg</math> побитовые логические операции [[XOR]], [[AND]], [[OR]] и [[NOT]] соответственно.
* Определим таблицу констант <math>T[1\ldots64]</math> — 64-элементная таблица данных, построенная следующим образом: <math>T[n] = \operatorname{int}(2^{32} \cdot |\sin n|)</math><ref>Иными словами, в таблице представлены по 32 бита после десятичной запятой от значений функции [[sin]], где аргумент n в радианах.</ref>.
* Каждый 512-битный блок проходит 4 этапа вычислений по 16 раундов. Для этого блок представляется в виде массива ''X'' из 16 слов по 32 бита. Все раунды однотипны и имеют вид: [abcd k s i], определяемый как <math>a = b + ((a + \operatorname{Fun}(b, c, d) + X[k] + T[i]) \lll s)</math>, где ''k'' — номер 32-битного слова из текущего 512-битного блока сообщения, и <math>\ldots \lll s</math> — циклический сдвиг влево на ''s'' бит полученного 32-битного аргумента. Число ''s'' задается отдельно для каждого раунда.

Заносим в блок данных элемент ''n'' из массива 512-битных блоков. Сохраняются значения 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'' + 1) и повторяем цикл.

=== Шаг 5. Результат вычислений ===
Результат вычислений находится в буфере ABCD, это и есть хеш. Если выводить побайтово, начиная с младшего байта A и заканчивая старшим байтом D, то мы получим MD5-хеш.
1, 0, 15, 34, 17, 18…

=== [[Псевдокод (язык описания алгоритмов)|Псевдокод]] ===
<syntaxhighlight lang="pascal">
// Все переменные — 32-битные беззнаковые целые. Все сложения выполняются по модулю 2^32.

var int s[64], K[64]
var int i

// s обозначает величины сдвигов для каждой операции:
s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }

// Определяем таблицу констант следующим образом
for i from 0 to 63 do
    K[i] := floor(2^32 × abs (sin(i + 1)))
end for
// (Или просто используем заранее подсчитанные значения):
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

// Инициализация переменных:
var int a0 := 0x67452301   // A
var int b0 := 0xefcdab89   // B
var int c0 := 0x98badcfe   // C
var int d0 := 0x10325476   // D

// Подготовка: добавляем бит "1" в конец сообщения.
append "1" bit to message    
 // Заметка: входные байты представлены строкой из бит,
 // причем первый бит — старший (big-endian).

// Подготовка: дописываем нулевые биты, пока длина сообщения не станет сравнима с 448 по модулю 512
append "0" bit until message length in bits ≡ 448 (mod 512)
// Дописываем остаток от деления изначальной длины сообщения на 2^64
append original length in bits mod 2^64 to message

// Разбиваем подготовленное сообщение на 512-битные "куски":
for each 512-bit chunk of padded message do
    // и работаем с каждым по отдельности
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15 // разбиваем "кусок" на 16 блоков по 32 бита
    // Инициализируем переменные для текущего куска:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
    // Основные операции:
    for i from 0 to 63 do
        var int F, g
        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31 then
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47 then
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63 then
            F := C xor (B or (not D))
            g := (7×i) mod 16
        F := F + A + K[i] + M[g]  // M[g] — 32 битный блок
        A := D
        D := C
        C := B
        B := B + (F <<< s[i]) // Выполняем битовый сдвиг
    end for
    // Прибавляем результат текущего "куска" к общему результату
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 // (Результат в формате little-endian)

</syntaxhighlight>Результат вычислений на примере языка программирования Python<syntaxhighlight lang="python" line="1">
import hashlib
import math
k:int
r:int
def left_rotate(n, b):
    return ((n << b) | (n >> (32 - b))) & 0xffffffff

def md5(message):
    a0 = 0x67452301
    b0 = 0xefcdab89
    c0 = 0x98badcfe
    d0 = 0x10325476

    ml = len(message) * 8
    message = bytearray(message)
    message.append(0x80)

    while len(message) % 64 != 56:
        message.append(0)

    message += ml.to_bytes(8, byteorder='little')

    for i in range(0, len(message), 64):
        chunk = message[i:i+64]

        a = a0
        b = b0
        c = c0
        d = d0

        # Main loop
        for j in range(64):
            if 0 <= j <= 15:
                f = (b & c) | ((~b) & d)
                g = j
            elif 16 <= j <= 31:
                f = (d & b) | ((~d) & c)
                g = (5*j + 1) % 16
            elif 32 <= j <= 47:
                f = b ^ c ^ d
                g = (3*j + 5) % 16
            elif 48 <= j <= 63:
                f = c ^ (b | (~d))
                g = (7*j) % 16

            d_temp = d
            d = c
            c = b
            b = (b + left_rotate((a + f + k[j] + int.from_bytes(chunk[4*g:4*(g+1)], byteorder='little')), r[j])) & 0xffffffff
            a = d_temp

        a0 = (a0 + a) & 0xffffffff
        b0 = (b0 + b) & 0xffffffff
        c0 = (c0 + c) & 0xffffffff
        d0 = (d0 + d) & 0xffffffff

    return '{:08x}{:08x}{:08x}{:08x}'.format(a0, b0, c0, d0)

# Пример использования:
import hashlib
message = "Hello, world!"
result = hashlib.md5(message.encode()).hexdigest()
print("MD5 хэш (hashlib):", result)

def md5(message):
    # Constants
    T = [int(abs(math.sin(i+1)) * 2**32) & 0xFFFFFFFF for i in range(64)]
    s = [[7, 12, 17, 22]] * 4 + [[5, 9, 14, 20]] * 4 + [[4, 11, 16, 23]] * 4 + [[6, 10, 15, 21]] * 4

    # Initialize variables
    A, B, C, D = 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476
    message = bytearray(message)
    length = (8 * len(message)) & 0xFFFFFFFFFFFFFFFF
    message.append(0x80)
    while len(message) % 64 != 56:
        message.append(0x00)
    message.extend(length.to_bytes(8, byteorder='little'))

    # Process message in 16-word blocks
    for i in range(0, len(message), 64):
        X = [int.from_bytes(message[i:i+4], byteorder='little') for i in range(i, i+64, 4)]
        A_, B_, C_, D_ = A, B, C, D

        # Main loop
        for j in range(64):
            if j < 16:
                F = (B & C) | ((~B) & D)
                F_index = j
            elif j < 32:
                F = (D & B) | ((~D) & C)
                F_index = (5 * j + 1) % 16
            elif j < 48:
                F = B ^ C ^ D
                F_index = (3 * j + 5) % 16
            else:
                F = C ^ (B | (~D))
                F_index = (7 * j) % 16

            dTemp = D
            D = C
            C = B
            B = B + left_rotate((A + F + T[j] + X[F_index]) & 0xFFFFFFFF, s[j % 4][j % 4])
            A = dTemp

        # Update state
        A = (A + A_) & 0xFFFFFFFF
        B = (B + B_) & 0xFFFFFFFF
        C = (C + C_) & 0xFFFFFFFF
        D = (D + D_) & 0xFFFFFFFF

    # Output
    result = bytearray(A.to_bytes(4, byteorder='little'))
    result.extend(B.to_bytes(4, byteorder='little'))
    result.extend(C.to_bytes(4, byteorder='little'))
    result.extend(D.to_bytes(4, byteorder='little'))
    return result.hex()

result = md5(message.encode())
print("MD5 хэш (самостоятельная реализация):", result)

</syntaxhighlight>

=== Сравнение MD5 и MD4 ===
Алгоритм MD5 происходит от MD4. В новый алгоритм добавили ещё один раунд, теперь их стало 4 вместо 3 в MD4. Добавили новую константу для того, чтобы свести к минимуму влияние входного сообщения, в каждом раунде на каждом шаге и каждый раз константа разная, она суммируется с результатом F и блоком данных. Изменилась функция <math>G = XZ \vee (Y \neg Z)</math> вместо <math>XY \vee XZ \vee YZ</math>. Результат каждого шага складывается с результатом предыдущего шага, из-за этого происходит более быстрое изменение результата. Для этой же цели оптимизирована величина сдвига на каждом круге. Изменился порядок работы с входными словами в раундах 2 и 3{{sfn|Rivest|1992}}.

== Примеры MD5-хешей ==
Хеш содержит 128 бит (16 байт) и обычно представляется как последовательность из 32 [[Шестнадцатеричная система счисления|шестнадцатеричных]] цифр<ref>{{cite web 
|url=http://interscience.in/IJCNS_Vol1Iss2/paper3.pdf 
|title=Detection Of Phishing Websites And Secure Transactions 
|publisher=Anna University 
|date=2012 
|accessdate=2015-10-20 
|archive-date=2016-03-04 
|archive-url=https://web.archive.org/web/20160304092343/http://interscience.in/IJCNS_Vol1Iss2/paper3.pdf 
|deadlink=yes 
}}</ref>.

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

  MD5("md5") = 1BC29B36F623BA82AAF6724FD3B16718

Даже небольшое изменение входного сообщения (в нашем случае на один бит: ASCII символ «5» с кодом 35<sub>16</sub> = 00011010'''1'''<sub>2</sub> заменяется на символ «4» с кодом 34<sub>16</sub> = 00011010'''0'''<sub>2</sub>) приводит к полному изменению хеша. Такое свойство алгоритма называется [[лавинный эффект|лавинным эффектом]].

  MD5("md4") = C93D3BF7A7C4AFE94B64E30C2CE39F4F

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

  MD5("") = D41D8CD98F00B204E9800998ECF8427E

== Криптоанализ ==
На данный момент существуют несколько видов «взлома» хешей MD5 — подбора сообщения с заданным хешем{{sfn|Ah Kioon, Wang, Deb Das|2013}}<ref name="RFC6151" />:
* [[Перебор по словарю]]
* [[Brute-force]]
* [[RainbowCrack]]
* [[Коллизия хеш-функции]]
При этом методы перебора по словарю и brute-force могут использоваться для взлома хеша других хеш-функций (с небольшими изменениями алгоритма). В отличие от них, RainbowCrack требует предварительной подготовки [[радужная таблица|радужных таблиц]], которые создаются для заранее определённой хеш-функции. Поиск коллизий специфичен для каждого алгоритма.

=== Атаки переборного типа ===
Для [[полный перебор|полного перебора]] или перебора по словарю можно использовать программы [[PasswordsPro]]<ref>{{cite web
 |url         = http://www.insidepro.com/rus/passwordspro.shtml
 |title       = PasswordsPro
 |publisher   = InsidePro Software
 |accessdate  = 2008-11-19
 |description = Программа для восстановления паролей к хешам различных типов
 |archiveurl  = https://web.archive.org/web/20110827033811/http://www.insidepro.com/rus/passwordspro.shtml
 |archivedate = 2011-08-27
 |deadlink    = yes
}}</ref>, [[MD5BFCPF]]<ref>{{sourceforge|md5bfcpf}}</ref>, [[John the Ripper]], [[Hashcat]]. Для перебора по словарю существуют готовые словари<ref>{{cite web
 | url = ftp://ftp.cerias.purdue.edu/pub/dict/
 | title = CERIAS — Security Archive
 | publisher = Center for Education and Research in Information Assurance and Security
 | datepublished = 2000-06
 | accessdate = 2008-11-19
 | archive-date = 2008-12-07
 | archive-url = https://web.archive.org/web/20081207033141/http://ftp.cerias.purdue.edu/pub/dict/
 | deadlink = no
 }}</ref>. Основным недостатком такого типа атак является высокая вычислительная сложность.

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

=== Коллизии MD5 ===
[[Коллизия хеш-функции]] — это получение одинакового значения функции для разных сообщений и идентичного начального буфера. В отличие от коллизий, ''псевдоколлизии'' определяются как равные значения хеша для разных значений начального буфера, причём сами сообщения могут совпадать или различаться. В MD5 вопрос коллизий не решается<ref name="RFC6151">{{cite web
|url=https://tools.ietf.org/html/rfc6151
|title=Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms
|publisher=Internet Engineering Task Force
|date=2011-03
|accessdate=2015-10-23
|archive-date=2017-06-15
|archive-url=https://web.archive.org/web/20170615213134/https://tools.ietf.org/html///rfc6151
|deadlink=no
}}</ref>.

В 1996 году [[Доббертин, Ганс|Ганс Доббертин]] нашёл псевдоколлизии в MD5, используя определённые ''инициализирующие'' векторы, отличные от стандартных. Оказалось, что можно для известного сообщения построить второе, такое, что оно будет иметь такой же хеш, как и исходное. C точки зрения математики это означает: MD5(IV,L1) = MD5(IV,L2), где IV — начальное значение буфера, а L1 и L2 — различные сообщения. Например, если взять начальное значение буфера<ref name=":2">{{cite web
 | url         = ftp://ftp.arnes.si/packages/crypto-tools/rsa.com/cryptobytes/crypto2n2.pdf.gz
 | title       = The Status of MD5 After a Recent Attack
 | author      = Hans Dobbertin 
 | accessdate  = 2015-10-22
}}</ref>:
 A = 0x12AC2375
 В = 0x3B341042
 C = 0x5F62B97C
 D = 0x4BA763E 
и задать входное сообщение
{| class="wikitable"
|<tt>AA1DDABE</tt> ||<tt>D97ABFF5</tt> ||<tt>BBF0E1C1</tt> ||<tt>32774244</tt>
|-
|<tt>1006363E</tt> ||<tt>7218209D</tt> ||<tt>E01C136D</tt> ||<tt>9DA64D0E</tt>
|-
|<tt>98A1FB19</tt> ||<tt>1FAE44B0</tt> ||<tt>236BB992</tt> ||<tt>6B7A779B</tt>
|-
|<tt>1326ED65</tt> ||<tt>D93E0972</tt> ||<tt>D458C868</tt> ||<tt>6B72746A</tt>
|}
то, добавляя число <math>2^9</math> к определённому 32-разрядному слову в блочном буфере, можно получить второе сообщение с таким же хешем. Ханс Доббертин представил такую формулу:
: <math>L2_i=\begin{cases} L1_i, & i\ne 14;\\ L1_i + 2^9,  & i = 14. \end{cases}</math>

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

В 2004 году китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фэн Дэнго (Feng Dengguo), [[Лай Сюэцзя]] (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на [[Кластер (группа компьютеров)|кластере]] [[System p|IBM p690]]) находить коллизии<ref name=":0">{{cite web
 |author        = Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu.
 |datepublished = 2004-08-17
 |url           = http://eprint.iacr.org/2004/199
 |title         = Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD
 |lang          = en
 |accessdate    = 2008-11-19
 |archiveurl    = https://www.webcitation.org/61AAF4PT7?url=http://eprint.iacr.org/2004/199
 |archivedate   = 2011-08-23
 |deadurl       = yes
}}</ref><ref>{{cite web
 |author        = Philip Hawkes, Michael Paddon, Gregory G. Rose.
 |datepublished = 2004-10-13
 |url           = http://eprint.iacr.org/2004/264
 |title         = Musings on the Wang  et al. MD5 Collision
 |lang          = en
 |accessdate    = 2008-11-19
 |archiveurl    = https://www.webcitation.org/61AAFVLMw?url=http://eprint.iacr.org/2004/264
 |archivedate   = 2011-08-23
 |deadurl       = yes
}}</ref>.

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

{| class="wikitable"
|<tt>d131dd02c5e6eec4693d9a0698aff95c</tt> ||<tt>2fcab5'''{{Background color|#87CEEB|8}}'''712467eab4004583eb8fb7f89</tt>
|-
|<tt>55ad340609f4b30283e4888325'''{{Background color|#87CEEB|7}}'''1415a</tt> ||<tt>085125e8f7cdc99fd91dbd'''{{Background color|#87CEEB|f}}'''280373c5b</tt>
|-
|<tt>d8823e3156348f5bae6dacd436c919c6</tt> ||<tt>dd53e2'''{{Background color|#87CEEB|b}}'''487da03fd02396306d248cda0</tt>
|-
|<tt>e99f33420f577ee8ce54b67080'''{{Background color|#87CEEB|a}}'''80d1e</tt> ||<tt>c69821bcb6a8839396f965'''{{Background color|#87CEEB|2}}'''b6ff72a70</tt>
|}

и

{| class="wikitable"
|<tt>d131dd02c5e6eec4693d9a0698aff95c</tt> ||<tt>2fcab5'''{{Background color|#87CEEB|0}}'''712467eab4004583eb8fb7f89</tt>
|-
|<tt>55ad340609f4b30283e4888325'''{{Background color|#87CEEB|f}}'''1415a</tt> ||<tt>085125e8f7cdc99fd91dbd'''{{Background color|#87CEEB|7}}'''280373c5b</tt>
|-
|<tt>d8823e3156348f5bae6dacd436c919c6</tt> ||<tt>dd53e2'''{{Background color|#87CEEB|3}}'''487da03fd02396306d248cda0</tt>
|-
|<tt>e99f33420f577ee8ce54b67080'''{{Background color|#87CEEB|2}}'''80d1e</tt> ||<tt>c69821bcb6a8839396f965'''{{Background color|#87CEEB|a}}'''b6ff72a70</tt>
|}

Каждый из этих блоков даёт MD5-хеш, равный 79054025255fb1a26e4bc422aef54eb4{{sfn|Wang, Yu|2005}}.

В 2006 году чешский исследователь Властимил Клима опубликовал алгоритм, позволяющий находить [[Коллизия хеш-функции|коллизии]] на обычном компьютере с любым начальным вектором (A,B,C,D) при помощи метода, названного им «[[туннелирование (метод)|туннелирование]]»<ref name=":3">{{cite web
 |author        = Vlastimil Kli'ma.
 |datepublished = 2006-04-17
 |url           = http://eprint.iacr.org/2006/105
 |title         = Tunnels in Hash Functions: MD5 Collisions Within a Minute
 |lang          = en
 |accessdate    = 2008-11-19
 |archiveurl    = https://www.webcitation.org/61AAFv2q7?url=http://eprint.iacr.org/2006/105
 |archivedate   = 2011-08-23
 |deadurl       = yes
}}</ref><ref>{{cite web
 |author      = Vlastimil Klima.
 |url         = http://cryptography.hyperlink.cz/MD5_collisions.html
 |title       = MD5 collisions
 |lang        = en
 |accessdate  = 2008-11-19
 |archiveurl  = https://www.webcitation.org/61AAGKcF4?url=http://cryptography.hyperlink.cz/MD5_collisions.html
 |archivedate = 2011-08-23
 |deadurl     = yes
}}</ref>.

Алгоритм MD5 использует итерационный [[Структура Меркла — Дамгора|метод Меркла — Дамгора]], поэтому становится возможным построение коллизий с одинаковым, заранее выбранным префиксом. Аналогично, коллизии получаются при добавлении одинакового суффикса к двум различным префиксам, имеющим одинаковый хеш. В 2009 году было показано, что для любых двух заранее выбранных префиксов можно найти специальные суффиксы, с которыми сообщения будут иметь одинаковое значение хеша. Сложность такой атаки составляет всего 2<sup>39</sup> операций подсчёта хеша{{sfn|Stevens, Lenstra, Weger|2012}}.

==== Метод Ван Сяоюня и Юй Хунбо ====
Метод {{iw|Ван Сяоюнь|Ван Сяоюня|en|Xiaoyun Wang}} и [[Юй Хунбо]] использует тот факт, что MD5 построен на итерационном методе Меркла — Дамгора. Поданный на вход файл сначала дополняется, так чтобы его длина была кратна 64 байтам, после этого он делится на блоки по 64 байта каждый <math>M_0</math>, <math>M_1</math>, <math>\dots{}</math>, <math>M_{n-1}</math>. Далее вычисляется последовательность 16-байтных состояний
<math>s_0</math>, <math>\dots{}</math>, <math>s_n</math> по правилу
<math>s_{i+1} = f\left(s_i, M_i\right)</math>, где <math>f</math> — некоторая фиксированная функция. Начальное состояние <math>s_0</math> называется ''инициализирующим вектором''.

Метод позволяет для заданного инициализирующего вектора найти две пары <math>M,M'</math> и <math>N,N'</math>, такие что <math>f(f(s,M),M')=f(f(s,N),N')</math>. Этот метод работает для любого инициализирующего вектора, а не только для вектора используемого по стандарту.

Эта атака является разновидностью ''[[Дифференциальный криптоанализ|дифференциальной]]'' атаки, которая, в отличие от других атак этого типа, использует целочисленное вычитание, а не [[Сложение по модулю 2|XOR]] в качестве меры разности. При поиске коллизий используется метод модификации сообщений: сначала выбирается произвольное сообщение <math>M_0</math>, далее оно модифицируется по некоторым правилам, сформулированным в статье, после чего вычисляется дифференциал хеш-функции, причём <math>M'_0=M_0+dM_0</math> с вероятностью <math>{2}^{-37}</math>. К <math>M_0</math> и <math>M'_0</math> применяется функция сжатия для проверки условий коллизии; далее выбирается произвольное <math>M_1</math>, модифицируется, вычисляется новый дифференциал, равный нулю с вероятностью <math>{2}^{-30}</math>, а равенство нулю дифференциала хеш-функции как раз означает наличие коллизии. Оказалось, что найдя одну пару <math>M_0</math> и <math>M'_0</math>, можно менять лишь два последних слова в <math>M_0</math>, тогда для нахождения новой пары <math>M_1</math> и <math>M'_1</math> требуется всего около <math>{2}^{39}</math> операций хеширования{{sfn|Wang, Yu|2005}}.

Применение этой атаки к [[MD4]] позволяет найти коллизию меньше чем за секунду. Она также применима к другим хеш-функциям, таким как [[RIPEMD-160|RIPEMD]] и [[HAVAL]]<ref name=":0" />.

== Примеры использования ==
Ранее считалось, что MD5 позволяет получать относительно надёжный идентификатор для блока данных. На данный момент данная хеш-функция не рекомендуется к использованию, так как существуют способы нахождения [[Коллизия хеш-функции|коллизий]] с приемлемой вычислительной сложностью<ref name="RFC6151" /><ref>{{Cite web|url = http://www.win.tue.nl/hashclash/SoftIntCodeSign/|title = Vulnerability of software integrity and code signing applications to chosen-prefix collisions for MD5|author = Marc Stevens, Arjen Lenstra and Benne de Weger|work = |date = 2007-11-30|publisher = |access-date = 2015-10-25|archive-date = 2007-12-13|archive-url = https://web.archive.org/web/20071213023720/http://www.win.tue.nl/hashclash/SoftIntCodeSign/|deadlink = no}}</ref>.

Свойство уникальности хеша широко применяется в разных областях<ref>{{Cite web|url = http://research.microsoft.com/pubs/64588/hash_survey.pdf|title = Hash functions: Theory, attacks, and applications|author = Ilya Mironov|work = Microsoft Research|date = 2005-11-14|publisher = |access-date = 2015-11-13|archive-date = 2016-03-04|archive-url = https://web.archive.org/web/20160304022937/http://research.microsoft.com/pubs/64588/hash_survey.pdf|deadlink = no}}</ref>. Приведенные примеры относятся и к другим [[Криптографическая хеш-функция#Применения|криптографическим хеш-функциям]].

С помощью MD5 проверяли целостность и подлинность скачанных файлов — так, некоторые программы поставляются вместе со значением [[Контрольная сумма|контрольной суммы]]. Например, пакеты для инсталляции свободного ПО{{source-ref|Q21694367|pages=57—58}}.

MD5 использовался для хеширования паролей. В системе [[UNIX]] каждый пользователь имеет свой пароль и его знает только пользователь. Для защиты паролей используется хеширование. Предполагалось, что получить настоящий пароль можно только полным перебором. При появлении [[UNIX]] единственным способом хеширования был [[DES]] (Data Encryption Standard), но им могли пользоваться только жители [[США]], потому что исходные коды [[DES]] нельзя было вывозить из страны. Во [[FreeBSD]] решили эту проблему. Пользователи [[США]] могли использовать библиотеку [[DES]], а остальные пользователи имеют метод, разрешённый для экспорта. Поэтому в [[FreeBSD]] стали использовать MD5 по умолчанию<ref>{{cite web
 |author        = Bill Swingle.
 |datepublished = 2006
 |url           = http://www.nbuv.gov.ua/books/2004/freebsd/crypt.html
 |title         = Руководство FreeBSD (DES, MD5 и шифрование)
 |accessdate    = 2008-11-20
 |deadurl       = yes
 |archive-date  = 2009-09-17
 |archive-url   = https://web.archive.org/web/20090917074507/http://www.nbuv.gov.ua/books/2004/freebsd/crypt.html
}}</ref>. Некоторые [[Linux]]-системы также используют MD5 для хранения паролей<ref>{{Книга|автор = Vicki Stanfield, Roderick W. Smith|заглавие = Linux System Administration (Craig Hunt Linux Library)|ответственный = |издание = 2|место = |издательство = Sybex|год = 2002|страницы = 479—483|страниц = 656|isbn = 978-0782141382}}</ref>.

Многие системы используют базы данных для аутентификации пользователей и существует несколько способов хранения паролей<ref>{{Книга|автор = Hossein Bidgoli|заглавие = The Internet Encyclopedia, Volume 3|ответственный = |издание = 1|место = |издательство = Wiley|год = 2003|страницы = 3—4|страниц = 908|isbn = 978-0471222019}}</ref>:
# Пароли хранятся как есть. При взломе такой базы все пароли станут известны.
# Хранятся только хеши паролей. Найти пароли можно, используя заранее подготовленные таблицы хешей. Такие таблицы составляются из хешей простых или популярных паролей.
# К каждому паролю добавляется несколько случайных символов (их называют «[[Соль (криптография)|соль]]») и результат хешируется. Полученный хеш вместе с «солью» сохраняются в открытом виде. Найти пароль с помощью таблиц таким методом не получится.

Существует несколько надстроек над MD5.
* MD5 ([[HMAC]]) — Keyed-Hashing for Message Authentication (хеширование с ключом для аутентификации сообщения) — алгоритм позволяет хешировать входное сообщение L с некоторым ключом K, такое хеширование позволяет аутентифицировать подпись<ref>{{Cite web|accessdate = 2015-12-05|author = Krawczyk, Hugo, Canetti, Ran, Bellare, Mihir|title = HMAC: Keyed-Hashing for Message Authentication|url = https://tools.ietf.org/html/rfc2104|publisher = tools.ietf.org|archive-date = 2021-04-15|archive-url = https://web.archive.org/web/20210415003434/https://tools.ietf.org/html/rfc2104|deadlink = no}}</ref>.
* MD5 ([[Base64]]) — здесь полученный MD5-хеш кодируется алгоритмом Base64.
* MD5 (Unix) — алгоритм вызывает тысячу раз стандартный MD5 для усложнения процесса. Также известен как MD5crypt<ref>{{Cite web|url = http://c59951.r51.cf2.rackcdn.com/4902-1103-alexander.pdf|title = password protection for modern operating systems|author = Steven Alexander|work = USENIX 2004|date = 2004-06|publisher = |access-date = 2015-12-05|archive-date = 2015-12-08|archive-url = https://web.archive.org/web/20151208104416/http://c59951.r51.cf2.rackcdn.com/4902-1103-alexander.pdf|deadlink = no}}</ref>.

== Примечания ==
{{примечания|2}}

== Литература ==
* {{source|Q27036232|ref=Rivest|ref-year=1992}} <!-- RFC 1321: The MD5 Message-Digest Algorithm -->
* {{source|Q21693194|ref=Boer, Bosselaers|ref-year=1993}} <!-- Collisions for the compression function of MD5 // Advances in Cryptology — EUROCRYPT’93 -->
* {{source|Q21898130|ref=Wang, Yu|ref-year=2005}} <!-- How to Break MD5 and Other Hash Functions // Advances in Cryptology — EUROCRYPT 2005 -->
* {{source|Q21694347|ref=Stevens, Lenstra, Weger|ref-year=2012}} <!-- Chosen-prefix collisions for MD5 and applications // International Journal of Applied Cryptography -->
* {{source|Q27031259|ref=Ah Kioon, Wang, Deb Das|ref-year=2013}} <!-- Security Analysis of MD5 Algorithm in Password Storage // Applied Mechanics and Materials -->

{{^}}

== Ссылки ==
* [https://www.md5.cz/ Генератор MD5 хеша из обычного текста]
* [https://www.md5online.org/ База данных простых MD5 хешей] (позволяет произвести обратный декодирование простых MD5 хешей, используя базу данных сгенерированных хешей)
* [https://md5.kz/ Одноимённый образовательный центр в городе Алматы]. Наименование образовательного центра является отсылкой на материал, который используется в нескольких лекциях по [https://md5.kz/?do=kurs-razrabotki-web-saitov направлению WEB разработки]
{{Хеш-алгоритмы}}

[[Категория:Криптографические хеш-функции]]
{{Добротная статья|Теория информации и криптография}}