Pull to refresh

Comments 50

А где наш ГОСТ 28147-89, DES, AES (Advanced Encryption Standard), Triple DES…?
Речь идет об алгоритмах хэширования, а не об алгоритмах шифрования.
Тогда говорить о «взломе» не совсем корректно.

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

Взлом — немного другое.

Шкалу скорее надо перевести как «Не сломам» «Ослаблен» «сломан»
Это уже к автору статьи ;)
UFO just landed and posted this here
Помню в начале века, ещё во времена повальной популярности PHP3 и Delphi, появился какой-то новый алгоритм хэширования ГОСТ Р (не помню номер). Говорили что он мега крут и даже на англоязычных ресурсах писали как он лучше традиционного MD5.

Вроде как в этом году написали что он сломан (хотя, может быть, это как раз не о нём, а об алгоритме шифрования).
Хм… не ругайте строго, слово хэш дошло позже когда все алгоритмы прочитал) И просто очень наш гост люблю и его таблицы замены, он для меня во всех отношениях бессмертен)
Уточним: а где наш ГОСТ 34.11-94?
(до 2011 — зеленый, с 2011 — бледно-желтый)
Вот ведь — и сам попался. Прошу последнюю строчку предыдущего поста не читать…
UFO just landed and posted this here
UFO just landed and posted this here
Если быть совсем точно, в оригинале про «чуваков со слэшдота», на русский это можно перевести как «чуваки с Хабра» или «гики», я выбрал более скромный вариант. :)
Тоже протоны во вселенной считали? :)
У нас на лекциях по криптографии считали…
Надо бы Sony кинуть ссылочку на табличку.
саркастично: это интересно, взял md5 от фильма какого-нибудь, записал карандашом в блокнот хеш и исходную длину, пришёл домой, декодировал назад в видео файл, посмотрел. Зашибись, нафиг носители)
Коллизии, всё таки, не обратимость…
Можно подбирать до тех пор пока формат файла не станет похожим на видеофайл ;)
Я думаю даже при MD5-хеш + длина файла там всё равно будет в коллизиях пару фильмов с разным сюжетом :D.
Это будет как бонус
Пару фильмов? ЕМНИП, MD5 — блочный, а значит коллизия блока в 512 байт будет давать тот же хэш. Вроде даже на Хабре проскакивала статья с «хорошим» и «плохим» exe с одинаковым MD5. Так что «фильмов» будет далеко не пара ;)
Тут скорее записав хэш от Матрицы рискуешь дома посмотреть Утомленные солнцем :)
Хотя все, конечно, сложнее.
Вроде китайцы придумали, как создать два файла с одинаковыми хешами.
Верно. Китайский док уместился всего на четырех страницах, а какие последствия для индустрии :)
Мне вот интересно, как же до сих пор живы торренты, заточенные под использование SHA-1? По логике вещей, правоторговцам следовало бы наводнить файлообмен файлами-пустышками, подобранными под коллизии — почему же этого до сих пор не случилось?
Видимо пока никто не разглядел как извлечь из этого выгоду. Разве что так, побаловаться. Как только у кого-то созреет сулящая дивиденды схема — сразу и дело пойдет.
Я, признаться, тоже не вижу смысла заниматься такой ерудой.
объяснитесь подробнее.
да, файлокуски хэшируются по sha1, и собственно что?
По вышеизложенной табличке получается, что SHA-1 лет семь как «ослаблен».

Если слабость хэша состоит в упрощении создания коллизий, то правоторговцы могли бы создавать фальшивые «файлокуски», которые с точки зрения протокола BitTorrent выглядели бы идентичными натуральным (за счёт коллизий), однако у потребителя в процессе потребления вызывали бы недовольство, которое со временем, накапливаясь, приводило бы к отвращению по отношению к торрентовому файлообмену.

Тем не менее, этого за последние семь лет не наблюдаем.

Стало быть, либо SHA-1 не слишком-то ослаблен, либо я упускаю из виду некоторую важную деталь картины.

Поэтому задал вопрос.
Дело в том, что конструктивного алгоритма для создания коллизий до сих пор нет даже для MD5. Вышеупоминавшиеся китайцы придумали способ создавать абстрактные пары файлов с совпадающими хешами, но не генерить коллизию по существующему файлу.
как заставить пользователя использовать скомпроментированый торрент-файл?
разве что распространяя через открытые трекеры, но там всегда есть опасность скачать какой-то левый файл.
Речь идет о том, что если будет возможность создать кусок файла, SHA-1 которого совпадает с SHA-1 куска, который Вы качаете, то ничего делать собственно и не надо. Достаточно посидировать уже существующую раздачу, а там уже от банальной нечитаемости файла и до полной его подмены — вариантов для развлечений милион.

