TEA

Алгоритм шифрування TEA заснований на бітових операцій з 64-бітним блоком, має 128-бітний ключ шифрування. Стандартна кількість раундів мережі Фейстеля біля 64 (32 циклу), однак, для досягнення найкращої продуктивності або шифрування, число циклів можна варіювати від 8 (16 раундів) до 64 (128 раундів). Мережа Фейстеля несиметрична через використання в якості операції накладення додавання по модулю 2³².

Перевагами шифру є його простота в реалізації, невеликий розмір коду й досить висока швидкість виконання, а також можливість оптимізації виконання на стандартних 32-бітних процесорах, так як в якості основних операцій використовуються операції виключна «АБО» (XOR), побітового зсуву й додавання по модулю 2³². Оскільки алгоритм не використовує таблиць підстановки і раундова функція досить проста, алгоритму потрібно не менше 16 циклів (32 раундів) для досягнення ефективної дифузії, хоча повна дифузія досягається вже через 6 циклів (12 раундів).

Алгоритм має відмінну стійкість до лінійного криптоаналізу і досить гарну до диференціального криптоаналізу. Головним недоліком цього алгоритму шифрування є його вразливість до атак «на пов'язаних ключах» (англ. Related-key attack). Через простий розклад ключів кожен ключ має 3 еквівалентних ключа. Це означає, що ефективна довжина ключа складає всього 126 біт[3][4], тому даний алгоритм не слід використовувати в якості геш-функції.

Вихідний текст розбивається на блоки по 64 біта кожен. 128-бітний ключ К ділиться на чотири 32-бітних підключа K[0], K[1], K[2] і K[3]. На цьому підготовчий процес закінчується, після чого кожен 64-бітний блок шифрується протягом 32 циклів (64 раундів) за нижченаведеним алгоритмом.[5]

Припустимо, що на вхід n-го раунду (1 ≤ n ≤ 64) надходять права й ліва частини  (L_n, R_n), тоді на виході n-го раунду будуть ліва й права частини (L_n+1, R_n+1), які обчислюються за такими правилами:

L_n+1 = R_n.

Якщо n = 2 * i — 1 для 1 ≤ i ≤ 32 (непарні раунди), то R_n+1 = L_n ${\displaystyle }$ ({ [ R_n ${\displaystyle }$ 4 ] ${\displaystyle }$ K[0] } ${\displaystyle }$ { R_n ${\displaystyle }$ i * δ } ${\displaystyle }$ { [ R_n ${\displaystyle }$ 5 ] ${\displaystyle }$ K[1] })

Якщо n = 2 * i для 1 ≤ i ≤ 32 (парні раунди), то R_n+1 = L_n ${\displaystyle }$ ({ [ R_n ${\displaystyle }$ 4 ] ${\displaystyle }$ K[2] } ${\displaystyle }$ { R_n ${\displaystyle }$ i * δ } ${\displaystyle }$ { [ R_n ${\displaystyle }$ 5 ] ${\displaystyle }$ K[3] })

Де

• X ${\displaystyle }$ Y — операція додавання чисел X і Y по модулю 2³².
• X ${\displaystyle }$ Y — побітове виключне АБО» (XOR) чисел X і Y, яке в мові програмування Сі позначається як X ^ Y
• X ${\displaystyle }$ Y і X ${\displaystyle }$ Y — операції побітового зсуву числа X на Y біт вліво й вправо відповідно.
• Константа δ була виведена з Золотого перерізу δ = (${\displaystyle }$ — 1) * 2³¹ = 2654435769 = 9E3779B9_h. У кожному раунді константа множиться на номер циклу i. Це було зроблено для запобігання простих атак, заснованих на симетрії раундів.

Також очевидно, що в алгоритмі шифрування TEA немає як такого алгоритму розкладу ключів. Замість цього в непарних раундах використовуються підключі К [0] та[1], у парних — К [2] і[3].

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

Реалізація на мові програмування Сі (адаптований варіант коду, представленого в статті Девіда Вілера та Роджера Нідгема) функцій шифрування і розшифрування з використанням алгоритму TEA:

#include <stdint.h>

void encrypt (uint32_t* v, uint32_t* k)
{
    /* set up */
    uint32_t v0 = v[0];
    uint32_t v1 = v[1];
    uint32_t sum = 0;
    uint32_t i;

    /* a key schedule constant */
    uint32_t delta = 0x9e3779b9;

    /* cache key */
    uint32_t k0 = k[0];
    uint32_t k1 = k[1];
    uint32_t k2 = k[2];
    uint32_t k3 = k[3];

    /* basic cycle start */
    for (i = 0; i < 32; i++)
    {
        sum += delta;
        v0 += ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1);
        v1 += ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);
    }
    /* end cycle */

    v[0] = v0;
    v[1] = v1;
}

