RC4 Verschlüsselung: Grundlagen

RC4 wurde bereits in früheren Posts erwähnt, insbesondere beim ITS-Tagebuch im Zusammenhang mit WEP. Neulich gab es eine weitere Attacke auf RC4 speziell für das beim HTTPS-Verkehr eingesetzte TLS Protokoll. Grund genug, den Schwachstellen von RC4 auf den Zahn zu fühlen!

Heute werden wir die Grundlagen zu RC4 lernen: Was ist RC4? Außerdem setzen wir den RC4 Algorithmus in C# um (sorry Leute, mit C bin ich noch nicht so weit). Keine Panik: Es sind weder Kryptographie-Kenntnisse noch Programmierer-Wissen erforderlich.

RC4 Crypto Beispiel

Beispiel für die RC4-Chiffre: Der ASCII-String „TacticalCode“ wurde mit dem Schlüssel „g3he1m“ verschlüsselt. Der Keystream ergibt sich aus der S-Box, die Werte sind hexadezimal.

Die Geschichte von RC4

Siehe Wikipedia. Kurz gesagt: RC4 wurde von Ron Rivest für RSA Security entwickelt. Der Algorithmus wurde zunächst geheim gehalten, was heute nicht üblich ist (security through obscurity). Durch ein anonymes Posting im Usenet konnte der Algorithmus allerdings rekonstruiert werden.
RC4 ist auch bekannt als ARC4 oder ARCFOUR. Es ist eine Stromchiffre, der Plaintext kann also byte-weise verschlüsselt werden.

Funktionsweise

Die Funktionsweise ist schon gut online Dokumentiert, allerdings werde ich es Schritt für Schritt erklären und wir werden alles anhand eines kleinen Programms nachvollziehen können.
Grundsätzlich besteht der Algorithmus aus 2 Komponenten:

  • Key-Scheduling Algorithm (KSA): S-Box wird dynamisch erzeugt
  • Pseudo-Random Generation Algorithm (PRGA): Verschlüsselung

Zunächst wird eine S-Box erzeugt. Mithilfe dieser S-Box findet eine Substitution statt, es werden also Werte ausgetauscht. Diese S-Box ergibt sich allein aus dem Schlüssel (Länge und Inhalt). Dies wird noch näher erläutert, wenn wir unser Testprogramm durchlaufen.

Ist diese S-Box nun erzeugt, wird die Verschlüsselung getätigt. Grob erklärt: Jedes Zeichen des Plaintextes wird mit einem Wert XOR-Verknüpft. Dieser Wert ergibt sich aus 2 Einträgen der S-Box, welche Addiert den Index des werden (und vertauscht, was zusätzliche pseudo-Zufälligkeit erzeugt).
Zu abstrakt? Hier ist der Code:

RC4 in C#

Als Grundlage für den Algorithmus habe ich das RC4 Beispiel von dotnet-snippets.de genommen. Die Syntax von C# ist allgemein leicht verständlich (und mit Kommentaren versehen), so dass der Quelltext auch als Pseudo-Code zur Veranschaulichung dient:

public void RC4(ref Byte[] bytes, Byte[] key)
{
	Byte[] s = new Byte[256];   //s-box
	Byte[] k = new Byte[256];   //key
	Byte temp;                  //substitution buffer
	int i, j;                   //counters

	//S-Box & Key (KSA)
	//1 Iteration for each S-Box & key element
	for (i = 0; i < 256; i++)
	{
		s[i] = (Byte)i;                     //Set Values to 0...255
		k[i] = key[i % key.GetLength(0)];   //Fill k with key, append if neccesary
	}

	j = 0;
	//1 Iteration for each S-Box element
	for (i = 0; i < 256; i++)
	{
		//Calculate j depending on the key
		j = (j + s[i] + k[i]) % 256;
		//Swap s[i] and s[j]
		temp = s[i];
		s[i] = s[j];
		s[j] = temp;
	}

	//Pseudo Random Generating Algorithm (PRGA)
	i = j = 0;
	//1 Iteration for each byte of the plaintext
	for (int x = 0; x < bytes.GetLength(0); x++)
	{
		i = (i + 1) % 256;      //Count-up i 0...255 to match S-Box index
		j = (j + s[i]) % 256;   //Calculate j depending on S-Box, match index
		temp = s[i];            //Swap s[i] and s[j]
		s[i] = s[j];
		s[j] = temp;
		int t = (s[i] + s[j]) % 256;    //s[i]+s[j] as index for an S-Box element
		bytes[x] ^= s[t];               //XOR plaintext-byte with S-Box element
	}
}

