AES (Rijndael)

Октябрь 2001 года. NIST публикует FIPS-197: победитель пятилетнего открытого конкурса - Rijndael от двух бельгийских криптографов, никогда не работавших на разведку. Спустя четверть века этот шифр защищает iMessage, банковские транзакции, SSL/TLS-трафик к google.com, конфиденциальные данные АНБ (для уровня TOP SECRET - AES-256). Не существует ни одной публично известной атаки лучше brute-force на полные 14 раундов AES-256. Стандарт, выбранный открытым голосованием, стал самым проверенным шифром в истории человечества.

• **iMessage и WhatsApp**: end-to-end шифрование сообщений строится на AES-256 с уникальным сессионным ключом per chat; протокол обмена ключей - X3DH + Double Ratchet (Signal Protocol)
• **TLS 1.3 (2018)**: 70% Web-трафика использует AES-GCM как симметричный шифр; AES-NI на серверах даёт terabit-per-second throughput
• **BitLocker, FileVault, LUKS**: full-disk encryption на Windows/macOS/Linux всё построено на AES-XTS (специальный режим для дисков); ключ выводится из пароля через PBKDF2 или Argon2

SubBytes: единственный нелинейный шаг

В 1997 году NIST объявил открытый конкурс на замену DES. Из 15 претендентов в финал вышли пять, и в 2001 году победил Rijndael от бельгийцев Joan Daemen и Vincent Rijmen. Стандарт получил имя AES (Advanced Encryption Standard). Размер блока - 128 бит, ключ - 128, 192 или 256 бит, число раундов - 10, 12 или 14 соответственно. В отличие от DES это не сеть Фейстеля, а **SP-сеть** (Substitution-Permutation): каждый раунд применяет четыре трансформации - SubBytes, ShiftRows, MixColumns, AddRoundKey. **SubBytes** - единственная нелинейная операция, и без неё AES линейный, а значит ломается простой линейной алгеброй.

SubBytes работает с состоянием как с 4x4 матрицей байтов. Каждый байт заменяется по таблице (S-box) размером 256 элементов. Этот S-box построен математически: для байта b его новое значение = аффинное преобразование от мультипликативного обратного b в поле GF(2^8). Это даёт sb-box максимальную нелинейность и balanced distribution, что важно для устойчивости к дифференциальному и линейному криптоанализу. Аффинное преобразование добавлено отдельно, чтобы исключить fixed-points (b -> b) и opposite fixed-points (b -> ~b).

ShiftRows и MixColumns: диффузия

SubBytes - локальная операция: каждый байт заменяется независимо. Чтобы изменение одного входного байта повлияло на много выходных, нужна **диффузия**. **ShiftRows** циклически сдвигает строки 4x4 состояния: строка 0 не сдвигается, строка 1 на 1 байт влево, строка 2 на 2, строка 3 на 3. Этот шаг 'размазывает' байты по столбцам. **MixColumns** умножает каждый столбец на фиксированную матрицу в GF(2^8) - один входной байт влияет на все 4 выходных байта столбца. Вместе эти два шага дают **полную диффузию** за два раунда: один бит входа меняет все 128 бит выхода.

Avalanche effect AES: один изменённый бит plaintext меняет в среднем 64 бита (50%) ciphertext - идеальный показатель. Для сравнения: однораундовый AES без MixColumns не достигает avalanche, потому что диффузия медленная. Принципы Шеннона из 1949 года формализовали это как 'confusion' (нелинейная связь между ключом и ciphertext, реализуется через SubBytes) и 'diffusion' (распределение редундантности plaintext по ciphertext, реализуется ShiftRows + MixColumns). AES - канонический пример этих принципов.

Расширение ключа

Из одного 128/192/256-битного ключа AES нужно получить 11/13/15 раундовых ключей по 128 бит каждый - всего 176/208/240 байт ключевого материала. Это делает **Key Expansion**. Алгоритм: разделить master key на слова по 4 байта (4/6/8 слов соответственно), затем итеративно генерировать новые слова: w[i] = w[i - Nk] XOR f(w[i-1]), где f - либо обычное копирование, либо специальная трансформация RotWord + SubWord + XOR с RCON для каждого Nk-го слова. RCON - таблица степеней 2 в GF(2^8): rcon[i] = 2^(i-1).

