Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для использования в других целях, см Blowfish (значения) .
Blowfish
Общий
ДизайнеровБрюс Шнайер
Впервые опубликовано1993 г.
ПреемникиTwofish
Деталь шифра
Ключевые размеры32–448 бит
Размеры блоков64 бит
СтруктураСеть Фейстеля
Раундов16
Лучший публичный криптоанализ
Четыре раунда Blowfish подвержены дифференциальной атаке второго порядка (Rijmen, 1997); [1] для класса слабых ключей 14 раундов Blowfish можно отличить от псевдослучайной перестановки (Vaudenay, 1996).

Blowfish - это блочный шифр с симметричным ключом , разработанный в 1993 году Брюсом Шнайером и включенный во многие комплекты шифров и продукты для шифрования. Blowfish обеспечивает хорошую скорость шифрования в программном обеспечении, и на сегодняшний день не было найдено никакого эффективного криптоанализа . Однако теперь расширенному стандарту шифрования (AES) уделяется больше внимания, и Шнайер рекомендует Twofish для современных приложений. [2]

Шнайер разработал Blowfish как алгоритм общего назначения, задуманный как альтернативу устаревшему DES и свободный от проблем и ограничений, связанных с другими алгоритмами. На момент выпуска Blowfish многие другие разработки были патентами, коммерческими или государственными секретами. Шнайер заявил, что «Blowfish не запатентован и останется таковым во всех странах. Таким образом, алгоритм становится общественным достоянием и может свободно использоваться кем угодно». [3]

Примечательные особенности дизайна включают зависящие от клавиш S-блоки и очень сложную схему расположения клавиш .

Алгоритм [ править ]

Blowfish имеет 64-битный размер блока и переменную длину ключа от 32 бит до 448 бит. [3] Это 16- этапный шифр Фейстеля, в котором используются большие зависящие от ключа S-блоки . По структуре он напоминает CAST-128 , в котором используются фиксированные S-блоки.

Структура Фейстеля Blowfish

На следующей диаграмме показана процедура шифрования Blowfish. Каждая строка представляет 32 бита. Существует пять массивов подключей: один P-массив из 18 элементов (обозначен на схеме как K, чтобы избежать путаницы с открытым текстом) и четыре S-блока из 256 элементов (S0, S1, S2 и S3).

Каждый раунд r состоит из 4 действий:

Действие 1Выполните XOR левой половины (L) данных с r- й записью P-массива
Действие 2Используйте данные XOR в качестве входных для F-функции Blowfish.
Действие 3Выполните XOR выхода F-функции с правой половиной (R) данных
Действие 4Поменять местами L и R

F-функция разделяет 32-битный ввод на четыре восьмибитовых четверти и использует четверти как ввод для S-блоков. S-блоки принимают 8-битный ввод и производят 32-битный вывод. Выходы складываются по модулю 2 32 и подвергаются операции XOR для получения окончательного 32-битного вывода (см. Изображение в правом верхнем углу). [4]

После 16-го раунда отмените последний обмен и выполните XOR L с K18 и R с K17 (выходное отбеливание).

Расшифровка точно такая же, как и шифрование, за исключением того, что P1, P2, ..., P18 используются в обратном порядке. Это не так очевидно, потому что xor коммутативен и ассоциативен. Распространенным заблуждением является использование обратного порядка шифрования в качестве алгоритма дешифрования (то есть сначала XORing P17 и P18 для блока зашифрованного текста, а затем использование P-записей в обратном порядке).

Ключевое расписание Blowfish начинается с инициализации P-массива и S-блоков значениями, полученными из шестнадцатеричных цифр числа пи , которые не содержат очевидного шаблона ( ничего не вижу в моем номере рукава ). Затем секретный ключ побайтово, циклически повторяя ключ, если необходимо, подвергается операции 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 бит присутствует, чтобы гарантировать, что каждый бит каждого подключа зависит от каждого бита ключа [3], поскольку последние четыре значения P-массива не влияют на каждый бит зашифрованного текста. Этот момент следует принимать во внимание для реализаций с другим числом раундов, поскольку, хотя он увеличивает безопасность от исчерпывающей атаки, он ослабляет безопасность, гарантированную алгоритмом. А учитывая медленную инициализацию шифра при каждой смене ключа, ему предоставляется естественная защита от атак грубой силы, что на самом деле не оправдывает размеры ключей, превышающие 448 бит.

