Kanin

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 12. november 2018; checks kræver 6 redigeringer .

Kanin er en high-speed stream cipher første gang præsenteret [1] i februar 2003 på det 10. FSE Symposium. I maj 2005 blev han indsendt til eStream- konkurrencen , som havde til formål at skabe europæiske standarder for strømkrypteringssystemer.

Rabbit er udviklet af Martin Boesgaard , Mette Vesterager , Thomas Pedersen , Jesper Christiansen og Ove Scavenius .

Rabbit bruger en 128-bit nøgle og en 64-bit initialiseringsvektor. Chifferen er designet til at blive brugt i software som en høj krypteringshastighed. Samtidig kunne krypteringshastigheden nå 3,7 cyklusser pr. byte ( CPB ) for Pentium 3-processoren og 10,5 cyklusser pr. byte for ARM7. Chifferen viste sig dog også at være hurtig og kompakt, når den blev implementeret i hardware.

Hovedkomponenten i chifferen er en bitstrømsgenerator , som krypterer 128 bits af en besked pr. iteration. Fordelen ved en chiffer er den grundige blanding af dens interne tilstande mellem to på hinanden følgende iterationer. Blandingsfunktionen er udelukkende baseret på de aritmetiske operationer, der er tilgængelige på moderne processorer, dvs. substitutions-S-bokse og opslagstabeller er ikke nødvendige for at implementere chifferen.

Forfatterne af chifferen har leveret et komplet sæt datablade på Crypticos hjemmeside [2] . Chifferen er også beskrevet i RFC 4503 . Cryptico havde patentet på chifferen, og i mange år krævede kommerciel brug af chifferen en licens. Den 6. oktober 2008 fik chifferen dog lov til at blive brugt til ethvert formål gratis [3] .

Kanin og eStream [4]

eStream- konkurrence

Strømchifferne for eSTREAM-projektet omfatter to profiler. Profil 1 inkluderer software-orienterede cifre, og Profil 2 inkluderer hardware-orienterede ciphers.

Projektets bedste cifre:

Profil 1	Profil 2
HC-128	F-FCSR-H v2
Kanin	Korn v1
Salsa20/12	MICKEY v2
Sosemanuk	Trivium

Profil 1 inkluderer symmetriske stream-cifre med god softwareimplementering. Så gode, at de burde have overgået den AES-bloksymmetriske krypteringsalgoritme i gammagenereringstilstande. Hovedkravet til denne profil var at give et sikkerhedsniveau på 128 bit.

Fordele og ulemper ved kaninchifferet

Rabbit er et af de ældste designs af eSTREAM-projektet. Denne stream-chiffer har ikke været genstand for nogen ændringer eller tilføjelser. Dens specifikation er forblevet uændret fra 2003 til i dag. Chifferen overlevede alle tre faser af projektet og var ikke udsat for kryptoanalytiske angreb på nogen af dem. Blandt andet er denne algoritme rigtig godt implementeret på de nye processorer i Intel-familien. Som en ulempe kan du se det faktum, at Rabbit-chifferet giver et sikkerhedsniveau på kun 128 bit.

Resultater af den endelige afstemning af eSTREAM-projektet for Profil 1.

Profil 1	briller
Kanin	2,80
Salsa 20	2,80
Sosemanuk	1,20
HC-128	0,60
NLS v2	-0,60
LEXv2	−1.20
CryptoMT v3	−1.40
Trække på	−1,60

Algoritme

Strømchifferets interne tilstand indeholder 513 bit. 512 af dem er opdelt i otte 32-bit tilstandsvariable og otte 32-bit tællere , hvor er tilstandsvariablen for delsystemet under iteration , og er den tilsvarende variable tæller. Den 513. bit er bærebitten , som skal gemmes mellem iterationerne. Denne bit initialiseres til nul. 8 tilstandsvariable og 8 tællere afhænger af nøglen under initialisering. $x_{{j,i}}$ $c_{{j,i}}$ $x_{{j,i}}$ $j$ $jeg$ $c_{{j,i}}$ ${\displaystyle \phi _{7,i))$

