60
1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

Embed Size (px)

Citation preview

Page 1: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

1

Kryptographische

Verfahren

Maxim Mariach Eugen Hofmann

Ira Tsalman

Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

Page 2: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

2

BegriffeDie Begriffe Kryptographie und -logie sind

ursprünglich aus den griechischen Wörtern kryptos (geheim) und logos (Wort, Kunde) bzw. graphien (schreiben) abgeleitet.

Die grundlegende Aufgabe der Kryptographie besteht in der Geheimhaltung von übertragenen oder gespeicherten Informationen und Schutz vor dem unbefugten Gebrauch.

Page 3: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

3

Begriffe

Kryptologie: mathematische Disziplin, die sowohl die Kryptographie als auch die Kryptoanalyse umfasst.

Kryptoanalyse: Lehre von der Entschlüsselung geheimer Texte.

Kryptographie: Wissenschaft zur Entwicklung von Kryptosystemen bzw. den Maßnahmen zur Ver- und Entschlüsselung von Daten.

Page 4: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

4

Begriffe

Sei n ein Klartext (Plaintext). Um die Datensicherheit zu vergrößern, verschlüsselt (encrypts) der Absender den Text und schickt das Resultat, den verschlüsselten Text (Cryptotext), durch einen Kanal. Der Empfänger (Benutzer) entschlüsselt den Kryptotext um den Plaintext zu bekommen.

Page 5: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

5

BegriffeDie Verschlüsselung (Encryption) und

Entschlüsselung (Decryption) findet im Rahmen eines bestimmten Kryptosystems statt. Jedes Kryptosystem besitzt einige Schlüssel (Keys). Jeder dieser Schlüssel bestimmt eine Verschlüsselungsfunktion ek und eine Entschlüssungsfunktion dk.

ek( n ) = cund umgekehrt gilt

dk( c ) = n

Deshalb ist dk( ek ( n ) )= n

Page 6: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

6

Kryptosystem

Ein „gutes“ Kryptosystem sollte folgende Eigenschaften besitzen:

1. Gegeben ek und n, soll es einfach sein c = ek(n) zu berechnen.

2. Gegeben dk und c, soll es einfach sein n = dk(c) zu berechnen.

3. Der Kryptotext ek ( n ) soll nicht viel länger sein als der Plaintext n.

4. Es soll sehr schwer oder nahezu unmöglich sein den Plaintext n aus dem Kryptotext ek ( n ) zu bestimmen ohne dk zu kennen.

Page 7: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

7

Kryptoanalyse

Eine Verschlüsselung ist brechbar, falls

Klartext oder Schlüssel aus dem Schlüsseltext abgeleitet werden können

Schlüssel für Klartext-Schlüsseltext-Paare gefunden werden können

Page 8: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

8

KryptoanalyseGrundlegende Angriffsarten:

1. Ciphertext only attack: (Angriff nur auf Schlüsseltext) Schlüssel wird nur aufgrund des abgehörten Schlüsseltextes bestimmt durch:

- (bekannte) Verschlüsselungsmethode

- Thema des Textes- wahrscheinliche Worte

Page 9: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

9

Kryptoanalyse

2. Known-plaintext only attack: ( Angriff mit bekanntem Klartext)Angreifer kennt einige Klartext- Schlüsseltext Paare, z.B.:- Angreifer fängt Nachricht vom Benutzerterminal zum Zentralrechner ab und weiß, dass diese mit Standard-Header „Login“ beginnt.- Wahrscheinliche Wörter der Nachricht sind bekannt.

Page 10: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

10

Kryptoanalyse

3. Chosen-plaintext attack: ( Angriff mit ausgewähltem Klartext )

- Angreifer kann Schlüsseltext zu ausgewähltem Klartext ableiten, z.B.:

- Angriff auf verschlüsselte DB:Angreifer fügt Elemente in DB ein und beobachtet Veränderungen.

Page 11: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

11

Kryptoanalyse

