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

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

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

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

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

Пример

Пусть итерация шифрования задаётся как

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

Где $c_{0}$ — это открытый текст, $k_{i}\in K$ — секретный раундовый ключ, $c_{r}$ — зашифрованный текст для $r$ — раундовой итерации шифрования.

Рассмотрим 2-раундовый шифр. Пусть $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},$

А на выходе из 2-го раунда:

$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)$ мы получим вычисляя назад и используя повторную формулу шифра до $s+1$ раунда.

Таким образом получается, что

$g(x)=h(c),$

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

Временная сложность

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

Ключ восстановления

Мы можем также использовать интерполяционную атаку, чтобы восстановить секретный ключ $K$. Если убрать последний раунд $r$ — раундового повторного шифра длиной блока $m$, выход шифра становится ${\tilde {y}}=c_{r-1}$. Получается шифр со сниженной сложностью шифрования. Идея состоит в том, чтобы сделать предположение на последнем $k_{r}$ раундового ключа мы можем расшифровать один раунд, чтобы получить выход ${\tilde {y}}$ приведённого шифра. Тогда, чтобы проверить предположение, нужно использовать интерполяционную атаку на сниженный шифр либо обычным способом, либо с помощью метода Meet-In-The-Middle.

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

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

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

Методом Meet-In-The-Middle мы выражаем выход $z$ из раунда $s<r$ в виде полинома открытого текста $x$ и в виде полинома выхода пониженного шифра ${\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$, а метод Meet-In-The-Middle имеет сложность $2^{m-1}(p+q-1)$ и требует $p+q-1$ известных различных пар $c/p$.

Использование

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

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

Литература

• Thomas Jakobsen, Lars Knudsen. The Interpolation Attack on Block Ciphers. — Springer-Verlag, January 1997. — С. 28–40. — ISBN 3-540-63247-6.
• E.Biham and A.Shamir. Differential Cryptanalysis of DES-like Cryptosystems. — 1991. — ISBN 3-89649-079-6.