Statusindstillingsdiagram

Algoritmen initialiseres ved at udvide 128-bit nøglen til 8 tilstandsvariable og 8 tællere, således at der er en en-til-en overensstemmelse mellem nøglen, initialtilstandsvariablerne , og de initiale tællere, . Nøglen er opdelt i 8 undernøgler: , , … , , tilstandsvariable og tællere initialiseres ved hjælp af undernøgler $x_{{j,0}}$ $c_{{j,0}}$ $K^{[127..0]}$ $k_{0}^{[15..0]}$ $k_{1}^{[31..16]}$ $k_{7}^{[127..112]}$

x_{j,0}={\begin{cases}k_{(j+1\mod 8)}\diamond k_{j},&{\text{for lige))\ j,\\k_{ (j+5\mod 8)}\diamond k_{(j+4\mod 8)},&{\text{for ulige}}\ j,\\\end{tilfælde}}

c_{j,0}={\begin{cases}k_{(j+4\mod 8)}\diamond k_{(j+5\mod 8)},&{\text{for lige)) \ j,\\k_{j}\diamond k_{(j+1\mod 8)},&{\text{for ulige}}\ j,\\\end{cases}}

hvor er sammenkædningsoperationen. $\diamant$

Systemet køres 4 gange i henhold til den næste tilstandsfunktion defineret nedenfor for at reducere korrelationen mellem nøglebit og interne tilstandsvariable bit. Til sidst geninitialiseres tællerne som følger:

{\displaystyle c_{j,4}=c_{j,4}\oplus x_{(j+4mod8),4))

for at forhindre nøglegendannelse ved at invertere tællersystemet.

Næste tilstandsfunktion

x_{{0,i+1}}=g_{{0,i}}+(g_{{7,i}}\lll 16)+(g_{{6,i}}\lll 16)

x_{{1,i+1}}=g_{{1,i}}+(g_{{0,i}}\lll 8)+g_{{7,i}}

x_{{2,i+1}}=g_{{2,i}}+(g_{{1,i}}\lll 16)+(g_{{0,i}}\lll 16)

x_{{3,i+1}}=g_{{3,i}}+(g_{{2,i}}\lll 8)+g_{{1,i}}

x_{{4,i+1}}=g_{{4,i}}+(g_{{3,i}}\lll 16)+(g_{{2,i}}\lll 16)

x_{{5,i+1}}=g_{{5,i}}+(g_{{4,i}}\lll 8)+g_{{3,i}}

x_{{6,i+1}}=g_{{6,i}}+(g_{{5,i}}\lll 16)+(g_{{4,i}}\lll 16)

x_{{7,i+1}}=g_{{7,i}}+(g_{{6,i}}\lll 8)+g_{{5,i}}

g_{j,i}=\operatørnavn {LSW} ((x_{j,i}+c_{j,i})^{2})\oplus \operatørnavn {MSW} ((x_{j,i }+c_{j,i})^{2})

Her er alle tilføjelser modulo 2 32 . Funktionerne og returnerer henholdsvis de nederste og øverste fire bytes af et 64-bit tal , - cyklisk skift til venstre. $\operatørnavn {LSW} (x)$ $\operatørnavn {MSW} (x)$ $x$ $\lll$

Tællersystem

Ligninger, der specificerer ændringen i tællersystemet:

c_{{0,i+1}}=c_{{0,i}}+a_{0}+\phi _{{7,i}}\mod 2^{{32}}

c_{{1,i+1}}=c_{{1,i}}+a_{1}+\phi _{{0,i+1}}\mod 2^{{32}}

c_{{2,i+1}}=c_{{2,i}}+a_{2}+\phi _{{1,i+1}}\mod 2^{{32}}

