XTEA

Як і 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³²[2].

В роботі XTEA застосовуються такі логічні операції: виключаюче «АБО», бітовий зсув і логічне «І». Крім того в XTEA використовується операція додавання цілих чисел по модулю 2³², які позначають як x ${\displaystyle }$ y (x і y ${\displaystyle }$ Z_2³²). Виключне «АБО» в булевій логіці позначається як x ${\displaystyle }$ y, а в мові Сі як x ^ y. Логічне «І» в булевій логіці — x ${\displaystyle }$ y в мові Сі — x & y. Логічний зсув x на y біт вліво позначається як x ${\displaystyle }$ y, а логічний зсув x на y біт вправо позначається як x ${\displaystyle }$ 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 ${\displaystyle }$ 4 ${\displaystyle }$ R_n ${\displaystyle }$ 5) ${\displaystyle }$ R_n } ${\displaystyle }$ ({ i — 1 } * δ ${\displaystyle }$ K [ ({ i — 1 } * δ) ${\displaystyle }$ 3 ]),

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

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

Вважається що XTEA більше захищений, ніж ТЕА, проте можна підібрати такий тип атак для яких XTEA більш вразливий[3]. Перший підхід — це диференціальні атаки. Так як 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¹²³[4].

Реалізація на мові Сі (адаптований варіант коду, представленого в статті Девіда Уїлера та Роджера Нидхема) шифрування і розшифрування з використанням алгоритму 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[5] (Ст. Денис). Втім, дані модифікації не були настільки широко досліджені і не одержали достатнього практичного застосування.

#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];
}

#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];
}

#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];
}

• TEA
• Мережа Фейстеля
• Бітові операції
• XXTEA
• RTEA
• Raiden

• David J. Wheeler Roger and M. Needham. «Correction to xtea.» Technical report, Computer Laboratory, University of Cambridge, October 1998 (PDF).
• 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), Simon Shepherd, 24 February 2006 — Вебсторінка з описом і посиланнями на різні реалізації XTEA
• Реалізація XTEA на PHP
• Реалізація XTEA на Java (32 проходу)
• Python XTEA Encryption (Python recipe) — Реалізація XTEA на Python
• Реалізація XTEA на Verilog (для FPGA)
• Звернення до реалізації алгоритмів XTEA-1, XTEA-2, XTEA-3 на C з Python