В криптографії XTEA eXtended TEA блочний шифроалгоритм покликаний усунути критичні помилки алгоритму TEA Розробниками ши

В криптографії, XTEA (eXtended TEA) — блочний шифроалгоритм, покликаний усунути критичні помилки алгоритму TEA. Розробниками шифру є Девід Вілер і Роджер Нідгем (факультет комп'ютерних наук Кембриджського університету). Алгоритм був представлений в невиданий технічному звіті в 1997 році. Шифр не запатентований, широко використовується в ряді криптографічних додатків і широкому спектрі апаратного забезпечення завдяки вкрай низькими вимогами до пам'яті і простоті реалізації.

XTEA
Деталі шифру

Розробники	Девід Уілер і Роджер Нідгем
Уперше оприлюднений	1997 р
Розмір ключа	128 біт
Розмір блоку	64 біт
Раундів	64
Тип	Мережа Фейстеля

Властивості шифру

Як і TEA, шифр заснований на операціях з 64-бітним блоком, має 32 повних цикли, в кожному повному циклі за два раунди Мережі Фейстеля, що означає 64 раунди мережі Фейстеля. Однак, кількість раундів для досягнення кращої дифузії може бути збільшено на шкоду продуктивності. Крім того в XTEA, як і в TEA, використовується 128-бітний ключ, який складається з чотирьох 32-бітних слів K[0], K[1], K[2] і K[3]. У XTEA немає алгоритму планування ключів у звичному розумінні. Для того, щоб визначити який з чотирьох слів ключа використовувати в кожному раунді, в алгоритмі використовується константа δ = 9E3779B9₁₆. В TEA ж такого розподілу немає. Ще однією відмінністю від TEA є перестановка бітових операцій, які використовуються в шифрі. Завдяки цим удосконаленням XTEA не зазнав сильних ускладнень порівняно з TEA, але в той же час ліквідував два основних недоліки алгоритму TEA:

кожен ключ в TEA еквівалентний трьом іншим, що означає, що ефективна довжина ключа складає 126 біт замість 128, як це було задумано розробниками;
TEA сприйнятливий до атак на пов'язаних ключах. Така атака може вимагати лише 2²³ обраного відкритого тексту і мати тимчасову складність що дорівнює 2³².

Опис алгоритму

В роботі XTEA застосовуються такі логічні операції: виключаюче «АБО», бітовий зсув і логічне «І». Крім того в XTEA використовується операція додавання цілих чисел по модулю 2³², які позначають як x $\boxplus$ y (x і y $\in$ Z_2³²). Виключне «АБО» в булевій логіці позначається як x $\oplus$ y, а в мові Сі як x ^ y. Логічне «І» в булевій логіці — x $\land$ y в мові Сі — x & y. Логічний зсув x на y біт вліво позначається як x $\ll$ y, а логічний зсув x на y біт вправо позначається як x $\gg$ y. Нехай на вхід n-го (1 ≤ n ≤ 64) раунду алгоритму подається (L_n,R_n), а на виході виходить (L_n+1,R_n+1), причому L_n+1 = R_n. R_n+1 обчислюється наступним чином:

якщо n = 2 * i — 1 для 1 ≤ i ≤ 32, R_n+1 = L_n + ({ (R_n $\ll$ 4 $\oplus$ R_n $\gg$ 5) $\boxplus$ R_n } $\oplus$ ({ i — 1 } * δ $\boxplus$ K [ ({ i — 1 } * δ) $\land$ 3 ]),

якщо n = 2 * i для 1 ≤ i ≤ 32, R_n+1 = L_n + ({ (R_n $\ll$ 4 $\oplus$ R_n $\gg$ 5) $\boxplus$ R_n } $\oplus$ (i * δ $\boxplus$ K [ (i * δ $\gg$ 11) $\land$ 3 ]).

Так як це блочний шифроалгоритм, де довжина блоку 64-біт, а довжина даних може бути не кратна 64-біт, значення всіх байтів доповнюють блок до кратності в 64-біт встановлюється в 0x01.

Криптоаналіз алгоритму

Вважається що XTEA більше захищений, ніж ТЕА, проте можна підібрати такий тип атак для яких XTEA більш вразливий. Перший підхід — це диференціальні атаки. Так як TEA використовує додавання по модулю 2³² ключа раунду і відкритого тексту, що подається на вхід, а XTEA використовує виключаюче «АБО», то простіше проводити диференціальну атаку на XTEA, ніж на TEA. Після 14 раундів XTEA можна побудувати з імовірністю 2^-57.79диференціальну характеристику і використовувати її для злому XTEA включає в себе 16 раундів (дана атака вимагає 2⁶¹ обраних відкритих текстів). У той же час для TEA важко побудувати хорошу диференціальну характеристику. Другий підхід усічена диференціальна атака. Після 8 раундів TEA і XTEA можна побудувати усічену диференціальну характеристику з ймовірністю 1. За допомогою цієї атаки можна зламати XTEA з максимальною кількістю раундів — 23 і TEA з максимальною кількістю раундів — 17. Таке розходження спостерігається через властивості планування ключів в кожному з алгоритмів.

Найбільш успішна з опублікованих атак на XTEA — це диференційна атака на пов'язаних ключах, яка здатна зламати 37 з 64 раундів алгоритму, використовуючи 2⁶³ обраних відкритих текстів з тимчасової складністю 2¹²⁵. Якщо розглядати підмножина слабких ключів, в яке входять 2^107.5 ключів з 2¹²⁸, то ця пані атака здатна зламати 51 з 64 раундів алгоритму з тимчасової складністю 2¹²³.

Приклад реалізації алгоритму

Реалізація на мові Сі (адаптований варіант коду, представленого в статті Девіда Уїлера та Роджера Нидхема) шифрування і розшифрування з використанням алгоритму 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[0], v1=v[1], 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[0]=v0; v[1]=v1; } void xtea_decipher(unsigned int num_rounds, uint32_t *v, uint32_t const *k) {  unsigned int i;  uint32_t v0=v[0], v1=v[1], 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[0]=v0; v[1]=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-3 (Ст. Денис). Втім, дані модифікації не були настільки широко досліджені і не одержали достатнього практичного застосування.

Алгоритм 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[0] + k[0]; z = v[1] + k[1]; /* 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[0] = y ^ k[2]; v[1] = z ^ k[3]; } 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[1] ^ k[3]; y = v[0] ^ k[2]; 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[1] = z - k[1]; v[0] = y - k[0]; }

Функція '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[0]; b = v[1] + k[0]; c = v[2]; d = v[3] + k[1]; 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[0] = a ^ k[2]; v[1] = b; v[2] = c ^ k[3]; v[3] = 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[3]; c = v[2] ^ k[3]; b = v[1]; a = v[0] ^ k[2]; 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[0] = a; v[1] = b - k[0]; v[2] = c; v[3] = d - k[1]; }

Основна перевага цього алгоритму — це можливість шифрувати великі блоки. Цей алгоритм використовує ті ж базові операції що і 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[0] + k[0]; b = v[1] + k[1]; c = v[2] + k[2]; d = v[3] + k[3]; 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[0] = a ^ k[4]; v[1] = b ^ k[5]; v[2] = c ^ k[6]; v[3] = d ^ k[7]; }   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[3] ^ k[7]; c = v[2] ^ k[6]; b = v[1] ^ k[5]; a = v[0] ^ k[4]; 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[3] = d - k[3]; v[2] = c - k[2]; v[1] = b - k[1]; v[0] = a - k[0]; }

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

Порівняння різних версій розширення XTEA

Ці три алгоритму є природними розширеннями TEA і XTEA. Їх відмінними рисами порівняно з оригінальними алгоритмами шифрування є кращий розклад ключів і більший розмір блоків і/або ключів. Використання ключів, динамічно залежних від відкритого тексту, означає, що не існує заздалегідь встановленого порядку для використання ключів і не потрібно виділення пам'яті. Це досить корисна властивість, так як завдання виявлення ключів, що використовуються найбільш часто, ускладнюється. Шифри володіють більшою захищеністю до диференціального криптоаналізу, так як біти в ключі можуть впливати на будь-які інші біти шифротексту. Використання нелінійної алгебри (додавання по модулю 2³², виключаюче «АБО») ефективно проти лінійного криптоананлиза. Крім того використання цих операцій не вносить вразливостей в алгоритми.

Перший алгоритм (XTEA-1) має найбільшу швидкість і при достатній кількості раундів (від 32 до 64) володіє хорошою надійністю. XTEA-2 являє собою розширення з великим розміром блоку, і він не більш захищений ніж XTEA-1. XTEA-3 — це розширення алгоритм з використанням більшого розміру блоку і ключа. Третій варіант працює трохи повільніше, але більш захищений. Так як ці алгоритми побудовані на базі оригінального TEA з усуненням всіх відомих недоліків, то їх можна вважати достатньо надійними.

Порівняльна таблиця алгоритмів:

Назва алгоритму	Мінімальна кількість раундів	Максимальна кількість раундів	Розмір блоку	Розмір ключа
XTEA-1	32	64	64 біта	128 біт
XTEA-2	64	128	128 біт	128 біт
XTEA-3	64	128	128 біт	256 біт

Однак дані алгоритми все одно потребують подальшої доробки. Перша проблема полягає в тому, тільки молодші біти відкритого тексту використовуються для циклічного бітового зсуву ключа (як у XTEA-1 і XTEA-2). Друга проблема полягає в тому, що ключ розділений на дві підгрупи по 4 елемента, і кожна частина виразу використовує тільки одну підгрупу (як у XTEA-3). XTEA-3 може бути розширено шляхом використання всіх восьми елементів в обох частинах висловлювання. Якщо ці вдосконалення будуть проведені, то алгоритм стане більш практичним, але тоді він буде дуже сильно відрізнятися від оригінального TEA.

Примітки

А. Roger M. Needham and David J. Wheeler. Tea extensions [ 20 вересня 2017 у Wayback Machine.]
John Kelsey, Bruce Schneier, David Wagner. Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, TEA^{[недоступне посилання з листопадаа 2019]}
Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee. Differential Cryptanalysis of TEA and XTEA^{[недоступне посилання з листопадаа 2019]}
Charles Bouillaguet, Orr Dunkelman, Gaetan Leurent, and Pierre-Alain Fouque. Another Look at Complementation Properties [ 6 липня 2017 у Wayback Machine.]
Tom St Denis. Extended TEA Algorithms [ 27 серпня 2018 у Wayback Machine.]

Дивись також

Посилання

David J. Wheeler Roger and M. Needham. «Correction to xtea.» Technical report, Computer Laboratory, University of Cambridge, October 1998 (PDF) [ 20 вересня 2017 у Wayback Machine.].
Dukjae Moon, Kyungdeok Hwang, Wonil Lee, Sangjin Lee and Jongin Lim. «Impossible Differential Криптоаналіз of Reduced Round XTEA and TEA.» Center for Information and Security Technologies(CIST), 2004 (PDF)^{[недоступне посилання з листопадаа 2019]}.

Реалізації

The Tiny Encryption Algorithm (TEA) [ 12 червня 2017 у Wayback Machine.], Simon Shepherd, 24 February 2006 — Вебсторінка з описом і посиланнями на різні реалізації XTEA
Реалізація XTEA на PHP [ 13 листопада 2015 у Wayback Machine.]
Реалізація XTEA на Java (32 проходу) [ 9 квітня 2016 у Wayback Machine.]
Python XTEA Encryption (Python recipe) [ 18 серпня 2016 у Wayback Machine.] — Реалізація XTEA на Python
Реалізація XTEA на Verilog [ 2 серпня 2017 у Wayback Machine.] (для FPGA)
Звернення до реалізації алгоритмів XTEA-1, XTEA-2, XTEA-3 на C з Python [ 11 червня 2018 у Wayback Machine.]

[report-1] А. Roger M. Needham and David J. Wheeler. Tea extensions [ 20 вересня 2017 у Wayback Machine.]

[tea_crypt-2] John Kelsey, Bruce Schneier, David Wagner. Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, TEA^{[недоступне посилання з листопадаа 2019]}

[differential-3] Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee. Differential Cryptanalysis of TEA and XTEA^{[недоступне посилання з листопадаа 2019]}

[4] Charles Bouillaguet, Orr Dunkelman, Gaetan Leurent, and Pierre-Alain Fouque. Another Look at Complementation Properties [ 6 липня 2017 у Wayback Machine.]

[extended-5] Tom St Denis. Extended TEA Algorithms [ 27 серпня 2018 у Wayback Machine.]