RC5
# RC5

RC5 (Rivest Cipher 5) ist eine 1994 von Ronald Rivest entworfene symmetrische Blockverschlüsselung. Das bedeutet, dass sowohl für das Verschlüsseln wie das Entschlüsseln der gleiche Schlüssel benutzt wird. Sie gehört zur Klasse der Feistelchiffren. Die Daten werden zunächst in Blöcke gleicher Größe aufgeteilt und über wiederholte Anwendung einfacher Operationen – sogenannter „Primitive“ – ver- oder entschlüsselt. Die Blockgröße, die Länge des Schlüssels und die Anzahl der Wiederholungen – die „Runden“ – sind nicht durch den Algorithmus vorgegeben und werden als Parameter vor der Verschlüsselung festgelegt.

Das Ziel beim Entwurf von RC5 war eine einfache und schnelle Chiffre. Sie baut auf datenabhängigen Rotationen auf, deren Eignung als Primitiv zum Entwicklungszeitpunkt noch weitgehend unerforscht war.

Anders als viele andere Blockchiffren verwendet RC5 keine S-Boxen, um das von Claude Shannon 1949 als „Konfusion“ bezeichnete und für sicheren Betrieb wichtige Verwischen statistischer Zusammenhänge zwischen Klartext, Schlüssel und Chiffretext zu erreichen. Eine S-Box sorgt für starke Konfusion, da man weitgehend frei wählen kann, wie zum Beispiel eine $b\times b$-S-Box die $2^{b}$ möglichen Werte der $b$ eingegebenen Bits auf die $2^{b}$ möglichen Ausgangswerte abbildet. S-Boxen erfordern in der praktischen Implementierung aber zusätzlichen Speicher und auch einen gewissen Rechenaufwand, da man ein Datenwort erst in genügend kleine Teile teilen muss, die der S-Box eingegeben werden, denn ein ganzes Wort von 16 oder mehr Bit ist dafür zu groß. Danach muss man die Ergebnisse auch wieder zu einem Wort zusammensetzen. Der Verzicht auf S-Boxen macht RC5 sehr einfach und schnell und insbesondere auch für den Einsatz in ressourcenarmen Bereichen – etwa digitaler Hardware mit begrenzter Chipfläche – interessant.

Eine konkrete Softwareimplementation, die verschiedene Betriebsmodi zur Verkettung von Blöcken bietet – nämlich CBC, CBC-Pad und CTS – wird im Standard RFC 2040 spezifiziert.

RC5 diente als Basis für die Verschlüsselung RC6, die zur Wahl des Advanced Encryption Standard kandidierte.

In den Vereinigten Staaten hielt das Unternehmen RSA Security bis 2015 ein Patent auf RC5.

## Beschreibung

RC5 besitzt variable Blockgrößen (32, 64 oder 128 Bits), Schlüssellängen (0–2040 Bits) und Rundenzahlen (0–255). Eine spezifische Wahl dieser Parameter wird üblicherweise mit „RC5-w/r/b“ bezeichnet – w ist die Länge eines Wortes in Bit (ein Block besteht aus zwei Wörtern), r die Anzahl der Runden und b die Länge des Schlüssels in Bytes. Rivest empfahl ursprünglich RC5-32/12/16 und RC5-64/16/16 für 64-Bit-Architekturen.

RC5 besteht aus drei Komponenten: Verschlüsselung, Entschlüsselung und Schlüsselexpansion. Die in Ver- und Entschlüsselung verwendeten kryptographischen Primitive des Verfahrens sind:

* die Addition zweier Wörter modulo $2^{w}$
* die bitweise XOR-Verknüpfung zweier Wörter
* die Rotation eines Wortes um b Bitpositionen, wobei b durch die $\log _{2}w$ niederwertigsten Bits des anderen Wortes gegeben wird

Die Primitive operieren auf Wörtern von w Bit, die jeweils einen Halbblock bilden. Die Sicherheit des Algorithmus hängt maßgeblich von der Verwendung der Rotation ab, die die einzige nichtlineare Operation des Verfahrens ist. Auch der Nachfolgealgorithmus RC6 und in Teilen der AES-Kandidat MARS basieren auf datenabhängigen Rotationen.

