Жизненный цикл криптографических хэш-алгоритмов

[@sunswordred]

А где наш ГОСТ 28147-89, DES, AES (Advanced Encryption Standard), Triple DES…?

[@Aminuofu]

Речь идет об алгоритмах хэширования, а не об алгоритмах шифрования.

[@socialNoob]

Тогда говорить о «взломе» не совсем корректно.

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

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

Шкалу скорее надо перевести как «Не сломам» «Ослаблен» «сломан»

[@Aminuofu]

Это уже к автору статьи ;)

[@StrangeAttractor]

Помню в начале века, ещё во времена повальной популярности PHP3 и Delphi, появился какой-то новый алгоритм хэширования ГОСТ Р (не помню номер). Говорили что он мега крут и даже на англоязычных ресурсах писали как он лучше традиционного MD5.

Вроде как в этом году написали что он сломан (хотя, может быть, это как раз не о нём, а об алгоритме шифрования).

[@sunswordred]

Хм… не ругайте строго, слово хэш дошло позже когда все алгоритмы прочитал) И просто очень наш гост люблю и его таблицы замены, он для меня во всех отношениях бессмертен)

[@OLS]

Уточним: а где наш ГОСТ 34.11-94?
(до 2011 — зеленый, с 2011 — бледно-желтый)

[@OLS]

Вот ведь — и сам попался. Прошу последнюю строчку предыдущего поста не читать…

[@XuMiX]

www.securitylab.ru/news/405678.php
раз уж про гост речь зашла

[@alizar]

Если быть совсем точно, в оригинале про «чуваков со слэшдота», на русский это можно перевести как «чуваки с Хабра» или «гики», я выбрал более скромный вариант. :)

[@RomanL]

Тоже протоны во вселенной считали? :)

[@lunatik42]

У нас на лекциях по криптографии считали…

[@Evgin]

Надо бы Sony кинуть ссылочку на табличку.

[@Aco]

саркастично: это интересно, взял md5 от фильма какого-нибудь, записал карандашом в блокнот хеш и исходную длину, пришёл домой, декодировал назад в видео файл, посмотрел. Зашибись, нафиг носители)

[@PycBouH]

Коллизии, всё таки, не обратимость…

[@liq]

Можно подбирать до тех пор пока формат файла не станет похожим на видеофайл ;)

[@Iskin]

Я думаю даже при MD5-хеш + длина файла там всё равно будет в коллизиях пару фильмов с разным сюжетом :D.

[@Aco]

Это будет как бонус

[@NickLion]

Пару фильмов? ЕМНИП, MD5 — блочный, а значит коллизия блока в 512 байт будет давать тот же хэш. Вроде даже на Хабре проскакивала статья с «хорошим» и «плохим» exe с одинаковым MD5. Так что «фильмов» будет далеко не пара ;)

[@CapeCod]

Тут скорее записав хэш от Матрицы рискуешь дома посмотреть Утомленные солнцем :)
Хотя все, конечно, сложнее.

[@denisnomad]

Что произошло в 2004 году?

[@lunatik42]

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

[@CapeCod]

Верно. Китайский док уместился всего на четырех страницах, а какие последствия для индустрии :)

[@kljaver]

Перешёл на SHA-256 при использовании GPG после того, как объявили, что SHA-1 того.
Кому интересно, вот инструкция от дебианщиков www.debian-administration.org/users/dkg/weblog/48

[@Mithgol]

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

[@CapeCod]

Видимо пока никто не разглядел как извлечь из этого выгоду. Разве что так, побаловаться. Как только у кого-то созреет сулящая дивиденды схема — сразу и дело пойдет.
Я, признаться, тоже не вижу смысла заниматься такой ерудой.

[@mark_ablov]

объяснитесь подробнее.
да, файлокуски хэшируются по sha1, и собственно что?

[@Mithgol]

По вышеизложенной табличке получается, что SHA-1 лет семь как «ослаблен».

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

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

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

Поэтому задал вопрос.

[@lunatik42]

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

[@mark_ablov]

как заставить пользователя использовать скомпроментированый торрент-файл?
разве что распространяя через открытые трекеры, но там всегда есть опасность скачать какой-то левый файл.

[@Katagi]

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

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

[@lesha_penguin]

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

А если вдруг, предположить, что все-таки копирасты начнут это делать? Что произойдет? Ну, да, сначала будет срач и паника. А потом, недельки через две, выходят два расширения протокола bittorent. Первое расширение самой структуры torrent-файла — в info секцию добавляется еще один ключик — хеш кусков данных с другой хеш-функцией с другим, укрупненным размером куска (типа, подбирать чтобы все куски файла имели идентичные хешфункции по двум алгоритмам хеширования да еще если размер кусков разный задолбятся). Сохраняется совместимость со старыми торрент-клиентами, а новые, обновленные клиенты, будут легко выпаливают говнофайлы. А второе расширение самого протокола bittorent — blacklist exchange (аналог peer exchange), по которому те, кто распостраняет такие говнофайлы быстро попадают в блеклист.

[@CleverMouse]

Это некоторая путаница в терминах. Пусть h — хеш-функция. Есть разные задачи:
1. Поиск коллизий. Ищутся такие x,y, что h(x) = h(y).
2. Поиск прообраза. Дано a, ищется такое x, что h(x) = a.
3. Поиск второго прообраза. Дано a, ищется такое y, не равное a, что h(y) = h(a).

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

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

[@vanfukov]

Не подсказывайте им!

[@naum]

Судя по таблице, вы — ГИК!

[@sshz]

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

[@vanfukov]

Просто надо в Хабраюмор перенести.

[@nekt]

осталось придумать способ, как в базе сменить одни хэши паролей на другие хэши паролей.

[@GearHead]

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

[@sshz]

Как же быть с теми, кто не заходил на сайт, они же все опасносте!

[@GearHead]

дык никак, оригинала-то нет.
даже если подобрать под всех остальных коллизии, вы рискуете, что пользователь не зайдёт в след. раз на сайт, т.к. коллизия != сам оригинал.

[@Biga]

Если у есть связи в ФСБ, то можно попросить базу ваших паролей…

[@Regis]

Можно в базе заменить старые хэши f(x) на новые g(f(x)) [f — старая функция хэширования, g — новая]. Коллизии будут расти, но в большинстве случаев это будет приемлемо. Ну и соответственно при авторизации придется вычислять g(f(x)) вместо g(x). При желании можно добавить соли.

[@OverQuantum]

Радует, что на SHA-3 устроен полноценный конкурс. Это вселяет надежду, что миграция будет требоваться всё-таки пореже, чем раз в два года.

[@Honeyman]

Хорошая статья.

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

А в остальном — хорошая статья. Полезная.

[@Ruster]

MD5 Взлома? да и еще 2004 ом году? стыдно признаться, но я не зал.