Twofish

Twofish — это симметричный блочный шифр, разработанный в 1998 году группой криптографов во главе с Брюсом Шнайером. Шифр является финалистом конкурса AES (Advanced Encryption Standard), проводившегося Национальным институтом стандартов и технологий США (NIST) для выбора нового стандарта шифрования. Twofish отличается высокой скоростью работы на различных платформах, гибкостью (поддержка ключей длиной 128, 192 и 256 бит) и устойчивостью к известным криптоаналитическим атакам, хотя и не был выбран в качестве финального стандарта AES.

История создания

Разработка Twofish началась в 1997 году, когда NIST объявил конкурс на создание нового стандарта шифрования, который должен был прийти на смену устаревшему DES. Команда Counterpane Systems (США) под руководством Брюса Шнайера, известного криптографа и автора шифра Blowfish, представила свой алгоритм в 1998 году. Twofish стал одним из пяти финалистов конкурса, наряду с MARS, RC6, Serpent и Rijndael. В 2000 году победителем был объявлен Rijndael, который впоследствии стал стандартом AES. Тем не менее, Twofish остаётся широко используемым алгоритмом, особенно в программных реализациях, где его производительность часто превосходит AES.

Описание алгоритма

Twofish представляет собой блочный шифр с размером блока 128 бит. Он использует структуру сети Фейстеля, что облегчает реализацию и делает шифр устойчивым к некоторым видам атак. Ключевой особенностью Twofish является использование предварительно вычисляемых S-блоков (таблиц замен), которые зависят от ключа, что усложняет криптоанализ.

Основные параметры

• Размер блока: 128 бит (16 байт).
• Длина ключа: 128, 192 или 256 бит (16, 24 или 32 байта).
• Число раундов: 16 (для всех длин ключа).
• Структура: Сеть Фейстеля с 4 ветвями.

Раундовая функция

Каждый раунд Twofish включает несколько этапов:

1. Разделение блока: 128-битный блок делится на 4 32-битных слова.
2. Применение S-блоков: Каждое слово проходит через 4 различных S-блока, которые зависят от ключа. S-блоки построены на основе арифметики в поле Галуа GF(2⁸) и включают нелинейные преобразования.
3. Матричное умножение: Результаты S-блоков объединяются с помощью матрицы MDS (Maximum Distance Separable), которая обеспечивает диффузию — распространение изменений по всему блоку.
4. Сложение с раундовыми ключами: После матричного преобразования данные складываются (по модулю 2³²) с двумя раундовыми ключами.
5. Перестановка: В конце раунда выполняется операция PHT (Pseudo-Hadamard Transform), которая смешивает слова между собой.

Генерация ключей

Процедура расширения ключа в Twofish сложнее, чем в большинстве других шифров. Она включает:

• Разделение ключа: Исходный ключ разбивается на 2 или 4 части (в зависимости от длины ключа), которые используются для вычисления S-блоков.
• Вычисление раундовых ключей: Для каждого из 16 раундов генерируется 2 раундовых ключа (всего 40 ключей, включая предварительное и послeраундовое забеливание).
• Зависимость от ключа: S-блоки вычисляются динамически на основе ключа, что делает шифр устойчивым к атакам, основанным на известных таблицах замен.

Криптоанализ и безопасность

На момент создания Twofish считался одним из самых безопасных шифров. Он устойчив ко всем известным видам атак, включая:

• Линейный криптоанализ: Из-за нелинейности S-блоков и большого числа раундов (16) линейные приближения практически невозможны.
• Дифференциальный криптоанализ: Матрица MDS обеспечивает высокую диффузию, что делает дифференциальные атаки неэффективными.
• Атаки на связанные ключи: Генерация ключей в Twofish спроектирована так, чтобы даже незначительное изменение ключа приводило к полностью различным раундовым ключам.

На 2025 год не опубликовано ни одной практической атаки, которая бы взламывала Twofish быстрее, чем полный перебор ключа (2¹²⁸ для 128-битного ключа). Однако в 2011 году была предложена теоретическая атака на 8-раундовую версию Twofish (из 16) с использованием метода «невозможных дифференциалов», но она не представляет угрозы для полного шифра.

Применение

Twofish широко используется в различных областях, где требуется высокая скорость шифрования и гибкость:

• Программное обеспечение: Входит в состав многих криптографических библиотек (OpenSSL, libtomcrypt, Crypto++). Часто применяется в программах для шифрования дисков (TrueCrypt, VeraCrypt) как альтернатива AES.
• Аппаратные реализации: Благодаря простой структуре сети Фейстеля Twofish может быть эффективно реализован на микроконтроллерах и FPGA.
• Протоколы безопасности: Используется в некоторых VPN-решениях и системах аутентификации.
• Криптовалюты: Некоторые алгоритмы хеширования (например, в криптовалюте Monero) используют модификации Twofish.

Сравнение с AES

Основное преимущество AES — аппаратная поддержка в современных процессорах (инструкции AES-NI), что делает его быстрее на массовых платформах. Twofish, однако, остаётся конкурентоспособным в программных реализациях и на платформах без аппаратного ускорения.

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

• Название «Twofish» происходит от двух рыбок (англ. two fish), что отсылает к предшественнику Blowfish (рыба-шар) и символизирует развитие идеи.
• Twofish не запатентован и доступен для свободного использования без лицензионных отчислений, что способствовало его широкому распространению в открытом ПО.
• В 2019 году исследователи из Университета Квинсленда предложили квантовую атаку на Twofish, но она требует наличия квантового компьютера с миллионами кубитов, что пока недостижимо.

Источники

• Schneier, B., Kelsey, J., Whiting, D., Wagner, D., Hall, C., & Ferguson, N. (1998). Twofish: A 128-Bit Block Cipher. Counterpane Systems.
• NIST. (2000). Report on the Development of the Advanced Encryption Standard (AES).
• Ferguson, N., & Schneier, B. (2003). Practical Cryptography. Wiley.
• Daemen, J., & Rijmen, V. (2002). The Design of Rijndael: AES — The Advanced Encryption Standard. Springer.
• Biham, E., & Keller, N. (2011). Impossible Differential Attack on 8-Round Twofish. Journal of Cryptology.