Интерполяционная атака

В криптографии интерполяционная атака — это тип криптоаналитической атаки на блочные шифры .

После того, как две атаки, дифференциальный криптоанализ и линейный криптоанализ , были представлены на блочных шифрах, были введены некоторые новые блочные шифры , которые доказали свою безопасность против дифференциальных и линейных атак. Среди них было несколько итерированных блочных шифров, таких как KN-Cipher и шифр SHARK . Однако в конце 1990-х годов Томас Якобсен и Ларс Кнудсен показали, что эти шифры легко взломать, представив новую атаку, названную интерполяционной атакой.

В атаке для представления S-блока используется алгебраическая функция . Это может быть простая квадратичная функция , полиномиальная или рациональная функция над полем Галуа . Его коэффициенты могут быть определены стандартными методами интерполяции Лагранжа с использованием известных открытых текстов в качестве точек данных. Альтернативно, выбранные открытые тексты могут использоваться для упрощения уравнений и оптимизации атаки.

В своей простейшей версии интерполяционная атака выражает зашифрованный текст как полином открытого текста. Если полином имеет относительно небольшое количество неизвестных коэффициентов, то с помощью набора пар открытый текст/зашифрованный текст (p/c) полином можно восстановить. После восстановления полинома злоумышленник получает представление о шифровании, не зная точного секретного ключа.

Интерполяционную атаку также можно использовать для восстановления секретного ключа.

Проще всего описать метод на примере.

Пример [ править ]

Пусть итерационный шифр задается формулой

c_{i}=(c_{i-1}\oplus k_{i})^{3},

где $c_{0}$ это открытый текст, $c_{i}$ вывод $i^{th}$ круглый, $k_{i}$ секрет $i^{th}$ круглый ключ (полученный из секретного ключа $K$ по некоторому ключевому расписанию ), и для $r$ -раундовый итеративный шифр, $c_{r}$ это зашифрованный текст.

Рассмотрим двухраундовый шифр. Позволять $x$ обозначают сообщение и $c$ обозначают зашифрованный текст.

Тогда результат раунда 1 станет

c_{1}=(x+k_{1})^{3}=(x^{2}+k_{1}^{2})(x+k_{1})=x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3},

и результат второго раунда станет

c_{2}=c=(c_{1}+k_{2})^{3}=(x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3}+k_{2})^{3}

=x^{9}+x^{8}k_{1}+x^{6}k_{2}+x^{4}k_{1}^{2}k_{2}+x^{3}k_{2}^{2}+x^{2}(k_{1}k_{2}^{2}+k_{1}^{4}k_{2})+x(k_{1}^{2}k_{2}^{2}+k_{1}^{8})+k_{1}^{3}k_{2}^{2}+k_{1}^{9}+k_{2}^{3},

Выражение зашифрованного текста как полинома от открытого текста дает

p(x)=a_{1}x^{9}+a_{2}x^{8}+a_{3}x^{6}+a_{4}x^{4}+a_{5}x^{3}+a_{6}x^{2}+a_{7}x+a_{8},

где $a_{i}$ являются константами, зависящими от ключа.

Использование столько пар открытый текст/зашифрованный текст, сколько неизвестных коэффициентов в полиноме. $p(x)$ , то мы можем построить полином. Это можно, например, сделать с помощью интерполяции Лагранжа (см. Полином Лагранжа ). Когда неизвестные коэффициенты определены, мы имеем представление $p(x)$ шифрования, без знания секретного ключа $K$ .

Существование [ править ]

Учитывая $m$ -битный блочный шифр, то есть $2^{m}$ возможные открытые тексты и, следовательно, $2^{m}$ отчетливый $p/c$ пары. Пусть будет $n$ неизвестные коэффициенты в $p(x)$ . Поскольку нам нужно как можно больше $p/c$ пар как количество неизвестных коэффициентов в полиноме, то интерполяционная атака существует только в том случае, если $n\leq 2^{m}$ .

Временная сложность [ править ]

