TEA

В криптографії,Tiny Encryption Algorithm (TEA)^[1] — блочний алгоритм шифрування типу «Мережі Фейстеля». Алгоритм був розроблений на факультеті комп'ютерних наук Кембриджського університету Девідом Вілером (David Wheeler) і Роджером Нідгемом (Roger Needham)  та  вперше представлений в 1994 році^[2] на симпозіумі зі швидкими алгоритмами шифрування в Льовені (Бельгія).

TEA

Розробники	Девід Уілер і Роджер Нідгем
Уперше оприлюднений	1994 р
Деталі шифру
Розмір ключа	128 біт
Розмір блоку	64 біт
Раундів	64 (32 циклу)
Тип	Мережа Фейстеля

Шифр не патентований, широко використовується в ряді криптографічних додатків і широкому спектрі апаратного забезпечення, завдяки вкрай низькими вимогами до пам'яті й простоті реалізації. Алгоритм має як програмну реалізацію на різних мовах програмування, так і апаратну реалізацію на інтегральних схемах типу FPGA.

Властивості

Алгоритм шифрування 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 \boxplus }$ ({ [ R_n ${\displaystyle \ll }$ 4 ] ${\displaystyle \boxplus }$ K[0] } ${\displaystyle \oplus }$ { R_n ${\displaystyle \boxplus }$ i * δ } ${\displaystyle \oplus }$ { [ R_n ${\displaystyle \gg }$ 5 ] ${\displaystyle \boxplus }$ K[1] })

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

Де

• X ${\displaystyle \boxplus }$ Y — операція додавання чисел X і Y по модулю 2³².
• X ${\displaystyle \oplus }$ Y — побітове виключне АБО» (XOR) чисел X і Y, яке в мові програмування Сі позначається як X ^ Y
• X ${\displaystyle \ll }$ Y і X ${\displaystyle \gg }$ Y — операції побітового зсуву числа X на Y біт вліво й вправо відповідно.
• Константа δ була виведена з Золотого перерізу δ = (${\displaystyle {\sqrt {5}}}$ — 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, так як він застосовує ту ж ідею використання операцій з ортогональних алгебраїчних груп. Цей підхід відмінно захищає від методів лінійного криптоаналізу.

Атаки на пов'язаних ключах

Алгоритм найбільш уразливий до «атак на пов'язаних ключах» (англ. Related-key attack), через простий розклад ключів (в тому числі відсутності алгоритму розкладу ключів як такого). Існують як мінімум три відомі атаки даного типу, вони були представлені в роботі Джона Келсі (John Kelsea), Брюса Шнайєра (Bruce Schneier) і Девіда Вагнера (David Wagner) в 1997 році^[6]. Найбільш прості з них дають диференціальну характеристику з імовірністю 2^-32 після 32 циклів алгоритму, тому потрібно не менше 2³⁴ обраних відкритих текстів для знаходження диференціальної характеристики з ймовірністю 1 і визначення всіх біт ключа. Більш складна в реалізації атака, що поєднує в собі ідеї «атаки на пов'язаних ключах» Елі Бихама (Eli Biham)^[7] та диференціальної атаки дає диференціальну характеристику з імовірністю 2^-11, вимагає всього 2²³ обраних відкритих текстів і час близько 2³² часів шифрування (тобто потребує кількість бітових операцій близько 2³²).

Диференціальний криптоаналіз

Було виявлено, що TEA досить стійкий до диференціального криптоаналізу. Атака на 10 раундів TEA вимагає 2^52.5 обраних відкритих текстів і має тимчасову складність 2⁸⁴. Кращий результат — криптоаналіз 17 раундів TEA. Дана атака вимагає всього 1920 обраних відкритих текстів, однак має тимчасову складність 2^123.37.

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

Ще одна проблема алгоритму 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 \oplus }$ 80000000h	K[3] ${\displaystyle \oplus }$ 80000000h
K[0] ${\displaystyle \oplus }$ 80000000h	K[1] ${\displaystyle \oplus }$ 80000000h	K[2]	K[3]
K[0] ${\displaystyle \oplus }$ 80000000h	K[1] ${\displaystyle \oplus }$ 80000000h	K[2] ${\displaystyle \oplus }$ 80000000h	K[3] ${\displaystyle \oplus }$ 80000000h

Розширення алгоритму

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

XTEA

XTEA має розмір блоку, який  дорівнює 64 бітам, розмір ключа 128 біт, кількість раундів мережі Фейстеля дорівнює 64. Алгоритм був розроблений Девідом Вілером і Роджером Нідгемом та опублікований у 1997 році. Головна відмінність від вихідного алгоритму TEA — наявність алгоритму розкладу ключів, що дозволило усунути критичну вразливість до атак на "пов'язаних ключах», але призвело до погіршення стійкості до диференціального криптоаналізу. Існують три модифікації цього алгоритму, розроблені Томом Денісом (Tom Denis)^[8]: XTEA-1 (розмір блоку — 64 біта, розмір ключа 128 біт, кількість раундів мережі Фейстеля — 32), XTEA-2 (розмір блоку 128 біт, розмір ключа 128 біт, кількість раундів мережі Фейстеля — 64) і XTEA-3 (розмір блоку 128 біт, розмір ключа — 256 біт, кількість раундів мережі Фейстеля — 64).

XXTEA

У 1998 році було опубліковано наступне розширення алгоритму, що отримало назву XXTEA. Розмір ключа 128 біт. Відмітною особливістю є можливість шифрування будь-яких блоків, довжина яких кратна 64 бітам, кількість раундів одно 52 + 6*(кількість 32-бітних слів в блоці) або 52 + 12*м при довжині блоку 64*M біт. Практична ефективність,  опублікованої анонімно диференціальної атаки, не доведена^[9].

RTEA

Існує так само альтернативна модифікація алгоритму TEA, що отримала найменування RTEA, розроблена у 2007 році «Marcos el Ruptor». Розмір блоку — 64 біта; для 128-бітного ключа число раундів мережі Фейстеля дорівнює 48, для 256-бітного — 64. За заявами розробників цей алгоритм продуктивніший і  стійкіший до криптоаналізу^[10], ніж XTEA, однак і на цей алгоритм вже існує «атака на пов'язаних ключах»^[11].

Raiden

З використанням механізмів генетичного програмування в 2006 році командою розробників на чолі з Хуліо Кастро (англ. Julio César Hernández Castro) був створений алгоритм Raiden, покликаний усунути уразливості шифру TEA. Він практично в точності повторює структуру алгоритму TEA, за винятком того, що у алгоритмі Raiden є розширений алгоритм розкладу ключів. Стандартне число раундів мережі Фейстеля одне 32 (16 циклів). Raiden використовує ключовий розклад, близький до ДПРЧ, трансформує ключ і генерує підключі для кожного раунду. Шифр успішно проходить тексти Diehard, Sexton і ENT^[12].

Порівняння різних версій розширення алгоритму TEA

Тут наведена порівняльна таблиця основних характеристик алгоритмів колекції TEA:

Назва алгоритму	Стандартна кількість раундів мережі Фейстеля	Розмір блоку	Розмір ключа
TEA	64	64 біта	128 біт
XTEA	64	64 біта	128 біт
XTEA-1	32	64 біта	128 біт
XTEA-2	64	128 біт	128 біт
XTEA-3	64	128 біт	256 біт
XXTEA	52 + 12 * M	64 * M біт	128 біт
RTEA	48 або 64	64 біта	128 або 256 біт
Raiden	32	64 біта	128 біт

У той же час, автори алгоритму TEA на своїй офіційній сторінці^[1] звертають увагу на те, що в реальних умовах практичного використання, алгоритм TEA все ще залишається досить надійним і всі знайдені вразливості, як правило, не є критичними, наприклад, при передачі даних в реальному часі.

Див. також

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

Примітки

1. Страница шифра TEA. Архів оригіналу за 12 червня 2017. Процитовано 22 квітня 2018.
2. Roger M. Needham and David J. Wheeler. TEA, a Tiny Encryption Algorithm [Архівовано 13 жовтня 2017 у Wayback Machine.]
3. Kelsey, John; Schneier, Bruce; Wagner, David (1996). Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES (PDF). Lecture Notes in Computer Science. 1109: 237—251. doi:10.1007/3-540-68697-5_19. Архів оригіналу (PDF) за 8 лютого 2012. Процитовано 22 квітня 2018.
4. Andem, Vikram Reddy (2003).A cryptoanalisys of the tiny encryption algorithm [Архівовано 20 квітня 2009 у Wayback Machine.]
5. Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee, (2003). Differential Cryptanalysis of TEA and XTEA^{[недоступне посилання з листопадаа 2019]}
6. Kelsey, John; Schneier, Bruce; Wagner, David (1997). Related-key cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X NewDES, RC2, and TEA. Lecture Notes in Computer Science. 1334: 233—246. doi:10.1007/BFb0028479. Архів оригіналу за 3 грудня 2008. Процитовано 22 квітня 2018.
7. Eli Biham, Computer Science Department, Technion — Israel Institute of Technology, Haifa 32000, Israel, (1992). «New Types of Cryptanalytic Attacks Using Related Keys»^{[недоступне посилання з листопадаа 2019]}
8. Tom St Denis. Extended TEA Algorithms [Архівовано 27 серпня 2018 у Wayback Machine.]
9. Исходная статья с реализацией атаки на XXTEA и примером кода. Архів оригіналу за 23 вересня 2009. Процитовано 22 квітня 2018.
10. Сравнительные результаты устойчивости симметричных криптоалгоритмов [Архівовано 25 липня 2008 у Wayback Machine.](англ.)
11. A related key attack for RTEA.^{[недоступне посилання з лютого 2019]}
12. Raiden: An alternative to TEA Block Cipher. Архів оригіналу за 5 березня 2016. Процитовано 22 квітня 2018. (англ.)

Посилання

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