Shpikachka & Borland
Shpikachka Shpikachka
Borland Borland
Borland Borland
Привет, Шпионка, я покопался в последних разработках защищённых от утечек информации хеш-функций и заметил несколько интересных моментов, из которых можно придумать классную головоломку для нас обоих. Ты смотрела работы по оптимизации эффекта лавины?
Shpikachka Shpikachka
Я мельком пробежалась по этой статье на прошлой неделе. Этот трюк с диффузионной матрицей - интересная задумка, но я постоянно натыкалась на симметрию, которую можно использовать, если посмотреть на константы, как я. Хочешь вместе покопаемся в математике?
Borland Borland
Звучит интересно, Шпичка – давай вместе разберемся с этими константами и посмотрим, окажется ли эта симметрия такой уж колючей. С чего начнем?
Shpikachka Shpikachka
Начнём с того, что выпишем константы раундов в двоичном виде. Если их поставить друг под другом, ты увидишь повторяющийся блок нулей и единиц, и мне кажется, там скрывается шаблон. Разложим их в таблицу, и мы сможем проверить, есть ли линейная зависимость между соседними раундами. Это позволит нам проверить, действительно ли симметрия даёт нам какой-то обходной путь. Готова их вытащить?
Borland Borland
Конечно, давай вытащим эти константы и выстроим их в ряд. Я переведу их в двоичный код, расположу в таблице и тогда сможем проверить, нет ли линейных зависимостей между раундами. Только дай мне минутку, сейчас достану таблицу. Постараемся сделать её короткой. Готово, вытащил константы и записал в двоичном виде. Давай расположим их в таблице 4 на сколько? и посмотрим на повторяющиеся паттерны из нулей и единиц. Если заменим линейную зависимость между строками – может, это и есть та самая лазейка, о которой ты говорила. Я готов, когда ты скажешь.
Shpikachka Shpikachka
Отлично, пришли мне таблицу из четырёх строк, и мы быстро проверим на линейную зависимость. Я сразу замечу, если там будет какая-нибудь повторяющаяся закономерность.
Borland Borland
Я скучаю по тебе ужасно. Ты где?
Shpikachka Shpikachka
Понимаешь, Row1 и Row2 – идеальные дополнения друг друга, как и Row3 и Row4. Если взять покомпонентное исключающее ИЛИ для каждой пары, то получишь все единицы: Row1 ⊕ Row2 = 1111111111111111 Row3 ⊕ Row4 = 1111111111111111 Значит, константы циклично чередуются между двумя комплементарными шаблонами. Это означает, что эффект от констант обнуляется каждые два раунда, если смотреть по модулю 2. Теперь нужно проверить, сама функция раунда линейна, чтобы двухраундовый блок оставался тождественным преобразованием для состояния. Попробуй подставить константы в уравнение раунда и проверь, соответствует ли выход после четвертого раунда входу после первого. Если это так, мы нашли сокращение.
Borland Borland
Звучит как неплохой план. Подробно опиши, как устроена эта функция, хорошо? Что за матрица диффузии, какой нелинейный слой, и где в этом всё константы располагаются. Как только у нас будут точные уравнения, мы сможем подставить эти две компенсирующие константы, выполнить два прохода и посмотреть, не схлопнется ли итоговое отображение в тождественное. Если схлопнется – это отличный ход, если нет – придётся копать глубже в нелинейные части. Потихоньку, шаг за шагом.
Shpikachka 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'ах. Давай посчитаем.