XXTEA

XXTEA
Skapare	David Wheeler och Roger Needham
Skapad	1998 _
publiceras	1998 _
Nyckelstorlek	128 bitar
Block storlek	bitar, där är antalet ord, inte mindre än 2
Antal omgångar	var - antalet ord
Sorts	Feistel nätverk

XXTEA  är en kryptografisk algoritm som implementerar blocksymmetrisk kryptering och är ett Feistel-nätverk . Det är en förlängning av Block TEA-algoritmen. Designad och publicerad av Wheeler och Roger 1998 Gjord på enkla och snabba operationer: XOR , substitution, addition. [1] [2]

Historik

Vid Fast Software Encryption Symposium i december 1994 presenterade David Wheeler och Roger Needham, professorer vid datorlaboratoriet vid University of Cambridge , den nya kryptografiska TEA -algoritmen . Denna algoritm designades som ett alternativ till DES , som vid den tiden redan ansågs vara föråldrad. [3] [4]

Senare 1996, under den personliga korrespondensen mellan David Wheeler och David Wagner, avslöjades en sårbarhet för den kopplade nyckelattacken , som officiellt presenterades 1997 vid den första internationella konferensen för ICIS av en grupp forskare bestående av Bruce Schneier , John Kelsey och David Wagner. [5] [6] Denna attack gav grunden för förbättringar av TEA- algoritmen , och i oktober 1996 publicerade Wheeler och Needham en intern labbrapport som citerade två nya algoritmer: XTEA och Block TEA. [7]

Den 10 oktober 1998 publicerade nyhetsgruppen sci.crypt.research en artikel av Markku-Juhani Saarinen där en Block TEA-sårbarhet hittades vid dekrypteringsstadiet [4] . Samma månad publicerade David Wheeler och Roger Needham en intern rapport från labbet som förbättrade Block TEA:s XXTEA-algoritm. [åtta]

Funktioner

XXTEA, liksom andra chiffer i TEA-familjen, har ett antal utmärkande egenskaper jämfört med liknande chiffer:

• Hög arbetshastighet
• Liten minnesförbrukning
• Enkel mjukvaruimplementering
• Relativt hög tillförlitlighet. [9] [10] [11] [4]

Beskrivning av algoritmen

Källtexten är uppdelad i ord om 32 bitar vardera, ett block bildas av de mottagna orden. Nyckeln är också uppdelad i 4 delar, bestående av ord på 32 bitar vardera, och en uppsättning nycklar bildas. Under en omgång av algoritmen krypteras ett ord från blocket. Efter att alla ord har krypterats slutar cykeln och en ny börjar. Antalet cykler beror på antalet ord och är lika med , där  är antalet ord. Kryptering av ett ord är som följer:

1. Vänster granne bitförskjuts åt vänster med två, och höger granne bitförskjuts åt höger med fem. De erhållna värdena är bitvis modulo 2 .
2. Vänster granne bitförskjuts till höger med tre, och höger granne bitförskjuts till vänster med 4. De erhållna värdena adderas bitvis modulo 2.
3. De resulterande talen läggs till modulo 2 32 .
4. Konstanten δ, härledd från det gyllene snittet δ = (  - 1) * 2 31 = 2654435769 = 9E3779B9 h [3] , multipliceras med cykelnumret (detta gjordes för att förhindra enkla attacker baserade på rund symmetri).
5. Antalet erhållet i föregående stycke adderas bit för bit modulo 2 med höger granne.
6. Siffran som erhålls i stycke 4 skiftas bitvis till höger med 2, adderas bitvis modulo två med det runda talet, och återstoden av divisionen med 4 hittas. Med hjälp av det resulterande talet väljs en nyckel från uppsättningen av nycklar.
7. Nyckeln som valts i föregående omgång läggs till bit för bit modulo 2 med vänster granne.
8. Siffrorna erhållna i föregående och 4 poäng läggs till modulo 2 32 .
9. Siffrorna som erhållits i föregående och 3 stycken läggs till bit för bit modulo 2, denna summa läggs till det krypterade ordet modulo 2 32 .

