XTEA

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 29 aprilie 2016; verificările necesită 8 modificări .

XTEA

Creator	David Wheeler și Roger Needham
Creată	1997 _
publicat	1997 _
Dimensiunea cheii	128 de biți
Dimensiunea blocului	pe 64 de biți
Numărul de runde	64
Tip de	Rețeaua Feistel

În criptografie , XTEA (eXtended TEA ) este un algoritm de criptare bloc conceput pentru a elimina erorile critice din algoritmul TEA . Dezvoltatorii cifrului sunt David Wheeler și Roger Needham (Departamentul de Informatică , Universitatea din Cambridge ). Algoritmul a fost prezentat într-un raport tehnic nepublicat în 1997 [1] . Cifrul nu este proprietar, utilizat pe scară largă într-o serie de aplicații criptografice și într-o gamă largă de hardware datorită cerințelor sale extrem de scăzute de memorie și ușurinței de implementare.

Proprietăți Cipher

La fel ca TEA , cifrul se bazează pe operațiuni de bloc pe 64 de biți, are 32 de cicluri complete, fiecare ciclu complet are două runde Feistel Network , adică 64 de runde Feistel Network. Cu toate acestea, numărul de runde pentru a obține o difuzie mai bună poate fi crescut în detrimentul performanței. În plus, XTEA, ca și TEA, utilizează o cheie de 128 de biți constând din patru cuvinte de 32 de biți K[0], K[1], K[2] și K[3]. XTEA nu are un algoritm de programare cheie în sensul obișnuit. Pentru a determina care dintre cele patru cuvinte cheie să folosească în fiecare rundă, algoritmul folosește constanta δ = 9E3779B9 16 . În TEA, nu există o astfel de distribuție. O altă diferență față de TEA este permutarea operațiilor pe biți utilizate în cifr. Datorită acestor îmbunătățiri, XTEA nu a suferit complicații majore în comparație cu TEA, dar în același timp a eliminat două dezavantaje principale ale algoritmului TEA [1] :

fiecare cheie din TEA este echivalentă cu alte trei, ceea ce înseamnă că lungimea efectivă a cheii este de 126 de biți în loc de 128, așa cum a fost intenționat de dezvoltatori;
TEA este susceptibil la atacuri asupra cheilor asociate. Un astfel de atac poate necesita doar 2 23 de texte clare alese și poate avea o complexitate temporală de 2 32 [2] .

Descrierea algoritmului

XTEA utilizează următoarele operații logice: XOR , deplasare de biți și AND logic . În plus, XTEA utilizează operația de adăugare a numerelor întregi modulo 2 32 , notate cu x y (x și y Z 2 32 ). „SAU” exclusiv în logica booleană este notat cu x y, iar în limbajul C cu x ^ y. „ȘI” logic în logica booleană este x y în limbajul C - x & y. O deplasare logică a lui x cu y biți la stânga este notată cu x y, iar o deplasare logică a x cu y biți spre dreapta este notă cu x y. Fie intrarea rundei a n-a (1 ≤ n ≤ 64) a algoritmului (L n ,R n ), iar rezultatul este (L n+1 ,R n+1 ), cu L n+1 = R n . R n+1 se calculează după cum urmează: $\box plus$ $\în$ $\oplus$ $\teren$ $\ll$ $\gg$

