Блочный шифр Blowfish¶

Blowfish — это симметричный блочный шифр, разработанный в 1993 году американским криптографом Брюсом Шнайером. Относится к классу блочных шифров с переменной длиной ключа (от 32 до 448 бит) и фиксированным размером блока в 64 бита. Blowfish был создан как быстрая, свободная и безопасная альтернатива существовавшим на тот момент алгоритмам, таким как DES, и не был запатентован, что способствовало его широкому распространению в программном обеспечении.

¶История

Разработка Blowfish была завершена в 1993 году. Основной целью Шнайера было создание алгоритма, который удовлетворял бы нескольким требованиям: высокая скорость шифрования на 32-битных микропроцессорах, компактный размер кода (менее 5 килобайт), простота реализации и отсутствие патентных ограничений. Название «Blowfish» (рыба-ёж) было выбрано как аллюзия на процесс «раздувания» ключа (key expansion) — одну из ключевых стадий алгоритма.

Первоначально шифр был опубликован в журнале Dr. Dobb’s Journal, а затем включён в книгу Шнайера «Applied Cryptography». Благодаря открытости и бесплатности, Blowfish быстро стал популярным в криптографических библиотеках и коммерческих продуктах, особенно в тех, где не требовалась высокая пропускная способность при шифровании больших объёмов данных.

¶Алгоритм

Blowfish является шифром Фейстеля, что означает, что он использует одинаковую структуру для шифрования и дешифрования, с той лишь разницей, что раундовые подключи применяются в обратном порядке. Алгоритм состоит из двух основных частей: расширения ключа (key expansion) и процесса шифрования данных.

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

На этапе расширения ключа из исходного ключа пользователя генерируется массив из 18 32-битных подключей (P-блоков) и четыре S-блока (substitution boxes), каждый размером 256 32-битных значений. Изначально P-блоки и S-блоки заполняются фиксированными значениями, полученными из дробной части числа π. Затем исходный ключ (длиной до 448 бит) побитово XOR-ится с первыми P-блоками. После этого выполняется итеративный процесс: зашифровывается нулевой блок данных (64 бита) с использованием текущих подключей, и результат заменяет P1 и P2. Процесс повторяется, последовательно заменяя все P-блоки и S-блоки, пока не будет сгенерирован полный набор подключей. Этот этап является ресурсоёмким, но выполняется однократно при инициализации шифра.

¶Шифрование

Процесс шифрования 64-битного блока данных состоит из 16 раундов. Каждый раунд включает следующие операции:

1. Разделение блока на левую (L) и правую (R) половины по 32 бита.
2. Выполнение функции F над левой половиной: L XOR-ится с P-блоком текущего раунда, затем результат делится на четыре 8-битных части, каждая из которых проходит через соответствующий S-блок (S1, S2, S3, S4). Полученные 32-битные значения складываются по модулю 2^32 и XOR-ятся.
3. Результат функции F XOR-ится с правой половиной R.
4. Левая и правая половины меняются местами (кроме последнего раунда).

После 16 раундов выполняется финальное XOR-сложение с P17 и P18, и блоки объединяются в 64-битный шифротекст.

¶Ключевые характеристики

• Размер блока: 64 бита. Это является основным ограничением шифра, так как при шифровании больших объёмов данных (более 2^32 блоков) возникает риск коллизий из-за дня рождения.
• Длина ключа: от 32 до 448 бит с шагом в 8 бит. Переменная длина ключа позволяет адаптировать шифр под требуемый уровень безопасности.
• Скорость: Blowfish демонстрирует высокую скорость шифрования на 32-битных процессорах, особенно при использовании таблиц S-блоков, которые помещаются в кэш. Однако на 64-битных архитектурах он уступает более современным шифрам, таким как Twofish или AES.
• Память: требует около 4 килобайт для хранения S-блоков и P-блоков, что делает его подходящим для встраиваемых систем.

¶Применение

Благодаря своей скорости и открытости, Blowfish широко применялся в различных областях:

• Программное обеспечение для шифрования: использовался в таких утилитах, как bcrypt (алгоритм хеширования паролей, основанный на Blowfish), GnuPG (в ранних версиях), а также в некоторых VPN-решениях.
• Встраиваемые системы: благодаря компактному коду и низким требованиям к памяти, Blowfish применялся в маршрутизаторах, смарт-картах и других устройствах с ограниченными ресурсами.
• Протоколы безопасности: входил в состав некоторых реализаций протокола SSH (Secure Shell) и IPsec, хотя со временем был вытеснен более современными алгоритмами.

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

На протяжении многих лет Blowfish считался устойчивым к известным атакам, включая дифференциальный и линейный криптоанализ. Однако его главный недостаток — 64-битный размер блока. В 2016 году исследователи продемонстрировали, что при шифровании больших объёмов данных (порядка 32 гигабайт) с использованием одного ключа вероятность коллизии блоков становится значительной, что может привести к утечке информации. Это ограничение делает Blowfish непригодным для шифрования современных больших потоков данных.

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

¶Сравнение с другими шифрами

Blowfish стал предшественником более совершенного шифра Twofish, разработанного тем же Брюсом Шнайером в 1998 году для участия в конкурсе AES. Twofish использует 128-битный блок и поддерживает ключи длиной до 256 бит, что делает его более устойчивым к атакам на основе коллизий. Другим популярным преемником является AES (Rijndael), который стал стандартом шифрования в США и многих других странах. В отличие от Blowfish, AES имеет фиксированный размер блока 128 бит и оптимизирован для аппаратной реализации.

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

• Алгоритм bcrypt, широко используемый для хеширования паролей, основан именно на Blowfish. Он модифицирует процесс расширения ключа, делая его намеренно медленным для защиты от атак перебором.
• Blowfish был одним из первых шифров, который был опубликован в открытом доступе без каких-либо патентных ограничений, что способствовало его быстрому внедрению в сообществе разработчиков.
• Несмотря на возраст, Blowfish до сих пор используется в некоторых старых системах и протоколах, хотя для новых проектов рекомендуется использовать шифры с 128-битным блоком, такие как AES или ChaCha20.

¶Источники

• Bruce Schneier. «Applied Cryptography: Protocols, Algorithms, and Source Code in C», 2nd Edition, 1996.
• Bruce Schneier. «Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)», Dr. Dobb’s Journal, 1994.
• NIST. «Recommendation for Block Cipher Modes of Operation», SP 800-38A, 2001.
• K. Bhargavan, G. Leurent. «On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN», 2016.