Kryptographie I - Exam

Aufgabe 1)

Betrachte die Blockchiffren AES und DES, zwei der bekanntesten Verschlüsselungsmethoden. DES operiert mit 64-Bit-Blöcken und verwendet einen 56-Bit-Schlüssel. Aufgrund von Sicherheitsmängeln gilt DES als unsicher und wurde durch 3DES verbessert, das die DES-Funktion dreimal durchläuft und somit sicherer, aber langsamer ist. AES hingegen verarbeitet 128-Bit-Blöcke und kommt mit verschiedenen Schlüsselgrößen (128, 192 oder 256 Bit). Die Anzahl der Runden in AES variiert mit der Schlüsselgröße (10, 12 oder 14 Runden) und besteht aus den vier Hauptschritten SubBytes, ShiftRows, MixColumns und AddRoundKey.

a)

(a) Erkläre den Unterschied zwischen DES und 3DES, speziell hinsichtlich der Sicherheit und der Performance. Warum wird DES nicht mehr als sicher betrachtet?

Lösung:

(a) Der Unterschied zwischen DES (Data Encryption Standard) und 3DES (Triple DES) liegt hauptsächlich in ihrer Sicherheit und Performance. Hier sind die wesentlichen Unterschiede:

• Sicherheit:
  • DES: DES arbeitet mit einem 56-Bit-Schlüssel und 64-Bit-Blöcken. Aufgrund der begrenzten Schlüssellänge ist DES anfällig für Brute-Force-Angriffe. Es wurde festgestellt, dass DES mit modernen Technologien in vertretbarer Zeit geknackt werden kann. Ein vollständiger Brute-Force-Angriff auf DES erfordert lediglich das Durchprobieren aller möglichen 56-Bit-Schlüssel.
  • 3DES: 3DES erhöht die Sicherheit von DES, indem es die DES-Verschlüsselungsfunktion dreimal hintereinander mit drei unterschiedlichen Schlüsseln verwendet. 3DES verwendet somit effektiv einen 168-Bit-Schlüssel (jeweils drei 56-Bit-Schlüssel). Dies macht Brute-Force-Angriffe wesentlich schwieriger und erhöht die Sicherheit erheblich im Vergleich zu DES.
• Performance:
  • DES: Da DES pro Verschlüsselungsvorgang nur einmal die DES-Funktion durchläuft, ist die Performance relativ hoch. Es ist im Vergleich zu 3DES schneller, da weniger Berechnungen erforderlich sind.
  • 3DES: Da 3DES die DES-Funktion dreimal durchläuft, ist es deutlich langsamer als DES. Die erhöhte Sicherheitsstufe wird auf Kosten der Geschwindigkeit erreicht. Dies macht 3DES weniger effizient für Anwendungen, die hohe Geschwindigkeiten erfordern.
• Warum DES nicht mehr als sicher betrachtet wird:
  • Die begrenzte Schlüssellänge von 56 Bit macht DES anfällig für Brute-Force-Angriffe, bei denen alle möglichen Schlüssel systematisch ausprobiert werden, bis der richtige gefunden wird. Angesichts der gestiegenen Rechenleistung moderner Computer ist dies in einer relativ kurzen Zeitspanne möglich.
  • Zusätzlich zu Brute-Force-Angriffen wurden auch andere kryptographische Schwächen in DES aufgedeckt, die seine Sicherheit weiter beeinträchtigen.

b)

(b) Angenommen, du hast einen AES-Algorithmus mit einer Schlüsselgröße von 192 Bit. Wie viele Runden durchläuft der Algorithmus? Beschreibe die vier Hauptschritte in einer dieser Runden.

Lösung:

(b) Angenommen, Du hast einen AES-Algorithmus mit einer Schlüsselgröße von 192 Bit. In diesem Fall durchläuft der Algorithmus 12 Runden.

Hier sind die vier Hauptschritte, die in einer dieser Runden durchgeführt werden:

• SubBytes: In diesem Schritt wird jeder Byte des 128-Bit-Datenblocks (16 Bytes) mithilfe einer substitution box (S-Box) ersetzt. Diese S-Box-Transformation ist nichtlinear und bietet Verwirrung während des Verschlüsselungsprozesses.
• ShiftRows: In diesem Schritt werden die Bytes jeder Zeile des 4x4-Bytes-Matrixblocks zyklisch verschoben. Konkret wird die erste Zeile unverändert gelassen, die zweite Zeile wird um ein Byte nach links verschoben, die dritte Zeile um zwei Bytes und die vierte Zeile um drei Bytes. Dies bewirkt eine Diffusion der Bytes über den Block.
• MixColumns: Dieser Schritt multipliziert jede Spalte der Blockmatrix mit einer festen Matrix. Dies ist ebenfalls eine Diffusionsoperation und sorgt dafür, dass die Bits weiter über den Block verteilt werden. Der MixColumns-Schritt wird in der letzten Runde des Algorithmus weggelassen.
• AddRoundKey: In diesem letzten Schritt der Runde wird ein Rundenschlüssel, der aus dem ursprünglichen Schlüssel abgeleitet wird, mittels XOR-Operation mit dem Block verknüpft. Dies ist entweder der erste oder letzte Schritt in jeder Runde und verknüpft den Datenblock mit dem Schlüssel.

Diese Schritte werden in jeder der 12 Runden durchlaufen, wobei in der letzten Runde der MixColumns-Schritt weggelassen wird.

c)

(c) Angenommen, eine Nachricht wird mit AES-256 verschlüsselt. Berechne die Anzahl der möglichen Schlüssel und vergleiche diese Anzahl mit der Anzahl möglicher Schlüssel bei DES. Wie verhält sich der Vergleich hinsichtlich der Brute-Force-Angriffe?

Lösung:

(c) Angenommen, eine Nachricht wird mit AES-256 verschlüsselt. Berechne die Anzahl der möglichen Schlüssel und vergleiche diese Anzahl mit der Anzahl möglicher Schlüssel bei DES. Wie verhält sich der Vergleich hinsichtlich der Brute-Force-Angriffe?

Anzahl der möglichen Schlüssel:

• AES-256: AES-256 verwendet einen 256-Bit-Schlüssel. Die Anzahl der möglichen Schlüssel ist daher: \(2^{256}\) Schlüssel.
• DES: DES verwendet einen 56-Bit-Schlüssel. Die Anzahl der möglichen Schlüssel ist daher: \(2^{56}\) Schlüssel.

Zur Verdeutlichung der Größenordnung:

• Für AES-256: \(2^{256} \approx 1.1579 \times 10^{77}\) mögliche Schlüssel
• Für DES: \(2^{56} \approx 7.21 \times 10^{16}\) mögliche Schlüssel

Vergleich hinsichtlich Brute-Force-Angriffe:

• DES: Aufgrund der vergleichsweise geringen Anzahl möglicher Schlüssel kann ein Brute-Force-Angriff auf DES heutzutage in relativ kurzer Zeit durchgeführt werden, insbesondere mit der modernen Rechenleistung und parallelen Verarbeitungstechniken.
• AES-256: Die Anzahl möglicher Schlüssel bei AES-256 ist astronomisch groß. Ein Brute-Force-Angriff auf \(2^{256}\) Schlüssel ist praktisch undurchführbar, selbst mit den leistungsstärksten Computern, die es derzeit gibt. Um die Größenordnung zu verdeutlichen: \(2^{256}\) ist so eine riesige Zahl, dass selbst die kombinierte Rechenleistung aller Computer weltweit über viele Jahre hinweg nicht ausreichen würde, um einen Brute-Force-Angriff erfolgreich durchzuführen.

d)

(d) Im Jahr 1999 wurde ein DES-Schlüssel in weniger als 23 Stunden mittels einer Brute-Force-Attacke gebrochen. Berechne, wie lange eine solche Attacke auf AES-128 dauern würde, wenn die gleiche Geschwindigkeit der Brute-Force-Attacke angenommen wird. Gehe davon aus, dass die Geschwindigkeit dieser Attacke bei 2⁵⁶ Schlüssel pro Tag liegt.

Lösung:

(d) Im Jahr 1999 wurde ein DES-Schlüssel in weniger als 23 Stunden mittels einer Brute-Force-Attacke gebrochen. Berechne, wie lange eine solche Attacke auf AES-128 dauern würde, wenn die gleiche Geschwindigkeit der Brute-Force-Attacke angenommen wird. Gehe davon aus, dass die Geschwindigkeit dieser Attacke bei \(2^{56}\) Schlüssel pro Tag liegt.

Um die Dauer einer Brute-Force-Attacke auf AES-128 zu berechnen, müssen wir die Anzahl der möglichen Schlüssel von AES-128 berücksichtigen:

• AES-128: AES-128 verwendet einen 128-Bit-Schlüssel. Die Anzahl der möglichen Schlüssel ist daher:

\(2^{128}\) Schlüssel.

Es wird angenommen, dass die Geschwindigkeit der Brute-Force-Attacke bei \(2^{56}\) Schlüssel pro Tag liegt.

Die Anzahl der möglichen Schlüssel für AES-128 beträgt \(2^{128}\). Wenn die Brute-Force-Attacke mit einer Rate von \(2^{56}\) Schlüsseln pro Tag durchgeführt wird, können wir die Dauer der Attacke wie folgt berechnen:

\[\text{Dauer (in Tagen)} = \frac{2^{128}}{2^{56}} = 2^{72}\]

Somit würden \(2^{72}\) Tage benötigt, um eine Brute-Force-Attacke auf AES-128 bei der gegebenen Geschwindigkeit durchzuführen.

Zur Verdeutlichung der Größenordnung:

\(2^{72}\) Tage sind eine extrem große Zahl:

• \(2^{72} \approx 4.72 \times 10^{21}\) Tage
• Um dies in Jahre umzurechnen, verwenden wir: \(\frac{4.72 \times 10^{21}}{365} \approx 1.29 \times 10^{19}\) Jahre

Eine Brute-Force-Attacke auf AES-128 würde somit etwa \(1.29 \times 10^{19}\) Jahre dauern, wenn die gleiche Geschwindigkeit von \(2^{56}\) Schlüsseln pro Tag angenommen wird. Das ist eine unvorstellbar lange Zeit und zeigt deutlich, dass ein Brute-Force-Angriff auf AES-128 praktisch unmöglich ist.

Aufgabe 2)

Du sollst zwei der Modi zur symmetrischen Verschlüsselung – CBC (Cipher Block Chaining) und CTR (Counter Mode) – näher untersuchen. Beide Modi definieren, wie Blöcke verarbeitet werden.

• CBC (Cipher Block Chaining): Jeder Klartextblock wird vor der Verschlüsselung mit dem vorangegangenen Chiffretextblock XOR-verknüpft.
• CTR (Counter Mode): Wandelt Blockchiffre in eine Stromchiffre um; jeder Block wird mit einem inkrementierten Zähler verschlüsselt.
• CBC Formel: \[C_i = E_K(P_i \bigoplus C_{i-1} )\]
• CTR Formel: \[C_i = P_i \bigoplus E_K(Nonce \bigparallel i)\]
• Ein Initialisierungsvektor (IV) wird für CBC benötigt.
• CTR kann parallel verarbeitet werden und ist somit geeignet für High-Speed-Anwendungen.

a)

Angenommen, Du hast eine Nachricht von 4 Blöcken (P1, P2, P3, P4). Der Initialisierungsvektor (IV) für den CBC-Mode ist gegeben als IV = 1010. Der Verschlüsselungsschlüssel K und der Klartext P_i sind in Binärform. Verwende den CBC-Mode, um die gesamte Nachricht zu verschlüsseln. Die XOR-Operation erfolgt bitweise. Zeige jeden Schritt Deiner Berechnungen und bestimme die endgültige Chiffretextsequenz (C1, C2, C3, C4).

Klartextblöcke: P1 = 1100, P2 = 1011, P3 = 1001, P4 = 1110 Schlüssel K: K = 0110

Lösung:

Um die Nachricht im CBC-Mode zu verschlüsseln, folge den gegebenen Schritten. Die XOR-Operation erfolgt bitweise, und der Verschlüsselungsalgorithmus wird symbolisch als E_K angegeben, da die eigentliche Verschlüsselungsfunktion nicht definiert ist. Um die Schritte klar darzustellen, werde ich die vollständige Berechnung für jeden Block zeigen.

• Initialisierung: IV = 1010
• Klartextblöcke: P1 = 1100, P2 = 1011, P3 = 1001, P4 = 1110
• K: K = 0110

Schritt-für-Schritt-Berechnungen:

• Berechnung von C1:

  • Klartextblock P1: 1100
  • IV (Initialisierungsvektor): 1010
  • Bitweises XOR von P1 und IV:

    1100⊕ 1010------0110

  • Verschlüsselung von 0110 mit Schlüssel K (E_K): Da die eigentliche Verschlüsselung E_K nicht spezifiziert ist, nehmen wir an: E_K(0110) = 0110
  • Somit ist C1 = 0110

