В криптографии, 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 более защищен, чем ТEA, однако можно подобрать такой тип атак для которых 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; }