Twofish

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Алгоритм блочного шифрування
Twofishalgo.svg
Назва: Serpent
Розробник: Брюс Шнайєр
Створений: 1998 р.
Опублікований: 1998 р.
Розмір ключа: 128/192/256 біт
Розмір блоку: 128 біт
Число раундів: 16
Тип: Мережа Фейстеля


Twofish — симетричний алгоритм блочного шифрування з розміром блоку 128 біт і довжиною ключа до 256 біт. Число раундів 16. Розроблено групою фахівців на чолі з Брюсом Шнайером. Був одним з п'яти фіналістів другого етапу конкурсу AES. Алгоритм розроблений на основі алгоритмів Blowfish, SAFER і Square.

Відмітними особливостями алгоритму є використання попередньо обчислюваних та залежних від ключа S-box'ів і складна схема розгортки підключення шифрування. Половина n-бітного ключа шифрування використовується як власне ключ шифрування, інша — для модифікації алгоритму (від неї залежать S-box'и).

Загальні відомості[ред.ред. код]

Twofish розроблявся спеціально з урахуванням вимог та рекомендацій NIST для конкурсу AES [1]:

  • 128-бітний блочний симетричний шифр
  • Довжина ключів 128, 192 і 256 біт
  • Відсутність слабких ключів
  • Ефективна програмна (в першу чергу на 32-бітних процесорах) та апаратна реалізація
  • Гнучкість (можливість використання додаткових довжин ключа, використання в поточному шифруванні, хеш-функціях і т. д.)
  • Простота алгоритму - для можливості його ефективного аналізу

Однак саме складність структури алгоритму і, відповідно, складність його аналізу на предмет слабких ключів або прихованих зв'язків, а також досить повільне час шифрування порівняно з Rijndael на більшості платформ, зіграло не на його користь. [2]

Алгоритм Twofish виник в результаті спроби модифіковані алгоритм Blowfish для 128-бітового вхідного блоку. Новий алгоритм повинен був бути легко реалізованим апаратно (у тому числі використовувати таблиці меншого розміру), мати досконалішу систему розширення ключа (key schedule) і мати однозначну функцію F.

В результаті, алгоритм був реалізований у вигляді змішаної мережі Фейстеля з чотирма гілками, які модифікують один одну з використанням криптоперетворень Адамара (Pseudo-Hadamar Transform, PHT).

Можливість ефективної реалізації на сучасних (для того часу) 32-бітних процесорах (а також в смарт-картах і подібних пристроях) - один з ключових принципів, яким керувалися розробники Twofish.
Наприклад, у функції F при обчисленні PHT і складання з частиною ключа K навмисно використовується додавання, замість традиційного xor. Це дає можливість використовувати команду LEA сімейства процесорів Pentium, яка за один такт дозволяє обчислити перетворення Адамара  ({T} _ {0} +2 {T} _ {1} + {K} _ {2r +9}) ~ mod ~ 2 ^ {32} . (Правда в такому випадку код доводиться компілювати під конкретне значення ключа).

Алгоритм Twofish не запатентований і може бути використаний ким завгодно без будь-якої плати або відрахувань. Він використовується в багатьох програмах шифрування, хоча і отримав менше поширення, ніж Blowfish.

Опис алгоритму[ред.ред. код]

Twofish розбиває вхідний 128-бітний блок даних на чотири 32-бітних подблока, над якими, після процедури вхідного відбілювання (input whitening), проводиться 16 раундів перетворень. Після останнього раунду виконується вихідна відбілювання (output whitening).

Відбілювання (whitening)[ред.ред. код]

Відбілювання - це процедура xor'а даних з підключами перед першим раундом і після останнього раунду. Вперше ця техніка була використана в шифрі Khufu/Khare і, незалежно, Рональдом Рівестом (Ron Rivest) в алгоритмі шифрування DESX. Joe Killian (NEC) і Phillip Rogaway (Каліфорнійський університет) показали, що відбілювання дійсно ускладнює завдання пошуку ключа повним перебором (exhaustive key-search) в DESX [3] . Розробники Twofish стверджують [4], що в Twofish відбілювання також істотно ускладнює завдання підбору ключа, оскільки криптоаналітика не може дізнатися, які дані потрапляють на вхід функції F першого раунду.

