Shpikachka & Borland
Borland
Привет, Шпионка, я покопался в последних разработках защищённых от утечек информации хеш-функций и заметил несколько интересных моментов, из которых можно придумать классную головоломку для нас обоих. Ты смотрела работы по оптимизации эффекта лавины?
Shpikachka
Я мельком пробежалась по этой статье на прошлой неделе. Этот трюк с диффузионной матрицей - интересная задумка, но я постоянно натыкалась на симметрию, которую можно использовать, если посмотреть на константы, как я. Хочешь вместе покопаемся в математике?
Borland
Звучит интересно, Шпичка – давай вместе разберемся с этими константами и посмотрим, окажется ли эта симметрия такой уж колючей. С чего начнем?
Shpikachka
Начнём с того, что выпишем константы раундов в двоичном виде. Если их поставить друг под другом, ты увидишь повторяющийся блок нулей и единиц, и мне кажется, там скрывается шаблон. Разложим их в таблицу, и мы сможем проверить, есть ли линейная зависимость между соседними раундами. Это позволит нам проверить, действительно ли симметрия даёт нам какой-то обходной путь. Готова их вытащить?
Borland
Конечно, давай вытащим эти константы и выстроим их в ряд. Я переведу их в двоичный код, расположу в таблице и тогда сможем проверить, нет ли линейных зависимостей между раундами. Только дай мне минутку, сейчас достану таблицу. Постараемся сделать её короткой. Готово, вытащил константы и записал в двоичном виде. Давай расположим их в таблице 4 на сколько? и посмотрим на повторяющиеся паттерны из нулей и единиц. Если заменим линейную зависимость между строками – может, это и есть та самая лазейка, о которой ты говорила. Я готов, когда ты скажешь.
Shpikachka
Отлично, пришли мне таблицу из четырёх строк, и мы быстро проверим на линейную зависимость. Я сразу замечу, если там будет какая-нибудь повторяющаяся закономерность.
Borland
Я скучаю по тебе ужасно. Ты где?
Shpikachka
Понимаешь, Row1 и Row2 – идеальные дополнения друг друга, как и Row3 и Row4.
Если взять покомпонентное исключающее ИЛИ для каждой пары, то получишь все единицы:
Row1 ⊕ Row2 = 1111111111111111
Row3 ⊕ Row4 = 1111111111111111
Значит, константы циклично чередуются между двумя комплементарными шаблонами. Это означает, что эффект от констант обнуляется каждые два раунда, если смотреть по модулю 2.
Теперь нужно проверить, сама функция раунда линейна, чтобы двухраундовый блок оставался тождественным преобразованием для состояния. Попробуй подставить константы в уравнение раунда и проверь, соответствует ли выход после четвертого раунда входу после первого. Если это так, мы нашли сокращение.
Borland
Звучит как неплохой план. Подробно опиши, как устроена эта функция, хорошо? Что за матрица диффузии, какой нелинейный слой, и где в этом всё константы располагаются. Как только у нас будут точные уравнения, мы сможем подставить эти две компенсирующие константы, выполнить два прохода и посмотреть, не схлопнется ли итоговое отображение в тождественное. Если схлопнется – это отличный ход, если нет – придётся копать глубже в нелинейные части. Потихоньку, шаг за шагом.
Shpikachka
Понятно. Итак, на каждом раунде: берём вектор состояния s, добавляем раундовую константу c, применяем нелинейный слой S-box N, и в конце умножаем на матрицу диффузии D. Математически это выглядит так: s′ = D · N (s ⊕ c). Константы, которые ты вытащил, это именно эти самые c для каждого раунда. Для двух раундов у нас получается: s₂ = D · N (D · N (s₀ ⊕ c₁) ⊕ c₂). Подставляешь те пары, которые ты нашёл для c₁ и c₂, вычисляешь s₂ и смотришь, получится ли оно равным s₀. Это и есть проверка. Если сходится – значит, двухраундовое преобразование – тождественное. Если нет – придётся покопаться глубже в S-box'ах. Давай посчитаем.
Borland
Я перепроверил алгебру с теми константами, что ты дала. Раз XOR-операция обнуляет эти константы, единственный способ, чтобы двухкруговая схема вернула исходное состояние – это если нелинейный слой N ведёт себя линейно для этой конкретной пары входных данных. Но поскольку N по своей природе является настоящим S-боксом, его выход – это не линейная функция от входа, а значит, композиция D·N·D·N почти наверняка исказит состояние. На практике ты бы выбрала какое-нибудь конкретное начальное состояние s₀, пропустила бы его через первый раунд с c₁, затем через второй раунд с c₂, и посмотрела бы, возвращается ли исходное состояние. С реальными D и N это практически никогда не произойдёт. Так что та уловка, которую ты ищешь, не выдерживает проверки нелинейным слоем. Если хочешь убедиться сама – попробуй несколько случайных s₀, увидишь, как результаты расходятся.