4. Chosen-ciphertext attack: ( Angriff mit ausgewähltem Schlüsseltext )

Angreifer kennt Verschlüsselungsalgorithmus und Verschlüsselungstext.

Page 12: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

12

Kryptographie

Es gibt zwei grundlegende Verschlüsselungsmethoden:

1. Transpositionsverschlüsselung: Umordnen der Bits/Zeichen des Klartextes („Permutation“).

2. Substitutionsverschlüsselung: ersetzen von

Bits, Zeichen oder Zeichenblocks.

Page 13: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

13

Einfache Substitutionsverschlüsselungen

Monoalphabetische Verschlüsselung:- Ersetzen jedes Zeichens des Klartext-Alphabets

durch entsprechendes Zeichen des Schlüsseltext-Alphabets

Beispiel:Ω = { A,B,…Z }Ω = ABCDEFGHIJKLMNOPQRSTUVWXYZΣ = HARPSICODBEFGJKLMNQTXYZUVW

n = SPACEek (n) = QMHRS

Page 14: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

14

Einfache Substitutionsverschlüsselungen

Verschlüsselungen basierend auf Verschiebungen im Alphabet:

z.B.: Cäsar – Verschlüsselung:

Jedes Zeichen wird um k Positionen ( mod n) nach rechts verschoben: f(a) = (a + k) mod n (z.B. A + 4 = E oder Y + 4 = C, bei k = 4 und n = 26 )

Page 15: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

15

Einfache Substitutionsverschlüsselungen

Kryptoanalyse

Durch Vergleich der Zeichenhäufigkeiten des Schlüsseltextes mit der erwarteten Häufigkeitsverteilung ( Ciphertext only attack - Angriff nur auf Schlüsseltext)

Buchstabe Englisch (%) Pascal (%)

A 7,49 4,7

I 6,65 8,6

L 3,57 5,11

Page 16: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

16

Homophone Substitutionen

Abbildung des Klartext-Alphabets auf Schlüsseltext-Alphabet

Beispiel: Σ = Englisches Alphabet Ω = {0,…99}- Anzahl der Zahlen, die einem Zeichen zugeordnet

werden können (Relative Häufigkeit des Buchtabens im englischen Alphabet)

- Keine Zahl wird mehr als einem Zeichen zugeordnet

( So kann L z.B. mit Hilfe von 22, 12 oder 43 abgebildet werden )

Page 17: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

17

Homophone Substitutionen

Kryptoanalyse

Kein Brechen möglich durch Häufigkeitsanalyse einzelner Zeichen, jedoch

Angriff mit Häufigkeitsverteilung von Zeichenfolgen möglich.

Page 18: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

18

Kodierungsbeispiel

Was meint ihr, welches Wort ist hier verschlüsselt?

Dojrulwkpxv

Algorithmus

Page 19: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

19

Polyalphabetische Substitutionsverschlüsselungen

Die Blöcke vom Klartext werden mit Blöcken vom Schlüsseltext ersetzt

Page 20: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

20

Substitutions- und Transpositionsverschlüsselungen

Transpositions- und Substitutionsverschlüsselungen halten nicht modernen kryptoanalytischen Verfahren stand.

Moderne Verschlüsselungen sind i.A. eine Kombination von mehreren Funktionen, die jeweils entweder Substitutions- oder Transpositions-Operatoren durchführen.

Sie arbeiten auf Bit-Ebene.

Page 21: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

21

Symmetrische und AsymmetrischeKryptosysteme

Symmetrische Kryptosysteme• DES• AES

Asymmetrische Kryptosysteme

Hybride Verschlüsselungsverfahren

Page 22: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

22

Symmetrische Kryptosysteme

Für Entschlüsselung und Verschlüsselung wird derselbe Schlüssel verwendet

Schlüsselaustausch erfolgt über einen sicheren Kanal

Beispiele: DES, IDEA, AES

Page 23: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

23

Vor- und Nachteile

(+) symmetrische Verfahren beruhen auf relativ

