Hallo liebe Steemians,

in diesem Teil geht um die Einweg-Funktionen.
Jeder, der in der Kryptoszene ein bisschen technisch unterwegs ist sollte hier genau aufpassen.
Erklärt werden unter anderem Hash-Funktionen, mit denen nahezu jedes Projekt in der Crypto-Szene arbeitet.

Daher möchte ich heute versuchen, euch dieses Thema ein bisschen näher zu bringen. Um da jedoch noch tiefer ins Detail zu gehen, würde den Rahmen hier auf Steemit ziemlich sprengen. Wer da näheres Interesse hat, sollte sich dann im www dazu ein bisschen umschauen.

Wer die vorangegangenen Posts nicht mitbekommen hat, kann diese hier nachlesen:

Teil 1: Einleitung & klassische Kryptographie
Teil 2: Modulare Arithmetik
Teil 3: Symmetrische Kryptographie #1
Teil 4: Symmetrische Kryptographie #2
Teil 5: Asymmetrische Kryptographie #1
Teil 6: Asymmetrische Kryptographie #2
Teil 7: Asymmetrische Kryptrographie #3
Teil 8: Elliptische Kurven

Einwegfunktionen

Funktionen, die nur in eine Richtung berechenbar sind, d.h.
f(x)⁻¹ existiert nicht, oder ist nicht ohne zusätzliche Informationen zu berechnen.

Prüfsummen

Verwendung zur Identifizierung/Korrektur von Bitfehlern
Keine kryptographische Relevanz, eignen sich daher nicht für Protokolle, denn Prüfsummen sind nicht kollisionsresistent.
Ein Angreifer kann leicht zwei Klartexte m1,m2 mit den selben Prüfsummen erzeugen.

Linearität von CRC-32

Definition 40: Homomorphie

Eine Funktion e auf der Menge A={a0,a1,...} ist homomorph, wenn für die Operation ° die folgende Abhängigkeit gilt:
    - Φ(a0 ° a1 ° ...) = Φ(a0) ° Φ(a1) ° ...

Die CRC-32 Prüfsumme ist linear, weil sie die Homomorphie-Eigenschaft erfüllt, d.h.
    CRC(A XOR B) = CRC(A) XOR CRC(B)

Beispiel: CRC-32 in WEP

Chiffrat c soll gegen Veränderungen geschützt werden
s ist der RC4 Schlüsselstrom

c = ( m || CRC(m) ) XOR s

Angriff:

Geg: c = (m || CRC(m) ) XOR s
Invertiere beliebige Bits in m -> m'
Ges: gültiges c' = (m' || CRC(m') ) XOR s

1. Invertierte Bits d = m XOR m'
2. Berechne CRC(d) 
3. Erzeuge c' = c                       XOR (d || CRC(d) )
              = ((m || CRC(m)) XOR s )  XOR (m XOR m' || CRC(m XOR m'))
              = (m' XOR CRC(m')) XOR s

Da für CRC-32 gilt: CRC(m') = CRC(m) XOR CRC(m XOR m'), funktiniert der Angriff

Hashfunktionen

Verwendung zur Identifizierung eines bestimmten Urbilds

Definition 41: Kryptographische Hashfunktionen

Eine Funktion, die eine Abbildung aus der Menge M={0,1}* in die Menge H={0,1}^n vornimmt.
    h = hashwert(m)     h∈H,m∈M

Eine kryptographische Hashfunktion erfüllt folgende Eigenschaften:
    1. Preimage Resistance      (Einweg-Eigenschaft)
       Gegeben h: Es ist schwer, ein m zu finden, für das gilt: h=Hash(m)
    2. Second Preimage Resistance   (Schwache Kollisionsresistenz)
       Gegeben m1: Es ist schwer, ein m2 zu finden, für das gilt: hash(m1) = hash(m2)
    3. Collision Resistance     (starke Kollisionsresistenz)
       Es ist schwer, ein m1 und m2 zu finden, für die gilt: m1 != m2 && Hash(m1) = Hash(m2)

Die Sicherheit einer iealen Hashfunktion ist abhängig von der Länge der Ausgabe(n) und reduzierbar auf den einfachsten Angriff (3.).
Wenn der Aufwand für 3. zu groß ist, dann erfüllt die Hashfunktion eine starke Kollisionsresistenz.

Wahrscheinlichkeit für Kollision:
Hashkollision
Pr("Hash-Kollision") = λ
Es benötigt ca t = 2^((n+1)/2) * √(ln(1 / (1-λ)))
Versuche, um eine Kollision mit Wahrscheinlichkeit λ zu finden

Konstruktion einer Hashfunktion nach dem Merkle-Damgard-Prinzip

Beschreibung:

f-Funktion (Kompressionsfunktion)
Wenn diese Kollisionssicher ist, ist auch H(m) Kollisionssicher
g-Funktion (Finalisierungsfunktion) (optional)
Sicheres Padding
Bei unterschiedlich langen Inputs werden unterschiedlich lange Paddings verwendet.

Message Authentication Codes (MAC)

MACs realisieren das Sicherheitsziel Integrity protection, jedoch nicht die non-repudiation Eigenschaft, wie digitale Signaturen.

Definition 42: Message Authentication Code (MAC)

Eine Hashfunktion, in die zusätzlich ein geheimer symmetrischer Schlüssel aus der Menge K={0,1}^m einfließt.
    h = MAC(m,k)        h∈H, m∈M, k∈K

Definition 43: HMAC

HMAC ist eine Konstruktion, die einen starken MAC erzeugt. Dabei wird eine beliebige Hashfunktion als Primitiv verwendet.

    HMAC(m,k) = Hash(k XOR opad, HASH(k XOR ipad,m))

Wobei ipad aus den Bytes "0x36" und opad aus den Bytes "0x5C" besteht

Definition 44: CBC-MAC

Der CBC-MAC verwendet eine Blockchiffre im CBC-Operationsmodus. Die Verschlüsselung der ersten n-1 Blöcke wird verworfen, der Hashwert/MAC h ist die Verschlüsselung des letzten Blocks m_n.

Ausblick

Im nächsten und letzten Teil meiner Kryptographie-Reihe werden wir uns noch ein paar spezielle Gebiete der Kryptographie anschauen. Es wird um formale Sicherheitsbeweise und die El-Gamal Verschlüsselung gehen.

Wie immer danke ich dir für dein Interesse. Wenn du Fragen zu einem Punkt hast, immer raus damit... Aufgrund der Komplexität des Themas ist es schwierig, dass in entsprechendem Umfang zu vermitteln, ohne den Rahmen komplett zu sprengen...

Natürlich bin ich immer froh über entsprechendes Feedback und natürlich auch ein Vote :)

[Kryptographie] Einweg-Funktionen