Interested Article - Blowfish

Blowfish (произносится [бло́уфиш]) — криптографический алгоритм , реализующий блочное симметричное шифрование с переменной длиной ключа. Разработан Брюсом Шнайером в 1993 году . Представляет собой сеть Фейстеля . Выполнен на простых и быстрых операциях: XOR , подстановка, сложение . Является незапатентованным и свободно распространяемым.

История

До появления Blowfish существовавшие алгоритмы были либо запатентованными, либо ненадёжными, а некоторые и вовсе держались в секрете (например, Skipjack ). Алгоритм был разработан в 1993 году Брюсом Шнайером в качестве быстрой и свободной альтернативы устаревшему DES и запатентованному IDEA . По заявлению автора, критериями проектирования Blowfish были :

скорость (шифрование на 32-битных процессорах происходит за 26 тактов);
простота (за счёт использования простых операций, уменьшающих вероятность ошибки реализации алгоритма);
компактность (возможность работать в менее, чем 5 Кбайт памяти);
настраиваемая безопасность (изменяемая длина ключа).

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

Алгоритм состоит из двух частей: расширение ключа и шифрование данных. На этапе расширения ключа исходный ключ (длиной до 448 бит) преобразуется в 18 32-битовых подключей и в 4 32-битных S-блока, содержащих 256 элементов. Общий объём полученных ключей равен $(18+256*4)*32=33344$ $(18+256*4)*32=33344$ бит или $4168$ $4168$ байт .

Параметры

секретный ключ $K$ $K$ (от 32 до 448 бит)
32-битные ключи шифрования $P_{1}-P_{18}$ $P_{{1}}-P_{{18}}$
32-битные таблицы замен $S_{1}-S_{4}$ $S_{{1}}-S_{{4}}$ :

$S_{1}[0],\ S_{1}[1],\ ...,\ S_{1}[255]$ $S_{{1}}[0],\ S_{{1}}[1],\ ...,\ S_{{1}}[255]$

$S_{2}[0],\ S_{2}[1],\ ...,\ S_{2}[255]$ $S_{{2}}[0],\ S_{{2}}[1],\ ...,\ S_{{2}}[255]$

$S_{3}[0],\ S_{3}[1],\ ...,\ S_{3}[255]$ $S_{{3}}[0],\ S_{{3}}[1],\ ...,\ S_{{3}}[255]$

$S_{4}[0],\ S_{4}[1],\ ...,\ S_{4}[255]$ $S_{{4}}[0],\ S_{{4}}[1],\ ...,\ S_{{4}}[255]$

Функция F(x)

Функция F(x) принимает на вход блок размером в 32 бита и проделывает с ним следующие операции :

32-битный блок делится на четыре 8-битных блока $(X_{1},X_{2},X_{3},X_{4})$ $(X_{{1}},X_{{2}},X_{{3}},X_{{4}})$ , каждый из которых является индексом массива таблицы замен $S_{1}-S_{4}$ $S_{{1}}-S_{{4}}$
значения $S_{1}[X_{1}]$ $S_{{1}}[X_{{1}}]$ и $S_{2}[X_{2}]$ $S_{{2}}[X_{{2}}]$ складываются по модулю $2^{32}$ $2^{32}$ , после складываются по модулю $2$ $2$ с $S_{3}[X_{3}]$ $S_{{3}}[X_{{3}}]$ и, наконец, складываются с $S_{4}[X_{4}]$ $S_{{4}}[X_{{4}}]$ по модулю $2^{32}$ $2^{32}$ .
Результат этих операций — значение $F(x)$ $F(x)$ .

 $F(X_{1},X_{2},X_{3},X_{4})=((((S_{1}[X_{1}]\ +\ S_{2}[X_{2}])\mod 2^{32})\oplus \ S_{3}[X_{3}])\ +\ S_{4}[X_{4}])\mod 2^{32}$  $F(X_{{1}},X_{{2}},X_{{3}},X_{{4}})=((((S_{{1}}[X_{{1}}]\ +\ S_{{2}}[X_{{2}}])\mod 2^{{32}})\oplus \ S_{{3}}[X_{{3}}])\ +\ S_{{4}}[X_{{4}}])\mod 2^{{32}}$

Алгоритм шифрования 64-битного блока с известным массивом P и F(x)

