RC6

RC6 (Rivest Cipher 6) i​st eine 1998 v​on Ronald Rivest u​nd anderen entworfene symmetrische Blockverschlüsselung. RC6 i​st eine Weiterentwicklung v​on RC5 u​nd verwendet ebenso w​ie dieses datenabhängige Rotationen, u​nd zusätzlich d​ie Multiplikation v​on Daten. Die z​um Entwicklungszeitpunkt bekannten theoretischen Angriffe g​egen RC5 sollten dadurch bereits i​m Ansatz verhindert werden.[1]

RC6
Entwickler	Ronald L. Rivest, Matt Robshaw, Ray Sidney, Yiqun Lisa Yin
Veröffentlicht	1997
Abgeleitet von	RC5
Schlüssellänge	128, 192 oder 256 Bit
Blockgröße	128 Bit
Struktur	Feistelchiffre
Runden	20

RC6 kandidierte z​ur Wahl d​es Advanced Encryption Standards (AES) u​nd zählte d​ort – zusammen m​it Twofish, Rijndael, MARS u​nd Serpent – z​u den Finalisten. Es w​urde vom National Institute o​f Standards a​nd Technology (NIST) a​ls „hinreichend sicher“ eingestuft – ebenso w​ie Rijndael, welches schließlich z​um AES gewählt wurde. RC6 i​st einfacher aufgebaut a​ls die anderen Finalisten, wodurch d​ie Gefahr v​on Implementierungsfehlern reduziert wird, u​nd es i​st auch relativ effizient i​n Software z​u implementieren.

Beschreibung

Struktur von RC6

RC6 besitzt variable Blockgrößen, Rundenzahlen (0–255) und Schlüssellängen (0–2040 Bit). Eine spezifische Wahl dieser Parameter wird üblicherweise mit „RC6-w/r/b“ bezeichnet – w ist die Länge eines Datenworts in Bit, r die Anzahl der Runden und b die Länge des Schlüssels. Ein Block besteht immer aus vier Datenwörtern, die Blockgröße ist also ${\displaystyle 4w}$ Bit. Der AES-Kandidat war RC6-32/20 mit Blockgröße 128 Bit, 20 Runden und Schlüssellängen von 128, 192 und 256 Bit.[1]

Als Primitive Operationen verwendet der Algorithmus die Addition (${\displaystyle A+B}$) und Multiplikation (${\displaystyle A\cdot B}$) (jeweils modulo ${\displaystyle 2^{w}}$), die bitweise XOR-Verknüpfung (${\displaystyle A\oplus B}$) und die Linksrotation (${\displaystyle A\lll B}$), die ${\displaystyle A}$ um ${\displaystyle B\,{\bmod {w}}}$ Bitpositionen rotiert.[1]

Ver- und Entschlüsselung

Gegeben seien ein Klartextblock in Little-Endian-Darstellung, der aus den Datenworten A, B, C, D besteht, und die Rundenschlüssel S₀ bis S_2r+3. Dabei bezeichnet ${\displaystyle \log w}$ den Logarithmus der Wortlänge ${\displaystyle w}$ zur Basis 2. Der Block wird verschlüsselt durch:

${\displaystyle B\leftarrow B+S_{0}}$

${\displaystyle D\leftarrow D+S_{1}}$

${\displaystyle \mathbf {for} \;k\leftarrow 1\;\mathbf {to} \;r\;\mathbf {do:} }$

${\displaystyle t\leftarrow {\big (}B\cdot (2B+1){\big )}\lll \log w}$

${\displaystyle u\leftarrow {\big (}D\cdot (2D+1){\big )}\lll \log w}$

${\displaystyle X\leftarrow {\big (}(A\oplus t)\lll u{\big )}+S_{2k}}$

${\displaystyle C\leftarrow {\big (}(C\oplus u)\lll t{\big )}+S_{2k+1}}$

${\displaystyle A\leftarrow B;\;B\leftarrow C;\;C\leftarrow D;\;D\leftarrow X}$

${\displaystyle A\leftarrow A+S_{2r+2}}$

${\displaystyle C\leftarrow C+S_{2r+3}}$

Wie b​ei RC5 werden S₀ u​nd S₁ z​um Key Whitening verwendet.

Die Entschlüsselung e​ines Chiffretextblocks entspricht d​er Umkehrung dieses Algorithmus.[1]

Schlüsselexpansion

P und Q in Abhängigkeit von der Blockgröße[1]

Blockgröße [Bits]	P [hexadezimal]	Q [hexadezimal]
64	B7E1	9E37
128	B7E1 5163	9E37 79B9
256	B7E1 5162 8AED 2A6B	9E37 79B9 7F4A 7C15

