Drake (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 1 januari 2020; kontroller kräver 2 redigeringar .

Dragon  är ett strömchiffer , som först presenterades [1] vid den årliga internationella konferensen ICISC 2003. I april 2005 skickades den till eSTREAM- tävlingen , som syftade till att identifiera strömchiffer som är lämpliga för allmän användning i applikationer med höga prestandakrav.

Dragon utvecklades av Ed Dawson, Kevin Chen, Matt Henricksen, William Millan, Leonie Simpson, HoonJae Lee och SangJae Moon.

Introduktion

Utformningen av strömchiffer har traditionellt baserats på driften av linjära återkopplingsskiftregister , eftersom de senare är väl förstådda och uppfyller allmänt accepterade statistiska kriterier. Icke-linjäriteten i chiffer gamma kan representeras antingen av verkan av ett icke-linjärt filter, eller av en oregelbunden kretsklocka, eller båda. När de implementeras i hårdvara uppvisar bitströmschiffer hög prestanda, men är ganska långsamma när de implementeras i programvara . Chiffer baserade på linjära återkopplingsskiftregister och som använder ett litet antal återkopplingar kan vara sårbara för attacker, men en ökning av antalet av de senare kan påverka chiffertets effektivitet negativt. Dessutom ifrågasätts tillförlitligheten hos chiffer med en linjär tillståndsändringsfunktion vid användning av algebraiska attacker. [2]

Ordbaserade chiffer kan överträffa bitbaserade chiffer i både hårdvaru- och mjukvaruimplementationer. De krypterar flera gånger mer data per iteration än chiffer med enbitars linjära återkopplingsskiftregister. När de implementeras i mjukvara kan de överträffa även snabba blockchiffer som AES med nästan en storleksordning [3] . Även om det är lätt att mäta prestanda för ordbaserade chiffer, är det svårt att exakt bedöma deras styrka.

Dragon designades med både prestanda och säkerhet i åtanke. Den använder ett icke-linjärt återkopplingsskiftregister tillsammans med ett icke-linjärt filter för att generera ett chiffergamma i form av 64-bitars ord. Dragon har prestanda i storleksordningen flera gigabit per sekund och kräver cirka 4 kilobyte minne.

Specifikation

Dragon kan användas med en 128-bitars nyckel och initialiseringsvektor, eller med en 256-bitars nyckel och initialiseringsvektor. Dessa versioner kallas Dragon-128 respektive Dragon-256. De fungerar nästan identiskt, med undantag för nyckelinitieringsprocessen.

Båda versionerna av Dragon-chifferet är byggda med ett enda 1024-bitars icke-linjärt återkopplingsskiftregister och 64-bitars minne M. Det initiala tillståndet skapas med hjälp av en nyckel och en initialiseringsvektor, som stöds av en tillståndsändringsfunktion F. Ändringen funktionen används också i nyckelströmsgenerering.

F-funktion

Dragon-128 och Dragon-256 använder samma F-funktion. F är en reversibel mappning från 192 bitar till 192 bitar: den tar 6 x 32 bitar som indata (betecknade a, b, c, d, e, f) och utdata 6 x 32 bitar (betecknade a', b', c', d', e', f'). Nätverket består av tre skikt: ett initialt blandningsskikt, ett S-boxskikt och ett slutligt blandningsskikt. Blandningsskikt använder modulo 2 addition 32 och modulo 2 addition (⊕). S-boxlagret består av G- och H-funktioner som i sin tur innehåller 8 × 32 S-boxar.

G- och H-funktioner

G- och H-funktionerna är icke-linjära virtuella 32 x 32 S-boxar byggda av två 8 x 32-bitars S-boxar. De 32 inmatade bitarna är uppdelade i fyra byte, x = x 0 ‖ x 1 ‖ x 2 ‖ x 3 , där a ‖ b anger sammankopplingen av a och b.

Initiering

För att initiera nyckeln delas det icke-linjära återkopplingsskiftregistret i åtta 128-bitars ord, betecknade Wo ... W7 . Initialisering sker i två faser.

Fas 1: "propagera" chiffertillståndet : Under den första fasen "propageras" det initiala tillståndet för det 1024-bitars icke-linjära återkopplingsskiftregistret och 64-bitars minnet M med hjälp av nyckeln (K) och initialiseringsvektorn ( IV).

Dragon-128 tar en 128-bitars nyckel och en 128-bitars IV och "multiplicerar" tillståndet för det icke-linjära återkopplingsskiftregistret så att (W 0 ‖ … ‖ W 7 ) = (K ‖ K ' ⊕ IV ' ‖ IV ‖ K ⊕ IV ' ‖ K ' ‖ K ⊕ IV ‖ IV ' ‖ K ' ⊕ IV), där primtal indikerar att de höga och låga 64-bitarshalvorna har bytts.

Dragon-256 tar en 256-bitars nyckel och en 128-bitars IV och "multiplicerar" tillståndet för det icke-linjära återkopplingsskiftregistret så att (W 0 ‖ … ‖ W 7 ) = (K ‖ K ⊕ IV ‖ ~( K ⊕ IV) ‖IV).

I båda fallen är 64-bitarsminnet M förfyllt med det konstanta värdet 0x0000447261676F6E, vilket är ASCII-representationen av ordet "Dragon".

Fas 2: Blanda tillståndet för chiffer : Under den andra fasen tillämpas tillståndsändringsfunktionen 16 gånger för att blanda innehållet i det icke-linjära återkopplingsskiftregistret och 64-bitars minnet M. 128-bitars funktionsargumentet F är bildad som en linjär kombination av tre skiftregisterord med olinjär återkoppling, exakt a ‖ b ‖ c ‖ d = (W 0 ⊕ W 6 ⊕ W 7 ). Dessutom är e ‖ f = M.

Kretsen är klockad så att W 7 hoppas över vid tidpunkten t, och så Wi t+1 = W t i -1 , 0 ≤ i ≤ 7. Det 128-bitars återkopplingsord som bildar innehållet i W t +1 är erhålls genom att lägga till modulo 2 W 0 t 0 c (a ' ‖ b ' ‖ c ' ‖ d ' ). De återstående två 32-bitarsorden sammanfogas och används för att uppdatera minnet: e ' ‖ f ' = M.

För att skydda mot attacker som kräver kunskap om ett stort antal nyckelströmselement och mot okända framtida attacker, kan inte mer än 2 64 bitar av nyckelström skapas för varje par av K och IV.

Generering av nyckelström

Under generering av nyckelström delas ett 1024-bitars icke-linjärt återkopplingsskiftregister i 32 32-bitars ord Bi , 0 ≤ i ≤ 31. F-funktionen används också i processen.

I varje iteration väljs fyra 32-bitars inmatningsargument F från det icke-linjära återkopplingsskiftregistret för orden Bo , B9 , B16 och B19 . De återstående två argumenten är resultatet av modulo 2-addition av orden B30 och B31 med ML respektive MR , där ML och MR är de låga respektive höga orden i minnet M.

Det icke-linjära återkopplingsskiftregistret skiftas två bitar, och Bo och Bi fylls med återkopplingsverkan från F-funktionsutgångarna b ' respektive c ' . 64-bitars nyckelströmsordet z bildas av sammanlänkningen av a ' och e ' . 64-bitarsminnet M fungerar som en räknare under nyckelströmsgenerering och inkrementeras varje cykel.

Implementering och prestanda

Dragon-chifferet designades med både hårdvara och mjukvara i åtanke.

Programvaruimplementering

Prestandautvärderingar har gjorts [4] , som visar att Dragon är ganska effektiv både vad gäller prestanda och minneskostnader.

Hårdvaruimplementering

Implementeringen av Dragon på hårdvarunivå gör att en hög grad av parallellitet kan uppnås. Operationer på F-funktionens sex inmatningsargument kan delas in i tre grupper som var och en använder två argument. Pre-mix och post-mix implementeras med 32-bitars modulo adderare. G- och H-funktioner implementerades med hjälp av LUT-tabeller och XOR-operatorer. När den tillverkas med Samsung 0.13um ASIC -teknik , vid en klockfrekvens på 2,6 GHz, är den minsta latensen 2,774 ns vid en prestanda på 23 Gbps.

För att förbättra hastigheten på hårdvaruimplementeringen föreslogs en speciell datorstruktur [5] . På en Altera FPGA-enhet uppnår en effektiv implementering av Dragon en genomströmning på 1,06 Gbps.

Kryptanalys

År 2005 genomförde Håkan Englund och Alexander Maximov tillförlitlighetsstudier på Dragon [6] och avslöjade en sårbarhet i den. Samma år publicerade chifferförfattarna en artikel [7] som förnekade möjligheten till effektivt utnyttjande av denna sårbarhet. Men 2007 förbättrade Joo Yeon Cho och Josef Pieprzyk den tidigare föreslagna attacktekniken [8] . Och även om en sådan attack praktiskt taget inte är genomförbar i praktiken, ökade detta inte chiffrets rykte.

Slutsats

Efter att ha gått igenom två faser av eSTREAM- tävlingen kom Dragon-chifferet inte till finalen och förlorade mot starkare konkurrenter.

Se även

Anteckningar

  1. ↑ Chen, K., Millan, W., Fuller, J., Simpson, L., Dawson, E., Lee, H., Moon, S.:Dragon: A Fast Word Based Stream Cipher. I: Park, C.-s., Chee, S. (red.) ICISC 2004. LNCS, vol. 3506, sid. 33-50. Springer, Heidelberg (2005) ( [1] Arkiverad 1 juli 2012 på Wayback Machine )
  2. ↑ Courtois, N.: Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt. I: Lee, P., Lim, C. (red.) ICISC 2002. LNCS, vol. 2587, sid. 182-199. Springer, Heidelberg (2003)
  3. ↑ Nationellt institut för standarder och teknologi. Federal Information Processing Standards Publication 197 (2001)
  4. ↑ eSTREAM-projektet - eSTREAM-fas 3 . Hämtad 28 oktober 2011. Arkiverad från originalet 31 oktober 2011.
  5. ↑ Lee, H., Moon, S.: Parallell Stream Cipher för säker höghastighetskommunikation. Signal Processing 82(2), 137-143 (2002)
  6. ↑ Håkan Englund och Alexander "Attacka draken" . Datum för åtkomst: 28 oktober 2011. Arkiverad från originalet den 27 maj 2011.
  7. ↑ Ed Dawson, Matt Henricksen, Willam Millan och Leonie Simpson, "The Dragon Is Alive and Well" [2] Arkiverad 27 maj 2011 på Wayback Machine
  8. ↑ Joo Yeon Cho och Josef Pieprzyk, "An Improved Distinguisher for Dragon" [3] Arkiverad 27 september 2011 på Wayback Machine

Litteratur

Länkar