Блочные шифры: принципы

В 1977 году IBM и АНБ анонсировали DES - стандарт шифрования США. Академическое сообщество было в ярости: S-блоки выглядели странно, АНБ участвовало в разработке. Подозревали бэкдор. Через 20 лет выяснилось: S-блоки были специально укреплены против дифференциального криптоанализа - метода, который АНБ знало, а академическое сообщество изобрело заново только в 1990 году.

• **AES** (Rijndael) с 2001 года - мировой стандарт шифрования: HTTPS, Wi-Fi, SSD-шифрование, iPhone Secure Enclave
• **DES Triple-DES**: шифрование данных банков и платёжных карт использовало 3DES вплоть до 2023 года, когда его официально отозвали
• **Современные атаки**: лучший взлом AES-128 требует 2^126 операций (Biclique attack, 2011) - практически неотличимо от полного перебора 2^128

Сеть Фейстеля

1973 год: IBM публикует DES. Его сердце - сеть Фейстеля, изобретённая Хорстом Фейстелем. Гениальное свойство: **шифрование и дешифрование используют одну и ту же схему**, только ключи раундов применяются в обратном порядке. Входной блок делится на левую (L) и правую (R) половины. Раунд: L_new = R, R_new = L XOR F(R, K). Функция F может быть сколь угодно сложной - обратимость обеспечивается XOR-структурой, а не обратимостью самой F.

Свойства сети Фейстеля: (1) Обратимость: даже если F не обратима, шифр обратим благодаря XOR; (2) Симметрия enc/dec: один и тот же hardware/software, только ключи в обратном порядке - критично для эффективной реализации; (3) Количество раундов: DES - 16 раундов, больше раундов = выше безопасность, ниже скорость; (4) Не все блочные шифры Feistel-based: AES использует SPN (Substitution-Permutation Network) - более эффективную структуру.

S-блоки (Substitution Boxes)

Если функция раунда в Feistel-сети линейна (XOR, сдвиги), криптоаналитик строит систему линейных уравнений и решает её. Нелинейность - обязательное условие безопасности. **S-блок (Substitution Box)** - нелинейная таблица замены: принимает n бит на вход и возвращает m бит на выход (обычно 6->4 в DES, 8->8 в AES). 8 S-блоков DES - единственный источник нелинейности в шифре. AES использует один S-блок на основе операции инверсии в поле GF(2^8).

Критерии безопасного S-блока (критерии Адамара): (1) Нелинейность: максимальная корреляция с любой линейной функцией должна быть минимальной; (2) Строгий лавинный критерий (SAC): изменение одного входного бита меняет каждый выходной бит с вероятностью 1/2; (3) Условие инъективности (для AES): 8->8 S-блок должен быть биекцией; (4) Алгебраическая сложность: не должно быть простого алгебраического представления. S-блоки DES проектировались с учётом дифференциального криптоанализа (который был засекречен IBM).

Перемешивание и диффузия

Клод Шеннон в 1949 году сформулировал два принципа безопасного шифра: **перемешивание (confusion)** - сокрытие связи между ключом и шифртекстом (обеспечивается S-блоками), и **диффузия (diffusion)** - распространение изменения одного бита открытого текста на весь шифртекст (обеспечивается перестановками и линейными слоями). AES реализует диффузию через ShiftRows (сдвиг строк) и MixColumns (умножение на матрицу в GF(2^8)) - после двух раундов каждый бит шифртекста зависит от каждого бита открытого текста.

AES структура (SPN - Substitution-Permutation Network): раунд = SubBytes (S-блоки, confusion) + ShiftRows (сдвиг строк, диффузия в пределах строк) + MixColumns (умножение на MDS-матрицу, максимальная диффузия между столбцами) + AddRoundKey (XOR с ключом раунда). 10/12/14 раундов для 128/192/256-битных ключей. MixColumns: каждый байт столбца перемешивается с остальными тремя, обеспечивая Branch Number = 5 (максимум для 4-байт операции).

Лавинный эффект

Хороший блочный шифр должен демонстрировать **лавинный эффект**: изменение одного бита открытого текста или ключа должно приводить к изменению примерно половины бит шифртекста. Это свойство делает невозможными атаки, основанные на анализе частичных изменений. После первого раунда AES одно изменение затрагивает 4 байта, после двух раундов - все 16 байт. Это называется полной диффузией за 2 раунда (two-round diffusion). DES достигает полной диффузии за 5-6 раундов - именно поэтому AES эффективнее при том же числе раундов.

Формальное измерение лавинного эффекта: (1) SAC (Strict Avalanche Criterion): каждый выходной бит изменяется с P=0.5 при изменении любого одного входного бита; (2) BIC (Bit Independence Criterion): выходные биты изменяются независимо друг от друга; (3) Расстояние Хэмминга между шифртекстами при 1-битном изменении входа должно быть ~N/2. Недостаточный лавинный эффект - признак слабости шифра: DES с 5 раундами вместо 16 уязвим к дифференциальному криптоанализу.

Ключевые идеи

• **Сеть Фейстеля** обеспечивает обратимость через XOR, не требуя обратимости функции раунда F - это позволяет использовать сложные нелинейные преобразования
• **S-блоки** - единственный источник нелинейности в блочных шифрах; без них линейный криптоанализ вскрывает ключ за субэкспоненциальное время
• **Confusion + Diffusion** (Шеннон, 1949): S-блоки скрывают связь ключ/шифртекст, а перестановки/MixColumns распространяют изменения - вместе за 10 раундов дают AES

Связанные темы

Принципы блочных шифров применяются во всей современной криптографии:

• Криптоанализ классических шифров — Линейный и дифференциальный криптоанализ - прямые наследники частотного анализа; S-блоки DES спроектированы именно для защиты от них
• DES — DES - первая промышленная реализация принципов Фейстеля и Шеннона; его анализ обнажил требования к числу раундов и качеству S-блоков

Вопросы для размышления

• Если увеличить число раундов AES с 10 до 20, как это повлияет на безопасность и производительность? Есть ли точка убывающей отдачи?
• АНБ знало о дифференциальном криптоанализе в 1970-х и укрепило S-блоки DES. Как это влияет на доверие к стандартам шифрования?
• MixColumns AES - линейная операция в GF(2^8). Почему линейность здесь допустима, несмотря на то что линейность S-блоков была бы катастрофой?

Связанные уроки

• alg-35-bit-manipulation
• nt-03