Universal Reencryption

Page 1

Diese Niederschrift ist die Ausarbeitung zu dem von mir am 01. Juli 2003 gehaltenen Vortrag zum Thema ”Universal Reencryption”.

”Universal Reencryption” ist eine neue kryptografische Technik, mittels derer Wiederverschl¨ usselung von Ciphertexten ohne Schl¨ ussel m¨ oglich ist. Diese wurde von P. Golle, M. Jakobsson, A. Juels und P. Syverson in [www 00] vorgestellt. Diese Verschl¨ usselungstechnik beruht auf dem ElGamal-Algorithmus. Nachfolgend werde ich diese Technik beschreiben und im speziellen Anwendungsfeld MIXnetze demonstrieren.

1 Einf¨ uhrung

Da die Technik des Reencryption im Folgenden anhand der MIXnetze pr¨ asentiert werden soll, wird eine kurze Einf¨ uhrung zu MIXnetzen und dem zugrundeliegenden kryptografischen Verfahren, dem ElGamal-Kryptoverfahren, gegeben.

1.1 MIXnetze

Ein MIXnetzwerk oder kurz MIXnetz ist ein Netz von Servern, welches es Kommunikationspartnern erm¨ oglicht, unerkannt zu kommunizieren. Ein MIX empf¨ angt Nachrichten gleicher L¨ ange und codiert diese Nachrichten um. Da in diese MIXe nicht hineingesehen werden kann, ist es einem Angreifer unm¨ oglich zu erfahren, wer wem welche Nachricht gesendet hat. Ein einfaches entschl¨ usselndes MIXnetz ¹ finden Sie in Abbildung 1 dargestellt. Der Versender der Nachricht verschl¨ usselt seine Nachricht mit allen ¨ offentlichen Schl¨ usseln aller MIXe und dem des Empf¨ angers. Jeder MIX entschl¨ usselt seine Nachricht nun mit dem ihm eigenen privaten Schl¨ ussel. Da die Nachrichten alle gleicher L¨ ange sind (notfalls aufgef¨ ullt mit Dummy-Traffic)

Page 2

und die MIXe im Idealfall warten sollten, bis eine gewisse große Anzahl Nachrichten eingegangen ist, ist es nicht m¨ oglich ausgehende Nachrichten am MIX eingehenden zuzuordnen. Die Nachrichten haben nach jeder Entschl¨ usselungsstufe zwar ein anderes Aussehen (und kommen gegebenenfalls auch in anderer Reihenfolge heraus), aber immer noch die gleiche L¨ ange. Ausf¨ uhrlicheres zu MIXen finden Sie auch in [Pfit 00].

1.2 ElGamal-Kryptoverfahren

Das ElGamal Kryptoverfahren wurde 1985 erstmals von Taher ElGamal vorgestellt. Dieses Verfahren basiert auf dem diskreten Logarithmus. Zuerst wird eine m¨ oglichst große Primzahl p gew¨ ahlt, f¨ ur die gelten sollte: ^p−1 2 ist ebenfalls Primzahl. Desweiteren wird ein Generator

^{∗ 2} gew¨ ahlt. Eine zuf¨ allig gew¨ ahlte Zahl x (1 < x < p) als privater Schl¨ ussel wird von Z p

noch ben¨ otigt. Der ¨ offentliche Schl¨ ussel errechnet sich wie folgt: y = g ^x mod p. Neben dem ¨ offentlichen Schl¨ ussel y werden auch der Generator g und die anfangs gew¨ ahlte Primzahl p ver¨ offentlicht.

Um eine Nachricht m zu verschl¨ usseln, wird nunmehr eine Zufallszahl k mit 1 < k < p ben¨ otigt. Der ¨ offentliche Schl¨ ussel y, der Generator g, sowie die Primzahl p sind dem Empf¨ anger bereits bekannt. Die Nachricht wird als c 0 = (my ^k )mod p verschl¨ usselt. Zus¨ atzlich wird die Hilfsgr¨ oße c 1 = g ^k mod p ¨ ubermittelt. Die Zufallszahl k wird nicht ver¨ offentlicht.

Der Empf¨ anger erh¨ alt c 0 und c 1 . Mithilfe seines privaten Schl¨ ussels x kann er die Nachricht jetzt entschl¨ usseln: m = (c 0 c ^p−1−x )mod p.

1

Ein kurzes Beispiel soll das ElGamal-Verfahren verdeutlichen:

1. Wahl der Primzahl, Generator, privater Schl¨ ussel: p = 23, g = 5, x = 3 2. Errechnen des ¨ offentlichen Schl¨ ussels: y = g ^x mod p = 5 ³ mod 23 = 125 mod 23 = 10

Page 3

3. Nachricht und Zufallszahl: m = 7, k = 2 4. Verschl¨ usselung: c 0 = (my ^k ) mod p = (7 ∗ 10 ² ) mod 23 = 10

5. Hilfsgr¨ oße: c 1 = g ^k mod p = 5 ² mod 23 = 2

6. Entschl¨ usselung: m = (c 0 c ^p−1−x ) mod p = (10 ∗ 2 ²³⁻¹⁻³ ) mod 23 = 7

1

2 Reencryption

Die Idee der Reencryption basiert auf der Problematik der Ausfallsicherheit von MIXservern in einem MIXnetz. Im eingangs gezeigten MIXnetz ist das komplette Netz unbrauchbar, sobald ein MIX ausf¨ allt. Daher ist es sinnvoll, ein Verfahren zu haben, dass unabh¨ angig von der Anzahl der MIXe zuverl¨ assig arbeitet. Dieses Verfahren muss aber die Eigenschaften des MIXnetzes weiterhin erf¨ ullen, die Nachrichten m¨ ussen also umcodiert und umsortiert von MIX zu MIX weitergeleitet werden. Um dieses unabh¨ angig von der Anzahl der MIXe zu gestalten, bietet es sich an, ein Verfahren ohne Schl¨ usselaustausch zwischen den MIXen zu kreieren. Eine Zwischenstufe ist die Reencryption mittels ElGamal. F¨ ur dieses Verfahren wird nur noch der ¨ offentliche Schl¨ ussel des Empf¨ angers ben¨ otigt.

2.1 ElGamal-Reencryption

Basierend auf der ElGamal Verschl¨ usselung k¨ onnen Nachrichten mehrfach mit dem selben ¨ offentlichen Schl¨ ussel verschl¨ usselt, jedoch in einem einzelnen Schritt entschl¨ usselt werden. Hierbei wird das ElGamal-Tupel (c 0 , c 1 ) mittels einer weiteren Zufallszahl k erneut verschl¨ usselt. Wie bereits erw¨ ahnt wird das Tupel (c 0 , c 1 ) mittels (m y ^k , g ^k ) errechnet. Die Ent-

Page 0

schl¨ usselung D(c 0 , c 1 ) = (c 0 c ¹ mit y = g ^x ergibt m g k x

¨ offentlichen Schl¨ ussels und des Generators sowie einer neuen, vom aktuellen MIXserver gebildeten Zufallszahl die Nachricht wiederzuverschl¨ usseln. Damit ist die Wiederverschl¨ usselung

folgendermaßen definiert: (c D(c 1 ) =

Es ist also offensichtlich, dass die Anzahl der Zufallszahlen {k, k , k , ...} und somit auch die Anzahl der Wiederverschl¨ usselungen keinen Einfluss auf den Entschl¨ usselungsvorgang haben. Zur Demonstration dieses Verfahrens wird obiges Beispiel aufgegriffen und dementsprechend fortgesetzt.

1. Schritte 1-4 wie oben

2. 1. Wiederverschl¨ usselung

(a) Wahl der Zufallszahl k = 15

1 = (c 1 g k ) mod p = (2 ∗ 5 ¹⁵ ) mod 23 = 15

3. Entschl¨ usselung nach der 1. Wiederverschl¨ usselung: D(c

= 4 15 3 mod 23 ergibt ³ (4 ∗ 19) mod 23 = 7 = m

4. 2. Wiederverschl¨ usselung

(a) Wahl der Zufallszahl k = 7 0 y ^k ) mod p = (4 ∗ 10 ⁷ ) mod 23 = 10 1 g k ) mod p = (15 ∗ 5 ⁷ ) mod 23 = 2 1 = (c

0 , c

= 10 2 3 mod 23 ergibt (10 ∗ 3) mod 23 = 7 = m

2.2 Universal Reencryption

Im Gegensatz zur ElGamal-Reencryption ben¨ otigt dieses Verfahren den ¨ offentlichen Schl¨ ussel des Empf¨ angers nicht mehr. In einem universellen Kryptosystem besteht der Ciphertext einer Nachricht m aus einem Ciphertextpaar [E[m]; E[1]]. Da die ElGamal Verschl¨ usselung homo-morph ⁴ ist, kann die zweite Komponente verwendet werden die erste wiederzuverschl¨ usseln. Die Schl¨ usselgenerierung erfolgt wie bereits gezeigt als (P K, SK) = (y, x) = (g ^x , x). Der Sender verschl¨ usselt seine Nachricht m mittels des ¨ offentlichen Schl¨ ussels y, des Generators g und zweier Zufallszahlen k 0 , k 1 .

C = [(a 0 , b 0 ); (a 1 , b 1 )] = [(my ^k0 , g ^k0 ); (y ^k1 , g ^k1 )] Die beiden Ciphertextteile werden analog zum ElGamal-Verfahren entschl¨ usselt. m 0 = ^a0 und m 1 = ^a1 . Wenn m 1 = 1 ist, dann ist m 0 die Nachricht. Ist dies nicht der Fall,

b ^x b x

Page 5

so ist die Entschl¨ usselung fehlgeschlagen und eine Meldung wird ausgegeben. Die Wiederverschl¨ usselung der Nachrichten findet wie folgt statt:

k k k k 0 , b C = [(a 0 ); (a 1 , b 1 )] = [(a 0 a 1 ); (a 1 )] Auch dieses Verfahren soll durch ein Bei- 1 ,b 0 b 1 , b 0 0 1 1

spiel n¨ aher gebracht werden:

1. Schl¨ usselgenerierung: x = 3, g = 5, p = 23

2. Errechnen des ¨ offentlichen Schl¨ ussels: y = g ^x mod p = 5 ³ mod 23 = 10

3. Nachricht und Zufallszahlen: m = 7, k 0 = 2, k 1 = 3

4. Verschl¨ usselung: C = [(a 0 , b 0 ); (a 1 , b 1 )]

= [(my ^k0 , g ^k0 ); (y ^k1 , g ^k1 )] = [((7 ∗ 10 ² ) mod 23, 5 ² mod 23); (10 ³ mod 23, 5 ³ mod 23)] = [(10, 2); (11, 10)]

5. 1. Wiederverschl¨ usselung

(a) Wahl der Zufallszahlen: k 0 = 8, k
0 , b

= [((10 ∗ 11 ⁸ ) mod 23, (2 ∗ 10 ⁸ ) mod 23); (11 ⁹ mod 23, 10 ⁹ mod 23)] = [(11, 4); (19, 20)]

6. Entschl¨ usselung nach der 1. Wiederverschl¨ usselung: m 0 =

m 0 = 11

m 0 = 7, m 1 = 1 Da m 1 = 1 ist, ist m 0 = 7 die Nachricht f¨ ur diesen Empf¨ anger.

7. 2. Wiederverschl¨ usselung

(a) Wahl der Zufallszahlen: k 0 = 13, k 0 , b

= [((11 ∗ 19 ¹³ ) mod 23, (4 ∗ 20 ¹³ ) mod 23); (19 ¹⁷ mod 23, 20 ¹⁷ mod 23)] = [(8, 10); (21, 7)]

8. Entschl¨ usselung nach der 2. Wiederverschl¨ usselung: m 0 =

m 0 = 8

m 0 = 7, m 1 = 1 Da m 1 = 1 ist, ist m 0 = 7 die Nachricht f¨ ur diesen Empf¨ anger.

3 Anwendung im MIXnetz

Eine konkrete Anwendung von ”Universal Reencryption” sind MIXnetze. Es gibt eine Menge von Sendern die Nachrichten an Empf¨ anger senden wollen, ohne dass der Weg dieser Nachrichten von irgendjemandem verfolgt werden kann. Es ist davon auszugehen, dass jeder m¨ ogliche Sender alle ¨ offentlichen Schl¨ ussel seiner m¨ oglichen Empfangspartner kennt. Das Kommunikationsprotokoll sieht dann wie folgt aus:

• Initialisierung

Jeder Sender ver¨ offentlicht seine universell verschl¨ usselte Nachricht; verschl¨ usselt mit dem ¨ offentlichen Schl¨ ussel des Empf¨ angers, f¨ ur den diese Nachricht sein soll. Diese

Page 6

Nachrichten aller Sender werden in irgendeiner Form ⁵ gesammelt. Alle Eintr¨ age haben das gleiche Aussehen ([E(m); E(1)]), daher sind sie durch reines Betrachten nicht unterscheidbar. • Universelles Mixen

Jeder MIXserver erh¨ alt nunmehr einen Pool von Nachrichten den er wiederverschl¨ usselt und weitergibt; im Fall des Bulletin Board ver¨ offentlicht er sie einfach wieder. • Empfangen der Nachricht

Potentielle Empf¨ anger m¨ ussen alle Nachrichten entschl¨ usseln die das MIXnetz ausgibt. Erfolgreiche Entschl¨ usselungen geben die Nachrichten aus, nicht erfolgreiche Entschl¨ usselungen geben die Fehlermeldung aus.

4 Schlußbemerkungen

4.1 Aufwand

Offensichtlich ist dieses Verfahren erheblich aufw¨ andiger als andere bekannte Verfahren. Schon aufgrund der zwei Ciphertextpaare ist der Wiederverschl¨ usselungsaufwand doppelt so hoch wie beim ElGamal-Reencryption Verfahren. Ebenfalls aufwendig erscheint der Broadcast am Ende der MIXkette. Jeder m¨ ogliche Empf¨ anger muss also von allen n Nachrichten den zweiten Ciphertextteil entschl¨ usseln um herauszufinden, ob die Nachricht ¨ uberhaupt f¨ ur

ihn ist, um dann erst die eigentliche Nachricht zu entschl¨ usseln. Im Einzelnen: ⁶ O Sender = 2 O Reencryption = 2nk O Recipient = n + 1

O = 2 + 2nk + n + 1 = 2nk + n + 3 mit n − Anzahl N achrichten und k − Anzahl M IXserver F¨ ur n = 10 und k = 5 ist O n=10,k=5 = 2nk + n + 3 = 113.

Offensichtlich ist dieses Verfahren erheblich aufw¨ andiger als andere Verfahren.

4.2 Korrektheit

Solange alle MIXserver korrekt arbeiten, ist dieses Verfahren als korrekt anzusehen. Arbeitet einer der MIXserver nicht mehr korrekt, geht die Nachricht verloren, da durch falsches Wiederverschl¨ usseln auch der zweite Ciphertextteil falsch wiederverschl¨ usselt wird und der eigentlich gemeinte Empf¨ anger diese Nachricht nicht finden kann. Eine zweite M¨ oglichkeit w¨ are, ein MIX versucht nur den ersten Ciphertextteil einer Nachricht zu ersetzen um einen Empf¨ anger gezielt falsche Informationen zukommen zu lassen. Dieses w¨ are m¨ oglich, wenn dieser MIX weiß, welche Nachricht f¨ ur welchen Empf¨ anger ist, und er im Besitz des ¨ offentlichen Schl¨ ussels dieses Empf¨ angers ist.

Page 7

4.3 Anonymit¨ at

Solange auch nur ein MIXserver ehrlich arbeitet, ist die Anonymit¨ at der Kommunikation gew¨ ahrleistet. Diese kann durch die Tatsache gw¨ ahrleistet werden, dass auch nach nur einem MIXserver nicht mehr nachvollzogen werden kann, von wem an wen diese Nachricht versandt wurde.

4.4 FAZIT

Das Verfahren des Universal Reencryption ist damit als Variante f¨ ur MIXnetze einsetzbar. Der große Vorteil liegt unzweifelhaft darin, dass es keine Schl¨ ussel der weiteren Kommunikationsteilnehmer ben¨ otigt. Ein weiterer Vorteil liegt darin, dass es m¨ oglich wird, MIXnetze zu skalieren und selbst bei Ausfall eines MIXes die Nachricht nicht zu verlieren. Der Hauptnachteil dieses Verfahrens liegt in der Zustellung und Entschl¨ usselung der Nachrichten. Dadurch, dass jeder m¨ ogliche Empf¨ anger von allen Nachrichten zumindest einen Teil entschl¨ usseln muss, um ¨ uberhaupt ersteinmal herauszufinden, ob die Nachricht f¨ ur ihn ist, ist der Auf-wand f¨ ur die Zustellung der Nachrichten sehr hoch. Hier wird noch zu ¨ uberlegen sein, ob

dieses Verfahren im Ergebnis noch praxisrelevant einsetzbar ist.

Page 8

Quellennachweis: [Pfit 00] A.Pfitzmann, Sicherheit in Rechnernetzen: Mehrseitige Sicherheit in

Phillip Golle, Markus Jakobsson, Ari Juels, Paul Syverson, Universal [www 00]

Abbildungsnachweis:

[Abbildung 1] aus: A.Pfitzmann, Sicherheit in Rechnernetzen: Mehrseitige Sicherheit