Рассмотрим алгоритм получения дайджеста сообщения MD5 (RFC 1321), разработанный Роном Ривестом из MIT.

Алгоритм получает на входе сообщение произвольной длины и создает в качестве выхода дайджест сообщения длиной 128 бит. Алгоритм состоит из следующих шагов:

Рис. 3.1.

Шаг 1: добавление недостающих битов

Сообщение дополняется таким образом, чтобы его длина стала равна 448 по модулю 512 (длина = 448 (mod 512)) . Это означает, что длина добавленного сообщения на 64 бита меньше, чем число, кратное 512. Добавление производится всегда, даже если сообщение имеет нужную длину. Например, если длина сообщения 448 битов, оно дополняется 512 битами до 960 битов. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Добавление состоит из единицы, за которой следует необходимое ко-личество нулей.

Шаг 2: добавление длины

64-битное представление длины исходного (до добавления) сообщения в битах присоединяется к результату первого шага. Если первоначальная длина больше, чем 2 64 , то используются только последние 64 бита. Таким образом, поле содержит длину исходного сообщения по модулю 2 64 .

В результате первых двух шагов создается сообщение, длина которого кратна 512 битам. Это расширенное сообщение представляется как после-довательность 512-битных блоковY0, Y1, . . ., YL-1 , при этом общая длина расширенного сообщения равна L * 512 битам. Таким образом, длина полученного расширенного сообщения кратна шестнадцати 32-битным словам.

Рис. 3.2.

Шаг 3: инициализация MD-буфера

Используется 128-битный буфер для хранения промежуточных и окон-чательных результатов хэш-функции. Буфером являются четыре 32-битных регистра (A, B, C, D) . Эти регистры инициализируются следующими шестнадцатеричными числами:

А = 01234567

В = 89ABCDEF

C = FEDCBA98

D = 76543210

Шаг 4: обработка последовательности 512-битных (16-словных) блоков

Основой алгоритма является модуль, состоящий из четырех циклических обработок, обозначенный как H MD5 . Четыре цикла имеют похожую структуру, но каждый цикл использует свою элементарную логическую функцию, обозначаемую f F , f G , f H и f I с оответственно (рис. 3.3).

Каждый цикл принимает в качестве входа текущий 512-битный блок Y q , обрабатывающийся в данный момент, и 128-битное значение буфера ABCD , которое является промежуточным значением дайджеста, и изменяет содержимое этого буфера. На каждом цикле также используется четвертая часть 64-элементной таблицы T ... T , построенной на основе функции sin .

Где в правой части означает целую часть числа, i задано в радианах. Так как abs (sin(i)) является числом между 0 и 1, каждый элемент Т [i] является целым, которое может быть представлено 32 битами. Таблица обеспечивает "случайный" набор 32-битных значений, которые должны ликвидировать любую регулярность во входных данных.

Для получения MDq+1 выход четырех циклов складывается по модулю 2 32 с MDq . Сложение выполняется независимо для каждого из четырех слов в буфере.

Рис. 3.3.

Шаг 5: выход

После обработки всех L 512-битных блоков выходом L -ой стадии является 128-битный дайджест сообщения.

Рассмотрим более детально логику каждого из четырех циклов выполнения одного 512-битного блока. Каждый цикл состоит из 16 шагов, оперирующих с буфером ABCD . Каждый шаг представлен на рис. 3.4.

где A, B, C, D - четыре слова буфера; после выполнения каждого отдельного шага происходит циклический сдвиг влево на одно слово.

f - одна из элементарных функций f F , f G , f H , f I .

CLS s - циклический сдвиг влево на s битов 32-битного аргумента.

X[k] - M - k -ое 32-битное слово в q -ом 512 блоке сообщения.

T[i] - i -ое 32-битное слово в таблице Т .

Сложение по модулю 2 32 .

Рис. 3.4.

В каждом из четырех циклов алгоритма используется одна из четырех так называемых элементарных логических функций. Каждая элементарная функция получает три 32-битных слова на входе и на выходе создает одно 32-битное слово. Каждая функция является набором побитовых логических операций, т.е. n-ый бит выхода является функцией от n-ого бита трех входов. Элементарные функции следующие:

Массив из 32-битных слов X содержит значение текущего 512-битного входного блока, который обрабатывается в настоящий момент. Каждый цикл выполняется 16 раз, а так как каждый блок входного сообщения обрабатывается в четырех циклах, то каждый блок входного сообщения обрабатывается по описанной выше схеме 64 раза. Если представить входной 512-битный блок в виде шестнадцати 32-битный слов, то каждое входное 32-битное слово используется четыре раза, по одному разу в каждом цикле, и каждый элемент таблицы Т , состоящей из 64 32-битных слов, используется только один раз. После каждого шага цикла происходит циклический сдвиг влево четырех слов A, B, C и D . На каждом шаге изменяется только одно из четырех слов буфера ABCD . Следовательно, каждое слово буфера изменяется 16 раз, и затем 17-ый раз в конце для получения окончательного выхода данного блока.

