XXTEA

XXTEA

Розробники	Девід Уілер і Роджер Нідгем
Уперше оприлюднений	1998 р
Раундів	${\displaystyle 6*n+52}$, де ${\displaystyle n}$ - кількість слів
Тип	Мережа Фейстеля

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]

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

Схема алгоритму шифрування XXTEA

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

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

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

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

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

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

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

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

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

Другий підхід відрізняється від першого тим, що після першого раунду шифрування ${\displaystyle r+1}$ слова, різниця повинна перейти у нього самого з ${\displaystyle r+2}$ слова, при цьому різниця може зміниться, а після наступного раунду шифрування різниця повернеться в ${\displaystyle r+2}$ слово і стане дорівнювати початковому, але змінить знак. Після проведення оцінки даного методу, Еліас Яаррков отримав, що для успішного знаходження правильної пари досить 2⁵⁹ текстів, причому різниця повинна лежати в інтервалі ${\displaystyle [-d;d]}$, де ${\displaystyle 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);
    }
  }

Примітки

1. Wheeler et al, 1998.
2. Yarrkov, 2010.
3. Wheeler et al, 1994.
4. Saarinen, 1998.
5. Kelsey et al, 1997.
6. ICIS, 1997.
7. Wheeler et al, 1996.
8. Sima et al, 2012.
9. Cenwei, 2008.
10. David J. Wheeler and Roger M. Needham (October 1998). Correction to XTEA (PDF). Computer Laboratory, Cambridge University, England. Архів оригіналу (PDF) за 20 вересня 2017. Процитовано 4 липня 2008.

Література

• David J. Wheeler, Roger M. Needham. Correction to XTEA. — 1998. — Жовтень.
• E. Yarrkov. Cryptanalysis of XXTEA. — 2010. — . — Травень.
• Saarinen M.-J. Cryptanalysis of Block Tea. — 1998. — . — Жовтень.
• David J. Wheeler, Roger M. Needham. TEA, a tiny encryption algorithm. — 1994. — Грудень.
• David J. Wheeler, Roger M. Needham. TEA extensions. — 1996. — Жовтень.
• J. Kelsey, B. Schneier and D. Wagner. Related-key cryptanalysis of 3-WAY, Biham-DES,CAST, DES-X, NewDES, RC2, and TEA. — 1997. — Листопад.
• Mao Cenwei. Comparison of a Few Small Ciphers Applicable to RFID. — 2008. — Червень.
• I. Sima, D. Tarmurean и V. Greu. XXTEA, an alternative replacement of KASUMI cipher algorithm in A5/3 GSM and f8, f9 UMTS data security functions. — 2012. — Червень.
• First International Conference, ICIS'97, Beijing, China, November 11-14, 1997, Proceedings / Editors: Yongfei Han, Tatsuaki Okamoto, Sihan Quing. — 1. — Springer-Verlag Berlin Heidelberg, 1997. — ISBN 978-3-540-63696-0.