einfacher Mathematik wie Addition, Multiplikation und Komplementbildung

→ Die Ver- und Entschlüsselung sind sehr schnell

sind relativ leicht in Hardware implementierbar

(-) Der Schlüssel zur Ver- und Entschlüsselung ist

gleich Sicherheitsrisiko Schlüsselaustausch

Spontane Kommunikation ?

Page 24: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

24

DES (Data Encryption Standard)

basiert auf dem zu Anfang der 70er Jahre von IBM entwickeltem Verschlüsselungsverfahren Lucifer →Verkürzung des ursprünglich 128-Bit langen Schlüssels auf 64 Bit

wurde erstmals 1974 von der US Regierung veröffentlicht und ist als ANSI-Standard normiert (ANSI X3.92-1981)

Entwurfskriterien: leicht verständlich, preiswert umsetzbar, effizient berechenbar, öffentlich verfügbar

Blockalgorithmus, welcher 64 Bits Klartext in 64 Bits Schlüsseltext und umgekehrt überführt

Die Schlüssellänge beträgt 64 Bits, von denen aber nur 56 Bits signifikant sind

Page 25: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

25

ArbeitsweiseP

IP

L0 R0

L1 R1

+

f(R0,K0)

L16R16

.

.

.

IP-1

C

Initiale Permutation

1 Bit 2 Bit …↓ ↓58 52

Aufteilung

Der Block wird in zwei 32-Bit Blöcke zerlegt

.

.

.

Ri-1

E

E(Ri-1) Ki

+

S1 S2 S3 S4 S5 S6 S7 S8

P

F(Ri-1,Ki)

Page 26: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

26

ECB-Modus (Electronic Code Book)

DES wird blockweise auf jeweils 64 Bit lange Klartextblöcke angewandt

Problem: Angreifer kann innerhalb einer Schlüsselperiode Chiffretexte abhören, zwischenspeichern und später wieder in den Kanal einspielen.

→ Die Reihenfolge der Blöcken kann auch verändert werden, ohne dass dies vom Empfänger erkannt werden könnte

Page 27: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

27

CBC-Modus (Cipher Block Chaining)

vor der Verschlüsselung wird ein Klartextblock Pi mit dem Vorgängerblock Ci-1 Modulo 2 addiert → Abhängigkeit zwischen den Blöcken

DES

Ci=Ek(Ci-1Pi)

DES

Schieberegister Schieberegister

+ +Pi PiCi

Ci-1 Ci-1

Pi=Dk(Ci)Ci-1

Zufällige Blöcke als initiale Kettenwerte,d.h. C0=ICV

Ein Übertragungsfehler im i.ten Block kann sich in den i+1.ten Block fortpflanzen

Page 28: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

28

CFB-Modus (Cipher Feedback)

DES als Pseudo-Zufallszahlengenerator

linke 8 Bit

Schieberegister

DES

+

64 Bit

64 Bit

8 Bit

linke 8 Bit

Schieberegister

DES

+

64 Bit

64 Bit

8 Bit

8 Bit 8 Bit

Klartext Klartext 8 Bit 8 Bit 8 Bit

Effizienzproblem: in jedem Durchlauf werden nur 8 Bit verschlüsselt

Übertragungsfehler pflanzt solange fort, bis das fehlerhafte Zeichen aus dem Register fällt

Page 29: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

29

OFB-Modus (Output Feedback)

Die linken 8 Bit des chiffrierten Registers werden in das Schieberegister geschoben

linke 8 Bit

Schieberegister

DES

+

64 Bit

64 Bit

8 Bit

linke 8 Bit

Schieberegister

DES

+

64 Bit

64 Bit

8 Bit 8 Bit 8 Bit

Klartext Klartext 8 Bit 8 Bit 8 Bit

Keine Fehlerfortpflanzung Effizienzproblem

Page 30: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

30

3DES (Triple-DES)

Idee: Mehrfachverschlüsselung auf Basis von DES und verschiedenen Schlüsseln zu benutzen