c_{{3,i+1}}=c_{{3,i}}+a_{3}+\phi _{{2,i+1}}\mod 2^{{32}}

{\displaystyle c_{4,i+1}=c_{4,i}+a_{4}+\phi _{3,i+1}\mod 2^{32))

c_{{5,i+1}}=c_{{5,i}}+a_{5}+\phi _{{4,i+1}}\mod 2^{{32}}

c_{{6,i+1}}=c_{{6,i}}+a_{6}+\phi _{{5,i+1}}\mod 2^{{32}}

c_{{7,i+1}}=c_{{7,i}}+a_{7}+\phi _{{6,i+1}}\mod 2^{{32}}

hvor bærebitantallet er givet af $\phi _{j,i+1}$

\phi _{j,i+1}={\begin{cases}1,&{\text{if))\ c_{0,i}+a_{0}+\phi _{7,i }\geqslant 2^{32}\wedge j=0,\\1,&{\text{if))\ c_{j,i}+a_{j}+\phi _{j-1,i+1 }\geqslant 2^{32}\wedge j>0,\\0,&{\text{ellers}}.\end{cases}}

Konstanterne er også defineret som $a_{j}$

a_{0}={\mathtt {0x4D34D34D)),\quad a_{1}={\mathtt {0xD34D34D3)),

a_{2}={\mathtt {0x34D34D34)),\quad a_{3}={\mathtt {0x4D34D34D)),

a_{4}={\mathtt {0xD34D34D3)),\quad a_{5}={\mathtt {0x34D34D34)),

a_{6}={\mathtt {0x4D34D34D)),\quad a_{7}={\mathtt {0xD34D34D3)).

Ekstraktionsskema

Efter hver iteration genereres 128 outputbits ved hjælp af følgende formler:

s_{i}^{{[15..0]}}=x_{{0,i}}^{{[15..0]}}\oplus x_{{5,i}}^{{[31 ..16]}}

s_{i}^{{[31..16]}}=x_{{0,i}}^{{[31..16]}}\oplus x_{{3,i}}^{{[15 ..0]}}

s_{i}^{{[47..32]}}=x_{{2,i}}^{{[15..0]}}\oplus x_{{7,i}}^{{[31 ..16]}}

s_{i}^{{[63..48]}}=x_{{2,i}}^{{[31..16]}}\oplus x_{{5,i}}^{{[15 ..0]}}

s_{i}^{{[79..64]}}=x_{{4,i}}^{{[15..0]}}\oplus x_{{1,i}}^{{[31 ..16]}}

s_{i}^{{[95..80]}}=x_{{4,i}}^{{[31..16]}}\oplus x_{{7,i}}^{{[15 ..0]}}

s_{i}^{{[111..96]}}=x_{{6,i}}^{{[15..0]}}\oplus x_{{3,i}}^{{[31 ..16]}}

s_{i}^{{[127..112]}}=x_{{6,i}}^{{[31..16]}}\oplus x_{{1,i}}^{{[15 ..0]}}

hvor er 128-bit blok af krypteringsstrømmen ved den iteration. $s_{i}$ $jeg$

Krypterings- og dekrypteringsskema

En XOR-operation udføres mellem de udtrukne bits og teksten/chifferteksten til kryptering/dekryptering.

c_{i}=p_{i}\oplus s_{i},

p_{i}=c_{i}\oplus s_{i},

hvor og angiver den th blok af henholdsvis chiffertekst og tekst. $c_{i}$ $p_{i}$ $jeg$

Key Setup Scheme Egenskaber

Nøgleinstallation kan opdeles i tre faser: nøgleudvidelse, iterationssystem, modifikation.

