Eine Hashfunktion ist eine Abbildung, welche eine beliebige Input String auf einen String mit fixer länge abbildet.

\(h: K \rightarrow S\)

Wobei die Menge K die Daten repräsentiert und S die Menge der Möglichen Hashwerte

Ein einfaches Beispiel Quersumme:

\(42 \rightarrow 6 = 4 + 2\)

• Eine Hashfunktion muss auf eine beliebige Menge an Daten angewendet werden können.
• Eine Hashfunktion muss Output einer fixen Länge produzieren
• Wenn man die Hashfunktion H hat und einen Input x, muss die Berechnung von H(x) einfach sein

Eigenschaften von Kryptologischen Hash Funktionen

• Wenn man H und H(x) kennt sollte es unmöglich sein x zu berrechnen.
• Hohe Kollisionsresistenz: Wenn man H und H(x) kennt soll es unmöglich sein zwei Inputs zu berechnen bei denen gilt: \(H(x)=H(x')\)

• Datenbanken: Suche von Daten per Hashtabelle
• Prüfsumme:
  • Erkennung von Veränderung von Datensätzen (Übertragungen)
  • Quersumme
  • Hashtree
• Kryptographie:
  • Hashing von Passwörtern
  • Digitale Signaturen

Welche Eigenschaften einer Hashfunktion nutzt man, wenn man Passwörter gehashed abspeichert.

• Divisionsmethode: \(h(k) = k % m\)
• Zerlegungsmethode:
  • Zerlegung des Schlüssels bis gültige Adresse vorhanden ist:
  • h(135612) = [13] + [56] + [12] = 81 = [8] + [1] = 9

Kryptologische Hashfunktionen

• MD5
• SHA1, SHA2, SHA3
• PBKDF2

Kryptografische Hash Funktionen nie selber implementieren!

Am besten Hash Funktionen verwenden, welche über die Standard Library der jeweiligen Sprache bereit gestellt wird.

In Python:

import hashlib
m = hashlib.sha256()
m.update(b"Nobody inspects")
m.update(b" the spammish repetition")
print(m.hexdigest())

## 031edd7d41651593c5fe5c006fa5752b37fddff7bc4e843aa6af0c950f4b9406

import hashlib
for a in hashlib.algorithms_guaranteed:
  print(a)

## sha1
## md5
## sha224
## sha256
## sha3_384
## shake_128
## sha384
## blake2b
## sha3_224
## sha3_256
## shake_256
## sha512
## blake2s
## sha3_512

import hashlib
def hashFor(data):
    # Prepare the project id hash
    hashId = hashlib.md5()
    hashId.update(repr(data).encode('utf-8'))
    return hashId.hexdigest()
if __name__ == '__main__':
    data1 = ['abc', 'de']
    data2 = ['a', 'bcde']
    print(hashFor(data1) + ':', data1)
    print(hashFor(data2) + ':', data2)

## d26d27d8cbb7c6fe50637155c21d5af6: ['abc', 'de']
## dbd5ab5df464b8bcee61fe8357f07b6e: ['a', 'bcde']

import uuid
import hashlib
def hash_password(password):
    # uuid is used to generate a random number
    salt = uuid.uuid4().hex
    return hashlib.sha256(salt.encode() + password.encode()).hexdigest() + ':' + salt
    
def check_password(hashed_password, user_password):
    password, salt = hashed_password.split(':')
    return password == hashlib.sha256(salt.encode() + user_password.encode()).hexdigest()
 
new_pass = input('Please enter a password: ')
hashed_password = hash_password(new_pass)
print('The string to store in the db is: ' + hashed_password)
old_pass = input('Now please enter the password again to check: ')
if check_password(hashed_password, old_pass):
    print('You entered the right password')
else:
    print('I am sorry but the password does not match')

Lesen Sie das verteilte Review zu Hash Funktionen und probieren Sie mögliche Attacken auf Hash Funktionen zu verstehen.

Für einen Hash den Input herausfinden.

schwierig \(h(x) = y\) herauszufinden, wenn y bekannt ist.

Einen neuen Input, wenn der Input bekannt ist, finden welcher den selben Hashwert hat.

schwierig \(x \neq x'\) \(h(x) = h(x')\) herauszufinden, wenn x bekannt ist.

Herausfinden ob 2 Dokumente auf den selben Hash Wert abgebildet werden. Im Unterschied zu 2nd Pre-Image Attacke sind dabei beide Inputs frei wählbar.

SHA1 hat einen output von 160bit. Daher \(2^{160}\) mögliche Hashwerte. Bei einer Bruteforce Attake muss daher \(2^{160}\) Werte ausprobiert werden. Bei \(1'000'000'000\) Operationen pro Sekunde würde dies ca. \(4.6 * 10^{31}\) Jahre benötigen.

Geburtstags Angriff

Hierbei werden 2 zufällige Dokumente ausgewählt, deren Hashwert berechnet und überprüft ob dieser identisch ist. Für eine Erfolgswahrscheinlichkeit von 50% müssen dann nur noch \(1.18*10^{80}\) Versuche durchgeführ werden. Die Laufzeit würde hierfür nur noch \(4.5*10^7\) Jahre betragen.

Alle Hash funktionen haben einen Output mit einer fixen Länge. Oft 128, 256, 512. Man kann pysikalisch nachweisen, dass eine Brute-Force Attacke auf 256 Bits lange Hash Werte unmöglich ist.

Basierend auf dem Zweiten Hauptsatz der Thermodynamik benötigt das Speichern von Informationen Energie. Für einen Bit-Wechsel ist eine Energie von \(kT\) erforderlich. T ist dabei die absolute Temperatur und k die Boltzmann Konstante.

Mit der Boltzmann Konstante \(k=1.38×10^{-23} J/K\) und der Temperatur des Universums \(T=3.2K\) würde ein perfekter Computer \(4.4×10^{-23}J\) für jeden Bitwechsel benötigen. Die Sonne produziert \(1.21×10^{34}J/a\) Energie. Damit könnten man \(2.7×10^{56}\) Bitwechsel in einem perfekten Computer durchführen. Das würde reichen um 187-bit durch alle Werte zu interieren. Eine Supernove Explosion erzeugt \(2×10^{44}J\), was reichen würde um einen 219bit Wert durch alle Werte zu iterieren.

• Implementieren Sie niemals einen Sicherheitsrelevanten Hash Algorithmus selber!!!!
• Überlegen Sie sich welchen Hash Algorithmus Sie verwenden.