XTEA

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. dubna 2016; kontroly vyžadují 8 úprav .
XTEA
Tvůrce David Wheeler a Roger Needham
Vytvořeno 1997 _
zveřejněno 1997 _
Velikost klíče 128 bit
Velikost bloku 64 bit
Počet kol 64
Typ Síť Feistel

V kryptografii je XTEA (eXtended TEA )  blokový šifrovací algoritmus navržený k odstranění kritických chyb v algoritmu TEA . Vývojáři šifry jsou David Wheeler a Roger Needham (Department of Computer Science , University of Cambridge ). Algoritmus byl představen v nepublikované technické zprávě v roce 1997 [1] . Šifra není proprietární, je široce používána v řadě kryptografických aplikací a široké škále hardwaru kvůli extrémně nízkým nárokům na paměť a snadné implementaci.

Vlastnosti šifry

Stejně jako TEA je šifra založena na 64bitových blokových operacích, má 32 celých cyklů, každý celý cyklus má dvě kola Feistel Network , což znamená 64 kol Feistel Network. Počet nábojů pro dosažení lepší difúze však lze zvýšit na úkor výkonu. Kromě toho XTEA, stejně jako TEA, používá 128bitový klíč sestávající ze čtyř 32bitových slov K[0], K[1], K[2] a K[3]. XTEA nemá klíčový plánovací algoritmus v obvyklém smyslu. Aby bylo možné určit, které ze čtyř klíčových slov použít v každém kole, používá algoritmus konstantu δ = 9E3779B9 16 . V TEA taková distribuce neexistuje. Dalším rozdílem oproti TEA je permutace bitových operací použitých v šifře. Díky těmto vylepšením neprodělala XTEA ve srovnání s TEA větší komplikace, ale zároveň eliminovala dvě hlavní nevýhody algoritmu TEA [1] :

Popis algoritmu

XTEA používá následující logické operace: XOR , bitový posun a logické AND . XTEA navíc používá operaci sčítání celých čísel modulo 2 32 , označených jako x y (x a y Z 2 32 ). Exkluzivní "OR" v booleovské logice je označeno jako x y a v jazyce C jako x ^ y. Logické "AND" v booleovské logice je x y v jazyce C - x & y. Logický posun x o y bitů doleva se označí x y a logický posun x o y bitů doprava se označí x y. Nechť vstup n-tého (1 ≤ n ≤ 64) kola algoritmu je (L n ,R n ) a výstup je (L n+1 ,R n+1 ), přičemž L n+1 = R n . Rn +1 se vypočítá takto:

pokud n = 2 * i - 1 pro 1 ≤ i ≤ 32, pak R n+1 = L n + ({ (R n 4 R n 5) R n } ({ i - 1 } * δ K [ ({ i — 1 } * δ) 3 ]),

pokud n = 2 * i pro 1 ≤ i ≤ 32, pak R n+1 = L n + ({ (R n 4 R n 5) R n } (i * δ K [ (i * δ 11) 3 ]) .

Protože se jedná o blokovou šifru, kde délka bloku je 64 bitů a délka dat nemusí být násobkem 64 bitů, je hodnota všech bajtů vyplnění bloku na násobek 64 bitů nastavena na 0x01 .

Algoritmus kryptoanalýzy

Předpokládá se, že XTEA je bezpečnější než TEA, ale je možné zachytit typ útoku, pro který je XTEA zranitelnější [3] . Prvním přístupem jsou diferenciální útoky . Vzhledem k tomu, že TEA používá modulo 2 přidání 32 kruhové klávesy a vstupního prostého textu a XTEA používá XOR, je snazší napadnout XTEA diferenciálně než TEA. Po 14 kolech XTEA lze sestavit diferenciální charakteristiku s pravděpodobností 2 −57,79 a použít ji k rozbití XTEA, která obsahuje 16 kol (tento útok vyžaduje 2 61 vybraných otevřených textů). Zároveň je pro TEA obtížné vybudovat dobrou diferenciální charakteristiku. Druhým přístupem je zkrácený diferenciální útok. Po 8 kolech TEA a XTEA lze sestrojit zkrácenou diferenciální charakteristiku s pravděpodobností 1. Prostřednictvím tohoto útoku je možné rozbít XTEA s maximálním počtem kol 23 a TEA s maximálním počtem kol 17. Tento rozdíl je pozorován díky klíčovým plánovacím vlastnostem v každém z algoritmů.

Nejúspěšnějším publikovaným útokem na XTEA je diferenciální útok s propojeným klíčem, který je schopen prolomit 37 ze 64 kol algoritmu pomocí 263 vybraných otevřených textů s časovou složitostí 2125 . Pokud vezmeme v úvahu podmnožinu slabých klíčů, která zahrnuje 2 107,5 klíčů z 2 128 , pak je tento útok schopen prolomit 51 ze 64 kol algoritmu s časovou složitostí 2 123 [4] .

Příklad implementace algoritmu

Implementace šifrování a dešifrování pomocí algoritmu XTEA v jazyce C (převzato z kódu prezentovaného v článku Davida Wheelera a Rogera Needhama [1] ).

#include <stdint.h> void xtea_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { unsigned int i ; uint32_t v0 = v [ 0 ], v1 = v [ 1 ], součet = 0 , delta = 0x9E3779B9 ; for ( i = 0 ; i < počet_kol ; i ++ ) { v0 += ((( v1 << 4 ) ^ ( v1 >> 5 )) + v1 ) ^ ( součet + k [ součet & 3 ]); součet += delta ; v1 += ((( v0 << 4 ) ^ ( v0 >> 5 )) + v0 ) ^ ( součet + k [( součet >> 11 ) & 3 ]); } v [ 0 ] = v0 ; v [ 1 ] = v1 ; } void xtea_decipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { unsigned int i ; uint32_t v0 = v [ 0 ], v1 = v [ 1 ], delta = 0x9E3779B9 , suma = delta * počet_kol ; for ( i = 0 ; i < počet_kol ; i ++ ) { v1 -= ((( v0 << 4 ) ^ ( v0 >> 5 )) + v0 ) ^ ( součet + k [( součet >> 11 ) & 3 ]); součet -= delta ; v0 -= ((( v1 << 4 ) ^ ( v1 >> 5 )) + v1 ) ^ ( součet + k [ součet & 3 ]); } v [ 0 ] = v0 ; v [ 1 ] = v1 ; }

komentáře:

  • v - zdrojový text sestávající ze dvou slov po 32 bitech
  • k - klíč sestávající ze čtyř 32bitových slov
  • num_rounds — počet cyklů algoritmu (doporučeno 32)
  • num_rounds musí být stejné pro šifrování a dešifrování, pokud num_rounds==0, pak nedojde k šifrování ani dešifrování

Změny oproti původnímu kódu:

  • typ uint32_t se používá kvůli tomu, že má vždy velikost 32 bitů, na rozdíl od long (přítomného v původním kódu), který může obsahovat 64 bitů (například na některých 64bitových systémech)
  • zdrojový kód nepoužívá typ const
  • redundantní závorky ve výrazech pro v0 a v1 jsou ve zdrojovém kódu vynechány, v této úpravě jsou ponechány pro větší přehlednost

Verze algoritmu

Objevená zranitelnost v plánu klíčů a přítomnost úspěšných útoků na algoritmy TEA , XTEA a XXTEA vedly k vytvoření alternativních šifer řadou kryptoanalytiků. Konkrétně v současnosti existují algoritmy RTEA (Sean O'Neill), Raiden (Julio Castro), XTEA-1, XTEA-2 a XTEA-3 [ 5] (Tom St. Denis) založené na šifrách rodiny TEA . Tyto modifikace však nebyly tak široce studovány a nenašly dostatečné praktické uplatnění.

Algoritmus XTEA-1

Jednou ze zranitelností XTEA je to, že bity v klíči ovlivňují stejné bity v každém kole algoritmu. Tento problém lze eliminovat použitím šifry, která obsahuje algoritmus pro plánování klíčů. Plánování klíčů je dynamické a nevyžaduje alokaci paměti. Plánování klíče se provádí cyklickým bitovým posouváním klíče o hodnotu, která závisí na otevřeném textu. Algoritmus XTEA-1 implementuje tuto myšlenku posílení šifry XTEA mírnou změnou struktury šifry, aniž by se změnily základní principy algoritmu.

Šifra využívá technologii whitewashing a transformaci podklíče závislou na datech, což ztěžuje kryptoanalýzu , protože původní algoritmus obsahoval zranitelnost - úprava určitých klíčových bitů se projevila v odpovídajících bitech šifrového textu.

Implementace XTEA-1 v jazyce C :

#include <stdint.h> uint32_t rol ( základ uint32_t , posun uint32_t ) { uint32_t res ; /* pouze 5 bitů posunu je významných*/ posun &= 0x1F ; res = ( základ << posun ) | ( základ >> ( 32 - posun )); vrátit res ; } void xtea1_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { unsigned int i ; uint32_t y , z , součet = 0 , delta = 0x9E3779B9 ; /* načíst a předbílit registry */ y = v [ 0 ] + k [ 0 ]; z = v [ 1 ] + k [ 1 ]; /* Kulaté funkce */ for ( i = 0 ; i < počet_kol ; i ++ ) { y += (( z << 4 ) ^ ( z >> 5 )) + ( z ^ součet ) + rol ( k [ součet & 3 ], z ); součet += delta ; z += (( y << 4 ) ^ ( y >> 5 )) + ( y ^ součet ) + rol ( k [( součet >> 11 ) & 3 ], y ); } /* zveřejňovat a ukládat registry */ v [ 0 ] = y ^ k [ 2 ]; v [ 1 ] = z ^ k [ 3 ]; } void xtea1_decipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { unsigned int i ; uint32_t y , z , delta = 0x9E3779B9 , suma = delta * počet_kol ; z = v [ 1 ] ^ k [ 3 ]; y = v [ 0 ] ^ k [ 2 ]; for ( i = 0 ; i < počet_kol ; i ++ ) { z -= (( y << 4 ) ^ ( y >> 5 )) + ( y ^ součet ) + rol ( k [( součet >> 11 ) & 3 ], y ); součet -= delta ; y -= (( z << 4 ) ^ ( z >> 5 )) + ( z ^ součet ) + rol ( k [ součet & 3 ], z ); } v [ 1 ] = z - k [ 1 ]; v [ 0 ] = y - k [ 0 ]; }

Funkce 'rol' provádí cyklický bitový posun klíče pomocí nejméně významných 5 bitů posunu. Tento algoritmus používá pouze jeden posun za kolo, což je na většině moderních procesorů poměrně efektivní a rychlé .

Algoritmus XTEA-2

XTEA-1 je možné změnit pomocí 128bitového bloku. Výsledný algoritmus vyžaduje více kol, ale jeho rychlost šifrování je vyšší než u XTEA.

Implementace XTEA-2 v C :

#include <stdint.h> void xtea2_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ){ unsigned int i ; uint32_ta , b , c , d , součet = 0 , t , delta = 0x9E3779B9 ; _ a = v [ 0 ]; b = v [ 1 ] + k [ 0 ]; c = v [ 2 ]; d = v [ 3 ] + k [ 1 ]; for ( i = 0 ; i < počet_kol ; i ++ ) { a += (( b << 4 ) ^ ( b >> 5 )) + ( d ^ součet ) + rol ( k [ součet & 3 ], b ); součet += delta ; c += (( d << 4 ) ^ ( d >> 5 )) + ( b ^ součet ) + rol ( k [( součet >> 11 ) & 3 ], d ); t = a ; a = b_ _ b = c ; c = d ; d = t ; } v [ 0 ] = a ^ k [ 2 ]; v [ 1 ] = b ; v [ 2 ] = c ^ k [ 3 ]; v [ 3 ] = d ; } void xtea2_decipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ){ unsigned int i ; uint32_ta , b , c , d , t , delta = 0x9E3779B9 , součet = delta * počet_kol ; _ d = v [ 3 ]; c = v [ 2 ] ^ k [ 3 ]; b = v [ 1 ]; a = v [ 0 ] ^ k [ 2 ]; for ( i = 0 ; i < počet_kol ; i ++ ) { t = d _ d = c ; c = b _ b = a ; a = t_ _ c -= (( d << 4 ) ^ ( d >> 5 )) + ( b ^ součet ) + rol ( k [( součet >> 11 ) & 3 ], d ); součet -= delta ; a -= (( b << 4 ) ^ ( b >> 5 )) + ( d ^ součet ) + rol ( k [ součet & 3 ], b ); } v [ 0 ] = a ; v [ 1 ] = b - k [ 0 ]; v [ 2 ] = c ; v [ 3 ] = d - k [ 1 ]; }

Hlavní výhodou tohoto algoritmu je schopnost šifrovat velké bloky. Tento algoritmus používá stejné základní operace jako XTEA-1, ale vyžaduje více iterací. Ve skutečnosti vyžaduje dvakrát tolik iterací od 32 do 64 (od 64 do 128 kol). 48 iterací je kompromisem mezi rychlostí a spolehlivostí šifrování.

Algoritmus XTEA-3

Dalším přirozeným rozšířením XTEA-1 je použití 256bitového klíče a praktičtějšího 128bitového bloku. Tento algoritmus vyžaduje 32 až 64 iterací, ale zároveň poskytuje spolehlivou ochranu proti útokům vyčerpávajícím vyhledáváním. Šifra používá technologii whitewashing a implementuje operace závislé na klíči, což ztěžuje kryptoanalýzu.

Implementace XTEA-3 v C :

#include <stdint.h> void xtea3_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { unsigned int i ; uint32_ta , b , c , d , součet = 0 , t , delta = 0x9E3779B9 ; _ součet = 0 ; a = v [ 0 ] + k [ 0 ]; b = v [ 1 ] + k [ 1 ]; c = v [ 2 ] + k [ 2 ]; d = v [ 3 ] + k [ 3 ]; for ( i = 0 ; i < num_rounds ; i ++ ){ a += ((( b << 4 ) + rol ( k [( součet % 4 ) + 4 ], b )) ^ ( d + součet ) ^ (( b >> 5 ) + rol ( k [ součet % 4 ], b >> 27 ))); součet += delta ; c += ((( d << 4 ) + rol ( k [(( součet >> 11 ) % 4 ) + 4 ], d )) ^ ( b + součet ) ^ (( d >> 5 ) + rol ( k [( součet >> 11 ) % 4 ], d >> 27 ))); t = a ; a = b_ _ b = c ; c = d ; d = t ; } v [ 0 ] = a ^ k [ 4 ]; v [ 1 ] = b ^ k [ 5 ]; v [ 2 ] = c ^ k [ 6 ]; v [ 3 ] = d ^ k [ 7 ]; } void xtea3_decipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { unsigned int i ; uint32_ta , b , c , d , t , delta = 0x9E3779B9 , součet = delta * počet_kol ; _ d = v [ 3 ] ^ k [ 7 ]; c = v [ 2 ] ^ k [ 6 ]; b = v [ 1 ] ^ k [ 5 ]; a = v [ 0 ] ^ k [ 4 ]; for ( i = 0 ; i < num_rounds ; i ++ ){ t = d _ d = c ; c = b _ b = a ; a = t_ _ c -= ((( d << 4 ) + rol ( k [(( součet >> 11 ) % 4 ) + 4 ], d )) ^ ( b + součet ) ^ (( d >> 5 ) + rol ( k [( součet >> 11 ) % 4 ], d >> 27 ))); součet -= delta ; a -= ((( b << 4 ) + rol ( k [( součet % 4 ) + 4 ], b )) ^ ( d + součet ) ^ (( b >> 5 ) + rol ( k [ součet % 4 ], b >> 27 ))); } v [ 3 ] = d - k [ 3 ]; v [ 2 ] = c - k [ 2 ]; v [ 1 ] = b - k [ 1 ]; v [ 0 ] = a - k [ 0 ]; }

XTEA-3 používá 5 MSB a 5 LSB registru prostého textu k otáčení klíče, protože statistiky ukazují, že tyto bity jsou nejvíce náchylné ke změně. Tento algoritmus také vyžaduje minimálně 32 iterací, avšak 48 iterací je kompromisem mezi rychlostí a spolehlivostí šifrování dat.

Porovnání různých verzí rozšíření XTEA

Tyto tři algoritmy jsou přirozeným rozšířením TEA a XTEA. Jejich charakteristické rysy ve srovnání s původními šifrovacími algoritmy jsou lepší rozvrh klíčů a větší blok a/nebo velikost klíče. Použití klíčů, které jsou dynamicky závislé na otevřeném textu, znamená, že neexistuje žádné předem určené pořadí pro použití klíčů a není vyžadována alokace paměti. To je poměrně užitečná vlastnost, protože úkol objevit nejčastěji používané klíče se stává obtížnější. Šifry jsou bezpečnější proti rozdílové kryptoanalýze , protože bity v klíči mohou ovlivnit jakékoli jiné bity v šifrovaném textu. Použití nelineární algebry (sčítání modulo 2 32 kromě "OR") je účinné proti lineární kryptoanalýze . Kromě toho použití těchto operací nezavádí do algoritmů zranitelnosti.

První algoritmus (XTEA-1) má nejvyšší rychlost a při dostatečném počtu kol (od 32 do 64) má dobrou spolehlivost. XTEA-2 je větší blokové rozšíření a není o nic bezpečnější než XTEA-1. XTEA-3 je rozšířením algoritmu pomocí větší velikosti bloku a klíče. Třetí možnost je o něco pomalejší, ale bezpečnější. Vzhledem k tomu, že tyto algoritmy jsou založeny na původním TEA s odstraněním všech známých nedostatků, lze je považovat za poměrně spolehlivé.

Srovnávací tabulka algoritmů:

Název algoritmu Minimální počet kol Maximální počet kol Velikost bloku Velikost klíče
XTEA-1 32 64 64 bitů 128 bit
XTEA-2 64 128 128 bit 128 bit
XTEA-3 64 128 128 bit 256 bit

Tyto algoritmy však stále vyžadují další vylepšení. Prvním problémem je, že pro klíčové cyklické bitové posouvání se používají pouze nejméně významné bity otevřeného textu (jako v XTEA-1 a XTEA-2). Druhým problémem je, že klíč je rozdělen do dvou podskupin po 4 prvcích a každá část výrazu používá pouze jednu podskupinu (jako v XTEA-3). XTEA-3 lze rozšířit použitím všech osmi prvků v obou částech výrazu. Pokud dojde k těmto vylepšením, algoritmus se stane praktičtějším, ale pak se bude příliš lišit od původního TEA.

Viz také

Poznámky

  1. ↑ 1 2 3 A. Roger M. Needham a David J. Wheeler. Tea extensions Archivováno 20. září 2017 na Wayback Machine
  2. ↑ John Kelsey, Bruce Schneier, David Wagner. Související klíčová kryptoanalýza 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, TEA  (nedostupný odkaz)
  3. ↑ Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee. Diferenciální kryptoanalýza TEA a XTEA  (nedostupný odkaz)
  4. ↑ Charles Bouillaguet, Orr Dunkelman, Gaetan Leurent a Pierre-Alain Fouque. Další pohled na vlastnosti komplementace Archivováno 6. července 2017 na Wayback Machine
  5. ↑ Tom St Denis. Extended TEA Algorithms Archived 27. srpna 2018 na Wayback Machine

Odkazy

  • David J. Wheeler a Roger M. Needham. Oprava na xtea. Technická zpráva, Computer Laboratory, University of Cambridge, říjen 1998 (PDF) .
  • Dukjae Moon, Kyungdeok Hwang, Wonil Lee, Sangjin Lee a Jongin Lim. "Nemožná diferenciální kryptoanalýza redukovaného kulatého XTEA a TEA." Centrum pro informační a bezpečnostní technologie (CIST), 2004 (PDF)  (odkaz není k dispozici) .
Implementace
 Symetrické kryptosystémy
Streamové šifry
Síť Feistel
Síť SP
jiný