Trivium (шифр)

Структура шифру Trivium

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

Шифр був представлений в грудні 2008 року як частина портфоліо європейського проекту eSTREAM, за профілем 2 (апаратно-орієнтовані шифри). Авторами шифру є Крістоф Де Канньєр і Барт Пренел.

Даний потоковий шифр генерує аж до $2^{64}$ біт вихідного потоку з 80 біт ключа і 80 біт IV (вектора ініціалізації). Це — найпростіший шифр проекту eSTREAM, який показує відмінні результати по криптостійкості.

Trivium включений в стандарт ISO/IEC 29192-3 як легкий потоковий шифр.

Опис

Початковий стан Trivium являє собою 3 зсувних регістри сумарної довжини в 288 біт. Кожен такт відбувається зміна бітів в регістрах зсуву шляхом нелінійної комбінації прямого і зворотного зв'язку. Для ініціалізації шифру ключ K і ініціалізувалися вектор IV записуються в 2 з 3х регістрів і відбувається виконання алгоритму протягом 4х288 = 1152 раз, що гарантує залежність кожного біта початкового стану від кожного біта ключа і кожного біта ініціалізувального вектора.

Після проходження стадії ініціалізації кожен такт генерується новий член ключового потоку Z, який проходить процедуру XOR з наступним членом тексту. Процедура розшифровки відбувається в зворотному порядку — кожен член шифротексту проходить процедуру XOR з кожним членом ключового потоку Z.

Алгоритм

Потокові шифри

Trivium генерує послідовність Z, так званий ключовий потік, довгою аж до $N\le 2^{64}$ біт. Для шифрування повідомлення необхідно провести операцію XOR від повідомлення і ключового потоку. Розшифровка проводиться аналогічним чином виконується операція XOR від шифротексту і ключового потоку.

Ініціалізація

Алгоритм ініціалізується завантаженням 80 бітного ключа і 80 бітного ініціалізуючого вектора в 288 бітний початковий стан. Ініціалізація може бути описана наступним псевдокодом.

$(s_1,s_2,...,s_{93})\leftarrow (K_1,...,K_{80},0,...,0)$

$(s_{94},s_{95},...,s_{177})\leftarrow (I{V}_1,...,I{V}_{80},0,...,0)$

$(s_{178},s_{179},...,s_{288})\leftarrow (0,...0,1,1,1)$

$\text{for}i=1\text{to}4\cdot 288\text{do}$

$t_1\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171}$

$t_2\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264}$

$t_3\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69}$

$(s_1,s_2,...,s_{93})\leftarrow (t_3,s_1,...,s_{92})$

$(s_{94},s_{95},...,s_{177})\leftarrow (t_1,s_{94},...,s_{176})$

$(s_{178},s_{179},...,s_{288})\leftarrow (t_2,s_{178},...,s_{287})$

$\text{end for}$

Процедура ініціалізації гарантує те, що кожен біт початкового стану залежить від кожного біта ключа і кожного біта не ініціалізуючого вектора. Даний ефект досягається вже після 2х повних проходів (2 * 288 виконань циклу). Ще 2 проходи призначені для ускладнення бітових взаємозв'язків. Для прикладу перші 128 байт ключового потоку Z, отриманого від нульового ключа і ініціалізуючого вектора, мають приблизно однакову кількість рівномірно розподілених 1 і 0. Навіть при найпростіших і однакових ключах алгоритм Trivium видає послідовність чисел, близьку до випадкової.

Робота алгоритму

Генератор потоку використовує 15 біт з 288битного початкового стану для зміни 3х біт стану та обчислення 1 біта ключового потоку $z_i$. В результаті роботи алгоритму може бути отримано до $N\le 2^{64}$ біт ключового потоку. Алгоритм може бути описаний наступним псевдокодом.

$\text{for}i=1\text{to}N\text{do}$

$t_1\leftarrow s_{66}+s_{93}$

$t_2\leftarrow s_{162}+s_{177}$

$t_3\leftarrow s_{243}+s_{288}$

$z_i\leftarrow t_1+t_2+t_3$

$t_1\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171}$

$t_2\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264}$

$t_3\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69}$

$(s_1,s_2,...,s_{93})\leftarrow (t_3,s_1,...,s_{92})$

$(s_{94},s_{95},...,s_{177})\leftarrow (t_1,s_{94},...,s_{176})$

$(s_{178},s_{179},...,s_{288})\leftarrow (t_2,s_{178},...,s_{287})$

$\text{end for}$

В даному псевдокоді всі обчислення проводяться за модулем 2. Тобто операції додавання і множення є операціями XOR і AND.

Період

