Benutzer:DieserGorilla/Rabbit (Algorithmus)

Überarbeiten

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, and Ove Scavenius und bei der Firma Cryptico entwickelt und wurde 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 kommerziell 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 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 einem Ü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-zuEins 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^{[15..0]}$, $K^{[31..16]}$, $K^{[47..32]}$, $K^{[63..48]}$, $K^{[79..64]}$, $K^{[95..80]}$, $K^{[111..96]}$ und $K^{[127..112]}$

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

Das wird, entsprechend der folgenden 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+4mod8),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 Kombinantionen des IV zu einem einzigartigen Keystreams 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 Übertragbit $\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ällt.

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üsselden Text Sichere Nachricht (0x53696368657265204e6163687269636874) kontrarelevtiviert, so erhällt 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, auf der ARM7 basierenden Prozesssor.

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 vorallem bei Embedded-Systemen zum Einsatz kommt.

Weblinks

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

Einzelnachweise

Kategorie:Stromverschlüsselung