void decrypt (uint32_t* v, uint32_t* k)
{
    /* set up */
    uint32_t v0 = v[0];
    uint32_t v1 = v[1];
    uint32_t sum = 0xC6EF3720;
    uint32_t i;

    /* a key schedule constant */
    uint32_t delta = 0x9e3779b9;

    /* cache key */
    uint32_t k0 = k[0];
    uint32_t k1 = k[1];
    uint32_t k2 = k[2];
    uint32_t k3 = k[3];        

    /* basic cycle start */
    for (i = 0; i < 32; i++)
    {                              
        v1 -= ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);
        v0 -= ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1);
        sum -= delta;                                   
    }
    /* end cycle */

    v[0] = v0;
    v[1] = v1;
}

Коментарі:

• v — початковий текст складається з двох частин по 32 біта
• k — ключ складається з чотирьох 32-бітних частин

Зміни у порівнянні з оригінальним кодом:

• використовується тип uint32_t внаслідок того, що він завжди має розмір 32 біта на відміну від long (присутній в оригінальному коді), який може містити 64 біта (наприклад в деяких 64 бітних системах)
• вихідний код не використовує тип const
• у вихідному коді опущені надлишкові дужки у виразах для v0 і v1, в даній модифікації вони залишені для більшої наочності

Передбачається, що даний алгоритм забезпечує захищеність, порівнянну з алгоритмом шифрування IDEA, так як він застосовує ту ж ідею використання операцій з ортогональних алгебраїчних груп. Цей підхід відмінно захищає від методів лінійного криптоаналізу.

Еквівалентні ключі

Ще одна проблема алгоритму TEA — наявність еквівалентних ключів. Було показано, що кожен ключ має три йому еквівалентних[4]. Це означає, що ефективна довжина ключа має всього 126 біт замість 128, задуманих розробниками, тому TEA небажано використовувати в якості геш-функції, що було відображено в книзі Ендрю Хуанга (Andrew Huang) «Hacking the Xbox: an introduction to reverse engineering» на прикладі злому ігрової приставки Microsoft Xbox.

Таблиця еквівалентних ключів:

K[0]	K[1]	K[2]	K[3]
K[0]	K[1]	K[2] ${\displaystyle }$ 80000000h	K[3] ${\displaystyle }$ 80000000h
K[0] ${\displaystyle }$ 80000000h	K[1] ${\displaystyle }$ 80000000h	K[2]	K[3]
K[0] ${\displaystyle }$ 80000000h	K[1] ${\displaystyle }$ 80000000h	K[2] ${\displaystyle }$ 80000000h	K[3] ${\displaystyle }$ 80000000h

Виявлення ряду серйозних недоліків і слабких місць у вихідному алгоритмі TEA призвело до швидкого створення його розширень. Основними відмінностями всіх цих алгоритмів є вдосконалений розклад ключів, динамічна залежність ключа від тексту, а також інший розмір ключа, вхідного блоку і/або кількість раундів мережі Фейстеля.

• XTEA
• XXTEA
• RTEA
• Raiden
• Мережа Фейстеля

• Сторінка алгоритму шифрування TEA
• Roger M. Needham and David J. Wheeler. «TEA, a Tiny Encryption Algorithm»(PDF)
• Andew Hang. «Hacking the Xbox: an introduction to reverse engineering» ISBN 978-1593270292
• Журнал «Хакер Онлайн», TEA: блочний шифр своїми руками, (2004)
• Paris Kitsos,Yan Zhang. «RFID Security: Techniques, Protocols and System-On-Chip Design»
• David J. Wheeler Roger and M. Needham. «Correction to xtea.» Technical report, Computer Laboratory, University of Cambridge, October 1998 (PDF).
• Roger M. Needham and David J. Wheeler. «Tea extensions.» Technical report, Computer Laboratory, University of Cambridge, October 1997 (PDF).
• Test vectors for TEA
• JavaScript implementation of XXTEA with Base64
• PHP implementation of XTEA
• JavaScript implementation of TEA
• Ruby implementation of XXTEA with Base64
• LGPL Java/J2ME implementation of TEA
• Visual Basic.NET implementation of TEA