Предположим, что время построения полинома $p(x)$ с использованием $p/c$ пары малы по сравнению со временем, необходимым для шифрования требуемых открытых текстов. Пусть будет $n$ неизвестные коэффициенты в $p(x)$ . Тогда временная сложность этой атаки равна $n$ , требующий $n$ известный отдельный $p/c$ пары.

Интерполяционная атака Meet-In-The-Middle [ править ]

Часто этот метод более эффективен. Вот как это делается.

Учитывая $r$ круглый итерационный шифр с длиной блока $m$ , позволять $z$ быть результатом шифрования после $s$ раунды с $s<r$ . Мы выразим стоимость $z$ как многочлен открытого текста $x$ , и как многочлен зашифрованного текста $c$ . Позволять $g(x)\in GF(2^{m})[x]$ быть выражением $z$ с помощью $x$ , и разреши $h(c)\in GF(2^{m})[c]$ быть выражением $z$ с помощью $c$ . Полином $g(x)$ получается путем прямого вычисления с использованием повторяющейся формулы шифра до округления $s$ , и полином $h(c)$ получается путем вычисления в обратном направлении по повторяемой формуле шифра, начиная с раунда $r$ до раунда $s+1$ .

Так что это должно поддерживаться

g(x)=h(c),

и если оба $g$ и $h$ являются полиномами с небольшим количеством коэффициентов, то мы можем решить уравнение для неизвестных коэффициентов.

Временная сложность [ править ]

Предположим, что $g(x)$ может быть выражено $p$ коэффициенты и $h(c)$ может быть выражено $q$ коэффициенты. Тогда нам понадобится $p+q$ известный отдельный $p/c$ пары, чтобы решить уравнение, представив его в виде матричного уравнения. Однако это матричное уравнение разрешимо с точностью до умножения и сложения. Поэтому, чтобы убедиться, что мы получили единственное и ненулевое решение, мы устанавливаем коэффициент, соответствующий высшей степени, равным единице, а постоянный член - нулю. Поэтому, $p+q-2$ известный отдельный $p/c$ нужны пары. Таким образом, временная сложность этой атаки равна $p+q-2$ , требующий $p+q-2$ известный отдельный $p/c$ пары.

При использовании подхода «Встреча посередине» общее количество коэффициентов обычно меньше, чем при использовании обычного метода. Это делает метод более эффективным, поскольку меньше $p/c$ нужны пары.

Восстановление ключей [ править ]

Мы также можем использовать атаку интерполяции для восстановления секретного ключа. $K$ .

Если мы удалим последний раунд $r$ -круглый итерационный шифр с длиной блока $m$ , результат шифрования становится ${\tilde {y}}=c_{r-1}$ . Назовем этот шифр сокращенным шифром. Идея состоит в том, чтобы угадать ключ последнего раунда. $k_{r}$ , так что мы можем расшифровать один раунд и получить выходные данные ${\tilde {y}}$ сокращенного шифра. Затем для проверки предположения мы используем интерполяционную атаку на сокращенный шифр либо обычным методом, либо методом «Встреча посередине». Вот как это делается.

Обычным методом выражаем вывод ${\tilde {y}}$ сокращенного шифра как полинома открытого текста $x$ . Вызов полинома $p(x)\in GF(2^{m})[x]$ . Тогда, если мы сможем выразить $p(x)$ с $n$ коэффициенты, затем используя $n$ известный отдельный $p/c$ пары, мы можем построить полином. Чтобы проверить угадывание ключа последнего раунда, проверьте еще один $p/c$ пара, если это так

p(x)={\tilde {y}}.

Если да, то с большой вероятностью угадывание ключа последнего раунда было правильным. Если нет, то еще раз угадайте ключ.

Методом «Встреча посередине» мы выражаем вывод $z$ из раунда $s<r$ как многочлен открытого текста $x$ и как полином от результата сокращенного шифра ${\tilde {y}}$ . Вызов полиномов $g(x)$ и $h({\tilde {y}})$ , и пусть они выражаются через $p$ и $q$ коэффициенты соответственно. Затем с $q+p-2$ известный отдельный $p/c$ пары, мы можем найти коэффициенты. Чтобы проверить угадывание ключа последнего раунда, проверьте еще один $p/c$ пара, если это так

