Blowfish

Blowfish
Создатель:	Брюс Шнайер
Создан:	1993 г.
Опубликован:	1993 г.
Размер ключа:	от 32 до 448 бит
Размер блока:	64 бит
Число раундов:	16
Тип:	Сеть Фейстеля

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

История

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

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

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

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

Параметры

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

  <math>S_{1}[0],\ S_{1}[1],\ ...,\ S_{1}[255]</math>

  <math>S_{2}[0],\ S_{2}[1],\ ...,\ S_{2}[255]</math>

  <math>S_{3}[0],\ S_{3}[1],\ ...,\ S_{3}[255]</math>

  <math>S_{4}[0],\ S_{4}[1],\ ...,\ S_{4}[255]</math>

Функция F(x)

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

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

<math>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}</math>

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

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

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

   <math>R_i\ =\ L_{i-1} \oplus P_{i}</math>

   <math>L_i\ =\ R_{i-1} \oplus F(R_i)</math>

3. После 16 раунда <math>L_{16}\ ,\ R_{16}</math> меняются местами:

   <math>R_{16}\ \leftleftarrows\ L_{16}\ </math>

   <math>\ L_{16}\ \leftleftarrows\ R_{16}</math>

4. К получившимся блокам прибавляются <math>P_{17}</math> и <math>P_{18}</math>

   <math>L_{17} = L_{16} \oplus P_{18} </math>

   <math>R_{17} = R_{16} \oplus P_{17} </math>

5. Выходной блок <math>Y</math> равен конкатенации (объединению) <math>L_{17}</math> и <math>R_{17}</math>.

Алгоритм Blowfish

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

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

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

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

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

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

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

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

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

Модификация F(x): на вход подается 64-битный блок, который делится на восемь 8-битных блоков (X1-X8). Результат вычисляется по формуле <math>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])\ )\ )</math>, где <math>\boxplus</math> — это операция сложения по модулю <math>2^{32}</math>
На сегодняшний день (ноябрь 2008) не существует атак, выполняемых за разумное время. Успешные атаки возможны только из-за ошибок реализации.

Применения

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

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

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

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

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

Ссылки

• [www.schneier.com/blowfish.html Официальный веб-сайт Blowfish]
• [www.schneier.com/blowfish-products.html Список продуктов, использующих Blowfish]
• [eprint.iacr.org/2005/144.pdf Dieter Schmidt. Kaweichel, an Extension of Blowfish for 64-Bit Architectures] (англ.)

Отрывок, характеризующий Blowfish

Когда одетое, обмытое тело лежало в гробу на столе, все подходили к нему прощаться, и все плакали.
Николушка плакал от страдальческого недоумения, разрывавшего его сердце. Графиня и Соня плакали от жалости к Наташе и о том, что его нет больше. Старый граф плакал о том, что скоро, он чувствовал, и ему предстояло сделать тот же страшный шаг.
Наташа и княжна Марья плакали тоже теперь, но они плакали не от своего личного горя; они плакали от благоговейного умиления, охватившего их души перед сознанием простого и торжественного таинства смерти, совершившегося перед ними.



Для человеческого ума недоступна совокупность причин явлений. Но потребность отыскивать причины вложена в душу человека. И человеческий ум, не вникнувши в бесчисленность и сложность условий явлений, из которых каждое отдельно может представляться причиною, хватается за первое, самое понятное сближение и говорит: вот причина. В исторических событиях (где предметом наблюдения суть действия людей) самым первобытным сближением представляется воля богов, потом воля тех людей, которые стоят на самом видном историческом месте, – исторических героев. Но стоит только вникнуть в сущность каждого исторического события, то есть в деятельность всей массы людей, участвовавших в событии, чтобы убедиться, что воля исторического героя не только не руководит действиями масс, но сама постоянно руководима. Казалось бы, все равно понимать значение исторического события так или иначе. Но между человеком, который говорит, что народы Запада пошли на Восток, потому что Наполеон захотел этого, и человеком, который говорит, что это совершилось, потому что должно было совершиться, существует то же различие, которое существовало между людьми, утверждавшими, что земля стоит твердо и планеты движутся вокруг нее, и теми, которые говорили, что они не знают, на чем держится земля, но знают, что есть законы, управляющие движением и ее, и других планет. Причин исторического события – нет и не может быть, кроме единственной причины всех причин. Но есть законы, управляющие событиями, отчасти неизвестные, отчасти нащупываемые нами. Открытие этих законов возможно только тогда, когда мы вполне отрешимся от отыскиванья причин в воле одного человека, точно так же, как открытие законов движения планет стало возможно только тогда, когда люди отрешились от представления утвержденности земли.

