XTEA

XTEA

Создатель:	Дэвид Уилер и Роджер Нидхэм
Создан:	1997 г.
Опубликован:	1997 г.
Размер ключа:	128 бит
Размер блока:	64 бит
Число раундов:	64
Тип:	Сеть Фейстеля

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

Свойства шифра

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

каждый ключ в TEA эквивалентен трем другим, что означает, что эффективная длина ключа составляет 126 бит вместо 128, как это было задумано разработчиками;
TEA восприимчив к атакам на связанных ключах. Такая атака может потребовать всего лишь 2²³ выбранного открытого текста и иметь временную сложность равную 2³²^[2].

Описание алгоритма

В работе XTEA применяются следующие логические операции: исключающее «ИЛИ», битовый сдвиг и логическое “И”. Кроме того в XTEA используется операция сложения целых чисел по модулю 2³², обозначающаяся как x y (x и y Z_2³²). Исключающее «ИЛИ» в булевой логике обозначается как x y, а в языке Си как x ^ y. Логическое “И” в булевой логике - x y в языке Си - x & y. Логический сдвиг x на y бит влево обозначается как x y , а логический сдвиг x на y бит вправо обозначается как x 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 4 R_n 5 ) R_n } ( { i - 1 } * δ K [ ( { i - 1 } * δ ) 3 ] ),

если n = 2 * i для 1 ≤ i ≤ 32, то R_n+1 = L_n + ( { ( R_n 4 R_n 5 ) R_n } ( i * δ K [ ( i * δ 11) 3 ] ).

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

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

Считается что XTEA более защищен, чем ТEA, однако можно подобрать такой тип атак для которых 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 - это дифференциальная атака на связанных ключах, которая способна взломать 27 из 64 раундов алгоритма. Она требует 2^20.5 выбранных открытых текстов и имеет временную сложность равную 2^115.15 ^[4].

Пример реализации алгоритма

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

Алгоритм 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.

Примечания

↑ Tea extensions
Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, TEA

Differential Cryptanalysis of TEA and XTEA

Related Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST

Extended TEA Algorithms

См. также

TEA

Сеть Фейстеля

Битовые операции

XXTEA

RTEA

Raiden

Различные реализации (внешние ссылки)

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

Ссылки

David J. Wheeler and Roger 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 Cryptanalysis of Reduced Round XTEA and TEA.» Center for Information and Security Technologies(CIST), 2004 (PDF).

Симметричные криптосистемы

Потоковые шифры

A3 • A5 • A8 • Decim • MICKEY • RC4 • Rabbit • SEAL • SOSEMANUK • Trivium • VMPC

Сеть Фейстеля

ГОСТ 28147-89 • Blowfish • Camellia • CAST-128 • CAST-256 • CIPHERUNICORN-A • CIPHERUNICORN-E • CLEFIA • Cobra • DFC • DEAL • DES • DESX • EnRUPT • FEAL • FNAm2 • HPC • IDEA • KASUMI • Khufu • LOKI97 • MARS • NewDES • Raiden • RC5 • RC6 • RTEA • SEED • Sinople • Skipjack • TEA • Triple DES • Twofish • XTEA • XXTEA

SP-сеть

3-WAY • ABC • AES (Rijndael) • Akelarre • Anubis • ARIA • BaseKing • BassOmatic • CRYPTON • Diamond2 • Grand Cru • Hierocrypt-L1 • Hierocrypt-3 • KHAZAD • Lucifer • Present • Rainbow • SAFER • Serpent • SHARK • SQUARE • Threefish

Другие

FROG • NUSH • REDOC • SHACAL • SC2000

Light-industry-up.ru

Экосистема промышленности

Публикации