Blowfish

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Алгоритм блочного шифрування
BlowfishFFunction.svg
Назва: Blowfish
Розробник: Брюс Шнайєр
Створений: 1993 р.
Опублікований: 1993 р.
Розмір ключа: 32-448 біт
Розмір блоку: 64біт
Число раундів: 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. Підготовчий — формування ключів шифрування по секретному ключу.
  2. *Ініціалізація масивів P і S за допомогою секретного ключа K
  3. *# Ініціалізація P1-P18 фіксованим рядком, що складається з шістнадцяткових цифр мантиси числа пі.
  4. *# Проводиться операція XOR над P1 з першими 32 бітами ключа K, над P2 з другими 32-бітами і так далі.
    Якщо ключ K коротше, то він накладається циклічно.
  5. * Шифрування ключів і таблиць замін
  6. *# Алгоритм шифрування 64-бітного блоку, використовуючи початкові ключі P1-P18 і таблицю замін S1-S4, шифрує 64 бітну нульовий (0x0000000000000000) рядок. Результат записується в P1, P2.
  7. *# P1 і P2 шифруються зміненими значеннями ключів і таблиць замін. Результат записується в P3 і P4.
  8. *# Шифрування триває до зміни всіх ключів P1-P18 і таблиць замін S1-S4.
  9. Шифрування тексту отриманими ключами і 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]} \approx2 ^ {3 +7 * [(t-2) / 2]} обраних відкритих текстів (t - число раундів, а символи [] означають операцію отримання цілої частини числа). Ця атака може бути використана тільки для алгоритму з  t \le 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 mod 2^{32}

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

Застосування[ред.ред. код]

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

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

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

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

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


Посилання[ред.ред. код]