Blowfish — это блочный шифр с симметричным ключом , разработанный в 1993 году Брюсом Шнайером и включенный во многие наборы шифров и продукты шифрования. Blowfish обеспечивает хорошую скорость шифрования в программном обеспечении, и на сегодняшний день не найдено эффективного криптоанализа . Однако теперь расширенному стандарту шифрования (AES) уделяется больше внимания, и Шнайер рекомендует Twofish для современных приложений. [3]
Шнайер разработал Blowfish как алгоритм общего назначения, задуманный как альтернатива устаревшему DES и свободный от проблем и ограничений, связанных с другими алгоритмами. На момент выпуска Blowfish многие другие разработки были запатентованы, обременены патентами или составляли коммерческую или государственную тайну. Шнайер заявил, что «Blowfish не имеет патента и останется таковым во всех странах. Алгоритм настоящим размещен в общественном достоянии и может свободно использоваться кем угодно». [4]
Примечательные особенности конструкции включают зависящие от ключа S-блоки и очень сложную схему клавиш .
Blowfish имеет размер блока 64 бита и переменную длину ключа от 32 до 448 бит. [4] Это 16-раундовый шифр Фейстеля , в котором используются большие зависящие от ключа S-блоки . По структуре напоминает CAST-128 , в котором используются фиксированные S-блоки.
На соседней диаграмме показана процедура шифрования Blowfish. Каждая строка представляет 32 бита. Существует пять массивов подключей: один P-массив с 18 элементами (обозначенный на диаграмме как K, чтобы избежать путаницы с открытым текстом) и четыре S-блока с 256 элементами (S0, S1, S2 и S3).
Каждый раунд r состоит из 4 действий:
F-функция разделяет 32-битный входной сигнал на четыре 8-битных четверти и использует четверти в качестве входных данных для S-блоков. S-блоки принимают 8-битный ввод и производят 32-битный вывод. Выходные данные суммируются по модулю 2 32 и подвергаются операции XOR для получения окончательного 32-битного результата (см. изображение в правом верхнем углу). [5]
После 16-го раунда отмените последний обмен и выполните XOR L с K18 и R с K17 (выходное отбеливание).
Расшифровка точно такая же, как шифрование, за исключением того, что P1, P2,..., P18 используются в обратном порядке. Это не так очевидно, поскольку xor коммутативен и ассоциативен. Распространенным заблуждением является использование обратного порядка шифрования в качестве алгоритма дешифрования (т.е. сначала выполняется XOR P17 и P18 к блоку зашифрованного текста, а затем использование P-записей в обратном порядке).
Расписание ключей Blowfish начинается с инициализации P-массива и S-блоков значениями, полученными из шестнадцатеричных цифр числа pi , которые не содержат очевидного шаблона ( ничего не вижу в моем рукаве ). Затем секретный ключ побайтно обрабатывается, при необходимости циклически повторяется, и выполняется операция XOR со всеми P-записями по порядку. Затем 64-битный блок с нулями шифруется с помощью алгоритма в его нынешнем виде. Результирующий зашифрованный текст заменяет P 1 и P 2 . Затем тот же зашифрованный текст снова шифруется с использованием новых подключей, и новый зашифрованный текст заменяет P 3 и P 4 . Это продолжается, заменяя весь P-массив и все записи S-блока. В общей сложности алгоритм шифрования Blowfish будет запущен 521 раз для генерации всех подразделов — обрабатывается около 4 КБ данных.
Поскольку длина P-массива составляет 576 бит, а ключевые байты подвергаются операции XOR через все эти 576 бит во время инициализации, многие реализации поддерживают размеры ключей до 576 бит. Причиной этого является несоответствие между исходным описанием Blowfish, в котором используются 448-битные ключи, и его эталонной реализацией, в которой используются 576-битные ключи. Тестовые векторы для проверки сторонних реализаций также были созданы с 576-битными ключами. На вопрос, какая версия Blowfish правильная, Брюс Шнайер ответил: «Тестовые векторы следует использовать для определения единственного настоящего Blowfish».
Другое мнение состоит в том, что ограничение в 448 бит существует для того, чтобы гарантировать, что каждый бит каждого подраздела зависит от каждого бита ключа, [4] поскольку последние четыре значения P-массива не влияют на каждый бит зашифрованного текста. Этот момент следует учитывать для реализаций с другим количеством раундов, поскольку хотя он и повышает защищенность от исчерпывающей атаки, но ослабляет безопасность, гарантируемую алгоритмом. А учитывая медленную инициализацию шифра при каждой смене ключа, ему предоставляется естественная защита от атак методом перебора, что на самом деле не оправдывает размеры ключей, превышающие 448 бит.
uint32_t P [ 18 ]; uint32_t S [ 4 ][ 256 ]; uint32_t f ( uint32_t x ) { uint32_t h = S [ 0 ] [ x >> 24 ] + S [ 1 ] [ x >> 16 & 0xff ]; return ( h ^ S [ 2 ] [ x >> 8 & 0xff ] ) + S [ 3 ] [ x & 0xff ]; } void Blowfish_encrypt ( uint32_t * L , uint32_t * R ) { for ( short r = 0 ; r < 16 ; r ++ ) { * L = * L ^ P [ r ]; * р знак равно ж ( * L ) ^ * р ; поменять местами ( Л , Р ); } Обмен ( L , R ); * Р = * Р ^ П [ 16 ]; * Л = * Л ^ П [ 17 ]; } void Blowfish_decrypt ( uint32_t * L , uint32_t * R ) { for ( short r = 17 ; r > 1 ; r -- ) { * L = * L ^ P [ r ]; * р знак равно ж ( * L ) ^ * р ; поменять местами ( Л , Р ); } Обмен ( L , R ); * Р = * Р ^ П [ 1 ]; * Л = * Л ^ П [ 0 ]; } // ... // инициализация P-массива и S-блоков значениями, полученными из числа pi; в примере опущен // ... { /* инициализировать блок P с ключом*/ uint32_t k ; для ( коротко я знак равно 0 , п знак равно 0 ; я < 18 ; я ++ ) { k = 0x00 ; для ( короткий j знак равно 0 ; j < 4 ; j ++ ) { k = ( k << 8 ) | ( uint8_t ) клавиша [ p ]; р = ( р + 1 ) % key_len ; } п [ я ] ^= k ; } /* расширение ключа Blowfish (521 итерация) */ uint32_t l = 0x00 , r = 0x00 ; for ( коротко я знак равно 0 ; я < 18 ; я += 2 ) { blowfish_encrypt ( & l , & r ); п [ я ] знак равно л ; п [ я + 1 ] знак равно р ; } for ( short i = 0 ; i < 4 ; i ++ ) { for ( short j = 0 ; j < 256 ; j += 2 ) { blowfish_encrypt ( & l , & r ); S [ я ][ j ] знак равно л ; S [ я ][ j + 1 ] знак равно р ; } } } Blowfish — быстрый блочный шифр , за исключением случаев смены ключей. Каждый новый ключ требует предварительной обработки, эквивалентной шифрованию около 4 килобайт текста, что очень медленно по сравнению с другими блочными шифрами. Это предотвращает его использование в некоторых приложениях, но не является проблемой в других.
Blowfish должен быть инициализирован с помощью ключа. Хорошей практикой является хеширование этого ключа. Чтобы предотвратить хеширование этого ключа с помощью слишком короткой хеш-функции (SHA-160, SHA-256), в 2005 году появилась хеш-функция, основанная на MD2, разработанная Роном Ривестом, только для паролей Blowfish. Эта функция хеширует ключ или пароль в ключ длиной 56 или 72 байта для Blowfish или 528 байт для Blowfish II. [6]
В одном приложении медленная смена ключей Blowfish на самом деле является преимуществом: метод хеширования пароля (crypt $2, т.е. bcrypt), используемый в OpenBSD , использует алгоритм, полученный из Blowfish, который использует расписание медленного ключа; Идея состоит в том, что требуемые дополнительные вычислительные усилия обеспечивают защиту от атак по словарю . См. растяжку клавиш .
Blowfish занимает чуть более 4 килобайт оперативной памяти . Это ограничение не является проблемой даже для старых настольных и портативных компьютеров , хотя оно и препятствует использованию в самых маленьких встроенных системах , таких как первые смарт-карты .
Blowfish был одним из первых безопасных блочных шифров, не подпадающих под действие каких-либо патентов и поэтому свободно доступных для использования каждым. Это преимущество способствовало его популярности в криптографическом программном обеспечении.
bcrypt — это функция хеширования паролей , которая в сочетании с переменным количеством итераций («стоимость работы») использует дорогостоящую фазу установки ключей Blowfish для увеличения рабочей нагрузки и продолжительности хэш-вычислений, что еще больше снижает угрозы от атак методом перебора.
bcrypt — это также название кроссплатформенной утилиты шифрования файлов, разработанной в 2002 году и реализующей Blowfish. [7] [8] [9] [10]
Использование Blowfish 64-битного размера блока (в отличие, например, от 128-битного размера блока AES) делает его уязвимым для атак на день рождения , особенно в таких контекстах, как HTTPS . В 2016 году атака SWEET32 продемонстрировала, как использовать атаки «дни рождения» для восстановления открытого текста (т. е. расшифровки зашифрованного текста) на основе шифров с размером блока 64 бита. [11] Проект GnuPG рекомендует не использовать Blowfish для шифрования файлов размером более 4 ГБ [12] из-за небольшого размера блока. [13]
Известно, что вариант Blowfish с сокращенным циклом уязвим к атакам с известным открытым текстом на рефлексивно слабые ключи. Реализации Blowfish используют 16 раундов шифрования и не подвержены этой атаке. [14] [15]
Брюс Шнайер рекомендовал перейти на своего преемника Blowfish, Twofish . [3]
Blowfish II был выпущен в 2005 году и разработан не Брюсом Шнайером. Он имеет точно такой же дизайн, но содержит в два раза больше таблиц S и использует 64-битные целые числа вместо 32-битных. Он больше не работает с 64-битными блоками, а работает со 128-битными блоками, такими как AES. [16]
Однако на данный момент я поражен, что его все еще используют. Если люди спросят, я рекомендую вместо этого Twofish.
Blowfish не следует использовать для шифрования файлов размером более 4 ГБ, но у Twofish таких ограничений нет.
Для шифра с размером блока в восемь байт вы, вероятно, повторите блок примерно после 32 гигабайт данных. Это означает, что если вы зашифруете одно сообщение размером более 32 гигабайт, это практически статистическая гарантия того, что вы получите повторную блокировку. Плохо. По этой причине мы рекомендуем вам не использовать шифры с восьмибайтовыми блоками данных, если вы собираетесь выполнять массовое шифрование. Маловероятно, что у вас возникнут какие-либо проблемы, если размер ваших сообщений не превышает 4 гигабайт.
