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

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

После того, как две атаки, дифференциальный криптоанализ и линейный криптоанализ , были представлены на блочных шифрах, были введены некоторые новые блочные шифры , которые доказали свою безопасность против дифференциальных и линейных атак. Среди них было несколько итерированных блочных шифров, таких как 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 г.