После Бородинского сражения, занятия неприятелем Москвы и сожжения ее, важнейшим эпизодом войны 1812 года историки признают движение русской армии с Рязанской на Калужскую дорогу и к Тарутинскому лагерю – так называемый фланговый марш за Красной Пахрой. Историки приписывают славу этого гениального подвига различным лицам и спорят о том, кому, собственно, она принадлежит. Даже иностранные, даже французские историки признают гениальность русских полководцев, говоря об этом фланговом марше. Но почему военные писатели, а за ними и все, полагают, что этот фланговый марш есть весьма глубокомысленное изобретение какого нибудь одного лица, спасшее Россию и погубившее Наполеона, – весьма трудно понять. Во первых, трудно понять, в чем состоит глубокомыслие и гениальность этого движения; ибо для того, чтобы догадаться, что самое лучшее положение армии (когда ее не атакуют) находиться там, где больше продовольствия, – не нужно большого умственного напряжения. И каждый, даже глупый тринадцатилетний мальчик, без труда мог догадаться, что в 1812 году самое выгодное положение армии, после отступления от Москвы, было на Калужской дороге. Итак, нельзя понять, во первых, какими умозаключениями доходят историки до того, чтобы видеть что то глубокомысленное в этом маневре. Во вторых, еще труднее понять, в чем именно историки видят спасительность этого маневра для русских и пагубность его для французов; ибо фланговый марш этот, при других, предшествующих, сопутствовавших и последовавших обстоятельствах, мог быть пагубным для русского и спасительным для французского войска. Если с того времени, как совершилось это движение, положение русского войска стало улучшаться, то из этого никак не следует, чтобы это движение было тому причиною.
Этот фланговый марш не только не мог бы принести какие нибудь выгоды, но мог бы погубить русскую армию, ежели бы при том не было совпадения других условий. Что бы было, если бы не сгорела Москва? Если бы Мюрат не потерял из виду русских? Если бы Наполеон не находился в бездействии? Если бы под Красной Пахрой русская армия, по совету Бенигсена и Барклая, дала бы сражение? Что бы было, если бы французы атаковали русских, когда они шли за Пахрой? Что бы было, если бы впоследствии Наполеон, подойдя к Тарутину, атаковал бы русских хотя бы с одной десятой долей той энергии, с которой он атаковал в Смоленске? Что бы было, если бы французы пошли на Петербург?.. При всех этих предположениях спасительность флангового марша могла перейти в пагубность.
В третьих, и самое непонятное, состоит в том, что люди, изучающие историю, умышленно не хотят видеть того, что фланговый марш нельзя приписывать никакому одному человеку, что никто никогда его не предвидел, что маневр этот, точно так же как и отступление в Филях, в настоящем никогда никому не представлялся в его цельности, а шаг за шагом, событие за событием, мгновение за мгновением вытекал из бесчисленного количества самых разнообразных условий, и только тогда представился во всей своей цельности, когда он совершился и стал прошедшим.
На совете в Филях у русского начальства преобладающею мыслью было само собой разумевшееся отступление по прямому направлению назад, то есть по Нижегородской дороге. Доказательствами тому служит то, что большинство голосов на совете было подано в этом смысле, и, главное, известный разговор после совета главнокомандующего с Ланским, заведовавшим провиантскою частью. Ланской донес главнокомандующему, что продовольствие для армии собрано преимущественно по Оке, в Тульской и Калужской губерниях и что в случае отступления на Нижний запасы провианта будут отделены от армии большою рекою Окой, через которую перевоз в первозимье бывает невозможен. Это был первый признак необходимости уклонения от прежде представлявшегося самым естественным прямого направления на Нижний. Армия подержалась южнее, по Рязанской дороге, и ближе к запасам. Впоследствии бездействие французов, потерявших даже из виду русскую армию, заботы о защите Тульского завода и, главное, выгоды приближения к своим запасам заставили армию отклониться еще южнее, на Тульскую дорогу. Перейдя отчаянным движением за Пахрой на Тульскую дорогу, военачальники русской армии думали оставаться у Подольска, и не было мысли о Тарутинской позиции; но бесчисленное количество обстоятельств и появление опять французских войск, прежде потерявших из виду русских, и проекты сражения, и, главное, обилие провианта в Калуге заставили нашу армию еще более отклониться к югу и перейти в середину путей своего продовольствия, с Тульской на Калужскую дорогу, к Тарутину. Точно так же, как нельзя отвечать на тот вопрос, когда оставлена была Москва, нельзя отвечать и на то, когда именно и кем решено было перейти к Тарутину. Только тогда, когда войска пришли уже к Тарутину вследствие бесчисленных дифференциальных сил, тогда только стали люди уверять себя, что они этого хотели и давно предвидели.


Знаменитый фланговый марш состоял только в том, что русское войско, отступая все прямо назад по обратному направлению наступления, после того как наступление французов прекратилось, отклонилось от принятого сначала прямого направления и, не видя за собой преследования, естественно подалось в ту сторону, куда его влекло обилие продовольствия.
Если бы представить себе не гениальных полководцев во главе русской армии, но просто одну армию без начальников, то и эта армия не могла бы сделать ничего другого, кроме обратного движения к Москве, описывая дугу с той стороны, с которой было больше продовольствия и край был обильнее.
Передвижение это с Нижегородской на Рязанскую, Тульскую и Калужскую дороги было до такой степени естественно, что в этом самом направлении отбегали мародеры русской армии и что в этом самом направлении требовалось из Петербурга, чтобы Кутузов перевел свою армию. В Тарутине Кутузов получил почти выговор от государя за то, что он отвел армию на Рязанскую дорогу, и ему указывалось то самое положение против Калуги, в котором он уже находился в то время, как получил письмо государя.
Откатывавшийся по направлению толчка, данного ему во время всей кампании и в Бородинском сражении, шар русского войска, при уничтожении силы толчка и не получая новых толчков, принял то положение, которое было ему естественно.
Заслуга Кутузова не состояла в каком нибудь гениальном, как это называют, стратегическом маневре, а в том, что он один понимал значение совершавшегося события. Он один понимал уже тогда значение бездействия французской армии, он один продолжал утверждать, что Бородинское сражение была победа; он один – тот, который, казалось бы, по своему положению главнокомандующего, должен был быть вызываем к наступлению, – он один все силы свои употреблял на то, чтобы удержать русскую армию от бесполезных сражений.