Длина блоков на которые делится сообщение в хэш функции md5 равна

Обновлено: 02.07.2024

Этот алгоритм был разработан в 1991 году профессором Рональдом Л. Ривестом. Алгоритм MD5 часто называют алгоритмом шифрования, но на самом деле это утверждение ошибочно. Главным преимуществом MD5 является то, что зашифрованные данные восстановить нельзя. А что это за алгоритм шифрования, который шифрует данные так, что никто их не сможет узнать? MD5 — это хэш-функция. У многих возник вопрос: что же это такое? Остановимся на этом вопросе.

Что такое Хэш-функция

Предположим, у нас есть некоторый набор данных. Для простоты будем рассматривать натуральные числа от 1 до 10 6 . И пусть есть некоторая функция, в которой один параметр — натуральное число от 1 до 10 6 , а возвращаемое значение — натуральное число от 1 до 1000. Нам не важно, что именно делает эта функция, нам важно то, что она каждому натуральному числу от 1 до 10 6 ставит в соответствие другое натуральное число от 1 до 1000. Для примера рассмотрим одну из самых простых функций, выполняющих это действие:

int hash(long int x)if (x%1000==0) return 1000;
return (x % 1000);
>

function hash(x:longint):longint;
begin
if (x mod 1000=0) then hash:=1000 else
hash:=x mod 1000;
end;

Это и есть простая хэш-функция. Если мы знаем параметр функции, то однозначно можем сказать, какой будет результат. А если нам известен результат, то можем ли мы узнать однозначно параметр? Конечно, нет. Для числа 234 параметр может быть 234,1234, 2234,3234… Поэтому однозначно восстановить параметр не получится.

Зачем нужен MD5

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

1. Перед созданием копии сайта, которая будет перенесена в школу, удалять все пароли.
2. Зашифровать все пароли так, чтобы никто не смог расшифровать их обратно.

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

Как работает MD5

Теперь посмотрим, как именно работает MD5. Для обработки MD5 получает некоторую строку. Эта строка преобразуется в последовательность из нулей и единиц. Как это делается? У каждого символа есть свой номер. Эти номера можно записать в двоичной системе счисления. Получается, каждый символ можно записать как последовательность нулей и единиц. Если этим воспользоваться, получим из строки последовательность из нулей и единиц. Пусть q будет длина получившейся последовательности (ровно 64 бита, возможно, с незначащими нулями). К получившейся последовательности приписывается 1. В результате длина последовательности увеличивается на 1. Затем к последовательности приписываются нули, пока длина не станет по модулю 512 равна 448 (length mod 512=448). Далее к последовательности дописываются младшие 32 бита числа q, а затем — старшие. Длина последовательности становится кратной 512. Полученную последовательность назовем S. Для подсчета результата используются четыре двойных слова (32 бита). Эти двойные слова инициализируются следующими шестнадцатеричными значениями, где первым следует самый младший байт:

A: 01 23 45 67
B: 89 ab cd ef
C: fe dc ba 98
D: 76 54 32 10
Также для подсчета результата используются следующие функции:
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))

X,Y,Z — это двойные слова. Результаты функций, также двойные слова. Для подсчета используется еще одна функция (назовем ее W). Она хитро обрабатывает данные и возвращает результат (подробно ее описывать не буду, т.к. она выполняет серию простых преобразований). Обработка данных происходит с использованием функций F, G, H, I.

На рисунке схематически изображена функция. Слева — входные данные, справа — выходные.

Все необходимые функции и обозначения рассмотрены. Теперь рассмотрим, как происходит просчет результата:
1. Запоминаем первые 512 бит последовательности S.
2. Удаляем первые 512 бит последовательности S (можно обойтись и без удаления, но тогда на первом шаге надо брать не первые 512, а
следующие 512 бит).
3. Вызываем функцию W. Параметры A,B,C,D — это текущие значения соответствующих двойных слов. Параметр T — это запомненные 512 бит.
4. Прибавляем к A A0.
5. B=B+B0.
6. C=C+C0.
7. D=D+D0.
8. Если длина последовательности 0, выходим.
9. Переходим к шагу 1.

После выполнения этого алгоритма A,B,C,D — это результат (его длина будет 128 бит). Часто можно видеть результат MD5 как последовательность из 32 символов 0..f. Это то же самое, только результат записан не в двоичной системе счисления, а в шестнадцатеричной.

