Stream Chiffre - Stream cipher

Der Betrieb des Keystream- Generators in A5/1 , einer LFSR-basierten Stream-Chiffre zum Verschlüsseln von Mobiltelefongesprächen.

Eine Stromchiffre ist eine symmetrische Schlüssel - Chiffre in dem Klartext - Ziffern mit einem kombiniert werden Pseudo - Zufallsverschlüsselungszeichenstrom ( Keystream ). In einer Stromchiffre wird jede Klartextziffer einzeln mit der entsprechenden Ziffer des Schlüsselstroms verschlüsselt, um eine Ziffer des Chiffretextstroms zu ergeben . Da die Verschlüsselung jeder Ziffer vom aktuellen Zustand der Chiffre abhängt, wird sie auch als State Chiffre bezeichnet . In der Praxis ist eine Ziffer typischerweise ein Bit und die Kombinationsoperation ist ein Exklusiv-Oder (XOR).

Der pseudozufällige Schlüsselstrom wird typischerweise seriell aus einem zufälligen Startwert unter Verwendung digitaler Schieberegister erzeugt . Der Seed-Wert dient als kryptografischer Schlüssel zum Entschlüsseln des Chiffretext-Streams. Stromchiffren stellen einen anderen Ansatz für die symmetrische Verschlüsselung dar als Blockchiffren . Blockchiffren arbeiten mit großen Ziffernblöcken mit einer festen, unveränderlichen Transformation. Diese Unterscheidung ist nicht immer eindeutig: In einigen Betriebsarten wird ein Blockchiffrierprimitive so verwendet, dass es effektiv als Stromchiffre fungiert. Stromchiffren werden typischerweise mit einer höheren Geschwindigkeit ausgeführt als Blockchiffren und haben eine geringere Hardwarekomplexität. Allerdings können Stream-Chiffren anfällig für Sicherheitsverletzungen sein (siehe Stream-Chiffre-Angriffe ); B. wenn der gleiche Startzustand (Seed) zweimal verwendet wird.

Lose Inspiration aus dem One-Time-Pad

Stromchiffren können als Annäherung an die Wirkung einer bewährten unzerbrechlichen Chiffre angesehen werden, dem One-Time-Pad (OTP). Ein One-Time-Pad verwendet einen Schlüsselstrom von vollständig zufälligen Ziffern. Der Schlüsselstrom wird nacheinander mit den Klartextziffern kombiniert, um den Geheimtext zu bilden. Dieses System wurde 1949 von Claude E. Shannon als sicher bewiesen . Der Schlüsselstrom muss jedoch völlig zufällig mit mindestens der gleichen Länge wie der Klartext generiert werden und kann nicht mehr als einmal verwendet werden. Dies macht die Implementierung des Systems in vielen praktischen Anwendungen umständlich, und als Ergebnis wurde das Einmal-Pad mit Ausnahme der kritischsten Anwendungen nicht weit verbreitet verwendet. Schlüsselgenerierung, -verteilung und -verwaltung sind für diese Anwendungen von entscheidender Bedeutung.

Eine Stromchiffre verwendet einen viel kleineren und bequemeren Schlüssel wie 128 Bit. Basierend auf diesem Schlüssel generiert es einen pseudozufälligen Keystream, der ähnlich wie beim One-Time-Pad mit den Klartextziffern kombiniert werden kann. Dies ist jedoch mit Kosten verbunden. Der Schlüsselstrom ist jetzt pseudozufällig und somit nicht wirklich zufällig. Der mit dem One-Time-Pad verbundene Sicherheitsnachweis gilt nicht mehr. Es ist durchaus möglich, dass eine Stromchiffre völlig unsicher ist.

Typen

Eine Stromchiffre generiert aufeinanderfolgende Elemente des Schlüsselstroms basierend auf einem internen Zustand. Dieser Zustand wird im Wesentlichen auf zwei Arten aktualisiert: Wenn sich der Zustand unabhängig von den Klartext- oder Chiffretextnachrichten ändert , wird die Chiffre als eine synchrone Stromchiffre klassifiziert . Im Gegensatz dazu aktualisieren selbstsynchronisierende Stromchiffren ihren Zustand basierend auf vorherigen Geheimtextziffern.

Synchrone Stromchiffren

Lorenz SZ Chiffriermaschine , wie sie vom deutschen Militär im Zweiten Weltkrieg eingesetzt wurde

