Кнудсен, Ларс

Интегральный криптоанализ — это вид криптоанализа частично применимый для атак на блочные шифры, основанные на подстановочно-перестановочных сетях. Он был сформулирован Ларсом Кнудсеном в процессе поиска атаки на шифр SQUARE, поэтому в литературе его часто называют Square-атакой. Метод был расширен и применён на сходные с Square шифры CRYPTON, Rijndael, и SHARK. Модификации Square-атаки также были применены к шифрам Hierocrypt-L1, IDEA, Camellia, Skipjack, MISTY1, MISTY2, SAFER++, KHAZAD и FOX (сейчас называемый IDEA NXT).

Интегральный криптоанализ построен на принципе рассмотрения набора открытых текстов, в которых одна часть остаётся константой, а вторая варьируется всеми возможными способами. Например, атака может использовать набор из 256 открытых текстов, в которых все кроме 8 бит варьируются. Очевидно, что XOR этого набора равен нулю. XOR соответствующего набора шифротекстов даёт нам информацию о работе алгоритма шифрования. Такой метод использования большого набора открытых текстов вместо пары, как в дифференциальном криптоанализе, и дал название «интегральный».

Криптоанализ невозможных дифференциалов является разновидностью дифференциального криптоанализа, применённого к блочным шифрам. В обыкновенном дифференциальном криптоанализе рассматривается разница, имеющая некоторую конечную вероятность, в криптоанализе невозможных дифференциалов — разница, имеющая вероятность 0, то есть «невозможная».

Эта методика была впервые описана Ларсом Кнудсеном в заявке на конкурс AES по шифру DEAL. Название методике дали Эли Бихам, Алекс Бирюков и Ади Шамир на конференции CRYPTO’98.

Этот метод нашёл широкое применение и был использован в атаках на шифры IDEA, Khufu и Khafre, E2, разновидности Serpent, MARS, Twofish, Rijndael, CRYPTON, Zodiac (cipher), Hierocrypt-3, TEA, XTEA, Mini-AES, ARIA, Camellia, и SHACAL-2.

SAFER K-64 является итеративно блочным шифром. Алгоритм работает с 64-битовым блоком и 64-битовым ключом. Кнудсен обнаружил слабое место в распределении ключей. Их генерация в алгоритме была совсем не трудной. Первым подключом является сам ключ пользователя. Следующие подключи генерируются процедурой ${\displaystyle K_{i+1}=\left({K_{i}<<<3i}\right)+c_{i+1}}$. Операция <<< — циклический сдвиг влево на 3 бита внутри каждого байта ключа.

Константа ${\displaystyle c_{i}}$ получается из формулы ${\displaystyle c_{ij}=45^{45^{((9i+j){\mbox{ mod }}256)}{\mbox{ mod }}257}{\mbox{ mod }}257}$, где j — номер байта константы ${\displaystyle c_{i}}$. Слабость этого алгоритма заключалась в том, что почти для каждого ключа найдется не меньше одного(иногда даже 9) другого ключа, который при шифровании какого-то другого сообщения дает нам тот же самый шифрованный текст, то есть ${\displaystyle F(M_{1},K_{1})=F(M_{2},K_{2})}$. Кнудсен установил, что число различных открытых текстов, которые шифруются одинаковыми шифротекстами приблизительно ${\displaystyle 2^{22}}$ — ${\displaystyle 2^{28}}$ из возможных ${\displaystyle 2^{64}}$ текстов. В итоге с помощью анализа от ${\displaystyle 2^{44}}$ до ${\displaystyle 2^{47}}$ открытых текстов можно найти 8 бит исходного ключа, состоящего из 64 бит. Затем этот алгоритм был усовершенствован самим Кнудсеном до SAFER SK-64.

Существует шутка, что SK расшифровывается как Stop Knudsen, или в переводе «Остановить Кнудсена». Она появилась вследствие того, что новый алгоритм делал атаку Кнудсена безуспешной. На самом деле, SK расшифровывается как Strengthened Key Schedule, означающее «Усиленное расширение ключа».