Blowfish в псевдокоде [ править ]

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  encrypt  ( uint32_t  &  L ,  uint32_t  &  R )  {  для  ( int  i = 0  ;  i < 16  ;  i  + =  2 )  {  L  ^ =  P [ i ];  R  ^ =  f ( L );  R  ^ =  P [ i + 1 ];  L  ^ =  f ( R );  }  L  ^ =  P[ 16 ];  R  ^ =  P [ 17 ];  своп  ( L ,  R ); }void  decrypt  ( uint32_t  &  L ,  uint32_t  &  R )  {  для  ( int  i = 16  ;  i  >  0  ;  i  - =  2 )  {  L  ^ =  P [ i + 1 ];  R  ^ =  f ( L );  R  ^ =  P [ i ];  L  ^ =  f ( R );  }  L  ^ =  P[ 1 ];  R  ^ =  P [ 0 ];  своп  ( L ,  R ); } // ...  // инициализация P-массива и S-боксов значениями, полученными из pi; опущено в примере  // ... {  for  ( int  i = 0  ;  i < 18  ;  ++ i )  P [ i ]  ^ =  key [ i  %  keylen ];  uint32_t  L  =  0 ,  R  =  0 ;  для  ( int  i = 0  ;  i < 18  ;  i + = 2)  {  encrypt  ( L ,  R );  P [ i ]  =  L ;  P [ i + 1 ]  =  R ;  }  for  ( int  i = 0  ;  i < 4  ;  ++ i )  for  ( int  j = 0  ;  j < 256 ;  j + = 2 )  {  encrypt  ( L , R );  S [ i ] [ j ]  =  L ;  S [ i ] [ j + 1 ]  =  R ;  } }

Blowfish на практике [ править ]

Blowfish - это быстрый блочный шифр , кроме случаев смены ключей. Каждый новый ключ требует предварительной обработки, эквивалентной шифрованию около 4 килобайт текста, что очень медленно по сравнению с другими блочными шифрами. Это предотвращает его использование в некоторых приложениях, но не является проблемой для других.

В одном приложении медленное изменение ключа Blowfish на самом деле является преимуществом: метод хеширования пароля (crypt $ 2, т.е. bcrypt), используемый в OpenBSD, использует алгоритм, производный от Blowfish, который использует расписание медленных ключей; идея состоит в том, что требуемые дополнительные вычислительные усилия обеспечивают защиту от атак по словарю . См. Растяжку клавиш .

Иглобрюхие имеет объем памяти , чуть более 4 килобайт оперативной памяти . Это ограничение не является проблемой даже для старых настольных и портативных компьютеров , хотя оно препятствует использованию в самых маленьких встроенных системах, таких как ранние смарт-карты .

Blowfish был одним из первых безопасных блочных шифров, не защищенных какими-либо патентами и, следовательно, свободно доступными для использования всеми. Это преимущество способствовало его популярности в криптографическом программном обеспечении.

bcrypt - это функция хеширования паролей, которая в сочетании с переменным числом итераций («стоимость» работы) использует дорогостоящую фазу настройки ключей Blowfish для увеличения рабочей нагрузки и продолжительности хеш-вычислений, дополнительно уменьшая угрозы от атак грубой силы.

bcrypt - это также название кроссплатформенной утилиты для шифрования файлов, разработанной в 2002 году и реализующей Blowfish. [5] [6] [7] [8]

Слабость и преемники [ править ]

Использование Blowfish 64-битного размера блока (в отличие от, например, 128-битного размера блока AES) делает его уязвимым для атак по случаю дня рождения , особенно в таких контекстах, как HTTPS . В 2016 году атака SWEET32 продемонстрировала, как использовать атаки по случаю дня рождения для восстановления открытого текста (т. Е. Дешифрования зашифрованного текста) для шифров с размером блока 64-бит. [9] Проект GnuPG не рекомендует использовать Blowfish для шифрования файлов размером более 4 ГБ [10] из-за небольшого размера блока. [11]