• Berechnung von C2:

  • Klartextblock P2: 1011
  • Vorhergehender Chiffretextblock C1: 0110
  • Bitweises XOR von P2 und C1:

    1011⊕ 0110------1101

  • Verschlüsselung von 1101 mit Schlüssel K (E_K): Da die eigentliche Verschlüsselung E_K nicht spezifiziert ist, nehmen wir an: E_K(1101) = 1101
  • Somit ist C2 = 1101

• Berechnung von C3:

  • Klartextblock P3: 1001
  • Vorhergehender Chiffretextblock C2: 1101
  • Bitweises XOR von P3 und C2:

    1001⊕ 1101------0100

  • Verschlüsselung von 0100 mit Schlüssel K (E_K): Da die eigentliche Verschlüsselung E_K nicht spezifiziert ist, nehmen wir an: E_K(0100) = 0100
  • Somit ist C3 = 0100

• Berechnung von C4:

  • Klartextblock P4: 1110
  • Vorhergehender Chiffretextblock C3: 0100
  • Bitweises XOR von P4 und C3:

    1110⊕ 0100------1010

  • Verschlüsselung von 1010 mit Schlüssel K (E_K): Da die eigentliche Verschlüsselung E_K nicht spezifiziert ist, nehmen wir an: E_K(1010) = 1010
  • Somit ist C4 = 1010

Endgültige Chiffretextsequenz:

• C1 = 0110
• C2 = 1101
• C3 = 0100
• C4 = 1010

Die endgültige Chiffretextsequenz lautet also: 0110, 1101, 0100, 1010.

b)

Betrachte nun dieselbe Nachricht und denselben Verschlüsselungsschlüssel wie im vorherigen Teil der Aufgabe, jedoch im CTR-Mode. Der Nonce wird als 0101 vorgegeben. Verschlüssele die Nachricht mittels des CTR-Modes und zeige auch hier jeden Berechnungsschritt auf. Bestimme die endgültige Chiffretextsequenz (C1, C2, C3, C4).

Klartextblöcke: P1 = 1100, P2 = 1011, P3 = 1001, P4 = 1110 Schlüssel K: K = 0110 Nonce: 0101

Lösung:

Um die Nachricht im CTR-Mode zu verschlüsseln, arbeiten wir gemäß der CTR-Formel: \(C_i = P_i \oplus E_K(\text{Nonce} \parallel i)\). Der Nonce bleibt für alle Blöcke gleich, während der Zähler (\(i\)) für jeden Block um 1 erhöht wird. Die bitweise XOR-Operation und die Verschlüsselungsfunktion \(E_K\) werden angewendet.

• Klartextblöcke: P1 = 1100, P2 = 1011, P3 = 1001, P4 = 1110
• Schlüssel K: K = 0110
• Nonce: 0101

Schritt-für-Schritt-Berechnungen:

• Berechnung von C1:

  • Klartextblock P1: 1100
  • Zähler für den ersten Block: \(i = 1\), also \(\text{Nonce} \parallel i = 0101 || 1 = 0101 || 0001 = 01010001\)
  • Verschlüsselung von 01010001 mit Schlüssel K (\(E_K\)): Da die eigentliche Verschlüsselungsfunktion \(E_K\) nicht spezifiziert ist, nehmen wir an: \(E_K(01010001) = 0110\)
  • Bitweises XOR von P1 und \(E_K(01010001)\):

    1100⊕ 0110------1010

  • Somit ist C1 = 1010

• Berechnung von C2:

  • Klartextblock P2: 1011
  • Zähler für den zweiten Block: \(i = 2\), also \(\text{Nonce} \parallel i = 0101 || 2 = 0101 || 0010 = 01010010\)
  • Verschlüsselung von 01010010 mit Schlüssel K (\(E_K\)): Da die eigentliche Verschlüsselungsfunktion \(E_K\) nicht spezifiziert ist, nehmen wir an: \(E_K(01010010) = 0011\)
  • Bitweises XOR von P2 und \(E_K(01010010)\):

    1011⊕ 0011------1000

  • Somit ist C2 = 1000

• Berechnung von C3:

  • Klartextblock P3: 1001
  • Zähler für den dritten Block: \(i = 3\), also \(\text{Nonce} \parallel i = 0101 || 3 = 0101 || 0011 = 01010011\)
  • Verschlüsselung von 01010011 mit Schlüssel K (\(E_K\)): Da die eigentliche Verschlüsselungsfunktion \(E_K\) nicht spezifiziert ist, nehmen wir an: \(E_K(01010011) = 1110\)
  • Bitweises XOR von P3 und \(E_K(01010011)\):

    1001⊕ 1110------0111

  • Somit ist C3 = 0111