Bei einer synchronen Stromchiffre wird ein Strom von Pseudozufallsziffern unabhängig vom Klartext und den Geheimtextnachrichten erzeugt und dann mit dem Klartext (zum Verschlüsseln) oder dem Geheimtext (zum Entschlüsseln) kombiniert. In der gebräuchlichsten Form werden Binärziffern verwendet ( Bits ) und der Schlüsselstrom mit dem Klartext unter Verwendung der Exklusiv-Oder- Operation (XOR) kombiniert. Dies wird als binäre additive Stromchiffre bezeichnet .

Bei einer synchronen Stromchiffre müssen Sender und Empfänger genau im Gleichschritt sein, damit die Entschlüsselung erfolgreich ist. Wenn der Nachricht während der Übertragung Ziffern hinzugefügt oder daraus entfernt werden, geht die Synchronisierung verloren. Um die Synchronisation wiederherzustellen, können verschiedene Offsets systematisch versucht werden, um die korrekte Entschlüsselung zu erhalten. Ein anderer Ansatz besteht darin, den Geheimtext an regelmäßigen Stellen in der Ausgabe mit Markierungen zu versehen.

Wenn jedoch eine Ziffer bei der Übertragung beschädigt wird, anstatt hinzugefügt oder verloren zu gehen, ist nur eine einzelne Ziffer im Klartext betroffen und der Fehler breitet sich nicht auf andere Teile der Nachricht aus. Diese Eigenschaft ist nützlich, wenn die Übertragungsfehlerrate hoch ist; es ist jedoch weniger wahrscheinlich, dass der Fehler ohne weitere Mechanismen erkannt wird. Darüber hinaus sind synchrone Stromchiffren aufgrund dieser Eigenschaft sehr anfällig für aktive Angriffe : Wenn ein Angreifer eine Ziffer im Geheimtext ändern kann, könnte er vorhersehbare Änderungen am entsprechenden Klartextbit vornehmen; zum Beispiel führt das Spiegeln eines Bits im Geheimtext dazu, dass dasselbe Bit im Klartext gespiegelt wird.

Selbstsynchronisierende Stromchiffren

Ein anderer Ansatz verwendet mehrere der vorherigen N Geheimtextziffern, um den Schlüsselstrom zu berechnen. Solche Schemata sind als selbstsynchronisierende Stromchiffren , asynchrone Stromchiffren oder Ciphertext Autokey ( CTAK ) bekannt. Die Idee der Selbstsynchronisation wurde 1946 patentiert und hat den Vorteil, dass sich der Empfänger nach dem Empfang von N Geheimtextziffern automatisch mit dem Schlüsselstromgenerator synchronisiert , was die Wiederherstellung erleichtert, wenn Ziffern weggelassen oder zum Nachrichtenstrom hinzugefügt werden. Einstellige Fehler sind in ihrer Wirkung begrenzt und betreffen nur bis zu N Klartextziffern.

Ein Beispiel für eine selbstsynchronisierende Stromchiffre ist eine Blockchiffre im Cipher-Feedback- (CFB) -Modus .

Basierend auf Linear-Feedback-Schieberegistern

Binäre Stromchiffren werden oft unter Verwendung von Linear-Feedback-Schieberegistern (LFSRs) konstruiert, da sie leicht in Hardware implementiert und mathematisch leicht analysiert werden können. Die alleinige Verwendung von LFSRs reicht jedoch nicht aus, um eine gute Sicherheit zu gewährleisten. Es wurden verschiedene Schemata vorgeschlagen, um die Sicherheit von LFSRs zu erhöhen.

Nichtlineare Kombinationsfunktionen

Ein Ansatz besteht darin, n LFSRs parallel zu verwenden, wobei ihre Ausgänge unter Verwendung einer binären booleschen Funktion ( F ) mit n Eingängen kombiniert werden .

Da LFSRs von Natur aus linear sind, besteht eine Technik zum Entfernen der Linearität darin, die Ausgänge mehrerer paralleler LFSRs in eine nichtlineare Boolesche Funktion einzuspeisen , um einen Kombinationsgenerator zu bilden . Verschiedene Eigenschaften einer solchen Kombinationsfunktion sind kritisch, um die Sicherheit des resultierenden Schemas zu gewährleisten, beispielsweise um Korrelationsangriffe zu vermeiden .

Taktgesteuerte Generatoren

Normalerweise werden LFSRs regelmäßig gestuft. Ein Ansatz zur Einführung von Nichtlinearität besteht darin, das LFSR unregelmäßig takten zu lassen, gesteuert durch die Ausgabe eines zweiten LFSR. Solche Generatoren umfassen den Stop-and-Go-Generator , den Wechselschrittgenerator und den Schrumpfgenerator .

