XXTEA

XXTEA
Розробники	Девід Уілер і Роджер Нідгем
Уперше оприлюднений	1998 р
Раундів	, де - кількість слів
Тип	Мережа Фейстеля

XXTEA — криптографічний алгоритм, що реалізує блочне симетричне шифрування і є мережею Фейстеля. Є розширенням алгоритму Block TEA. Розроблений і опублікований Девідом Уілером і Роджером Нідгемом в 1998 році. Виконаний на простих і швидких операціях: XOR, підстановка, додавання.^[1]^[2]

Історія

На симпозіумі Fast Software Encryption в грудні 1994 року Девід Уілер і Роджер Нідгем, професори Комп'ютерної Лабораторії Кембриджського Університету (Computer Laboratory, University of Cambridge), представили новий криптографічний алгоритм TEA. Даний алгоритм проектувався як альтернатива DES, який до того моменту вже вважався застарілим.^[3]^[4]

Пізніше в 1996 році в ході особистого листування Девіда Уїлера з Девідом Вагнером була виявлена уразливість до атаки на пов'язаних ключах, яка була офіційно представлена в 1997 році на Першій Міжнародній Конференції ICIS групою вчених, що складалася з Брюса Шнайера, Джона Келсі і Девіда Вагнера.^[5]^[6] Ця атака стала підставою для покращення алгоритму TEA, і в жовтні 1996 року Уілер і Нідгем опублікували внутрішній звіт лабораторії, в якій наводилося два нових алгоритми: XTEA і Block TEA.^[7]

10 жовтня 1998 року група новин sci.crypt.research опублікувала статтю Маркку-Юхані Саарінена, в якій була знайдена уразливість Block TEA на стадії дешифрування^[4]. У тому ж місяці Девід Уілер і Роджер Нідгем опублікували внутрішній звіт лабораторії, в якій наводилося поліпшення алгоритму Block TEA — XXTEA.^[1]

Особливості

XXTEA, як і інші шифри колекції TEA, має ряд відмінних особливостей у порівнянні з аналогічними шифрами:

Висока швидкість роботи
Мале споживання пам'яті
Проста програмна реалізація
Відносно висока надійність.^[8]^[9]^[2]^[4]

Опис роботи алгоритму

Вихідний текст розбивається на слова по 32 біта кожне, з отриманих слів формується блок. Ключ також розбивають на 4 частини, що складаються зі слів по 32 біта кожен, і формують масив ключів. В ході одного раунду роботи алгоритму шифрується одне слово з блоку. Після того, як були зашифровані слова, закінчується цикл і починається новий. Кількість циклів залежить від кількості слів і дорівнює $6+52/n$ , де $n$ — кількість слів. Шифрування одного слова полягає в наступному:

Над лівим сусідом виконується операція бітового зсуву вліво на два, а над правим операція бітового зсуву вправо на п'ять. Над отриманими значеннями виконують операцію побітового додавання за модулем 2.
Над лівим сусідом виконується операція бітового зсуву вправо на три, а над правим операція бітового зсуву вліво на 4. Над отриманими значеннями виконують операцію побітового додавання за модулем 2
Отримані числа складають по модулю 2³².
Константа δ, виведена із Золотого перетину (δ = ( ${\sqrt {5}}$ — 1) * 2³¹ = 2654435769 = 9E3779B9_h)^[3] множиться на номер циклу (це було зроблено для запобігання простим атакам, заснованим на симетрії раундів).
Отримане в попередньому пункті число складають побітово по модулю 2 з правим сусідом.
Отримане в пункті 4 число зсувають побітово направо на 2, складають побітово по модулю два з номером раунду, і знаходять залишок від ділення на 4. З допомогою отриманого числа вибирають ключ з масиву ключів.
Обраний в попередньому раунді ключ складають побітово по модулю 2 з лівим сусідом.
Числа, отримані у попередньому та 4 пунктах складають по модулю 2³².
Числа, отримані в попередньому і 3 пунктах складають побітово по модулю 2, цю суму складають з шифрованим словом по модулю 2³².

Криптоаналіз

На даний момент існує атака на основі адаптивно підібраного відкритого тексту, опублікована Еліасом Яаррковом в 2010 році. Існує два підходи, в яких використовується зменшення кількості циклів за рахунок збільшення кількості слів.

Перший підхід

Схема першого підходу диференціального криптоаналізу XXTEA