В 1997 году Ларс Кнудсен вместе со своими коллегами Йоаном Дайменом (англ. Joan Daemen) и Винсентом Рэйменом (англ. Vincent Rijmen) разработали атаку на блочный шифр SQUARE[2]. Сам алгоритм состоял из 6 раундов, включающих 4 операции, линейное преобразование строк, нелинейную замену байт, транспонирование и сложение с ключом. Они выбрали атаку на основе подобранного открытого текста. Основная идея заключалась в выборе наборов текста. Было обнаружено, что из 256 выбранных открытых текстов найдутся два, которые однозначно определят ключ шифрования с подавляющим успехом, если бы шифр состоял из 4 раундов. Затем атака была продолжена на 5 и 6 раунды и успешно завершена, хотя и была невозможна из-за отсутствия современных технологий. Тем не менее, она считалась актуальной, так как она считалась одной из самых быстрых.

В своей статье «Hash functions based on block ciphers and quaternary codes»[3](«Хеш-функции, основанные на блочных шифрах и четвертичных кодах») Ларс Кнудсен показал, что разработка эффективной хеш-функции с минимальной встроенной памятью на основе m — битного блочного шифра представляет собой трудную задачу. Более того, ни одна из рассмотренным им хеш-функций не обеспечивала защиты лучше, чем 2^m получаемой методом «грубой силы». Изменяя модель немного(например, путём увеличения размера внутреннее памяти, а также путём введения выходных преобразований), можно получить функцию сжатия и, таким образом, хеш-функцию, для которой безопасность может быть доказана на основе вероятных предположений, сформулированных Кнудсеном. Предлагаемый им метод являлся как лучшим на текущий момент (а именно скорость шифрования равной ${\displaystyle {\frac {1}{4}}}$ или 4 для хеширования одного блока), так и обеспечивал высокий уровень безопасности, или более высокую эффективность при тех же уровнях безопасности. Для большого значения встроенной памяти, скорости близки к тем, которые могут быть получены. Кроме того, хеш-функция обеспечивает высокую степень параллелизма, которая даст ещё более эффективную реализацию.

RMAC[4] — система аутентификации на основе блочных шифров. В настоящее время алгоритмы блочного шифра, одобренные, чтобы использоваться в RMAC, являются AES и тройной-DES. В своей работе Кнудсен проанализировал эту систему и получил, что схема позволяет атаковать некоторый контроль над одним из двух ключей основного блочного шифра и это позволяет предпринять несколько связно-ключевых атак на RMAC. Также он описал эффективное нападение на RMAC при использовании с тройной-DES и общую атаку на RMAC, которая может быть использована по поиску одного ключа из двух быстрее, чем полный перебор. Его атака на RMAC-DES требует ${\displaystyle 2^{16}}$ набранных сообщений, которая практически возможна с сегодняшней скоростью обработки.

В своей работе Кнудсен исследовал фальсификацию и атаку на ключ восстановления на аутентификационной схеме 3gpp-MAC[5], предложенной в 3gpp спецификацию. Он предложил три основных класса атак. Атаки в первом классе используют большое количество «выбранных MACs», во втором классе используют большое количество «известных MACs», а в третьем классе требуется большое количество проверок MAC, но очень мало «известных MACs» и совсем не требуют «выбранных MACs». Первый класс предоставляет как фальсификацию, так и атаку на ключ восстановления, в то время как, второй и третий классы только атаку на ключ. Принимаются во внимание, как простые ключи(single-key), так и двойные ключи(two-key). Атака фальсификации имеет отношение к обоим видам ключей, в то время как, атака на ключ восстановления относится только ко второму варианты(two-key).

Структура хеш-функции CRUSH[6] показана на рисунке. Функция состоит их буфера данных (data buffer), компоненты биекционного выбора (Bijection Selection Component) логических (булевых) функций и биективной функции B (эффективного блочного шифра, для которого текст берется из буфера данных). Кнудсен показал, что CRUSH или более общий метод повторного деления на два (Iterated Halving) не удовлетворяют требованиям хороших хеш-функций или с точки зрения безопасности или выполнения. Он показал, как генерировать коллизии и вторые прообразы для использования Повторного деления на два (Iterated Halving). Возможность создания таких коллизий основана на функции B. Сложность этих атак является чрезвычайно малой и составляет всего лишь десяток расшифровок функции B, независимо от размера. Атаки применяются, когда используется любой блочный шифр, включая AES с 192-битовыми и AES c 256-битовыми ключами.