Свойства Key Expansion: (1) нелинейность через SubWord (применение S-box к 4 байтам) - линейный key schedule был бы уязвим к related-key attacks; (2) необратимость по дизайну - зная один раундовый ключ, нельзя восстановить master key за полиномиальное время; (3) дешёвая инкрементальная генерация - можно вычислять ключи на лету в hardware. Слабость замечена в 2009 году: для AES-256 существует related-key атака на полные 14 раундов сложностью 2^99 (Biryukov & Khovratovich) - это академическая угроза, не практическая, потому что requires контроль связи между ключами.

Безопасность AES

За 25 лет публичного анализа AES не получил ни одной практической атаки лучше полного перебора. Лучшая известная атака на AES-128 - biclique cryptanalysis (Bogdanov, Khovratovich, Rechberger 2011) со сложностью 2^126.1 - всего на 2 бита эффективнее, чем 2^128 brute force. На современном оборудовании 2^128 = принципиально невыполнимо: миллиард GPU за миллиард лет покроют ~2^100. AES-256 имеет дополнительный margin: 2^254 даже для гипотетических атак на 14 раундов. Этого достаточно даже с учётом возможного появления квантовых компьютеров (алгоритм Гровера сокращает 2^n до 2^(n/2)) - AES-256 даёт post-quantum 128-битную безопасность.

Что атакует AES в реальности: (1) Side-channel - timing attacks на cache (Bernstein 2005 показал утечки через распределение времени доступа к S-box таблице), power analysis, EM emission. Решения: constant-time реализация, AES-NI hardware-инструкции; (2) Implementation bugs - неправильное использование режимов (ECB вместо CBC/GCM, повтор nonce в GCM); (3) Key management - утечка master key через memory dumps, неправильное PBKDF2/Argon2 при выводе ключа из пароля. Сам алгоритм - стена; атакуют то, что вокруг.

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

• **SubBytes** - единственный нелинейный шаг AES, реализованный через мультипликативное обратное в GF(2^8) и аффинное преобразование; источник криптостойкости
• **ShiftRows + MixColumns** - линейные операции диффузии: за 2 раунда один бит входа влияет на все 128 бит выхода (avalanche effect)
• **Key Expansion** генерирует 11/13/15 раундовых ключей из одного master-ключа через SubWord, RotWord и RCON-константы; защита от related-key атак
• **Безопасность** - алгоритм без практических атак за 25 лет; реальные уязвимости приходят через side-channels (timing, power) и неправильное использование (повтор nonce, фиксированный IV)

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

FIPS-197 из вступления изменил индустрию: открытый конкурс показал, что лучший шифр выбирается публичным анализом, а не Closed-Door принципом. AES стоит в центре современной криптографии и связан с целым стеком практических протоколов:

• DES и 3DES — Предшественник AES; конкурс NIST на замену DES в 1997-2001 годах задал критерии (128-битный блок, открытый дизайн, hardware-efficiency), под которые победил Rijndael
• Режимы блочных шифров — AES сам по себе шифрует только 128 бит; для больших сообщений нужны режимы (CBC, CTR, GCM); неправильный режим (ECB, повторный nonce) ломает безопасность сильнее, чем слабый блочный шифр
• AEAD и GCM — AES-GCM - современный AEAD-стандарт, дающий одновременно confidentiality и integrity; используется в TLS 1.3 и большинстве production-систем

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

• AES-128 защищает банковский трафик и при квантовом компьютере деградирует до 64-битной безопасности (Гровер). AES-256 - до 128. Стоит ли уже сейчас мигрировать legacy-системы на AES-256, или это преждевременная оптимизация?
• Daemen и Rijmen опубликовали полную спецификацию Rijndael до победы в конкурсе - и это помогло, а не повредило. Сравните с подходом NSA в проектировании DES (S-боксы держались в секрете 15 лет). Какой подход выигрывает долгосрочно?
• AES-NI ускоряет шифрование в 10 раз и даёт constant-time реализацию против timing attacks. Что произойдёт с защищённостью систем, если найдётся уязвимость в самом hardware-блоке AES-NI?

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

• crypto-13-des — DES - предшественник, понимание Feistel vs SPN важно для AES
• crypto-15-block-cipher-modes — AES используется во всех режимах блочного шифрования
• crypto-07-computational-complexity — 128/256-битные ключи: невозможность brute-force через сложность
• alg-01-big-o — O(2^128) для AES-128: почему это недостижимо даже для квантовых компьютеров
• net-23-https-tls
• net-34-ipsec