Линейный криптоанализ и таблицы приближений

Линейный криптоанализ (Мацуй, 1993) — это атака с известным открытым текстом, которая находит линейные аппроксимации (XOR определённых битов) шифра, выполняющиеся с вероятностью p ≠ 1/2. Используя множество пар открытый текст–шифртекст, можно по статистическому смещению раскрыть биты ключа.

Линейная аппроксимация для S-блока: сумма выбранных битов входа XOR сумма выбранных битов выхода = 0 (mod 2) с вероятностью p. Она выражается так: P[a·x XOR b·y = 0] = 1/2 + ε, где a,b — битовые маски, а ε — смещение (желательно, чтобы |ε| >> 0).

LAT подсчитывает для каждой маски входа a и маски выхода b количество входов x, для которых (a·x) XOR (b·S(x)) = 0. Вычтите 2^{n-1}, чтобы получить смещение. У хорошего S-блока |max_bias| = 1 (вероятность 1/2 ± 1/2^{n/2}), то есть таблица максимально равномерна.

Для независимых линейных аппроксимаций через несколько раундов смещения перемножаются: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Каждая аппроксимация раунда вдвое уменьшает эффективное смещение. После большого числа раундов общее смещение приближается к 0, поэтому для его обнаружения требуется экспоненциально больше пар.

Чтобы атаковать шифр с r раундами, найдите линейный след ε через r-1 раундов. Соберите N = 1/ε^2 открытых текстов, известных атакующему. Для каждого кандидата на байт ключа последнего раунда k' частично расшифруйте последний раунд с помощью XOR и проверьте, выполняется ли линейная аппроксимация чаще N/2 раз. Правильный k' демонстрирует правильное смещение.

В 1993 году Мацуй атаковал DES с 16 раундами, используя линейную аппроксимацию 14 раундов со смещением 2^{-21.4}. Потребовалось 2^{43} известных открытых текстов. На первом этапе были восстановлены 26 битов ключа, а оставшиеся 30 — полным перебором. Это была первая практическая атака, оказавшаяся быстрее полного перебора всего ключевого пространства DES.

Максимальное значение LAT для S-блока AES: |ε| = 4/256 = 1/64. Стратегия широкого следа ограничивает число активных S-блоков в любом следе из 4 раундов значением ≥ 25. Общее смещение ≤ (1/64)^{25/2} ≈ 2^{-75}. Требуется 2^{150} известных открытых текстов, что практически невыполнимо.

Дифференциальный: пары известных или выбранных открытых текстов; использует разности на выходе. Линейный: известные открытые тексты; использует статистические линейные аппроксимации. На практике оба метода применяются как атаки с выбранным открытым текстом. Оба являются критериями проектирования: S-блоки должны противостоять обоим методам — иметь малый максимум DDT И малый максимум LAT.

Используйте несколько линейных аппроксимаций одновременно, чтобы уменьшить сложность по данным. Нюберг и Леандер расширили метод Мацуй: объединение M аппроксимаций сокращает объём данных в log(M) раз. Метод применяется к PRESENT, SIMON и другим лёгким шифрам.

Линейная аппроксимация, применённая к потоковым шифрам: найдите корреляцию между гаммой и линейной функцией выхода LFSR. Такая корреляция, если она ненулевая, позволяет восстановить ключ быстрее полного перебора. Этот подход повлиял на проектирование нелинейных объединяющих функций в потоковых шифрах.

Интегральный криптоанализ (Кнудсен—Вагнер): выберите набор открытых текстов, в котором некоторые байты принимают все 256 значений, а остальные остаются фиксированными. После нескольких раундов XOR всех выходов в определённых позициях равен 0, то есть они сбалансированы. Метод использует структуру AES и эффективно взламывает AES с уменьшенным числом раундов.

Что утверждает лемма о накоплении при объединении линейных аппроксимаций?

Линейный криптоанализ находит линейные аппроксимации S-блоков со смещением. AES противостоит ему благодаря оптимальному с точки зрения LAT S-блоку и стратегии широкого следа. Мацуй взломал DES с помощью следа из 14 раундов, используя 2^43 известных открытых текстов. Далее: атаки дней рождения и поиск коллизий.