Die Primitive werden im Folgenden mit A+B für die Addition, A⊕B für bitweise XOR-Verknüpfung und A⋘B bzw. A⋙B für die Links-/Rechtsrotationen des Halbblocks A um (B mod w) Bitstellen bezeichnet.

### Schlüsselexpansion

Mit der Schlüsselexpansion werden aus dem geheimen Schlüssel die Rundenschlüssel $S_0,$ …, $S_{2r+1}$ – wobei $S_0$ und $S_1$ zum Key Whitening verwendet werden – generiert. Das System aus Rundenschlüsseln wird auch als erweiterte Schlüsseltabelle bezeichnet. Um dies zu erreichen wird der geheime Schlüssel zunächst in Halbblöcke $L_i$ aufgespalten, bei Bedarf wird mit Nullen aufgefüllt. Anschließend werden die Rundenschlüssel $S_k$ mittels Konstanten auf einen festen Anfangszustand initialisiert:

| Blockgröße (Bits) | P (hexadezimal) | Q (hexadezimal) |
| - | - | - |
| 032 | B7E1 | 9E37 |
| 064 | B7E1 5163 | 9E37 79B9 |
| 128 | B7E1 5162 8AED 2A6B | 9E37 79B9 7F4A 7C15 |

    $S_{0}\leftarrow P$
    $\mathbf {for} \;k\leftarrow 1\;\mathbf {to} \;2r+1\;\mathbf {do}$:
       $S_{k}\leftarrow S_{k-1}+Q$

P und Q sind hierbei ungerade Ganzzahlen, die mit der eulerschen Zahl e und dem goldenen Schnitt Φ in Abhängigkeit von der verwendeten Blockgröße generiert werden.

Letztlich werden die Halbblöcke $L_i$ und $S_k$ in drei Durchläufen miteinander vermischt:

    $k\leftarrow i\leftarrow 0$
    $A\leftarrow B\leftarrow 0$
    $\mathbf {do} \;3\cdot \max {\big2(r+1),\lceil b/(w/8)\rceil {\big )}\;\mathbf {times}$:
       $A\leftarrow S_{k}\leftarrow (S_{k}+A+B)\lll 3$
       $B\leftarrow L_{i}\leftarrow (L_{i}+A+B)\lll (A+B)$
       $k\leftarrow (k+1)\mod {{\big2(r+1){\big )}}$
       $i\leftarrow (i+1)\mod {{\big\lceil b/(w/8)\rceil {\big )}}$

### Ver- und Entschlüsselung

Gegeben seien ein Klartextblock in Little-Endian-Darstellung, der aus den Halbblöcken A, B besteht und die Rundenschlüssel $S_0,…,$ $S_{2r+1}.$ Der Block wird verschlüsselt durch:

    $A\leftarrow A+S_{0}$
    $B\leftarrow B+S_{1}$
    $\mathbf {for} \;k\leftarrow 1\;\mathbf {to} \;r\;\mathbf {do}$:
       $A\leftarrow {\big(A\oplus B)\lll B{\big )}+S_{2k}$
       $B\leftarrow {\big(B\oplus A)\lll A{\big )}+S_{2k+1}$

Hierbei entspricht jede Halbrunde einer Runde einer Feistelchiffre. Die Entschlüsselung eines entsprechenden Chiffretextblocks aus den Halbblöcken A, B verläuft analog:

    $\mathbf {for} \;k\leftarrow r\;\mathbf {downto} \;1\;\mathbf {do}$:
       $B\leftarrow {\big(B-S_{2k+1})\ggg A{\big )}\oplus A$
       $A\leftarrow {\big(A-S_{2k})\ggg B{\big )}\oplus B$
    $B\leftarrow B-S_{1}$
    $A\leftarrow A-S_{0}$

## Kryptoanalyse