E D E

K1 K2 K1/K3

gilt heute als relativ sicher

Page 31: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

31

Schwäche des DES

war nicht vollständig veröffentlicht, es wurden sogar Hintertüren der NSA vermutet, die allerdings nie gefunden wurden

differentielle und lineare Kryptoanalyse: Schlüsselermittlung aus 247 bzw. 243 Klar- und Chiffretextpaaren

vollständige Suche: 256 große Schlüsselraum, aber im Durchschnitt sind nur 255 Schlüssel zu testen

invariant unter der binären Komplimentbildung:

der Aufwand lässt sich noch mal halbieren Existenz von schwachen Schlüssel Am 15.07.1998 RSA Challenge III: in 23 Stunden wurde

56 Bit DES-Schlüssel geknackt.

Page 32: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

32

AES: Advanced Encryption Standard

2.10.00: Rijndael als Sieger des AES-Wettbewerbes Symmetrischer Blockalgorithmus Block- und Schlüssellänge: 128 Bit, 192 Bit oder 256 Bit Anzahl der Runden: 10, 12 oder 14 je nach Schlüssellänge

und Blocklänge frei von Patenten und unentgeltlich nutzbar gegen bekannte Methoden der Kryptoanalyse resistent hat eine überdurchschnittliche Performance leicht in Hard- und Software implementierbar mit

geringem Ressourcenverbrauch

Page 33: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

33

Die Arbeitsweise von AESEingabeblock

Schlüsselexpansion

Vorrunde

runde <N-1

Schlussrunde

Ausgabe

State

Rundenfunktionen arbeiten auf den s.g. Zuständen

Zustand: Byte-Array mit 4 Zeilen und Nb Spalten

Abbildung vom Klartext geschieht spaltenweise

substitution()

shiftRow()

mixColumn()

keyAddition()

a0,0 a0,1 a0,2 a0,3

a1,0 a1,1 a1,2 a1,3

a2,0 a2,1 a2,2 a2,3

a3,0 a3,1 a3,2 a3,3

Schlüsselexpansion

Die Rundenschlüssel werden vom AES-Schlüssel erzeugt: Expandierung des Schlüssels und Selektion des Teilschlüssels

Der Erzeugungsprozess ist nicht linear und nicht invertierbar

Vorrunde

In der Vorrunde wird der Klartext mit dem aktuellen Rundenschlüssel durch XOR verknüpft

Page 34: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

34

Die Arbeitsweise von AESEingabeblock

Schlüsselexpansion

Vorrunde

runde <N-1

Schlussrunde

Ausgabe

substitution()

shiftRow()

mixColumn()

keyAddition()

Substitution

Jedes Byte eines Blockes wird durch Anwendung einer S-Box ersetzt.

S-Box: nicht lineare Operationen (Bildung des Multiplikativ-Inverses, affine Substitution)

Permutation

Die Zeilen des States werden um eine bestimmte Anzahl von Spalten nach links verschoben

Diffusion

Jeder Spalte eines States wird eine neue zugeordnet

KeyAddition

Zum Abschluss einer Runde wird der Block durch XOR mit dem jeweiligen Rundenschlüssel

verknüpft

Schlussrunde

In dieser Runde wird mixColumn ausgelassen

Page 35: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

35

Kryptographische Stärke des AES

Mit den Schlüssellängen von 128 Bit ergibt sich ein Schlüsselraum von 3.4×1038, mit 192 Bit 6.2×1057 und mit 256 Bit 1.1×1077.

DES hat einen Schlüsselraum von 7.2×1016.

Annahme: Es gibt eine Maschine, die den ganzen DES Schlüsselraum in einer Sekunde durchsucht.

Es würde bei Rijndael ungefähr 149'000 Billionen Jahre dauern.(Man bedenke, dass es das Universum seit weniger als 20 Milliarden Jahren geben soll)

Page 36: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

36

Kryptographische Stärke des AES

resistent gegenüber allen bekannten Angriffen

resistent gegen lineare und differentielle Kryptoanalyse: Transformationen in der S-Box

kann mit dem geringsten Aufwand gegen Angriffe geschützt werden, die auf Messungen von Änderungen der Stromaufnahme beruhen

Page 37: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

37

Schwächen des AES ?

Mai 2001: Algorithmus als geschlossene Formel mit 250 TermenNiemand weiß, ob daraus jemals ein sinnvoller Angriff auf AES konstruiert werden kann

Courtois und Pieprzyk: 128-Bit-AES als System von 8000 quadratischen Gleichungen mit 1600 Variablen Derartige Systeme lassen sich im Allgemeinen nicht mit vertretbarem Rechenaufwand lösen

XSL-Methode: Angriff auf AES mit 2100 Operationen

Die genannten Angriffe sind rein akademischer Natur !

Page 38: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

38

Asymmetrische Kryptosysteme

Für Entschlüsselung und Verschlüsselung werden unterschiedliche Schlüssel k und k‘ verwendet

Enschlüsselungsschlüssel k‘ kann praktisch nicht aus dem Verschlüsselungsschlüssel abgeleitet werden

Schlüssel zur Verschlüsselung darf öffentlich bekannt sein

Page 39: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

39

Vor- und Nachteile

(+) einfaches Schlüsselmanagement: es muss kein sicherer

Kanal für den Schlüsseltausch vorhanden sein gut für digitale Signaturen geeignet

(-) sehr hohe Aufwand für Ver- und Entschlüsselung Größere Schlüssellänge Chiffretexte sind länger sind als die originalen Klartexte

und die Algorithmen sind in der Regel nur schwer hardwareseitig umzusetzen

Unsicherheit, dass das zugrunde liegende mathematische Problem eine einfachere Lösung hat

Page 40: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

40

Hybride Verschlüsselungsverfahren

kombinieren symmetrische und asymmetrische Verschlüsselungsverfahren

Dokument wird mit einem symmetrischen Sitzungsschlüssel verschlüsselt

Sitzungsschlüssel wird mit einem öffentlichen Schlüssel verschlüsselt

Page 41: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

41

RSA und MD5

RSAHash (md5)GeburtstagangriffDigitale SignaturenBlinde UnterschriftDigitales Geld

Page 42: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

42

RSA

Public-Key-Verschlüsselungssystem welches im Jahre 1977 von Ron Rivest, Adi Shamir  und Leonard Adleman am MIT erfunden wurde

kann zur Verschlüsselung und zum digitalen Signieren verwendet werden

Page 43: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

43

RSA

Algorithmus:p und q große Primzahlenn: n = p n = p q q

e: teilerfremd zu ((p-1)(q-1))((p-1)(q-1))

d: ed ed ≡1 mod ≡1 mod (p-1)(q-1)(p-1)(q-1)

Privater Schlüssel: d, nd, nÖffentlicher Schlüssel: e, ne, n

Verschlüsselung: C = NC = Nee mod n mod nEntschlüsselung: N = CN = Cdd mod n = (N mod n = (Nee))dd mod n mod n

Page 44: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

44

Kryptographische Stärke des RSA

Die Sicherheit von RSA basiert auf dem Problem, eine

große ganze Zahl in ihre Primfaktoren zu zerlegen Wie schnell kann man faktorisieren?

Es gibt „schnelle“ Verfahren nur für spezielle Zahlen

Die schnellsten allgemeinen Verfahren Zahlkörpersieb und Elliptische-Kurven-Faktorisierung haben einen Zeitaufwand der Größenordnung:

Bernstein: Annahme, dass man den Aufwand um den Faktor 3 zu reduzieren könnte

MIPS-Jahre, um den Schlüssel zu knacken RSA Schlüssellänge

104

1011

512 Bit

1024 Bit

Page 45: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

45

Kryptographische Stärke des RSA

512-Bit-RSA-Schlüssel sind nicht mehr sicher! Empfehlung

Primfaktoren: e1 < | log2(p) – log2(q) | < e2

