Вікіпедія

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 раундів). Мережа Фейстеля несиметрична через використання як операції накладення додавання по модулю 232.

Перевагами шифру є його простота в реалізації, невеликий розмір коду й досить висока швидкість виконання, а також можливість оптимізації виконання на стандартних 32-бітних процесорах, так як основні операції використовуються операції виключна «АБО» (XOR), побітового зсуву й додавання по модулю 232. Оскільки алгоритм не використовує таблиць підстановки і раундова функція досить проста, алгоритму потрібно не менше 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) надходять права й ліва частини  (Ln, Rn), тоді на виході n-го раунду будуть ліва й права частини (Ln+1, Rn+1), які обчислюються за такими правилами:

Ln+1 = Rn.

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

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

Де

  • X   Y — операція додавання чисел X і Y по модулю 232.
  • X   Y — побітове виключне АБО» (XOR) чисел X і Y, яке в мові програмування Сі позначається як X ^ Y
  • X   Y і X   Y — операції побітового зсуву числа X на Y біт вліво й вправо відповідно.
  • Константа δ була виведена з Золотого перерізу δ = (  — 1) * 231 = 2654435769 = 9E3779B9h. У кожному раунді константа множиться на номер циклу 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 циклів алгоритму, тому потрібно не менше 234 обраних відкритих текстів для знаходження диференціальної характеристики з ймовірністю 1 і визначення всіх біт ключа. Більш складна в реалізації атака, що поєднує в собі ідеї «атаки на пов'язаних ключах» Елі Бихама (Eli Biham)[7] та диференціальної атаки дає диференціальну характеристику з імовірністю 2-11, вимагає всього 223 обраних відкритих текстів і час близько 232 часів шифрування (тобто потребує кількість бітових операцій близько 232).

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

ред.

Було виявлено, що TEA досить стійкий до диференціального криптоаналізу. Атака на 10 раундів TEA вимагає 252.5 обраних відкритих текстів і має тимчасову складність 284. Кращий результат — криптоаналіз 17 раундів TEA. Дана атака вимагає всього 1920 обраних відкритих текстів, однак має тимчасову складність 2123.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]   80000000h K[3]   80000000h
K[0]   80000000h K[1]   80000000h K[2] K[3]
K[0]   80000000h K[1]   80000000h K[2]   80000000h K[3]   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 все ще залишається досить надійним і всі знайдені вразливості, як правило, не є критичними, наприклад, при передачі даних в реальному часі.

Див. також

ред.

Примітки

ред.
  1. ↑ а б Страница шифра TEA. Архів оригіналу за 12 червня 2017. Процитовано 22 квітня 2018. [Архівовано 2017-06-12 у Wayback Machine.]
  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. [Архівовано 2012-02-08 у Wayback Machine.]
  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. [Архівовано 2009-09-23 у Wayback Machine.]
  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. (англ.)

Посилання

ред.
Отримано з https://uk.wikipedia.org/w/index.php?title=TEA&oldid=44029659
  NODES
Idea 2
idea 2
Note 2