Zu Kryptoanalysezwecken wird auch eine als RC5⊕ bezeichnete Variante verwendet, bei der die modulare Addition der Halbblöcke vollständig gegen bitweises XOR ausgetauscht wird. Diese Variante ist – durch einen unter XOR bestehenden Zusammenhang zwischen Bits der Chiffretexte und Bits der mit dem Klartext verknüpften Rundenschlüssel – kryptographisch schwächer und eignet sich vorwiegend als Vereinfachung zur Analyse der datenabhängigen Rotationen.

Auch die analoge Variante RC5P, die ausschließlich Additionen verwendet, hat sich als kryptographisch schwächer herausgestellt. John Kelsey, Bruce Schneier und David Wagner zeigten 1999 mit einem neuartigen Angriff – von ihnen als „mod n“-Kryptanalyse bezeichnet – dass Chiffren, die nur auf Additionen und Rotationen basieren, generell gebrochen werden können. Der Angriff basiert dabei auf Korrelationen zwischen Klartext und Chiffretext der letzten Runde bei Betrachtung modulo n. Durch geeignete Wahl von n kann ein Angreifer auf diesem Wege Informationen über den letzten Rundenschlüssel erhalten. Die Autoren schlossen aus ihren Ergebnissen, dass die Vermischung der Operationen „+“ und „⊕“ für die Sicherheit von RC5 essentiell ist.

### Chosen-Plaintext-Angriffe

Kaliski und Yin von den RSA Laboratories zeigten 1995, dass für differentielle Kryptanalyse gegen RC5-32/9 $2^{45}$ Paare gewählter Klartexte und zugehöriger Chiffretexte benötigt werden, was etwa der Stärke von 16-Runden-DES entspricht. Für RC5-32/12 werden hingegen $2^{62}$ solcher Paare benötigt. Der Angriff rekonstruiert hierbei Bits von $L_{2r},$ woraus Informationen über $S_{2r+1}$ hergeleitet werden können. Sobald $S_{2r+1}$ bekannt ist, kann eine einfachere Analyse auf RC5 mit verringerter Rundenzahl angewandt werden. Die gewählte Schlüssellänge ist für diesen Angriff bedeutungslos.

1996 verbesserten Knudsen und Meier den differentiellen Angriff und zeigten zudem die Existenz einer Vielzahl schwacher Schlüssel. Diese entstehen durch die Struktur der Chiffre und sind unabhängig von der Wahl des Expansionsalgorithmus. Der Angriff von Knudsen und Meier nutzt Datenabhängigkeit der zyklischen Rotationen, indem solche Klartexte identifiziert werden, bei denen innerhalb der ersten Runden nicht rotiert wird. Auf diese Weise wird die Anzahl der gewählten Klartextpaare auf $2^{39}$ für RC5-32/9 und bis zu $2^{54}$ für RC5-32/12 gesenkt. Für RC5-64 sind – aus akademischer Sicht – die ursprünglich von Rivest vorgeschlagenen 16 Runden mit $2^{83}$ benötigten, gewählten Klartextpaaren nicht hinreichend sicher gegen differentielle Kryptanalyse.

Eine weitere Verbesserung der differentiellen Kryptanalyse wurde 1998 von Buryukov und Kushilevitz des Israelischen Institute of Technology in Haifa publiziert. Dieser Angriff, bei dem sogenannte „gute“ Paare aus gewählten Klar- und Chiffretexte über Hamming-Gewichte der Rundendifferenzen gewählt werden, reduziert die Anzahl der benötigten gewählten Klartextpaare für RC5-32/12 auf $2^{44}.$ Die Autoren schlossen daraus, dass differentielle Angriffe gegen RC5-32/12/16 mit $2^{38}$ und gegen RC5-64/16/16 mit $2^{63}$ gewählten Klartextpaaren möglich seien.