Kryptanalys

För tillfället finns det en adaptiv-klartextbaserad attack publicerad av Elias Jaarrkov 2010. Det finns två metoder som använder sig av att minska antalet loopar genom att öka antalet ord.

Första tillvägagångssättet

Anta att vi har en öppen text. Låt oss ta 5 vissa ord från det, som börjar med , som vi krypterar med . Låt oss lägga till ett nummer till , så får vi en ny klartext. Låt oss nu utföra den första krypteringscykeln för dessa texter. Om skillnaden efter kryptering bara kvarstår i detta ord, fortsätter vi kryptering. Om skillnader med andra ord börjar dyka upp, så börjar vi sökningen igen antingen genom att ändra den ursprungliga eller försöka hitta en annan skillnad. Att lagra skillnaden i endast ett ord är möjligt eftersom krypteringsfunktionen inte är bijektiv för varje granne. Elias Jaarrkov genomförde en serie experiment och fann att sannolikheten att gå igenom skillnaden på 5 hela cykler gav sannolikheten mellan och för de flesta nycklar, det vill säga om ett par texter gick igenom 5 av 6 hela cykler, så kan det anses vara korrekt, eftersom om du sätter skillnaden i slutet av blocket kommer det att finnas skillnader i de flesta ord. Denna attack genomfördes och nyckeln för algoritmen återställdes med antalet cykler reducerat till tre.

Den andra metoden

Det andra tillvägagångssättet skiljer sig från det första genom att efter den första omgången av kryptering av ordet, måste skillnaden gå in i det från själva ordet, medan skillnaden kan ändras, och efter nästa omgång av kryptering kommer skillnaden att återgå till ord och bli lika med den ursprungliga, men byt tecken. Efter att ha utvärderat denna metod fann Elias Jaarkov att 2 59 texter räcker för att lyckas hitta rätt par, och skillnaden borde ligga i intervallet , där , och ökad d inte förbättrade resultaten. En framgångsrik attack gjordes sedan på XXTEA med antalet cykler reducerat till 4, och det korrekta paret erhölls med 235 par texter, medan den tidigare uppskattningen ger behovet av 234,7 par texter.

Nyckelåterställning

Att känna till det korrekta paret av texter räcker det att köra algoritmen i omvänd ordning, eftersom vi nu vet allt utom nyckeln. [2] [12]

Anteckningar

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

Litteratur

• David J. Wheeler, Roger M. Needham. Rättelse till  XTEA . - 1998. - Oktober.
• E. Yarrkov. Kryptoanalys av XXTEA  (engelska) . - 2010. - 4 maj.
• Saarinen M.-J. Kryptanalys av Block  Tea . - 1998. - 20 oktober.
• David J. Wheeler, Roger M. Needham. TEA, en liten krypteringsalgoritm  . - 1994. - December.
• David J. Wheeler, Roger M. Needham. TEA-  förlängningar . - 1996. - Oktober.
• J. Kelsey, B. Schneier och D. Wagner. Relaterad nyckelkryptanalys av 3-WAY, Biham-DES,CAST, DES-X, NewDES, RC2 och  TEA . - 1997. - November.
• Mao Cenwei. Jämförelse av några små chiffer som är tillämpliga på RFID  . - 2008. - Juni.
• I. Sima, D. Tarmurean och V. Greu. XXTEA, en alternativ ersättning av KASUMI-chifferalgoritm i A5/3 GSM och f8, f9 UMTS datasäkerhetsfunktioner  . - 2012. - Juni.
• Första internationella konferensen, ICIS'97, Peking, Kina, 11-14 november 1997, Proceedings / Redaktörer: Yongfei Han, Tatsuaki Okamoto, Sihan Quing. - 1. - Springer-Verlag Berlin Heidelberg, 1997. - (Lecture Notes in Computer Science). - ISBN 978-3-540-63696-0 .