Twofish — симетричний алгоритм блочного шифрування з розміром блоку 128 біт і довжиною ключа до 256 біт. Число раундів 16. Розроблено групою фахівців на чолі з Брюсом Шнайером. Був одним з п'яти фіналістів другого етапу конкурсу AES. Алгоритм розроблений на основі алгоритмів Blowfish, SAFER і Square.
Відмінними особливостями алгоритму є використання попередньо обчислюваних та залежних від ключа S-box'ів і складна схема розгортки підключення шифрування. Половина n-бітного ключа шифрування використовується як власне ключ шифрування, інша — для модифікації алгоритму (від неї залежать S-box'и).
Загальні відомості Twofish розроблявся спеціально з урахуванням вимог та рекомендацій NIST для конкурсу AES «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: 128-бітний блочний симетричний шифр Довжина ключів 128, 192 і 256 біт Відсутність слабких ключів Ефективна програмна (в першу чергу на 32-бітних процесорах) та апаратна реалізація Гнучкість (можливість використання додаткових довжин ключа, використання в поточному шифруванні, хеш-функціях і т. д.) Простота алгоритму - для можливості його ефективного аналізу
Однак саме складність структури алгоритму і, відповідно, складність його аналізу на предмет слабких ключів або прихованих зв'язків, а також досить повільний час шифрування порівняно з Rijndael на більшості платформ, зіграло не на його користь. 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.
Алгоритм Twofish виник в результаті спроби модифікувати алгоритм Blowfish для 128-бітового вхідного блоку. Новий алгоритм повинен був бути легко реалізованим апаратно (у тому числі використовувати таблиці меншого розміру), мати досконалішу систему розширення ключа (key schedule) і мати однозначну функцію F.
В результаті, алгоритм був реалізований у вигляді змішаної мережі Фейстеля з чотирма гілками, які модифікують один одну з використанням криптоперетворень Адамара (Pseudo-Hadamar Transform, PHT).
Можливість ефективної реалізації на сучасних (для того часу) 32-бітних процесорах (а також в смарт-картах і подібних пристроях) - один з ключових принципів, яким керувалися розробники Twofish. Наприклад, у функції F при обчисленні PHT і складання з частиною ключа K навмисно використовується додавання, замість традиційного xor. Це дає можливість використовувати команду LEA сімейства процесорів Pentium, яка за один такт дозволяє обчислити перетворення Адамара . (Правда в такому випадку код доводиться компілювати під конкретне значення ключа).
Алгоритм Twofish не запатентований і може бути використаний ким завгодно без будь-якої плати або відрахувань. Він використовується в багатьох програмах шифрування, хоча і отримав менше поширення, ніж Blowfish.
Опис алгоритму Twofish розбиває вхідний 128-бітний блок даних на чотири 32-бітних підблоки, над якими, після процедури вхідного відбілювання (input whitening), проводиться 16 раундів перетворень. Після останнього раунду виконується вихідна відбілювання (output whitening).
Відбілювання (whitening) Відбілювання — це процедура xor'а даних з підключами перед першим раундом і після останнього раунду. Вперше ця техніка була використана в шифрі Khufu/Khare і, незалежно, Рональдом Рівестом () в алгоритмі шифрування DESX. Joe Killian (NEC) і Phillip Rogaway (Каліфорнійський університет) показали, що відбілювання дійсно ускладнює завдання пошуку ключа повним перебором (exhaustive key-search) в DESX J. Kilian and P. Rogaway rogaway/papers/desx.pdf «How to Protect DES Against Exhaustive Key Search» February 2, 2000 . Розробники Twofish стверджують 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, що в Twofish відбілювання також істотно ускладнює завдання підбору ключа, оскільки криптоаналітика не може дізнатися, які дані потрапляють на вхід функції F першого раунду.
Тим не менш, виявилися і негативні сторони. Цікаве дослідження провели фахівці дослідницького центру компанії IBM. Suresh Chari, Charanjit Jutla, Josyula R. Rao, Pankaj Rohatgi «A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards» , 1999 Вони виконали реалізацію алгоритму 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, причому обчислення проводяться в скінченному полі по модулю непривідного многочлена
MDS матриця — це така матриця над кінцевим полем K, що якщо взяти її як матрицю лінійного перетворення з простору у простір , то будь-які два вектори з простору виду (x, f (x)) будуть мати як мінімум m+1 відмінностей в компонентах. Тобто набір векторів вигляду (x, f (x)) утворює код, що володіє властивістю максимального рознесення (maximum distance separable code). Таким кодом, наприклад, є код Ріда-Соломона.
В Twofish властивість максимальної рознесеність матриці MDS означає, що загальна кількість змінних байт вектора a і вектора не менше п'яти. Іншими словами, будь-яка зміна тільки одного байта в a призводить до зміни всіх чотирьох байтів в b.
Криптоперетворення Адамара (Pseudo-Hadamar Transform, PHT) криптоперетворення Адамара — оборотне перетворення бітового рядка довжиною 2n. Рядок розбивається на дві частини a і b однакової довжини в 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 розбивається з перестановкою байт на два однакові блоки і . Потім за допомогою блоку і функції h шифрується значення 2 * i, а за допомогою блоку шифрується значення 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 ) по модулю непривідного многочлена . Матриця MDS має вигляд:
Перестановки q 0 і q 1 q 0 і q 1 - фіксовані перестановки 8 бітів вхідного байта x.
Байт x розбивається на дві 4-бітні половинки a 0 і b 0 , над якими проводяться наступні перетворення:
Тут - 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 байтів , де k = N / 64. Ці 8 * k байтів розбиваються на слова по чотири байти, і в кожному слові байти переставляються у зворотному порядку. У підсумку виходить 2 * k 32-бітних слова
Отримані 2 * k 32-бітних розбиваються на два вектора і розміром в k 32-бітових слів.
Підключі для i-го раунду обчислюються за формулами:
Функція g і S-box'и Функція g визначається через функцію h:
Вектор S, як і вектора M e і M o , теж формується з вихідного ключа і складається з k 32-бітових слів. Вихідні байти ключа розбиваються на k груп по вісім байт. Кожна така група розглядається як вектор з 8-ма компонентами і множиться на фіксовану RS матрицю розміром 4x8 байт. В результаті множення виходить вектор, що складається з чотирьох байт. Обчислення проводяться в полі Галуа по модулю непріводімогомногочлена . RS-матриця має вигляд:
Криптоаналіз
Вивчення Twofish зі скороченими числом раундів показало, що алгоритм володіє великим запасом міцності, і, в порівнянні з іншими фіналістами конкурсу AES, він виявився найстійкішим. Проте його незвичайна структура і відносна складність породили деякі сумніви щодо якості цієї міцності.
Нарікання викликало розділення вихідного ключа на дві половини при формуванні раундових підключів. Криптографи Fauzan Mirza і Sean Murphy припустили, що такий поділ дає можливість організувати атаку за принципом «розділяй і володарюй», тобто розбити задачу на дві аналогічні, але простіші Fauzan Mirza, Sean Murphy «An Observation on the Key Schedule of Twofish» - Information Security Group, Royal Holloway, University of London - January 26, 1999. Однак реально подібну атаку провести не вдалося.
На 2008 рік найкращим варіантом криптоаналізу Twofish є варіант усіченого диференціального криптоаналізу, який був опублікований Shiho Moriai і Yiqun Lisa Yin в Японії в 2000 році Shiho Moriai, Yiqun Lisa Yin / twofish-analysis-shiho.pdf «Cryptanalysis of Twofish (II)» - The Institute of Economics, Information and Communication Engineers. Вони показали, що для знаходження необхідних диференціалів потрібно 2 51 підібраних відкритих текстів. Проте дослідження мали теоретичний характер, жодної реальної атаки проведено не було. У своєму блозі творець Twofish Брюс Шнайєр стверджує, що в реальності провести таку атаку неможливо Bruce Schneier «Twofish Cryptanalysis Rumors» blog.