Trivium (chiffer)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 31 december 2018; kontroller kräver 4 redigeringar .

Trivium  är en symmetrisk synkron streaming-krypteringsalgoritm primärt inriktad på hårdvaruimplementering med en flexibel balans mellan hastighet och antal element, som även har möjlighet till en ganska effektiv mjukvaruimplementering.

Chifferet introducerades i december 2008 som en del av portföljen för det europeiska eSTREAM- projektet , profil 2 (hårdvaruorienterade chiffer). Författarna till chiffret är Christophe De Kannier och Bart Prenel.

Detta strömchiffer genererar upp till bitar av utströmmen från 80 bitar av nyckeln och 80 bitar av IV (initieringsvektor). Detta är den enklaste chifferen i eSTREAM-projektet, som visar utmärkta resultat när det gäller kryptografisk stabilitet.

Trivium ingår i ISO/IEC 29192-3-standarden som ett lättviktsströmchiffer.

Beskrivning

Det initiala tillståndet för Trivium är 3 skiftregister med en total längd på 288 bitar. Varje klockcykel ändrar bitarna i skiftregistren med hjälp av en icke-linjär kombination av frammatning och återkoppling. För att initiera chifferet skrivs nyckeln K och initialiseringsvektorn IV i 2 av 3 register och algoritmen exekveras 4x288 = 1152 gånger, vilket garanterar att varje bit i initialtillståndet beror på varje bit av nyckeln och varje bit. av initialiseringsvektorn.

Efter att ha passerat initieringssteget genereras varje cykel en ny medlem av nyckelströmmen Z , som passerar XOR- proceduren med nästa medlem i texten. Dekrypteringsproceduren sker i omvänd ordning - varje medlem av chiffertexten XORed med varje medlem av nyckelströmmen Z. [ett]

Algoritm

Stream chiffer

Trivium genererar en Z -sekvens , den så kallade nyckelströmmen, upp till bitar lång. För att kryptera ett meddelande är det nödvändigt att XOR meddelandet och nyckelströmmen. Dekryptering utförs på liknande sätt, XOR-operationen utförs från chiffertexten och nyckelströmmen.

Initiering

Algoritmen initieras genom att ladda en 80-bitars nyckel och en 80-bitars initialiseringsvektor till ett 288-bitars initialtillstånd. Initialisering kan beskrivas med följande pseudokod .

Initieringsproceduren säkerställer att varje bit av initialtillståndet beror på varje bit av nyckeln och varje bit av initialiseringsvektorn. Denna effekt uppnås redan efter 2 hela pass (2*288 cykelutföranden). Ytterligare två pass är utformade för att komplicera bitförhållandena. Till exempel har de första 128 byten av nyckelströmmen Z , erhållna från nollnyckeln och initialiseringsvektorn, ungefär samma antal 1:or och 0:or jämnt fördelade. Även med de enklaste och identiska nycklarna producerar Trivium-algoritmen en sekvens av tal som är nära slumpmässiga.

De första 128 byten av nyckelströmmen, genererade från nollorna K och IV i hexadecimal form 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 initialiseringscykler, har enheterna skrivna i cellerna och påverkat alla andra bitar i det initiala tillståndet, och därmed, även med de enklaste och identiska nycklarna, kommer varje byte i meddelandet att ändras som ett resultat av krypteringen algoritm.

Algoritmoperation

Strömgeneratorn använder 15 bitar från ett 288-bitars initialtillstånd för att ändra 3 bitar av tillståndet och beräkna 1 bit av nyckelströmmen . Som ett resultat av algoritmen kan upp till bitar av nyckelströmmen erhållas . Algoritmen kan beskrivas med följande pseudokod.

I denna pseudokod utförs alla beräkningar modulo 2. Det vill säga att additions- och multiplikationsoperationer är XOR- och AND- operationer .

Period

Nyckelflödesperioden är svår att bestämma på grund av den icke-linjära naturen hos initialtillståndsändringar. Även om alla triggers är OCH-behandlade, vilket resulterar i en helt linjär krets, kan det visas att vilket par av nyckel och initialiseringsvektor som helst kommer att resultera i genereringen av en nyckelström med en period av ordningen (som redan överskrider den nödvändiga nyckelströmlängden ).

Om vi ​​antar att Trivium börjar generera en slumpmässig nyckelström efter ett litet antal iterationer, kommer alla genererade sekvenser upp till längd att vara lika sannolika. Samt sannolikheten att nyckel/initieringsvektorparet kommer att generera en nyckelström med en period som är mindre än ungefär [2] .

Trivium familj chiffer