g(x)=h({\tilde {y}}).

Если да, то с большой вероятностью угадывание ключа последнего раунда было правильным. Если нет, то еще раз угадайте ключ.

Как только мы нашли правильный ключ последнего раунда, мы можем продолжить аналогичным образом с оставшимися ключами раунда.

Временная сложность [ править ]

С секретным круглым ключом длиной $m$ , то есть $2^{m}$ разные ключи. Каждый с вероятностью $1/2^{m}$ быть правильным, если выбрано случайно. Поэтому нам в среднем придется сделать $1/2\cdot 2^{m}$ догадывается, прежде чем найти правильный ключ.

Следовательно, нормальный метод имеет среднюю временную сложность. $2^{m-1}(n+1)$ , требующий $n+1$ известный отдельный $c/p$ пары, а метод «Встреча посередине» имеет среднюю временную сложность. $2^{m-1}(p+q-1)$ , требующий $p+q-1$ известный отдельный $c/p$ пары.

Приложение из реального мира [ править ]

Атака «Встреча посередине» может использоваться в варианте атаки на S-блоки, в котором используется обратная функция, поскольку при $m$ -бит S-box тогда $S:f(x)=x^{-1}=x^{2^{m}-2}$ в $GF(2^{m})$ .

Блочный шифр SHARK использует SP-сеть с S-box. $S:f(x)=x^{-1}$ . Шифр устойчив к дифференциальному и линейному криптоанализу после небольшое количество раундов. Однако в 1996 году он был взломан Томасом Якобсеном и Ларсом Кнудсеном с помощью интерполяционной атаки. Обозначим через АКУЛУ $(n,m,r)$ версия SHARK с размером блока $nm$ биты с использованием $n$ параллельный $m$ -битные S-блоки в $r$ раунды. Якобсен и Кнудсен обнаружили, что существует интерполяционная атака на SHARK. $(8,8,4)$ (64-битный блочный шифр), используя около $2^{21}$ выбранные открытые тексты и интерполяционная атака на SHARK $(8,16,7)$ (128-битный блочный шифр), используя около $2^{61}$ выбранные открытые тексты.

Также Томас Якобсен представил вероятностную версию интерполяционной атаки с использованием Мадху Судана алгоритма для улучшенного декодирования кодов Рида-Соломона . Эта атака может сработать, даже если алгебраическая связь между открытым текстом и зашифрованным текстом сохраняется только для части значений.

Ссылки [ править ]

Томас Якобсен , Ларс Кнудсен (январь 1997 г.). Интерполяционная атака на блочные шифры ( PDF / PostScript ) . 4-й международный семинар по быстрому программному шифрованию (FSE '97), LNCS 1267. Хайфа : Springer-Verlag . стр. 28–40 . Проверено 3 июля 2007 г.
Томас Якобсен (25 августа 1998 г.). Криптоанализ блочных шифров с вероятностными нелинейными отношениями низкой степени (PDF/PostScript) . Достижения в криптологии — КРИПТО '98. Санта-Барбара, Калифорния : Springer-Verlag. стр. 212–222 . Проверено 6 июля 2007 г. ( Видео презентации в Google Video — используется Flash )
Шихо Мориай; Такеши Симояма; Тошинобу Канеко (март 1999 г.). Интерполяционные атаки блочного шифра: SNAKE (PDF) . ФСЕ '99. Рим: Springer-Verlag. стр. 275–289. дои : 10.1007/3-540-48519-8_20 . Проверено 6 ноября 2022 г.
Амр М. Юсеф; Гуан Гун (апрель 2000 г.). Об интерполяционных атаках на блочные шифры (PDF) . FSE 2000. Нью-Йорк : Springer-Verlag. стр. 109–120 . Проверено 6 июля 2007 г.
Каору Куросава; Тецу Ивата; Вьет Дуонг Куанг (август 2000 г.). Интерполяционная атака с поиском корня (PDF/PostScript) . Материалы 7-го ежегодного международного семинара по избранным областям криптографии (SAC 2000). Ватерлоо, Онтарио : Springer-Verlag. стр. 303–314 . Проверено 6 июля 2007 г.