imported>Handprint6077: /* growthexperiments-addlink-summary-summary:3|0|0 */

2024-12-22T22:23:41Z

growthexperiments-addlink-summary-summary:3|0|0

Neue Seite

{{Dieser Artikel|erläutert das Verschlüsselungsverfahren. Zum Datenübertragungsprotokoll siehe [[RC-5]].}}
{{Infobox Blockchiffre
| name = RC5
| bild = RC5 InfoBox Diagram.svg
| bildname = Eine Runde (zwei Halbrunden) von RC5
| entwickler = [[Ronald Rivest|Ronald L. Rivest]]
| datum = 1994
| abgeleitet =
| 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
| kryptoanalyse = RC5-32/12 ist anfällig für die [[differentielle Kryptoanalyse]] bei 244 gewählten Klartextblöcken.
}}

'''RC5''' ('''R'''ivest '''C'''ipher '''5''') ist eine 1994 von [[Ronald Rivest]] entworfene [[Symmetrisches Kryptosystem|symmetrische]] [[Blockverschlüsselung]]. Das bedeutet, dass sowohl für das [[Verschlüsselung|Verschlüsseln]] wie das Entschlüsseln der gleiche [[Schlüssel (Kryptologie)|Schlüssel]] benutzt wird. Sie gehört zur Klasse der [[Feistelchiffre]]n. Die Daten werden zunächst in Blöcke gleicher Größe aufgeteilt und über wiederholte Anwendung einfacher Operationen – sogenannter „[[Kryptographisches Primitiv|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 (Informatik)|Parameter]] vor der Verschlüsselung festgelegt.

Das Ziel beim Entwurf von RC5 war eine einfache und schnelle Chiffre. Sie baut auf datenabhängigen [[Bitweiser Operator#Zyklische Verschiebung|Rotationen]] auf, deren Eignung als Primitiv zum Entwicklungszeitpunkt noch weitgehend unerforscht war.<ref name="rivest1995">{{Literatur |Autor=[[Ronald L. Rivest]] |Titel=The RC5 encryption algorithm |Sammelwerk=Lecture Notes in Computer Science |Band=1008/1995 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=1995 |ISBN=3-540-60590-8 |Seiten=86–96 |DOI=10.1007/3-540-60590-8}}</ref>

Anders als viele andere Blockchiffren verwendet RC5 keine [[S-Box]]en, um das von [[Claude Elwood Shannon|Claude Shannon]] 1949 als „[[Konfusion (Kryptologie)|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 <math>b \times b</math>-S-Box die <math>2^b</math> möglichen Werte der <math>b</math> eingegebenen Bits auf die <math>2^b</math> 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 [[Cipher Block Chaining Mode|CBC]], CBC-Pad und [[Ciphertext Stealing Mode|CTS]] – wird im Standard <nowiki>RFC 2040</nowiki> spezifiziert.<ref>{{RFC-Internet |RFC=2040 |Titel=The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms |Datum= |Autor=Ronald Rivest, Robert W. Baldwin}}</ref>

RC5 diente als Basis für die Verschlüsselung [[RC6]], die zur Wahl des [[Advanced Encryption Standard]] kandidierte.<ref name="Borst1999">{{Literatur |Autor=Johan Borst, Bart Preneel, Joos Vandewalle |Titel=Linear Cryptanalysis of RC5 and RC6 |Sammelwerk=Lecture Notes in Computer Science |Band=1636 |Nummer=1999 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=1999 |ISSN=1611-3349 |Seiten=16}}</ref>

In den Vereinigten Staaten hielt das Unternehmen RSA Security bis 2015 ein Patent auf RC5.<ref>{{Patent| Land=US| V-Nr=5724428| Code=A| Titel=Block encryption algorithm with data-dependent rotations| A-Datum=1995-11-01| V-Datum=1998-03-03| Anmelder=RSA Data Security| Erfinder=Ronald L. Rivest}}</ref>

== 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 (Informatik)|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 [[Byte]]s. Rivest empfahl ursprünglich RC5-32/12/16 und RC5-64/16/16 für 64-Bit-Architekturen.<ref name="rivest1995" />

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 <math>2^w</math>
* die bitweise [[XOR-Verknüpfung]] zweier Wörter
* die Rotation eines Wortes um ''b'' Bitpositionen, wobei ''b'' durch die <math>\log_2 w</math> 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.<ref name="rivest1995" /> Auch der Nachfolgealgorithmus RC6 und in Teilen der AES-Kandidat [[MARS (Verschlüsselung)|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 S0, …, S2r+1 – wobei S0 und S1 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 Li aufgespalten, bei Bedarf wird mit Nullen aufgefüllt. Anschließend werden die Rundenschlüssel Sk mittels Konstanten auf einen festen Anfangszustand initialisiert:

{| class="wikitable float-right"
|- class="hintergrundfarbe5"
! Blockgröße (Bits)
! P (hexadezimal)
! Q (hexadezimal)
|-
| {{0}}32
| B7E1
| 9E37
|-
| {{0}}64
| B7E1 5163
| 9E37 79B9
|-
| 128
| B7E1 5162 8AED 2A6B
| 9E37 79B9 7F4A 7C15
|}

:<math>S_0 \leftarrow P</math>
:<math>\mathbf{for} \; k\leftarrow 1 \; \mathbf{to}\; 2r + 1 \;\mathbf{do}</math>:
::<math>S_k \leftarrow S_{k-1} + Q</math>

P und Q sind hierbei [[ungerade]] [[Ganzzahl]]en, die mit der [[Eulersche Zahl|eulerschen Zahl]] ''e'' und dem [[Goldener Schnitt|goldenen Schnitt]] Φ in Abhängigkeit von der verwendeten Blockgröße generiert werden.

Letztlich werden die Halbblöcke Li und Sk in drei Durchläufen miteinander vermischt:

:<math>k \leftarrow i \leftarrow 0</math>
:<math>A \leftarrow B \leftarrow 0</math>
:<math>\mathbf{do}\; 3\cdot \max\big(2(r+1), \lceil b/(w/8) \rceil\big)\; \mathbf{times}</math>:
::<math>A \leftarrow S_k \leftarrow (S_k + A + B) \lll 3</math>
::<math>B \leftarrow L_i \leftarrow (L_i + A + B) \lll (A + B)</math>
::<math>k \leftarrow (k+1) \mod{\big(2(r+1)\big)}</math>
::<math>i \leftarrow (i +1) \mod{\big(\lceil b/(w/8) \rceil\big)}</math>

=== Ver- und Entschlüsselung ===
Gegeben seien ein Klartextblock in [[Little Endian|Little-Endian]]-Darstellung, der aus den Halbblöcken A, B besteht und die Rundenschlüssel S0,…, S2r+1. Der Block wird verschlüsselt durch:

:<math>A \leftarrow A+S_0</math>
:<math>B \leftarrow B+S_1</math>
:<math>\mathbf{for}\; k \leftarrow 1\; \mathbf{to}\; r \; \mathbf{do}</math>:
::<math>A \leftarrow \big((A \oplus B) \lll B\big) + S_{2k}</math>
::<math>B \leftarrow \big((B \oplus A) \lll A\big) + S_{2k+1}</math>

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

:<math>\mathbf{for}\; k \leftarrow r \;\mathbf{downto}\; 1 \;\mathbf{do}</math>:
::<math>B \leftarrow \big((B - S_{2k+1}) \ggg A\big) \oplus A</math>
::<math>A \leftarrow \big((A - S_{2k}) \ggg B \big) \oplus B</math>
:<math>B \leftarrow B - S_1</math>
:<math>A \leftarrow A - S_0</math>

== Kryptoanalyse ==
Zu [[Kryptoanalyse]]zwecken 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.<ref name="biryukov1998">{{Literatur |Autor=Alex Biryukov, Eyal Kushilevitz |Titel=Improved Cryptanalysis of RC5 |Sammelwerk=Lecture Notes in Computer Science |Band=1403/1998 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=1998 |ISBN=3-540-64518-7 |Seiten=85–99 |DOI=10.1007/BFb0054119}}</ref>

Auch die analoge Variante RC5P, die ausschließlich Additionen verwendet, hat sich als kryptographisch schwächer herausgestellt. John Kelsey, [[Bruce Schneier]] und [[David Wagner (Kryptologe)|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.<ref name="kelsey1999">{{Literatur |Autor=John Kelsey, [[Bruce Schneier]], [[David Wagner (Kryptologe)|David Wagner]] |Titel=Mod n Cryptanalysis, with Applications against RC5P and M6 |Sammelwerk=Lecture Notes in Computer Science |Band=1636/1999 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=1999 |ISSN=1611-3349 |Seiten=139}}</ref>

=== Chosen-Plaintext-Angriffe ===
Kaliski und Yin von den RSA Laboratories zeigten 1995, dass für differentielle Kryptanalyse gegen RC5-32/9 245 Paare gewählter Klartexte und zugehöriger Chiffretexte benötigt werden, was etwa der Stärke von 16-Runden-[[Data Encryption Standard|DES]] entspricht. Für RC5-32/12 werden hingegen 262 solcher Paare benötigt. Der Angriff rekonstruiert hierbei Bits von L2r, woraus Informationen über S2r+1 hergeleitet werden können. Sobald S2r+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.<ref name="kaliski1995">{{Literatur |Autor=Burton S. Kaliski Jr., Yiqun Lisa Yin |Titel=On Differential and Linear Cryptanalysis of the RC5 Encryption Algorithm |Sammelwerk=Lecture Notes in Computer Science |Band=963/1995 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=1995 |ISSN=1611-3349 |Seiten=171}}</ref>

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.<ref name="knudsen1996">{{Literatur |Autor=Lars R. Knudsen, Willi Meier |Titel=Improved Differential Attacks on RC5 |Sammelwerk=Lecture Notes in Computer Science |Band=1109/1996 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=1996 |ISSN=1611-3349 |Seiten=216}}</ref> 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 239 für RC5-32/9 und bis zu 254 für RC5-32/12 gesenkt. Für RC5-64 sind – aus akademischer Sicht – die ursprünglich von Rivest vorgeschlagenen 16 Runden<ref name="rivest1995" /> mit 283 benötigten, gewählten Klartextpaaren nicht hinreichend sicher gegen differentielle Kryptanalyse.<ref name="knudsen1996" />

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-Gewicht]]e der Rundendifferenzen gewählt werden, reduziert die Anzahl der benötigten gewählten Klartextpaare für RC5-32/12 auf 244. Die Autoren schlossen daraus, dass differentielle Angriffe gegen RC5-32/12/16 mit 238 und gegen RC5-64/16/16 mit 263 gewählten Klartextpaaren möglich seien.<ref name="biryukov1998" />

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 [[Chi-Quadrat-Test|χ²-Test]] aufbauende Korrelationsangriff rekonstruiert den letzten Rundenschlüssel für RC5 mit 17 Halbrunden mittels 254 gewählten Klartexten mit einer Erfolgswahrscheinlichkeit von 80 %. Ebenso zeigten die Autoren, dass der Angriff für etwa einen in 220 Schlüsseln mit gleicher Wahrscheinlichkeit auch RC5 mit voller Rundenzahl bricht.<ref name="shimoyama2000">{{Literatur |Autor=Takeshi Shimoyama, Kiyofumi Takeuchi, Juri Hayakawa |Hrsg=NIST |Titel=Correlation Attack to the Block Cipher RC5 and the Simplified Variants of RC6 |Datum=2000 |Kommentar=zu AES3 eingereicht |Online={{Webarchiv |url=http://www.csrc.nist.gov/CryptoToolkit/aes/round2/conf3/papers/36-tshimoyama.pdf |text=csrc.nist.gov |wayback=20041108005031}} |Format=PDF |KBytes=}}</ref>

=== Known-Plaintext-Angriffe ===
Kaliski und Yin zeigten, dass eine Rekonstruktion der erweiterten Schlüsseltabelle mittels linearer Approximationen bereits für fünf Runden 247 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.<ref name="kaliski1995" /> Nach Ali Aydın Selçuk der University of Maryland beruht dieser Angriff jedoch auf falschen Annahmen und ist somit fehlerhaft.<ref name="selcuk1998">{{Literatur |Autor=Ali Aydin Selçuk |Titel=New Results in Linear Cryptanalysis of RC5 |Sammelwerk=Lecture Notes in Computer Science |Band=1372/1998 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=1998 |ISSN=1611-3349 |Seiten=1}}</ref>

1997 publizierte Howard M. Keys RC5-32/12/16 die Existenz linear schwacher Schlüssel. Er fand 228 Schlüssel, bei denen sich eine lineare Kryptanalyse bereits mit 217 bekannten Klartexten durchführen lässt. Weiterhin existieren 268 Schlüssel, für die die Chiffre theoretisch mit 257 Klartexten gebrochen werden kann. Die Schlüssel hängen dabei wesentlich vom verwendeten Expansionsalgorithmus ab.<ref name="heys1997">{{Literatur |Autor=Howard M. Heys |Titel=Linearly weak keys of RC5 |Sammelwerk=IEE Electronics Letters |Band=33 |Nummer=10 |Datum=1997-05-08 |ISSN=0013-5194 |Seiten=836–838 |Online=[http://www.engr.mun.ca/~howard/PAPERS/rc5_letter.pdf engr.mun.ca] |Format=PDF |KBytes=}}</ref>

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 24+6r und RC5-64/r mit 23+8r bekannten Klartexten mit 90-prozentiger Erfolgswahrscheinlichkeit.<ref name="Borst1999" /> Miyaji, Nonaka und Takii bezeichneten diese Ergebnisse 2002 als „highly optimistic“ (zu deutsch: „hochgradig optimistisch“) und stellten ihrerseits einen auf dem [[Chi-Quadrat-Test|χ²-Test]] aufbauenden Korrelationsangriff vor, mit dem eine 90-prozentige Erfolgswahrscheinlichkeit gegen RC5-32/r mit 26,14r+2,27 bekannten Klartexten möglich sei.<ref name="miyaji2002">{{Literatur |Autor=Atsuko Miyaji, Masao Nonaka, Yoshinori Takii |Titel=Known Plaintext Correlation Attack against RC5 |Sammelwerk=Lecture Notes in Computer Science |Band=2271/2002 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=2002 |ISSN=1611-3349 |Seiten=115–141}}</ref>

=== 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 [[Landau-Symbole|O]](1) ausführen,<ref name="rivest1995" /> ist dies nicht notwendig etwa für [[Eingebettetes System|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 220 Chiffretexten mit Zeitbedarf Ω(228) und O(240). Der Angriff kann jedoch implementationsbasiert durch Dummy-Rotationen vermieden werden.<ref name="handschuh1999">{{Literatur |Autor=Helena Handschuh, Howard M. Heys |Titel=A Timing Attack on RC5 |Sammelwerk=Lecture Notes in Computer Science |Band=1556/1999 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=1999 |ISSN=1611-3349 |Seiten=631}}</ref>

=== 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.<ref name="dist.net">[http://www.distributed.net/RC5/ Project RC5.] distributed.net</ref> Die niedriger dotierten „Challenges“ RC5-32/12/5 und RC5-32/12/6 wurden bereits zuvor in 3,5 und 313 Stunden gebrochen.<ref>[http://www.rsa.com/rsalabs/node.asp?id=2103 Status and Prizes] von RSA Laboratories</ref>

== Literatur ==
* {{Literatur
|Autor=Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
|Titel=Handbook of Applied Cryptography
|Verlag=CRC Press
|Ort=Boca Raton FL u. a.
|Datum=1996
|ISBN=0-8493-8523-7
|Seiten=269–270, 280–281}}
* {{Literatur
|Autor=[[Bruce Schneier]]
|Titel=Angewandte Kryptographie. Protokolle, Algorithmen und Sourcecode in C
|Verlag=Addison-Wesley Publishing
|Ort=Bonn u. a.
|Datum=1996
|ISBN=3-89319-854-7
|Seiten=397–399
|Kommentar=''Informationssicherheit''}}

== Einzelnachweise ==
<references />

{{Lesenswert|August 2007|35889542}}

[[Kategorie:Abkürzung]]
[[Kategorie:Blockverschlüsselung]]

RC5 - Versionsgeschichte

imported>Handprint6077: /* growthexperiments-addlink-summary-summary:3|0|0 */