Blowfish представляет собой Сеть Фейстеля , состоящую из 16 раундов. Алгоритм шифрования блока $X$ $X$ размером 64 бит выглядит следующим образом :

Разделение входного блока $X$ $X$ на 2 32-битных блока $L_{0},R_{0}$ $L_{{0}},R_{{0}}$
Для $i=1\ ...\ 16:$ $i=1\ ...\ 16:$

$L_{i}\ =\ L_{i-1}\oplus P_{i}$ $L_{i}\ =\ L_{i-1}\oplus P_{i}$

$R_{i}\ =\ R_{i-1}\oplus F(L_{i})$ $R_{i}\ =\ R_{i-1}\oplus F(L_{i})$
После 16 раунда $L_{16}\ ,\ R_{16}$ $L_{{16}}\ ,\ R_{{16}}$ меняются местами:

$R_{16}\ \leftleftarrows \ L_{16}\$ $R_{{16}}\ \leftleftarrows \ L_{{16}}\$

$\ L_{16}\ \leftleftarrows \ R_{16}$ $\ L_{{16}}\ \leftleftarrows \ R_{{16}}$
К получившимся блокам прибавляются $P_{17}$ $P_{{17}}$ и $P_{18}$ $P_{{18}}$

$L_{17}=L_{16}\oplus P_{18}$ $L_{{17}}=L_{{16}}\oplus P_{{18}}$

$R_{17}=R_{16}\oplus P_{17}$ $R_{{17}}=R_{{16}}\oplus P_{{17}}$
Выходной блок $Y$ $Y$ равен конкатенации (объединению) $L_{17}$ $L_{{17}}$ и $R_{17}$ $R_{{17}}$ .

Алгоритм Blowfish

Разделён на 2 этапа :

Подготовительный — формирование ключей шифрования по секретному ключу.
- Инициализация массивов P и S при помощи секретного ключа K
  1. Инициализация $P_{1}-P_{18}$ $P_{1}-P_{{18}}$ фиксированной строкой, состоящей из шестнадцатеричных цифр мантиссы от 3 сентября 2008 на Wayback Machine .
  2. Производится операция XOR над $P_{1}$ $P_1$ с первыми 32 битами ключа $K$ $K$ , над $P_{2}$ $P_2$ со вторыми 32-битами и так далее.
    Если ключ $K$ $K$ короче, то он накладывается циклически.
- Шифрование ключей и таблиц замен
  1. Алгоритм шифрования 64-битного блока, используя инициализированные ключи $P_{1}-P_{18}$ $P_{1}-P_{{18}}$ и таблицу замен $S_{1}-S_{4}$ $S_{1}-S_{4}$ , шифрует 64 битную нулевую (0x0000000000000000) строку. Результат записывается в $P_{1}$ $P_1$ , $P_{2}$ $P_2$ .
  2. $P_{1}$ $P_1$ и $P_{2}$ $P_2$ шифруются изменёнными значениями ключей и таблиц замен. Результат записывается в $P_{3}$ $P_{3}$ и $P_{4}$ $P_{4}$ .
  3. Шифрование продолжается до изменения всех ключей $P_{1}-P_{18}$ $P_{1}-P_{{18}}$ и таблиц замен $S_{1}-S_{4}$ $S_{1}-S_{4}$ .
Шифрование текста полученными ключами и F(x), с предварительным разбиением на блоки по 64 бита. Если невозможно разбить начальный текст точно на блоки по 64 бита, используются различные режимы шифрования для построения сообщения, состоящего из целого числа блоков. Суммарная требуемая память 4168 байт.

Дешифрование происходит аналогично , только $P_{1}-P_{18}$ $P_{1}-P_{{18}}$ применяются в обратном порядке.

Выбор начального значения P-массива и таблицы замен

Нет ничего особенного в цифрах числа пи . Данный выбор заключается в инициализации последовательности, не связанной с алгоритмом, которая могла бы быть сохранена как часть алгоритма или получена при необходимости ( Пи (число) ). Как указывает Шнайер : «Подойдёт любая строка из случайных битов — цифры числа e, RAND-таблицы или биты с выхода генератора случайных чисел.»

Криптостойкость

