хэш md5 что это
Анализ безопасности хранения и хеширования паролей при помощи алгоритма MD5
С появлением компьютерных технологий стало более продуктивным хранить информацию в базах данных, а не на бумажных носителях. Веб-приложения, нуждающиеся в аутентификации пользователя, обычно проверяют входные пароли, сравнивая их с реальными паролями, которые обычно хранятся в частных базах данных компании. Если злоумышленники получат доступ к вышеупомянутой базе данных личные данные пользователей будут утеряны. В настоящее время базы данных используют хеш-алгоритмы для защиты хранящихся паролей, но проблемы, связанные с безопасностью все еще актуальны. Каждый год хакеры опубликовывают большой список взломанных паролей от известных социальных сетей или же хранилищ данных. Подобные атаки оказались успешными благодаря использованию слабого алгоритма хеширования.
Криптографические хеш-функции, чаще называемые просто хешем, — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, проверку целостности данных, защиту файлов и даже обнаружение зловредного ПО. Это математический алгоритм, преобразовывающий произвольный массив данных в состоящую из букв и цифр строку фиксированной длины. Причем при условии использования того же типа хеша эта длина будет оставаться неизменной, вне зависимости от объема вводных данных [2]. Существует масса алгоритмов хеширования, отличающихся криптостойкостью, сложностью, разрядностью и другими свойствами. Считается, что идея хеширования принадлежит сотруднику IBM, появилась около 50 лет назад и с тех пор не претерпела принципиальных изменений. В наши дни хеширование обрело массу новых свойств и используется в очень многих областях информационных технологий.
Преобразование сообщения произвольной длины в хеш-значение подразумевает работу пяти шагов алгоритма, каждый из которых имеет свою определенную задачу. Рассмотрим подробнее шаги алгоритма:
Шаг 1: Выравнивание потока
Необходимо добавление дополнительных битов к исходному сообщению, выполненное таким образом, чтобы длина исходного сообщения с добавочными битами была эквивалентна 448 по модулю 512. Добавление выполняется даже в том случае, если длина исходного сообщения уже сравнима с 448. В битах заполнения только первый бит равен 1, а остальные биты равны 0.
Шаг 2. Добавление длины сообщения
В конец сообщения дописывают 64-битное представление длины данных (количество бит в сообщении) до выравнивания. На этом этапе полученное сообщение имеет длину, кратную 512 битам. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.
Шаг 3: инициализация MD-буфера
Шаг 4: обработка сообщения в цикле
MD5 использует четыре вспомогательные функции, которые принимают на вход три 32-битных числа и производят 32-битный вывод [1].
Эти функции используют логические операторы типа OR, XOR, AND, NOT. Содержимое четырех буферов смешивается с входными данными (из предыдущего шага) с помощью вспомогательного буфера, который строится на основе вычислений со вспомогательными функциями. Выполняется четыре раунда, в каждом из которых используется своя вспомогательная функция.
Шаг 5. Результат вычислений
После выполнения всех раундов буфер A, B, C, D содержит вывод MD5, это и есть хеш.
Для того чтобы повысить безопасность хранения паролей алгоритм MD5 может использоваться для хеширования исходных паролей. Таким образом в базе данных будут храниться значения хеш-функции соответствующего алгоритма, а не открытого текста. Во время аутентификации входной пароль также хешируется алгоритмом MD5 на стороне клиента аналогичным образом, и результирующее хеш-значение сравнивается с значением в базе данных для конкретного пользователя.
Криптоанализ алгоритма MD5 говорит о том, что на данный момент существуют несколько видов «взлома» хешей MD5:
1) атаки переборного типа
В криптографии атака полного перебора или исчерпывающий поиск — ключей- это стратегия, которая теоретически может быть использована против любых зашифрованных данных. Злоумышленник, который не может воспользоваться слабостью в системе шифрования, реализовывает атаку подобного типа. Она включает в себя систематическую проверку всех возможных ключей, пока не будет найден правильный. В худшем случае для взлома сообщения потребуется задействовать всю вычислительную мощность.
Для полного перебора или перебора по словарю можно использовать программы PasswordsPro, MD5BFCPF, John the Ripper.
2) атаки в которых применяются радужные таблицы
Радужные таблицы состоят из хеш-цепочек и более эффективны, чем предыдущий упомянутый тип атак, поскольку они оптимизируют требования к хранению, хотя поиск выполняется немного медленнее. Радужные таблицы отличаются от хеш-таблиц тем, что они создаются с использованием как хеш-функций, так и функций редукции [4].
Пусть существует хеш-функция H с длиной хеша n и конечное множество паролей P. Хеш-таблица должна справляться с главной задачей: содержать структуру данных, которая для любого значения хеша h может либо найти такой элемент p из P, что H(p)=h, либо определить, что такого элемента не существует. Простейший способ сделать это — вычислить H(p) для всех p из P, но для хранения такой таблицы, как выяснилось ранее потребуется слишком много памяти поэтому стоит обратиться к хеш-цепочкам.
Цепочки хешей — метод для уменьшения требования к объёму памяти. Главная идея — определение функции редукции R, которая сопоставляет значениям хеша значения из P. Стоит отметить, что R не является обращением хеш-функции. Рассмотрим подробнее построение хеш-цепочки [11]:
1) Каждое звено именуется результатом хэш-функции над полями данных этого звена;
2) Каждое звено кроме первого обязательно имеет поле данных с именем предыдущего звена.
Таким образом вся цепочка имеет сквозную зависимость, направленную к первому звену, хеш последнего звена фактически является цифровым отпечатком всей цепочки.
Начиная с исходного пароля и попеременно применяя к каждому полученному значению H и R, получается цепочка перемежающихся паролей и хешей.
Для каждого хеша h, значение которого нужно хотим обратить (найти соответствующий ему пароль), вычисляем последовательность R(…R(H(R(h)))…). Если какое-то из промежуточных значений совпадёт с каким-нибудь концом какой-либо цепочки, следует взять начало этой цепочки и восстанавливаем её полностью. С высокой вероятностью полная цепочка будет содержать значение хеша h, а предшествующий ему пароль будет искомым.
Радужные таблицы являются развитием идеи таблицы хеш-цепочек. Функции редукции применяются по очереди, перемежаясь с функцией хеширования: H, R1, H, R2, …, H, Rk.
Использование последовательностей функций редукции изменяет способ поиска по таблице. Поскольку хеш может быть найден в любом месте цепочки, необходимо сгенерировать k различных цепочек.
Существует множество систем взлома паролей и веб-сайтов, которые используют подобные таблицы. Основная идея данного метода — достижение компромисса между временем поиска по таблице и занимаемой памятью. Конечно, использование радужных таблиц не гарантирует 100% успеха взлома систем паролей. Однако, чем больше набор символов, используемый для создания радужной таблицы, и чем продолжительнее хеш-цепочки, тем больше будет шансов получить доступ к базе данных исходных паролей.
Коллизии MD5
Одно из главных свойств и требований к хеш-функциям это относительная невозможность (с точки зрения вычислений) по получению одинакового значения хеша для разных входных сообщений и идентичного начального буфера. Коллизии существуют для большинства хеш-функций, но для «хороших» функций частота их возникновения близка к теоретическому минимуму.
MD5 был тщательно изучен криптографическим сообществом с момента его первоначального выпуска и до 2004 года демонстрировал лишь незначительные недостатки. Однако летом 2004 года криптографы Ван Сяоюнь и Фэн Дэнго продемонстрировали алгоритм способный генерировать MD5-коллизии с использованием стандартного вектора инициализации.
Исследование [10] показало, что можно создать два 512-битных входных блока и изменить определенные биты внутри этих блоков, чтобы создать два слегка отличающихся сообщения с одинаковым хэш-значением. Время создания пары сообщений MD5 составляло в среднем 1 час. Пример подобной пары сообщений, дающий одинаковый хеш представлен ниже (различающиеся разряды выделены):
Позже данный алгоритм был усовершенствован, как следствие время поиска пары сообщений значительно уменьшилось, что позволило находить коллизии с приемлемой вычислительной сложностью. Как оказалось, в MD5 вопрос коллизий не решается.
Факторы, влияющие на безопасность пароля и возможные решения
Надежность и сложность пароля в сфере информационных технологий обычно измеряется в терминах теории информации. Чем выше информационная энтропия, тем надежнее пароль и, следовательно, тем труднее его взломать.
где N и L — количество возможных символов и количество символов в пароле соответственно. H измеряется в битах. [9]
Как видно, чем длиннее пароль и чем больше набор символов, из которого он получен, тем он надёжнее. Правда вместо количества попыток, которые необходимо предпринять для угадывания пароля, принято вычислять логарифм по основанию 2 от этого числа, и полученное значение называется количеством «битов энтропии» в пароле. При увеличении длины пароля на один бит количество возможных паролей удвоится, что сделает задачу атакующего в два раза сложнее. В среднем атакующий должен будет проверить половину из всех возможных паролей до того, как найдет правильный. В качестве наилучшей практики должно выполняться предварительное требование: приложение настаивает на том, чтобы пользователь использовал надежный пароль в процессе регистрации.
Добавление “соли” к паролю
Одна из наиболее распространенных причин успешных атак заключается в том, что компании не используют добавление соли к исходному паролю. Это значительно облегчает хакерам взлом системы с помощью атак типа радужных таблиц, особенно учитывая тот факт, что многие пользователи используют очень распространенные, простые пароли, имеющие одинаковые хеши. Соль-это вторичный фрагмент информации, состоящий из строки символов, которые добавляются к открытому тексту (исходному паролю пользователя), а затем хешируется [8]. Соление делает пароли более устойчивыми к атакам типа радужных таблиц, так как подобный пароль будет иметь более высокую информационную энтропию и, следовательно, менее вероятное существование в предварительно вычисленных радужных таблицах. Как правило, соль должна быть не менее 48 бит. Добавление соли можно осуществить следующими способами:
1) Использование единой соли для всех паролей: учитывая, что соль достаточно длинная и сложная, стандартная радужная таблица не может быть использована для расшифровки соленых хешей. Однако два одинаковых пароля все равно будут иметь один и тот же хеш.
2) Использование различной (случайной) соли для каждого пароля и хранение соли в самой базе данных: если мы используем разные соли для каждого пароля, то два одинаковых пароля будут иметь разные хеши. Злоумышленник должен генерировать различные радужные таблицы для каждого отдельного пользователя, что делает его вычислительно сложнее для взлома. Соли могут храниться в открытом виде в базе данных. Цель соли не в том, чтобы быть неизвестной, а в том, чтобы быть достаточно случайной, чтобы препятствовать использованию радужных таблиц.
3) Использование существующего значения столбца. Существующее значение столбца, например, username, можно использовать в качестве соли. Это решение аналогично второму решению, рассмотренному выше. Оно препятствует использованию стандартной радужной таблице, но тем не менее хакер может создать радужную таблицу для определенного имени пользователя, например, “root” или “admin”.
Заключение
Как уже отмечалось ранее, основная задача любой функции хеширования сообщений − производить образы, которые можно считать относительно случайными. Чтобы считаться криптографически безопасной, хэш-функция должна отвечать двум основным требованиям: во-первых, злоумышленник не может сгенерировать сообщение, соответствующее определенному хеш-значению и во-вторых, невозможно создать два сообщения, которые производят одно и то же значение. К сожалению, выяснилось, что алгоритм MD5 не способен отвечать данным требованиям. IETF (Internet Engineering Task Force) рекомендовала новым проектам протоколов не использовать MD5 так как исследовательские атаки предоставили достаточные основания для исключения использования алгоритма в приложениях, которым требуется устойчивость к различного рода коллизиям.
Хеши MD5 больше не считаются безопасными, и их не рекомендовано использовать для криптографической аутентификации.
Ссылки на источники и литература:
2. A.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин. Основы криптографии. 2-е издание, М. Гелиос АРВ-2006.
5. Rivest, R. (1992, April). The MD5 Message Digest Algorithm. Request for Comments (RFC) 1321. Retrieved from https://www.rfceditor.org/rfc/rfc1321.txt
6. Kioon M. C, Wang Z. S, Shubra D.D Security Analysis of MD5 Algorithm in Password Storage // Scientific.Net. 2013. С. 2706-2711.
8. John Black, Martin Cochran, Trevor Highland Fast Software Encryption. FSE изд. 2006. С. 262-277.
Национальная библиотека им. Н. Э. Баумана
Bauman National Library
Персональные инструменты
MD5 (Message Digest 5)
| General | |
|---|---|
| Designers | Ronald Rivest |
| First published | April 1992 |
| Series | MD2, MD4, MD5, MD6 |
| Cipher detail | |
| Digest sizes | 128 bit |
| Block sizes | 512 bit |
| Structure | Merkle–Damgård construction |
| Rounds | 4 [1] |
| Best public cryptanalysis | |
| A 2013 attack by Xie Tao, Fanbao Liu, and Dengguo Feng breaks MD5 collision resistance in 2 18 time. This attack runs in less than a second on a regular computer. [2] | |
MD5 (Message Digest 5) — 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 году. Предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. Является улучшенной в плане безопасности версией MD4. Зная MD5-образ (называемый также MD5-хеш или MD5-дайджест), невозможно восстановить входное сообщение, так как одному MD5-образу могут соответствовать разные сообщения. Используется для проверки подлинности опубликованных сообщений путём сравнения дайджеста сообщения с опубликованным. Эту операцию называют «проверка хеша» (hashcheck). Описан в RFC 1321.
Содержание
История
MD5 — один из серии алгоритмов по построению дайджеста сообщения, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института. Разработан в 1991 году, как более надёжный вариант предыдущего алгоритма MD4. Позже Гансом Доббертином были найдены недостатки алгоритма MD4.
В 1993 году Берт ден Боер (Bert den Boer) и Антон Босселарис (Antoon Bosselaers) показали, что в алгоритме возможны псевдоколлизии, когда разным инициализирующим векторам соответствуют одинаковые дайджесты для входного сообщения.
В 1996 году Ганс Доббертин (Hans Dobbertin) объявил о коллизии в алгоритме и уже в то время было предложено использовать другие алгоритмы хеширования, такие как Whirlpool, SHA-1 или RIPEMD-160.
Из-за небольшого размера хеша в 128 бит, можно рассматривать birthday атаки. В марте 2004 года был запущен проект MD5CRK с целью обнаружения уязвимостей алгоритма, используя birthday атаки.
Проект 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
На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Длина сообщения может быть любой (в том числе нулевой). Запишем длину сообщения в L. Это число целое и неотрицательное. Кратность каким-либо числам необязательна. После поступления данных идёт процесс подготовки потока к вычислениям.
Ниже приведены 5 шагов алгоритма:
Шаг 1. Выравнивание потока
Сначала дописывают единичный бит в конец потока(байт 0x80), затем необходимое число нулевых бит. Входные данные выравниваются так, чтобы их новый размер L’ был сравним с 448 по модулю 512 (L’ = 512 × N + 448). Выравнивание происходит, даже если длина уже сравнима с 448.
Шаг 2. Добавление длины сообщения
Шаг 3. Инициализация буфера
Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения шестнадцатеричными числами (шестнадцатеричное представление, сначала младший байт):
В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется инициализирующим вектором.
Определим ещё функции и константы, которые нам понадобятся для вычислений.
Шаг 4. Вычисление в цикле
Заносим в блок данных элемент n из массива. Сохраняются значения A, B, C и D, оставшиеся после операций над предыдущими блоками (или их начальные значения, если блок первый).
AA = A BB = B CC = C DD = D
Суммируем с результатом предыдущего цикла:
После окончания цикла необходимо проверить, есть ли ещё блоки для вычислений. Если да, то изменяем номер элемента массива (n++) и переходим в начало цикла.
Шаг 5. Результат вычислений
Результат вычислений находится в буфере ABCD, это и есть хеш. Если выводить побайтово начиная с младшего байта A и закончив старшим байтом D, то мы получим MD5 хеш.
Сравнение MD5 и MD4
Алгоритм MD5 происходит от MD4. В новый алгоритм добавили ещё один раунд, теперь их стало 4 вместо 3 в MD4. Добавили новую константу для того, чтобы свести к минимуму влияние входного сообщения, в каждом раунде на каждом шаге и каждый раз константа разная, она суммируется с результатом F и блоком данных. Изменилась функция G = XZ v (Y not(Z)) вместо (XY v XZ v YZ). Результат каждого шага складывается с результатом предыдущего шага, из-за этого происходит более быстрое изменение результата. Изменился порядок работы с входными словами в раундах 2 и 3.
Различия в скорости работы представлены в таблице:
| MD5 | MD4 | |||
|---|---|---|---|---|
| RFC | 2,614 сек | 37 359 Кб/с | 2,574 сек | 37 940 Кб/с |
| OpenSSL | 1,152 сек | 84 771 Кб/с | 0,891 сек | 109 603 Кб/с |
Необходимо было вычислить 10 000 хешей для сообщения длиной 10 000 байт. В качестве реализаций использовались OpenSSL и RFC 1321.
MD5 — что это такое, для чего нужно и как получить хеш онлайн
MD5 или Message Digest 5 это 128-битный алгоритм хеширования который разработан в начале 90-х годов профессором Рональдом Ривестом. В основном, представляется как последовательность из 32 шестнадцатеричных цифр, к примеру: 1bc29b36f623ba82aaf6724fd3b16718. Чтобы понять что такое MD5 сначала надо освоиться с понятием хеширование.
Что такое хеширование
Хеширование это процесс преобразования любого массива данных в выходную строку фиксированной длины. Это преобразование проводится с помощью, так называемых, хеш-функций. Такая функция на входе получает массив данных, а на выходе возвращает так называемый хеш (хеш-суму) – уникальную строку фиксированной длины.
Алгоритм работы хеш-функции построен таким образом, что для любого массива данных функция выдает уникальную строку. Ввиду этой особенности полученная строка может использоваться как цифровой отпечаток данных. Такой отпечаток можно юзать для проверки целостности данных.
К примеру, когда разработчик программного обеспечения публикует в сети свой программный продукт, вместечке с ним он может опубликовать его хеш. Это позволит юзерам проверить целостность программы перед ее установкой. Ели программа была заражена вирусами или загрузилась с ошибками, ее хеш не будет соответствовать хешу, который был опубликован разработчиком программы.
История развития MD5
Алгоритм MD5 был разработан профессором Рональдом Л. Ривестом из Массачусетского технологического института в 1991 году. Данный алгоритм стал заменой предыдущей версии алгоритма MD4. С этого времени алгоритм обрел большую популярность и стал использоваться повсеместно.
Начиная с 1993 года, регулярно появляются исследования, которые обнаруживают все новые уязвимости в алгоритме MD5. На данный момент алгоритм MD5 считается уязвимым и постепенно заменяется алгоритмом SHA.
Как получить хеш MD5
Чтобы получить MD5 хеш при помощи этого сервиса достаточно ввести строку в поле и нажать на кнопку «Hash». Поле этого появится хеш введенной строки.
Если же вам следует получить MD5 хеш файла, то придётся юзать специальные программы, к примеру, MD5summer ( http://www.md5summer.org/download.html ).
Работать с этой программой очень просто. Чтобы получить MD5 хеш файла достаточно запустить программу и выбрать нужный файл.
Проблемы надежности MD5
Казалось бы, такая характеристика MD5 должна обеспечивать 100% гарантии неуязвимости и сохранения данных. Но даже этого оказалось мало. В ходе проводимых исследований учеными был выявлен целый ряд прорех и уязвимостей в этом уже распространенном на тот момент алгоритме. Основной причиной слабой защищенности MD5 значится относительно легкое нахождение коллизий при шифровании.
Под коллизией понимают возможность получения одинакового результата вычислений хеш-функции при разных входных значениях.
Проще говоря, чем больше вероятность нахождения коллизий, тем надежность используемого алгоритма ниже. Вероятность нахождения коллизий при шифровании более надежными хеш-функциями практически сводится к 0.
То есть большая вероятность расшифровки паролей MD5 значится основной причиной отказа от использования этого алгоритма. Многие криптологи (специалисты по шифрованию данных) связывают низкую надежность MD5 с малой длиной получаемого хеш-кода.
Область применения алгоритма хеширования:
Основы безопасности при использовании MD5
Данный стандарт кодирования значится одним из самых распространенных методов защиты данных не лишь в прикладном, но и в веб-программировании. Так что не будет лишним обезопасить свой md5 hash от намеренного взлома.
Основным способом, гарантирующим безопасность хеша вашего пароля, значится использование «соли». Он основан на добавлении к паролю нескольких случайных символов и последующем хешировании результата.
Во многих языках программирования для этого используются специальные классы и функции. Не являются исключением из правил и серверные языки программирования.
Создать хеш-код MD5 в php можно при помощи нескольких функций:
При использовании функции md5() в PHP для задания значения соли используют методы генерации случайных чисел. К примеру, rand():
Помимо применения «соли» было разработано еще несколько методов защиты хеша MD5:
В материале приведены лишь начальные сведения об обеспечении безопасности хеша, полученного при помощи этого алгоритма. Самым простым и эффективным из них значится использование уникального значения «соли», которая даёт возможность существенно «насолить» злоумышленнику и «подсластить» жизнь владельцу взламываемого пароля.