Im Zuge der Wahl des neuen Advanced Encryption Standards reichten 2000 Takeshi Shimoyama (Fujitsu), Kiyofumi Takeuchi und Juri Hayakawa (Chuo University) eine modifizierte und auf RC5 adaptierte Variante eines 1999 von Knudsen und Meier vorgestellten Angriffs auf RC6 ein. Dieser, auf dem χ²-Test aufbauende Korrelationsangriff rekonstruiert den letzten Rundenschlüssel für RC5 mit 17 Halbrunden mittels $2^{54}$ gewählten Klartexten mit einer Erfolgswahrscheinlichkeit von 80 %. Ebenso zeigten die Autoren, dass der Angriff für etwa einen in $2^{20}$ Schlüsseln mit gleicher Wahrscheinlichkeit auch RC5 mit voller Rundenzahl bricht.

### Known-Plaintext-Angriffe

Kaliski und Yin zeigten, dass eine Rekonstruktion der erweiterten Schlüsseltabelle mittels linearer Approximationen bereits für fünf Runden $2^{47}$ bekannte Klartexte erfordert und somit gegen lineare Kryptanalyse die Stärke von DES erreicht. Bei mehr als sechs Runden ist der von diesen Autoren beschriebene Angriff sinnlos. Nach Ali Aydın Selçuk der University of Maryland beruht dieser Angriff jedoch auf falschen Annahmen und ist somit fehlerhaft.

1997 publizierte Howard M. Keys RC5-32/12/16 die Existenz linear schwacher Schlüssel. Er fand $2^{28}$ Schlüssel, bei denen sich eine lineare Kryptanalyse bereits mit $2^{17}$ bekannten Klartexten durchführen lässt. Weiterhin existieren $2^{68}$ Schlüssel, für die die Chiffre theoretisch mit $2^{57}$ Klartexten gebrochen werden kann. Die Schlüssel hängen dabei wesentlich vom verwendeten Expansionsalgorithmus ab.

Ein 1999 von Borst, Preneel und Vandewalle publizierter, auf linearen Approximationen aufbauender und aufgrund seines geringen Speicherbedarfs praktisch implementierbarer Angriff bricht RC5-32/r mit $2^{4+6r}$ und RC5-64/r mit $2^{3+8r}$ bekannten Klartexten mit 90-prozentiger Erfolgswahrscheinlichkeit. Miyaji, Nonaka und Takii bezeichneten diese Ergebnisse 2002 als „highly optimistic“ (zu deutsch: „hochgradig optimistisch“) und stellten ihrerseits einen auf dem χ²-Test aufbauenden Korrelationsangriff vor, mit dem eine 90-prozentige Erfolgswahrscheinlichkeit gegen RC5-32/r mit $2^{6,14r+2,27}$ bekannten Klartexten möglich sei.

### Andere Ansätze

Ein 1999 von Handschuh und Heys vorgestellter Angriff nutzt die benötigte Zeit für die bei der Verschlüsselung durchgeführten datenabhängigen Rotationen. Während Rivest annahm, moderne Prozessoren würden eine Rotation in Zeit O(1) ausführen, ist dies nicht notwendig etwa für eingebettete Systeme der Fall. Die auf solchen Plattformen auftretenden Zeitunterschiede erlauben Rückschlüsse über die Anzahl der durchgeführten Rotationen und ermöglichen – bei vollständiger Information – eine Rekonstruktion der erweiterten Schlüsseltabelle für RC5-32/12/16 mittels $2^{20}$ Chiffretexten mit Zeitbedarf $Ω(2^{28})$ und $O(2^{40}).$ Der Angriff kann jedoch implementationsbasiert durch Dummy-Rotationen vermieden werden.

### Angriffe in der Praxis

Die Firma RSA Security bot im Rahmen ihrer von 1997 bis zum Mai 2007 durchgeführten Secret-Key Challenge – einem öffentlichen Aufruf zum Brechen konkreter Chiffretexte – 10.000 US-Dollar für die Dechiffrierung verschiedener Chiffretexte. Die Organisation distributed.net koordinierte verteilte Angriffe auf die Chiffrate und brach RC5-32/12/7 innerhalb von 250 und RC5-32/12/8 innerhalb von 1757 Tagen. Die niedriger dotierten „Challenges“ RC5-32/12/5 und RC5-32/12/6 wurden bereits zuvor in 3,5 und 313 Stunden gebrochen.