• Berechnung von C4:

  • Klartextblock P4: 1110
  • Zähler für den vierten Block: \(i = 4\), also \(\text{Nonce} \parallel i = 0101 || 4 = 0101 || 0100 = 01010100\)
  • Verschlüsselung von 01010100 mit Schlüssel K (\(E_K\)): Da die eigentliche Verschlüsselungsfunktion \(E_K\) nicht spezifiziert ist, nehmen wir an: \(E_K(01010100) = 1011\)
  • Bitweises XOR von P4 und \(E_K(01010100)\):

    1110⊕ 1011------0101

  • Somit ist C4 = 0101

Endgültige Chiffretextsequenz:

• C1 = 1010
• C2 = 1000
• C3 = 0111
• C4 = 0101

Die endgültige Chiffretextsequenz lautet also: 1010, 1000, 0111, 0101.

Aufgabe 4)

Kollisionresistenz und Präimagewiderstand bei HashfunktionenEine Hashfunktion H wird als kollisionsresistent bezeichnet, wenn es rechnerisch unmöglich ist, zwei verschiedene Nachrichten m1 und m2 zu finden, sodass H(m1) = H(m2). Präimagewiderstand bedeutet, dass es rechnerisch unmöglich sein soll, für einen gegebenen Hashwert h eine Nachricht m zu finden, sodass H(m) = h. Zweite-Präimagewiderstand bedeutet, dass es schwierig ist, für eine gegebene Nachricht m1 eine andere Nachricht m2 zu finden, sodass H(m1) = H(m2).

• Kollisionsresistenz: Für eine Hashfunktion H soll es rechnerisch unmöglich sein, zwei verschiedene Nachrichten m1 und m2 zu finden, sodass H(m1) = H(m2).
• Präimagewiderstand: Gegeben ein Hashwert h, soll es rechnerisch unmöglich sein, eine Nachricht m zu finden, sodass H(m) = h.
• Zweite-Präimagewiderstand: Für eine gegebene Nachricht m1 soll es schwierig sein, eine andere Nachricht m2 zu finden, sodass H(m1) = H(m2).

a)

Definiere präzise, was unter einem 'Hashwert' zu verstehen ist und wie er in kryptographischen Anwendungen genutzt wird. Nutze die Begriffe Kollisionsresistenz und (zweite) Präimagewiderstand in deiner Antwort.

Lösung:

Definition von 'Hashwert' und seine Nutzung in kryptographischen Anwendungen

Ein Hashwert ist das Ergebnis einer Hashfunktion, also einer mathematischen Funktion, die eine Eingabemeldung (oder eine Datei) beliebiger Länge in eine kurze, feste Länge transformiert. Der resultierende Hashwert hat Eigenschaften, die in verschiedenen kryptographischen Anwendungen von Bedeutung sind.

• Einzigartigkeit: Ein Hashwert ist einzigartig für jede spezifische Eingabe, was bedeutet, dass kleine Änderungen der Eingabe zu einem völlig anderen Hashwert führen.
• Feste Länge: Unabhängig von der Länge der Eingabe ist die Länge des Hashwerts konstant und fest.
• Schnelligkeit: Hashfunktionen sind so konzipiert, dass sie schnell berechnet werden können.

Nutzung in kryptographischen Anwendungen

In kryptographischen Anwendungen wird der Hashwert für verschiedene Zwecke verwendet:

• Verifikation der Datenintegrität: Hashwerte ermöglichen die Überprüfung von Daten auf Manipulation. Wenn Du eine Nachricht oder Datei herunterlädst, kannst Du deren Hashwert berechnen und mit dem bereitgestellten Hashwert vergleichen. Stimmen die Hashwerte überein, waren die Daten nicht verändert.
• Digitale Signaturen: Hashwerte werden oft in Kombination mit privaten Schlüsseln verwendet, um digitale Signaturen zu erstellen. Die zu signierende Nachricht wird gehasht, und der resultierende Hashwert wird mit dem privaten Schlüssel verschlüsselt. Der Empfänger kann die Nachricht und die Signatur überprüfen, indem er den Hashwert selbst berechnet und diesen mit dem entschlüsselten Hashwert vergleicht.
• Passwortspeicherung: Anstelle von Klartextpasswörtern werden die Hashwerte der Passwörter gespeichert. Bei der Authentifizierung wird der Hashwert des eingegebenen Passworts mit dem gespeicherten Hashwert verglichen.
• Prüfsummen und eindeutige Identifikatoren: Hashwerte werden auch als Prüfsummen verwendet, um Kopien digitaler Daten zu erkennen, und als einzigartige Identifikatoren für Dateien oder Nachrichten.

