Rabbit (Algorithmus)

Rabbit ist eine Stromchiffre, die einen Schlüssel mit einer Länge von 128 Bit und einen 64 Bit Initialisierungsvektor verwendet.

Geschichte

Rabbit wurde 2003 von Martin Boesgaard, Mette Vesterager, Thomas Pedersen, Jesper Christiansen und Ove Scavenius bei der Firma Cryptico entwickelt und erstmals im Februar 2003 auf dem 10ten FSE Workshop vorgestellt. Das Design von Rabbit wurde von dem komplexen Verhalten realwertiger chaotischer Karten inspiriert. Chaotische Karten zeichnen sich in erster Linie durch eine exponentielle Empfindlichkeit gegenüber kleinen Störungen aus, so dass Iterationen solcher Karten zufällig und langfristig unvorhersehbar erscheinen.

Der Algorithmus wird im RFC 4503 beschrieben, von Cryptico wurde ein Patent für den Algorithmus angemeldet und verlangte viele Jahre lang eine Lizenzgebühr für die kommerzielle Nutzung der Verschlüsselung. Seit Oktober 2008 ist die Software als Public Domain Software lizenziert und kann daher auch für kommerzielle Zwecke kostenfrei genutzt werden.

Funktionalität

Verschlüsselung mit dem Rabbit-Algorithmus

Entschlüsselung mit dem Rabbit-Algorithmus

Der Rabbit-Algorithmus nimmt einen geheimen 128 bit-Schlüssel und einen 64 bit-Initialisierungsvektor als Eingabe und erzeugt für jede Iteration einen Ausgabeblock von 128 pseudozufälligen Bits aus einer Kombination der internen Statusbits. Die Ver- und Entschlüsselung erfolgt durch eine Kontravalenz (bitweise XOR-Verknüpfung) der pseudozufälligen Daten mit dem Klar- bzw. Verschlüsselungstext. Die Größe des internen Zustands beträgt 513 bit, aufgeteilt auf acht 32 bit-Zustandsvariablen, acht 32 bit-Zähler und ein Übertragsbit.

Das Key Vorbereitungsschema

Der Algorithmus wird durch die Expandierung des 128 bit-Schlüssels, sowohl in die 8 Zustandsvariablen, als auch in die 8 Zähler so initialisiert, dass eine Eins-zu-Eins Korrespondenz zwischen dem Schlüssel und den Anfangszustandsvariablen $x_{j,0}$ und den Anfangszählern $c_{j,0}$ besteht. Der Schlüssel $K^{[127..0]}$ wird in folgende acht Unterschlüssel unterteilt:
$k_{0}=K^{[15..0]}$, $k_{1}=K^{[31..16]}$, $k_{2}=K^{[47..32]}$, $k_{3}=K^{[63..48]}$, $k_{4}=K^{[79..64]}$, $k_{5}=K^{[95..80]}$, $k_{6}=K^{[111..96]}$ und $k_{7}=K^{[127..112]}$

Die Zustands- und Zählervariablen werden folgendermaßen initialisiert:
$x_{j,0}={\begin{cases}k_{(j+1)mod8}\diamond k_{j}&{\text{bei geraden }}j\\k_{(j+5)mod8}\diamond k_{(j+4)mod8}&{\text{bei ungeraden }}j\end{cases}}$
und
$c_{j,0}={\begin{cases}k_{(j+4)mod8}\diamond k_{(j+5)mod8}&{\text{bei geraden }}j\\k_{j}\diamond k_{(j+1)mod8}&{\text{bei ungeraden }}j\end{cases}}$

Anschließend wird, entsprechend dem nachfolgenden Zählsystem und der Next-State-Funktion, viermal iteriert, um die Korrelationen zwischen den Bits im Schlüssel und den Bits in den internen Zustandsvariablen zu verringern Abschließend werden die Zählerwerte entsprechend der folgenden Formal neu initialisiert, um eine Wiederherstellung des Schlüssels durch Umkehrung des Zählersystems zu verhindern:
$c_{j,4}=c_{j,4}\oplus x_{((j+4)mod8),4}$

