RC5

RC5
RC5 Eine Runde (zwei Halbrunden) von RC5
Entwickler	Ronald L. Rivest
Veröffentlicht	1994
Schlüssellänge	1 bis 2040 Bits
Blockgröße	32, 64 oder 128 Bit
Struktur	Feistelchiffre
Runden	1 bis 255 Runden, empfohlen mindestens 16 Runden
Beste bekannte Kryptoanalyse
RC5-32/12 ist anfällig für die differentielle Kryptoanalyse bei 244 gewählten Klartextblöcken.

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₀, …, S_2r+1 – wobei S₀ und S₁ 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 {\big (}2(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 {{\big (}2(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₀,…, 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⁴⁵ 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⁶² 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³⁹ für RC5-32/9 und bis zu 2⁵⁴ für RC5-32/12 gesenkt. Für RC5-64 sind – aus akademischer Sicht – die ursprünglich von Rivest vorgeschlagenen 16 Runden mit 2⁸³ 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⁴⁴. Die Autoren schlossen daraus, dass differentielle Angriffe gegen RC5-32/12/16 mit 2³⁸ und gegen RC5-64/16/16 mit 2⁶³ 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⁵⁴ gewählten Klartexten mit einer Erfolgswahrscheinlichkeit von 80 %. Ebenso zeigten die Autoren, dass der Angriff für etwa einen in 2²⁰ 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⁴⁷ 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²⁸ Schlüssel, bei denen sich eine lineare Kryptanalyse bereits mit 2¹⁷ bekannten Klartexten durchführen lässt. Weiterhin existieren 2⁶⁸ Schlüssel, für die die Chiffre theoretisch mit 2⁵⁷ 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²⁰ Chiffretexten mit Zeitbedarf Ω(2²⁸) und O(2⁴⁰). 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.

Literatur

• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, Boca Raton FL u. a. 1996, ISBN 0-8493-8523-7, S. 269–270, 280–281. 
• Bruce Schneier: Angewandte Kryptographie. Protokolle, Algorithmen und Sourcecode in C. Addison-Wesley Publishing, Bonn u. a. 1996, ISBN 3-89319-854-7, S. 397–399 (Informationssicherheit).