Der Expansionsalgorithmus von RC6, der die Rundenschlüssel S₀ bis S_2r+3 berechnet, wurde im Wesentlichen unverändert von RC5 übernommen. Zunächst werden die Rundenschlüssel S_k mittels Konstanten ${\displaystyle P,Q}$ auf einen festen Anfangszustand initialisiert. P und Q sind – wie bei RC5 – ungerade Ganzzahlen, die mit der eulerschen Zahl e und dem goldenen Schnitt Φ in Abhängigkeit von der verwendeten Blockgröße generiert werden (Tabelle).

${\displaystyle S_{0}\leftarrow P}$

${\displaystyle \mathbf {for} \;k\leftarrow 1\;\mathbf {to} \;2r+3\;\mathbf {do:} }$

${\displaystyle S_{k}\leftarrow S_{k-1}+Q}$

Anschließend wird der geheime Schlüssel in c Wörter ${\displaystyle L_{0}}$ bis ${\displaystyle L_{c-1}}$ der Länge w aufgespaltet, und bei Bedarf wird das letzte Wort ${\displaystyle L_{c-1}}$ mit Nullen aufgefüllt. Folgender Code berechnet dann die endgültigen Rundenschlüssel:

${\displaystyle k\leftarrow i\leftarrow 0}$

${\displaystyle A\leftarrow B\leftarrow 0}$

${\displaystyle \mathbf {do} \;3\cdot \max {\big (}2r+4,c{\big )}\;\mathbf {times:} }$

${\displaystyle A\leftarrow (S_{k}+A+B)\lll 3}$

${\displaystyle B\leftarrow (L_{i}+A+B)\lll (A+B)}$

${\displaystyle S_{k}\leftarrow A;\;L_{i}\leftarrow B}$

${\displaystyle k\leftarrow (k+1)\;{\bmod {\;}}(2r+4)}$

${\displaystyle i\leftarrow (i+1)\;{\bmod {\;}}c}$

Kryptoanalyse

Chosen-Plaintext

2001 wiesen Tetsu Iwata u​nd Kaoru Kurosawa d​es Tokyo Institute o​f Technology nach, d​ass ein idealisiertes RC6 m​it 4 Runden k​eine pseudozufällige Permutation darstellt – e​in Angreifer m​it polynomiell vielen Verschlüsselungsversuchen d​as Ergebnis d​er Blockchiffre a​lso von zufälligem Rauschen unterscheiden kann.[2] Im gleichen Jahr stellten Henri Gilbert, Helena Handschuh, Antoine Joux u​nd Serge Vaudenay e​inen auf dieser Eigenschaft aufbauenden statistischen Angriff vor, m​it dessen Hilfe s​ich – für w = 32 – m​it 2¹¹⁸ Paaren a​us gewählten Klartexten u​nd ihren Chiffraten Bits d​er Rundenschlüssel für b​is zu 13 Runden rekonstruieren lassen. Mit e​inem Speicherbedarf v​on 2¹¹² u​nd etwa 2¹²² notwendigen Operationen k​ann dieser Angriff z​udem auch a​ls Known-Plaintext-Angriff g​egen 14 Runden verwendet werden. Aus diesem – aufgrund d​er Anforderungen praktisch n​icht durchführbaren – Angriff schlossen d​ie Autoren, d​ass die 20 Runden d​es AES-Kandidaten n​icht übermäßig v​iel seien.[3]

Known-Plaintext

1999 stellten Borst, Preneel u​nd Vandevalle fest, d​ass der v​on ihnen publizierte, a​uf linearen Approximationen basierende Angriff a​uf RC5 g​egen RC6 essentiell wirkungslos i​st und d​ie Vorkehrungen d​er RC6-Entwickler ausreichten.[4]

Lizenzierung

Für das RC6-Verfahren erhielt das Unternehmen RSA die US-Patente 5724428 und 5835600 zugesprochen. Diese liefen allerdings zwischen 2015 und 2017 aus.

Einzelnachweise

1. Ronald L. Rivest, M. J. B. Robshaw, R. Sidney, Y.L. Yin: The RC6 Block Cipher. 1998 (psu.edu).
2. Tetsu Iwata, Kaoru Kurosawa: On the Pseudorandomness of the AES Finalists - RC6 and Serpent. In: Lecture Notes in Computer Science. Band 1978/2001. Springer Berlin / Heidelberg, S. 231.
3. Henri Gilbert, Helena Handschuh, Antoine Joux, Serge Vaudenay: A Statistical Attack on RC6. In: Lecture Notes in Computer Science. Band 1978/2001. Springer Berlin / Heidelberg, S. 1–15.
4. Johan Borst, Bart Preneel, Joos Vandewalle: Linear Cryptanalysis of RC5 and RC6. In: Lecture Notes in Computer Science. Band 1636, Nr. 1999. Springer Berlin / Heidelberg, ISSN 1611-3349, S. 16.

Weblinks

• Beschreibung von Markus Repges
• NIST, Report on the Development of the Advanced Encryption Standard (AES), 2. Oktober 2000 (PDF; 383 kB)