Nøgleudvidelsesstadiet garanterer en en-til-en-korrespondance mellem tilstandsnøglen og tællernøglen, hvilket forhindrer nøgler i at være overflødige. Den allokerer også nøglebits på en optimal måde til iterationer.
Iterationssystemet sikrer, at efter én iteration af den næste tilstandsfunktion, vil hver bit af nøglen påvirke alle otte tilstandsvariable. Det sikrer også, at efter den anden iteration af den næste tilstandsfunktion, vil alle nøglebits påvirke alle tilstandsbit med en sandsynlighed på 0,5. For at sikre pålideligheden af krypteringen udføres iteration fire gange.
Selvom tællerne er kendt af en angriber, komplicerer ændring af tælleren i høj grad gendannelsen af nøglen ved at invertere systemtælleren, da det vil kræve information om tilstandsvariablerne, og det krænker også en-til-en forholdet mellem nøglen og skranken.

Sikkerhed

Rabbit giver 128-bit beskyttelse mod angribere, hvis mål er en enkelt unik nøgle. Hvis angrebet sker på flere nøgler ad gangen, og det er lige meget, hvilken af dem der er knækket, så reduceres sikkerheden til 96 bit [5] .

Angreb på nøgleetableringsfunktionen

Når først nøglen er indstillet, er tæller- og tilstandsbittene strengt og meget ikke-lineært afhængige af nøglebittene. Dette gør det sværere at knække for part-key gætteangreb, selvom tællerbits var kendt efter tælleren blev ændret. At kende tællerne gør selvfølgelig andre typer hacks lettere.

Kollisionsangreb

Rabbit-chifferet bruger tvetydig kortlægning, forskellige nøgler kan potentielt føre til den samme farveskala. Dette problem koger dybest set ned til spørgsmålet om, hvorvidt forskellige nøgler resulterer i de samme tællerværdier, da forskellige tællerværdier næsten helt sikkert vil resultere i forskellige gammagenerationer. Bemærk, at nøgleudvidelses- og iterationssystemet er designet på en sådan måde, at hver nøgle resulterer i unikke tællerværdier. Ændring af tælleren kan dog resultere i lige store tællerværdier for to forskellige nøgler. Hvis vi antager, at den interne tilstand efter fire indledende iterationer i det væsentlige er tilfældig og ikke korrelerer med tællersystemet, er sandsynligheden for kollisioner givet af "fødselsdagsparadokset", det vil sige, for alle nøgler forventes en kollision i en 256- bittæller $2^{128}$ [ angiv ] . Tællersystemkollisionen bør således ikke give problemer i praksis.

Relateret nøgleangreb

Angrebet er baseret på brugen af symmetriegenskaber i den næste tilstand og nøgleindstillingsfunktioner. Overvej for eksempel to nøgler og relateret til en relation for alle . Dette fører til forholdet og . Overvej nu, hvornår og er den samme nøgle. Hvis betingelsen er opfyldt, vil den næste tilstandsfunktion beholde symmetriegenskaben. Men man kan nemt kontrollere, at konstanterne , er valgt således, at . Den næste tilstandsfunktion er således ikke modtagelig for det tilknyttede nøgleangreb. $K$ ${\tilde K}$ $K^{{[i]}}={\tilde K}^{{[i+2]}}$ $jeg$ $x_{{j,0}}={\tilde x}_{{j+2,0}}$ $c_{{j,0}}={\tilde c}_{{j+2,0}}$ $K$ ${\tilde K}$ $a_{{j,0}}={\tilde a}_{{j+2,0}}$ $a_{j}$ $a_{{j,0}}\neq {\tilde a}_{{j+2,0}}$

Delvist nøglegætangreb

Gæt-og-bekræft angreb

Et sådant angreb ville være muligt, hvis outputbits kunne forudsiges ved hjælp af et lille sæt interne tilstandsbit. Angriberen skal gætte den passende del af tilstandsvariablerne, forudsige outputbittene og sammenligne dem med direkte observerede bits i outputtet for at verificere, at hans gæt er korrekt. En angriber skal gætte mindst 2*12 inputbytes for at forskellige g-funktioner kan teste mod én byte. Dette svarer til at gætte 192 bit, hvilket er sværere end at prøve alle tasterne.

