Stream cipher
Inden for kryptografi er en stream cipher en symmetrisk nøglecipher, hvor bits i klartekst kombineres med en pseudo-tilfældig cipherbitstrøm (keystream) ved hjælp af en eksklusiv-eller-operation (xor). I en stream cipher krypteres klartekstcifrene én ad gangen, og transformationen af de på hinanden følgende cifre varierer under krypteringstilstanden. Et alternativt navn er en tilstandschiffer, da krypteringen af hvert enkelt ciffer afhænger af den aktuelle tilstand. I praksis er cifrene typisk enkelte bits eller bytes.
Stream ciphers repræsenterer en anden tilgang til symmetrisk kryptering end blokcifre. Blokchiffrer opererer med store blokke af fast længde. Stream ciphers udføres typisk med en højere hastighed end block ciphers og har lavere krav til hardwaren. Stream ciphers kan imidlertid være udsat for alvorlige sikkerhedsproblemer, hvis de anvendes forkert; f.eks. må den samme starttilstand aldrig anvendes to gange.
En stream cipher anvender en meget mindre og mere praktisk kryptografisk nøgle, f.eks. 128 bit-nøgler. På grundlag af denne nøgle genererer den en pseudorandom nøglestrøm, som kan kombineres med klartekstcifrene på samme måde som en engangskrypteringsalgoritmen. Men fordi nøglestrømmen er pseudorandom og ikke virkelig tilfældig, kan den sikkerhed, der er forbundet med one-time pad'en, ikke anvendes, og det er meget muligt for en stream cipher at være fuldstændig usikker.
Hvordan fungerer nøglestrømsgeneratoren i A5/1, en LFSR-baseret stream cipher, der bruges til at kryptere mobiltelefonsamtaler.
Typer af stream ciphers
En stream cipher genererer på hinanden følgende elementer i nøglestrømmen på grundlag af en intern tilstand. Denne tilstand opdateres på to måder:
- Hvis tilstanden ændres uafhængigt af klartekst- eller ciphertext-meddelelserne, klassificeres cipheret som en synkron stream cipher.
- Hvis tilstanden opdateres på grundlag af tidligere ændringer af ciffertekstcifrene, klassificeres cifferet som en selvsynkroniserende stream ciphers.
Synkrone stream ciphers
I en synkron strømchiffer genereres en strøm af pseudo-tilfældige tal uafhængigt af klartekst- og ciffertekstmeddelelserne og kombineres derefter med klarteksten (for at kryptere) eller med cifferteksten (for at dekryptere). I den mest almindelige form anvendes binære cifre (bits), og nøglestrømmen kombineres med klarteksten ved hjælp af eksklusiv eller-operationen (XOR). Dette kaldes en binær additiv stream cipher.
I en synkron stream cipher skal afsender og modtager være synkrone, for at dekrypteringen kan lykkes. Hvis der tilføjes eller fjernes cifre fra meddelelsen under transmissionen, går synkroniseringen tabt. For at genoprette synkroniseringen kan man systematisk prøve forskellige forskydninger for at opnå den korrekte dekryptering. En anden fremgangsmåde er at markere den krypterede tekst med markører på regelmæssige punkter i output.
Hvis et ciffer imidlertid beskadiges under transmissionen, og ikke tilføjes eller går tabt, er det kun et enkelt ciffer i klarteksten, der påvirkes, og fejlen forplanter sig ikke til andre dele af meddelelsen. Denne egenskab er nyttig, når transmissionsfejlprocenten er høj; den gør det dog mindre sandsynligt, at fejlen vil blive opdaget uden yderligere mekanismer. Desuden er synkrone stream ciphers på grund af denne egenskab meget modtagelige for aktiveangreb - hvis en angriber kan ændre et ciffer i cifferteksten, kan han måske foretage forudsigelige ændringer af den tilsvarende bit i klarteksten; f.eks. kan en ændring af en bit i cifferteksten få den samme bit til at blive vendt (Toggled) i klarteksten.
Selvsynkroniserende stream ciphers
Selvsynkroniserende stream ciphers er en anden teknik, der bruger en del af de foregående N ciffertekstcifre til at beregne nøglestammen. Sådanne ordninger er også kendt som asynkrone stream ciphers eller ciphertext autokey (CTAK). Idéen om selvsynkronisering blev patenteret i 1946 og har den fordel, at modtageren automatisk synkroniserer sig med nøglestrømsgeneratoren efter at have modtaget N ciffertekstcifre, hvilket gør det nemmere at genoprette, hvis cifre falder bort eller tilføjes til meddelelsesstrømmen. Enkeltcifrede fejl har en begrænset effekt, idet de kun påvirker op til N klartekstcifre. Det er noget vanskeligere at udføre aktive angreb på selvsynkroniserende stream ciphers end på synkrone modstykker.
Et eksempel på en selvsynkroniserende stream cipher er en blokcipher i cipher-feedback-tilstand (CFB).
Lineær feedback-skifteregister-baserede stream ciphers
Binære stream ciphers er ofte konstrueret ved hjælp af lineære feedback-skifteregistre (LFSR), fordi de let kan implementeres i hardware og hurtigt kan analyseres matematisk. Det er imidlertid ikke tilstrækkeligt at anvende LFSR'er alene for at opnå god sikkerhed. Der er blevet udviklet forskellige ordninger for at øge sikkerheden ved LFSR'er.
Ikke-lineære kombinationsfunktioner
Da LFSR'er i sagens natur er lineære, er en teknik til at fjerne lineariteten at føre udgangene fra en gruppe af parallelle LFSR'er ind i en ikke-lineær boolsk funktion for at danne en kombinationsgenerator. Forskellige egenskaber ved en sådan kombinationsfunktion er vigtige for at sikre sikkerheden i den resulterende ordning, f.eks. for at undgå korrelationsangreb.
Klokkestyret generatorer
Normalt trinreguleres LFSR'er regelmæssigt. En teknik til at indføre ikke-linearitet er at lade LFSR'en clockes uregelmæssigt, styret af output fra en anden LFSR. Sådanne generatorer omfatter stop-and-go generatoren, vekslende tringeneratoren og krympningsgeneratoren.
Stop-and-go generatoren (Beth og Piper, 1984) består af to LFSR'er. Den ene LFSR clockes, hvis den anden LFSR's output er en "1", ellers gentager den sit tidligere output. Dette output kombineres derefter (i nogle versioner) med output fra en tredje LFSR, der clockes med en regelmæssig hastighed.
Krympningsgeneratoren anvender en anden teknik. Der anvendes to LFSR'er, som begge clockes regelmæssigt på følgende måde:
- Hvis output fra den første LFSR er "1", bliver output fra den anden LFSR output fra generatoren.
- Hvis output fra den første LFSR er "0", kasseres output fra den anden, og generatoren udsender ingen bit.
Denne teknik lider under timingangreb på den anden generator, da udgangens hastighed er variabel på en måde, der afhænger af den anden generators tilstand. Dette kan forbedres ved at buffere output.
Filtergenerator
En anden metode til at forbedre sikkerheden i en LFSR er at overføre hele tilstanden i en enkelt LFSR til en ikke-lineær filtreringsfunktion.
Andre design
I stedet for en lineær drivanordning kan man anvende en ikke-lineær opdateringsfunktion. Klimov og Shamir foreslog f.eks. trekantede funktioner (T-funktioner) med en enkelt cyklus på n bitord.
Sikkerhed
For at være sikker skal perioden for nøglestrømmen (antallet af cifre, der udgives, før strømmen gentager sig selv) være tilstrækkelig stor. Hvis sekvensen gentages, kan de overlappende ciphertexter tilpasses til hinanden "i dybden", og der findes teknikker, som gør det muligt at udtrække klarteksten fra ciphertexter, der er genereret ved hjælp af disse metoder.
Anvendelse
Stream ciphers anvendes ofte i applikationer, hvor klartekst kommer i mængder af ukendt længde, som f.eks. i sikre trådløse forbindelser. Hvis en blokchiffer skulle anvendes i denne type applikationer, ville designeren være nødt til at vælge enten transmissionseffektivitet eller implementeringskompleksitet, da blokchiffrer ikke direkte kan arbejde med blokke, der er kortere end deres blokstørrelse. Hvis en 128-bit blokchiffer f.eks. modtager separate 32-bit blokke af klartekst, skal tre fjerdedele af de overførte data polstres. Block ciphers skal anvendes i ciphertext stealing eller residual block termination mode for at undgå padding, mens stream ciphers eliminerer dette problem ved at operere på den mindste transmitterede enhed (normalt bytes).
En anden fordel ved stream ciphers i militær kryptografi er, at cipher stream kan genereres af en krypteringsenhed, der er underlagt strenge sikkerhedsforanstaltninger, og derefter sendes til andre enheder, f.eks. et radiosæt, som udfører xor-operationen som en del af deres funktion. Den anden enhed kan være designet til brug i mindre sikre miljøer.
RC4 er den mest udbredte stream cipher i software; andre omfatter: Andre er: A5/1, A5/2, Chameleon, FISH, Helix, ISAAC, MUGI, Panama, Phelix, Pike, SEAL, SOBER, SOBER-128 og WAKE.
RC4 er et af de mest udbredte stream cipher-designs.
Sammenligning af Stream Ciphers
| StreamCipher | CreationDate | Hastighed | (bits) | Angreb | |||
| Effektivt | Initialiseringsvektor | InternalState | Bedst kendt | Beregningskompleksitet | |||
| A5/1 | 1989 | Stemme (Wphone) | 54 | 114 | 64 | Aktiv KPA ELLER | ~2 sekunder OR239.91 |
| A5/2 | 1989 | Stemme (Wphone) | 54 | 114 | 64? | Aktiv | 4,6 millisekunder |
| FISH | 1993 | Ret hurtigt (Wsoft) | Kæmpe | Angreb med kendt klartekst | 211 | ||
| Korn | Før 2004 | Hurtig | 80 | 64 | 160 | Nøgleafledning | 243 |
| HC-256 | Før 2004 | 4 (WP4) | 256 | 256 | 65536 | ||
| ISAAC | 1996 | 2.375 (W64-bit) | 8-8288 normalt | N/A | 8288 | (2006) Første runde svag intern statsopdeling | 4.67×101240 (2001) |
| MUGI | 1998-2002 | 128 | 128 | 1216 | N/A (2002) | ~282 | |
| PANAMA | 1998 | 2 | 256 | 128? | 1216? | Hashkollisioner (2001) | 282 |
| Phelix | Før 2004 | op til 8 (Wx86) | 256 + en 128-bit nonce | 128? | Differential (2006) | 237 | |
| Gedde | 1994 | 0,9 x FISH (Wsoft) | Kæmpe | N/A (2004) | N/A (2004) | ||
| Py | Før 2004 | 2.6 | 8-2048? | 64 | 8320 | Kryptoanalytisk teori (2006) | 275 |
| Kanin | 2003-feb | 3,7(WP3)-9,7(WARM7) | 128 | 64 | 512 | N/A (2006) | N/A (2006) |
| 1987 | Imponerende | 8-2048 normalt | 8 | 2064 | Shamir initialbytes-nøgleafledning OR KPA | 213 OR 233 | |
| Salsa20 | Før 2004 | 4.24 (WG4) -11 | 128 + en 64-bit nonce | 512 | 512 + 384 (nøgle+IV+indeks) | Differential (2005) | N/A (2005) |
| Scream | 2002 | 4 - 5 (Wsoft) | 128 + en 128-bit nonce | 32? | 64-bit rundfunktion | ||
| SEAL | 1997 | Meget hurtig (W32-bit) | 32? | ||||
| SNOW | Før 2003 | Meget godt (W32-bit) | 128 ELLER 256 | 32 | |||
| SOBER-128 | 2003 | op til 128 | Smedje af beskeder | 2−6 | |||
| SOSEMANUK | Før 2004 | Meget godt (W32-bit) | 128 | 128 | |||
| Trivium | Før 2004 | 4 (Wx86) - 8 (WLG) | 80 | 80 | 288 | Brute force-angreb (2006) | 2135 |
| Turing | 2000-2003 | 5.5 (Wx86) | 160 | ||||
| VEST | 2005 | 42 (WASIC) -64 (WFPGA) | Variabel sædvanligvis | Variabel sædvanligvis | 256 - 800 | N/A (2006) | N/A (2006) |
| VÆK | 1993 | Hurtig | 8192 | CPA & CCA | Sårbar | ||
| StreamCipher | CreationDate | Hastighed | (bits) | Angreb | |||
| Effektivt | Initialiseringsvektor | InternalState | Bedst kendt | Beregningskompleksitet | |||
Relaterede sider
- eSTREAM
Spørgsmål og svar
Spørgsmål: Hvad er en stream cipher?
Svar: En stream cipher er en symmetrisk nøglecipher, hvor klartekstbits kombineres med en pseudo-tilfældig cipherbitstrøm (keystream) ved hjælp af en eksklusiv-eller-operation (xor).
Sp: Hvordan adskiller den sig fra blokchifre?
Svar: Stream ciphers udføres typisk med højere hastighed end block ciphers og har lavere hardwarekrav. Block ciphers opererer med store blokke af fast længde, mens stream ciphers krypterer cifre et ad gangen, og transformationen af de på hinanden følgende cifre varierer under krypteringstilstanden.
Spørgsmål: Hvilken type nøgler bruger den?
Svar: Stream ciphers anvender meget mindre og mere bekvemme kryptografiske nøgler, f.eks. 128 bit-nøgler.
Spørgsmål: Hvordan genererer den nøglestrømmen?
Svar: Nøglestrømmen genereres på grundlag af den anvendte kryptografiske nøgle på samme måde som ved engangs-pad-krypteringsalgoritmen. Men da nøglestrømmen er pseudotilfældig og ikke virkelig tilfældig, kan den sikkerhed, der er forbundet med engangskoden, ikke anvendes.
Spørgsmål: Hvorfor må man aldrig bruge den samme starttilstand to gange?
Svar: Hvis man bruger den samme starttilstand to gange, kan det føre til alvorlige sikkerhedsproblemer, da det gør det lettere for angribere at dekryptere data uden at kende eller have adgang til din kryptografiske nøgle.
Sp: Er der nogen risiko forbundet med at bruge stream ciphers?
A: Ja, hvis de bruges forkert eller uden at tage de rette forholdsregler, er der risiko forbundet med at bruge stream ciphers, da de kan være helt usikre, hvis de ikke håndteres korrekt.
