Эта статья является кандидатом в добротные статьи

Blowfish

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Blowfish
Создатель:

Брюс Шнайер

Создан:

1993 г.

Опубликован:

1993 г.

Размер ключа:

от 32 до 448 бит

Размер блока:

64 бит

Число раундов:

16

Тип:

Сеть Фейстеля

Blowfish (произносится [бло́уфиш]) — криптографический алгоритм, реализующий блочное симметричное шифрование с переменной длиной ключа.

Разработан Брюсом Шнайером в 1993 году. Представляет собой сеть Фейстеля[1][2]. Выполнен на простых и быстрых операциях: XOR, подстановка, сложение[2]. Является незапатентованным и свободно распространяемым.

История[править | править вики-текст]

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

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

Описание алгоритма[править | править вики-текст]

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

Параметры[править | править вики-текст]

  • секретный ключ K (от 32 до 448 бит)
  • 32-битные ключи шифрования P_{1} - P_{18}
  • 32-битные таблицы замен S_{1} - S_{4}:
    S_{1}[0],\ S_{1}[1],\ ...,\ S_{1}[255]
    S_{2}[0],\ S_{2}[1],\ ...,\ S_{2}[255]
    S_{3}[0],\ S_{3}[1],\ ...,\ S_{3}[255]
    S_{4}[0],\ S_{4}[1],\ ...,\ S_{4}[255]

Функция F(x)[править | править вики-текст]

Функция F(x) в Blowfish

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

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

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

Сеть Фейстеля при зашифровании

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

  1. Разделение входного блока X на 2 32-битных блока L_{0}, R_{0}
  2. Для i = 1\ ...\ 16:
    R_i\ =\ L_{i-1} \oplus P_{i+1}
    L_i\ =\ R_{i-1} \oplus F(R_i)
  3. После 16 раунда L_{16}\ ,\ R_{16} меняются местами:
    R_{16}\ \leftleftarrows\ L_{16}\
    \ L_{16}\ \leftleftarrows\ R_{16}
  4. К получившимся блокам прибавляются P_{17} и P_{18}
    L_{17} = L_{16} \oplus P_{18}
    R_{17} = R_{16} \oplus P_{17}
  5. Выходной блок Y равен конкатенации (объединению) L_{17} и R_{17}.

Алгоритм Blowfish[править | править вики-текст]

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

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

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

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

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

Криптостойкость[править | править вики-текст]

S-блоки называются слабыми, если существуют такие i, j, N = {1,2,3,4} : S_N[i] = S_N[j]. Ключ, генерирующий слабые S-блоки, тоже называется слабым. Серж Воденэ указал[4] на наличие небольшого класса слабых ключей (генерирующих слабые S-блоки). Вероятность появления слабого S-блока равна 2^{-15}. Он также рассмотрел упрощенный вариант Blowfish, с известной функцией F(x) и слабым ключом. Для этого варианта требуется 3*2^{2+7*[(t-2)/2]}\approx2^{3+7*[(t-2)/2]} выбранных открытых текстов (t — число раундов, а символы [] означают операцию получения целой части числа). Эта атака может быть использована только для алгоритма с t \le 7. Для t = 7 требуется 2^{24} открытых текстов, причём для варианта с известным F(x) и случайным ключом требуется 2^{48} открытых текстов. Но данная атака неэффективна для Blowfish с 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])\ )\ ), где \boxplus — это операция сложения по модулю 2^{32}
На сегодняшний день (ноябрь 2008) не существует атак, выполняемых за разумное время. Успешные атаки возможны только из-за ошибок реализации[1].

Применения[править | править вики-текст]

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

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

Сравнение с симметричными криптосистемами[править | править вики-текст]

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

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

Источники[править | править вики-текст]

  • Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  • Serge Vaudenay A New Family of Block Ciphers. — Springer-Verlag, 1992. — P. 27 — 32.
  • Meyers, R.K., Desoky, A.H. An Implementation of the Blowfish Cryptosystem. — Signal Processing and Information Technology, 2008. ISSPIT 2008. IEEE International Symposium on, 16-19 Dec. 2008. — P. 346 - 351.
  • Tingyuan Nie, Chuanwang Song, Xulong Zhi Performance Evaluation of DES and Blowfish Algorithms. — Signal Processing and IBiomedical Engineering and Computer Science (ICBECS), 2010 International Conference on, 23-25 April 2010. — P. 1 - 4.
  • Christian Cachin, Jan Camenisch Advances in Cryptology - EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic. — Interlaken, Switzerland: Springer Science & Business Media, 2004. — С. 557. — 628 с.
  • P. K. Yuen Practical Cryptology and Web Security. — Pearson Education. — 2006. — С. 390. — 879 с.

Примечания[править | править вики-текст]

  1. 1 2 3 4 5 6 7 Bruce Schneier Applied Cryptography: Protocols, Algorithms, and Source Code in C. — Second Edition. — John Wiley & Sons, 1996. — ISBN 0-471-11709-9.
  2. 1 2 3 4 5 6 7 8 9 P. K. Yuen Practical Cryptology and Web Security. — Pearson Education. — 2006. — С. 390. — 879 с.
  3. 1 2 3 B. Schneier Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish) // Fast Software Encryption, Cambridge Security Workshop Proceedings (December 1993), Springer-Verlag. — 1994. — С. 191 — 204.
  4. Serge Vaudenay On the weak keys of blowfish // Springer-Verlag. — 1996. — С. 27–32.
  5. Christian Cachin, Jan Camenisch Advances in Cryptology - EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic. — Interlaken, Switzerland: Springer Science & Business Media, 2004. — С. 557. — 628 с.
  6. Tingyuan Nie, Chuanwang Song, Xulong Zhi Performance Evaluation of DES and Blowfish Algorithms // IEEE. — 23-25 April 2010.

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