S-блоки называются слабыми , если существуют такие $i,j,N={1,2,3,4}:S_{N}[i]=S_{N}[j]$ $i,j,N={1,2,3,4}:S_{N}[i]=S_{N}[j]$ . Ключ, генерирующий слабые S-блоки , тоже называется слабым . указал на наличие небольшого класса слабых ключей (генерирующих слабые S-блоки). Вероятность появления слабого S-блока равна $2^{-15}$ $2^{{-15}}$ . Он также рассмотрел упрощенный вариант Blowfish, с известной функцией F(x) и слабым ключом. Для этого варианта требуется $3*2^{2+7*[(t-2)/2]}\approx 2^{3+7*[(t-2)/2]}$ $3*2^{{2+7*[(t-2)/2]}}\approx 2^{{3+7*[(t-2)/2]}}$ выбранных открытых текстов (t — число раундов, а символы [] означают операцию получения целой части числа). Эта атака может быть использована только для алгоритма с $t\leq 7$ $t\leq 7$ . Для $t=7$ $t=7$ требуется $2^{24}$ $2^{24}$ открытых текстов, причём для варианта с известным F(x) и случайным ключом требуется $2^{48}$ $2^{{48}}$ открытых текстов. Но данная атака неэффективна для Blowfish с 16 раундами ( $t=16$ $t=16$ ).

Невозможно заранее определить, является ли ключ слабым. Проводить проверку можно только после генерации ключа.

Криптостойкость можно настраивать за счёт изменения количества раундов шифрования (увеличивая длину массива P) и количества используемых S-блоков . При уменьшении используемых S-блоков возрастает вероятность появления слабых ключей, но уменьшается используемая память. Адаптируя Blowfish для 64-битной архитектуры, можно увеличить количество и размер S-блоков (а следовательно и память для массивов P и S), а также усложнить F(x), причём для алгоритма с такой функцией F(x) невозможны вышеуказанные атаки.

Модификация F(x): на вход подается 64-битный блок, который делится на восемь 8-битных блоков (X1-X8). Результат вычисляется по формуле $F(X1,..,X8)=(\ (\ (S1[X1]\ \boxplus \ S2[X2])\ \oplus \ (S3[X3]\ \boxplus \ S4[X4])\)\ \boxplus \ (\ (S5[X5]\ \boxplus \ S6[X6])\ \oplus (S7[X7]\ \boxplus \ S8[X8])\)\)$ $F(X1,..,X8)=(\ (\ (S1[X1]\ \boxplus \ S2[X2])\ \oplus \ (S3[X3]\ \boxplus \ S4[X4])\)\ \boxplus \ (\ (S5[X5]\ \boxplus \ S6[X6])\ \oplus (S7[X7]\ \boxplus \ S8[X8])\)\)$ , где $\boxplus$ $\boxplus$ — это операция сложения по модулю $2^{32}$ $2^{32}$

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

Известно, что вариант Blowfish с уменьшенным количеством раундов является уязвимым для атак на основе открытых текстов на сравнительно слабых ключах. Реализации Blowfish с 16 раундами шифрования не подвержены подобным атакам. Тем не менее, Брюс Шнайер рекомендовал переход на последователя Blowfish - Twofish .

Применения

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

хеширование паролей
защита электронной почты и файлов
- GnuPG (безопасное хранение и передача)
в линиях связи: связка ElGamal (не запатентован) или RSA (действие патента закончилось в 2000 году) и Blowfish вместо IDEA
- в маршрутизаторе с ключом длиной 144 бита
обеспечение безопасности в протоколах сетевого и транспортного уровня
- SSH (транспортный уровень)
- OpenVPN (создание зашифрованных каналов)

Сравнение с симметричными криптосистемами

Скорость шифрования алгоритма во многом зависит от используемой техники и системы команд. На различных архитектурах один алгоритм может значительно опережать по скорости своих конкурентов, а на другом ситуация может сравняться или даже измениться в прямо противоположную сторону. Более того, программная реализация значительно зависит от используемого компилятора. Использование ассемблерного кода может повысить скорость шифрования. На скорость шифрования влияет время выполнения операций mov, add, xor, причём время выполнения операций увеличивается при обращении к оперативной памяти (для процессоров серии Pentium примерно в 5 раз). Blowfish показывает более высокие результаты при использовании кэша для хранения всех подключей. В этом случае он опережает алгоритмы DES , IDEA . На отставание IDEA влияет операция умножения по модулю $2^{32}+1$ $2^{{32}}+1$ . Скорость Twofish может быть близка по значению к Blowfish за счёт большего шифруемого блока.

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