Gæt-og-bestem angreb

Essensen af denne metode er, at du skal gætte flere ukendte chiffervariabler og ved hjælp af dem udlede de resterende ukendte. Derefter køres systemet flere gange, og outputtet sammenlignes med chifferens reelle output for at kontrollere antagelsen. Angriberen forsøger at genskabe 512 bits intern tilstand, dvs. han observerer 4 på hinanden følgende 128-bit data ved udgangen af chifferen og gør følgende:

Opdeler en 32-bit tæller og en 32-bit statusvariabel i 8-bit variable.
Skriver et system af ligninger, der modellerer ændringen i tællere og tilstandsvariabler og outputdata. Resultatet er 160 ligninger og 160 ubekendte.
Løser dette system ved at gætte så mange ubekendte som muligt.

Effektiviteten af denne tilgang afhænger af antallet af gættede variabler. Dette tal er afgrænset nedefra af 8-bit undersystemet med det mindste antal inputvariabler. Hvis vi ignorerer tællerne, afhænger hver byte af den næste tilstandsfunktion af 12 inputbytes. Hvis du tager tællerne i betragtning, afhænger hver byte ved udgangen af undersystemet allerede af 24 inputbytes. Derfor skal angriberen gætte mere end 128 bit, hvilket gør angrebet umuligt.

Algebraiske angreb

Algebraisk normal form (ANF) af g-funktionen

Givet en boolsk funktion er ANF en repræsentation som et multivariat polynomium (det vil sige summen af monomer fra inputvariablerne). Et stort antal monomialer og deres gode effektfordeling er vigtige egenskaber ved ikke-lineære blokke i en chiffer. $f:(0,1)^{n}\højrepil (0,1)$ $f$

For en tilfældig boolsk funktion i 32 variabler er det gennemsnitlige antal monomialer , og det gennemsnitlige antal monomialer, der inkluderer alle givne variabler, er . Hvis vi betragter 32 sådanne funktioner valgt tilfældigt, så er det gennemsnitlige antal monomer, der ikke er i nogen af de 32 funktioner, 1, og den tilsvarende varians er også 1. $2^{{31}}$ $2^{30}$

For en g-funktion i Rabbit-chifferet har ANF for de 32 boolske underfunktioner mindst en potens på 30. Antallet af monomialer varierer fra til , hvor det for en tilfældig funktion skal være . Fordelingen af monomialer som funktion af graden er vist i figuren. Ideelt set skulle hoveddelen have været mellem de stiplede linjer, der viser afvigelser fra middelværdien for en ideel tilfældig funktion. Nogle boolske funktioner adskiller sig væsentligt fra resultaterne for den tilfældige funktion, men de har alle et stort antal monomialer i høj grad. $2^{{24,5}}$ $2^{{30,9}}$ $2^{{31}}$

Derudover blev et delvist sammenfald af 32 funktioner undersøgt. Det samlede antal monomialer, der forekommer én gang, er , mens antallet af monomialer, der slet ikke forekommer, er . Sammenlignet med en tilfældig funktion er der tale om ret store afvigelser. Disse oplysninger kan være nyttige til at analysere chifferen i fremtiden. $2^{{26.03}}$ $2^{{26.2}}$

Algebraisk normal form (ANF) for den komplette chiffer

Det er praktisk talt umuligt at beregne ANF for alle bits i outputtet for en komplet chiffer. Men at reducere nøglestørrelsen fra 128 bit til 32 bit gør det muligt at lære de 32 booleske outputfunktioner som en funktion af en 32 bit nøgle.