ee11 ≈ 0.5, ≈ 0.5, ee22 ≈ 30≈ 30

Bis Ende 2005 Bis Ende 2006 Bis Ende 2007

1024 1024 (Mindestwert)

2048 (Empfehlung)

1536 (Mindestwert)

2048 (Empfehlung)

Page 46: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

46

Was ist Hash?

Eine volumenmäßig kleinere Abbildung eines Dokuments.

Ziel einer Hashfunktion ist es, den unendlichen Definitionsbereich (die Menge aller Dokumente) möglichst „gleichmäßig“ auf den Wertebereich abzubilden.

Page 47: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

47

Wozu Hash?

Nicht das ganze Dokument, sondern nur den Hash verschlüsseln Signatur

Bei Datenbanken, um zu entscheiden, an welcher Stelle man einen Datensatz in die Datenbank einfügt

Prüfsumme

Page 48: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

48

MD5 Ziele Nicht umkehrbar Es soll keine bessere Möglichkeit geben, zwei

Dokumente mit gleicher Signatur zu finden, als eine "Brute Force"-Attacke.

Keine unbewiesenen Annahmen (z.B. der derzeit mangels geeigneter Algorithmen sehr hohe Aufwand zur Faktorzerlegung großer Zahlen) sollten dem Algorithmus zugrunde liegen.

MD5 soll schnell und kompakt sein, um auch in kleinen Computern vernünftige Anwendungen zu finden.

Page 49: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

49

MD5 Funktionsweise

MD5 arbeitet in 4 Runden und mit 64 Konstanten. Das Ergebnis ist ein 128-Bit-Hashwert

Sein Ablauf besteht aus vier Schritten:– Padding

– Initialisierung

– Berechnung des Blockhashwertes

– Bestimmung des Hashwertes

Page 50: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

50

Padding

Nachricht auf ein Vielfaches von 512 Bit ergänzen, da mit 512-Bit-Blöcken gearbeitet wird.

An die Nachricht wird zuerst eine einzelne 1 angehängt und dann noch so viele Nullen, bis die Nachricht kongruent 448 modulo 512 ist. (Das Anhängen der 1 stellt sicher, dass die Nachricht mindestens eine Eins enthält.)

In die letzten 64 freien Bit wird die Länge der ursprünglichen Nachricht geschrieben.

Page 51: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

51

Initialisierung

Bei der Berechnung werden vier 32-Bit-Puffer verwendet, die den aktuellen Rundenhashwert mit einer Größe von 128 Bit beinhalten. Diese müssen, da MD5 eine iterative Hashfunktion ist, initialisiert werden; dafür werden die folgenden Werte benutzt:

h(0) := 76543210hexh(0) := 76543210hexh(1) := fedcba98hexh(1) := fedcba98hexh(2) := 98abcdefhexh(2) := 98abcdefhexh(3) := fedcba89hexh(3) := fedcba89hex

Page 52: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

52

Blockhashwertberechnung

64 Funktionen ft(x,y,z)ft(x,y,z), 64 Konstanten K(t)K(t), 64 Rotationskonstanten RRt t

und die 16 Worte W(i)W(i) des

aktuellen Blockes werden in Abhängigkeit der jeweiligen Prozeßstufe verwendet.

Die 64 verwendeten additiven Konstanten K(t)K(t) leiten sich aus irrationalen Zahlen, in Abhängigkeit der zugehörigen Prozeßstufe.

Page 53: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

53

Blockhashwertberechnung

A := h0 B := h1 C := h2 D := h3 FOR t = 0 TO 63 DO

BEGIN T := B + ((A + ft(B,C,D) + W(t) + Kt), Rk) B := A A := D D := C C := T

ENDh0 := h0 + A h1 := h1 + B h2 := h2 + C h3 := h3 + D

Page 54: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

54

Bestimmung des Hashwertes

Es wird nun solange Schritt 3 mit dem nächsten Block iteriert, bis alle Nachrichtenblöcke bearbeitet worden sind. Die Ausgabe des MD5 ist dann die Konkatenation der Worte h0 bis h3: HMD5 (N) = h0 || h1 || h2 || h3HMD5 (N) = h0 || h1 || h2 || h3

Page 55: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

55

Geburtstagsangriff

Ein Versuch zwei Dokumente herzustellen, die denselben Hashwert besitzen. Man müsste versuchen, eine Person unter Vorspiegelung falscher Tatsachen zu einer Unterschrift unter A zu bewegen, um dann auch eine gültige Unterschrift für B zu haben.

Dem Angriff liegt das so genannte "Geburtstagsparadoxon" zugrunde: In einem Raum müssten 183 Personen sein, damit mit einer Wahrscheinlichkeit größer 50 % eine Person anwesend ist, die den gleichen Geburtstag hat wie der Gastgeber. Es müssen aber nur 23 sein, um mit einer Wahrscheinlichkeit größer 50 % zwei Personen mit demselben (aber beliebigen) Geburtstag zu finden.

Page 56: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

56

Geburtstagsangriff

Angenommen, man arbeitet mit 64-Bit-Hashwerten, so würde es (bei einer Rechenleistung von 1 Mio. Hashwerten pro Sekunde) rund 600.000 Jahre dauern, bis ein zweites Dokument mit dem gleichen Hashwert wie ein vorgegebenes Dokument gefunden wäre. Um ein Paar von Dokumenten mit übereinstimmendem Hashwert zu finden, benötigte derselbe Rechner aber nur rund eine Stunde.

Um die Hashfunktion sicher gegenüber der

Geburtstagsattacke zu machen, sollte man mit 160-Bit- Hashwerten arbeiten.

Page 57: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

57

Digitale Signatur

Eine Art von Siegel zu digitalen Daten. Wird unter Einsatz mathematischer Verfahren mit Hilfe eines Schlüssels erzeugt. So kann die Signatur jederzeit überprüft und damit der Signaturschlüssel-Inhaber und die Unverfälschtheit der Daten festgestellt werden.

Page 58: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

58

Blinde Unterschrift

Signieren einer Nachricht ohne ihren Inhalt zu kennen

Verhüllen: A wählt zufälligen Verhüllungsfaktor r und berechnet mit dem öffentlichen Schlüssel (e, n) des B: m'=m m'=m r r ee mod (n) mod (n)

Unterschreiben: B verwendet privaten Schlüssel d und berechnet: s'=ms'=m''dd mod (n) mod (n)

Enthüllen: A berechnet s=s'/r mod ks=s'/r mod k und hat somit (s, m) derart, daß s=ms=mdd mod (n) mod (n) m trägt die Signatur von B, jedoch kennt B die Zahl m nicht

Page 59: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

59

Digitales Geld

Die Bank signiert eine digitale Münze ohne zu wissen um welche Münze es sich genau handelt Anonymität und Authentizität

PC von A generiert eine Zufallszahl = Digitale Münze PC von A verbindet die Münze mit einer zweiten

Zufallszahl Bank von A signiert die so verhüllte Münze mit ihrem

privaten Schlüssel PC von A nimmt die Verhüllung ab; Signatur der Bank

verbleibt C und die Bank von A verwenden den öffentlichen

Schlüssel der Bank, um bei Erhalt der digitalen Münze ihre Echtheit zu prüfen

Page 60: 1 Kryptographische Verfahren Maxim Mariach Eugen Hofmann Ira Tsalman Seminar: Sicherheit in vernetzten Systemen. WS 2002/2003

60

Literatur

Buchmann, Johannes. Einführung in die Kryptographie. Springer Verlag, 1999.

Böhmer, Wolfgang. Virtual Private Networks.Carl Hanser Verlag, 2002.

Oppliger, Rolf. IT-Sicherheit. Vieweg Verlag, 1997.

Rijndael Specification http://csrc.nist.gov/encryption/aes/rijndael/Rijndael.pdf