Введение
Тип криптоаналитической атаки
В криптографии интерполяционная атака — это тип криптоаналитической атаки на блочные шифры. После того как дифференциальный криптоанализ и линейный криптоанализ были представлены для блочных шифров, были разработаны новые блочные шифры, которые оказались устойчивыми к дифференциальным и линейным атакам. Среди них были итеративные блочные шифры, такие как шифр KN и шифр SHARK. Однако Томас Якобсен и Ларс Кнудсен в конце 1990-х годов показали, что эти шифры легко взламываются с помощью новой атаки, названной интерполяционной атакой. В этой атаке алгебраическая функция используется для представления S-блока. Это может быть простая квадратичная функция, полином или рациональная функция над полем Галуа. Её коэффициенты могут быть определены стандартными методами интерполяции Лагранжа, используя известные открытые тексты в качестве точек данных. Альтернативно, можно использовать выбранные открытые тексты для упрощения уравнений и оптимизации атаки. В своей простейшей форме интерполяционная атака выражает шифротекст как полином от открытого текста. Если полином имеет относительно небольшое количество неизвестных коэффициентов, то, имея набор пар открытый текст/шифротекст (p/c), можно восстановить полином. После восстановления полинома злоумышленник получает представление о шифровании, не имея точного знания секретного ключа. Интерполяционная атака также может быть использована для восстановления секретного ключа. Описать этот метод проще всего на примере.
In cryptography, an interpolation attack is a type of cryptanalytic attack against block ciphers. After the two attacks, differential cryptanalysis and linear cryptanalysis, were presented on block ciphers, some new block ciphers were introduced, which were proven secure against differential and linear attacks. Among these there were some iterated block ciphers such as the KN Cipher and the SHARK cipher. However, Thomas Jakobsen and Lars Knudsen showed in the late 1990s that these ciphers were easy to break by introducing a new attack called the interpolation attack. In the attack, an algebraic function is used to represent an S box. This may be a simple quadratic, or a polynomial or rational function over a Galois field. Its coefficients can be determined by standard Lagrange interpolation techniques, using known plaintexts as data points. Alternatively, chosen plaintexts can be used to simplify the equations and optimize the attack. In its simplest version an interpolation attack expresses the ciphertext as a polynomial of the plaintext. If the polynomial has a relative low number of unknown coefficients, then with a collection of plaintext/ciphertext (p/c) pairs, the polynomial can be reconstructed. With the polynomial reconstructed the attacker then has a representation of the encryption, without exact knowledge of the secret key. The interpolation attack can also be used to recover the secret key. It is easiest to describe the method with an example.
Существование
Рассматривая блочный шифр с битами, существует возможных открытых текстов и, следовательно, различных пар "открытый текст - шифротекст". Пусть в полиноме имеется неизвестных коэффициентов. Поскольку для интерполяционной атаки требуется количество пар "открытый текст - шифротекст", равное количеству неизвестных коэффициентов в полиноме, то такая атака возможна только если .
Временная сложность
Предположим, что время построения многочлена по парам (x, y) незначительно по сравнению со временем шифрования необходимых открытых текстов. Пусть в многочлене имеется неизвестных коэффициентов. Тогда временная сложность данной атаки составляет O(n^3), требующая n различных известных пар (x, y).
Временная сложность
Предположим, что функцию можно выразить через коэффициентов, а функцию – через коэффициентов. Тогда для решения уравнения, представленного в виде матричного уравнения, потребуется известных различных пар. Однако данное матричное уравнение имеет решение с точностью до умножения и добавления. Чтобы гарантировать получение единственного и ненулевого решения, мы устанавливаем коэффициент при старшей степени равным единице, а свободный член – нулю. Следовательно, требуется известных различных пар. Таким образом, временная сложность данной атаки составляет , что требует известных различных пар. При использовании подхода "встреча посередине" общее количество коэффициентов обычно меньше, чем при использовании стандартного метода. Это делает метод более эффективным, поскольку требуется меньше пар.
Восстановление ключа
Мы также можем использовать интерполяционную атаку для восстановления секретного ключа. Если мы удалим последний раунд из итерационного шифра с длиной блока , выход шифра станет . Назовем этот шифр – упрощенным шифром. Идея заключается в том, чтобы сделать предположение о ключе последнего раунда , такое, чтобы мы могли расшифровать один раунд и получить выход упрощенного шифра . Затем, чтобы проверить это предположение, мы используем интерполяционную атаку на упрощенный шифр либо обычным методом, либо методом «Встреча в середине». Вот как это делается. Обычным методом мы выражаем выход упрощенного шифра как полином от открытого текста. Обозначим этот полином . Если мы можем выразить этот полином с коэффициентами, то, используя известных различных пар, мы можем построить этот полином. Чтобы проверить предположение о ключе последнего раунда, необходимо проверить с помощью одной дополнительной пары, выполняется ли следующее условие:
If we remove the last round of an round iterated cipher with block length , the output of the cipher becomes Call the cipher the reduced cipher. The idea is to make a guess on the last round key , such that we can decrypt one round to obtain the output of the reduced cipher. Then to verify the guess we use the interpolation attack on the reduced cipher either by the normal method or by the Meet In The Middle method. Here is how it is done. By the normal method we express the output of the reduced cipher as a polynomial of the plaintext Call the polynomial Then if we can express with coefficients, then using known distinct pairs, we can construct the polynomial. To verify the guess of the last round key, then check with one extra pair if it holds that
Если да, то с высокой вероятностью предположение о ключе последнего раунда было верным. Если нет, то делаем другое предположение о ключе. Методом «Встреча в середине» мы выражаем выход раунда как полином от открытого текста , а также как полином от выхода упрощенного шифра . Обозначим эти полиномы и , и пусть они будут выражены соответственно с помощью и коэффициентов. Тогда, имея известных различных пар, мы можем найти эти коэффициенты. Чтобы проверить предположение о ключе последнего раунда, необходимо проверить с помощью одной дополнительной пары, выполняется ли следующее условие:
Если да, то с высокой вероятностью предположение о ключе последнего раунда было верным. Если нет, то делаем другое предположение о ключе. Как только мы найдем правильный ключ последнего раунда, мы можем продолжить аналогичным образом с оставшимися ключами раундов.
Временная сложность
С секретным ключом циклической структуры длины *n*, существует 2^n различных ключей. Каждый из них имеет вероятность 1/2^n быть правильным при случайном выборе. Поэтому, в среднем, потребуется сделать 2^n попыток, прежде чем найти правильный ключ. Следовательно, у стандартного метода средняя временная сложность 2^n, требующая 2^n известных различных пар (plaintext, ciphertext), а у метода "встреча посередине" (Meet In The Middle) средняя временная сложность 2^(n/2), требующая 2^(n/2) известных различных пар (plaintext, ciphertext).
Реальное применение
Атака "встреча посередине" может быть использована в варианте для атаки на S-блоки, использующем обратную функцию, поскольку при S-блоке размером *n* бит, то в...
Блок-шифр SHARK использует SP-сеть с S-блоками. Шифр устойчив к дифференциальному и линейному криптоанализу после небольшого числа раундов. Однако в 1996 году он был взломан Томасом Якобсеном и Ларсом Кнудсеном с использованием интерполяционной атаки. Обозначим SHARK версию SHARK с размером блока *n* бит, использующую параллельные S-блоки размером *m* бит в *r* раундах. Якобсен и Кнудсен обнаружили, что существует интерполяционная атака на SHARK (64-битный блок-шифр) с использованием примерно *x* выбранных открытых текстов, и интерполяционная атака на SHARK (128-битный блок-шифр) с использованием примерно *y* выбранных открытых текстов. Также Томас Якобсен представил вероятностную версию интерполяционной атаки, используя алгоритм Мадху Судана для улучшения декодирования кодов Рида-Соломона. Эта атака может работать даже тогда, когда алгебраическая зависимость между открытым текстом и зашифрованным текстом выполняется только для части значений.
The block cipher SHARK uses SP network with S box The cipher is resistant against differential and linear cryptanalysis after
a small number of rounds. However it was broken in 1996 by Thomas Jakobsen and Lars Knudsen, using interpolation attack. Denote by SHARK a version of SHARK with block size bits using parallel bit S boxes in rounds. Jakobsen and Knudsen found that there exist an interpolation attack on SHARK (64 bit block cipher) using about chosen plaintexts, and an interpolation attack on SHARK (128 bit block cipher) using about chosen plaintexts. Also Thomas Jakobsen introduced a probabilistic version of the interpolation attack using Madhu Sudan's algorithm for improved decoding of Reed Solomon codes. This attack can work even when an algebraic relationship between plaintexts and ciphertexts holds for only a fraction of values.