Blowfish

Blowfish

Розробники	Брюс Шнайєр
Уперше оприлюднений	1993 р.
Раундів	16
Тип	мережа Фейстеля

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

Розроблений Брюсом Шнайєром в 1993 році. Являє собою шифр на основі мережі Фейстеля. Виконано на простих і швидких операціях: XOR, підстановка, додавання. Не запатентований і вільно поширюваний.

Історія

До появи Blowfish алгоритми, що існували були або запатентованими, або ненадійними, а деякі і зовсім трималися в секреті (наприклад, Skipjack). Алгоритм був розроблений у 1993 році Брюсом Шнайєром як швидка й вільна альтернатива застарілому DES і запатентованому IDEA. За заявою автора, критерії проектування Blowfish були:

• Швидкість (шифрування на 32-бітних процесорах відбувається за 26 тактів);
• Простота (за рахунок використання простих операцій, які зменшують імовірність помилки реалізації алгоритму);
• Компактність;
• Можливість налаштування стійкості.

Опис алгоритму

Параметри

• Секретний ключ K (від 32 до 448 біт)
• 32-бітові ключі шифрування P1-P18
• 32-бітові таблиці замін S1-S4:

  S1 [0] S1 [1] .. S1 [255]

  S2 [0] S2 [1] .. S2 [255]

  S3 [0] S3 [1] .. S3 [255]

  S4 [0] S4 [1] .. S4 [255]

Функція F (x)

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

1. 32-бітний блок ділиться на чотири 8-бітних блоки (X1, X2, X3, X4), кожен з яких є індексом масиву таблиці замін S1-S4
2. Значення S1[X1] і S2[X2] складаються по модулю $2^{32}$, після "XOR"яться з S3[X3] і, нарешті, додаються з S4[X4] по модулю $2^{32}$.
3. Результат цих операцій — значення F (x).

$F(X1,X2,X3,X4)=(((S1[X1]\ +\ S2[X2])\mod 2^{32}\ \oplus \ S3[X3])\ +\ S4[X4])\mod 2^{32}$

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

Мережа Фейстеля при шифруванні

• Поділ на 32-бітові блоки: $L_{0}\,\ R_{0}$
• $L_{0}\$ і $R_{0}\$ «XOR»-ся з ключами $P_{0}\$, $P_{1}\$
• Обчислення в i-тому раунді:

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

  $L_{i}\ =\ R_{i-1}\oplus F(R_{i})$

• Після 16 раунду $L_{16}\,\ R_{16}$ міняються місцями:

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

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

Алгоритм Blowfish

Розділений на 2 етапи:

1. Підготовчий — формування ключів шифрування по секретному ключу.
   • Ініціалізація масивів P і S за допомогою секретного ключа K
     1. Ініціалізація P1-P18 фіксованим рядком, що складається з шістнадцяткових цифр мантиси числа пі [Архівовано 3 вересня 2008 у Wayback Machine.].
     2. Проводиться операція XOR над P1 з першими 32 бітами ключа K, над P2 з другими 32-бітами і так далі.
        Якщо ключ K коротше, то він накладається циклічно.
   • Шифрування ключів і таблиць замін
     1. Алгоритм шифрування 64-бітного блоку, використовуючи початкові ключі P1-P18 і таблицю замін S1-S4, шифрує 64 бітну нульовий (0x0000000000000000) рядок. Результат записується в P1, P2.
     2. P1 і P2 шифруються зміненими значеннями ключів і таблиць замін. Результат записується в P3 і P4.
     3. Шифрування триває до зміни всіх ключів P1-P18 і таблиць замін S1-S4.
2. Шифрування тексту отриманими ключами і F(x), з попереднім розбиттям на блоки по 64 біти. Якщо неможливо розбити початковий текст точно на блоки по 64 біти, використовуються різні режими шифрування для побудови повідомлення, що складається з цілого числа блоків. Сумарні необхідна пам'ять 4168 байт: P1-P18: 18 змінних по 32 біта; S1-S4: 4x256 змінних по 32 бита.