Erklärung:
Als Funktionsparameter haben wir 2 Byte-Arrays. Genauer gesagt: Ein Verweis auf ein Array, welches den Plaintext enthält (ref Byte[] bytes), und ein Array, welches unseren Schlüssel enthält (Byte[] key).

In den Zeilen 2-6 werden (lokale) Variablen angelegt: Ein Byte-Array für die S-Box, ein Byte-Array für den Schlüssel, ein temporäres byte (Zwischenspeicher für Substitutionen) und 2 Zähler: i und j. Daraus ergibt sich eine weitere Eigenschaft von RC4: Der Schlüssel kann maximal 256 Byte lang sein, also 2048bit.
In der ersten For-Schleife werden 2 Sachen erledigt:

  • Die S-Box wird mit den Werten 0…255 aufgefüllt (s[0]=0, s[1]=1 usw…)
  • Das Key-Array wird mit dem Schlüssel aufgefüllt

Der Schlüssel muss aber nicht genau 256 Bytes lang sein. Ist der Schlüssel kleiner, wird er einfach so lange wiederholt, bis 256 Bytes voll sind. Im Programm erreicht man das einfach mit i mod Keylänge: Die Variable i wird bis 255 hochgezählt, um alle Indizes des Key-Arrays anzusprechen. Ist der Schlüssel kürzer, muss man am Ende des Schlüssels wieder von Vorn beginnen. Wendet man auf i jetzt den Modulo der Länge vom Schlüssel an, geschieht folgendes:

Der Index für das Key-Array wird bis zur Länge (Größe, Anzahl der Elemente) des Key-Arrays minus 1 hochgezählt. Danach steht der Index wieder auf 0.
Ein Fall von schwarzer Computer-Magie? Nein, rechnet es selbst nach:

Zählt i bis 10, nehmt als Schlüssellänge 3. i mod 3 = 0; 1; 2; 0; 1; 2; 0; 1; 2; 0; (0%3=0; 1%3=1; 2%3=2; 3%3=0; 4%3=1;…) – Dies sind genau die Indizes, die wir für das Key-Array brauchen, da der Index mit 0 beginnt. Merken, dasselbe Prinzip wird gleich noch einmal angewandt.
Sind Arrays für Schlüssel (k) und S-Box (s) aufgefüllt, kann die S-Box anhand des Schlüssel-Arrays k erzeugt werden. Die zweite Zählervariable j wird genullt.

In der zweiten For-Schleife geschieht folgendes: Es werden 256 Iterationen durchlaufen, eine für jedes Element der S-Box. Für Jedes Element wird ein j bestimmt durch j = (j + s[i] + k[i])%256. Der Wert für j ist abhängig vom Schlüssel k, daher wird die S-Box auch als dynamisch bezeichnet. j + s[i] + k[i] soll eine möglichst große „Verwürfelung“ (Permutation) hervorrufen, was es unmöglich machen soll, Rüchschlüsse vom Ciphertext auf den Plaintext zu schließen. So viel sei verraten: hier befindet sich eine Schwachstelle im RC4-Algorithmus. Der Modulo 256 bewirkt wieder, dass j nicht größer sein kann, als die Anzahl der Elemente im Array.

Nun werden s[i] und s[j] vertauscht. Nach 256 Durchläufen ist die S-Box fertig generiert, das Key-Scheduling ist abgeschlossen. Die S-Box ist für jeden Schlüssel statisch, für gleiche Schlüssel wird sich also immer exakt dieselbe S-Box ergeben.