dacă n = 2 * i - 1 pentru 1 ≤ i ≤ 32, atunci R n+1 = L n + ({ (R n 4 R n 5) R n } ({ i - 1 } * δ K [ ({ i — 1 } * δ) 3 ]), $\ll$ $\oplus$ $\gg$ $\box plus$ $\oplus$ $\box plus$ $\teren$

dacă n = 2 * i pentru 1 ≤ i ≤ 32, atunci R n+1 = L n + ({ (R n 4 R n 5) R n } (i * δ K [ (i * δ 11) 3 ]) . $\ll$ $\oplus$ $\gg$ $\box plus$ $\oplus$ $\box plus$ $\gg$ $\teren$

Deoarece acesta este un cifru bloc, unde lungimea blocului este de 64 de biți și lungimea datelor poate să nu fie un multiplu de 64 de biți, valoarea tuturor octeților care completează blocul la un multiplu de 64 de biți este setată la 0x01 .

Algoritmul de criptoanaliza

Se crede că XTEA este mai sigur decât TEA, dar este posibil să se ridice un tip de atac pentru care XTEA este mai vulnerabil [3] . Prima abordare este atacurile diferențiale . Deoarece TEA folosește adăugarea modulo 2 a tastei cu 32 rotunde și introduce text simplu, iar XTEA folosește XOR, este mai ușor să ataci XTEA diferențial decât TEA. După 14 runde de XTEA, se poate construi o caracteristică diferențială cu o probabilitate de 2 −57,79 și o poate folosi pentru a sparge un XTEA care include 16 runde (acest atac necesită 2 61 de texte clare alese). În același timp, este dificil pentru TEA să construiască o caracteristică diferențială bună. A doua abordare este un atac diferențial trunchiat. După 8 runde de TEA și XTEA, se poate construi o caracteristică diferențială trunchiată cu probabilitatea 1. Prin acest atac, este posibilă spargerea XTEA cu un număr maxim de runde de 23 și TEA cu un număr maxim de runde de 17. Această diferență se observă datorită proprietăților cheie de planificare în fiecare dintre algoritmi.

Cel mai de succes atac publicat asupra XTEA este atacul diferențial cu chei legate, care este capabil să spargă 37 din 64 de runde ale algoritmului folosind 263 de texte clare alese cu o complexitate de timp de 2125 . Dacă luăm în considerare un subset de chei slabe, care include 2 107,5 chei din 2 128 , atunci acest atac este capabil să spargă 51 din 64 de runde ale algoritmului cu o complexitate de timp de 2 123 [4] .

Un exemplu de implementare a algoritmului

Implementarea limbajului C (adaptat din codul prezentat în articolul lui David Wheeler și Roger Needham [1] ) a criptării și decriptării folosind algoritmul XTEA:

#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 ], sum = 0 , delta = 0x9E3779B9 ; pentru ( i = 0 ; i < num_rounds ; i ++ ) { v0 += ((( v1 << 4 ) ^ ( v1 >> 5 )) + v1 ) ^ ( suma + k [ suma & 3 ]); suma += delta ; v1 += ((( v0 << 4 ) ^ ( v0 >> 5 )) + v0 ) ^ ( suma + k [( suma >> 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 , sum = delta * num_rounds ; pentru ( i = 0 ; i < num_rounds ; i ++ ) { v1 -= ((( v0 << 4 ) ^ ( v0 >> 5 )) + v0 ) ^ ( suma + k [( suma >> 11 ) & 3 ]); suma -= delta ; v0 -= ((( v1 << 4 ) ^ ( v1 >> 5 )) + v1 ) ^ ( suma + k [ suma & 3 ]); } v [ 0 ] = v0 ; v [ 1 ] = v1 ; }

Comentarii:

v - text sursă format din două cuvinte de 32 de biți
k - o cheie formată din patru cuvinte de 32 de biți
num_rounds — numărul de cicluri de algoritm (recomandat 32)
num_rounds trebuie să fie același pentru criptare și decriptare, dacă num_rounds==0, atunci nu vor avea loc nici criptarea, nici decriptarea

Modificări față de codul original:

tipul uint32_t este folosit datorită faptului că are întotdeauna o dimensiune de 32 de biți, spre deosebire de long (prezent în codul original), care poate conține 64 de biți (de exemplu, pe unele sisteme pe 64 de biți)
codul sursă nu folosește tipul const
parantezele redundante din expresiile pentru v0 și v1 sunt omise în codul sursă, în această modificare sunt lăsate pentru o mai mare claritate

Versiuni ale algoritmului

Vulnerabilitățile descoperite în programul cheie și prezența atacurilor de succes asupra algoritmilor TEA , XTEA și XXTEA au condus la crearea unor cifruri alternative de către un număr de criptoanalisti. În special, în prezent există algoritmi RTEA (Sean O'Neill), Raiden (Julio Castro), XTEA-1, XTEA-2 și XTEA-3 [ 5] (Tom St. Denis) bazați pe cifrurile familiei TEA . Cu toate acestea, aceste modificări nu au fost studiate atât de larg și nu au primit suficientă aplicare practică.

Algoritmul XTEA-1

Una dintre vulnerabilitățile din XTEA este că biții din cheie afectează aceiași biți în fiecare rundă a algoritmului. Această problemă poate fi eliminată prin utilizarea unui cifr care include un algoritm de programare a cheilor. Programarea cheilor este dinamică și nu necesită alocare de memorie. Programarea cheii se face prin deplasarea ciclică a biților a cheii cu o valoare care depinde de textul simplu. Algoritmul XTEA-1 implementează această idee de consolidare a cifrului XTEA modificând ușor structura cifrului fără a schimba principiile de bază ale algoritmului.

Cifrul folosește tehnologia de văruire și transformarea subcheilor dependentă de date, ceea ce face criptanaliza dificilă , deoarece algoritmul original conținea o vulnerabilitate - modificarea anumitor biți cheie a fost reflectată în biții corespunzători ai textului cifrat.

Implementarea XTEA-1 în limbajul C :

#include <stdint.h> uint32_t rol ( uint32_t de bază , uint32_t shift ) { uint32_t res ; /* doar 5 biți de schimbare sunt semnificativi*/ deplasare &= 0x1F ; res = ( baza << shift ) | ( baza >> ( 32 - shift )); return res ; } void xtea1_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { unsigned int i ; uint32_t y , z , sum = 0 , delta = 0x9E3779B9 ; /* încărcați și prealbiți registrele */ y = v [ 0 ] + k [ 0 ]; z = v [ 1 ] + k [ 1 ]; /* Funcții rotunde */ pentru ( i = 0 ; i < num_rounds ; i ++ ) { y += (( z << 4 ) ^ ( z >> 5 )) + ( z ^ sum ) + rol ( k [ sum & 3 ], z ); suma += delta ; z += (( y << 4 ) ^ ( y >> 5 )) + ( y ^ sum ) + rol ( k [( sum >> 11 ) & 3 ], y ); } /* postează registre albe și magazine */ 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 , sum = delta * num_rounds ; z = v [ 1 ] ^ k [ 3 ]; y = v [ 0 ] ^ k [ 2 ]; pentru ( i = 0 ; i < num_rounds ; i ++ ) { z -= (( y << 4 ) ^ ( y >> 5 )) + ( y ^ sum ) + rol ( k [( sum >> 11 ) & 3 ], y ); suma -= delta ; y -= (( z << 4 ) ^ ( z >> 5 )) + ( z ^ sum ) + rol ( k [ sum & 3 ], z ); } v [ 1 ] = z - k [ 1 ]; v [ 0 ] = y - k [ 0 ]; }

Funcția „rol” efectuează o schimbare ciclică de biți a tastei folosind cei 5 biți mai puțin semnificativi de deplasare. Acest algoritm folosește doar o schimbare pe rundă, care este destul de eficient și rapid pe majoritatea procesoarelor moderne .

Algoritmul XTEA-2

Este posibil să schimbați XTEA-1 folosind un bloc de 128 de biți. Algoritmul rezultat necesită mai multe runde, dar viteza sa de criptare este mai mare decât cea a XTEA.

Implementarea XTEA-2 în C :

#include <stdint.h> void xtea2_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ){ unsigned int i ; uint32_t a , b , c , d , sum = 0 , t , delta = 0x9E3779B9 ; a = v [ 0 ]; b = v [ 1 ] + k [ 0 ]; c = v [ 2 ]; d = v [ 3 ] + k [ 1 ]; pentru ( i = 0 ; i < num_rounds ; i ++ ) { a += (( b << 4 ) ^ ( b >> 5 )) + ( d ^ sum ) + rol ( k [ sum & 3 ], b ); suma += delta ; c += (( d << 4 ) ^ ( d >> 5 )) + ( b ^ sum ) + rol ( k [( sum >> 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_t a , b , c , d , t , delta = 0x9E3779B9 , sum = delta * num_rounds ; d = v [ 3 ]; c = v [ 2 ] ^ k [ 3 ]; b = v [ 1 ]; a = v [ 0 ] ^ k [ 2 ]; pentru ( i = 0 ; i < num_rounds ; i ++ ) { t = d _ d = c ; c = b _ b = a ; a = t _ c -= (( d << 4 ) ^ ( d >> 5 )) + ( b ^ sum ) + rol ( k [( sum >> 11 ) & 3 ], d ); suma -= delta ; a -= (( b << 4 ) ^ ( b >> 5 )) + ( d ^ sum ) + rol ( k [ sum & 3 ], b ); } v [ 0 ] = a ; v [ 1 ] = b - k [ 0 ]; v [ 2 ] = c ; v [ 3 ] = d - k [ 1 ]; }

Principalul avantaj al acestui algoritm este capacitatea de a cripta blocuri mari. Acest algoritm folosește aceleași operațiuni de bază ca XTEA-1, dar necesită mai multe iterații. De fapt, necesită de două ori mai multe iterații de la 32 la 64 (de la 64 la 128 de runde). 48 de iterații reprezintă un compromis între viteza și fiabilitatea criptării.

Algoritmul XTEA-3

O altă extensie naturală a XTEA-1 este utilizarea unei chei de 256 de biți și a blocului mai practic de 128 de biți. Acest algoritm necesită de la 32 la 64 de iterații, dar în același timp oferă protecție fiabilă împotriva atacurilor prin căutare exhaustivă. Cifrul folosește tehnologia de văruire și implementează operațiuni dependente de cheie, ceea ce îngreunează criptoanaliza.

Implementarea XTEA-3 în C :

#include <stdint.h> void xtea3_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { unsigned int i ; uint32_t a , b , c , d , sum = 0 , t , delta = 0x9E3779B9 ; suma = 0 ; a = v [ 0 ] + k [ 0 ]; b = v [ 1 ] + k [ 1 ]; c = v [ 2 ] + k [ 2 ]; d = v [ 3 ] + k [ 3 ]; pentru ( i = 0 ; i < num_rounds ; i ++ ){ a += ((( b << 4 ) + rol ( k [( suma % 4 ) + 4 ], b )) ^ ( d + suma ) ^ (( b >> 5 ) + rol ( k [ suma % 4 ], b >> 27 ))); suma += delta ; c += ((( d << 4 ) + rol ( k [(( suma >> 11 ) % 4 ) + 4 ], d )) ^ ( b + suma ) ^ (( d >> 5 ) + rol ( k [( suma >> 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_t a , b , c , d , t , delta = 0x9E3779B9 , sum = delta * num_rounds ; d = v [ 3 ] ^ k [ 7 ]; c = v [ 2 ] ^ k [ 6 ]; b = v [ 1 ] ^ k [ 5 ]; a = v [ 0 ] ^ k [ 4 ]; pentru ( i = 0 ; i < num_rounds ; i ++ ){ t = d _ d = c ; c = b _ b = a ; a = t _ c -= ((( d << 4 ) + rol ( k [(( suma >> 11 ) % 4 ) + 4 ], d )) ^ ( b + suma ) ^ (( d >> 5 ) + rol ( k [( suma >> 11 ) % 4 ], d >> 27 ))); suma -= delta ; a -= ((( b << 4 ) + rol ( k [( suma % 4 ) + 4 ], b )) ^ ( d + suma ) ^ (( b >> 5 ) + rol ( k [ suma % 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 folosește cele 5 MSB și 5 LSB-uri ale registrului de text simplu pentru a roti cheia, deoarece statisticile arată că acești biți sunt cei mai susceptibili la schimbare. Acest algoritm necesită, de asemenea, cel puțin 32 de iterații, cu toate acestea, 48 de iterații reprezintă un compromis între viteza și fiabilitatea criptării datelor.

Comparația diferitelor versiuni ale extensiei XTEA

Acești trei algoritmi sunt extensii naturale ale TEA și XTEA. Caracteristicile lor distinctive în comparație cu algoritmii de criptare inițiali sunt o programare mai bună a cheilor și un bloc mai mare și/sau dimensiunea cheii. Utilizarea cheilor care sunt dependente dinamic de textul simplu înseamnă că nu există o ordine predeterminată pentru utilizarea cheilor și nu este necesară alocarea de memorie. Aceasta este o proprietate destul de utilă, deoarece sarcina de a descoperi cheile cele mai frecvent utilizate devine mai dificilă. Cifrurile sunt mai sigure împotriva criptoanalizei diferențiale , deoarece biții din cheie pot afecta orice alți biți din textul cifrat. Utilizarea algebrei neliniare (adăugare modulo 2 32 excluzând „OR”) este eficientă împotriva criptoanalizei liniare . În plus, utilizarea acestor operațiuni nu introduce vulnerabilități în algoritmi.

Primul algoritm (XTEA-1) are cea mai mare viteză și, cu un număr suficient de runde (de la 32 la 64), are o fiabilitate bună. XTEA-2 este o extensie de bloc mai mare și nu este mai sigură decât XTEA-1. XTEA-3 este o extensie a algoritmului care utilizează o dimensiune de bloc și o cheie mai mare. A treia opțiune este puțin mai lentă, dar mai sigură. Deoarece acești algoritmi se bazează pe TEA original cu eliminarea tuturor deficiențelor cunoscute, ei pot fi considerați destul de fiabili.

Tabel comparativ al algoritmilor:

Numele algoritmului	Număr minim de runde	Număr maxim de runde	Dimensiunea blocului	Dimensiunea cheii
XTEA-1	32	64	64 de biți	128 de biți
XTEA-2	64	128	128 de biți	128 de biți
XTEA-3	64	128	128 de biți	256 de biți

Cu toate acestea, acești algoritmi necesită încă o rafinare suplimentară. Prima problemă este că numai biții mai puțin semnificativi ai textului clar sunt utilizați pentru deplasarea ciclică a biților cheie (ca în XTEA-1 și XTEA-2). A doua problemă este că cheia este împărțită în două subgrupuri de 4 elemente, iar fiecare parte a expresiei folosește doar un subgrup (ca în XTEA-3). XTEA-3 poate fi extins folosind toate cele opt elemente din ambele părți ale expresiei. Dacă se fac aceste îmbunătățiri, atunci algoritmul va deveni mai practic, dar atunci va fi prea diferit de TEA original.

Vezi și

Note

↑ 1 2 3 A. Roger M. Needham și David J. Wheeler. Extensii de ceai Arhivat pe 20 septembrie 2017 la Wayback Machine
↑ John Kelsey, Bruce Schneier, David Wagner. Criptanaliză cheie asociată pentru 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, TEA (link indisponibil)
↑ Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee. Criptanaliză diferențială a TEA și XTEA (link indisponibil)
↑ Charles Bouillaguet, Orr Dunkelman, Gaetan Leurent și Pierre-Alain Fouque. O altă privire asupra proprietăților de completare Arhivată 6 iulie 2017 la Wayback Machine
↑ Tom St Denis. Algoritmi extinși TEA Arhivat 27 august 2018 la Wayback Machine

Link -uri

David J. Wheeler și Roger M. Needham. Corectare la xtea. Raport tehnic, Laboratorul de calculatoare, Universitatea din Cambridge, octombrie 1998 (PDF) .
Dukjae Moon, Kyungdeok Hwang, Wonil Lee, Sangjin Lee și Jongin Lim. „Criptanaliză diferențială imposibilă a rotundei reduse XTEA și TEA”. Center for Information and Security Technologies (CIST), 2004 (PDF) (link nu este disponibil) .

Implementări

The Tiny Encryption Algorithm (TEA) , Simon Shepherd, 24 februarie 2006 — Pagină web cu descrieri și link-uri către diverse implementări XTEA
Implementarea XTEA în PHP
Implementarea XTEA în Java (32 de treceri)
Criptare Python XTEA (rețetă Python) - Implementarea Python a XTEA
Implementarea XTEA pe Verilog (pentru FPGA )
Referitor la implementarea algoritmilor XTEA-1, XTEA-2, XTEA-3 în C din Python

Criptosisteme simetrice
Cifruri în flux	A3 A5 A8 Decim F-FCSR Cereale HC-256 KCipher-2 MICKEY MUGI ŞTIUCĂ Phelix RC4 Iepure SIGILIU ZĂPADĂ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Rețeaua Feistel	GOST 28147-89 (Magma) blowfish Camelia CAST-128 CAST-256 CIFERUNICORN-A CIFERUNICORN-E CLEFIA Cobra AFACERE DES DESX DFC E2 ENRUPT FEAL HPC IDEE KASUMI Khafre Khufu LOKI97 MacGuffin MARTE PLASĂ CEȚA1 NewDES NDS RC5 RC6 SEMINTA Simon Sinople lista SM4 Speck CEAI XTEA XXTEA Raiden RTEA Triplu DES Doi pești
Rețeaua SP	Lăcustă 3 căi ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Centura CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer prezent Curcubeu MAI SIGUR RECHIN PĂTRAT Şarpe trei pești
Alte	BROASCĂ NUSH REDOC SC2000 SHACAL CS-Cipher