Home > Kryptographie > Moderne Kryptographie > RC4
Kryptographie
In diesem Kapitel will ich Ihnen eine sog. Stromchiffrierung vorstellen. Im Gegensatz zu Blockchiffrierungen, die wir im Kapitel über DES kennengelernt haben, arbeiten solche Verfahren nicht auf Blöcken, sondern verarbeiten immer ein Bit oder ein Byte (manchmal auch 32-Bit-"Wörter"). Oft handelt es sich bei diesen Chiffrierungen um sog. Pseudozufallsgeneratoren, über die wir in diesem Kapitel und später mehr erfahren werden.
RC4 ist eigentlich ein solcher Pseudozufallsgenerator. Das Verfahren wurde 1987 von Ronald L. Rivest für RSA Data Security Inc. (heute RSA Security) entwickelt. Der Algorithmus war ganze sieben Jahre lang geheim, bis 1994 jemand anonym den Quellcode veröffentlichte.
Keine Bange – RC4 ist so einfach, dass ihn die meisten Programmierer aus dem Kopf implementieren können.
Im Gegensatz zu DES hat RC4 eine variable Schlüssellänge. Die Schlüssellänge kann bis zu 2048 Bit (!) betragen. RC4 verschlüsselt immer ein Byte auf einmal.
Bei RC4 gibt es eine S-Box S (nochmal zur Erinnerung: eine S-Box ist eine Substitutionstabelle) mit 256 Einträgen der Länge 8 Bit (man sagt auch, die S-Box hat eine Größe von 8 · 8, d. h. 8 Bit werden ersetzt, 8 Bit erhält man als Ausgabe). Die Einträge in dieser Box reichen von S0 (1. Eintrag) bis S255 (256. Eintrag). Außerdem gibt es zwei 8-Bit große Zähler i und j, die zu Anfang auf 0 gesetzt werden.
Bevor man mit RC4 verschlüsseln kann, muss man den Algorithmus initialisieren, in unserem Falle muss die S-Box erstellt werden. Dies geschieht folgendermaßen:
Zuerst wird die S-Box linear aufgefüllt: S0 = 0, S1 = 1, ... S255 = 255. Dann wird folgende Schleife durchlaufen:
für i von 0 bis 255
j = (j + Si + Ki mod k) mod 256
vertausche Si und Sj
nächstes i
wobei K der Schlüssel und k die Schlüssellänge ist. Falls der Schlüssel nicht genau 256 Byte lang ist, muss er wiederholt werden, man fängt also wieder bei K0 an. Dies kann man einfach erreichen, indem man eine modulo-Operation durchführt, d. h. i mod Schlüssellänge.
So, jetzt wollen wir ein Zufallsbyte erzeugen. Dieses Byte wird mit dem Klartextbyte xor-verknüpft, um das Geheimtextbyte zu erhalten:
Alle Operationen verstehen sich modulo 256, d. h. jedes Ergebnis wird einer modulo-256-Operation unterzogen. Schließlich hat die S-Box ja nur 256 Einträge, d. h. der erste Eintrag ist S0 und der letzte S255.
Zur Entschlüsselung xor-verknüpft man das Geheimtextbyte mit dem Zufallsbyte und erhält das Klartextbyte – Entschlüsselung ist praktisch genau dasselbe wie Verschlüsselung – xor macht's möglich. Theoretisch könnte man die Bytes auch addieren (modulo 256) statt xor'en, die Entschlüsselung wäre dann aber geringfügig komplizierter.
Wir können so viele Schlüsselbytes erzeugen wie wir lustig sind. Um einen Text zu verschlüsseln, brauchen wir so viele Bytes wie der Text lang ist. Bei einem 1.302 Byte langen Text lassen wir uns 1.302 Schlüsselbytes ausgeben, mit denen wir die Klartextbytes per xor verknüpfen. Ebenso bei der Entschlüsselung, da die Ver- und Entschlüsselungs-Funktionen identisch sind – xor sei Dank!
Tja, das war's. Bisher konnte man keine Schwächen im Algorithmus feststellen. Doch leider haben solche Stromchiffrierungen äußerst störende Eigenschaften. Zunächst einmal ist das berechnete Zufallsbyte völlig unabhängig vom Klartextbyte. Das Klartextbyte wird einfach nur mit dem erzeugten Zufallsbyte per xor verknüpft, mehr nicht. Hier gibt es keine komplizierten Operationen mit Klartext und Schlüssel wie bei DES. Und das ist das Problem: Im allerschlimmsten Fall liegt dem Angreifer ein Paar Klartext/Chiffretext vor. Um an die ganze Zufallssequenz zu gelangen, muss der Angreifer nur den Klartext und den Chiffretext xor'en, da gilt:
b xor k xor b = k
Hier ist b das Klartextbyte und k ein Zufallsbyte. b xor k ist also nichts anderes als der Chiffretext. Da xor praktisch selbstumkehrend ist, kann ein Angreifer so ohne große Mühe die gesamte Zufallssequenz berechnen. Er kann zwar nicht direkt auf den ursprünglichen Schlüssel kommen, d. h. den Schlüssel, mit dem RC4 initialisiert wurde, er kann aber möglicherweise andere verschlüsselte Texte damit knacken.
Das zweite Problem ergibt sich dann, wenn wir zwei unterschiedliche Texte mit demselben Schlüssel verschlüsseln. Die Klartexte müssen dabei nicht bekannt sein. Man betrachtet die beiden Texte jetzt als einen ganzen Text. Dort, wo der zweite Text anfängt, wiederholt sich die von RC4 erzeugte Zufallssequenz. Der böse Bub kann nach Mustern suchen und Methoden benutzen, die zum Knacken von Vigenère-Chiffrierungen verwendet werden. Je mehr Chiffretexte dem Angreifer zur Verfügung stehen, desto mehr Material erhält er für seine Kryptoanalyse.
Nicht alle Stromchiffrierungen sind völlig unabhängig vom Klartext wie RC4. Trotzdem sind diese beiden Eigenschaften äußerst störend in der Kryptographie. Meist werden daher Blockchiffrierungen vorgezogen, weil sie eben diesen Angriffen standhalten – das ist ein wichtiges Kriterium für die Sicherheit eines Blockalgorithmus! Gleichwohl gibt es eine Möglichkeit, diese beiden Probleme zu umgehen. Dazu nimmt man eine gehörige Prise Salz ...
Salt (Salz) ist eine Zufallssequenz bestimmter Länge, an die das Passwort (bzw. der Schlüssel) angehängt wird. Diese Sequenz hat meistens eine Länge zwischen 40 und 88 Bit. Lautet die Zufallssequenz beispielsweise tu53mp[! und das Passwort geheim, so ergibt sich als Schlüssel:
tu53mp[!geheim
Mit diesem Schlüssel initialisiert man die Stromchiffrierung oder ggf. auch die Blockchiffrierung (für solche gibt es allerdings eine bessere Methode, auf die wir im Kapitel über Betriebsmodi von Blockchiffrierungen noch zu sprechen kommen). Da die Bytefolge zufällig gewählt wurde, ergibt sich für jeden Klartext ein anderer Schlüssel, und daher wird jeder Klartext individuell verschlüsselt. Der Angreifer kann zwar immer noch die Schlüsselsequenz rekonstruieren, wenn ihm Klartext und Chiffretext zur Verfügung stehen, dies wird ihm jedoch nicht viel nützen, da diese Zufallsbytes nur für diesen einen Text gelten. Auch wenn er zwei unterschiedliche Klartexte besitzt, die mit demselben Passwort verschlüsselt wurden, ist eine Kryptoanalyse sinnlos, da die Zufallssequenzen völlig unterschiedlich sind (was wir hoffen!). Leider hat dieses Verfahren auch einen kleinen Nachteil: Beim Verschlüsseln einer Datei muss der Algorithmus neu initialisiert werden, jedesmal mit neuem Salt. Bei RC4 ist das nicht besonders gravierend, da das "Keysetup", wie man auch sagt, recht schnell durchgeführt werden kann. Bei Verfahren wie SEAL jedoch dauert das Keysetup sehr lange. Dafür verschlüsselt SEAL sehr schnell; wahrscheinlich ist es das schnellste Verfahren überhaupt! Tja, was man sich an Geschwindigkeit bei der Verschlüsselung erkauft, muss man an Geschwindigkeit beim Initialisieren sparen ... (so in etwa, Sie wissen schon, was ich meine :-)
Salt wird nicht nur für kryptographische Algorithmen verwendet, sondern auch für sog. Einweg-Hash-Funktionen.
Und nun kommt die wichtigste Frage überhaupt: Ist RC4 sicher? Dazu nur so viel: Man geht davon aus, dass RC4 sicher ist. RSA Security behauptet, der Algorithmus sei resistent gegen differentielle und lineare Kryptoanalyse, arbeite mit großen Zyklen und sei hochgradig nichtlinear; zudem habe es eine Periode von 10100 (!), d. h. nach 10100 Verschlüsselungen trete eine Wiederholung des Schlüsselstroms auf. Gleichwohl existieren keine öffentlichen Analyseergebnisse. Bemerkenswert ist immerhin die enorme Anzahl möglicher Zustände von RC4: 21700 (ca. 10512)! Der Algorithmus ist so konstruiert, dass sich die S-Box dank der Zähler i und j nur langsam verändert. Die oben beschrieben Variante von RC4 arbeitet auf einer Wortlänge von 8 Bit. Die Idee ließe sich jedoch auch auf größere Wortlängen verallgemeinern: So wäre auch 16-Bit-RC4 denkbar, welches auf Basis von 16-Bit-Wörtern arbeitet und eine S-Box mit 65536 (216) Einträgen besitzt. Zwar würde die Initialisierung von RC4 erheblich länger dauern, der entstehende Algorithmus sollte jedoch doppelt so schnell wie 8-Bit-RC4 sein.
Wichtiger Hinweis: Vor Kurzem wurde eine geringfügige Schwäche bei RC4 gefunden: Die ersten 256 ausgegebenen Schlüsselbytes gäben Rückschlüsse auf den Zustand der S-Box; dieses Problem lässt sich leicht umgehen, indem die ersten 256 Schlüsselbytes verworfen werden, d. h. die Initialisierungs-Prozedur müsste um folgende Routine ergänzt werden:
für i von 1 bis 256
verschlüssele einen beliebigen Wert
nächstes i
Diese Variante von RC4 wird auch als "ARC4" ("Alleged-RC4") bezeichnet.
Bleibt noch zu erwähnen, dass RC4 von RSA Security patentiert ist und ohne Lizenz (theoretisch jedenfalls) nicht verwendet werden darf. Wenn Sie RC4 in kommerziellen Produkten unlizenziert einzusetzen gedenken, ist Vorsicht geboten, denn RSA Security könnte auf das bestehende Patent pochen und einen Prozess gegen Sie anstrengen. Sie können sich aber dieses Hindernisses entledigen, indem Sie RC4 unter einem anderen Namen verwenden; gebräuchlich ist z. B. "PC1" – oder benutzen Sie gleich die ARC4-Variante. Sie können ja vorsichtshalber noch anmerken, dieser Algorithmus sei "100% kompatibel zum RC4-Algorithmus". :-) Nichtsdestoweniger wird RC4 mittlerweile in unzähligen Produkten eingesetzt.
Ronald L. Rivest ist nicht nur Autor von RC4, sondern auch zahlreicher anderer Algorithmen wie RC2, RC5 und dem AES-Kandidaten RC6. Außerdem war er an der Entwicklung von RSA beteiligt. Sein Hash-Algorithmus MD5 diente als Vorlage für nachfolgende Algorithmen wie SHA-1; tatsächlich wurde bei SHA-1, der von der NSA entwickelt wurde, grundlegende Funktionen übernommen. "RCx" steht übrigens für "Ron's Code" (Nummer x). Rivests Algorithmen sind zumeist einfach und daher leichter zu untersuchen als Verfahren, deren mathematische Eigenschaften sehr komplex sind. Bisher konnte kein Verfahren von Rivest erfolgreich geknackt werden. RC4 wird in vielen Software-Produkten eingesetzt und ist die wohl beliebteste Stromchiffrierung, da ausgesprochen einfach, aber trotzdem gut. Mehr über Mr. Rivest erfahren Sie auf seiner Homepage.
 Zurück |
nach oben |
 |
 Übersicht |
Weiter  |
Letzte Änderung: 25.03.2002
© 2002 by Christian Thöing