logo
 
?

md5 как взломать

Двое моих знакомых, задавших в течение недели вопросы примерно одинаковые по сути (примерно в духе: «А я слышал, что MD5/SHA-1 уже взломан, почему мы до сих пор их используем ?

»), подтолкнули меня к написанию этой заметки, хотя основные события, описываемые ниже, произошли уже более 3 лет назад.

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

При этом эти идентификаторы: На сегодняшний день подавляющую долю применений хеш-функций «берут на себя» алгоритмы MD5, SHA-1, SHA-256, а в нашей стране еще и ГОСТ Р 34.11-94, являющийся де факто практически монополистом в сертифицированных ФАПСИ/ФСБ криптопродуктах.

Конечно, существует и множество других менее известных, или распространенных только в узких сообществах алгоритмов (например, RIPEMD, TIGER, PANAMA и др.) Достаточно долгое время (с середины 1990-х годов) уходящее поколение криптографических функций считалось весьма и весьма стойким.

И хотя в основе и MD5 и SHA-1 лежали идеи, заложенные в алгоритме MD4, который был взломан в начале 1990-х, улучшения предпринятые на этапе проектирования (а именно, увеличение количества проходов (раундов) при вычислении хеш-значения и более тщательная проработка применяемых математических операций) привели к тому, что вплоть до 2004 года семейство считалось неуязвимым к любого рода атакам.

Гром среди ясного неба прозвучал 16 августа 2004, когда группа китайских исследователей (под руководством X.

Wang) опубликовала на открытом сервере научных публикаций org безо всяких объяснений пары реальных коллизий для MD4, MD5, RIPEMD и HAVAL с единственным замечанием о том, что подбор этих входных текстов занял у них 1 час 5 минут. Сильнейшие криптографы вновь обратили свое внимание на семейство «MD5/SHA-1» и конечно на примеры, приведенные в прорывной статье. Несколько более продуманная чем у MD5 и RIPEMD-160 структура математических преобразований ограничивает лучшую из известных на сегодняшний день в открытых кругах реализаций атаки (предложенной, кстати, теми же китайцами) вычислительной трудоемкостью 2^63 операций. Даже с учетом экспоненциального роста производительности выч.техники вряд ли подбор хотя бы одной коллизии будет осуществим одним компьютером в ближайшие двадцать лет.

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

Здоровые амбиции (получить первую искусственную коллизию для SHA-1, кстати официально являющегося стандартом криптохеширования в США) подтолкнули исследователей из Университета Граца (Австрия) запустить распределенный поиск на сервере tugraz.at, оптимистичные прогнозы ожидают первую SHA-1 коллизию в ближайшие 5 лет.

И наконец, вопрос, который затрагивается всегда при обсуждении этой методики — уязвим ли к этой атаке ГОСТ Р 34.11-94? Отечественный криптостандарт использует иную схему «замешивания» блоков исходного текста при хешировании, поэтому на сегодняшний день описанные методики для ГОСТа применить не удалось.

Наилучшая из известных атак (вызвавшая правда несколько ажиотажных заголовков в СМИ в 2008) предложена исследователями из того же Граца и улучшает процесс подбора коллизий в 2^23 раз.