Table of Contents

Prinzipien moderner Kryptographie

Zusammenfassung

Begriffe:

Hash-Funktionen

Eine Hash-Funktion verarbeitet eine Bitfolge beliebiger Länge (Input) reproduzierbar zu einer Bitfolge konstanter Länge $\ell$ (Output). Gewünschte Eigenschaften einer kryptographisch nutzbaren Hashfunktion (im Regelfall nicht beweisbar):

Je nach Anwendung kann auch gewünscht sein, dass die Erzeugung des Hashes rechenaufwendig sein muss.

Konkrete Hashfunktionen (mit Kommandozeilenargument)

Aufgaben

  1. Erzeugen Sie verschiedene Hashwerte einer Text-Datei (z.B. eines Ruby-Codes).
  2. Kopieren Sie die Datei und ändern Sie genau 1 Bit (nicht 1 Byte!). Bestimmen Sie dann wieder die Hashwerte.
  3. Schreiben Sie ein Ruby-Programm, das für einen gegebenen Text den Hashwert berechnet und dann für alle Bit-Folgen, die sich um genau ein Bit vom gegebenen Text unterscheiden. Berechnen Sie dann die Anzahl Bits, um die sich die neuen Hashwerte vom Original-Hashwert unterscheiden und erzeugen Sie daraus ein Histogramm.

Hilfestellungen zu Punkt 3:

Lösungsansatz

Lösungsansatz

Hinweis: Code herunterladen, nicht kopieren.

hashtest.rb
require 'digest'
 
# s: String, bit: nummer
def flipBit(s, bit)
    # Kopie von s
    s = String.new(s)
    byte = bit/8;
    bit = bit%8;
    s.setbyte(byte,
      s.getbyte(byte)^(1 << bit))
    return s
end
 
# s1,s2: Zwei gleich lange Strings
def count_bit_diff(s1,s2)
    diff = 0
    s1.size.times{|i|
      xor = s1.getbyte(i)^s2.getbyte(i)
      # Ganzzahl: 1 Byte
      8.times{|bit|
        diff+=1 if (xor & (1<<bit))!=0
      }
    }
    return diff
end
 
text = File.read("hashtest.rb")
hash_orig = Digest::SHA256.digest(text)
counters = Array.new(256,0)
(text.size*8).times{|bit|
    modif = flipBit(text, bit);
    hash_modif = Digest::SHA256.digest(modif)
    counters[count_bit_diff(hash_orig, hash_modif)]+=1
}
 
# Generate CSV-Output
counters.each_with_index{|c,i|
        puts "#{i};#{c}"
}

Das Historgramm kann wie folgt erzeugt werden: 

ruby hashtest.rb > test.csv
libreoffice test.csv

In LibreOffice ist der Strichpunkt (Semicolon) als Trennzeichen zu wählen. Das Histogramm kann als Balkendiagramm erzeugt werden, wobei die erste Spalte als Labels verwendet wird.

Anwendungen

Rainbow-Tables

Trade-Off: Speicherplatz/Rechenpower.

Zutaten: Bakannte Hash-Funktion $h(s)$, Spezielle Hash-ähnliche Funktionen $p_i(h)$, die aus Hashes Passwörter generieren. Diese Funktionen können einander sehr ähnlich sein. Z.B. fassen die Funktionen den Hash als Ganzzahl auf, rechnen i dazu und dann modulo die Anzahl Passwörter im betrachteten Passwortraum und liefern das entsprechende Passwort (z.B. 0 ist 'aaaaa').

Generierung der Tabelle:

  1. Starte mit einem Passwort $x$.
  2. Speichere das Passwort $x$
  3. Für $i$ von 0 bis $(n-1)$ mal (so $10^4$ oder so): $x := p_i(h(x))$
  4. Speichere $h(x)$
  5. Wiederhole ab Schritt 2.

Entschlüsseln eines Passworts, gegeben Hash $y$.

  1. Für $j$ von $n$ bis zu 0 hinunter:
    1. Fasse $h$ als Eintrag in Spalte $j$ auf und rechne die Kette zu Ende (beginnend mit $p_j(h)$).
    2. Wenn das Ende der Kette in der Tabelle vorkommt, die ganze Kette neu rechnen. Hoffen, dass der gesuchte Hash in der Kette ist (es ist nicht unwahrscheinlich, dass zwei verschiedene Startpasswörter zum gleichen Hash am Ende führen).

Ursprünglich hatte man diverse Tabellen mit unterschiedlichen Reduktionsfunktionen $p_i(h)$, um das Zusammenlaufen von Ketten zu vermeiden.

Siehe http://lasec.epfl.ch/pub/lasec/doc/Oech03.pdf (ist offenbar eine Erfindung aus Lausanne ;-))

Spielzeug Beispiel

Code zur Abschätzung des Rechenaufwands

Code zur Abschätzung des Rechenaufwands

rainbowtable.rb
require 'digest'
 
# Passwords are 7 lower case letters a-z
# Hash is SHA256
 
# Makes a password out of a hex hash
def makePW(hash, n=7)
  z = hash.to_i(16)
  pw = ""
  n.times{
    pw += (z % 26 + 'a'.ord).chr
    z/=26
  }
  return pw
end
 
#Random password (for starting a chain)
def randPass(n=7)
  Array.new(n){('a'.ord+rand(26)).chr}.join  
end
 
# Check, how many hashes per second/minute/hour can be computed
def speedTest(n=5)
  text = "a"*5
  n = 26**text.size
  start = Time.now
  n.times {
    Digest::SHA256.hexdigest(text)
    text.succ!
  }
  total = Time.now-start
  puts "#{n} Hashes in #{total} secs."
  puts "Makes #{(n/total).to_i} hashes/s"
  puts "Makes #{(n/total*60).to_i} hashes/min"
  puts "Makes #{(n/total*3600).to_i} hashes/h"
end

Public-Private Key Encryption

17.01.17_1355.pdf

Mathematische Grundlagen

$b^e \mod n$ effizient ausrechnen. Annahme: $e$ liegt im Zweiersystem vor, z.B. 0b10001011. Dann ist $$b^e = b^{1+2+8+128} = b^1 \cdot b^2 \cdot b^8 \cdot b^{128}$$

Die Potenzen $b^2$, $b^4$, $b^8$, $b^{16}$, etc. können durch wiederholtes quadrieren erhalten werden.

Pseudo-Code zum Potenzieren

Ruby-Code

Ruby-Code

modpow.rb
def modpow(b,e,n)
  res = 1
  while (e>0)
    if e & 1 == 1
      res = (res*b)%n
    end
    e = e >> 1
    b=(b*b)%n
  end
  return res
end

Diffie-Hellmann Key-Exchange

Achtung: Nicht jede Primzahl und nicht jede Basis ist dafür geeignet. Die sollten sorgfältig ausgewählt werden, was Rechenaufwand bedeutet. Das ist der Grund, warum viele Internetdienste gleiche Primzahlen und Basen verwenden.

Siehe z.B. https://de.wikipedia.org/wiki/Diffie-Hellman-Schl%C3%BCsselaustausch

RSA-Schlüssel zum Spielen (hier 32 Bit, bietet keine Sicherheit)

# 32 bit Schlüssel generieren
openssl genrsa 32 > key.pem
 
# Daten anzeigen (dezimal und hexadezimal)
openssl rsa -text -noout < key.pem
 
# Public key schreiben
openssl rsa -in key.pem -outform PEM -pubout > public.pem

Zutaten: Modulus $n$ (Produkt zweier Primzahlen), öffentlicher Exponent $o$ (normalerweise 65537 = 0x10001), privater Exponent $p$.

Eigenschaft: $$\left(x^o\right)^p \mod n= x \mod n = \left(x^p\right)^o \mod n$$

Public/private-Key Verschlüsselung

Grundlage: Zwei Schlüssel, einer privat, einer öffentlich. Was mit dem einen verschlüsselt wird, kann nur mit dem anderen Schlüssel entschlüsselt werden.

Verschlüsselung

Alice verschlüsselt mit dem öffentlichen Schlüssel von Bob. Nur Bob kann die Nachricht mit seinem privaten Schlüssel lesen.

Effektiv wird normalerweise ein Schlüssel für ein symmetrisches Verfahren (typischerweise AES) verschlüsselt und dann die Nachricht damit.

Digitale Unterschrift

Alice verschlüsselt mit ihrem privaten Schlüssel. Bob entschlüsselt mit dem öffentlichen Schlüssel von Alice. Bob weiss, dass nur Alice diesen Text/Dokument verschlüsselt haben kann.

Effektiv wird normalerweise nur ein Hash der Nachricht verschlüsselt.

Authentifizierung

Zuordnung Schlüssel-Person (oder Server) muss überprüft werden. Ansätze:

OTR, Deniability, Forward Secrecy