Можно суммировать алгоритм MD5 следующим образом:

IV - начальное значение буфера ABCD , определенное на шаге 3.

Yq - q -ый 512-битный блок сообщения.

L - число блоков в сообщении (включая поля дополнения и длины).

MD - окончательное значение дайджеста сообщения.

MD5 или Message Digest 5 это 128-битный алгоритм хеширования разработанный в начале 90-х годов профессором Рональдом Ривестом. Как правило, представляется как последовательность из 32 шестнадцатеричных цифр, например:. Для того чтобы понять что такое MD5 сначала нужно разобраться с понятием хеширование.

Хеширование это процесс преобразования любого массива данных в выходную строку фиксированной длины. Это преобразование проводится с помощью, так называемых, хеш-функций. Такая функция на входе получает массив данных, а на выходе возвращает так называемый хеш (хеш-суму) – уникальную строку фиксированной длины.

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

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

История развития MD5

Алгоритм MD5 был разработан профессором Рональдом Л. Ривестом из Массачусетского технологического института в 1991 году. Данный алгоритм стал заменой предыдущей версии алгоритма MD4. С этого времени алгоритм обрел большую популярность и стал использоваться повсеместно.

Начиная с 1993 года, регулярно появляются исследования, которые обнаруживают все новые уязвимости в алгоритме MD5. На данный момент алгоритм MD5 считается уязвимым и постепенно заменяется алгоритмом SHA.

Как получить хеш MD5

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

Для того чтобы получить MD5 хеш с помощью этого сервиса достаточно ввести строку в поле и нажать на кнопку «Hash». Поле этого появится хеш введенной строки.

