Технология и формат XX–XXI вв.

Шифр Вернама и блочный стандарт шифрования AES

От абсолютно стойкого телеграфного шифра Первой мировой войны и теоремы Клода Шеннона (1949) к открытому стандарту FIPS 197 (2001), защитившему глобальную экономику и государственные тайны.

Краткая справка

Шифр Вернама (1917), дополненный требованием однократного случайного ключа, стал единственной криптосистемой с математически доказанной Клодом Шенноном (1949) абсолютной стойкостью, но оставался неудобным для массовой коммерции из-за длины ключей. Когда 56-битный стандарт DES устарел и утратил доверие, открытый международный конкурс NIST (1997–2001) утвердил бельгийский алгоритм Rijndael стандартом AES, положив конец криптовойнам 1990-х и обеспечив защиту HTTPS, Wi-Fi и гостайн.

Схема нелинейной подстановки байтов SubBytes в раунде блочного шифра AES (Rijndael)
Операция SubBytes в алгоритме AES: каждый байт 128-битной матрицы состояния заменяется по таблице S-box, вычисленной в поле Галуа GF(2⁸) для защиты от линейного и дифференциального криптоанализа. Иллюстрация: Matt Crypto, Public domain

От телетайпного ключа Вернама к краху DES и конкурсу AES

В годы Первой мировой войны массовое внедрение телетайпов потребовало быстрой автоматической криптографии, защищённой от перехвата. В 1917 году инженер AT&T Гилберт Вернам изобрёл релейное устройство (патент США № 1 310 719 от 22 июля 1919 г.), побитово складывавшее пятибитный код Бодо с ключевой перфолентой. Исходная замкнутая петля ленты повторялась и поддавалась взлому, пока офицер Корпуса связи США Джозеф Моборн не предложил делать ключ полностью случайным и однократным — так появился «одноразовый блокнот» (One-Time Pad). В секретном отчёте 1945 года, опубликованном в октябре 1949 года в Bell System Technical Journal под названием «Теория связи в секретных системах», математик Bell Labs Клод Шеннон доказал абсолютную секретность шифра Вернама и сформулировал принципы конфузии и диффузии для практических шифров.

Однако шифр Вернама проиграл в гражданской экономике: необходимость заранее доставить безопасный ключ длиной с само сообщение ограничила его дипломатией, разведкой и горячей линией Москва — Вашингтон (причём повторное использование одноразовых лент СССР в 1940-х позволило американскому проекту «Венона» прочесть часть переписки). Массовой банковской и компьютерной индустрии требовался короткий ключ. Утверждённый в 1977 году 56-битный стандарт DES к концу 1990-х безнадёжно устарел (в 1998 году машина EFF Deep Crack перебрала ключ DES за 56 часов), а закрытые проекты спецслужб вроде Skipjack и чипа Clipper бизнес отверг в разгар «криптовойн» из-за экспортных запретов и подозрений во встроенных лазейках. Тогда 2 января 1997 года институт NIST объявил открытый мировой конкурс. Из 15 претендентов в финал вышли пять (MARS, RC6, Rijndael, Serpent, Twofish). 2 октября 2000 года победил бельгийский шифр Rijndael Йоана Даймена и Винсента Рэймена, утверждённый 26 ноября 2001 года как федеральный стандарт FIPS 197 (AES) и вступивший в силу 26 мая 2002 года.

Математика XOR и устройство SP-сети алгоритма AES

Шифр Вернама побитово складывает открытый текст с истинно случайным одноразовым ключом по модулю 2 (операция XOR, ⊕): Ci = Pi ⊕ Ki. Пока ключ случаен, непредсказуем и не повторяется, любая осмысленная расшифровка той же длины равновероятна, и перехват шифртекста не даёт противнику ни бита информации.

AES решает противоположную задачу: с помощью короткого ключа (128, 192 или 256 бит) превратить 128-битный блок данных в непроницаемую нелинейную перестановку за 10, 12 или 14 раундов. Отказавшись от сети Фейстеля (на которой строился DES), Даймен и Рэймен применили подстановочно-перестановочную сеть (SP-сеть) над байтовой матрицей состояния 4×4. Каждый раунд объединяет четыре операции: нелинейную замену байтов SubBytes через таблицу S-box (вычисление обратного элемента в конечном поле Галуа GF(28) по модулю полинома z8 + z4 + z3 + z + 1 с аффинным преобразованием), циклический сдвиг строк ShiftRows, линейное перемешивание столбцов MixColumns (MDS-матрица в GF(28)) и наложение раундового ключа AddRoundKey из процедуры расширения ключа. Оптимизация таблицами поиска дала Rijndael лидерство по скорости от 8-битных смарт-карт до 64-битных серверов.

Победа открытой криптографии и защита глобальной инфраструктуры

Победа бельгийского открытого алгоритма разрушила монополию закрытых государственных шифров. В июне 2003 года АНБ США впервые в истории допустило публичный алгоритм для защиты государственной тайны — уровень SECRET (128 бит) и TOP SECRET (192 и 256 бит; современные требования предписывают 256 бит), а обязательная сертификация модулей по программе NIST/CSEC CMVP (FIPS 140-2) сделала совместимость с AES условием госзакупок США и Канады. Свободный от патентных отчислений стандарт (также ISO/IEC 18033-3) стал рабочей основой защищённого веба HTTPS/TLS, сетей Wi-Fi (WPA2 и WPA3), корпоративных VPN, шифрования дисков (BitLocker, FileVault, dm-crypt) и процессинга банковских карт.

В 2005 году Дэниел Бернштейн и группа Ади Шамира продемонстрировали практические атаки по сторонним каналам (кеш-тайминг-атаки на OpenSSL и dm-crypt позволяли восстановить ключ за 800 операций шифрования). Ответом индустрии стало аппаратное ускорение: с 2010–2011 годов корпорации Intel (Arrandale, Sandy Bridge) и AMD (Bulldozer) встроили в процессоры инструкции AES-NI. Это снизило затраты с 18 до 1,3 такта на байт (гигабайты в секунду) и полностью закрыло тайминг-утечки на уровне кремния.

Дискуссии о криптостойкости и испытание квантовой эпохой

Лаконичная алгебра AES в GF(28) привлекла пристальное внимание криптоаналитиков. В 2002 году Н. Куртуа и Й. Пепшик предложили теоретическую XSL-атаку на основе разреженных уравнений. Брюс Шнайер и Нильс Фергюсон выражали осторожный скепсис к простой алгебраической структуре шифра, но Винсент Рэймен назвал XSL-атаку «лишь мечтой», а дальнейший анализ подтвердил её несостоятельность из-за переоценки числа независимых уравнений. Единственная атака на полный AES-128 быстрее перебора — метод биклик (А. Богданов, Д. Ховратович, К. Рехбергер, 2011; улучшена в 2015 г.) — снижает сложность лишь вчетверо, до 2126 операций, что физически неосуществимо.

На пороге квантовой эпохи асимметричные алгоритмы RSA и эллиптические кривые уязвимы для алгоритма Шора, тогда как квантовый поиск Гровера теоретически сокращает эффективную длину симметричного ключа лишь вдвое и плохо распараллеливается. Поэтому AES-256 сохраняет статус квантово-устойчивого мирового стандарта на десятилетия вперёд, сосуществуя с потоковым ChaCha20 и российским ГОСТ Р 34.12-2015 («Кузнечик»).

Цепочка влияния: причины и последствия

Исторический «эффект домино» — какие предпосылки вызвали это событие или явление и к каким переменам оно привело.

Что привело к этому (истоки и предпосылки)

Технология и форматвторая половина XIX в.Эволюция технологии и стандарта

Мультиплексная связь в телеграфии

Равномерный 5-битный код Бодо и временное разделение каналов напрямую породили перфоленточные телетайпы, поточное криптошифрование и архитектуру цифровых сетей.

Государства и ключевые связи в графе

Связанные личности, технологии, места и понятия

Технология и формат Мультиплексная связь в телеграфии вторая половина XIX в. — Эволюция технологии и стандарта

Частые вопросы и ответы

Почему шифр Вернама называют абсолютно стойким и почему его нельзя использовать вместо AES везде?
Клод Шеннон в 1949 году доказал, что при истинно случайном неповторяющемся ключе длиной не меньше самого сообщения перехватчик не получает никакой информации. Однако безопасная доставка гигабайтов и терабайтов одноразовых ключей в интернете невозможна — поэтому шифр Вернама используют лишь для особо секретных дипломатических и военных линий.
Почему на конкурсе NIST победил бельгийский алгоритм Rijndael, а не его конкуренты?
Помимо высокой криптостойкости, Rijndael показал наилучший баланс скорости, минимальных требований к памяти и простоты аппаратной и программной реализации как на 8-битных смарт-картах, так и на 32/64-битных серверах. Он обошёл в финале достойных соперников — Serpent, Twofish, RC6 и MARS.
Чем различаются варианты AES-128, AES-192 и AES-256?
Размер блока данных во всех трёх вариантах стандарта FIPS 197 жёстко фиксирован и равен 128 битам, но отличается длина ключа и число раундов перемешивания: 10 раундов для ключа 128 бит, 12 раундов для 192 бит и 14 раундов для 256 бит. Для максимальной долгосрочной защиты и против квантовых атак используют AES-256.
Взломали ли алгоритм AES на сегодняшний день?
Практически пригодного взлома самого алгоритма AES не существует. Лучшая теоретическая атака методом биклик (2011–2015) снижает сложность для AES-128 лишь с 2^128 до 2^126 операций, что физически неосуществимо. Реальные взломы затрагивают только слабые реализации по сторонним каналам (тайминг, энергопотребление) или утечки ключей.
Зачем в процессорах Intel и AMD ввели инструкции AES-NI?
Аппаратное выполнение раундов AES непосредственно на кремнии ускоряет шифрование более чем в десять раз (до гигабайтов в секунду на ядро), снижает энергопотребление мобильных устройств и устраняет зависимость времени выполнения от таблиц в кеше процессора, полностью блокируя тайминг-атаки.

Научная литература и источники

  1. AES (стандарт шифрования) — Википедия (математика раундов, история конкурса NIST, криптостойкость) [ru.wikipedia.org]
  2. Advanced Encryption Standard — Wikipedia (FIPS 197, оценка АНБ, атаки по сторонним каналам и биклик-анализ) [en.wikipedia.org]
  3. NIST FIPS PUB 197 — Specification for the Advanced Encryption Standard (AES), 2001 (upd. 2023) [nvlpubs.nist.gov]
  4. Joan Daemen, Vincent Rijmen — AES Proposal: Rijndael (документация авторов алгоритма для NIST) [csrc.nist.gov]
  5. One-time pad — Wikipedia (патент Гилберта Вернама 1919 г., вклад Дж. Моборна и К. Шеннона) [en.wikipedia.org]