XXTEA

XXTEA
Tvůrce David Wheeler a Roger Needham
Vytvořeno 1998 _
zveřejněno 1998 _
Velikost klíče 128 bit
Velikost bloku bitů, kde je počet slov, ne méně než 2
Počet kol , kde je počet slov
Typ Síť Feistel

XXTEA  je kryptografický algoritmus , který implementuje blokově symetrické šifrování a je sítí Feistel . Jedná se o rozšíření algoritmu Block TEA. Navrhli a publikovali Wheeler a Roger v roce 1998 Vyrobeno na jednoduchých a rychlých operacích: XOR , substituce, sčítání. [1] [2]

Historie

Na Fast Software Encryption Symposium v prosinci 1994 představili David Wheeler a Roger Needham, profesoři z počítačové laboratoře University of Cambridge , nový kryptografický algoritmus TEA . Tento algoritmus byl navržen jako alternativa k DES , který byl v té době již považován za zastaralý. [3] [4]

Později v roce 1996, v průběhu osobní korespondence mezi Davidem Wheelerem a Davidem Wagnerem, byla odhalena zranitelnost souvisejícího klíčového útoku , která byla oficiálně představena v roce 1997 na První mezinárodní konferenci ICIS skupinou vědců sestávající z Bruce Schneiera , John Kelsey a David Wagner. [5] [6] Tento útok poskytl základ pro vylepšení algoritmu TEA a v říjnu 1996 Wheeler a Needham zveřejnili interní laboratorní zprávu, která citovala dva nové algoritmy: XTEA a Block TEA. [7]

Dne 10. října 1998 zveřejnila diskusní skupina sci.crypt.research článek Markku-Juhani Saarinena, ve kterém byla ve fázi dešifrování nalezena zranitelnost Block TEA [4] . Ve stejném měsíci David Wheeler a Roger Needham zveřejnili interní zprávu z laboratoře, která zlepšila algoritmus XXTEA společnosti Block TEA. [osm]

Funkce

XXTEA, stejně jako ostatní šifry z rodiny TEA, má ve srovnání s podobnými šiframi řadu charakteristických rysů:

Popis algoritmu

Zdrojový text je rozdělen na slova po 32 bitech, z přijatých slov je vytvořen blok. Klíč je také rozdělen na 4 části, z nichž každá se skládá ze slov o 32 bitech, a tvoří se pole klíčů. Během jednoho kola algoritmu je zašifrováno jedno slovo z bloku. Po zašifrování všech slov cyklus končí a začíná nový. Počet cyklů závisí na počtu slov a je roven , kde  je počet slov. Šifrování jednoho slova je následující:

  1. Levý soused je posunut doleva o dva a pravý soused je posunut doprava o pět. Získané hodnoty jsou bitové modulo 2 .
  2. Levý soused je bitově posunut doprava o tři a pravý soused je bit doleva o 4. Získané hodnoty jsou bitově modulo 2 přidány.
  3. Výsledná čísla se sečtou modulo 2 32 .
  4. Konstanta δ, odvozená ze Zlatého poměru δ = (  - 1) * 2 31 = 2654435769 = 9E3779B9 h [3] , se vynásobí číslem cyklu (to bylo provedeno, aby se zabránilo jednoduchým útokům založeným na kruhové symetrii).
  5. Číslo získané v předchozím odstavci se přidává bit po bitu modulo 2 s pravým sousedem.
  6. Číslo získané v odstavci 4 se posune bitově doprava o 2, přidá se bitové modulo dva s kulatým číslem a je nalezen zbytek po dělení 4. Pomocí výsledného čísla se vybere klíč z pole klíčů.
  7. Klíč vybraný v předchozím kole se přidává bit po bitu modulo 2 s levým sousedem.
  8. Čísla získaná v předchozím a 4 bodech se přičtou modulo 2 32 .
  9. Čísla získaná v předchozím a 3 odstavcích se přičítají bit po bitu modulo 2, tento součet se přičítá k zašifrovanému slovu modulo 2 32 .

Kryptoanalýza

V současné době existuje adaptivní útok založený na prostém textu, který publikoval Elias Jaarrkov v roce 2010. Existují dva přístupy, které používají snížení počtu smyček zvýšením počtu slov.

První přístup

Předpokládejme, že máme nějaký otevřený text. Vezměme z něj 5 určitých slov počínaje , která zašifrujeme . Přidáme nějaké číslo do , a dostaneme nový prostý text. Nyní provedeme první cyklus šifrování těchto textů. Pokud po zašifrování zůstane rozdíl pouze v tomto slově, pokračujeme v šifrování. Pokud se začnou objevovat rozdíly v jiných slovech, pak zahájíme hledání znovu buď změnou původního, nebo se pokusíme najít jiný rozdíl. Uložení rozdílu pouze do jednoho slova je možné, protože funkce šifrování není pro každého souseda bijektivní . Elias Jaarrkov provedl řadu experimentů a zjistil, že pravděpodobnost, že projde rozdílem 5 úplných cyklů, dává pravděpodobnost mezi a pro většinu klíčů, to znamená, že pokud dvojice textů prošla 5 ze 6 úplných cyklů, pak může být považováno za správné, protože pokud dáte rozdíl na konec bloku, budou rozdíly ve většině slov. Tento útok byl proveden a klíč pro algoritmus byl obnoven s počtem cyklů sníženým na tři.

Druhý přístup

Druhý přístup se od prvního liší tím, že po prvním kole šifrování slova do něj musí jít rozdíl od slova samotného, ​​přičemž rozdíl se může změnit a po dalším kole šifrování se rozdíl vrátí do slovo a stát se rovnými původnímu, ale změňte znaménko. Po vyhodnocení této metody Elias Jaarkov zjistil, že k úspěšnému nalezení správné dvojice stačí 2 59 textů a rozdíl by měl ležet v intervalu , kde , a zvyšování d výsledky nezlepšilo. Poté byl proveden úspěšný útok na XXTEA s počtem cyklů sníženým na 4 a správný pár byl získán s 235 páry textů, zatímco předchozí odhad udává potřebu 234,7 párů textů.

Obnova klíče

Když známe správnou dvojici textů, stačí spustit algoritmus v obráceném pořadí, protože nyní víme všechno kromě klíče. [2] [12]

Poznámky

  1. ↑ Wheeler a kol., 1998 .
  2. ↑ 12 Yarrkov , 2010 .
  3. ↑ 12 Wheeler a kol., 1994 .
  4. ↑ 1 2 3 Saarinen, 1998 .
  5. ↑ Kelsey a kol., 1997 .
  6. ↑ ICIS, 1997 .
  7. ↑ Wheeler a kol., 1996 .
  8. ↑ Wheeler a kol., 1998 .
  9. ↑ Sima et al, 2012 .
  10. ↑ Cenwei, 2008 .
  11. ↑ Yarkov, 2010 .
  12. ↑ Sima et al, 2012 .

Literatura

 Symetrické kryptosystémy
Streamové šifry
Síť Feistel
Síť SP
jiný