Blowfish

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

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

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

Название «Blowfish» (рыба-ёж) было выбрано как отсылка к структуре алгоритма, которая включает в себя сложные перестановки, напоминающие раздувание тела рыбы. Первая версия шифра была представлена на конференции Fast Software Encryption (FSE) в 1993 году, а затем опубликована в трудах конференции.

Алгоритм работы

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

Ключевое расписание

Ключевое расписание в Blowfish преобразует пользовательский ключ (длиной от 32 до 448 бит) в несколько массивов подключей. Всего генерируется 18 32-битных подключей (P-массив) и четыре S-блока (S-box), каждый размером 256 32-битных значений. Эти массивы инициализируются фиксированными значениями, основанными на шестнадцатеричных цифрах числа π (пи). Затем каждый подключ и S-блок последовательно модифицируется с использованием пользовательского ключа и самого шифра.

Процесс расширения ключа является ресурсоёмким и выполняется однократно перед началом шифрования. Это делает Blowfish медленным при частой смене ключей, но быстрым при шифровании больших объёмов данных одним ключом.

Шифрование

Шифрование блока данных (64 бита) выполняется за 16 раундов. Каждый раунд включает:

1. Разделение блока на левую (L) и правую (R) половины (по 32 бита).
2. Операция XOR левой половины с i-м подключём P[i].
3. Применение функции Фейстеля (F) к результату. Функция F делит 32-битное слово на четыре 8-битные части, каждая из которых проходит через соответствующий S-блок (замена по таблице). Результаты четырёх S-блоков складываются по модулю 2^32 (XOR) и комбинируются.
4. Результат функции F XOR-ится с правой половиной.
5. Левая и правая половины меняются местами (кроме последнего раунда).

После 16 раундов выполняется финальная операция XOR левой половины с P[17] и правой половины с P[18], после чего половинки объединяются в выходной блок.

Расшифрование

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

Характеристики

• Размер блока: 64 бита (8 байт).
• Длина ключа: от 32 до 448 бит (с шагом 8 бит).
• Количество раундов: 16.
• Тип: шифр Фейстеля.
• Скорость: высокая на 32-битных процессорах (около 26 тактов на байт на Pentium Pro).
• Память: требует около 4 Кбайт для хранения S-блоков и P-массива.

Криптостойкость и уязвимости

На протяжении многих лет Blowfish считался стойким шифром. Однако со временем были выявлены некоторые теоретические и практические ограничения:

• Атака на слабые ключи: Для некоторых ключей S-блоки могут генерировать повторяющиеся значения, что снижает стойкость. Однако вероятность такого события крайне мала.
• Атака с известным открытым текстом: В 1997 году была предложена атака, использующая структуру S-блоков, но она требовала большого объёма памяти и не была практичной.
• Атака по сторонним каналам: Как и многие алгоритмы, Blowfish уязвим для атак по времени выполнения и атак на кэш-память, если реализация не защищена.
• Малый размер блока (64 бита): В современных условиях (большие объёмы данных, высокая скорость сетей) 64-битный блок подвержен атакам типа «день рождения» при шифровании более 2^32 блоков (около 32 Гбайт данных). Это делает Blowfish непригодным для шифрования очень больших объёмов информации без смены ключа.

Применение

Blowfish широко использовался в 1990-х и 2000-х годах в различных программных продуктах и протоколах:

• Парольные менеджеры: Например, в программе KeePass (в первых версиях) Blowfish использовался для шифрования базы паролей.
• VPN и туннелирование: В протоколах PPTP и некоторых реализациях IPsec.
• Шифрование дисков: В утилитах, таких как bcrypt (хэширование паролей), используется модифицированная версия Blowfish.
• Встраиваемые системы: Благодаря небольшому размеру кода и высокой скорости, Blowfish применялся в микроконтроллерах и смарт-картах.

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

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

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

Источники

• Schneier, B. (1994). «Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)». Fast Software Encryption. Lecture Notes in Computer Science. 809. Springer.
• Schneier, B. (1996). «Applied Cryptography: Protocols, Algorithms, and Source Code in C». John Wiley & Sons.
• NIST. (1999). «FIPS PUB 197: Advanced Encryption Standard (AES)».
• Спецификация алгоритма Blowfish на официальном сайте Брюса Шнайера.