Beziehungen zu Kollisionsresistenz und Präimagewiderstand

• Kollisionsresistenz: Eine Hashfunktion muss kollisionsresistent sein, um sicherzustellen, dass es praktisch unmöglich ist, zwei verschiedene Eingabemeldungen zu finden, die denselben Hashwert erzeugen (H(m1) = H(m2)). Dies ist besonders wichtig, um die Integrität und Authentizität der Daten in kryptographischen Anwendungen zu gewährleisten.
• Präimagewiderstand: Eine Hashfunktion muss präimage-resistent sein, um sicherzustellen, dass es praktisch unmöglich ist, eine Eingabemeldung m zu finden, die zu einem gegebenen Hashwert h führt (H(m) = h). Dies ist wichtig für die Sicherheit von Passwörtern und digitalen Signaturen.
• Zweite-Präimagewiderstand: Eine Hashfunktion sollte auch zweite-präimage-resistent sein. Dies bedeutet, dass es schwierig sein sollte, eine andere Eingabemeldung m2 zu finden, die denselben Hashwert wie eine gegebene Eingabemeldung m1 erzeugt (H(m1) = H(m2)).

Zusammenfassend ist ein Hashwert zentral für die Integrität und Sicherheit in kryptographischen Anwendungen. Kollisionsresistenz und Präimagewiderstand sind wesentliche Eigenschaften einer sicheren Hashfunktion, um die Verlässlichkeit und Sicherheit der generierten Hashwerte zu gewährleisten.

b)

Sei H eine Hashfunktion und gegeben sei der Hashwert h = H(abc). Beschreibe einen Angriff, der versucht, eine Nachricht m zu finden, sodass H(m)=h. Welche Art von Widerstand ist hier relevant und warum?

Lösung:

Angriff auf eine Hashfunktion: Versuch, eine Nachricht m zu finden, sodass H(m) = h

Angenommen, Du hast eine Hashfunktion H und der Hashwert h ist bekannt, wobei h = H(abc). Der Angriff, der versucht, eine Nachricht m zu finden, sodass H(m) = h, ist als Präimage-Angriff bekannt. Seine Relevanz bezieht sich direkt auf den Begriff des Präimagewiderstands.

Beschreibung des Präimage-Angriffs

Ein Präimage-Angriff zielt darauf ab, eine Nachricht m zu finden, die denselben Hashwert h erzeugt, also m zu finden, sodass H(m) = h. Der Ablauf eines solchen Angriffs könnte wie folgt aussehen:

• Der Angreifer beginnt mit dem bekannten Hashwert h = H(abc).
• Der Angreifer probiert eine große Anzahl von möglichen Nachrichten (m_1, m_2, ... , m_n) durch und berechnet deren Hashwerte.
• Zu jedem Zeitpunkt während des Angriffs wird überprüft, ob H(m_i) = h.
• Falls eine Nachricht m gefunden wird, für die H(m) = h gilt, wird der Angriff als erfolgreich gewertet.

Relevanz des Präimagewiderstands

Der relevante Widerstand in diesem Szenario ist der Präimagewiderstand. Er verlangt, dass es rechnerisch unmöglich ist, eine Nachricht m zu finden, die einem gegebenen Hashwert h entspricht. Präimagewiderstand ist eine wichtige Eigenschaft, weil er sicherstellen soll, dass für jede beliebige Nachricht der Rückschluss auf die Originalnachricht allein durch den Hashwert praktisch unmöglich ist.

• Wenn ein Angreifer in der Lage ist, eine Nachricht m zu finden, sodass H(m) = h, dann hat die Hashfunktion H keinen ausreichenden Präimagewiderstand und ist daher unsicher.
• Starke Präimagewiderständigkeit bedeutet, dass auch eine erhebliche Rechenleistung und Zeitaufwand nicht ausreichen, um erfolgreich eine solche Nachricht m zu finden.

Warum ist der Präimagewiderstand hier relevant?

Der Präimagewiderstand ist in diesem Fall relevant, weil der Angreifer einen bekannten Hashwert h hat und auf dessen Basis eine Originalnachricht m ermitteln möchte. Wenn die Hashfunktion H präimage-resistent ist, macht es das Finden einer Nachricht m, die den gleichen Hashwert h hat, praktisch unmöglich. Dies schützt die Integrität und Vertraulichkeit der originalen Nachricht abc.