Період ключового потоку складно визначити, за нелінійного характеру змін початкового стану. Навіть якщо відкрити всі тригери AND, що призведе до повністю лінійною схемою, можна показати, що будь-яка пара ключа і ініціалізуючого вектора приведе до генерації ключового потоку з періодом порядку $2^{96-3}-1$ (що вже перевершує необхідну довжину ключового потоку $2^{64}$).

Якщо ж припустити, що Trivium починає генерувати випадковий ключовий потік, після невеликої кількості ітерацій, то всі згенеровані послідовності, довжиною до $2^{288}$ будуть рівноймовірні. А також ймовірність того, що пара ключ/ініціалізувалися вектор згенерують ключовий потік з періодом менше, ніж $2^{80}$ буде порядку $2^{-208}$.

Шифри сімейства Trivium

Модифікації даного шифру відрізняються кількістю регістрів зсуву і їх довжинами.

Univium

Шифр Univium складається з одного регістра зсуву, для кодування необхідний тільки ключ довжиною, що не перевищує довжину регістра.

Bivium

Разом з Trivium його автори запропонували шифр Bivium, в якому реалізовані тільки 2 зсувних регістра сумарної довжини 177 біт. Процес ініціалізації аналогічний Trivium. Кожен такт змінюються 2 біти стану і формується новий біт ключового потоку. По генерації ключового потоку Z розрізняють 2 версії: Bivium-A і Bivium-B(Bivium). У Bivium-A реалізована пряма залежність нового члена Z від зміненого стану біта $z_i\leftarrow t_1$, на відміну від неї в Bivium-B (Bivium) $z_i\leftarrow t_1+t_2$.

Trivium-toy і Bivium-toy

Toy-версії були отримані шляхом зменшення довжин регістрів, що дозволило знизити обчислювальну складність алгоритму, при цьому зберігаючи всі математичні властивості. Довжина кожного регістра скорочувалася в 3 рази, причому Bivium-toy також складалася лише з двох регістрів.

Кожна модифікація шифру Trivium створена для спрощення його математичного опису, що має більше навчальну мету, ніж мету застосувати їх у засобах захисту інформації.

Продуктивність

Стандартна апаратна реалізація алгоритму вимагає наявності 3488 логічних елементів і виробляє 1 біт ключового потоку за 1 такт. Але, так як кожний новий стан біта не змінюється принаймні протягом 64 раундів, то ще 64 стану можуть бути згенеровані паралельно при збільшенні кількості логічних елементів до 5504. Також можливі різні варіації продуктивності в залежності від кількості використаних елементів.

Програмна інтерпретація даного алгоритму також досить ефективна. Реалізація Trivium на мові C на процесорі AthlonXP 1600+ дозволяє отримати швидкість шифрування понад 2,4 Мбіт/с

Захищеність

На відміну від ранніх потокових шифрів, як наприклад RC4, алгоритм Trivium, крім закритого ключа (K) також має ініціалізуючий вектор (IV), який є відкритим ключем. Застосування IV дозволяє проводити безліч незалежних сеансів шифрування/розшифрування використовуючи всього лише 1 ключ і кілька ініціалізуючих векторів (по одному для кожного сеансу). Також можна використовувати кілька ініціалізуючих векторів для одного сеансу, використовуючи для кожного нового повідомлення новий IV

В даний момент не відомо жодних методів атаки на даний алгоритм, які були б ефективніше послідовного перебору (або брутфорса (Шаблон:Lang-en)). Складність проведення даної атаки залежить від довжини повідомлення і становить близько $2^{120}$.

Існують дослідження методів атак (наприклад кубічна атака), які близькі по ефективності до перебору. Крім того, існує метод атаки, що дозволяє відновити K з IV і ключового потоку. Складність даної атаки дорівнює $2^{135}$ і незначно зменшується при збільшенні кількості инициализирующих векторів, що використовувалися з одним ключем. Можливі також атаки з дослідженням псевдовипадковою послідовності ключового потоку з метою знаходження закономірностей і передбачення подальших біт потоку, але дані атаки вимагають вирішення складних нелінійних рівнянь. Найменша отримана складність такої атаки становить $2^{164}$

Методи дослідження

Практично всі досягнення в області злому Trivium являють собою спроби застосувати атаки, вдало проведені на усічених версіях алгоритму. Найчастіше, досліджуваним використовується версія алгоритму Bivium, в якому використовується лише 2 зсувних регістра сумарної довжини 192 біта.

Посилання

• Trivium на сторінці проекту eSTREAM Шаблон:Webarchive
• Опис алгоритму на сторінці проекту eSTREAM Шаблон:Webarchive
• Принципи побудови потокових шифрів Шаблон:Webarchive