Тим не менш, виявилися і негативні сторони. Цікаве дослідження провели фахівці дослідницького центру компанії IBM. [5] Вони виконали реалізацію алгоритму Twofish для типової смарт-карти з CMOS-архітектурою і проаналізували можливість атаки за допомогою диференціального аналізу споживаної потужності (DPA - Differential Power Analysis). Атаці піддавалася саме процедура вхідного вибілювання, оскільки вона безпосередньо використовує xor подключей з вхідними даними. У результаті дослідники показали, що можна повністю обчислити 128-бітовий ключ проаналізувавши всього 100 операцій шифрування довільних блоків.

Функція g[ред.ред. код]

Функція g - основа алгоритму Twofish. На вхід функції подається 32-бітове число X, яке потім розбивається на чотири байти x0, x1, x2, x3. Кожен з вийшов байтів пропускається через свій S-box. (Слід зазначити, що S-box'и в алгоритмі не фіксовані, а залежать від ключа). Отримані 4 байти на виходах S-box'ов інтерпретуються як вектор з чотирма компонентами. Цей вектор множиться на фіксовану матрицю MDS (maximum distance separable) розміром 4x4, причому обчислення проводяться в поле Галуа  GF (2 ^ 8) по модулю непривідного многочлена  x ^ 8 + x ^ 6 + x ^ 5 + x ^ 3 + 1

MDS матриця - це така матриця над кінцевим полем K, що якщо взяти її в якості матриці лінійного перетворення  f (x) = (MDS) x з простору  K ^ n у простір  K ^ m , то будь-які два вектори з простору  K ^ {n + m} виду (x, f (x)) будуть мати як мінімум m+1 відмінностей в компонентах . Тобто набір векторів вигляду (x, f (x)) утворює код, що володіє властивістю максимального рознесення (maximum distance separable code). Таким кодом, наприклад, є код Ріда-Соломона.

В Twofish властивість максимальної разнесеність матриці MDS означає, що загальна кількість змінних байт вектора a і вектора  b = (MDS) a не менше п'яти. Іншими словами, будь-яка зміна тільки одного байта в a призводить до зміни всіх чотирьох байтів в b.

Криптоперетворення Адамара (Pseudo-Hadamar Transform, PHT)[ред.ред. код]

криптоперетворення Адамара - оборотне перетворення бітового рядка довжиною 2n. Рядок розбивається на дві частини a і b однакової довжини в n біт. Перетворення обчислюється таким чином:

a' = a + b \, \pmod{2^n}\,
b' = a + 2b\, \pmod{2^n}\,

Ця операція часто використовується для «розсіювання» коду (наприклад в шифрі SAFER).

В Twofish це перетворення використовується при змішуванні результатів двох g-функций (n = 32).

Циклічний зсув на 1 біт[ред.ред. код]

У кожному раунді два правих 32-бітових блоку, які xor-ятся з результатами функції F, додатково циклічно зрушуються на один біт. Третій блок зрушується до операції xor, четвертий блок - після. Ці зрушення спеціально додані, щоб порушити вирівнювання по байтам, яке властиво S-box'ам та операції множення на MDS-матрицю. Проте шифр перестає бути повністю симетричним, так як при шифрации і розшифровці зрушення слід здійснювати в протилежні сторони.

Генерація ключів[ред.ред. код]

Twofish розрахований на роботу з ключами довжиною 128, 192 і 256 біт. З вихідного ключа генерується 40 32-бітних подключей, перші вісім з яких використовуються тільки в операціях вхідного і вихідного вибілювання, а решта 32 - в раундах шифрування, по два підключа на раунд. Особливістю Twofish є те, що вихідний ключ використовується також і для зміни самого алгоритму шифрування, так як використовуються у функції g S-box'и не фіксовані, а залежать від ключа.

Для формування раундових подключей вихідний ключ M розбивається з перестановкою байт на два однакові блоки  M_o і  M_e . Потім за допомогою блоку  M_o і функції h шифрується значення 2 * i, а за допомогою блоку  M_e шифрується значення 2*i+1, де i - номер поточного раунду (0 - 15). Отримані зашифровані блоки змішуються криптоперетвореням Адамара, і потім використовуються як раундові подключі.

Технічні подробиці[ред.ред. код]

Розглянемо більш докладно алгоритм формування раундових подключів, а також залежить від ключа функції g. Як для формування подключів, так і для формування функції g в Twofish використовується одна основна функція: h (X, L 0 , L 1 , ..., L k ). Тут X, L 0 , L 1 , ..., L k - 32 бітні слова, а k = N / 64, де N - довжина вихідного ключа в бітах. Результатом функції є одне 32-бітове слово.

Функція h[ред.ред. код]

Функція виконується в k етапів. Тобто для довжини ключа 256 біт буде 4 етапи, для ключа в 192 біта - 3 етапи, для 128 біт - 2 етапи.

На кожному етапі вхідний 32-бітове слово розбивається на 4 байта, і кожен байт піддається фіксованою перестановці бітів q 0 або q 1

Результат представляється у вигляді вектора з 4 байтів і множиться на MDS матрицю. Обчислення проводяться в поле Галуа GF (2 8 ) по модулю непривідного многочлена  x ^ 8 + x ^ 6 + x ^ 5 + x ^ 3 + 1 .

Матриця MDS має вигляд:

~\mbox{MDS} = \begin{pmatrix} 
01 & EF & 5B & 5B \\ 
5B & EF & EF & 01 \\ 
EF & 5B & 01 & EF \\
EF & 01 & EF & 5B
\end{pmatrix}

Перестановки q 0 і q 1 [ред.ред. код]

q 0 і q 1 - фіксовані перестановки 8 бітів вхідного байта x.

Байт x розбивається на дві 4-бітні половинки a 0 і b 0 , над якими проводяться наступні перетворення:

~a_0 = x/16            ~b_0 = x\bmod{16}
~a_1 = a_0 \oplus b_0            ~b_1 = a_0 \oplus \mbox{ROR}_4(b_0,1) \oplus 8a_0 \bmod{16}
~a_2 = t_0[a_1]            ~b_2 = t_1[b_1]
~a_3 = a_2 \oplus b_2            ~b_3 = a_2 \oplus \mbox{ROR}_4(b_2,1) \oplus 8a_2 \bmod{16}
~a_4 = t_2[a_3]            ~b_4 = t_3[b_3]
~y = 16b_4 + a_4

Тут  ~ \mbox {ROR} _4 - 4-бітний циклічний зсув вправо, а t 0 , t 1 , t 2 , t 3 - табличні заміни 4-бітових чисел.

Для q 0 таблиці мають вигляд:

t0 = [ 8 1 7 D 6 F 3 2 0 B 5 9 E C A 4 ]
t1 = [ E C B 8 1 2 3 5 F 4 A 6 7 0 9 D ]
t2 = [ B A 5 E 6 D 9 0 C 8 F 3 2 4 7 1 ]
t3 = [ D 7 F 4 1 2 6 E 9 B 3 0 8 5 C A ]

Для q 1 таблиці мають вигляд:

t0 = [ 2 8 B D F 7 6 E 3 1 9 4 0 A C 5 ]
t1 = [ 1 E 2 B 4 C 3 7 6 D A 5 F 9 0 8 ]
t2 = [ 4 C 7 5 1 6 9 A 0 E D 8 2 B 3 F ]
t3 = [ B 9 5 1 C 3 D E 6 4 7 F 2 0 8 A ]

Генерація ключів[ред.ред. код]

Нехай M - вихідний ключ, N - його довжина в бітах. Генерація подключів відбувається наступним чином:

  • Оригінальний ключ розбивається на 8 * k байтів  m_0, ..., m_ {8k-1} , де k = N / 64.
  • Ці 8 * k байтів розбиваються на слова по чотири байти, і в кожному слові байти переставляються у зворотному порядку. У підсумку виходить 2 * k 32-бітних слова  M_i
 ~ M_i = \sum ^ 3_ {j = 0} m_ {(4i + j)} \cdot 2 ^ {8j} ~ ~ ~ ~ ~ i = 0, ..., 2k-1
  • Отримані 2 * k 32-бітних розбиваються на два вектора  ~ M_e і  ~ M_o розміром в k 32-бітових слів.
 ~ M_e = (M_0, M_2, ..., M_ {2k-2})
 ~ M_o = (M_1, M_3, ..., M_ {2k-1})

Підключи для i-го раунду обчислюються за формулами:

~\rho=2^{24} + 2^{16} + 2^8 + 2^0
~A_i = h(2i\rho, M_e)
~B_i = \mbox{ROL}(h((2i+1)\rho, M_0), 8)
~K_{2i} = (A_i + B_i)\bmod{2^{32}}
~K_{2i+1} = \mbox{ROL}((A_i+2B_i)\bmod{2^{32}},9)

Функція g і S-box'и[ред.ред. код]

Функція g визначається через функцію h:  ~ g (X) = h (X, S)

Вектор S, як і вектора M e і M o , теж формується з вихідного ключа і складається з k 32-бітових слів. Вихідні байти ключа розбиваються на k груп по вісім байт. Кожна така група розглядається як вектор з 8-ма компонентами і множиться на фіксовану RS матрицю розміром 4x8 байт. В результаті множення виходить вектор, що складається з чотирьох байт. Обчислення проводяться в поле Галуа  GF (2 ^ 8) по модулю непріводімогомногочлена  x ^ 8 + x ^ 6 + x ^ 3 + x ^ 2 + 1 .

RS-матриця має вигляд:

~\mbox{RS} = \begin{pmatrix} 
01 & A4 & 55 & 87 & 5A & 58 & DB & 9E \\ 
A4 & 56 & 82 & F3 & 1E & C6 & 68 & E5 \\
02 & A1 & FC & C1 & 47 & AE & 3D & 19 \\
A4 & 55 & 87 & 5A & 58 & DB & 9E & 03
\end{pmatrix}

Криптоаналіз[ред.ред. код]

Вивчення Twofish зі скороченими числом раундів показало, що алгоритм володіє великим запасом міцності, і, в порівнянні з іншими фіналістами конкурсу AES, він виявився найстійкішим. Проте його незвичайна структура і відносна складність породили деякі сумніви в якості цієї міцності.

Нарікання викликало розділення вихідного ключа на дві половини при формуванні раундових подключів. Криптографи Fauzan Mirza і Sean Murphy припустили, що такий поділ дає можливість організувати атаку за принципом «розділяй і володарюй», тобто розбити задачу на дві аналогічні, але простіші [6]. Однак реально подібну атаку провести не вдалося.

На 2008 рік кращим варіантом криптоаналізу Twofish є варіант усіченого диференціального криптоаналізу, який був опублікований Shiho Moriai і Yiqun Lisa Yin в Японії в 2000 році [7]. Вони показали, що для знаходження необхідних диференціалів потрібно 2 51 підібраних відкритих текстів. Проте дослідження носили теоретичний характер, жодної реальної атаки проведено не було. У своєму блозі творець Twofish Брюс Шнайєр стверджує, що в реальності провести таку атаку неможливо [8].

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

Примітки[ред.ред. код]

  1. «Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES)» (англ.). Department of Commerce - National Institute of Standards and Technology - Federal Register: September 12, 1997
  2. Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. pdf «Report on the Development of the Advanced Encryption Standard (AES)» (англ.). - National Institute of Standards and Technology.
  3. J. Kilian and P. Rogaway rogaway/papers/desx.pdf «How to Protect DES Against Exhaustive Key Search» (англ.) February 2, 2000
  4. N. Ferguson, J. Kelsey, B. Schneier, D. Whiting «A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish» (англ.) Twofish Technical Report # 6, February 14, 2000
  5. Suresh Chari, Charanjit Jutla, Josyula R. Rao, Pankaj Rohatgi «A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards» (англ.), 1999
  6. Fauzan Mirza, Sean Murphy [http:/ / csrc.nist.gov/archive/aes/round1/conf2/papers/mirza.pdf «An Observation on the Key Schedule of Twofish»] (англ.) - Information Security Group, Royal Holloway, University of London - January 26, 1999
  7. Shiho Moriai, Yiqun Lisa Yin / twofish-analysis-shiho.pdf «Cryptanalysis of Twofish (II)» (англ.) - The Institute of Economics, Information and Communication Engineers
  8. Bruce Schneier «Twofish Cryptanalysis Rumors » (англ.) blog