Вариант Blowfish с уменьшенным числом раундов известен своей восприимчивостью к атакам с использованием известного открытого текста на рефлексивно слабые ключи. Реализации Blowfish используют 16 раундов шифрования и не подвержены этой атаке. [12] [13] Тем не менее Брюс Шнайер рекомендовал перейти на своего преемника Blowfish, Twofish . [2]

См. Также [ править ]

  • Три рыбы
  • Макгаффин

Ссылки [ править ]

  1. ^ Винсент Риджмен (1997). «Криптоанализ и разработка итерированных блочных шифров» ( PostScript ) . Кандидатская диссертация . Архивировано 08 мая 2013 года.
  2. ^ a b Дана, МакКонначи (2007-12-27). «Брюс Всемогущий: Шнайер проповедует безопасность верным Linux» . Компьютерный мир . п. 3. Архивировано 02 декабря 2016 года . Проверено 26 января 2018 . На данный момент, однако, я удивлен, что он все еще используется. Если люди спрашивают, я рекомендую Twofish.
  3. ^ a b c Брюс Шнайер (1993). «Описание нового ключа переменной длины, 64-битного блочного шифра (Blowfish)» . Быстрое программное шифрование, Труды Кембриджского семинара по безопасности . Springer-Verlag : 191–204. Архивировано 26 января 2014 года.
  4. ^ "Криптография: Описание нового ключа переменной длины, 64-битного блочного шифра (Blowfish) - Шнайер о безопасности" . www.schneier.com . Архивировано 4 марта 2016 года . Проверено 31 декабря 2015 .
  5. ^ "Bcrypt - шифрование файлов Blowfish" Архивировано 29 августа 2015 г. надомашней странице программы шифрования файлов bcrypt Wayback Machine (bcrypt.sourceforge.net)
  6. ^ "Бесплатная загрузка bcrypt - whodunnit.tools.bcrypt" . bcrypt463065.android.informer.com . Архивировано 4 марта 2016 года . Проверено 7 мая 2018 .
  7. ^ "Пакет T2 - ствол - bcrypt - Утилита для шифрования файлов" . www.t2-project.org . Архивировано 21 апреля 2017 года . Проверено 7 мая 2018 .
  8. ^ "Oracle GoldenGate の ラ イ セ ン ス" . docs.oracle.com . Архивировано 27 октября 2017 года . Проверено 7 мая 2018 .
  9. ^ Картикеян Bhargavan; Гаэтан Леурент (август 2016 г.). «О практической (не) безопасности 64-битных блочных шифров - коллизионные атаки по HTTP через TLS и OpenVPN» . ACM CCS 2016. Архивировано 9 октября 2016 года .
  10. ^ «Часто задаваемые вопросы по GnuPG» . Архивировано 21 декабря 2017 года . Проверено 26 января 2018 . Blowfish не следует использовать для шифрования файлов размером более 4 ГБ, но Twofish не имеет таких ограничений.
  11. ^ «Часто задаваемые вопросы по GnuPG» . Архивировано 21 декабря 2017 года . Проверено 27 января 2018 . Для шифра с размером блока восемь байтов вы, вероятно, повторите блок примерно после 32 гигабайт данных. Это означает, что если вы зашифруете одно сообщение размером более 32 гигабайт, это в значительной степени статистическая гарантия того, что у вас будет повторяющийся блок. Плохо. По этой причине мы не рекомендуем использовать шифры с восьмибайтовыми блоками данных, если вы собираетесь выполнять массовое шифрование. Маловероятно, что у вас возникнут проблемы, если размер ваших сообщений будет меньше 4 гигабайт.
  12. ↑ Том Гонсалес (январь 2007 г.). «Атака отражения на Blowfish» (PDF) . Журнал файлов классов LATEX. Архивировано из оригинального (PDF) 18 ноября 2015 года . Проверено 17 ноября 2015 .
  13. ^ Orhun Кара & Cevat манапа (март 2007). «Новый класс слабых ключей для Blowfish» (PDF) . FSE 2007. Архивировано (PDF) из оригинала 05.10.2016.

Внешние ссылки [ править ]

  • Брюс Шнайер. «Алгоритм шифрования Blowfish» .
  • Брюс Шнайер. «Продукты, в которых используется Blowfish» .
  • «Стандартное название криптографического алгоритма: Blowfish» .