Есть задача создания системы доступа навигационного устройства (трекера) к узлу связи (серверу) на основе открытого ключа, зашифрованного по MD5. Знаю, что существует множество сайтов, для поиска подходящей коллизии по MD5 отпечатку. Насколько полны те базы с уже сгененированными хэшами?
Какова вероятность подбора исходного ключа за незначительное время (несколько дней) по MD5 хэшу, если длина исходного ключа равна 32символа?
13 сентября 2009 в 12:02
блиин, точно, это же всего-лишь коллизии там да велика вероятность зная прообраз что будут коллизии отличающиеся на 1-2 символа, но без исходного файла подобрать данные так и есть очень сложно.
подобрать колизию к данному паролю и подобрать какой-либо пароль по его хешу это разные задачи. устойчивость md5 осталась где положено, искать коллизию можно если вы хотите md5 использовать как цифровую подпись, а хранить хеш вполне надёжно.
12 сентября 2009 в 1:01
Подбор коллизий требует разных временных затрат, в частности, подробнее можно прочитать здесь: //www.mscs.dal.ca/~selinger/md5collision/
В том, что касается брута, чистые RT уже почти никто не использует, используются параллельные вычисления на основе CUDA (о разнице в производительности по сравнению с четырех ядерным процессором можно почитать в интернете), как правило – вкупе с таблицами для гибридной атаки.
Вообще же, если серьезные люди за ТС охотиться не будут, то можно спокойно использовать сальтованый хэш – вомзножность взломать его за адекватное время у скрипт киддисов, которыми сейчас по большей части населены хакирьские говносайтики стремится к нулю примерно с той же скоростью, что последовательность "единица на эн факториал".
12 сентября 2009 в 0:05
#14
Да админы просто поменяют хранимый у них хеш на новый.
Имхо пароль можно и по хешу проверять, но хранимые данные тож им шифровать. Т.е. для входа в ОС надо ввести пароль, а сами юзерские данные на винте за этим же паролем и сидят (но уже по криптоалгоритму). Ну подобрали мы коллизию, ну пустила ОС внутрь, но данные то под другим паролем… Хотя наф такое, забыл пароль и все прощайте данные…
12 сентября 2009 в 0:05
ЗЫ, на вики пример есть
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70
и
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70
имеют одинаковый MD5 хеш
79054025255fb1a26e4bc422aef54eb4 и не сильно отличаются то
12 сентября 2009 в 0:04
Алиев Shooshpanchik Дамир, если бы можно было однозначно подобрать прообраз то это был бы метод супер сжатия, естественно интересует подбор какого либо варианта.
"И подобрать такие данные чтоб получилась коллизия зверски трудно." вот ия так же думал, часто хранят на сервере не сам пароль а его хеш, потому и говорят что мол помочь восстановить пароль не можем, максимум это имея права админа переустановить, но если зная хеш можно подобрать какой либо пароль который примет сервак…
#11, а это не липа случаем была? полно слухов по сети гуляет не все они достоверны… ты сам пробовал или реальные авторитетные издания анализировали эту ситуацию? просто он реально считается хорошим хешем… а без алгоритма хранить полную таблицу из 32 байтного адреса это не реально. хранить всякие qwer, 12345 можно 3gpo можно, а дальше уже или нужен алгоритм с зависимостями или программа должны быть хорошим экстрасенсом.
12 сентября 2009 в 0:01
хотя случайное совпадение маловероятно, создать колиизию все-таки можно. это позволяет по хешу пароля подобрать что-нибудь подходящее. хранить хеши паролей в таблице – обычная практика, а получить эту таблицу можно различными путями.
11 сентября 2009 в 23:02
MD5 (англ. Message Digest 5) — 128-битный алгоритм ХЕШИРОВАНИЯ. (Это не криптоалгоритм). Т.е. он позволяет проверить являются ли данные теми же от которых создан хеш, но не позволяет восстановить по хешу эти данные.
(См. также Алгоритмы хеширования CRC16, CRC32, MD4, MD6, HAVAL, SHA-1, SHA-2)
Входные данные выравниваются так, чтобы их размер был сравним с 448 по модулю 512 (L’ = 512 × N + 448). Сначала дописывают единичный бит в конец потока, затем необходимое число нулевых бит (выравнивание происходит, даже если длина уже конгруэнтна — сравнима с 448).
В оставшиеся 64 бита дописывают 64-битное представление длины данных до выравнивания. Если длина превосходит 264 − 1, то дописывают только младшие биты. После этого длина потока станет кратной степеням двойки — 16, 32. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.
Коллизия хеш-функции — это получение одинакового значения функции для разных сообщений и идентичного начального буфера.
Т.е. на пяльцах – есть два файла, один размером 1Мб, второй 1Гб. А MD5-хеш у них совпал.
Ну и хусть совпал, но восстановить оригинальное сообщение по этому 128-битному хешу невозможно. И подобрать такие данные чтоб получилась коллизия зверски трудно. Изменение всего 1 бита ведет к огромному изменению в хеше.
11 сентября 2009 в 22:00
ну как сказать. как хеш-функция MD5 действительно неплох – дает хорошее распределение на большинстве входных данных. поэтому зачем переписывать то, что хорошо работает? а для одностороннего шифрования паролей можно использовать и другие алгоритмы.
про файлы – что-то там темное было. ты им три файла (ограничение, если и было, измерялось десятками килобайт – не суть важно, в общем) – они тебе три файла.
11 сентября 2009 в 9:00
вот и меня по началу удивило что по хешу md5 научились подбирать проообраз, и тихо так вокруг, куча софта не переписывается, а хранить таблицы хеша это отдельная тема и она под любые алгоритмы годится, другое дело время их генерации и объём.
только как-же тогда с файлами народ подбирал такие же? или это на файлы до 8 символов распространялось? (извините если вопросы ламерские, просто интересно с целью повышения самообразовыванности, как-то в голове засело что md5 хорошая хеш функция и кучу криптотестов выдерживала в моё время.)
11 сентября 2009 в 1:01
32 символа нам не осилить. + еще соль.
В примере расчет на НЕ БОЛЕЕ 8 СИМВОЛОВ.
Или ты 32 бита имел в ввиду ?
11 сентября 2009 в 0:05
мда уж, похоже надо думать что иное…
кстати, в группе "программисты" 20 тыс человек. Еслизапустить распараллеленную задачу расчета таблиц среди этой группы в течение часа, то можно считать, что MD5 – пустое место!
Ну это так… информация к размышлению!
11 сентября 2009 в 0:00
//ru.wikipedia.org/wiki/Rainbow_table
Хотя применение радужных таблиц облегчает использование метода грубой силы (bruteforce) для подбора паролей, в некоторых случаях необходимые для их генерации/использования вычислительные мощности не позволяют одиночному пользователю достичь желаемых результатов за приемлемое время. К примеру для паролей длиной не более 8 символов, состоящих из букв, цифр и специальных символов !@#$%^&*()-_+= захешированных алгоритмом MD5 могут быть сгенерированы таблицы со следующими параметрами:
длина цепочки 1400
количество цепочек 50 000 000
количество таблиц 800
При этом вероятность нахождения пароля с помощью данных таблиц составит 0.7542 (75.42 %), сами таблицы займут 596 Гб, генерация их на компьютере уровня Пентиум-3 1ГГц займёт 3 года а поиск 1 пароля по готовым таблицам не более 22 минут.
Однако процесс генерации таблиц возможно распараллелить, например расчёт одной таблицы с вышеприведёнными параметрами занимает примерно 33 часа. В таком случае если в нашем распоряжении есть 100 компьютеров, все таблицы можно сгенерировать через 11 суток.
Защита от радужных таблиц
Один из распространённых методов защиты от взлома с помощью радужных таблиц — использование необратимых хеш-функций, которые включают salt («соль», или «затравка»). Например, рассмотрим следующую функцию для создания хеша от пароля:
хеш = MD5( пароль + соль ),
где + обозначает конкатенацию.
Для восстановления такого пароля взломщику необходимы таблицы для всех возможных значений затравки.
По сути, затравка увеличивает длину и возможно сложность пароля. Если таблица рассчитана на некоторую длину или на некоторый ограниченный набор символов, то затравка может предотвратить восстановление пароля.
10 сентября 2009 в 23:05
брутить – дело дурное. лучше посчитайте немного.
10 сентября 2009 в 23:04
Не знаю, как вы – но я до сих пор свой хеш разбрутить не могу =)
В неопытных руках это сильная защита.
10 сентября 2009 в 23:02
еще года как 2 назад умелии вызывать коллизии в течении нескольких часов
10 сентября 2009 в 23:00
А если использовать "соленый" хэш, то подбор сильно усложнится…
10 сентября 2009 в 23:00
MD5 уже давно ненадежен. какие-то люди уже принимали от всех желающих файлы и возвращали другие с таким же MD5.