Другое дело, что, как уже сказали выше, сделать файл по готовому SHA-1 нельзя. Можно сделать 2 файла с одинаковым SHA-1.
Этому есть одно логичное обьяснение: копирастам намного проще устроить маски-шоу на очередной торрент-трекер, чем привлекать хитрые технические решения, которые тут же в качестве ответной реакции вызовут только новый шаг в «споре брони и снаряда».

А если вдруг, предположить, что все-таки копирасты начнут это делать? Что произойдет? Ну, да, сначала будет срач и паника. А потом, недельки через две, выходят два расширения протокола bittorent. Первое расширение самой структуры torrent-файла — в info секцию добавляется еще один ключик — хеш кусков данных с другой хеш-функцией с другим, укрупненным размером куска (типа, подбирать чтобы все куски файла имели идентичные хешфункции по двум алгоритмам хеширования да еще если размер кусков разный задолбятся). Сохраняется совместимость со старыми торрент-клиентами, а новые, обновленные клиенты, будут легко выпаливают говнофайлы. А второе расширение самого протокола bittorent — blacklist exchange (аналог peer exchange), по которому те, кто распостраняет такие говнофайлы быстро попадают в блеклист.
Это некоторая путаница в терминах. Пусть h — хеш-функция. Есть разные задачи:
1. Поиск коллизий. Ищутся такие x,y, что h(x) = h(y).
2. Поиск прообраза. Дано a, ищется такое x, что h(x) = a.
3. Поиск второго прообраза. Дано a, ищется такое y, не равное a, что h(y) = h(a).

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

В криптографии слова «хеш-функция скомпрометирована» означают «для хотя бы одной задачи найдено решение существенно быстрее, чем в случае абстрактной хеш-функции». Отсюда отнюдь не следует, что есть решения других задач.
Судя по таблице, вы — ГИК!
Понравилась табличка, судя по которой за последние 8 лет ничего нового не взломали и вывод, что способы хэширования владельцам сайтов нужно менять каждые пару лет, желтая пресса в действии.
Просто надо в Хабраюмор перенести.
осталось придумать способ, как в базе сменить одни хэши паролей на другие хэши паролей.
в принципе это довольно просто. добавляем колонку переведена запись на новый хеш или нет (в начале вся колонка false). потом при авторизации пользователя, если запись не переведена, введённый пароль подошёл и пользователь авторизован, пересохраняем хеш новым алгоритмом и значение колонки ставим в true. так постепенно переведём всю базу.
Как же быть с теми, кто не заходил на сайт, они же все опасносте!
дык никак, оригинала-то нет.
даже если подобрать под всех остальных коллизии, вы рискуете, что пользователь не зайдёт в след. раз на сайт, т.к. коллизия != сам оригинал.
Если у есть связи в ФСБ, то можно попросить базу ваших паролей…
Можно в базе заменить старые хэши f(x) на новые g(f(x)) [f — старая функция хэширования, g — новая]. Коллизии будут расти, но в большинстве случаев это будет приемлемо. Ну и соответственно при авторизации придется вычислять g(f(x)) вместо g(x). При желании можно добавить соли.
Радует, что на SHA-3 устроен полноценный конкурс. Это вселяет надежду, что миграция будет требоваться всё-таки пореже, чем раз в два года.
Хорошая статья.

Жаль только что табличка заканчивается 2009-ым годом. Да что SHA-2 на варианты не разделена (а то SHA-224 и SHA-512 имеют очевидно весьма разную стойкость). Да что жёлтый цвет в табличке есть (а то я его не люблю он, по методикам жёлтой прессы, информации не даёт, а только запугивает; ибо уменьшить количество операций, необходимое для взлома, с 2256 до 28, или с 2256 до 2254 — это одинаковый жёлтый прямоугольник, но совершенно разная опасность).

А в остальном — хорошая статья. Полезная.
MD5 Взлома? да и еще 2004 ом году? стыдно признаться, но я не зал.
UFO just landed and posted this here
Sign up to leave a comment.

Articles