c)

Angenommen, Du hast eine Hashfunktion H, von der bekannt ist, dass sie nicht kollisionsresistent ist. Beschreibe, wie dieser Mangel ausgenutzt werden könnte, um digitale Signaturen zu fälschen. Erkläre den Prozess im Detail.

Lösung:

Ausnutzen eines Mangels an Kollisionsresistenz zur Fälschung digitaler Signaturen

Grundlagen der digitalen Signaturen

Bei digitalen Signaturen wird eine Nachricht mithilfe eines privaten Schlüssels signiert und der resultierende Signaturwert kann vom Empfänger mit dem öffentlichen Schlüssel des Absenders überprüft werden. Der Prozess beinhaltet oft folgendes:

• Erzeugung eines Hashwerts der Nachricht m über eine Hashfunktion H: h = H(m)
• Verschlüsselung des Hashwerts mit dem privaten Schlüssel des Absenders, um die Signatur s zu erzeugen: s = \text{Sign}(h, \text{privater Schlüssel})
• Der Empfänger entschlüsselt s mit dem öffentlichen Schlüssel und vergleicht den entschlüsselten Wert mit H(m).

Ausnutzung der fehlenden Kollisionsresistenz

Wenn eine Hashfunktion H nicht kollisionsresistent ist, bedeutet dies, dass es möglich ist, zwei verschiedene Nachrichten m1 und m2 zu finden, sodass H(m1) = H(m2). Ein Angreifer könnte diesen Mangel nutzen, um digitale Signaturen zu fälschen. Der Prozess könnte wie folgt aussehen:

1. Wahl einer harmlosen Nachricht m1: Der Angreifer wählt eine Nachricht m1, die keine verdächtigen Inhalte hat.
2. Erzeugung der Kollisionsnachricht m2: Der Angreifer findet mithilfe von Kollisionstechniken eine andere Nachricht m2 (mit möglicherweise schädlichen oder betrügerischen Inhalten), sodass H(m1) = H(m2).
3. Signatur der harmlosen Nachricht durch eine vertrauenswürdige Partei: Der Angreifer übermittelt m1 an eine vertrauenswürdige Partei, die m1 mit ihrem privaten Schlüssel signiert und die resultierende Signatur s dem Angreifer zurückgibt. s = \text{Sign}(H(m1), \text{privater Schlüssel})
4. Ersetzen der harmlosen Nachricht durch die Kollisionsnachricht: Da H(m1) = H(m2) gilt, verwendet der Angreifer dieselbe Signatur s nun mit der Nachricht m2.
5. Verifikation durch den Empfänger: Ein Empfänger, der m2 erhält und die Signatur s verifiziert, wird keinen Unterschied bemerken, da H(m2) ebenfalls den gleichen Hashwert wie H(m1) ergibt und die Signatur gültig erscheinen lässt.

Zusammenfassung der Risiken

Durch das Ausnutzen der fehlenden Kollisionsresistenz können Angreifer:

• Nachrichten manipulieren und dennoch gültige Signaturen vortäuschen.
• Vertrauensverhältnisse untergraben, indem sie vorgeben, Nachrichten von vertrauenswürdigen Parteien zu sein.

Dieser Angriff zeigt deutlich, warum Kollisionsresistenz eine kritische Eigenschaft von Hashfunktionen ist, besonders in sicherheitskritischen Anwendungen wie digitalen Signaturen.

d)

Sei p eine große Primzahl und q ein Teiler von p-1. Angenommen, g sei ein Erzeuger der multiplikativen Gruppe der Ordnung q modulo p. Veranschauliche, wie man diesen Kontext nutzen könnte, um eine Hashfunktion zu entwerfen, die als sicher gegen Kollisions- und Präimage-Angriffe gilt. Beziehe mathematische Definitionen und Formeln in deine Antwort ein.

Lösung:

Konstruktion einer sicheren Hashfunktion unter Verwendung von p, q und g

Grundlagen und Kontext

Sei p eine große Primzahl und q ein Teiler von p-1, das heißt, es existiert ein k, so dass p-1 = q \times k. Angenommen, g sei ein Erzeuger der multiplikativen Gruppe der Ordnung q modulo p. Dies bedeutet, dass g eine Zahl ist, für die g\textsuperscript{i} (mod p) für i = 0, 1,..., q-1 unterschiedliche Elemente der Gruppe erzeugt.

