MD5 - MD5

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

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

MD5 был разработан Рональдом Ривестом в 1991 году для замены более ранней хэш-функции MD4 и был указан в 1992 году как RFC 1321.

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

31 декабря 2008 года CMU Software Engineering Institute пришел к выводу, что MD5 по сути «криптографически взломан и непригоден для дальнейшего использования». Слабые стороны MD5 использовались в полевых условиях, наиболее печально известной вредоносной программой Flame в 2012 году. По состоянию на 2019 год 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 года Клима опубликовал алгоритм, который может обнаруживать столкновение в течение одной минуты на одном ноутбуке, используя метод, который он называет туннелированием.

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

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

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

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

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

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

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

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

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

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

Коллизионные уязвимости

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

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

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

В 2012 году, по данным Microsoft , авторы вредоносной программы 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 был предложен Антоном Кузнецовым в 2014 году, который позволил обнаружить коллизию за 11 часов на вычислительном кластере.

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

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

Приложения

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

Диаграмма, показывающая использование хеширования MD5 при передаче файлов

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

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

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

Алгоритм

Рисунок 1. Одна операция MD5. MD5 состоит из 64 таких операций, сгруппированных в четыре раунда по 16 операций. F - нелинейная функция; в каждом раунде используется одна функция. M i обозначает 32-битный блок ввода сообщения, а K i обозначает 32-битную константу, различную для каждой операции. <<< s обозначает левый поворот бит на s мест; s варьируется для каждой операции. обозначает сложение по модулю 2 32 .

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

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

обозначают операции 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 bits 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-bits 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 / и можно распараллелить):

( 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:

Смотрите также

использованная литература

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

  • Берсон, Томас А. (1992). "Дифференциальный криптоанализ Mod 2 32 с приложениями к MD5". ЕВРОКРИПТ . С. 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 . Проверено 9 августа 2010 года .
  • Доббертин, Ганс (1996). «Состояние MD5 после недавней атаки» . CryptoBytes . 2 (2).
  • Сяоюнь Ван; Хунбо Ю (2005). «Как взломать MD5 и другие хеш-функции» (PDF) . ЕВРОКРИПТ . ISBN 3-540-25910-4. Архивировано из оригинального (PDF) 21 мая 2009 года . Проверено 6 марта 2008 года .

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