MD5

MD5

Общий
Дизайнеры	Рональд Ривест
Впервые опубликовано	апрель 1992 г.
Ряд	МД2 , МД4 , МД5, МД6
Деталь шифрования
Размеры дайджеста	128 бит
Размеры блоков	512 бит
Структура	Строительство Меркле – Дамгорда
Раунды	4
Лучший публичный криптоанализ
Атака Се Тао, Фаньбао Лю и Дэнго Фэна в 2013 году преодолела сопротивление столкновению MD5 в 2 раза. 18 время. На обычном компьютере эта атака выполняется менее чем за секунду. MD5 подвержен атакам расширения длины .

Алгоритм дайджеста сообщения MD5 — это широко используемая хеш-функция, создающая 128- битное хэш-значение. MD5 был разработан Рональдом Ривестом в 1991 году для замены более ранней хеш-функции MD4 . и был указан в 1992 году как RFC 1321.

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

История и криптоанализ

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

В 1993 году Ден Бур и Босселерс дали ранний, хотя и ограниченный, результат обнаружения « псевдоколлизии MD5 » функции сжатия ; то есть два разных вектора инициализации , которые создают идентичный дайджест.

В 1996 году Доббертин объявил о коллизии функции сжатия MD5 (Доббертин, 1996). Хотя это не была атака на полную хеш-функцию MD5, она была достаточно близка к тому, чтобы криптографы рекомендовали переключиться на замену, такую ​​как SHA-1 (с тех пор также скомпрометированная) или RIPEMD-160 .

Размер хеш-значения (128 бит) достаточно мал, чтобы можно было предположить атаку на день рождения . MD5CRK — это распределенный проект, начатый в марте 2004 года с целью продемонстрировать, что MD5 практически небезопасен за счет обнаружения коллизий с помощью атаки «день рождения».

MD5CRK завершился вскоре после 17 августа 2004 года, когда о столкновениях и Хунбо Юй объявили Сяоюнь Ван , Дэнго Фэн, Сюэцзя Лай для полного MD5 . Сообщается, что их аналитическая атака на кластере IBM p690 заняла всего один час .

1 марта 2005 года Арьен Ленстра , Сяоюнь Ван и Бенне де Вегер продемонстрировали создание двух сертификатов X.509 с разными открытыми ключами и одинаковым значением хеш-функции MD5, что является очевидным практическим столкновением. В конструкцию включены закрытые ключи для обоих открытых ключей. Несколько дней спустя Властимил Клима описал улучшенный алгоритм, способный создавать коллизии MD5 за несколько часов на одном ноутбуке. 18 марта 2006 года Клима опубликовал алгоритм, который может обнаружить столкновение за одну минуту на одном ноутбуке, используя метод, который он называет туннелированием.

связанные с MD5 различные ошибки RFC, Были опубликованы . В 2009 году Киберкомандование США использовало хеш-значение MD5 своей миссии как часть своей официальной эмблемы.

24 декабря 2010 года Тао Се и Дэнго Фэн объявили о первой опубликованной одноблочной (512-битной) коллизии MD5. (Предыдущие открытия столкновений основывались на многоблочных атаках.) По «соображениям безопасности» Се и Фэн не раскрыли новый метод атаки. Они бросили вызов криптографическому сообществу, предложив вознаграждение в размере 10 000 долларов США тому, кто первым обнаружит другую 64-байтовую коллизию до 1 января 2013 года. Марк Стивенс ответил на вызов и опубликовал конфликтующие одноблочные сообщения, а также алгоритм построения и источники.

В 2011 году информационный RFC 6151. было одобрено для обновления соображений безопасности в MD5 и HMAC-MD5.

Безопасность

Одним из основных требований к любой криптографической хеш-функции является то, что с вычислительной точки зрения невозможно найти два разных сообщения, которые хэшируют одно и то же значение. MD5 катастрофически не соответствует этому требованию. 31 декабря 2008 года Институт программной инженерии CMU пришел к выводу, что MD5 по сути «криптографически взломан и непригоден для дальнейшего использования». Слабые стороны MD5 использовались в полевых условиях, наиболее печально известная вредоносная программа Flame в 2012 году. По состоянию на 2019 год MD5 продолжает широко использоваться, несмотря на его хорошо задокументированные недостатки и неодобрение экспертами по безопасности.

Существует атака коллизий , которая позволяет за секунды обнаружить коллизии на компьютере с процессором Pentium 4 2,6 ГГц (сложность 2 ^24.1 ). Кроме того, существует также атака коллизии выбранного префикса , которая может вызвать коллизию двух входных данных с указанными префиксами в течение нескольких секунд с использованием готового вычислительного оборудования (сложность 2). ³⁹ ). Способности находить коллизии во многом способствовало использование готовых графических процессоров . На графическом процессоре NVIDIA GeForce 8400GS можно вычислить 16–18 миллионов хешей в секунду. NVIDIA GeForce 8800 Ultra может вычислять более 200 миллионов хэшей в секунду.

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

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

Обзор проблем безопасности

В 1996 году в конструкции MD5 был обнаружен недостаток. Хотя в то время это не считалось фатальной слабостью, криптографы начали рекомендовать использование других алгоритмов, таких как SHA-1 , который с тех пор также оказался уязвимым. В 2004 году было показано, что MD5 не устойчив к столкновениям . Таким образом, MD5 не подходит для таких приложений, как SSL сертификаты или цифровые подписи , которые полагаются на это свойство для цифровой безопасности. Исследователи также обнаружили более серьезные недостатки в MD5 и описали возможную коллизионную атаку — метод создания пары входных данных, для которых MD5 выдает идентичные контрольные суммы . Дальнейшие успехи в взломе MD5 были достигнуты в 2005, 2006 и 2007 годах. В декабре 2008 года группа исследователей использовала этот метод для подделки действительности сертификата SSL .

По состоянию на 2010 год Институт программной инженерии CMU считает MD5 «криптографически взломанным и непригодным для дальнейшего использования». и большинству правительственных приложений США теперь требуется семейство хеш-функций SHA-2 . В 2012 году вредоносная программа Flame использовала недостатки MD5 для подделки цифровой подписи Microsoft .

Уязвимости столкновений

Дополнительная информация: Атака столкновения.

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

В 2005 году исследователям удалось создать пары PostScript . документов и X.509 сертификаты с тем же хешем. Позже в том же году дизайнер MD5 Рон Ривест написал, что «md5 и sha1 явно сломаны (с точки зрения устойчивости к столкновениям)».

30 декабря 2008 года группа исследователей объявила на 25-м Конгрессе Chaos Communication , как они использовали коллизии MD5 для создания промежуточного сертификата центра сертификации, который оказался законным при проверке его хеша MD5. Исследователи использовали кластер PS3 в EPFL в Лозанне , Швейцария. изменить обычный сертификат SSL, выданный RapidSSL, на рабочий сертификат CA для этого издателя, который затем можно будет использовать для создания других сертификатов, которые будут выглядеть законными и выданными RapidSSL. VeriSign , эмитенты сертификатов RapidSSL, заявили, что прекратили выпуск новых сертификатов, использующих MD5 в качестве алгоритма контрольной суммы для RapidSSL, как только было объявлено об уязвимости. Хотя компания Verisign отказалась отозвать существующие сертификаты, подписанные с использованием MD5, их ответ посчитали адекватным авторы эксплойта ( Александр Сотиров , Марк Стивенс , Якоб Аппельбаум , Арьен Ленстра , Дэвид Молнар, Даг Арне Освик и Бенне де Вегер). Брюс Шнайер написал об атаке, что «мы уже знали, что MD5 — это неработающая хеш-функция» и что «никто больше не должен использовать MD5». Исследователи SSL написали: «Мы желаем, чтобы центры сертификации прекратили использовать MD5 при выдаче новых сертификатов. Мы также надеемся, что использование MD5 в других приложениях также будет пересмотрено».

По данным Microsoft , в 2012 году авторы вредоносного ПО Flame использовали коллизию MD5 для подделки сертификата подписи кода Windows.

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

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

Оба создают хэш MD5. 79054025255fb1a26e4bc422aef54eb4. Разница между двумя выборками заключается в том, что старший бит в каждом полубайте перевернут. Например, 20-й байт (смещение 0x13) в верхнем образце, 0x87, равен 10000111 в двоичном формате. Ведущий бит в байте (также ведущий бит в первом полубайте) инвертируется, образуя 00000111, что соответствует 0x07, как показано в нижнем примере.

Позже также оказалось возможным создавать коллизии между двумя файлами с отдельно выбранными префиксами. Этот метод использовался при создании мошеннического сертификата CA в 2008 году. новый вариант параллельного поиска коллизий с использованием MPI , который позволил обнаружить коллизию за 11 часов на вычислительном кластере. В 2014 году Антон Кузнецов предложил

Уязвимость прообраза

В апреле 2009 года была опубликована атака на MD5, которая ломает устойчивость MD5 к прообразу . Эта атака является лишь теоретической, с вычислительной сложностью 2 ^123.4 для полного прообраза.

Приложения

Дайджесты MD5 широко используются в мире программного обеспечения для обеспечения некоторой уверенности в том, что переданный файл доставлен в целости и сохранности. Например, файловые серверы часто предоставляют предварительно вычисленную MD5 (известную как md5sum ) контрольную сумму для файлов, чтобы пользователь мог сравнить с ней контрольную сумму загруженного файла. Большинство операционных систем на базе Unix включают в свои дистрибутивы утилиты суммирования MD5; Пользователи Windows могут использовать включенную функцию PowerShell «Get-FileHash», включенную функцию командной строки «certutil -hashfile <имя файла> md5», установите утилиту Microsoft, или использовать сторонние приложения. ПЗУ Android также используют этот тип контрольной суммы.

Diagram showing use of MD5 hashing in file transmission

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

Исторически MD5 использовался для хранения одностороннего хеша пароля , часто с растяжением ключа . NIST не включает MD5 в список рекомендуемых хешей для хранения паролей.

MD5 также используется в области электронного раскрытия информации , чтобы предоставить уникальный идентификатор каждому документу, которым обмениваются в процессе юридического раскрытия. Этот метод может быть использован для замены системы нумерации марок Бейтса , которая десятилетиями использовалась при обмене бумажными документами. Как указано выше, такое использование не рекомендуется из-за простоты атак коллизий.

Алгоритм

Рисунок 1. Одна операция MD5. MD5 состоит из 64 таких операций, сгруппированных в четыре раунда по 16 операций. F – нелинейная функция; в каждом раунде используется одна функция. Mi _K битный блок ввода сообщения, а обозначает 32 - _i обозначает 32-битную константу, разную для каждой операции. <<< _s обозначает поворот левого бита на s мест; s варьируется для каждой операции. $\boxplus$ обозначает сложение по модулю 2 ³² .

MD5 преобразует сообщение переменной длины в выходные данные фиксированной длины в 128 бит. Входное сообщение разбивается на блоки по 512 бит (шестнадцать 32-битных слов); сообщение дополняется так, что его длина делится на 512. Заполнение работает следующим образом: сначала к концу сообщения добавляется один бит, 1. Далее следует столько нулей, сколько необходимо для увеличения длины сообщения до 64 бит, меньше, чем кратное 512. Оставшиеся биты заполняются 64 битами, представляющими длину исходного сообщения по модулю 2. ⁶⁴ .

алгоритм MD5 работает с 128-битным состоянием, разделенным на четыре 32-битных слова, обозначенных A , B , C и D. Основной Они инициализируются определенными фиксированными константами. Затем основной алгоритм по очереди использует каждый 512-битный блок сообщения для изменения состояния. Обработка блока сообщения состоит из четырех аналогичных этапов, называемых раундами ; каждый раунд состоит из 16 подобных операций, основанных на нелинейной функции F , модульном сложении и вращении влево. Рисунок 1 иллюстрирует одну операцию в течение раунда. Есть четыре возможных функции; В каждом раунде используется другой:

${\begin{aligned}F(B,C,D)&=(B\wedge {C})\vee (\neg {B}\wedge {D})\\G(B,C,D)&=(B\wedge {D})\vee (C\wedge \neg {D})\\H(B,C,D)&=B\oplus C\oplus D\\I(B,C,D)&=C\oplus (B\vee \neg {D})\end{aligned}}$

$\oplus ,\wedge ,\vee ,\neg$ обозначают операции XOR , AND , OR и NOT соответственно.

Псевдокод

По этому алгоритму рассчитывается MD5-хеш. Все значения имеют прямой порядок байтов .

// : All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
var int s[64], K[64]
var int i

// s specifies the per-round shift amounts
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 }

// Use binary integer part of the sines of integers (Radians) as constants:
for i from 0 to 63 do
    K[i] := floor(232 × abs(sin(i + 1)))
end for
// (Or just use the following precomputed table):
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 }

// Initialize variables:
var int a0 := 0x67452301   // A
var int b0 := 0xefcdab89   // B
var int c0 := 0x98badcfe   // C
var int d0 := 0x10325476   // D

// Pre-processing: adding a single 1 bit
append "1" bit to message<    
 // Notice: the input bytes are considered as bit strings,
 //  where the first bit is the most significant bit of the byte.

// Pre-processing: padding with zeros
append "0" bit until message length in bits ≡ 448 (mod 512)

// Notice: the two padding steps above are implemented in a simpler way
  //  in implementations that only work with complete bytes: append 0x80
  //  and pad with 0x00 bytes so that the message length in bytes ≡ 56 (mod 64).

append original length in bits mod 264 to message

// Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message do
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
    // Initialize hash value for this chunk:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
    // Main loop:
    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
        // Be wary of the below definitions of a,b,c,d
        F := F + A + K[i] + M[g]  // M[g] must be a 32-bit block
        A := D
        D := C
        C := B
        B := B + leftrotate(F, s[i])
    end for
    // Add this chunk's hash to result so far:
    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 // (Output is in little-endian)

Вместо показанной формулировки из исходного RFC 1321 для повышения эффективности можно использовать следующую формулировку (полезно, если используется язык ассемблера - в противном случае компилятор обычно оптимизирует приведенный выше код. Поскольку в этих формулировках каждое вычисление зависит от другого, это часто медленнее, чем описанный выше метод, в котором nand/and можно распараллелить):

( 0 ≤ i ≤ 15): F := D xor (B and (C xor D))
(16 ≤ i ≤ 31): F := C xor (D and (B xor C))

MD5-хеши

128-битные (16-байтовые) хеши MD5 (также называемые дайджестами сообщений ) обычно представляются как последовательность из 32 шестнадцатеричных цифр. Ниже демонстрируется 43-байтовый ввод ASCII и соответствующий хэш MD5:

MD5("The quick brown fox jumps over the lazy dog") =
9e107d9d372bb6826bd81d3542a419d6

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

MD5("The quick brown fox jumps over the lazy dog.") = 
e4d909c290d0fb1ca068ffaddf22cbd0

Хэш строки нулевой длины:

MD5("") = 
d41d8cd98f00b204e9800998ecf8427e

Алгоритм MD5 указан для сообщений, состоящих из любого количества битов; он не ограничен кратными восьми битам ( октетам , байтам ). Некоторые реализации MD5, такие как md5sum , могут быть ограничены октетами или не поддерживать потоковую передачу сообщений изначально неопределенной длины.

Реализации

Ниже приведен список библиотек шифрования, поддерживающих MD5:

• Ботан
• Надувной замок
• криптлиб
• Крипто++
• Libgcrypt
• Крапива
• OpenSSL
• волкSSL

См. также

• Сравнение криптографических хэш-функций
• Сводка безопасности хеш-функции
• ХэшКлэш
• MD5Crypt
• md5deep
• я MD5
• MD6
• ША-1
• ША-2

Дальнейшее чтение

• Персон, Томас А. (1992). «Дифференциальный криптоанализ Мод 2» ³² с приложениями к MD5». EUROCRYPT . стр. 71–80. ISBN  3-540-56413-6 .
• Берт ден Бур; Антон Босселерс (1993). «Коллизии функции сжатия MD5». Достижения в криптологии – EUROCRYPT '93 . ЕВРОКРИПТ. Берлин; Лондон: Спрингер. стр. 293–304. ISBN  978-3-540-57600-6 .
• Ханс Доббертин, Криптоанализ сжатия MD5. Объявление в Интернете, май 1996 г. «CiteSeerX» . Сайт Citeseer.ist.psu.edu. Архивировано из оригинала 24 июня 2008 года . Проверено 9 августа 2010 г.
• Доббертин, Ганс (1996). «Состояние MD5 после недавней атаки» . Криптобайты . 2 (2).
• Сяоюнь Ван; Хунбо Ю (2005). «Как взломать MD5 и другие хэш-функции» (PDF) . ЕВРОКРИПТ . ISBN  3-540-25910-4 . Архивировано из оригинала (PDF) 21 мая 2009 года . Проверено 6 марта 2008 г.

Внешние ссылки

• Рекомендации W3C по MD5. Архивировано 28 декабря 2014 г. на Wayback Machine.
• Калькулятор MD5. Архивировано 16 ноября 2022 г. на Wayback Machine.