RC4
RC4, ARC4 oder Arcfour ist eine Stromverschlüsselung, die mit Standards wie HTTPS, SSH 1 und WEP bzw. WPA weite Verbreitung gefunden hat.
RC4 (Ron’s Code 4) wurde 1987 von Ronald L. Rivest entwickelt, ist eine Marke von RSA Security und ist offiziell geheim (Security by Obscurity). ARC4 (Alleged RC4) oder Arcfour geht auf eine anonyme Veröffentlichung von Quelltext im Jahr 1994 zurück und ist Open Source.
Im Februar 2015 wurde mit RFC 7465 der Einsatz von RC4 im Rahmen von TLS verboten, da es erhebliche Sicherheitsmängel aufweist.[1][2]
Beschreibung
Eine Zufallsfolge wird aus einem nur einmalig zu verwendenden Schlüssel erzeugt. Der Klartext wird Bit für Bit per XOR mit der Zufallsfolge verknüpft, um die Daten zu verschlüsseln.
Der Zufallsgenerator verwendet eine sogenannte S-Box, eine zufällig gewählte Permutation oder Substitution der Zahlen 0 bis 255. Die S-Box wird in einem ersten Schritt aus dem geheimen Schlüssel berechnet und anschließend zur Berechnung der Zufallsfolge verwendet. Nach jedem Berechnungsschritt werden zwei Werte der S-Box vertauscht.
Die Sicherheit eines solchen Verfahrens ist nur gewährleistet, wenn sich die Zufallsfolge nicht wiederholt. Daher darf der Schlüssel bzw. das Passwort nur einmalig verwendet werden. Für die Besetzung der S-Box und die Werte zweier weiterer Variablen gibt es ca. 21684 Möglichkeiten, was einer Schlüssellänge von 210 (1684/8) Zeichen entsprechen würde. Nach dem Geburtstagsparadoxon ist zu erwarten, dass es Schlüssel mit einer Schlüssellänge von ((1684/2)/8) 105 Zeichen gibt, die identische Permutationen der S-Box erzeugen. Bekannt sind mittlerweile mindestens zwei 24 Zeichen (192 Bit) lange Schlüssel, die zur gleichen Permutation der S-Box führen. Damit gibt es zwei verschiedene Schlüssel, die zur gleichen Verschlüsselungsfolge führen.[3]
Der Algorithmus ist sehr einfach mit praktisch jeder Hard- und Software zu implementieren und sehr effizient berechenbar.
Im WEP wurde der einmalige Schlüssel durch einfaches Zusammensetzen eines festen geheimen Schlüssels und eines Session Key bestimmt. In diesem Fall ist es jedoch möglich, den festen geheimen Schlüssel abzuleiten. Falls der Schlüssel mit einer Hashfunktion quasi zufällig gewählt wird, kann der RC4 aber weiterhin als sicher betrachtet werden.
Bei Microsoft-Windows-Systemen, welche an eine NT-Domäne angebunden sind, wird das Anmeldepasswort, welches der Benutzer in der GINA-Oberfläche eingibt, nach vorangegangener Aushandlung eines Schlüssels per RC4-HMAC verschlüsselt und durch einen Kerberos-Frame an den Server übertragen. Die Aushandlung des Schlüssels findet während der Meldung „Netzwerkverbindungen werden vorbereitet“ statt.
Algorithmus
Kern des Verfahrens ist die sogenannte S-Box, eine zufällige Vertauschung oder Permutation des Standard-Alphabets (Byte-Werte 0–255). Mittels der S-Box wird eine Zufallsfolge erzeugt, die Bit für Bit durch Addition modulo 2, auch XOR-Verknüpfung genannt, mit dem Nachrichtenstrom verknüpft wird. Die S-Box wird zunächst als identische Abbildung vorbesetzt, so dass für i=0 bis 255 gilt.
Die initiale Belegung der S-Box kann mit dem folgenden Pseudo-Code beschrieben werden. Die S-Box wird dabei aus dem Schlüssel der Länge Byte berechnet:
k[]: gegebene Schlüssel-Zeichenfolge der Länge 5 bis 256 Byte
L := Länge des Schlüssels in Byte
s[]: Byte-Vektor der Länge 256
Für i = 0 bis 255
s[i] := i
j := 0
Für i = 0 bis 255
j := (j + s[i] + k[i mod L]) mod 256
vertausche s[i] mit s[j]
Die anschließende Berechnung der Zufallsfolge erfolgt analog:
klar[]: gegebene Klartext-Zeichenfolge der Länge X
schl[]: Vektor zum Abspeichern des Schlüsseltextes
i := 0
j := 0
Für n = 0 bis X-1
i := (i + 1) mod 256
j := (j + s[i]) mod 256
vertausche s[i] mit s[j]
zufallszahl := s[(s[i] + s[j]) mod 256]
schl[n] := zufallszahl XOR klar[n]
Zum Entschlüsseln verwendet man den gleichen Algorithmus, wobei der Schlüsseltext anstelle des Klartextes eingegeben wird. Zwei XOR-Verknüpfungen mit derselben Zufallszahl heben sich gegenseitig auf, und als Ausgabe entsteht wieder der Klartext.
Sicherheit
Wie jede Stromchiffre bietet auch RC4 keinen Integritätsschutz. Wenn ein Angreifer ein Bit einer verschlüsselten Nachricht ändert, so ändert er damit auch das gleiche Bit des Klartextes.
Der erste praktische Angriff auf die RC4-Chiffre gelang Scott Fluhrer, Itsik Mantin und Adi Shamir im Jahr 2001.[4] RSA Security empfahl daraufhin, die ersten 256 Bytes des Schlüsselstroms zu verwerfen.[5] Andreas Klein verbesserte den Angriff, so dass er auch dann funktioniert, wenn die ersten 256 Byte verworfen werden.[6] Er empfahl, die Ausgabe der ersten 12 Runden zu verwerfen.
Anfang 2013 wurde ein neues Angriffsszenario von AlFardan, Bernstein, Paterson, Poettering und Schuldt vorgeschlagen, das statistische Auffälligkeiten in der Schlüsseltabelle von RC4[7] verwendet, um einen Klartext zu entschlüsseln, der über mehrere mit RC4 verschlüsselte TLS-Verbindungen übertragen wird.[8][9] 2015 stellten Mathy Vanhoef und Frank Piessens einen praktisch durchführbaren Angriff auf RC4 vor, in dem Magic-Cookies innerhalb von 52 Stunden entschlüsselt werden konnten.[10]
Jacob Appelbaum ist der Ansicht, dass die NSA die RC4-Verschlüsselung in Echtzeit brechen könne. Bruce Schneier bezeichnete dies als eine plausible Vermutung.[11]
Die Europäische Agentur für Netz- und Informationssicherheit empfiehlt, RC4 durch Rabbit oder Snow 3G zu ersetzen.[12] Auch das Bundesamt für Sicherheit in der Informationstechnik rät von der Verwendung von RC4 ab. So setzt beispielsweise die Deutsche Finanzagentur RC4 seit November 2013 nicht mehr ein.[13]
Die Internet Engineering Task Force verbietet mit dem RFC 7465 seit Februar 2015 den Einsatz von RC4, da die Verschlüsselung in der Praxis durch zu wenige Versuche knackbar geworden wäre und sie keine ausreichend hohe Sicherheit für TLS Sessions mehr zur Verfügung stellen könne.[14][2]
Nachfolger
Spritz
Am 27. Oktober 2014 stellten Ronald L. Rivest und Jacob C. N. Schuldt eine verbesserte Variante von RC4 namens Spritz vor.[15] Allerdings wird die Performance von RC4 nicht ganz erreicht. Der Algorithmus ist nur etwa halb so schnell wie RC4, aber noch immer wesentlich schneller als standardisierte Blockchiffren wie der Advanced Encryption Standard. Die Schlüsselberechnung dauert länger als bei RC4.[16]
Es folgt eine kurze Gegenüberstellung der Kernstücke von RC4 und SPRITZ.
RC4:
i = i + 1
j = j + S[i]
SWAP(S[i],S[j])
z = S[S[i] + S[j]]
Return z
SPRITZ:
i = i + w
j = k + S[j + S[i]]
k = i + k + S[j]
SWAP(S[i],S[j])
z = S[j + S[i + S[z + k]]]
Return z
Der Parameter w ist eine zu N teilerfremde Zahl, wobei N (meist 256) die Größe des Arrays S ist. Addiert wird immer modulo N. Nach N Iterationen hat i daher jeden Wert von 0 bis N-1 genau einmal angenommen. Jeder Wert in S wurde entsprechend mindestens einmal mit einer zufällig gewählten Position vertauscht.
Weblinks
- Überblick über Arbeiten bezüglich der Sicherheit von RC4 (englisch)
- Original-Post des damals noch geheimen RC4-Algorithmus im Usenet (englisch)
- Scott Fluhrer, Itsik Mantin, Adi Shamir: Weaknesses in the Key Scheduling Algorithm of RC4. (PDF; 297 kB; englisch)
- A Stream Cipher Encryption Algorithm “Arcfour” (Internet Engineering Task Force Network Working Group 1997)
- RFC 4345 – Improved Arcfour Modes for the Secure Shell (SSH) Transport Layer Protocol
Einzelnachweise
- Jürgen Schmidt: IETF verbietet RC4-Verschlüsselung in TLS. Heise Security, 20. Februar 2015, abgerufen am 20. Februar 2015.
- A. Popov: Prohibiting RC4 Cipher Suites. Internet Engineering Task Force (IETF), Februar 2015, abgerufen am 11. März 2016.
- Mitsuru Matsui: Key Collisions of the RC4 Stream Cipher. Fast Software Encryption, 2009. In: Lecture Notes. In: Computer Science, Nummer 5665, Springer Verlag, 2009, S. 38–50, Präsentation (PDF; 267 kB; englisch)
- Scott Fluhrer, Itsik Mantin, Adi Shamir: Weaknesses in the Key Scheduling Algorithm of RC4. In: Selected Areas in Cryptography (= Lecture Notes in Computer Science). Band 2259. Springer, 2001, S. 1–24, doi:10.1007/3-540-45537-X_1 (weizmann.ac.il). Weaknesses in the Key Scheduling Algorithm of RC4 (Memento des Originals vom 2. Juni 2004 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
- RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4. (Nicht mehr online verfügbar.) RSA Security, archiviert vom Original am 29. September 2011; abgerufen am 10. September 2012 (englisch). Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
- Andreas Klein: Attacks on the RC4 stream cipher. In: Designs, Codes and Cryptography. Band 48, Nr. 3. Springer, 2008, S. 269–286, doi:10.1007/s10623-008-9206-6.
- Pouyan Sepehrdad, Serge Vaudenay, Martin Vuagnoux: Discovery and Exploitation of New Biases in RC4. In: Lecture Notes in Computer Science. 6544, 2011, S. 74–91. doi:10.1007/978-3-642-19574-7_5.
- Green, Matthew: Attack of the week: RC4 is kind of broken in TLS. In: Cryptography Engineering. Abgerufen am 12. März 2013.
- Nadhem AlFardan, Dan Bernstein, Kenny Paterson, Bertram Poettering, Jacob Schuldt: On the Security of RC4 in TLS. Royal Holloway University of London. Abgerufen am 13. März 2013.
- Mathy Vanhoef, Frank Piessens: All Your Biases Belong To Us: Breaking RC4 in WPA-TKIP and TLS (PDF; 346 kB).
- NSA entschlüsselt Webserver-Daten angeblich in Echtzeit. Heise Security. Abgerufen am 7. November 2013.
- Michael Brenner: ENISA-Empfehlungen zu Krypto-Verfahren. Heise Security. Abgerufen am 18. November 2013.
- Wichtige Information für Internetbanking-Nutzer. (Nicht mehr online verfügbar.) Deutsche Finanzagentur, 19. November 2013, archiviert vom Original am 7. Januar 2015; abgerufen am 2. Januar 2014. Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
- Jürgen Schmidt: IETF verbietet RC4-Verschlüsselung in TLS. In: Heise Security. Heise online, 20. Februar 2015, abgerufen am 8. Juli 2015.
- Spritz – a spongy RC4-like stream cipher and hash function. Ronald L. Rivest und Jacob C. N. Schuldt, 27. Oktober 2014, abgerufen am 1. November 2014.
- Spritz: A New RC4-Like Stream Cipher. Bruce Schneier, 27. Oktober 2014, abgerufen am 1. November 2014.