IV Schema

Das IV-Setup Schema kommt zustande, indem der 64 bit-IV-Stream auf alle 256 bit des Counterstate XORed wird. Die 64 bit des IV werden im Folgenden als $IV^{[63::0]}$ notiert.

• $c_{0,4}=c_{0,4}\oplus IV^{[31..0]}$
• $c_{2,4}=c_{2,4}\oplus IV^{[63..32]}$
• $c_{4,4}=c_{4,4}\oplus IV^{[31..0]}$
• $c_{6,4}=c_{6,4}\oplus IV^{[63..32]}$

• $c_{1,4}=c_{1,4}\oplus (IV^{[63..48]}\diamond IV^{[31..16]})$
• $c_{3,4}=c_{3,4}\oplus (IV^{[47..32]}\diamond IV^{[15..0]})$
• $c_{5,4}=c_{5,4}\oplus (IV^{[63..48]}\diamond IV^{[31..16]})$
• $c_{7,4}=c_{7,4}\oplus (IV^{[47..32]}\diamond IV^{[15..0]})$

Das System wird dann viermal iteriert, um alle Zustandsbits nichtlinear von allen IV-Bits abhängig zu machen. Die Modifikation des Zählers durch die IV garantiert, dass alle $2^{64}$möglichen Kombinationen des IV zu einem einzigartigen Keystream führen.

Next-state Function

Der Kern des Rabbit-Algorithmus ist die Iteration des Systems, definiert durch folgenden Gleichungen:

• $x_{0,i+1}=g_{0,i}+(g_{7,i}\ll 16)+(g_{6,i}\ll 16)$
• $x_{1,i+1}=g_{1,i}+(g_{0,i}\ll 8)+g_{7,i}$
• $x_{2,i+1}=g_{2,i}+(g_{1,i}\ll 16)+(g_{0,i}\ll 16)$
• $x_{3,i+1}=g_{3,i}+(g_{2,i}\ll 8)+g_{1,i}$
• $x_{4,i+1}=g_{4,i}+(g_{3,i}\ll 16)+(g_{2,i}\ll 16)$
• $x_{5,i+1}=g_{5,i}+(g_{4,i}\ll 8)+g_{3,i}$
• $x_{6,i+1}=g_{6,i}+(g_{5,i}\ll 16)+(g_{4,i}\ll 16)$
• $x_{7,i+1}=g_{7,i}+(g_{6,i}\ll 8)+g_{5,i}$

$g_{j,i}=((x_{j,i}+c_{j,i})^{2}\oplus ((x_{j,i}+c_{j,i})^{2}\gg 32))mod2^{32}$

Zählsystem

Für den Zähler werden folgende Konstanten benötigt, die wie folgt definiert sind:

• $a_{0}=0x4D34D34D$
• $a_{1}=0xD34D34D3$
• $a_{2}=0x34D34D34$
• $a_{3}=0x4D34D34D$
• $a_{4}=0xD34D34D3$
• $a_{5}=0x34D34D34$
• $a_{6}=0x4D34D34D$
• $a_{7}=0xD34D34D3$

Die Dynamik der Zähler ist folgendermaßen definiert:

• $c_{0,i+1}=c_{0,i}+a_{0}+\phi _{7,i}mod2^{32}$
• $c_{1,i+1}=c_{1,i}+a_{1}+\phi _{0,i+1}mod2^{32}$
• $c_{2,i+1}=c_{2,i}+a_{2}+\phi _{1,i+1}mod2^{32}$
• $c_{3,i+1}=c_{3,i}+a_{3}+\phi _{2,i+1}mod2^{32}$
• $c_{4,i+1}=c_{4,i}+a_{4}+\phi _{3,i+1}mod2^{32}$
• $c_{5,i+1}=c_{5,i}+a_{5}+\phi _{4,i+1}mod2^{32}$
• $c_{6,i+1}=c_{6,i}+a_{6}+\phi _{5,i+1}mod2^{32}$

