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^32[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 } * δ $\gg$ 11) $\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 более защищен, чем Т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-1 на языке Assembler (MASM32):

.const
Delta   equ     09E3779B9h      ;  Delta
DIS     equ     0C6EF3720h      ;  Initial value of sum in decipher routine
N       equ     32              ;  n (number of iterations) ... use it or not???
; ..........................................................................
.data
v dd 0, 0               ;  Data to be encrypted or decrypted
w dd ?, ?               ;  Results
k dd 0,0,0,0            ;  Key
Password    db      "1234567890123456"  ; Zero Teminated or not
PlainText   db      "bbbbbbbbhhhhhhhh", 0
; ..........................................................................
.code
Start:
XTEA1_Encipher  proc
                PUSHAD                          ; Save registers
                MOV     EAX, v[0 * 4]           ; EAX -> y
                MOV     EBX, v[1 * 4]           ; EBX -> z
                MOV     ECX, N                  ; ECX -> n
                XOR     EDX, EDX                ; EDX -> sum
EnStart:        MOV     ESI, EBX
                MOV     EDI, ESI
                SHL     ESI, 4                  ; z << 4
                SHR     EDI, 5                  ; z >> 5
                XOR     EDI, ESI                ; z << 4 ^ z >> 5
                ADD     EDI, EBX                ; (z << 4 ^ z >> 5) + z
                MOV     ESI, EDX
                AND     ESI, 3                  ; sum & 3
                MOV     ESI, k[ESI * 4]         ; k[sum & 3]
                ADD     ESI, EDX                ; sum + k[sum & 3]
                XOR     ESI, EDI                ; (z << 4 ^ z >> 5) + z ^ sum + k[sum & 3]
                ADD     EAX, ESI                ; y += (z << 4 ^ z >> 5) + z ^ sum + k[sum & 3]
                ADD     EDX, Delta              ; sum += delta
                MOV     ESI, EAX
                MOV     EDI, ESI
                SHL     ESI, 4                  ; y << 4
                SHR     EDI, 5                  ; y >> 5
                XOR     EDI, ESI                ; y << 4 ^ y >> 5
                ADD     EDI, EAX                ; (y << 4 ^ y >> 5) + y
                MOV     ESI, EDX
                SHR     ESI, 11                 ; sum >> 11
                AND     ESI, 3                  ; sum >> 11 & 3
                MOV     ESI, k[ESI * 4]         ; k[sum >> 11 & 3]
                ADD     ESI, EDX                ; sum + k[sum >> 11 & 3]
                XOR     ESI, EDI                ; (y << 4 ^ y >> 5) + y ^ sum + k[sum >> 11 & 3];
                ADD     EBX, ESI                ; z += (y << 4 ^ y >> 5) + y ^ sum + k[sum >> 11 & 3];
                LOOP    EnStart
                MOV     w[0 * 4], EAX
                MOV     w[1 * 4], EBX
                POPAD                           ; Restore registers
                RET
XTEA1_Encipher  endp
; ..........................................................................
XTEA1_Decipher  proc
                PUSHAD                          ; Save registers
                MOV     EAX, v[0 * 4]           ; EAX -> y
                MOV     EBX, v[1 * 4]           ; EBX -> z
                MOV     ECX, N                  ; ECX -> n
                MOV     EDX, DIS                ; EDX -> sum
DeStart:        MOV     ESI, EAX
                MOV     EDI, ESI
                SHL     ESI, 4                  ; y << 4
                SHR     EDI, 5                  ; y >> 5
                XOR     EDI, ESI                ; y << 4 ^ y >> 5
                ADD     EDI, EAX                ; (y << 4 ^ y >> 5) + y
                MOV     ESI, EDX
                SHR     ESI, 11                 ; sum >> 11
                AND     ESI, 3                  ; sum >> 11 & 3
                MOV     ESI, k[ESI * 4]         ; k[sum >> 11 & 3]
                ADD     ESI, EDX                ; sum + k[sum >> 11 & 3]
                XOR     ESI, EDI                ; (y << 4 ^ y >> 5) + y ^ sum + k[sum >> 11 & 3]
                SUB     EBX, ESI                ; z -= (y << 4 ^ y >> 5) + y ^ sum + k[sum >> 11 & 3]
                SUB     EDX, Delta              ; sum -= delta
                MOV     ESI, EBX
                MOV     EDI, ESI
                SHL     ESI, 4                  ; z << 4
                SHR     EDI, 5                  ; z >> 5
                XOR     EDI, ESI                ; z << 4 ^ z >> 5
                ADD     EDI, EBX                ; (z << 4 ^ z >> 5) + z
                MOV     ESI, EDX
                AND     ESI, 3                  ; sum & 3
                MOV     ESI, k[ESI * 4]         ; k[sum & 3]
                ADD     ESI, EDX                ; sum + k[sum & 3]
                XOR     ESI, EDI                ; (z << 4 ^ z >> 5) + z ^ sum + k[sum & 3]
                SUB     EAX, ESI                ; y -= (z << 4 ^ z >> 5) + z ^ sum + k[sum & 3]
                LOOP    DeStart
                MOV     w[0 * 4], EAX
                MOV     w[1 * 4], EBX
                POPAD                           ; Restore registers
                RET
XTEA1_Decipher  endp

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

Примечания

1. ↑ ^{1 2 3} А. Roger M. Needham and David J. Wheeler. Tea extensions
2. ↑ John Kelsey, Bruce Schneier, David Wagner. Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, TEA
3. ↑ Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee. Differential Cryptanalysis of TEA and XTEA
4. ↑ Youngdai Ko, Seokhie Hong, Wonil Lee, Sangjin Lee, Ju-Sung Kang. Related Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST
5. ↑ Tom St Denis. Extended TEA Algorithms

См. также

• TEA
• Сеть Фейстеля
• Битовые операции
• XXTEA
• RTEA
• Raiden

Ссылки

• 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).