Nun kann der Plaintext mithilfe der S-Box verschlüsselt werden (PRGA):
Die Zähler i und j werden wieder = 0 gesetzt, dieses mal wird eine For-Schleife für jedes Element im Plaintext-Array (bytes) durchlaufen: i wird bei jeder Iteration um 1 erhöht, dabei wird wieder der Modulo 256 genommen. Ist der Plaintext größer als 256 bytes, wird i also bis 255 hochgezählt und beginnt danach wieder bei 0. Der Inhalt des Key-Arrays k wird also so lange hintereinander angefügt, dass sich die gleiche Länge wie das Plaintext-Array ergibt. Diese Aneinanderreihung wird Keystream genannt.

Es wird wieder ein j berechnet durch j = (j + s[i]) % 256. j Ist also wieder von der S-Box abhängig. Anschließend werden das i-te und j-te Element der S-Box vertauscht. Dadurch ist gewährleistet, dass jedes Element der S-Box alle 256 Durchläufe mindestens einmal vertauscht wird. Das ist wichtig, um Rückschlüsse auf den Schlüssel zu vermeiden. (s[i] + s[j]) % 256 ergibt einen Index für die S-Box. Der Wert an dieser Stelle wird nun mit dem x-ten Wert des Plaintextes durch ein XOR verknüpft. x wird in der For-Schleife hochgezählt, also wird ein Byte nach dem anderen verschlüsselt.

RC4 Algorithmus Schaubild

RC4 PRGA: s[i]+s[j] ergeben den Intex für das Element der S-Box, welches ein Plaintext-Byte durch XOR-Verknüpfung verschlüsselt.

Wer einen C# Debugger installiert hat, durchläuft das Programm am besten schrittweise. Ein Tool dazu ist gerade in Arbeit. Dies soll dabei helfen, den Algorithmus besser zu verstehen. Sobald ich das Programm (in C#, also .NET) fertig habe, werde ich einen weiteren Post dazu schreiben. Eine Version in C ist ebenfalls geplant, lässt aber noch auf sich warten.

Fazit

Ich hoffe, ich konnte den Algorithmus anschaulich erklären. Falls noch Fragen offen sind, bitte die Kommentare nutzen! Diese Grundlagen sind wichtig zur Verständnis der nächsten Posts, welche die FMS-Attacke auf RC4, Andreas Kleins entdeckte Schwachstellen und einiges mehr erläutern.

Disclamer: Die hier vermittelten Kenntnisse sind selbst erlernt. Es gibt keine 100% Garantie, dass die Fakten richtig sind, aber ich denke, selbst wenn Fehler vorhanden sind, sind diese zu vernachlässigen. Ist dies nicht der Fall, und selbst wenn es vernachlässigbare Fehler sind, bitte ich ausdrücklich um Korrekturhinweise! Auch ich würde gerne noch mehr lernen, also immer her mit Kritiken.

MfG
Damon Dransfeld

Dieser Eintrag wurde veröffentlicht in Kryptographie
Bookmarken: Permanent-Link Schreibe einen Kommentar oder hinterlasse einen Trackback: Trackback-URL.

Ein Kommentar

  1. Peppy
    Erstellt am 16. August 2013 um 21:28 | Permalink zum Kommentar

    Schön gemachtes Tutorial, wirklich nice.
    Ist den die C-version schon fertig und post bereit ?
    Wäre Top !! greeez and keep going ;)

Achtung: Wordpress interpretiert bestimmte Zeichenfolgen als Markup und verändert diese. Nutzt für Programmcode lieber Gist oder PasteBin-Services und verlinkt die Code-Schnipsel.

Schreibe eine Antwort an Peppy

Ihre E-Mail wird niemals veröffentlicht oder verteilt. Benötigte Felder sind mit * markiert

*
*

Du kannst diese HTML Tags und Attribute verwenden: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>