Если же вам нужно получить MD5 хеш файла, то придётся использовать специальные программы, например, MD5summer (

90.3K

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

Что такое MD5?

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

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

Область применения хеш-кодов:

• Создание электронных подписей;
• Хранение паролей в базах данных систем безопасности;
• В рамках современной криптографии для создания уникальных ключей онлайн;
• Проверка подлинности и целостности элементов файловой системы ПК.

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

Утилита md5sum, предназначенная для хеширования данных заданного файла по алгоритму MD5, возвращает строку. Она состоит из 32 чисел в шестнадцатеричной системе исчисления (016f8e458c8f89ef75fa7a78265a0025).

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

Проблемы надежности MD5

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

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

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

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

Область применения алгоритма хеширования:

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

• Для хеширования паролей – в семействе операционных систем UNIX каждый пользователь системы имеет свой уникальный пароль, для защиты которого используется хеширование на основе MD5 . Некоторые системы на основе Linux также пользуются этим методом шифрования паролей.

Обзор средств для декодирования хеш-кода MD5

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

Удобнее всего использовать специализированные ресурсы, предоставляющие возможность сделать это online :

• md5.web-max.ca – данный сервис обладает простым и понятным интерфейсом. Для получения декодированного значения нужно ввести хеш и заполнить поле проверочной капчи:

• md5decrypter.com – аналогичный сервис;
• msurf.ru – данный ресурс имеет простой русскоязычный интерфейс. Его функционал позволяет не только расшифровывать значения хеш-кодов, но и создавать их:

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

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

Создание хеша MD5 является односторонним процессом. Поэтому не подразумевает обратного декодирования первоначального значения.

Основы безопасности при использовании MD5

Этот стандарт кодирования является одним из самых распространенных методов защиты данных не только в прикладном, но и в веб-программировании. Поэтому не будет лишним обезопасить свой md5 hash от намеренного взлома.

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

Во многих языках программирования для этого используются специальные классы и функции. Не являются исключением из правил и серверные языки программирования.

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

Функция MD5 хэширования в PHP называется md5() . Принимает функция одну строку, которую необходимо зашифровать. Функция возвращает MD5 хэш :

$str = "MyPassword";
echo md5($str);
?>

Запустив данный скрипт, Вы увидите MD5-хэш , соответствующий строке "MyPassword ".

То есть простейший скрипт проверки логина и пароля:

$login = "Admin";
$password = "48503dfd58720bd5ff35c102065a52d7"; //В реальности считывается из БД
if (($_GET["login"] == $login) && (md5($_GET["password"]) == $password)) echo "Welcome!";
else echo "Access denied";
?>

Теперь поговорим о свойствах MD5-хэширования .

1. MD5-хэш содержит 32 символа
2. MD5-хэш уникален для каждой строки
3. Процесс MD5-хэширования необратим
4. Процесс MD5-хэширования достаточно медлителен

Третий пункт, пожалуй, самый важный, потому что если бы он был обратим, то смысл хэширования практически бы отсутствовал. Глупо шифровать, например, пароли, если их можно легко потом расшифровать.

Четвёртый пункт, как бы это парадоксально не звучало, также является очень большим плюсом. Почему? Очень просто: человек, который будет вынужден подождать этот процесс 0.001 секунды, сильно не пострадает. А вот злоумышленник, который будет перебирать пароли пострадает резко, так как медлительность алгоритма уже задаёт предел - 1000 паролей в секунду. Хотя, безусловно, скорость зависит от быстродействия сервера. Но тем не менее, для злоумышленника низкая скорость получения MD5-хэша - это очень большая проблема.

На будущее: никогда не храните пароли в открытом виде, забудьте об этом раз и навсегда. Поэтому всегда отправляйте пароли в базу данных в виде MD5-хэша , и, соответственно, сравнивайте хэши паролей, а не сами пароли.

Песочница

Лунтик 27 марта 2011 в 16:59

Хэш-функция MD5

• Чулан *

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

Что такое хэш-функция и чем её едят?

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

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

Не буду углубляться в историю создания, об этом можно почитать в википедии, однако отмечу что алгоритм был создан профессором Р. Риверстом в 1991 году на основе алгоритма md4. Описан этот алгоритм в RFC 1321
Алгоритм состоит из пяти шагов:
1)Append Padding Bits
В исходную строку дописывают единичный байт 0х80, а затем дописывают нулевые биты, до тех пор, пока длина сообщения не будет сравнима с 448 по модулю 512. То есть дописываем нули до тех пор, пока длина нового сообщения не будет равна [длина] = (512*N+448),
где N - любое натуральное число, такое, что это выражение будет наиболее близко к длине блока.
2)Append Length
Далее в сообщение дописывается 64-битное представление длины исходного сообщения.
3)Initialize MD Buffer
На этом шаге инициализируется буффер
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Как можно заметить буффер состоит из четырех констант, предназначенный для сбора хэша.
4)Process Message in 16-Word Blocks
На четвертом шаге в первую очередь определяется 4 вспомогательные логические функции, которые преобразуют входные 32-битные слова, в, как ни странно, в 32-битные выходные.
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))
Также на этом шаге реализуется так называемый «белый шум» - усиление алгоритма, состоящее 64 элементного массива, содержащего псевдослучайные числа, зависимые от синуса числа i:
T[i]=4,294,967,296*abs(sin(i))
Далее начинается «магия». Копируем каждый 16-битный блок в массив X и производим манипуляции:
AA = A
BB = B
CC = C
DD = D
Затем происходят «чудесные» преобразования-раунды, которых всего будет 4. Каждый раунд состоит из 16 элементарных преобразований, которые в общем виде можно представить в виде , которое, в свою очередь, можно представить как A = B + ((A + F(B,C,D) + X[k] + T[i]) <<< s), где
A, B, C, D - регистры
F(B,C,D) - одна из логических функций
X[k] - k-тый элемент 16-битного блока.
T[i] - i-тый элемент таблицы «белого шума»
<<< s - операция циклического сдвига на s позиций влево.
Приводить все раунды не имеет смысла, все их можно посмотреть
Ну и в конце суммируем результаты вычислений:
A = A + AA
B = B + BB
C = C + CC
D = D + DD
5) Output
Выводя побайтово буффер ABCD начиная с A и заканчивая D получим наш хэш.

Надежность

Существует мнение что взломать хэш MD5 невозможно, однако это неправда, существует множество программ подбирающих исходное слово на основе хэша. Абсолютное большинство из них осуществляет перебор по словарю, однако существуют такие методы как RainbowCrack , он основан на генерировании множества хэшей из набора символов, чтобы по получившейся базе производить поиск хэша.
Также у MD5, как у любой хэш-функции, существует такое понятие как коллизии - это получение одинаковых хэшей для разных исходных строк. В 1996 году Ганс Доббертин нашёл псевдоколлизии в MD5, используя определённый инициализирующий буффер (ABCD). Также в 2004 году китайские исследователи Ван Сяоюнь, Фен Дэнгуо, Лай Сюэцзя и Юй Хунбо объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии. Однако в 2006 году чешский исследователь Властимил Клима опубликовал алгоритм, позволяющий находить коллизии на обычном компьютере с любым начальным вектором (A,B,C,D) при помощи метода, названного им «туннелирование».

Прилагаю собственный пример реализации функции на C#:
md5.rar

Теги: криптография, md5

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