For en strippet version af Rabbit-chifferet blev opsætningsfunktionen undersøgt for et andet antal iterationer. ANF bestemmes efter 0, 1, 2, 3, 4 iterationer og en yderligere iteration i ekstraktionsskemaet. For 0+1 iterationer var antallet af monomialer cirka 2^31, som forventet for den tilfældige funktion. Men efter to iterationer stabiliserede resultatet sig. Det betyder, at der ikke er flere udsving i outputtet. Antallet af manglende polynomier er henholdsvis 0, 1, 2, 3, 1 i iterationer (0+1), ..., (4+1). Det er indlysende, at disse data svarer til resultaterne for tilfældige funktioner.

Korrelationsangreb

Lineær tilnærmelse

Det lineære angreb involverer at finde den bedste lineære tilnærmelse mellem bitsene ved indgangen til den næste tilstandsfunktion og bitsene ved udgangen af ekstraktionskredsløbet. For at gøre dette skal du bruge Walsh-Hadamard Transform , idet det antages, at alle inputdata er lineært uafhængige. Det blev fundet, at den bedste lineære korrelation har en korrelationskoefficient af orden , hvilket indebærer at generere output fra iterationer for at sammenligne med en tilfældig funktion. $2^{{-57.8}}$ $2^{{114}}$

Anden ordens tilnærmelse

Afskæring af ANF for g-funktionen af termer over anden orden forbedrer i høj grad tilnærmelsen under de rigtige forhold.

Betegn ved andenordens tilnærmelse ANF for . Ifølge de eksperimentelle resultater er korrelationskoefficienten mellem og mindre end , og korrelationskoefficienten mellem og er omtrent lig med . Dette betyder, at nogle termer i højere grad afskæres, når modulo 2 tilføjes til to tilstødende bit. Ved at bygge på disse data giver en chiffer med en anden tilnærmelsesorden i bedste fald en korrelationskoefficient . Denne værdi af korrelationskoefficienten er utilstrækkelig til et angreb. Hvis vi også tager højde for tællerne, så er analysen meget mere kompliceret. https://vk.com/tibber $f^{{[j]}}$ $g^{{[j]}}$ $f$ $g$ $2^{{-9,5}}$ $f^{{[j]}}\oplus f^{{[j+1]}}$ $g^{{[j]}}\oplus g^{{[j+1]}}$ $2^{{-2,72}}$ $2^{{-26.4}}$

Noter

↑ M. Boesgaard, M. Vesterager, T. Pedersen, J. Christiansen, O. Scavenius. Rabbit: A High-Performance Stream Cipher. Proc. FSE 2003. Springer LNCS 2887, pp. 307-329 ( PDF )
↑ M. Boesgaard, T. Pedersen, M. Vesterager, E. Zenner. The Rabbit Stream Cipher - Design og sikkerhedsanalyse. Proc. SASC 2004. ( PDF Arkiveret 17. maj 2011 på Wayback Machine )
↑ Phorum :: ECRYPT forum :: Kanin bliver offentligt ejendom . Hentet 18. december 2010. Arkiveret fra originalen 30. juni 2009. (ubestemt)
↑ eSTREAM-porteføljen Steve Babbage, Christophe De Canni`ere, Anne Canteaut, Carlos Cid, Henri Gilbert, Thomas Johansson, Matthew Parker, Bart Preneel, Vincent Rijmen og Matthew Robshaw6 ( PDF Arkiveret 13. august 2012 på Wayback Machine )
↑ Christophe De Cannière, Joseph Lano og Bart Preneel , "Comments on the Rediscovery of Time Memory Data Tradeoffs", 2005. ( PDF Arkiveret 6. juli 2015 på Wayback Machine )

Links

Crypticos hjemmeside Arkiveret 28. januar 2011 på Wayback Machine
Rabbit RFC Arkiveret 24. maj 2011 på Wayback Machine
eSTREAM-side på Rabbit Arkiveret 17. august 2010 på Wayback Machine
Komparativ analyse af eSTREAM-projektchiffer

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher