Trivium (chiffer)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 31. december 2018; checks kræver 4 redigeringer .

Trivium  er en symmetrisk synkron streaming krypteringsalgoritme primært fokuseret på hardwareimplementering med en fleksibel balance mellem hastighed og antal elementer, som også har mulighed for en ret effektiv softwareimplementering.

Chifferen blev introduceret i december 2008 som en del af porteføljen af ​​det europæiske eSTREAM- projekt , profil 2 (hardware-orienterede chiffer). Forfatterne af chifferen er Christophe De Kannier og Bart Prenel.

Denne strømchiffer genererer op til bits af outputstrømmen fra 80 bits af nøglen og 80 bits IV (initialiseringsvektor). Dette er den enkleste chiffer i eSTREAM-projektet, som viser fremragende resultater med hensyn til kryptografisk stabilitet.

Trivium er inkluderet i ISO/IEC 29192-3 standarden som en letvægts stream-chiffer.

Beskrivelse

Triviums starttilstand er 3 skifteregistre med en samlet længde på 288 bit. Hver clock-cyklus ændrer bits i skifteregistrene ved hjælp af en ikke-lineær kombination af feed-forward og feedback. For at initialisere chifferen skrives nøglen K og initialiseringsvektoren IV i 2 af 3 registre, og algoritmen udføres 4x288 = 1152 gange, hvilket garanterer, at hver bit i starttilstanden afhænger af hver bit af nøglen og hver bit. af initialiseringsvektoren.

Efter at have passeret initialiseringsstadiet, genereres hver cyklus et nyt medlem af nøglestrømmen Z , som passerer XOR -proceduren med det næste medlem af teksten. Dekrypteringsproceduren finder sted i omvendt rækkefølge - hvert medlem af chifferteksten XOR - behandles med hvert medlem af nøglestrømmen Z. [en]

Algoritme

Stream ciphers

Trivium genererer en Z -sekvens , den såkaldte keystream, op til bit lang. For at kryptere en meddelelse er det nødvendigt at XOR meddelelsen og nøglestrømmen. Dekryptering udføres på lignende måde, XOR-operationen udføres fra chifferteksten og nøglestrømmen.

Initialisering

Algoritmen initialiseres ved at indlæse en 80-bit nøgle og en 80-bit initialiseringsvektor til en 288-bit initial tilstand. Initialisering kan beskrives med følgende pseudokode .

Initialiseringsproceduren sikrer, at hver bit af den indledende tilstand afhænger af hver bit af nøglen og hver bit af initialiseringsvektoren. Denne effekt opnås allerede efter 2 hele gennemløb (2*288 cyklusudførelser). 2 flere gennemløb er designet til at komplicere bitrelationerne. For eksempel har de første 128 bytes af nøglestrømmen Z , opnået fra nul-nøglen og initialiseringsvektoren, omtrent det samme antal 1'ere og 0'er jævnt fordelt. Selv med de enkleste og identiske nøgler producerer Trivium-algoritmen en sekvens af tal, der er tæt på tilfældige.

De første 128 bytes af nøglestrømmen, genereret fra nuller K og IV i hexadecimal 0000000 e0 fb 26 bf 59 58 1b 05 7a 51 4e 2e 9f 23 7f c9 0000010 32 56 16 03 07 19 2d cf a8 e7 0f 79 b2 a1 cd e9 0000020 52 f7 03 92 68 02 38 b7 4c 2b 75 1a a2 9a 9a 59 0000030 55 28 98 49 74 6e 59 80 80 03 4c 1a a5 b5 f2 d4 0000040 34 69 bb 86 ca 52 15 b3 ae 80 12 69 73 55 9a 31 0000050 b2 6c 0e f5 16 40 20 d6 30 7f 4e 3f 48 16 dc 24 0000060 25 5c ad c4 10 a1 c9 1b bb e8 01 4e dc fc 2e 27 0000070 9e fa ae 02 a2 48 05 b2 2e fb f4 4f 27 76 56 27 0000080 3e 5e b7 06 4e e6 4a 57 7b ad a2 3a 1c 52 ff 48 0000090 f3 92 f8 87 ff 98 aa 87 e6 bf f6 19 38 3c ff 19 00000a0 3f 0a a5 fd 01 ec d0 d8 fa f0 fa 87 09 a1 4e ee 00000b0 63 29 9f 9b 31 ef 95 a5 c7 76 19 8d c7 e0 df 55 00000c0 1b 0f 50 e9 b8 91 85 ea 06 7b d5 2a ad 2b 77 f4 00000d0 ac 84 9b 6d 3f 2e a9 85 99 d7 04 95 02 33 fd f0 00000e0 b7 f8 5b 6e b7 c8 f0 b4 46 aa 20 cd a0 dd dd 4f

Som du kan se, efter 4 initialiseringscyklusser, blev enhederne skrevet i celler og påvirket alle andre bits i den oprindelige tilstand, og selv med de enkleste og identiske nøgler vil hver byte i meddelelsen blive ændret som et resultat af krypteringen algoritme.

Algoritmeoperation

Strømgeneratoren bruger 15 bit fra en 288-bit starttilstand til at ændre 3 bit af tilstanden og beregne 1 bit af nøglestrømmen . Som et resultat af algoritmen kan op til bits af nøglestrømmen opnås . Algoritmen kan beskrives med følgende pseudokode.

I denne pseudokode udføres alle beregninger modulo 2. Det vil sige, at additions- og multiplikationsoperationer er XOR- og AND -operationer .

Periode

Nøgleflowperioden er svær at bestemme på grund af den ikke-lineære natur af initialtilstandsændringer. Selvom alle triggere er AND-behandlet, hvilket resulterer i et fuldstændig lineært kredsløb, kan det vises, at et hvilket som helst par af nøgle og initialiseringsvektor vil resultere i generering af en nøglestrøm med en periode i rækkefølgen (som allerede overstiger den nødvendige nøglestrømlængde ).

Hvis vi antager, at Trivium begynder at generere en tilfældig nøglestrøm efter et lille antal iterationer, så vil alle genererede sekvenser op til længde være lige sandsynlige. Samt sandsynligheden for, at nøgle/initialiseringsvektorparret vil generere en nøglestrøm med en periode mindre end ca. [2] .

Trivium familie ciphers

Ændringer af denne chiffer er forskellige i antallet af skifteregistre og deres længder.

Univium

Univium-strømchifferet består af et enkelt skifteregister, og kun en nøgle, der ikke er længere end registrets længde, er nødvendig til indkodning. [en]

Bivium

Sammen med Trivium foreslog dets forfattere Bivium-chifferet, som kun implementerer 2 skifteregistre med en samlet længde på 177 bit. Initialiseringsprocessen ligner Trivium. Hver cyklus ændres 2 statusbits, og en ny bit af nøglestrømmen genereres. Ifølge generationen af ​​nøglestrømmen Z er der 2 versioner: Bivium-A og Bivium-B (Bivium). I Bivium-A er en direkte afhængighed af det nye medlem Z af den ændrede tilstandsbit implementeret , fra forskellen fra den i Bivium-B (Bivium) . [3]

Trivium-legetøj og Bivium-legetøj

Legetøjsversioner blev opnået ved at reducere registerlængderne, hvilket reducerede algoritmens beregningsmæssige kompleksitet, mens alle matematiske egenskaber bibeholdtes. Længden af ​​hvert register blev reduceret med 3 gange, og Bivium-legetøjet bestod også kun af to registre.

Hver modifikation af Trivium-chifferet blev skabt for at forenkle dens matematiske beskrivelse, som har mere et pædagogisk formål end formålet med at bruge dem i informationssikkerhedsværktøjer. [fire]

Ydeevne

Standard hardwareimplementeringen af ​​algoritmen kræver 3488 porte og producerer 1 bit af nøglestrømmen pr. clock-cyklus. Men da hver ny tilstand af en bit ikke ændres i mindst 64 runder, kan der genereres 64 flere tilstande parallelt, når antallet af logiske elementer stiger til 5504. Desuden er forskellige ydelsesvariationer mulige afhængigt af antallet af elementer Brugt.

Softwarefortolkningen af ​​denne algoritme er også ret effektiv. Triviums C -implementering på AthlonXP 1600+ leverer over 2,4 Mbps kryptering

Sikkerhed

I modsætning til tidlige stream-cifre som RC4 , har Trivium-algoritmen, udover den private nøgle ( K ), også en initialiseringsvektor ( IV ), som er den offentlige nøgle. Brug af IV tillader flere uafhængige krypterings-/dekrypteringssessioner ved brug af kun 1 nøgle og flere initialiseringsvektorer (en for hver session). Det er også muligt at bruge flere initialiseringsvektorer til den samme session ved at bruge en ny IV for hver ny besked.

I øjeblikket kendes ingen metoder til angreb på denne algoritme, der ville være mere effektive end sekventiel optælling . Kompleksiteten af ​​dette angreb afhænger af meddelelsens længde og er i størrelsesordenen .

Der findes undersøgelser af angrebsmetoder (for eksempel det kubiske angreb [5] ), som i effektivitet er tæt på opregning. Derudover er der en angrebsmetode, der giver dig mulighed for at gendanne K fra IV og keystream. Kompleksiteten af ​​dette angreb er ens og falder lidt med en stigning i antallet af initialiseringsvektorer, der bruges med én nøgle. Angreb er også mulige ved at studere den pseudo-tilfældige sekvens af nøglestrømmen for at finde mønstre og forudsige efterfølgende bits af strømmen, men disse angreb kræver løsning af komplekse ikke-lineære ligninger. Den mindste resulterende kompleksitet af et sådant angreb er [6] [7]

Forskningsmetoder

Næsten alle Triviums hacking-præstationer er forsøg på at bruge angreb udført med succes på trunkerede versioner af algoritmen [1] . Ofte bruges en version af Bivium-algoritmen som den undersøgte, som kun bruger 2 skifteregistre med en samlet længde på 192 bit [1] .

Noter

  1. ↑ 1 2 3 4 Arkiveret kopi . Hentet 23. december 2009. Arkiveret fra originalen 25. september 2018.
  2. ↑ Arkiveret kopi . Hentet 23. december 2009. Arkiveret fra originalen 20. oktober 2016.
  3. ↑ To trivielle angreb på trivium | SpringerLink . Hentet 27. juli 2018. Arkiveret fra originalen 27. juli 2018.
  4. ↑ Arkiveret kopi . Hentet 10. marts 2017. Arkiveret fra originalen 12. marts 2017.
  5. ↑ Arkiveret kopi . Hentet 23. december 2009. Arkiveret fra originalen 17. maj 2017.
  6. ↑ Arkiveret kopi . Hentet 23. december 2009. Arkiveret fra originalen 26. august 2016.
  7. ↑ Arkiveret kopi . Hentet 23. december 2009. Arkiveret fra originalen 30. juli 2016.

Links

 Symmetriske kryptosystemer
Stream-cifre
Feistel netværk
SP netværk
Andet