28 January 2009

Взлом хеш-функций (2004-2006 гг.): как это было и что теперь делать?

Information Security
Двое моих знакомых, задавших в течение недели вопросы примерно одинаковые по сути (примерно в духе: «А я слышал, что MD5/SHA-1 уже взломан, почему мы до сих пор их используем ?»), подтолкнули меня к написанию этой заметки, хотя основные события, описываемые ниже, произошли уже более 3 лет назад.

Общие сведения (специалистам — пропускать без сомнений)


Как известно, криптографические хеш-суммы отличаются от обычных хеш-сумм тем, что помимо основных свойств, требуемых от любой хеш-функции :
  • способности преобразования входного значения (обычно текста) произвольной длины в выходное значение фиксированной длины,
  • статистической равномерности выпадающих выходных значений,
  • хорошей «разбросанности» (расхождении примерно в половине бит) выходных значений даже для незначительно (возможно только в 1 бите) отличающихся входных текстов;
к криптографическим хеш-алгоритмам предъявляются дополнительные требования :
  • разрядность выходных значений должна находиться далеко за пределами возможностей полного перебора на современной технике как по скорости обработки, так и по объему хранения (на практике это — разрядность в 128, 160, 256 и более бит);
  • не должно существовать способа (существенно более эффективного, чем полный перебор входных значений) вычислить какую-либо пару входных текстов, дающих на выходе одинаковое хеш-значение (неважно какое) — успешная атака на это требование называется «коллизией» хеш-функции;
  • не должно существовать способа (существенно более эффективного, чем полный перебор входных значений) по значению хеш-функции подобрать какой-либо входной текст, дающий на выходе алгоритма это хеш-значение — успешная атака на это требование называется «обращением» хеш-функции.
Три перечисленных выше требования к криптостойким хеш-функциям превращают их по факту в идентификаторы фиксированной длины для текстов, файлов и вообще произвольных блоков информации. При этом эти идентификаторы:
  1. уникальны на всем просторе современного информационного общества;
  2. необратимы, то есть не раскрывают абсолютно ничего о содержании исходного документа.
Это позволяет использовать хеш-функции в задачах:
  • проверки целостности файлов, архивов, сборок и т.п. (достаточно доверенно передать получателю хеш-сумму файла и тогда любые несанкционированные изменения в файле немедленно изменят его контрольную хеш-сумму);
  • хранения паролей в необратимом виде (в хранилище помещаются не сами пароли, а хеш-суммы от строки, например, вида «константа (соль)»+«пароль», что позволяет при раскрытии хеша сохранить собственно словарную парольную фразу в секрете);
  • электронно-цифровой подписи документов (собственно ЭЦП устанавливается всегда не на сам файл, что во-первых, было бы очень медленно, и во-вторых, несло бы некоторые проблемы с безопасностью самого ключа подписи, а на его хеш-сумму, обеспечивая точно такой же уровень защиты от модификаций).
На сегодняшний день подавляющую долю применений хеш-функций «берут на себя» алгоритмы MD5, SHA-1, SHA-256, а в нашей стране еще и ГОСТ Р 34.11-94, являющийся де факто практически монополистом в сертифицированных ФАПСИ/ФСБ криптопродуктах. Конечно, существует и множество других менее известных, или распространенных только в узких сообществах алгоритмов (например, RIPEMD, TIGER, PANAMA и др.)

Что же произошло?


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

Гром среди ясного неба прозвучал 16 августа 2004, когда группа китайских исследователей (под руководством X.Wang) опубликовала на открытом сервере научных публикаций eprint.iacr.org безо всяких объяснений пары реальных коллизий для MD4, MD5, RIPEMD и HAVAL с единственным замечанием о том, что подбор этих входных текстов занял у них 1 час 5 минут. Это было взрывом. Сильнейшие криптографы вновь обратили свое внимание на семейство «MD5/SHA-1» и конечно на примеры, приведенные в прорывной статье. Определенные закономерности были выяснены, и вскоре уже был построен методический аппарат построения коллизий к подобным шифрам, который на протяжении 2004-2006 всё совершенствовался и достиг на сегодняшний день быстродействия менее секунды на обычном персональном компьютере для генерации пары текстов, создающих коллизию. На сегодняшний день бесспорно взломаны (но только по атаке класса «коллизия» !) MD4, MD5, RIPEMD, HAVAL, SHA-0.

С SHA-1 ситуация несколько иная. Несколько более продуманная чем у MD5 и RIPEMD-160 структура математических преобразований ограничивает лучшую из известных на сегодняшний день в открытых кругах реализаций атаки (предложенной, кстати, теми же китайцами) вычислительной трудоемкостью 2^63 операций. Это объективно много. Даже с учетом экспоненциального роста производительности выч.техники вряд ли подбор хотя бы одной коллизии будет осуществим одним компьютером в ближайшие двадцать лет. Однако, не забываем, что существуют распределенные проекты. Здоровые амбиции (получить первую искусственную коллизию для SHA-1, кстати официально являющегося стандартом криптохеширования в США) подтолкнули исследователей из Университета Граца (Австрия) запустить распределенный поиск на сервере boinc.iaik.tugraz.at, оптимистичные прогнозы ожидают первую SHA-1 коллизию в ближайшие 5 лет.

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

Последствия


Что мы имеем «в сухом остатке»?

Криптоалгоритмы MD4, MD5, SHA-1, RIPEMD, HAVAL однозначно скомпрометированы в отношении атак генерации коллизий. Однако (!) к счастью, ни одной физически реализуемой атаки на обращение хеш-функций (даже для MD4) на сегодняшний день не опубликовано.

Чем это грозит ?

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

Может ли злоумышленник… ?
  • … создать другой файл/архив/т.п., который будет иметь ту же хеш-сумму, что и чужой оригинальный, чтобы потом заменить им оригинальный, например, на WEB-сервере или в репозитории исходных/двоичных кодов ? Нет. Однако, если он является автором оригинального файла, он может создать две версии файла с одинаковой хеш-суммой: безобидную и вредоносную, отдать на публичное изучение безобидную, а затем на этапе распространения незаметно менять версию на вредоносную — проверка на основе только хеш-функции этого не заметит.
  • … восстановить пароль клиента, выяснив тем или иным способом его хеш ? Однозначно, нет.
  • … модифицировать ранее созданный файл (свой или чужой), защищенный ЭЦП ? Нет. Однако, как и в первом случае он может изначально создать две версии исходного файла, подписать одну из них своей ЭЦП или отдать на подпись чужой ЭЦП (например, при депонировании документов третьей стороной или заверении времени создания документа), а затем после получения подписанного документа перенести блок, отвечающий за подпись, на вторую версию документа и ЭЦП окажется корректной, что конечно неприемлемо. На сегодняшний день, криптоаналитики уже продемонстрировали примеры коллизий платежных поручений, отличающихся лишь суммой платежа, а также коллизий X.509 сертификатов, имеющих разные открытые ключи, однако, одинаковые хеш-суммы, а следовательно и одинаковые заверяющие их подписи центров сертификации. Все это дает к сожалению достаточно большой простор для фантазии.

Чем пользоваться сегодня ?


  1. Из широко известных достаточно давно хеш-алгоритмов на сегодняшний день нет никаких претензий к ГОСТ Р 34.11-94 (разработчик ФАПСИ, 1995) и TIGER (разработчики — криптографы с мировым именем Э.Бихам и Р.Андерсон, 1995).
  2. Новое поколение алгоритмов SHA от американского института стандартизации NIST (2001-2002 годы) имеет новую нумерацию SHA-224, SHA-256, SHA-384, SHA-512 (от разрядности выходных значений) и иногда объединяется под общим кодовым названием SHA-2. Алгоритмы имеют иную структуру криптопреобразований и пока информации об атаках на них ни первого ни второго рода не поступало.
  3. Не удовлетворившись этим NIST запустил в 2007 году открытый конкурс на стандарт хеширования третьего поколения SHA-3 (в точности повторяющий по своим принципам то, как выбирали в 2000 году новый стандарт блочного шифрования AES). На текущий момент идет только первая фаза конкурса, до участия в ней допущен 51 алгоритм со всего света.
  4. Ну и напоследок, в принципе никто не запрещает Вам использовать для проверки две и более уязвимых функций одновременно. Создание пары документов, которые одновременно бы давали одинаковые между собой MD5-суммы и одинаковые между собой SHA-1 суммы, на сегодняшний день невозможно.
Tags:md5shaхешированиекриптоанализ
Hubs: Information Security
+141
24.8k 100
Comments 128