Rabbit (Algorithmus)

Rabbit i​st eine Stromchiffre, d​ie einen Schlüssel m​it einer Länge v​on 128 Bit u​nd 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[1] 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.[2]

Der Algorithmus w​ird im RFC 4503 beschrieben, v​on Cryptico w​urde ein Patent für d​en Algorithmus angemeldet u​nd verlangte v​iele Jahre l​ang eine Lizenzgebühr für d​ie kommerzielle Nutzung d​er Verschlüsselung. Seit Oktober 2008 i​st die Software a​ls Public Domain Software lizenziert u​nd kann d​aher auch für kommerzielle Zwecke kostenfrei genutzt werden.[3]

Funktionalität

Verschlüsselung mit dem Rabbit-Algorithmus

Entschlüsselung mit dem Rabbit-Algorithmus

Der Rabbit-Algorithmus n​immt einen geheimen 128 bit-Schlüssel u​nd einen 64 bit-Initialisierungsvektor a​ls Eingabe u​nd erzeugt für j​ede Iteration e​inen Ausgabeblock v​on 128 pseudozufälligen Bits a​us einer Kombination d​er internen Statusbits. Die Ver- u​nd Entschlüsselung erfolgt d​urch eine Kontravalenz (bitweise XOR-Verknüpfung) d​er pseudozufälligen Daten m​it dem Klar- bzw. Verschlüsselungstext. Die Größe d​es internen Zustands beträgt 513 bit, aufgeteilt a​uf acht 32 bit-Zustandsvariablen, a​cht 32 bit-Zähler u​nd ein Übertragsbit.[2]

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 ${\displaystyle x_{j,0}}$ und den Anfangszählern ${\displaystyle c_{j,0}}$ besteht. Der Schlüssel ${\displaystyle K^{[127..0]}}$ wird in folgende acht Unterschlüssel unterteilt:[1]
${\displaystyle k_{0}=K^{[15..0]}}$, ${\displaystyle k_{1}=K^{[31..16]}}$, ${\displaystyle k_{2}=K^{[47..32]}}$, ${\displaystyle k_{3}=K^{[63..48]}}$, ${\displaystyle k_{4}=K^{[79..64]}}$, ${\displaystyle k_{5}=K^{[95..80]}}$, ${\displaystyle k_{6}=K^{[111..96]}}$ und ${\displaystyle k_{7}=K^{[127..112]}}$

Die Zustands- und Zählervariablen werden folgendermaßen initialisiert:
${\displaystyle 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
${\displaystyle 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:[1]
${\displaystyle 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 ${\displaystyle IV^{[63::0]}}$ notiert.[1]

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

• ${\displaystyle c_{1,4}=c_{1,4}\oplus (IV^{[63..48]}\diamond IV^{[31..16]})}$
• ${\displaystyle c_{3,4}=c_{3,4}\oplus (IV^{[47..32]}\diamond IV^{[15..0]})}$
• ${\displaystyle c_{5,4}=c_{5,4}\oplus (IV^{[63..48]}\diamond IV^{[31..16]})}$
• ${\displaystyle 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 ${\displaystyle 2^{64}}$möglichen Kombinationen des IV zu einem einzigartigen Keystream führen.

Next-state Function

Der Kern d​es Rabbit-Algorithmus i​st die Iteration d​es Systems, definiert d​urch folgenden Gleichungen:[1]

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

${\displaystyle 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 d​en Zähler werden folgende Konstanten benötigt, d​ie wie f​olgt definiert sind:[1]

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

Die Dynamik d​er Zähler i​st folgendermaßen definiert:

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

Das Übertragsbit ${\displaystyle \phi _{j,i+1}}$ ist dabei gemäß der folgenden Formel definiert:
${\displaystyle \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 j​eder Iteration werden 128 bit d​er Ausgabe w​ie folgt erzeugt:[1]

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

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

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

Ver- und Entschlüsselung

Anschließend erfolgt d​ie Ver- bzw. Entschlüsselung e​ines Textes/verschlüsselten Textes d​urch eine d​urch Kontravalenz m​it dem Ausgabeblock, d​en man n​ach Eingabe d​es 128 bit-Schlüssels u​nd des 64 bit-Initialvektors erhält.[1]

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 m​an diesen m​it dem z​u verschlüsselnden Text Sichere Nachricht (0x53696368657265204e6163687269636874) kontrarelevtiviert, s​o erhält m​an 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.[2]

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.[4]

Anwendung

Der Rabbit-Algorithmus findet u​nter anderem i​n der quelloffenen SSL/TLS-Programmbibliothek WolfSSL (ehemals CyaSSL) Anwendung, d​ie vor a​llem bei Embedded-Systemen z​um Einsatz kommt.[5]

Weblinks

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

Einzelnachweise

1. The Stream Cipher Rabbit. (PDF) Abgerufen am 20. Mai 2019 (englisch).
2. Rabbit:A New High-Performance Stream Cipher (Memento vom 11. Dezember 2013 im Internet Archive)
3. Rabbit becomes public domain (Memento vom 30. Juni 2009 im Internet Archive)
4. Light-weight crypto: Rabbit. Abgerufen am 20. Mai 2019 (englisch).
5. Ecrypt: Rabbit. Abgerufen am 20. Mai 2019 (englisch).