Quelltext der Seite RC4

'''RC4''', ''ARC4'' oder ''Arcfour'' ist eine [[Stromverschlüsselung]], die mit Standards wie [[Hypertext Transfer Protocol Secure|HTTPS]], [[Secure Shell|SSH 1]] und [[Wired Equivalent Privacy|WEP]] bzw. [[Wi-Fi Protected Access|WPA]] weite Verbreitung gefunden hat.

RC4 (''Rivest Cipher 4'') wurde 1987 von [[Ronald L. Rivest]] entwickelt und ist eine [[Marke (Recht)|Marke]] von [[RSA Security]]. Der Algorithmus wurde vom Hersteller geheim gehalten (siehe [[Security by Obscurity]]), bis sein [[Quelltext]] im Jahr 1994 anonym auf einer [[Mailingliste]] veröffentlicht wurde.<ref>{{Internetquelle |url=https://web.archive.org/web/20010722163902/http://cypherpunks.venona.com/date/1994/09/msg00304.html |titel=Thank you Bob Anderson |abruf=2025-01-01 |werk=Cypherphunks Mailingliste}}</ref> Der Algorithmus fand Verbreitung als [[Open Source]] und wurde zur Vermeidung einer Markenrechtsverletzung als ''ARC4'' (''Alleged RC4'') oder ''Arcfour'' bezeichnet.

Im Februar 2015 wurde mit <nowiki>RFC&nbsp;7465</nowiki> der Einsatz von RC4 im Rahmen von [[Transport Layer Security|TLS]] verboten, da es erhebliche Sicherheitsmängel aufweist.<ref>{{Internetquelle |autor=Jürgen Schmidt |url=https://www.heise.de/security/meldung/IETF-verbietet-RC4-Verschluesselung-in-TLS-2556520.html |titel=IETF verbietet RC4-Verschlüsselung in TLS |hrsg=Heise Security |datum=2015-02-20 |abruf=2015-02-20}}</ref><ref name="RFC7465" />

== 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ällige Permutation|zufällig gewählte Permutation]] oder [[Monoalphabetische Substitution|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. 2<sup>1684</sup> 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 <math>\frac{\frac{1684}{2}}{8}\approx{105}</math> 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.<ref name="fse2009matsui">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, [http://www.iacr.org/workshops/fse2009/slides/2302_1015_Matsui.pdf Präsentation] (PDF; 267&nbsp;kB; englisch)</ref>

Der [[Algorithmus]] ist sehr einfach mit praktisch jeder Hard- und Software zu implementieren und sehr effizient berechenbar.

Im [[Wired Equivalent Privacy|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|Microsoft-Windows]]-Systemen, welche an eine NT-[[Domain Controller|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 (Protokoll)|Kerberos]]-Frame an den Server übertragen. Die Aushandlung des Schlüssels findet während der Meldung „Netzwerkverbindungen werden vorbereitet“ statt.

== Algorithmus ==

[[Datei:RC4.svg|mini|Die Nachschlagephase von RC4 bei einem Alphabet der Größe eines Bytes. Das Ausgabebyte wird von den Werten <math>S[i]</math> und <math>S[j]</math> ausgewählt, diese werden addiert modulo 256 gerechnet.]]
Kern des Verfahrens ist die sogenannte S-Box, eine zufällige Vertauschung oder Permutation des Standard-[[Alphabet (Mathematik)|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 <math>S[i] = i</math> 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 <math>k</math> der Länge <math>L</math> [[Byte]] berechnet:
<syntaxhighlight lang="text">
  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]
</syntaxhighlight>

Die anschließende Berechnung der Zufallsfolge erfolgt analog:
<syntaxhighlight lang="text">
  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]
</syntaxhighlight>

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 RC4 gelang Scott Fluhrer, Itsik Mantin und [[Adi Shamir]] im Jahr 2001.<ref>{{Literatur |Autor=Scott Fluhrer, Itsik Mantin, Adi Shamir |Titel=Weaknesses in the Key Scheduling Algorithm of RC4 |Sammelwerk=Selected Areas in Cryptography |Reihe=Lecture Notes in Computer Science |Band=2259 |Verlag=Springer |Datum=2001 |Seiten=1-24 |Online=http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps |DOI=10.1007/3-540-45537-X_1}}</ref>
[[RSA Security]] empfahl daraufhin, die ersten 256 Bytes (eine Runde) des Schlüsselstroms zu verwerfen.<ref>{{Internetquelle |url=http://www.rsa.com/rsalabs/node.asp?id=2009 |titel=RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4 |hrsg=RSA Security |sprache=en |offline=1 |archiv-url=https://web.archive.org/web/20110929141319/http://www.rsa.com/rsalabs/node.asp?id=2009 |archiv-datum=2011-09-29 |archiv-bot=2019-05-08 19:31:39 InternetArchiveBot |abruf=2012-09-10}}</ref>
Andreas Klein verbesserte daraufhin den Angriff, so dass er auch dann noch funktioniert.<ref>{{Literatur |Autor=Andreas Klein |Titel=Attacks on the RC4 stream cipher |Sammelwerk=Designs, Codes and Cryptography |Band=48 |Nummer=3 |Verlag=Springer |Datum=2008 |Seiten=269-286 |DOI=10.1007/s10623-008-9206-6}}</ref> 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 im von RC4 erzeugten Datenstrom nutzt,<ref>{{Literatur |Autor=Nadhem AlFardan, Daniel J. Bernstein, Kenneth G. Paterson, Bertram Poettering, Jacob C.N. Schuldt |Titel=On the Security of RC4 in TLS |Datum=2013-08 |ISBN=978-1-931971-03-4 |Online=https://www.usenix.org/conference/usenixsecurity13/technical-sessions/paper/alFardan}}</ref><ref>{{Literatur |Autor=Pouyan Sepehrdad, Serge Vaudenay, Martin Vuagnoux |Titel=Discovery and Exploitation of New Biases in RC4 |Sammelwerk=Lecture Notes in Computer Science |Band=6544 |Datum=2011 |Seiten=74–91 |Sprache=en |Online=http://link.springer.com/chapter/10.1007%2F978-3-642-19574-7_5 |DOI=10.1007/978-3-642-19574-7_5}}</ref> um eine Nachricht zu entziffern, die über mehrere RC4-verschlüsselte TLS-Verbindungen übertragen wird.<ref>{{Internetquelle |autor=Matthew Green |url=http://blog.cryptographyengineering.com/2013/03/attack-of-week-rc4-is-kind-of-broken-in.html |titel=Attack of the week: RC4 is kind of broken in TLS |werk=Cryptography Engineering |sprache=en |abruf=2013-03-12}}</ref><ref>{{Internetquelle |autor=Nadhem AlFardan, Dan Bernstein, Kenny Paterson, Bertram Poettering, Jacob Schuldt |url=http://www.isg.rhul.ac.uk/tls/ |titel=On the Security of RC4 in TLS |hrsg=Royal Holloway University of London |abruf=2013-03-13}}</ref>
2015 stellten Mathy Vanhoef und Frank Piessens einen praktisch durchführbaren Angriff vor, in dem [[Magic-Cookie]]s innerhalb von 52 Stunden entziffert werden konnten.<ref>Mathy Vanhoef, Frank Piessens: [http://www.rc4nomore.com/vanhoef-usenix2015.pdf ''All Your Biases Belong To Us: Breaking RC4 in WPA-TKIP and TLS''.] (PDF; 346&nbsp;kB) rc4nomore.com</ref>

[[Jacob Appelbaum]] ist der Ansicht, dass die [[National Security Agency|NSA]] die RC4-Verschlüsselung in [[Echtzeit]] [[Brechen (Kryptologie)|brechen]] könne. [[Bruce Schneier]] bezeichnete dies als eine plausible Vermutung.<ref>{{Internetquelle |url=https://www.heise.de/security/meldung/NSA-entschluesselt-Webserver-Daten-angeblich-in-Echtzeit-2041383.html |titel=NSA entschlüsselt Webserver-Daten angeblich in Echtzeit |hrsg=Heise Security |sprache=en |abruf=2013-11-07}}</ref>

Die [[Europäische Agentur für Netz- und Informationssicherheit]] empfiehlt, RC4 durch [[Rabbit (Algorithmus)|Rabbit]] oder [[SNOW|Snow 3G]] zu ersetzen.<ref>{{cite web | title=ENISA-Empfehlungen zu Krypto-Verfahren| url=https://www.heise.de/security/artikel/ENISA-Empfehlungen-zu-Krypto-Verfahren-2043356.html | publisher=Heise Security | accessdate=2013-11-18 | author=Michael Brenner}}</ref> Auch das [[Bundesamt für Sicherheit in der Informationstechnik]] rät von der Verwendung von RC4 ab. So setzt beispielsweise die [[Bundesrepublik Deutschland – Finanzagentur GmbH|Deutsche Finanzagentur]] RC4 seit November 2013 nicht mehr ein.<ref>{{Internetquelle |url=http://www.deutsche-finanzagentur.de/private-anleger/publikationen/aktuelle-meldungen/einzelnews/?tx_ttnews%5Btt_news%5D=10&cHash=96be0f72bff99b1135ae62ae2be1369c |titel=Wichtige Information für Internetbanking-Nutzer |hrsg=Deutsche Finanzagentur |datum=2013-11-19 |offline=1 |archiv-url=https://web.archive.org/web/20150107231802/http://www.deutsche-finanzagentur.de/private-anleger/publikationen/aktuelle-meldungen/einzelnews/?tx_ttnews%5Btt_news%5D=10&cHash=96be0f72bff99b1135ae62ae2be1369c |archiv-datum=2015-01-07 |archiv-bot=2019-05-08 19:31:39 InternetArchiveBot |abruf=2014-01-02}}</ref>

Die [[Internet Engineering Task Force]] verbietet mit dem <nowiki>RFC&nbsp;7465</nowiki> seit Februar 2015 den Einsatz von RC4, da in der Praxis die Zahl der Versuche, die zum Brechen der Verschlüsselung nötig wären, zu klein geworden wäre und sie keine ausreichend hohe Sicherheit für [[Transport Layer Security|TLS]]-Sessions mehr bieten könne.<ref>{{Internetquelle |autor=Jürgen Schmidt |url=https://www.heise.de/security/meldung/IETF-verbietet-RC4-Verschluesselung-in-TLS-2556520.html |titel=IETF verbietet RC4-Verschlüsselung in TLS |werk=Heise Security |hrsg=[[Heise online]] |datum=2015-02-20 |abruf=2015-07-08}}</ref><ref name="RFC7465" />

== Spritz ==
Am 27. Oktober 2014 stellten Ronald L. Rivest und Jacob C. N. Schuldt eine verbesserte Variante von RC4 namens Spritz vor.<ref name="rs14">{{Internetquelle |autor=Ronald L. Rivest, Jacob C. N. Schuldt |url=http://people.csail.mit.edu/rivest/pubs/RS14.pdf |titel=Spritz – a spongy RC4-like stream cipher and hash function |datum=2014-10-27 |format=PDF |abruf=2014-11-01}}</ref> Diese neue Variante ist auch Grundlage einer [[Kryptographische Hashfunktion|kryptographischen Hashfunktion]]. Allerdings wird die Performance von RC4 nicht erreicht. Der Algorithmus ist nur etwa halb so schnell wie RC4, und auch langsamer als die Blockchiffre [[Advanced Encryption Standard]] im [[Counter Mode]].<ref name="rs14" /> Die Schlüsselberechnung dauert länger als bei RC4.<ref>{{Internetquelle |url=https://www.schneier.com/blog/archives/2014/10/spritz_a_new_rc.html |titel=Spritz: A New RC4-Like Stream Cipher |hrsg=Bruce Schneier |datum=2014-10-27 |abruf=2014-11-01}}</ref>

Es folgt eine kurze Gegenüberstellung der Kernstücke von RC4 und SPRITZ.

RC4:
<syntaxhighlight lang="text">
  i = i + 1
  j = j + S[i]
  SWAP(S[i],S[j])
  z = S[S[i] + S[j]]
  Return z
</syntaxhighlight>

SPRITZ:
<syntaxhighlight lang="text">
  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
</syntaxhighlight>

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 ==
<!-- Bitte keine Implementierungen, die lassen sich leicht ergoogeln -->
* [http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html Überblick über Arbeiten bezüglich der Sicherheit von RC4] (englisch)
* [http://groups.google.com/groups?selm=sternCvKL4B.Hyy%40netcom.com Original-Post des damals noch geheimen RC4-Algorithmus im Usenet] (englisch)
* Scott Fluhrer, Itsik Mantin, [[Adi Shamir]]: [https://www.cs.cornell.edu/people/egs/615/rc4_ksaproc.pdf ''Weaknesses in the Key Scheduling Algorithm of RC4''.] (PDF; 297 kB) cs.cornell.edu (englisch).
* [http://tools.ietf.org/html/draft-kaukonen-cipher-arcfour-01 ''A Stream Cipher Encryption Algorithm “Arcfour”''.] [[Internet Engineering Task Force]] Network Working Group, 1997.
* {{RFC-Internet |RFC=4345 |Titel=Improved Arcfour Modes for the Secure Shell (SSH) Transport Layer Protocol |Datum=}}

== Einzelnachweise ==
<references responsive>
<ref name="RFC7465">
{{RFC-Internet |RFC=7465 |Titel=Prohibiting RC4 Cipher Suites |Datum=2015-02 |Autor=A. Popov}}
</ref>
</references>

[[Kategorie:Stromverschlüsselung]]
[[Kategorie:Abkürzung]]