XXTEA

XXTEA
Skaber	David Wheeler og Roger Needham
Oprettet	1998 _
offentliggjort	1998 _
Nøglestørrelse	128 bit
Blokstørrelse	bits, hvor er antallet af ord, ikke mindre end 2
Antal runder	, hvor er antallet af ord
Type	Feistel netværk

XXTEA  er en kryptografisk algoritme , der implementerer bloksymmetrisk kryptering og er et Feistel-netværk . Det er en udvidelse af Block TEA-algoritmen. Designet og udgivet af Wheeler og Roger i 1998 Lavet på enkle og hurtige operationer: XOR , substitution, addition. [1] [2]

Historie

Ved Fast Software Encryption Symposium i december 1994 præsenterede David Wheeler og Roger Needham, professorer ved Computer Laboratory ved University of Cambridge , den nye TEA kryptografiske algoritme . Denne algoritme blev designet som et alternativ til DES , som på det tidspunkt allerede blev betragtet som forældet. [3] [4]

Senere i 1996, i løbet af personlig korrespondance mellem David Wheeler og David Wagner, blev en sårbarhed over for det forbundne nøgleangreb afsløret , som officielt blev præsenteret i 1997 ved den første internationale konference for ICIS af en gruppe videnskabsmænd bestående af Bruce Schneier , John Kelsey og David Wagner. [5] [6] Dette angreb gav grundlaget for forbedringer af TEA- algoritmen , og i oktober 1996 offentliggjorde Wheeler og Needham en intern laboratorierapport, der citerede to nye algoritmer: XTEA og Block TEA. [7]

Den 10. oktober 1998 udgav nyhedsgruppen sci.crypt.research en artikel af Markku-Juhani Saarinen, hvori der blev fundet en Block TEA-sårbarhed på dekrypteringsstadiet [4] . I samme måned offentliggjorde David Wheeler og Roger Needham en intern rapport fra laboratoriet, der forbedrede Block TEA's XXTEA-algoritme. [otte]

Funktioner

XXTEA har ligesom andre cifre i TEA-familien en række karakteristiske træk sammenlignet med lignende cifre:

• Høj driftshastighed
• Lavt hukommelsesforbrug
• Enkel softwareimplementering
• Relativ høj pålidelighed. [9] [10] [11] [4]

Beskrivelse af algoritmen

Kildeteksten er opdelt i ord på 32 bit hver, en blok dannes ud fra de modtagne ord. Nøglen er også opdelt i 4 dele, bestående af ord på hver 32 bit, og der dannes en række nøgler. I løbet af en runde af algoritmen krypteres ét ord fra blokken. Når alle ordene er blevet krypteret, slutter cyklussen, og en ny begynder. Antallet af cyklusser afhænger af antallet af ord og er lig med , hvor  er antallet af ord. Kryptering af et ord er som følger:

1. Den venstre nabo er bit forskudt til venstre med to, og den højre nabo er bit forskudt til højre med fem. De opnåede værdier er bitvise modulo 2 .
2. Den venstre nabo bit-forskydes til højre med tre, og den højre nabo bit-forskydes til venstre med 4. De opnåede værdier adderes bitvis modulo 2.
3. De resulterende tal tilføjes modulo 2 32 .
4. Konstanten δ, afledt af det gyldne forhold δ = (  - 1) * 2 31 = 2654435769 = 9E3779B9 h [3] , multipliceres med cyklusnummeret (dette blev gjort for at forhindre simple angreb baseret på rund symmetri).
5. Tallet opnået i det foregående afsnit tilføjes bit for bit modulo 2 med den højre nabo.
6. Tallet opnået i afsnit 4 forskydes bitvis til højre med 2, tilføjes bitvist modulo 2 med det runde tal, og resten af ​​divideringen med 4 findes. Ved hjælp af det resulterende tal vælges en nøgle fra rækken af ​​nøgler.
7. Nøglen valgt i den foregående runde tilføjes bit for bit modulo 2 med venstre nabo.
8. Tallene opnået i det foregående og 4 punkter tilføjes modulo 2 32 .
9. Tallene opnået i de foregående og 3 afsnit tilføjes bit for bit modulo 2, denne sum tilføjes til det krypterede ord modulo 2 32 .

Krypteringsanalyse

I øjeblikket er der et adaptivt-klartekst-baseret angreb udgivet af Elias Jaarrkov i 2010. Der er to tilgange, der bruger at reducere antallet af sløjfer ved at øge antallet af ord.

Første tilgang

Antag, at vi har en åben tekst. Lad os tage 5 bestemte ord fra det, begyndende med , som vi krypterer med . Lad os tilføje et tal til , og vi får en ny klartekst. Lad os nu udføre den første krypteringscyklus for disse tekster. Hvis forskellen efter kryptering kun forbliver i dette ord, fortsætter vi kryptering. Hvis forskelle med andre ord begynder at dukke op, så starter vi søgningen igen enten ved at ændre den oprindelige eller forsøge at finde en anden forskel. Det er muligt at lagre forskellen i kun ét ord, fordi krypteringsfunktionen ikke er bijektiv for hver nabo. Elias Jaarrkov udførte en række eksperimenter og fandt ud af, at sandsynligheden for at gennemgå forskellen på 5 hele cyklusser gav sandsynligheden mellem og for de fleste nøgler, det vil sige, at hvis et tekstpar gennemgik 5 ud af 6 hele cyklusser, så kan det betragtes som korrekt, da hvis du sætter forskellen i slutningen af ​​blokken, vil der være forskel på de fleste ord. Dette angreb blev udført, og nøglen til algoritmen blev gendannet med antallet af cyklusser reduceret til tre.

Anden tilgang

Den anden tilgang adskiller sig fra den første ved, at efter den første runde af kryptering af ordet, skal forskellen gå ind i det fra selve ordet, mens forskellen kan ændre sig, og efter den næste runde af kryptering vil forskellen vende tilbage til ord og blive lig med den oprindelige, men skift fortegn. Efter at have evalueret denne metode fandt Elias Jaarkov ud af, at 2 59 tekster er nok til at finde det rigtige par, og forskellen skulle ligge i intervallet , hvor , og stigende d ikke forbedrede resultaterne. Et vellykket angreb blev derefter lavet på XXTEA med antallet af cyklusser reduceret til 4, og det korrekte par blev opnået med 235 par tekster, mens det tidligere estimat giver behovet for 234,7 par tekster.

Nøglegendannelse

At kende det korrekte tekstpar er det nok at køre algoritmen i omvendt rækkefølge, da vi nu ved alt undtagen nøglen. [2] [12]

Noter

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. Rettelse til  XTEA . - 1998. - Oktober.
• E. Yarrkov. Kryptoanalyse af XXTEA  (engelsk) . - 2010. - 4. maj.
• Saarinen M.-J. Krypteringsanalyse af Block  Tea . - 1998. - 20. oktober.
• David J. Wheeler, Roger M. Needham. TEA, en lille krypteringsalgoritme  . - 1994. - December.
• David J. Wheeler, Roger M. Needham. TEA  udvidelser . - 1996. - Oktober.
• J. Kelsey, B. Schneier og D. Wagner. Relateret nøglekrypteringsanalyse af 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2 og  TEA . - 1997. - November.
• Mao Cenwei. Sammenligning af nogle få små chiffer, der kan anvendes til RFID  . - 2008. - Juni.
• I. Sima, D. Tarmurean og V. Greu. XXTEA, en alternativ erstatning af KASUMI-krypteringsalgoritme i A5/3 GSM og f8 , f9 UMTS datasikkerhedsfunktioner  . - 2012. - Juni.
• Første internationale konference, ICIS'97, Beijing, 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 .