Примечания

↑ .
↑ .
↑ .
.
Karthikeyan Bhargavan. (неопр.) . ACM CCS 2016 (август 2016). 9 октября 2016 года.
(неопр.) . — «Blowfish should not be used to encrypt files larger than 4Gb in size, but Twofish has no such restrictions.» Дата обращения: 26 января 2018. 21 декабря 2017 года.
(неопр.) . — «For a cipher with an eight-byte block size, you’ll probably repeat a block after about 32 gigabytes of data. This means if you encrypt a single message larger than 32 gigabytes, it’s pretty much a statistical guarantee you’ll have a repeated block. That’s bad. For this reason, we recommend you not use ciphers with eight-byte data blocks if you’re going to be doing bulk encryption. It’s very unlikely you’ll have any problems if you keep your messages under 4 gigabytes in size.» Дата обращения: 27 января 2018. 21 декабря 2017 года.
Tom Gonzalez. (неопр.) . Journal of LATEX Class Files (январь 2007). 18 ноября 2015 года.
Orhun Kara. (неопр.) . FSE 2007 (март 2007). 5 октября 2016 года.
Dahna, McConnachie (неопр.) . Computerworld 3 (27 декабря 2007). — «At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.» Дата обращения: 26 января 2018. 2 декабря 2016 года.
.
.

Литература

Schneier B. (англ.) // : Cambridge Security Workshop Cambridge, U. K., December 9–11,1993 Proceedings / R. J. Anderson — Berlin: , 1994. — P. 191—204. — (; Vol. 809) — ISBN 978-3-540-58108-6 — ISSN ; —
Schneier B. (англ.) : Protocols, Algorithms, and Source Code in C — 2 — Wiley , 1995. — 784 p. — ISBN 978-0-471-12845-8
(англ.) // : Third International Workshop Cambridge, UK, February 21–23 1996 Proceedings / — Berlin: , 1996. — P. 27–32. — (; Vol. 1039) — ISBN 978-3-540-60865-3 — ISSN ; —
(англ.) // : International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004. Proceedings / , — , 2004. — P. 555—570. — 630 p. — ISBN 978-3-540-21935-4 —
6.1. A flexible and adabtive block cipher: Blowfish // (англ.) — 1 — , 2005. — P. 390. — 896 p. — ISBN 978-0-321-26333-9
, (англ.) // — IEEE , 2008. — P. 346—351. — ISBN 978-1-4244-3554-8 , 978-1-4244-3555-5 —
, , (англ.) // — IEEE , 2010. — P. 1—4. — ISBN 978-1-4244-5315-3 —

Ссылки

от 10 июля 2007 на Wayback Machine
от 14 июля 2007 на Wayback Machine
от 27 июня 2010 на Wayback Machine (англ.)

[_917806ba3e43fd37-1] .

[_0fc697232ab5c38f-2] .

[_bcc1b7e52b57916e-3] .

[_240ccdf2543fc3a3-4] .

[5] Karthikeyan Bhargavan. (неопр.) . ACM CCS 2016 (август 2016). 9 октября 2016 года.

[6] (неопр.) . — «Blowfish should not be used to encrypt files larger than 4Gb in size, but Twofish has no such restrictions.» Дата обращения: 26 января 2018. 21 декабря 2017 года.

[7] (неопр.) . — «For a cipher with an eight-byte block size, you’ll probably repeat a block after about 32 gigabytes of data. This means if you encrypt a single message larger than 32 gigabytes, it’s pretty much a statistical guarantee you’ll have a repeated block. That’s bad. For this reason, we recommend you not use ciphers with eight-byte data blocks if you’re going to be doing bulk encryption. It’s very unlikely you’ll have any problems if you keep your messages under 4 gigabytes in size.» Дата обращения: 27 января 2018. 21 декабря 2017 года.

[8] Tom Gonzalez. (неопр.) . Journal of LATEX Class Files (январь 2007). 18 ноября 2015 года.

[9] Orhun Kara. (неопр.) . FSE 2007 (март 2007). 5 октября 2016 года.

[schneier-interview-dec-2007-10] Dahna, McConnachie (неопр.) . Computerworld 3 (27 декабря 2007). — «At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.» Дата обращения: 26 января 2018. 2 декабря 2016 года.

[_a2bdd949342b2bbd-11] .

[_d7af7d3b7817b09e-12] .