В криптографії, XTEA (eXtended TEA) — блочний шифроалгоритм, покликаний усунути критичні помилки алгоритму TEA. Розробниками шифру є Девід Вілер і Роджер Нідгем (факультет комп'ютерних наук Кембриджського університету). Алгоритм був представлений в невиданий технічному звіті в 1997 роціА. Roger M. Needham and David J. Wheeler. Tea extensions . Шифр не запатентований, широко використовується в ряді криптографічних додатків і широкому спектрі апаратного забезпечення завдяки вкрай низькими вимогами до пам'яті і простоті реалізації.
Властивості шифру Як і TEA, шифр заснований на операціях з 64-бітним блоком, має 32 повних цикли, в кожному повному циклі за два раунди Мережі Фейстеля, що означає 64 раунди мережі Фейстеля. Однак, кількість раундів для досягнення кращої дифузії може бути збільшено на шкоду продуктивності. Крім того в XTEA, як і в TEA, використовується 128-бітний ключ, який складається з чотирьох 32-бітних слів K, K, K і K. У XTEA немає алгоритму планування ключів у звичному розумінні. Для того, щоб визначити який з чотирьох слів ключа використовувати в кожному раунді, в алгоритмі використовується константа δ = 9E3779B916. В TEA ж такого розподілу немає. Ще однією відмінністю від TEA є перестановка бітових операцій, які використовуються в шифрі. Завдяки цим удосконаленням XTEA не зазнав сильних ускладнень порівняно з TEA, але в той же час ліквідував два основних недоліки алгоритму TEA:
кожен ключ в TEA еквівалентний трьом іншим, що означає, що ефективна довжина ключа складає 126 біт замість 128, як це було задумано розробниками; TEA сприйнятливий до атак на пов'язаних ключах. Така атака може вимагати лише 223 обраного відкритого тексту і мати тимчасову складність що дорівнює 232John Kelsey, Bruce Schneier, David Wagner. Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, TEA.
Опис алгоритму В роботі XTEA застосовуються такі логічні операції: виключаюче «АБО», бітовий зсув і логічне «І». Крім того в XTEA використовується операція додавання цілих чисел по модулю 232, які позначають як x y (x і y Z232). Виключне «АБО» в булевій логіці позначається як x y, а в мові Сі як x ^ y. Логічне «І» в булевій логіці — x y в мові Сі — x & y. Логічний зсув x на y біт вліво позначається як x y, а логічний зсув x на y біт вправо позначається як x y. Нехай на вхід n-го (1 ≤ n ≤ 64) раунду алгоритму подається (Ln,Rn), а на виході виходить (Ln+1,Rn+1), причому Ln+1 = Rn. Rn+1 обчислюється наступним чином:
якщо n = 2 * i — 1 для 1 ≤ i ≤ 32, Rn+1 = Ln + ({ (Rn 4 Rn 5) Rn } ({ i — 1 } * δ K [ ({ i — 1 } * δ) 3 ]),
якщо n = 2 * i для 1 ≤ i ≤ 32, Rn+1 = Ln + ({ (Rn 4 Rn 5) Rn } (i * δ K [ (i * δ 11) 3 ]).
Так як це блочний шифроалгоритм, де довжина блоку 64-біт, а довжина даних може бути не кратна 64-біт, значення всіх байтів доповнюють блок до кратності в 64-біт встановлюється в 0x01.
Криптоаналіз алгоритму Вважається що XTEA більше захищений, ніж ТЕА, проте можна підібрати такий тип атак для яких XTEA більш вразливийSeokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee. Differential Cryptanalysis of TEA and XTEA. Перший підхід — це диференціальні атаки. Так як TEA використовує додавання по модулю 232 ключа раунду і відкритого тексту, що подається на вхід, а XTEA використовує виключаюче «АБО», то простіше проводити диференціальну атаку на XTEA, ніж на TEA. Після 14 раундів XTEA можна побудувати з імовірністю 2-57.79 диференціальну характеристику і використовувати її для злому XTEA включає в себе 16 раундів (дана атака вимагає 261 обраних відкритих текстів). У той же час для TEA важко побудувати хорошу диференціальну характеристику. Другий підхід усічена диференціальна атака. Після 8 раундів TEA і XTEA можна побудувати усічену диференціальну характеристику з ймовірністю 1. За допомогою цієї атаки можна зламати XTEA з максимальною кількістю раундів — 23 і TEA з максимальною кількістю раундів — 17. Таке розходження спостерігається через властивості планування ключів в кожному з алгоритмів.
Найбільш успішна з опублікованих атак на XTEA — це диференційна атака на пов'язаних ключах, яка здатна зламати 37 з 64 раундів алгоритму, використовуючи 263 обраних відкритих текстів з тимчасової складністю 2125. Якщо розглядати підмножина слабких ключів, в яке входять 2107.5 ключів з 2128, то ця пані атака здатна зламати 51 з 64 раундів алгоритму з тимчасової складністю 2123Charles Bouillaguet, Orr Dunkelman, Gaetan Leurent, and Pierre-Alain Fouque. Another Look at Complementation Properties .
Приклад реалізації алгоритму Реалізація на мові Сі (адаптований варіант коду, представленого в статті Девіда Уїлера та Роджера Нидхема) шифрування і розшифрування з використанням алгоритму XTEA: #include <stdint.h>
void xtea_encipher(unsigned int num_rounds, uint32_t *v, uint32_t const *k) { unsigned int i; uint32_t v0=v, v1=v, sum=0, delta=0x9E3779B9; for (i=0; i < num_rounds; i++) { v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]); sum += delta; v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
v=v0; v=v1; }
void xtea_decipher(unsigned int num_rounds, uint32_t *v, uint32_t const *k) { unsigned int i; uint32_t v0=v, v1=v, delta=0x9E3779B9, sum=delta*num_rounds; for (i=0; i < num_rounds; i++) { v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]); sum -= delta; v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
v=v0; v=v1; } Коментарі:
v — початковий текст складається з двох слів по 32 біта k — ключ складається з чотирьох 32-бітних слів num_rounds — число циклів алгоритму (рекомендується 32) num_rounds має бути однаковим для шифрування і розшифрування, якщо num_rounds==0 то ні шифрування, ні розшифрування відбуватися не буде
Зміни у порівнянні з оригінальним кодом:
використовується тип uint32_t внаслідок того, що він завжди має розмір 32 біта на відміну від long (присутній в оригінальному коді), який може містити 64 біта (наприклад в деяких 64-бітних системах) вихідний код не використовує тип const у вихідному коді опущені надлишкові дужки у виразах для v0 і v1, в даній модифікації вони залишені для більшої наочності
Версії алгоритму Виявлені вразливості в ключовому розкладі і наявність успішних атак на алгоритми TEA, XTEA і XXTEA призвели до створення поряд криптоаналітиків альтернативних варіантів шифру. Зокрема, на даний момент існують засновані на шифрах колекції TEA алгоритми RTEA (Шон о ' Ніл), Raiden (Хуліо Кастро), XTEA-1, XTEA-2 і XTEA-3Tom St Denis. Extended TEA Algorithms (Ст. Денис). Втім, дані модифікації не були настільки широко досліджені і не одержали достатнього практичного застосування.
Алгоритм XTEA-1 Одна з вразливостей XTEA полягає в тому, що біти в ключі впливають на одні й ті ж біти в кожному раунді алгоритму. Ця проблема може бути вирішена шляхом використання шифру, що включає в себе алгоритм розкладу ключів. Планування ключів проводиться динамічно і не потребує виділення пам'яті. Розклад ключів здійснюється шляхом циклічного бітового зсуву ключа на значення, залежне від відкритого тексту. Алгоритм XTEA-1 реалізує цю ідею щодо посилення шифру XTEA шляхом незначної зміни структури шифру без зміни основних принципів алгоритму.
Шифр використовує технологію забеливания і залежну від даних трансформацію підключа, що ускладнює криптоаналіз, оскільки вихідний алгоритм містив вразливість — модифікація певних біт ключа відбивалася на відповідних бітах шіфротекста.
Реалізація XTEA-1 на мові Сі: #include <stdint.h>
uint32_t rol(uint32_t base, uint32_t shift) { uint32_t res; /* only 5 bits of shift are significant*/ shift &= 0x1F; res = (base << shift) | (base >> (32 - shift)); return res; }
void xtea1_encipher(unsigned int num_rounds,uint32_t *v, uint32_t const *k) { unsigned int i; uint32_t y, z, sum=0, delta=0x9E3779B9; /* load and pre-white the registers */ y = v + k; z = v + k; /* Round functions */ for (i = 0; i < num_rounds; i++) { y += ((z << 4) ^ (z >> 5)) + (z ^ sum) + rol(k[sum & 3], z); sum += delta; z += ((y << 4) ^ (y >> 5)) + (y ^ sum) + rol(k[(sum >> 11) & 3], y); } /* post-white and store registers */ v = y ^ k; v = z ^ k; }
void xtea1_decipher(unsigned int num_rounds,uint32_t *v, uint32_t const *k) { unsigned int i; uint32_t y, z,delta=0x9E3779B9,sum=delta*num_rounds; z = v ^ k; y = v ^ k; for (i = 0; i < num_rounds; i++) { z -= ((y << 4) ^ (y >> 5)) + (y ^ sum) + rol(k[(sum >> 11) & 3], y); sum -= delta; y -= ((z << 4) ^ (z >> 5)) + (z ^ sum) + rol(k[sum & 3], z);
v = z - k; v = y - k; }
Функція 'rol' виконує циклічний бітовий зсув ключа, використовуючи 5 молодших бітів змінної shift. Цей алгоритм використовує лише один зсув за раунд, що досить ефективно і швидко працює на більшості сучасних процесорах.
Алгоритм XTEA-2 Можна змінити XTEA-1 використовуючи 128 бітний блок. Отриманий алгоритм вимагає більше раундів, але швидкість шифрування у нього вище, ніж у XTEA.
Реалізація XTEA-2 на Сі:#include <stdint.h>
void xtea2_encipher(unsigned int num_rounds,uint32_t *v, uint32_t const *k){ unsigned int i; uint32_t a, b, c, d, sum=0, t,delta=0x9E3779B9; a = v; b = v + k; c = v; d = v + k; for (i = 0; i < num_rounds; i++) { a += ((b << 4) ^ (b >> 5)) + (d ^ sum) + rol(k[sum & 3], b); sum += delta; c += ((d << 4) ^ (d >> 5)) + (b ^ sum) + rol(k[(sum >> 11) & 3], d); t = a; a = b; b = c; c = d; d = t; } v = a ^ k; v = b; v = c ^ k; v = d; }
void xtea2_decipher(unsigned int num_rounds,uint32_t *v, uint32_t const *k){ unsigned int i; uint32_t a, b, c, d, t, delta=0x9E3779B9, sum=delta*num_rounds; d = v; c = v ^ k; b = v; a = v ^ k; for (i = 0; i < num_rounds; i++) { t = d; d = c; c = b; b = a; a = t; c -= ((d << 4) ^ (d >> 5)) + (b ^ sum) + rol(k[(sum >> 11) & 3], d); sum -= delta; a -= ((b << 4) ^ (b >> 5)) + (d ^ sum) + rol(k[sum & 3], b); } v = a; v = b - k; v = c; v = d - k; }Основна перевага цього алгоритму — це можливість шифрувати великі блоки. Цей алгоритм використовує ті ж базові операції що і XTEA-1, але вимагає більше ітерацій. Насправді він вимагає в два рази більше ітерацій від 32 до 64 (від 64 до 128 раундів). 48 ітерацій — це компроміс між швидкістю і надійністю шифрування.
Алгоритм XTEA-3 Ще одне природне розширення XTEA-1 — це використання 256 бітного ключа і більш практичного 128 бітного блоку. Цей алгоритм вимагає від 32 до 64 ітерацій, але в той же час забезпечує надійний захист від атак шляхом повного перебору. Шифр використовує технологію забеливания і реалізує операції, залежні від ключа, що ускладнює криптоаналіз.
Реалізація XTEA-3 на Сі:#include <stdint.h>
void xtea3_encipher(unsigned int num_rounds,uint32_t *v, uint32_t const *k) { unsigned int i; uint32_t a, b, c, d, sum=0, t,delta=0x9E3779B9; sum = 0; a = v + k; b = v + k; c = v + k; d = v + k; for (i = 0; i < num_rounds; i++){ a += (((b << 4) + rol (k[(sum % 4) + 4], b)) ^ (d + sum) ^ ((b >> 5) + rol (k[sum % 4], b >> 27))); sum += delta; c += (((d << 4) + rol (k[((sum >> 11) % 4) + 4], d)) ^ (b + sum) ^ ((d >> 5) + rol (k[(sum >> 11) % 4], d >> 27))); t = a;a = b;b = c;c = d;d = t; } v = a ^ k; v = b ^ k; v = c ^ k; v = d ^ k;
void xtea3_decipher(unsigned int num_rounds,uint32_t *v, uint32_t const *k) { unsigned int i; uint32_t a, b, c, d, t,delta=0x9E3779B9,sum = delta * num_rounds; d = v ^ k; c = v ^ k; b = v ^ k; a = v ^ k; for (i = 0; i < num_rounds; i++){ t = d;d = c;c = b;b = a;a = t; c -= (((d << 4) + rol (k[((sum >> 11) % 4) + 4], d)) ^ (b + sum) ^ ((d >> 5) + rol (k[(sum >> 11) % 4], d >> 27))); sum -= delta; a -= (((b << 4) + rol (k[(sum % 4) + 4], b)) ^ (d + sum) ^ ((b >> 5) + rol (k[sum % 4], b >> 27)));
v = d - k; v = c - k; v = b - k; v = a - k;