Нехай у нас є якийсь відкритий текст. Візьмемо з нього 5 певних слів, починаючи з $r$ , які ми шифруємо з $r+1$ . Додамо яке-небудь число до $r+2$ і отримаємо новий відкритий текст. Тепер виконаємо перший цикл шифрування для цих текстів. Якщо після шифрування різниця залишилася тільки в даному слові, то продовжуємо шифрування. Якщо почали з'являтися різниці в інших словах, то починаємо пошук заново або змінюючи вихідний, або намагаючись підібрати іншу різницю. Збереження різниці тільки в одному слові можливо, так як функція шифрування не бієктивна для кожного сусіда. Еліас Яаррков провів ряд експериментів і з'ясував, що ймовірність проходження різниці $\Delta =13$ 5 повних циклів давала ймовірність між $2$ ^$-109$ і $2$ ^$-110$ для більшості ключів, тобто якщо пара текстів пройшла 5 з 6 повних циклів, то її можна вважати вірною, так як якщо помістити різницю в кінець блоку, будуть виникати різниці в більшості слів. Дана атака була проведена і був відновлений ключ для алгоритму з кількістю циклів зменшеною до трьох.

Другий підхід

Схема другого підходу диференціального криптоаналізу XXTEA

Другий підхід відрізняється від першого тим, що після першого раунду шифрування $r+1$ слова, різниця повинна перейти у нього самого з $r+2$ слова, при цьому різниця може зміниться, а після наступного раунду шифрування різниця повернеться в $r+2$ слово і стане дорівнювати початковому, але змінить знак. Після проведення оцінки даного методу, Еліас Яаррков отримав, що для успішного знаходження правильної пари досить 2⁵⁹ текстів, причому різниця повинна лежати в інтервалі $[-d;d]$ , де $d=32$ , причому збільшення d не поліпшила результатів. Після була проведена успішна атака на XXTEA з кількістю циклом зменшеним до 4, і правильна пара була отримана за допомогою 2³⁵ пар текстів, а попередня оцінка дає необхідність у 2^34.7 пар текстів.

Відновлення ключа

Знаючи правильну пару текстів, досить прогнати алгоритм у зворотному порядку, оскільки тепер нам відомо все крім ключа. ^[2]^[8]

Зразок коду

Оригінальне формулювання виправленого блоку TEA алгоритму, опублікованого Девідом Вільцером та Роджером Нідгем, полягає в наступному^[10]:

  #define MX ((z>>5^y<<2) + (y>>3^z<<4) ^ (sum^y) + (k[p&3^e]^z))
  
  long btea(long* v, long n, long* k) {
    unsigned long z=v[n-1], y=v[0], sum=0, e, DELTA=0x9e3779b9;
    long p, q ;
    if (n > 1) {          /* Coding Part */
      q = 6 + 52/n;
      while (q-- > 0) {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) y = v[p+1], z = v[p] += MX;
        y = v[0];
        z = v[n-1] += MX;
      }
      return 0 ; 
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      q = 6 + 52/n;
      sum = q*DELTA ;
      while (sum != 0) {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) z = v[p-1], y = v[p] -= MX;
        z = v[n-1];
        y = v[0] -= MX;
        sum -= DELTA;
      }
      return 0;
    }
    return 1;
  }

За словами Нідгема та Уілера:

BTEA буде кодувати або декодувати n слів як єдиний блок, де n> 1
v - вектор n даних слова

k - це ключ від 4 слів

n - для декодування є негативним

якщо n дорівнює нулю, то результат - 1, і ніякого кодування чи декодування не відбувається, інакше результат буде нульовим

передбачає 32-бітове "довге" та аналогічне кодування та декодування

Зверніть увагу, що ініціалізація z є невизначеною поведінкою для n <1, що може спричинити помилку сегментації або іншу небажану поведінку, - це було б краще помістити в блок «Coding Part». Крім того, у визначенні MX деякі програмісти вважатимуть за краще використовувати брекетинг, щоб визначити перевагу оператора.

Уточнена версія, включаючи такі вдосконалення, полягає в наступному:

  #include <stdint.h>
  #define DELTA 0x9e3779b9
  #define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))
  
  void btea(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n > 1) {          /* Coding Part */
      rounds = 6 + 52/n;
      sum = 0;
      z = v[n-1];
      do {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) {
          y = v[p+1]; 
          z = v[p] += MX;
        }
        y = v[0];
        z = v[n-1] += MX;
      } while (--rounds);
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      rounds = 6 + 52/n;
      sum = rounds*DELTA;
      y = v[0];
      do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) {
          z = v[p-1];
          y = v[p] -= MX;
        }
        z = v[n-1];
        y = v[0] -= MX;
        sum -= DELTA;
      } while (--rounds);
    }
  }