Ein Wechselschrittgenerator besteht aus drei LFSRs, die wir der Einfachheit halber als LFSR0, LFSR1 und LFSR2 bezeichnen. Die Ausgabe eines der Register entscheidet, welches der anderen beiden verwendet wird; Wenn beispielsweise LFSR2 eine 0 ausgibt, wird LFSR0 getaktet, und wenn es eine 1 ausgibt, wird stattdessen LFSR1 getaktet. Die Ausgabe ist das exklusive ODER des letzten von LFSR0 und LFSR1 erzeugten Bits. Der Ausgangszustand der drei LFSRs ist der Schlüssel.

Der Stop-and-Go-Generator (Beth und Piper, 1984) besteht aus zwei LFSRs. Ein LFSR wird getaktet, wenn die Ausgabe eines zweiten eine 1 ist, andernfalls wiederholt es seine vorherige Ausgabe. Dieser Ausgang wird dann (in einigen Versionen) mit dem Ausgang eines dritten, regelmäßig getakteten LFSR kombiniert.

Der Schrumpfgenerator verfolgt einen anderen Ansatz. Es werden zwei LFSRs verwendet, die beide regelmäßig getaktet werden. Wenn die Ausgabe des ersten LFSR 1 ist, wird die Ausgabe des zweiten LFSR die Ausgabe des Generators. Gibt der erste LFSR jedoch 0 aus, wird der Ausgang des zweiten verworfen und vom Generator kein Bit ausgegeben. Dieser Mechanismus leidet unter Timing-Angriffen auf den zweiten Generator, da die Drehzahl des Ausgangs in Abhängigkeit vom Zustand des zweiten Generators variabel ist. Dies kann durch Pufferung der Ausgabe abgemildert werden.

Filtergenerator

Ein anderer Ansatz zur Verbesserung der Sicherheit eines LFSR besteht darin, den gesamten Zustand eines einzelnen LFSR in eine nichtlineare Filterfunktion zu überführen .

Andere Designs

RC4 ist eines der am weitesten verbreiteten Stream-Chiffre-Designs.

Anstelle einer linearen Antriebsvorrichtung kann eine nichtlineare Aktualisierungsfunktion verwendet werden. Zum Beispiel schlugen Klimov und Shamir Dreiecksfunktionen ( T-Funktionen ) mit einem einzigen Zyklus für n-Bit-Wörter vor.

Sicherheit

Damit eine Stromchiffre sicher ist, muss ihr Schlüsselstrom eine große Periode haben , und es muss unmöglich sein, den Schlüssel oder den internen Zustand der Verschlüsselung aus dem Schlüsselstrom wiederherzustellen . Cryptographers verlangt auch , dass die Keystream selbst subtiler Vorurteile sein , die die Angreifer lassen würde unterscheiden einen Strom von Zufallsrauschen, und frei von nachweisbaren Beziehungen zwischen Schlüsselströmen dass entsprechen zugehörige Tasten oder verwandte Verschlüsselungs Nonces . Das sollte wahr sein für alle Tasten (es sollten kein seine schwacher Schlüssel ), auch wenn die Angreifer wissen , oder wählen einig Klartext oder Chiffretext .

Wie bei anderen Angriffen in der Kryptographie können Stream-Chiffre-Angriffe zertifizierungspflichtig sein, sodass sie nicht unbedingt praktische Möglichkeiten zum Entschlüsseln der Chiffre darstellen, aber darauf hinweisen, dass die Chiffre andere Schwächen aufweisen könnte.

Die sichere Verwendung einer sicheren synchronen Stromchiffre erfordert, dass man denselben Schlüsselstrom niemals zweimal wiederverwendet. Das bedeutet im Allgemeinen , dass jedem Aufruf der Chiffre eine andere Nonce oder ein anderer Schlüssel übergeben werden muss. Anwendungsdesigner müssen auch erkennen, dass die meisten Stromchiffren nicht Authentizität, sondern Datenschutz bieten : verschlüsselte Nachrichten können während der Übertragung noch modifiziert worden sein.