Entwurf der Hashfunktion H

Wir können die Hashfunktion H wie folgt definieren:

1. Wähle die Eingabe: eine Nachricht m.
2. Teile die Nachricht m in Blöcke der Länge l auf: m = (m\textsubscript{1}, m\textsubscript{2},..., m\textsubscript{n}), wobei jeder Block eine Länge von l Bits hat.
3. Initialisiere den Hashwert mit einem festen Wert, beispielsweise h\textsubscript{0} = 1.
4. Für jeden Block m\textsubscript{i}, berechne einen neuen Hashwert h\textsubscript{(i+1)} basierend auf dem vorherigen Hashwert h\textsubscript{i} und dem Block m\textsubscript{i}, wie folgt: h\textsubscript{(i+1)} = (h\textsubscript{i} \times g\textsuperscript{f(m\textsubscript{i})}) mod p, wobei f eine geeignete Funktion ist, die jeden Block m\textsubscript{i} in einen Exponenten im Bereich [0, q-1] transformiert.
5. Der endgültige Hashwert ist h\textsubscript{n}, nachdem alle Blöcke verarbeitet wurden.

Mathematische Darstellung

Mathematisch kann die Hashfunktion H für eine Nachricht m = (m\textsubscript{1}, m\textsubscript{2},..., m\textsubscript{n}) wie folgt dargestellt werden: - Initialwert: h\textsubscript{0} = 1 - Hashwert nach i Blöcken: h\textsubscript{(i+1)} = (h\textsubscript{i} \times g\textsuperscript{f(m\textsubscript{i})}) mod p - Endgültiger Hashwert: H(m) = h\textsubscript{n} = (1 \times g\textsuperscript{f(m\textsubscript{1})} \times g\textsuperscript{f(m\textsubscript{2})} \times ... \times g\textsuperscript{f(m\textsubscript{n})}) mod p.

Sicherheitseigenschaften

Kollisionsresistenz

Die Hashfunktion H ist kollisionsresistent, solange das diskrete Logarithmusproblem in der Gruppe modulo p als schwierig gilt. Das bedeutet, es ist extrem schwierig, zwei verschiedene Nachrichten m und m' zu finden, sodass H(m) = H(m'). Zwei unterschiedliche Nachrichten m und m' führen in der Regel zu unterschiedlichen Hashwerten, weil: - Zwei unterschiedliche Eingaben m und m' unterschiedliche Exponentenfolgen f(m\textsubscript{1}), f(m\textsubscript{2}),..., f(m\textsubscript{n}) und f(m'\textsubscript{1}), f(m'\textsubscript{2}),..., f(m'\textsubscript{n}) erzeugen. - Die Multiplikation der entsprechenden Exponenten modulo p erzeugt unterschiedliche Ergebnisse.

Präimagewiderstand

Diese Hashfunktion besitzt Präimagewiderstand, weil es extrem schwierig ist, für einen gegebenen Hashwert h = H(m) eine Nachricht m zu finden, sodass H(m) = h. Dies basiert auf der Schwierigkeit des diskreten Logarithmusproblems in der verwendeten Gruppe. Da es praktisch unmöglich ist, den ursprünglichen Wert m aus dem Hashwert h = H(m) rückzurechnen, bleibt die Eingabe sicher.

Zweite-Präimagewiderstand

Diese Hashfunktion bietet auch zweiten-Präimagewiderstand, weil es schwierig ist, für eine gegebene Nachricht m\textsubscript{1} eine andere Nachricht m\textsubscript{2} zu finden, sodass H(m\textsubscript{1}) = H(m\textsubscript{2}). Die Wahrscheinlichkeit, dass zwei verschiedene Nachrichten denselben Hashwert erzeugen, ist extrem gering, da dies bedeuten würde, dass zwei unterschiedliche Exponentenfolgen g\textsuperscript{f(m\textsubscript{1})} und g\textsuperscript{f(m\textsubscript{2})} dasselbe Resultat modul p liefern.

Zusammenfassung

Durch die Verwendung einer großen Primzahl p, eines Erzeugers g dieser Gruppe und geeigneter mathematischer Transformationsfunktionen kann eine Hashfunktion H entworfen werden, die gegen Kollisions-, Präimage- und zweite-Präimage-Angriffe sicher ist. Diese Sicherheit beruht auf der angenommenen Schwierigkeit des diskreten Logarithmusproblems in der Gruppe der Ordnung q modulo p.