Das Übertragsbit $\phi _{j,i+1}$ ist dabei gemäß der folgenden Formel definiert:
$\phi _{j,i+1}={\begin{cases}1&{\text{falls }}c_{0,i}+a_{0}+\phi _{7,i}\geq 2^{32}\wedge j=0\\1&{\text{falls }}c_{j,i}+a_{j}+\phi _{j-1,i+1}\geq 2^{32}\wedge j>0\\0&{\text{andernfalls}}\end{cases}}$

Extraktion

Nach jeder Iteration werden 128 bit der Ausgabe wie folgt erzeugt:

• $s_{i}^{[15..0]}=x_{0,i}^{[15..0]}\oplus x_{5,i}^{[31..16]}$
• $s_{i}^{[47..32]}=x_{2,i}^{[15..0]}\oplus x_{7,i}^{[31..16]}$
• $s_{i}^{[79..64]}=x_{4,i}^{[15..0]}\oplus x_{1,i}^{[31..16]}$
• $s_{i}^{[111..96]}=x_{6,i}^{[15..0]}\oplus x_{3,i}^{[31..16]}$

• $s_{i}^{[31..16]}=x_{0,i}^{[31..16]}\oplus x_{3,i}^{[15..0]}$
• $s_{i}^{[63..48]}=x_{2,i}^{[31..16]}\oplus x_{5,i}^{[15..0]}$
• $s_{i}^{[95..80]}=x_{4,i}^{[31..16]}\oplus x_{7,i}^{[15..0]}$
• $s_{i}^{[127..112]}=x_{6,i}^{[31..16]}\oplus x_{1,i}^{[15..0]}$

wobei $s_{i}$ der 128 bit-Ausgabeblock nach der Iteration $i$ ist.

Ver- und Entschlüsselung

Anschließend erfolgt die Ver- bzw. Entschlüsselung eines Textes/verschlüsselten Textes durch eine durch Kontravalenz mit dem Ausgabeblock, den man nach Eingabe des 128 bit-Schlüssels und des 64 bit-Initialvektors erhält.

Beispiel

Um einen Text mithilfe des Rabbit-Algorithmus zu verschlüsseln, benötigt man lediglich einen Schlüssel und einen Initialisierungsvektor. Mit dem Schlüssel Wikipedia (0x57696b697065646961) und dem Initialvektor 0x123123 erhält man den Ausgabeblock 0x9c677286866aad38f8e9b660f5411814.

Wenn man diesen mit dem zu verschlüsselnden Text Sichere Nachricht (0x53696368657265204e6163687269636874) kontrarelevtiviert, so erhält man die folgenden verschlüsselten Text a2115ff62ad536899a8b16d22f47746336.

Geschwindigkeit

Die Chiffre wurde für eine hohe Softwareleistung entwickelt. Bei einer vollständig optimierten Implementierung erreicht der Rabbit-Algorithmus eine Verschlüsselungsgeschwindigkeit von 3,7 Taktzyklen pro Byte auf einem Intel Pentium III und eine Verschlüsselungsgeschwindigkeit von 10,5 Taktzyklen pro Byte auf einem ARM7 Prozessor.

Sicherheit

Ein 128-Bit-Schlüssel macht es robust gegen Brute-Force-Angriffe. Es ist auch ziemlich einfach zu implementieren und erfordert eine minimale Speicherung von Zuständen. Im Vergleich zum Advanced Encryption Standard für Geräte mit geringer Leistung ergeben sich in der Schnelligkeit und der Robustheit Vorteile für den Rabbit-Algorithmus. Bislang wurden keine Schwachstellen in der Rabbit-Verschlüsselung gefunden.

Anwendung

Der Rabbit-Algorithmus findet unter anderem in der quelloffenen SSL/TLS-Programmbibliothek WolfSSL (ehemals CyaSSL) Anwendung, die vor allem bei Embedded-Systemen zum Einsatz kommt.

Weblinks

• https://www.ecrypt.eu.org/stream/e2-rabbit.html
• ecrypt.eu.org