В Интернете можно найти много программ, которые обещают найти строку, для которой алгоритм MD5 выдаст заданный результат. Эти программы действительно работают. Ранее отмечалось, что восстановить параметр невозможно. Как же работают эти программы? Они перебирают все возможные строки, применяют к ним алгоритм MD5, а затем сравнивают с образцом. Если значения совпали, это означает, что программа нашла необходимую строку. Но у этих программ есть маленький недостаток. Предположим, известно, что программе придется перебрать все слова длиной в 8 символов, состоящих из маленьких и больших латинских букв. Сколько времени это займет? Сколько всего таких слов? На первом месте может стоять любой из 26*2=52 символов. На 2, 3, 4, 5, 6, 7 и 8 — тоже 52. Значит, всего таких слов будет: 52*52*52*52*52*52*52*52=52 8 =53*10 12 . А если используются не только латинские буквы? То это еще больше. Перебор всех вариантов на обычном персональном компьютере займет очень много времени. В Интернете можно найти сайты, которые по введенному хэшу выдают строку, для которой будет точно такой же хэш. Эти сайты используют базу данных с заранее просчитанными хэшами. Но в базах хранятся не все хэшы, а только самые используемые. Вот один из таких сайтов: сайт Так что советую использовать в качестве пароля абсолютно случайную последовательность символов.

Руслан Коржик, rk@tut.by

Компьютерная газета. Статья была опубликована в номере 18 за 2006 год в рубрике безопасность

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

Конкретнее о MD5

Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.

О песочнице

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

Чтобы исключить предвзятость при оценке, все публикации анонимны, псевдонимы показываются случайным образом.

Проект 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 [ ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

MD5 хеши [ ]

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

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

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

Для перебора по словарю или брутфорса можно использовать программы PasswordsPro [2] , MD5BFCPF [3] , [4]

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

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

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

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

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

d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70

d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70

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

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

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

<\displaystyle N,N

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

Эта атака является разновидностью дифференциальной атаки, которая, в отличие от других атак этого типа, использует целочисленное вычитание а не с вероятностью 2 -37 . К >" width="" height="" />
и применяется функция сжатия для проверки условий коллизии; далее выбирается произвольное >" width="" height="" />
, модифицируется, вычисляется новый дифференциал, равный нулю с вероятностью 2 -30 , а равенство нулю дифференциала хеш-функции как раз означает наличие коллизии. Оказалось, что найдя одну пару >" width="" height="" />
и , можно менять лишь два последних слова в >" width="" height="" />
, тогда для нахождения новой пары >" width="" height="" />
и требуется всего около 2 39 операций хеширования.

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

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

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

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

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

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

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

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

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

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

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

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

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

А = 01 23 45 67; //0x67452301В = 89 AB CD EF; //0xEFCDAB89С = FE DC BA 98; //0x98BADCFED = 76 54 32 10. //0x1032547

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

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

· Потребуются 4 функции для четырёх раундов. Введём функции от трёх параметров — слов, результатом также будет слово.


1 раунд .


4 раунд .

где логические операции XOR, AND, OR и NOT соответственно.

· Определим таблицу констант — 64-элементная таблица данных, построенная следующим образом: , где . [4]

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

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

Раунд 1

/*[abcd k s i] a = b + ((a + F(b,c,d) + X[k] + T[i])



/*[abcd k s i] a = b + ((a + I(b,c,d) + X[k] + T[i])

MD5-хеши

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

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

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

При этом методы перебора по словарю и brute-force могут использоваться для взлома хеша других хеш-функций (с небольшими изменениями алгоритма). RainbowCrack требует предварительной подготовки радужных таблиц, которые создаются для заранее определённой хеш-функции. Поиск коллизий специфичен для каждого алгоритма.

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

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

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

Коллизии MD5

A = 0x12AC2375В = 0x3B341042C = 0x5F62B97CD = 0x4BA763E

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

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

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

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

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


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

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

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

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

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

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

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

1. Пароли хранятся как есть. При взломе такой базы все пароли станут известны.

2. Хранятся только хеши паролей (с помощью MD5, SHA). Найти пароли можно только полным перебором. Но при условии использования несложного, популярного или просто несчастливого пароля (который встречался ранее и занесён в таблицу) такая задача решается за доли секунды. Пароль из таблицы был найден всего за 0,036059 сек. [13]

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

Читайте также: