Итеративный блочный шифр

Итеративный блочный шифр — это разновидность симметричного криптографического алгоритма, который преобразует блок данных фиксированной длины в блок зашифрованного текста той же длины путём многократного повторения (итерации) одной и той же последовательности операций, называемой раундом. В отличие от поточных шифров, обрабатывающих данные побитно или побайтово, блочные шифры работают с целыми блоками, обычно размером 64, 128 или 256 бит. Итеративный принцип позволяет достичь высокой стойкости к криптоанализу при относительно простой реализации, так как сложность алгоритма наращивается за счёт числа раундов, а не усложнения отдельной операции.

Принцип работы

Основой итеративного блочного шифра является раундовая функция — преобразование, которое на каждом раунде принимает на вход блок данных и раундовый ключ (полученный из основного ключа шифрования с помощью процедуры расширения ключа). На выходе раундовой функции получается промежуточное состояние блока, которое передаётся на следующий раунд. Количество раундов (обычно от 10 до 16 для современных алгоритмов) выбирается таким образом, чтобы обеспечить необходимый уровень безопасности, в том числе против дифференциального и линейного криптоанализа.

Структура раунда

Типичный раунд итеративного блочного шифра включает несколько этапов:

• Подмешивание ключа (Key Addition) — операция XOR между текущим состоянием блока и раундовым ключом.
• Замена (Substitution) — нелинейное преобразование, часто реализуемое через S-блоки (таблицы замены), которое вносит нелинейность и затрудняет криптоанализ.
• Перестановка (Permutation) — линейное преобразование, перемешивающее биты внутри блока для распространения влияния каждого бита на как можно большее число выходных битов (свойство лавинного эффекта).

В некоторых шифрах (например, AES) эти этапы объединены в структуру, называемую SP-сеть (Substitution-Permutation Network). В других (например, DES) используется сеть Фейстеля, где блок делится на две половины, и на каждом раунде преобразуется только одна половина с помощью раундовой функции, а затем половинки меняются местами.

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

Для каждого раунда требуется свой раундовый ключ. Процедура расширения ключа (Key Schedule) из основного ключа шифрования генерирует последовательность раундовых ключей. Качество этой процедуры критически важно: если раундовые ключи связаны простой зависимостью, злоумышленник может восстановить основной ключ, зная один из раундовых. Современные шифры (например, AES) используют нелинейные преобразования и циклические сдвиги для генерации ключей.

Классификация

Итеративные блочные шифры классифицируют по нескольким признакам:

По архитектуре раунда

• Сеть Фейстеля (Feistel network) — блок делится на две равные части; на каждом раунде одна половина преобразуется с помощью раундовой функции, зависящей от другой половины и раундового ключа, затем половинки меняются местами. Примеры: DES, ГОСТ 28147-89, Blowfish.
• SP-сеть (Substitution-Permutation network) — на каждом раунде весь блок последовательно проходит через слои замены и перестановки. Примеры: AES (Rijndael), Serpent.
• ARX-конструкция (Add-Rotate-XOR) — использует только операции сложения, циклического сдвига и XOR, без S-блоков. Примеры: ChaCha20, Speck, Threefish.

По размеру блока и ключа

• 64-битные блоки — исторически распространены (DES, IDEA), но уязвимы к атакам на основе коллизий при больших объёмах данных. Современные стандарты рекомендуют блоки не менее 128 бит.
• 128-битные блоки — стандарт для современных алгоритмов (AES, Camellia, SM4).
• Ключи — от 56 бит (DES, ныне небезопасен) до 256 бит (AES-256) и более.

По режиму работы

Итеративный блочный шифр сам по себе шифрует только один блок. Для шифрования сообщений произвольной длины используются режимы работы (mode of operation):

• ECB (Electronic Codebook) — каждый блок шифруется независимо; уязвим к статистическим атакам.
• CBC (Cipher Block Chaining) — каждый блок перед шифрованием XOR-ится с предыдущим зашифрованным блоком.
• CTR (Counter) — шифруется счётчик, результат XOR-ится с открытым текстом; позволяет параллельное шифрование.
• GCM (Galois/Counter Mode) — обеспечивает шифрование и аутентификацию (AEAD).

История развития

Первым широко распространённым итеративным блочным шифром стал DES (Data Encryption Standard), принятый в 1977 году Национальным бюро стандартов США. Он использовал 56-битный ключ, 64-битный блок и 16 раундов сети Фейстеля. К концу 1990-х годов DES считался уязвимым из-за малой длины ключа, что привело к разработке Triple DES (3DES) — трёхкратного применения DES с разными ключами.

В 2001 году Национальный институт стандартов и технологий США (NIST) принял AES (Advanced Encryption Standard) на основе алгоритма Rijndael, разработанного бельгийскими криптографами Йоаном Дайменом и Винсентом Рейменом. AES использует SP-сеть, блок 128 бит, ключи 128, 192 или 256 бит и 10–14 раундов. Он стал стандартом де-факто для большинства криптографических приложений.

В России в 1989 году был принят ГОСТ 28147-89 — 64-битный блочный шифр с 256-битным ключом и 32 раундами сети Фейстеля. В 2015 году его заменил ГОСТ Р 34.12-2015 (стандарт «Кузнечик»), который использует 128-битный блок, 256-битный ключ и 10 раундов SP-сети.

Современные алгоритмы

Помимо AES, существуют другие широко используемые итеративные блочные шифры:

• Camellia — разработан японскими компаниями NTT и Mitsubishi Electric; блок 128 бит, ключи 128, 192, 256 бит; сертифицирован NESSIE и ISO/IEC 18033-3.
• SM4 — китайский национальный стандарт (GB/T 32907-2016); блок 128 бит, ключ 128 бит, 32 раунда сети Фейстеля.
• ChaCha20 — потоковый шифр, но может использоваться как блочный в режиме CTR; основан на ARX-конструкции; широко применяется в TLS (протоколы безопасности транспортного уровня) и VPN.
• Blowfish и Twofish — разработаны Брюсом Шнайером; Blowfish (64-битный блок) устарел, Twofish (128-битный блок) был финалистом конкурса AES.

Криптоанализ и стойкость

Итеративные блочные шифры подвержены нескольким классам атак:

• Дифференциальный криптоанализ — основан на изучении влияния разностей в открытых текстах на разности в зашифрованных. Современные шифры проектируются так, чтобы вероятность появления полезных дифференциалов была пренебрежимо мала.
• Линейный криптоанализ — использует линейные аппроксимации между битами открытого текста, шифротекста и ключа. Для защиты вводят нелинейные S-блоки с высокой нелинейностью.
• Атаки на основе времени (timing attacks) и побочных каналов (side-channel attacks) — используют зависимость времени выполнения или энергопотребления от данных. Для защиты применяют константное время выполнения и маскирование.
• Атаки на основе связанных ключей (related-key attacks) — возможны при плохой процедуре расширения ключа. AES-256 показал уязвимость к таким атакам в некоторых моделях, но практическая опасность спорна.

Для обеспечения безопасности на длительный срок (например, до 2030 года) рекомендуется использовать алгоритмы с ключом не менее 128 бит и блоком не менее 128 бит, а также применять аутентифицированное шифрование (GCM, CCM).

Применение

Итеративные блочные шифры используются повсеместно:

• Безопасность сетей — в протоколах TLS (AES, ChaCha20), IPsec (AES, Camellia), SSH (AES, ChaCha20).
• Шифрование дисков — BitLocker (AES), FileVault (AES), LUKS (AES, Twofish, Serpent).
• Электронная почта — PGP и S/MIME (AES, 3DES).
• Мобильные устройства — SIM-карты и NFC (AES, DES).
• Криптовалюты — хеширование и шифрование транзакций (AES, ChaCha20).

Интересные факты

• Алгоритм AES был выбран из 15 кандидатов в ходе открытого конкурса NIST (1997–2000). Победитель Rijndael получил 86 голосов из 122.
• Шифр ГОСТ 28147-89 долгое время был секретным и не публиковался в открытой печати до 1994 года.
• Самый быстрый итеративный блочный шифр на современных процессорах с поддержкой AES-NI (набор инструкций) — AES, который может шифровать со скоростью более 1 ГБ/с на одном ядре.
• В 1998 году Electronic Frontier Foundation (EFF) построила машину Deep Crack, которая взломала DES за 56 часов. Сейчас аналогичную задачу можно решить за несколько минут на обычном ПК.

Источники

• Шнайер Б. «Прикладная криптография». — М.: Триумф, 2002.
• Смарт Н. «Криптография». — М.: Техносфера, 2006.
• NIST FIPS 197: Advanced Encryption Standard (AES).
• ГОСТ Р 34.12-2015. Информационная технология. Криптографическая защита информации. Блочные шифры.
• Paar C., Pelzl J. «Understanding Cryptography». — Springer, 2010.