Modifieringar av detta chiffer skiljer sig åt i antalet skiftregister och deras längder.

Univium

Univium-strömchifferet består av ett enda skiftregister och endast en nyckel som inte är längre än registrets längd behövs för kodning. [ett]

Bivium

Tillsammans med Trivium föreslog dess författare Bivium-chifferet, som implementerar endast 2 skiftregister med en total längd på 177 bitar. Initieringsprocessen liknar Trivium. Varje cykel ändras 2 statusbitar och en ny bit av nyckelströmmen genereras. Enligt genereringen av nyckelströmmen Z finns det 2 versioner: Bivium-A och Bivium-B (Bivium). I Bivium-A implementeras ett direkt beroende av den nya medlemmen Z på den ändrade tillståndsbiten , från skillnaden från den i Bivium-B (Bivium) . [3]

Trivium-leksak och Bivium-leksak

Leksaksversioner erhölls genom att minska registerlängderna, vilket minskade algoritmens beräkningskomplexitet, samtidigt som alla matematiska egenskaper bibehölls. Längden på varje register minskades med 3 gånger, och Bivium-leksaken bestod också av endast två register.

Varje modifiering av Trivium-chifferet skapades för att förenkla dess matematiska beskrivning, som har mer ett pedagogiskt syfte än syftet att använda dem i informationssäkerhetsverktyg. [fyra]

Prestanda

Standardhårdvaruimplementeringen av algoritmen kräver 3488 grindar och producerar 1 bit av nyckelströmmen per klockcykel. Men eftersom varje nytt tillstånd av en bit inte ändras under minst 64 omgångar, kan ytterligare 64 tillstånd genereras parallellt när antalet logiska element ökar till 5504. Dessutom är olika prestandavariationer möjliga beroende på antalet element Begagnade.

Programvarutolkningen av denna algoritm är också ganska effektiv. Triviums C -implementering på AthlonXP 1600+ ger över 2,4 Mbps kryptering

Säkerhet

Till skillnad från tidiga strömchiffer som RC4 har Trivium-algoritmen, förutom den privata nyckeln ( K ), även en initialiseringsvektor ( IV ), som är den publika nyckeln. Att använda IV tillåter flera oberoende krypterings-/dekrypteringssessioner med bara en nyckel och flera initialiseringsvektorer (en för varje session). Det är också möjligt att använda flera initieringsvektorer för samma session, med en ny IV för varje nytt meddelande.

För närvarande är inga metoder för attack mot denna algoritm kända som skulle vara effektivare än sekventiell uppräkning . Komplexiteten av denna attack beror på längden på meddelandet och är i storleksordningen .

Det finns studier av attackmetoder (till exempel kubisk attack [5] ), som i effektivitet ligger nära uppräkning. Dessutom finns det en attackmetod som låter dig återställa K från IV och keystream. Komplexiteten i denna attack är lika stor och minskar något med en ökning av antalet initialiseringsvektorer som används med en nyckel. Attacker är också möjliga genom att studera den pseudo-slumpmässiga sekvensen av nyckelströmmen för att hitta mönster och förutsäga efterföljande bitar av strömmen, men dessa attacker kräver lösningen av komplexa olinjära ekvationer. Den minsta resulterande komplexiteten av en sådan attack är [6] [7]

Forskningsmetoder

Nästan alla Triviums hackningsprestationer är försök att använda attacker som framgångsrikt utförts på trunkerade versioner av algoritmen [1] . Ofta används en version av Bivium-algoritmen som den som studeras, som endast använder 2 skiftregister med en total längd på 192 bitar [1] .

Anteckningar

  1. ↑ 1 2 3 4 Arkiverad kopia . Hämtad 23 december 2009. Arkiverad från originalet 25 september 2018.
  2. ↑ Arkiverad kopia . Hämtad 23 december 2009. Arkiverad från originalet 20 oktober 2016.
  3. ↑ Två triviala attacker mot trivium | SpringerLink . Hämtad 27 juli 2018. Arkiverad från originalet 27 juli 2018.
  4. ↑ Arkiverad kopia . Hämtad 10 mars 2017. Arkiverad från originalet 12 mars 2017.
  5. ↑ Arkiverad kopia . Hämtad 23 december 2009. Arkiverad från originalet 17 maj 2017.
  6. ↑ Arkiverad kopia . Hämtad 23 december 2009. Arkiverad från originalet 26 augusti 2016.
  7. ↑ Arkiverad kopia . Hämtad 23 december 2009. Arkiverad från originalet 30 juli 2016.

Länkar

 Symmetriska kryptosystem
Streama chiffer
Feistel nätverk
SP nätverk
Övrig