Розшифрування відбувається аналогічно, тільки P1-P18 застосовуються у зворотному порядку.

Вибір початкового значення P-масиву і таблиці замін

Немає нічого особливого в цифрах числа пі. Цей вибір полягає в ініціалізації послідовності, не пов'язаної з алгоритмом, яка могла б бути збережена як частина алгоритму або отримана при необхідності (Пі (число)). Як вказує Брюс Шнайєр: «Підійде будь-який рядок з випадкових бітів цифр числа e, RAND-таблиці, або випадкові згенеровані цифри.»

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

• Слабкий S-box (і породжує його слабкий ключ) означає, що існує такі i, j, N = {1,2,3,4}: SN[i] == SN[j]

Криптостійкість головним чином залежить від F (x). На це вказав Serge Vaudenay, кажучи про наявність невеликого класу слабких ключів (таких, що утворюють слабкі S-box): ймовірність появи слабкого S-box дорівнює $2^{-15}$. Він також розглянув спрощений варіант Blowfish, з відомою функцією F(x) і слабким ключем. Для цього варіанту потрібно $3*2^{2+7*[(t-2)/2]}\approx 2^{3+7*[(t-2)/2]}$ обраних відкритих текстів (t - число раундів, а символи [] означають операцію отримання цілої частини числа). Ця атака може бути використана тільки для алгоритму з $t\leq 7$. Для $t=7$ потрібно $2^{24}$ відкритих текстів, причому для варіанту з відомим F (x) і випадковим ключем потрібно $2^{48}$ відкритих текстів. Але дана атака не ефективна для Blowfish з 16 раундами.

John Kelsey розробив атаку, яка дозволяла зламати 3-ітераційний Blowfish. Вона спирається на факт, що операції додавання по модулю $2^{32}$ і XOR НЕ комутативні.

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

Криптостійкість можна налаштовувати за рахунок зміни кількості раундів шифрування (збільшуючи довжину масиву P) і кількості використовуваних S-box. При зменшенні використовуваних S-box зростає ймовірність появи слабких ключів, але зменшується використовувана пам'ять. Для адаптації Blowfish на 64-бітної архітектуру, можна збільшити кількість і розмір S-box (а отже і пам'ять для масивів 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 \ \equiv mod2^{32}$

На листопад 2008 не існувало атак, які виконуються за розумний час. Успішні атаки можливі тільки через помилки реалізації.

Застосування

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

• Хешування паролів
• Захист електронної пошти і файлів
  • GnuPG (безпечне зберігання і передача)
• В лініях зв'язку: зв'язка ElGamal (не запатентований) або RSA (дія патенту закінчилося в 2000 році) і Blowfish замість IDEA
  • В маршрутизаторі Intel Express 8100 з ключем довжиною 144 біта
• Забезпечення безпеки в протоколах мережного і транспортного рівня
  • PuTTY (мережевий рівень)
  • SSH (транспортний рівень)
  • OpenVPN (створення зашифрованих каналів)

Порівняння з симетричними криптосистемами

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

Хоча Blowfish по швидкості випереджає свої аналоги, але при збільшенні частоти зміни ключа основний час його роботи буде йти на підготовчий етап, що в сотні разів зменшує його ефективність.

Посилання

• Blowfish як JavaScript-модулю [Архівовано 8 березня 2016 у Wayback Machine.]
• Andrey Breeze, На шляху до Skein: просто і зрозуміло про Blowfish [Архівовано 2 липня 2012 у Wayback Machine.]
• Максим Паригін, Алгоритм Blowfish [Архівовано 6 січня 2012 у Wayback Machine.]
• Офіційний вебсайт Blowfish [Архівовано 10 липня 2007 у Wayback Machine.]
• Список продуктів, що використовують Blowfish [Архівовано 14 липня 2007 у Wayback Machine.]
• Serge Vaudenay.On the weak Keys of Blowfish [Архівовано 4 лютого 2013 у Wayback Machine.] (англ.)
• Dieter Schmidt.Kaweichel, an Extension of Blowfish for 64-Bit Architectures [Архівовано 27 червня 2010 у Wayback Machine.] (англ.)