Kurze Zeiträume für Stromchiffren waren ein praktisches Anliegen. Beispielsweise können 64-Bit-Blockchiffren wie DES verwendet werden, um einen Schlüsselstrom im Output-Feedback- Modus (OFB) zu generieren . Wenn jedoch kein vollständiges Feedback verwendet wird, hat der resultierende Stream im Durchschnitt eine Periode von etwa 2 ³² Blöcken; für viele Anwendungen ist die Frist viel zu gering. Wenn beispielsweise eine Verschlüsselung mit einer Geschwindigkeit von 8 Megabyte pro Sekunde durchgeführt wird, wird ein Stream von Periode 2 ³² Blöcken nach etwa einer halben Stunde wiederholt.

Einige Anwendungen, die die Stromchiffre RC4 verwenden, sind aufgrund von Schwächen in der Schlüssel-Setup-Routine von RC4 angreifbar; neue Anwendungen sollten entweder RC4 vermeiden oder sicherstellen, dass alle Schlüssel eindeutig und idealerweise nicht miteinander verbunden sind (wie etwa durch ein gut gesetztes CSPRNG oder eine kryptografische Hash-Funktion generiert ) und dass die ersten Bytes des Schlüsselstroms verworfen werden.

Die Elemente von Stromchiffren sind oft viel einfacher zu verstehen als Blockchiffren und verbergen daher weniger wahrscheinlich zufällige oder böswillige Schwächen.

Verwendungszweck

Stromchiffren werden oft wegen ihrer Geschwindigkeit und Einfachheit der Implementierung in Hardware und in Anwendungen verwendet, bei denen Klartext in Mengen von unbekannter Länge vorkommt, wie eine sichere drahtlose Verbindung. Wenn eine Blockchiffre (die nicht in einem Stromchiffre-Modus arbeitet) in dieser Art von Anwendung verwendet werden sollte, müsste der Designer entweder die Übertragungseffizienz oder die Implementierungskomplexität wählen, da Blockchiffren nicht direkt mit Blöcken arbeiten können, die kürzer als ihre Blockgröße sind. Wenn beispielsweise eine 128-Bit-Blockchiffre separate 32-Bit-Klartext-Bursts empfängt, wären drei Viertel der übertragenen Daten Padding . Blockchiffren müssen im Ciphertext-Stealing- oder Restblock-Termination- Modus verwendet werden, um Padding zu vermeiden, während Streamchiffren dieses Problem beseitigen, indem sie natürlich auf der kleinsten Einheit arbeiten, die übertragen werden kann (normalerweise Bytes).

Ein weiterer Vorteil von Stromchiffren in der Militärkryptographie besteht darin, dass der Chiffrierstrom in einer separaten Box erzeugt werden kann, die strengen Sicherheitsmaßnahmen unterliegt, und anderen Geräten wie einem Funkgerät zugeführt werden kann, die im Rahmen ihrer Funktion die XOR-Operation durchführen. Letzteres Gerät kann dann in weniger strengen Umgebungen entworfen und verwendet werden.

ChaCha wird zur am weitesten verbreiteten Stromchiffre in der Software; andere sind: RC4 , A5/1 , A5/2 , Chamäleon , FISH , Helix , ISAAC , MUGI , Panama , Phelix , Pike , Salsa20 , SEAL , SOBER , SOBER-128 und WAKE .

Vergleich

Wissenswertes

• In Dokumenten der National Security Agency der Vereinigten Staaten wird manchmal der Begriff Algorithmen vom Kombinatortyp verwendet , die sich auf Algorithmen beziehen, die eine Funktion verwenden, um einen Pseudozufallszahlengenerator (PRNG) mit einem Klartextstrom zu kombinieren.

Siehe auch

• eSTREAM
• Linear-Feedback-Schieberegister (LFSR)
• Schieberegister mit nichtlinearer Rückkopplung (NLFSR)

Anmerkungen

Verweise

• Matt JB Robshaw, Stream Ciphers Technical Report TR-701, Version 2.0, RSA Laboratories, 1995 (PDF) .
• Beth, Thomas; Piper, Fred (1985). Der Stop-and-Go-Generator (PDF) . EUROKRYPTA '84. S. 88–92. doi : 10.1007/3-540-39757-4_9 .
• Christof Paar, Jan Pelzl, "Stream Ciphers" , Kapitel 2 von "Understanding Cryptography, A Lehrbuch für Studenten und Praktiker". (Begleitwebsite enthält einen Online-Kryptografiekurs, der Stromchiffren und LFSR behandelt), Springer, 2009.

Externe Links

• Technischer RSA-Bericht über den Betrieb der Stromchiffre.
• Kryptoanalyse und Design von Stromchiffren (Dissertation von Hongjun Wu).
• Analyse von Lightweight Stream Ciphers (Dissertation von S. Fischer).