как расшифровать хеш код
«Привет, мир»: разбираем каждый шаг хэш-алгоритма SHA-256
Что такое хэш-функция?
Три основных цели хэш-функций:
SHA-256 «Привет, мир»
Шаг 1 — Предварительная работа
Преобразуем «Привет, мир» в двоичный код:
Дополните код нулями, пока данные не станут равны 512 бит, минус 64 бита (в результате 448 бит):
Добавьте 64 бита в конец в виде целого числа с порядком байтов от старшего к младшему (big-endian), представляющего длину входного сообщения в двоичном формате. В нашем случае это 88, или «1011000».
Теперь у нас есть ввод, который будет делиться на 512 без остатка.
Шаг 2 — Инициализируйте значения хэша (h)
Теперь мы создаем 8 хэш-значений. Это жестко запрограммированные константы, которые представляют собой первые 32 бита дробных частей квадратных корней из первых восьми простых чисел: 2, 3, 5, 7, 11, 13, 17, 19.
Шаг 3 — Инициализация округленных констант (k)
Как и в предыдущем шаге, мы создадим еще несколько констант. На этот раз их будет 64. Каждое значение (0—63) представляет собой первые 32 бита дробных частей кубических корней первых 64 простых чисел (2—311).
Шаг 4 — Цикл фрагментов
Следующие шаги будут выполняться для каждого 512-битного «фрагмента» из наших входных данных. Поскольку фаза «Привет, мир» короткая, у нас есть только один фрагмент. В каждой итерации цикла мы будем изменять хэш-значения h0-h7, что приведет нас к конечному результату.
Шаг 5 — Созданием расписание сообщений (w)
Скопируйте входные данные из шага 1 в новый массив, где каждая запись представляет собой 32-битное слово:
Добавьте еще 48 слов, инициализированных нулем, чтобы у нас получился массив w [0… 63]
Измените обнуленные индексы в конце массива, используя следующий алгоритм:
Для i из w[16…63]:
В расписании сообщений осталось 64 слова (w):
Шаг 6 — Сжатие
Инициализируйте переменные a, b, c, d, e, f, g, h и установите их равными текущим значениям хэш-функции соответственно h0, h1, h2, h3, h4, h5, h6, h7.
Запустите цикл сжатия, который изменит значения a… h. Выглядит он следующим образом:
Все вычисления выполняются еще 63 раза, меняя переменные a-h. К счастью, мы не делаем это вручную. В итоге мы получили:
Шаг 7 — Измените окончательные значения
После цикла сжатия, во время цикла фрагментов, мы изменяем хеш-значения, добавляя к ним соответствующие переменные a-h. Как и ранее, все сложение производится по модулю 2 ^ 32:
Шаг 8 — Финальный хэш
Наконец, соединяем все вместе.
Мы прошли каждый шаг (за исключением нескольких итераций) SHA-256 в подробностях. Если хотите увидеть весь путь, что мы совершили, в форме псевдокода, заходите на WikiPedia.
Хеширование и расшифровка MD5 хеш-кода
Что такое MD5?
MD5 является одним из алгоритмов хеширования на 128-битной основе. Под хешированием понимают преобразование входных данных по определенному алгоритму в битовую строку определенной длины. При этом полученный в ходе вычислений результат представлен в шестнадцатеричной системе исчисления. Она называется хешем, хеш-суммой или хеш-кодом.
Процесс хеширования широко применяется в программировании и веб-индустрии. В основном для создания уникальных значений в ассоциативных массивах, идентификаторов.
Область применения хеш-кодов:
MD5 как стандарт хеширования был разработан в 1991 году для создания уникального хеш-кода от заданного значения с последующей проверкой его подлинности.
То есть хеш, полученный от функции, работа которой основана на этом алгоритме, выдает строку в 16 байт (128) бит. И эта строка включает в себя 16 шестнадцатеричных чисел. При этом изменение хотя бы одного ее символа приведет к последующему бесповоротному изменению значений всех остальных битов строки:
Проблемы надежности MD5
Казалось бы, такая характеристика MD5 должна обеспечивать 100% гарантии неуязвимости и сохранения данных. Но даже этого оказалось мало. В ходе проводимых исследований учеными был выявлен целый ряд прорех и уязвимостей в этом уже распространенном на тот момент алгоритме. Основной причиной слабой защищенности MD5 является относительно легкое нахождение коллизий при шифровании.
Проще говоря, чем больше вероятность нахождения коллизий, тем надежность используемого алгоритма ниже. Вероятность нахождения коллизий при шифровании более надежными хеш-функциями практически сводится к 0.
То есть большая вероятность расшифровки паролей MD5 является основной причиной отказа от использования этого алгоритма. Многие криптологи ( специалисты по шифрованию данных ) связывают низкую надежность MD5 с малой длиной получаемого хеш-кода.
Область применения алгоритма хеширования:
Обзор средств для декодирования хеш-кода MD5
Иногда при работе с компьютером или поврежденными базами данных требуется декодировать зашифрованное с помощью MD5 значение хеша.
Удобнее всего использовать специализированные ресурсы, предоставляющие возможность сделать это online :
Если происмотреться к значениям декодинга, отображенных на показонном выше рисунке, то становится понятно, что процесс расшифровки почти не дает результатов. Эти ресурсы представляют собой одну или несколько объединенных между собой баз данных, в которые занесены расшифровки самых простых слов.
При этом данные декодирования хеша MD5 даже такой распространенной части пароля как « админ » нашлись лишь в одной базе. Поэтому хеши паролей, состоящих из более сложных и длинных комбинаций символов, практически невозможно расшифровать.
Основы безопасности при использовании MD5
Этот стандарт кодирования является одним из самых распространенных методов защиты данных не только в прикладном, но и в веб-программировании. Поэтому не будет лишним обезопасить свой md5 hash от намеренного взлома.
Основным способом, гарантирующим безопасность хеша вашего пароля, является использование « соли ». Он основан на добавлении к паролю нескольких случайных символов и последующем хешировании результата.
Во многих языках программирования для этого используются специальные классы и функции. Не являются исключением из правил и серверные языки программирования.
Создать хеш-код MD5 в php можно с помощью нескольких функций:
При использовании функции md5() в PHP для задания значения соли используют методы генерации случайных чисел. Например, rand() :
Кроме применения « соли » было разработано еще несколько методов защиты хеша MD5 :
В статье приведены лишь начальные сведения об обеспечении безопасности хеша, полученного с помощью этого алгоритма. Самым простым и эффективным из них является использование уникального значения « соли », которая позволяет существенно « насолить » злоумышленнику и « подсластить » жизнь владельцу взламываемого пароля.
Чудеса хеширования
Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, защиту файлов и даже обнаружение зловредного ПО. Как они работают и где применяются?
Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, проверку целостности данных, защиту файлов и даже обнаружение зловредного ПО. Существует масса алгоритмов хеширования, отличающихся криптостойкостью, сложностью, разрядностью и другими свойствами. Считается, что идея хеширования принадлежит сотруднику IBM, появилась около 50 лет назад и с тех пор не претерпела принципиальных изменений. Зато в наши дни хеширование обрело массу новых свойств и используется в очень многих областях информационных технологий.
Что такое хеш?
Если коротко, то криптографическая хеш-функция, чаще называемая просто хешем, — это математический алгоритм, преобразовывающий произвольный массив данных в состоящую из букв и цифр строку фиксированной длины. Причем при условии использования того же типа хеша длина эта будет оставаться неизменной, вне зависимости от объема вводных данных. Криптостойкой хеш-функция может быть только в том случае, если выполняются главные требования: стойкость к восстановлению хешируемых данных и стойкость к коллизиям, то есть образованию из двух разных массивов данных двух одинаковых значений хеша. Интересно, что под данные требования формально не подпадает ни один из существующих алгоритмов, поскольку нахождение обратного хешу значения — вопрос лишь вычислительных мощностей. По факту же в случае с некоторыми особо продвинутыми алгоритмами этот процесс может занимать чудовищно много времени.
Как работает хеш?
Например, мое имя — Brian — после преобразования хеш-функцией SHA-1 (одной из самых распространенных наряду с MD5 и SHA-2) при помощи онлайн-генератора будет выглядеть так: 75c450c3f963befb912ee79f0b63e563652780f0. Как вам скажет, наверное, любой другой Брайан, данное имя нередко пишут с ошибкой, что в итоге превращает его в слово brain (мозг). Это настолько частая опечатка, что однажды я даже получил настоящие водительские права, на которых вместо моего имени красовалось Brain Donohue. Впрочем, это уже другая история. Так вот, если снова воспользоваться алгоритмом SHA-1, то слово Brain трансформируется в строку 97fb724268c2de1e6432d3816239463a6aaf8450. Как видите, результаты значительно отличаются друг от друга, даже несмотря на то, что разница между моим именем и названием органа центральной нервной системы заключается лишь в последовательности написания двух гласных. Более того, если я преобразую тем же алгоритмом собственное имя, но написанное уже со строчной буквы, то результат все равно не будет иметь ничего общего с двумя предыдущими: 760e7dab2836853c63805033e514668301fa9c47.
Впрочем, кое-что общее у них все же есть: каждая строка имеет длину ровно 40 символов. Казалось бы, ничего удивительного, ведь все введенные мною слова также имели одинаковую длину — 5 букв. Однако если вы захешируете весь предыдущий абзац целиком, то все равно получите последовательность, состоящую ровно из 40 символов: c5e7346089419bb4ab47aaa61ef3755d122826e2. То есть 1128 символов, включая пробелы, были ужаты до строки той же длины, что и пятибуквенное слово. То же самое произойдет даже с полным собранием сочинений Уильяма Шекспира: на выходе вы получите строку из 40 букв и цифр. При всем этом не может существовать двух разных массивов данных, которые преобразовывались бы в одинаковый хеш.
Вот как это выглядит, если изобразить все вышесказанное в виде схемы:
Для чего используется хеш?
Отличный вопрос. Однако ответ не так прост, поскольку криптохеши используются для огромного количества вещей.
Для нас с вами, простых пользователей, наиболее распространенная область применения хеширования — хранение паролей. К примеру, если вы забыли пароль к какому-либо онлайн-сервису, скорее всего, придется воспользоваться функцией восстановления пароля. В этом случае вы, впрочем, не получите свой старый пароль, поскольку онлайн-сервис на самом деле не хранит пользовательские пароли в виде обычного текста. Вместо этого он хранит их в виде хеш-значений. То есть даже сам сервис не может знать, как в действительности выглядит ваш пароль. Исключение составляют только те случаи, когда пароль очень прост и его хеш-значение широко известно в кругах взломщиков. Таким образом, если вы, воспользовавшись функцией восстановления, вдруг получили старый пароль в открытом виде, то можете быть уверены: используемый вами сервис не хеширует пользовательские пароли, что очень плохо.
Вы даже можете провести простой эксперимент: попробуйте при помощи специального сайта произвести преобразование какого-нибудь простого пароля вроде «123456» или «password» из их хеш-значений (созданных алгоритмом MD5) обратно в текст. Вероятность того, что в базе хешей найдутся данные о введенных вами простых паролях, очень высока. В моем случае хеши слов «brain» (8b373710bcf876edd91f281e50ed58ab) и «Brian» (4d236810821e8e83a025f2a83ea31820) успешно распознались, а вот хеш предыдущего абзаца — нет. Отличный пример, как раз для тех, кто все еще использует простые пароли.
Еще один пример, покруче. Не так давно по тематическим сайтам прокатилась новость о том, что популярный облачный сервис Dropbox заблокировал одного из своих пользователей за распространение контента, защищенного авторскими правами. Герой истории тут же написал об этом в твиттере, запустив волну негодования среди пользователей сервиса, ринувшихся обвинять Dropbox в том, что он якобы позволяет себе просматривать содержимое клиентских аккаунтов, хотя не имеет права этого делать.
Впрочем, необходимости в этом все равно не было. Дело в том, что владелец защищенного копирайтом контента имел на руках хеш-коды определенных аудио- и видеофайлов, запрещенных к распространению, и занес их в список блокируемых хешей. Когда пользователь предпринял попытку незаконно распространить некий контент, автоматические сканеры Dropbox засекли файлы, чьи хеши оказались в пресловутом списке, и заблокировали возможность их распространения.
Где еще можно использовать хеш-функции помимо систем хранения паролей и защиты медиафайлов? На самом деле задач, где используется хеширование, гораздо больше, чем я знаю и тем более могу описать в одной статье. Однако есть одна особенная область применения хешей, особо близкая нам как сотрудникам «Лаборатории Касперского»: хеширование широко используется для детектирования зловредных программ защитным ПО, в том числе и тем, что выпускается нашей компанией.
Как при помощи хеша ловить вирусы?
Примерно так же, как звукозаписывающие лейблы и кинопрокатные компании защищают свой контент, сообщество создает списки зловредов (многие из них доступны публично), а точнее, списки их хешей. Причем это может быть хеш не всего зловреда целиком, а лишь какого-либо его специфического и хорошо узнаваемого компонента. С одной стороны, это позволяет пользователю, обнаружившему подозрительный файл, тут же внести его хеш-код в одну из подобных открытых баз данных и проверить, не является ли файл вредоносным. С другой — то же самое может сделать и антивирусная программа, чей «движок» использует данный метод детектирования наряду с другими, более сложными.
Криптографические хеш-функции также могут использоваться для защиты от фальсификации передаваемой информации. Иными словами, вы можете удостовериться в том, что файл по пути куда-либо не претерпел никаких изменений, сравнив его хеши, снятые непосредственно до отправки и сразу после получения. Если данные были изменены даже всего на 1 байт, хеш-коды будут отличаться, как мы уже убедились в самом начале статьи. Недостаток такого подхода лишь в том, что криптографическое хеширование требует больше вычислительных мощностей или времени на вычисление, чем алгоритмы с отсутствием криптостойкости. Зато они в разы надежнее.
Кстати, в повседневной жизни мы, сами того не подозревая, иногда пользуемся простейшими хешами. Например, представьте, что вы совершаете переезд и упаковали все вещи по коробкам и ящикам. Погрузив их в грузовик, вы фиксируете количество багажных мест (то есть, по сути, количество коробок) и запоминаете это значение. По окончании выгрузки на новом месте, вместо того чтобы проверять наличие каждой коробки по списку, достаточно будет просто пересчитать их и сравнить получившееся значение с тем, что вы запомнили раньше. Если значения совпали, значит, ни одна коробка не потерялась.
Определения типов хэшей при помощи скрипта hash-Identifier для расшифровки паролей
Когда вы имеете дело с неизвестным хэшем, первый шаг – корректная идентификация типа.
Определения типов хэшей при помощи скрипта hash-Identifier для расшифровки паролей
Хэши обычно используются для хранения конфиденциальной информации, как, например, учетных записей, которые не должны находиться в открытом виде. При помощи утилит наподобие Hashcat мы можем взломать эти хэши однако только в случае, если знаем алгоритм генерации. Используя инструменты навроде скрипта hash-identifier, можно легко определить тип любых хэшей, чтобы затем указать правильный режим при работе с Hashcat.
Помимо взлома хэшей hash-identifier также полезен для идентификации алгоритма, используемого при выдаче контрольной суммы для загрузки файлов. Кроме того, этот скрипт помогает определить, к какому приложению относится хэшированный файл или значение (например, SQL базе или какому-либо другому формату, специфичному для конкретного поставщика).
Что такое хэш и как расшифровать пароль?
Как было сказано ранее, пароли, извлекаемые из базы данных или компьютера, обычно хранятся в виде хэшей, а не в открытом виде. Функция хэширования преобразует пароли в хаотичный набор символов и чисел, которые не должны быть обратимы обратно в пароль.
Однако два или более одинаковых пароля, при использовании одной и той же функции, будут иметь один и тот же хэш. Соответственно, при помощи этой функции можно получить набор хэшей для списка паролей, а затем использовать этот перечень для обнаружения подходящего пароля. Подобным образом работает множество утилит для взлома.
Хотя хранение пароля в виде хэша лучше, чем в открытом виде, вероятность взлома все равно остается, если у злоумышленника хороший набор правил или словарь, которые можно использовать в Hashcat или другой подобной программе.
Если вы много работаете с хэшами, то легко увидите разницу между разными и часто используемыми типами.
Например, сможете ли вы на глаз определить, к какому типу относятся хэши, указанные ниже?
При использовании Hashcat для взлома этого хэша мы должны установить опцию –m с целью работы в нужном режиме. Для взлома хэша MD5 мы бы указали режим 0.
В итоге, установив нужный алгоритм и используя хороший словарь, после расшифровки хэша мы получили слово «hashcat».
Какие хэши поддерживаются?
На данный момент Hashcat в состоянии расшифровать большое количество хэшей. В репозитории на GitHub для утилиты hash-identifier список поддерживаемых хэшей очень внушителен:
Для начала нужно установить Python3 на вашем компьютере (есть версии для разных платформ). Кроме того, вам понадобится утилита Hashcat, которую можно загрузить, используя команду apt install hashcat, после обновления системы при помощи команд apt update и apt upgrade.
Если вы хотите сгенерировать ваши собственные хэши для тестового взлома, то можете воспользоваться командой в формате echo —n PLAINTEXT | (HASHTYPE)sum. Например, при создании хэша SHA1 для слова «nullbyte» я запустил следующую команду:
Шаг 1. Загрузка и установка Hash-Identifier
Установить скрипт, написанный на Python, – очень просто. Откройте терминал и запустите следующую команду:
Затем посмотрите содержимое директории hash-identifier:
Вы должны обнаружить файл hash—id.py, который можно запустить при помощи команды ниже:
Шаг 2. Идентификация неизвестных хэшей
В качестве пробного подхода при помощи hash-identifier попробуем опознать следующие пять неизвестных хэшей:
Для начала в командной строке вводим первую строку и быстро получаем результат, что скорее всего имеем дело с хэшем, используемым в MySQL, который попробуем взломать чуть позже.
Третий хэш опознается как SHA1:
Четвертый хэш опознается как SHA512:
Наконец, пятый и последний хэш опознается как MD5:
Все прошло без особых проблем. Следующий шаг – поиск нужного режима, соответствующего обнаруженному типу, который будет указываться в Hashcat во время взлома.
Шаг 3. Подбор режима в Hashcat
При поиске нужного режима мы можем взглянуть на огромный список хэшей, поддерживаемых в Hashcat. Сокращенный вариант с наиболее популярными типами приведен ниже:
В списке выше есть два примера, которые могут соответствовать первому хэшу (7196759210defdc0), рассмотренному нами в предыдущем шаге. На первый взгляд, режим 200 «MySQL323» наиболее соответствует. Подтвердить гипотезу можно при помощи проверки тестового хэша в hash-identifier.
Точное совпадение с нужным хэшем:
Если мы попробуем другой тип (300), то увидим, что результаты не совпадают.
Соответственно, еще раз убеждаемся, что режим 200 выбран правильно.
Шаг 4. Расшифровка хэша при помощи Hashcat
После идентификации типа хэша и подбора нужно режима можно приступать к расшифровке пароля в Hashcat. Вначале нужно создать словарь с паролями, который будет использоваться в Hashcat для атаки на хэш. В сети есть много доступных списков, например, RockYou, но в нашем случае мы будем создавать тестовый словарь example.dict с несколькими паролями.
Если вы все еще находитесь внутри скрипта hash-identifier, нажмите Ctrl—C, а затем откройте файл в текстовом редакторе nano, запустив следующую команду:
После добавления нескольких предполагаемых паролей, один из которых – «hashcat», нажимаем Ctrl—X для выхода из редактора и вводим Y, чтобы сохранить изменения в файле. Теперь мы можем использовать этот файл в качестве словаря вместе с ранее выбранным режимом для взлома хэша. Базовая команда выглядит примерно так:
Вместо значения HASH_VALUE указываем хэш 7196759210defdc0, вместо MODE_NUMBER – подобранный ранее режим 200. Результат работы показан ниже. Если у вас старая система, как в моем случае – нужно указать параметр –force.
В результате мы получили 7196759210defdc0:hashcat и смогли расшифровать хэш посредством сравнения с элементами словаря из файла example.dict.
Когда вы имеете дело с неизвестным хэшем, первый шаг – корректная идентификация типа. Хотя скрипт hash-identifier – не идеален, но позволяет без особых проблем опознать наиболее распространённые хэши и отличить разные типа хэшей, которые выглядят одинаково, но требуют разных режим работы в Hashcat. Даже если hash-identifier не уверен, с каким типом вы имеете дело, сравнение с результатами примеров с сайта Hashcat, может помочь в идентификации.
Надеюсь это руководство, посвященное опознанию неизвестных хэшей, вам понравилось.
Все методы взлома MD5
Содержание статьи
Ни для кого не секрет, что криптография прочно вошла в нашу жизнь. Интернет-сервисы, социальные сети, мобильные устройства — все они хранят в своих базах пароли пользователей, зашифрованные с помощью различных алгоритмов. Наиболее популярным таким алгоритмом сегодня, безусловно, является MD5. О способах его взлома и пойдет речь.
Немного о криптографии
Современная криптография включает в себя три направления: шифрование с закрытым ключом, шифрование с открытым ключом и хеширование. Сегодня мы поговорим о том, что такое хеширование и с чем его едят. В целом под хешированием понимают преобразование входных данных произвольной длины в выходную битовую строку фиксированной длины. Чаще всего хеш-функции применяют в процессе аутентификации пользователя (в базе данных обычно хранится хеш пароля вместо самого пароля) и для вычисления контрольных сумм файлов, пакетов данных и т. п. Одним из наиболее известных и широко используемых алгоритмов хеширования является MD5.
WARNING!
Вся информация предоставлена исключительно в ознакомительных целях. Ни редакция, ни автор не несут ответственности за любой возможный вред, причиненный материалами данной статьи.
Начало
Алгоритм MD5 представляет собой 128-битный алгоритм хеширования. Это значит, что он вычисляет 128-битный хеш для произвольного набора данных, поступающих на его вход. Этот алгоритм разработал профессор Рональд Ривест из Массачусетского технологического института в 1991 году для замены менее надежного предшественника — MD4. Алгоритм был впервые опубликован в апреле 1992 года в RFC 1321. После этого MD5 стал использоваться для решения самых разных задач, от хеширования паролей в CMS до создания электронно-цифровых подписей и SSL-сертификатов.
О том, что алгоритм MD5 можно взломать, впервые заговорили в 1993 году. Исследователи Берт ден Боер и Антон Боссиларис показали, что в алгоритме возможны псевдоколлизии. Через три года, в 1996-м, Ганс Доббертин опубликовал статью, в которой доказал наличие коллизий и описал теоретическую возможность взлома MD5. Это был еще не взлом, но в мире начались разговоры о необходимости перехода на более надежные алгоритмы хеширования, например SHA1 (на момент написания этой статьи уже было доказано, что коллизии имеются и в этом алгоритме, поэтому рекомендую использовать SHA2) или RIPEMD-160.
Первые атаки
Непосредственный взлом MD5 начался 1 марта 2004 года. Компания CertainKey Cryptosystems запустила проект MD5CRK — распределенную систему поиска коллизий. Целью проекта был поиск двух сообщений с идентичными хеш-кодами. Проект завершился 24 августа 2004 года, когда четыре независимых исследователя — Ван Сяоюнь, Фэн Дэнгуо, Лай Сюэцзя и Юй Хунбо — обнаружили уязвимость алгоритма, позволяющую найти коллизии аналитическим методом за более-менее приемлемое время. С помощью этого метода можно всего лишь за час выявить коллизии на кластере IBM p690 (жаль, что у меня нет такого дома). 🙂 Первого марта 2005 года было продемонстрировано первое использование указанной уязвимости на практике. Группа исследователей представила два сертификата X.509 с разными наборами ключей, но с идентичными контрольными суммами. В том же году Властимил Клима опубликовал алгоритм, позволяющий обнаруживать коллизии на обычном ноутбуке за несколько часов. В 2006 он пошел дальше. Восемнадцатого марта 2006 года исследователь обнародовал алгоритм, находящий коллизии за одну минуту! Этот метод получил название «туннелирование». В 2008 году на конференции Chaos Communication Congress была представлена статья о методе генерации поддельных сертификатов X.509. Фактически это был первый случай реального использования коллизий в алгоритме MD5.
Пример коллизии MD5-хешей
Хакер #156. Взлом XML Encryption
Большая работа была также проделана и для ускорения взлома хешей. В 2007 году Кевин Бриз представил программу, использующую Sony PlayStation3 для взлома MD5. Он сумел добиться очень неплохих результатов: 1,4 миллиарда MD5-хешей генерировались всего лишь за одну секунду! Уже через два года, в 2009-м, на BlackHat USA вышла статья об использовании GPU для поиска коллизий, что позволяло повысить его скорость в несколько раз, особенно если он выполнялся с помощью нескольких видеокарт одновременно.
Видеокарта ATI Radeon HD 4850 X2 позволяет генерировать до 2,2 миллиардов хешей в секунду!
Использование алгоритма MD5 в ЭЦП неприемлемо вследствие недостаточной устойчивости этого алгоритма к поиску коллизий.
Это конец?
В 2011 году IETF согласилось внести изменения в RFC 1321 (MD5) и RFC 2104 (HMAC-MD5). Так появился документ RFC 6151. Он признает алгоритм шифрования MD5 небезопасным и рекомендует отказаться от его использования. На мой взгляд, этот документ официально положил конец MD5. Однако, несмотря на то что алгоритм MD5 был официально признан небезопасным, существуют тысячи, если не десятки и сотни тысяч приложений, которые используют его для хранения паролей, в электронно-цифровых подписях и для вычисления контрольных сумм файлов. Кстати, 31 октября 2008 года NIST объявила конкурс среди криптографов. Цель конкурса — разработать алгоритм хеширования на замену устаревшим SHA1 и SHA2. На данный момент финалисты уже определены — это BLAKE, Gostl, JH, Keccak и Skein.
Ighashgpu: взлом с помощью GPU
Мы используем вышеприведенный способ для взлома одного определенного хеша, сгенерированного при помощи алгоритма MD5. Максимальная длина возможного пароля составляет семь символов. Через какое-то время пароль будет найден (qwerty). Теперь давай попробуем взломать еще один хеш, но с немного другими условиями. Пусть наш хеш имеет вид d11fd4559815b2c3de1b685bb78a6283, а включает в себя буквы, цифры, знак подчеркивания и имеет суффикс «_admin». В данном случае мы можем использовать перебор пароля по маске, чтобы упростить программе задачу:
Здесь параметр ‘-u’ позволяет указать набор символов, используемых при переборе, а параметр ‘-m’ задает маску пароля. В нашем случае маска состоит из шести произвольных символов, после которых идет сочетание «_admin». Подбор пароля также не составит никакого труда.
Коллизии
Коллизией в криптографии называют два разных входных блока данных, которые для одной и той же хеш-функции дают один и тот же хеш. Каждая функция на выходе дает последовательность битов определенной длины, которая не зависит от размера первоначальных данных. Отсюда следует, что коллизии существуют для любого алгоритма хеширования. Однако вероятность того, что ты сможешь найти коллизию в «хорошем» алгоритме, практически стремится к нулю. К сожалению или к счастью, алгоритмы хеширования могут содержать ошибки, как и любые программы. Многие хеш-функции либо уже были сломаны, либо скоро будут. В данном случае «сломать» — значит найти коллизию за время, которое много меньше заявленной бесконечности.
Ighashgpu: списки
Теперь давай попробуем взломать сразу несколько паролей одновременно. Предположим, что к нам в руки попала база данных хешей паролей. При этом известно, что каждый пароль оканчивается символами c00l:
Сохрани хеши в файле encrypted.dat и запусти Ighashgpu как указано ниже:
После завершения работы программы в папке Ighashgpu появится файл ighashgpu_results.txt со взломанными паролями:
Взломаные хеши из файла encrypted.dat
Ighashgpu: соль
Напоследок давай произведем взлом «подсоленного» хеша. Предположим, что хеш генерируется по следующему алгоритму:
В итоге мы получили следующий хеш: 42151cf2ff27c5181bb36a8bcfafea7b. Ighashgpu позволяет указывать «соль» в параметре «-asalt»:
И мы снова получили искомый пароль легко и быстро.
Занимательная математика
Для 8-символьного пароля, составленного из первых 126 символов ASCII, доступно 63 527 879 748 485 376 возможных комбинаций. Для 254 символов количество возможных комбинаций возрастает до 17 324 859 956 700 833 536, что аж в 2,7 миллиарда раз больше, чем людей на нашей планете. Если создать текстовый файл, содержащий все эти пароли, то он займет миллионы терабайт. Конечно, в современном мире это возможно, но стоимость хранения такого файла будет просто заоблачной.
Взлом MD5 в режиме турбо
Взлом хешей путем полного перебора даже на самом лучшем железе занимает довольно много времени, особенно если пароль больше восьми символов. Самый простой способ увеличить скорость подбора пароля — это создать базу данных всех хешей для определенного набора символов. В 80-х годах прошлого столетия хакеры полагали, что когда у них появится более мощное железо, 640 Кб памяти и жесткий диск размером в 10 Мб, то такая база станет реальностью и подбор любого пароля превратится в минутное дело. Однако железо развивалось, а мечта так и оставалась мечтой. Ситуация изменилась лишь в августе 2003 года, после того, как Филипп Оэшлин, доктор философии в области компьютерных сетей из Швейцарского технологического института в Лозанне, опубликовал свою работу о проблеме выбора оптимального соотношения место-время. В ней описывался метод взлома хеш-функций с помощью «радужных» таблиц. Суть нового метода заключается в следующем. Сначала необходимо выбрать произвольный пароль, который затем хешируется и подвергается воздействию функции редукции, преобразующей хеш в какой-либо возможный пароль (к примеру, это могут быть первые 64 бита исходного хеша). Далее строится цепочка возможных паролей, из которой выбираются первый и последний элементы. Они записываются в таблицу. Чтобы восстановить пароль, применяем функцию редукции к исходному хешу и ищем полученный возможный пароль в таблице. Если такого пароля в таблице нет, хешируем его и вычисляем следующий возможный пароль. Операция повторяется, пока в «радужной» таблице не будет найден пароль. Этот пароль представляет собой конец одной из цепочек. Чтобы найти исходный пароль, необходимо прогнать всю цепочку заново. Такая операция не занимает много времени, в зависимости от алгоритма построения цепочки это обычно несколько секунд или минут. «Радужные» таблицы позволяют существенно сократить объем используемой памяти по сравнению с обычным поиском. Единственный недостаток описанного метода состоит в том, что на построение таблиц требуется довольно много времени.
Теперь перейдем от слов к делу и попробуем взломать пару-тройку хешей паролей с помощью этого метода.
Rainbow tables
«Радужные» таблицы — это особый тип словаря, который содержит цепочки паролей и позволяет подобрать пароль в течение нескольких секунд или минут с вероятностью 85–99%.
«Радужный» взлом
Сначала необходимо определиться с программой. Лично мне нравитсяRainbowCrack, которая распространяется бесплатно и работает как на Windows, так и на Linux. Она поддерживает четыре алгоритма хеширования: LN/NTLM, MD5 и SHA1. Программа не требует установки, достаточно распаковать ее куда-нибудь на диск. После распаковки необходимо найти «радужные» таблицы для алгоритма MD5. Здесь все не так просто: их можно либо скачать бесплатно, либо купить, либо сгенерировать самостоятельно. Один из самых больших архивов бесплатных таблиц доступен на сайте проекта Free Rainbow Tables. Кстати, ты тоже можешь помочь проекту, если скачаешь клиент с сайта и присоединишься к распределенной международной сети, которая генерирует «радужные» таблицы. На момент написания статьи на этом сайте уже было доступно 3 Тб таблиц для алгоритмов MD5, SHA1, LM и NTLM. Если у тебя нет возможности слить такой объем информации, то на том же сайте можно заказать диски с «радужными» таблицами. На данный момент предлагается три пакета: LN/NTLM, MD5 и SHA1 — по 200 долларов каждый. Мы же сгенерируем таблицы самостоятельно. Для этого необходимо использовать программу rtgen, входящую в состав RainbowCrack. Она принимает следующие входные параметры:
Рассмотрим последние параметры подробнее:
В данном случае мы создаем таблицу паролей, состоящих из цифр и прописных букв латинского алфавита и имеющих длину от одного до семи символов. На моем Eee PC с процессором Intel Atom N450 этот процесс занял почти два дня :). В итоге я получил файл md5loweralpha-numeric#1-702000×975054890.rt размером в 1,5 Гб.
Далее полученную таблицу необходимо отсортировать, чтобы оптимизировать поиск нужной нам цепочки. Для этого запускаем rtsort.exe:
Ждем пару минут и таблица готова! Теперь можно ломать сами пароли. Для начала попробуем подобрать пароль для одного хеша: d8578edf8458ce06fbc5bb76a58c5ca4. Запускаем rcrack_gui.exe и выбираем Add Hash. в меню File. В появившемся окне вводим хеш и нажимаем OK. Теперь выбираем файл с «радужной» таблицей. Для этого используем пункт Search Rainbow Tables. в меню Rainbow Table. В открывшемся окне для выбора файла ищем файл с таблицей, у меня это md5_loweralpha-numeric#1-7_0_2000x97505489_0.rt, затем жмем Open. Через несколько секунд пароль у нас в руках! Аналогичную операцию можно произвести и над списком хешей из файла.
Генерирую радужную таблицу
«Радужные» таблицы vs. CPU vs. GPU
Я думаю, ты обратил внимание на то, насколько быстро Ighashgpu способен взламывать MD5-хеши полным перебором, и на то, что RainbowCrack делает это еще быстрее при наличии хорошей «радужной» таблицы. Я решил сравнить скорость работы этих программ. Для чистоты эксперимента я использовал программу MDCrack, которая осуществляет брут пароля на CPU (и является одной из лучших среди программ такого типа). Вот что получилось в результате для GPU (nVidia GeForce GT 220M), CPU (Intel Atom N450, два ядра) и «радужных» таблиц:
Как видишь, скорость перебора с использованием CPU намного меньше, чем с использованием GPU или «радужных» таблиц. Более того, большинство специализированных программ позволяет создать кластер из видеокарт, благодаря чему скорость перебора пароля увеличивается в разы. Я думаю, ты обратил внимание на то, что скорость подбора 4- и 5-символьного паролей ниже, чем скорость подбора пароля из шести или семи символов. Это связано с тем, что поиск пароля начинается только после загрузки таблицы в память. Получается, что из шестнадцати секунд в среднем тринадцать тратится на загрузку и три — на взлом хеша.
Радужная таблица изнутри
bit.ly/vEhdir — добавление нового алгоритма хеширования в RainbowCrack при помощи API.
bit.ly/vTSB9K — описание формата «радужной» таблицы.
Вместо заключения
В конце я бы хотел немного поговорить о защите твоих паролей. Во-первых, не используй уязвимые алгоритмы хеширования, такие как MD5 или SHA1. На данный момент стоит задуматься об использовании одной из криптографических хеш-функций SHA2 или SHA3 (как только опубликуют соответствующий стандарт). Во-вторых, не используй функции хеширования напрямую. Всегда старайся использовать «соль» и комбинировать различные алгоритмы. И в-третьих, выбирай сложные произвольные пароли длиной как минимум восемь символов. Конечно, это не защитит тебя от взлома на 100 %, но хотя бы усложнит жизнь злоумышленникам.