dxdt.ru: занимательный интернет-журнал

В марте довольно много писали про новую атаку на SHA-256, “с обнаружением коллизий”. Вообще, тут нужно отделять академические атаки от практики, условно говоря, всяких биткойнов: в исходной работе (“New Records in Collision Attacks on SHA-2”, Li, Liu, Wang) речь идёт про академические атаки на урезанную “функцию сжатия” (см. ниже) из состава SHA-2 (SHA-256 – это разновидность SHA-2), да ещё и со специально подобранным предыдущим состоянием. Это общепринятый подход к исследованию стойкости хеш-функций, результат существенно лучше предыдущих достижений, но нужно учитывать, что он не обязательно приводит к практической атаке на полную хеш-функцию. В статье сказано именно про “практическую атаку”, это верно, однако это разная “практика”.

Возьмём в качестве примера SHA-256 и одну из практических (в академическом смысле) атак, представленных в упомянутой выше работе. Ядром схемы хеш-функции SHA-256 являются преобразования, соответствующие симметричному шифру. Повторно выполняемые раунды преобразований шифра, внутри хеш-функции, и образуют так называемую “функцию сжатия” – это важнейший элемент. Входной текст для преобразования в SHA-256 разбивается на блоки. Блок – это последовательность байтов, соответствующая разрядности функции, здесь – 256 бит или 32 байта. Блоки обрабатываются функцией сжатия, внутри которой выполняется заданное количество раундов – то есть, повторное применение одних и тех же преобразований, в цикле, к обрабатываемому блоку. Далее речь будет идти только про один блок, а не про полный входной текст.

После каждого раунда, блок, в результате применения преобразований, изменяется и потом снова подвергается тем же преобразованиям, которые опять изменяют блок. Эта комбинаторная часть позволяет добиться нужного разрежения для отображения входных блоков в выходные значения. Штатная схема SHA-256 использует 64 раунда в функции сжатия. Атака, о которой идёт речь, работает для 39 раундов (обратите внимание: с подобранным начальным состоянием – это очень важный момент).

Что это означает? Это означает, что исследователи нашли и предъявили кортеж из трёх конкретных значений (чисел или массивов байтов – как хотите), которые, будучи подставленными в урезанную до 39 раундов сжатия версию хеш-функции SHA-256, дают одинаковый результат. Одно из этих значений – это начальное состояние, устанавливаемое перед вызовом функции сжатия внутри урезанной SHA-256. То есть, при штатной реализации SHA-256 – этим состоянием либо был бы предыдущий обработанный блок, либо начальные константы из спецификации SHA-256. Два других упомянутых значения – это различающиеся в некоторых байтах входные блоки. Обработка этих блоков при указанных, весьма строгих, условиях – даёт коллизию. То есть, академическая “практическая” демонстрация, с конкретными числами. Это вполне себе строгий и разумный способ анализа стойкости преобразований. В данной науке это называется SFS-коллизия (от Semi-Free-Start). Но, опять же, очень далеко от демонстрации реальной, практической, “уничтожающей” коллизии SHA-256, то есть, демонстрации двух различных входных текстов, дающих одинаковый результат хеш-функции. (Что, конечно, не отменяет заметного продвижения.)

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

Естественно, обнаружение точек совпадения для уменьшенного количества раундов нередко даёт инструменты для взлома всей хеш-функции целиком. Именно поэтому академические атаки на примитивы с урезанным количеством раундов – важнейший инструмент. Однако, является ли тот факт, что коллизия найдена для более чем половины количества раундов, автоматической гарантией успешного применения того же метода к, предположим, половине оставшейся половины? Нет, совсем не является. Методы тут развиваются, так сказать, полностью “нелинейно”, так что непреодолимое вычислительное препятствие может возникнуть хоть бы и на каждом следующем раунде – потребуется полностью переделать метод атаки. Собственно, это очередное улучшение атак на SHA-2 как раз построено на новых методах, если сравнивать с теми методами, которые использовали для атак на MD5 и пр.

Конкретный пример, взятый из исходной работы: для 39 раундов SHA-256, при заданном начальном состоянии, получаются совпадающие значения для разных входных блоков (выдача программы, прилагаемой к работе):

431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d
431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d

Можно было бы предположить, что раз точка совпадения найдена, то и дальнейшие раунды дадут одинаковые результаты. Но это далеко не так – состояние хеш-функции шире, чем конкретный результат преобразования блока. Так, если в той же программе указать 42 раунда (всего на три раунда больше), то значения уже заметно разойдутся:

d33c0cff 17c9de13 21f528f0 3362e217 563f1779 521a1b9c df062e86 19fb5973 
105d6c34 43ceb0ad 120ba1a0 3362e217 d6dd86e0 7da567b5 cf1ca736 19fb5973

Это, ещё раз, никак не уменьшает ценности результата для 39 раундов, но показывает, что для полной SHA-256 всё, – пока что, – хорошо.

Криптографические хеш-функции отображают сообщения произвольной длины в блоки фиксированной длины, так что, математически, коллизии там есть по определению. Другое дело, что если хеш-функция хорошо отображает множество входных текстов в, скажем, 2^256 выходных значений, то о коллизиях “на полном переборе” можно не особенно задумываться: мало кто может создать и записать даже 2^128 текстов. Атаки с обнаружением точек совпадения в функции сжатия как раз, потенциально, выявляют дефекты отображения, которые могут позволить найти коллизии без необходимости полного перебора. А возможно, что и позволят найти способы решения гораздо более сложной задачи вычисления прообраза, – то есть, подбора входного текста по значению хеш-функции.

Адрес записки: https://dxdt.ru/2024/04/02/12690/