efinf:blc2016:krypto

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
efinf:blc2016:krypto [2017/01/17 07:24] – [Mathematische Grundlagen] Ivo Blöchligerefinf:blc2016:krypto [2017/01/26 08:30] (current) – Ivo Blöchliger
Line 1: Line 1:
 +{{backlinks>.}}
 +===== Prinzipien moderner Kryptographie =====
 +==== Zusammenfassung ====
  
 +  * Slides: {{ :efinf:blc2016:26.01.17_0742.pdf |}}
 + 
 +
 +Begriffe: 
 +  * **{{https://de.wikipedia.org/wiki/Kryptologie|Kryptologie}}** = {{https://de.wikipedia.org/wiki/Kryptographie|Kryptographie}} (Verschlüsseln) und {{https://de.wikipedia.org/wiki/Kryptoanalyse|Kryptoanalyse}} (gegnerisches Entschlüsseln)
 +  * Personen: **A**lice, **B**ob (legitime Kommunikationspartner), **E**ve (Evesdropper, Gegner) oder **M**allory {{https://de.wikipedia.org/wiki/Man-in-the-Middle-Angriff|Man-in-the-Middle}} (MITM)
 +
 +
 +
 +
 +==== 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):
 +  * Der Output ist "zufällig", d.h. die Änderung eines Bits im Input sollte "zufällig" etwa die Hälfte der Bits im Output ändern.
 +  * Es ist nicht möglich, zu einem gegebenen Output einen Input zu konstruieren (mal abgesehen von "alles durchprobieren", was einen Aufwand von ca. $2^{\ell-1}$ bedeutet).
 +  * Es ist nicht möglich, zu einem gegebenen Input einen zweiten Input zu kontruieren, der den gleichen Output hat.
 +  * Es ist nicht möglich, zwei (frei wählbare) Inputs mit gleichem Output zu konstruieren (mal abgesehen von "alles durchprobieren", was einen Aufwand von ca. $2^{\frac{ell}{2}}$ bedeutet).
 +
 +Je nach Anwendung kann auch gewünscht sein, dass die Erzeugung des Hashes rechenaufwendig sein muss.
 +
 +=== Konkrete Hashfunktionen (mit Kommandozeilenargument) ===
 +  * {{https://en.wikipedia.org/wiki/MD5|MD5}} (ist geknackt): ''md5sum''. Mögliche Anwendung: Dateien auf gleichen Inhalt prüfen, "Szenarien ohne Gegner".
 +  * {{https://en.wikipedia.org/wiki/SHA-1|SHA1}} (im Moment noch sicher, wird aber davon abgeraten): ''sha1sum''.
 +  * {{https://en.wikipedia.org/wiki/SHA-2|SHA-2}} SHA256 ''sha256sum'', SHA512 ''sha512sum''. Zur Zeit als sicher angesehene Hash-Funktionen.
 +  * {{https://en.wikipedia.org/wiki/SHA-3|SHA-3}} Neuste standardisierte Hashfunktionen. (Im package rhash: z.B. ''rhash --sha3-256''
 +
 +=== Aufgaben ===
 +  - Erzeugen Sie verschiedene Hashwerte einer Text-Datei (z.B. eines Ruby-Codes).
 +  - Kopieren Sie die Datei und ändern Sie genau 1 Bit (nicht 1 Byte!). Bestimmen Sie dann wieder die Hashwerte.
 +  - 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**:
 +  * Ein einzelnes Byte in einem String kann mit ''.getbyte(index)'' und ''.setbyte(index,byte)'' gelesen und gesetzt werden. Mit der XOR-Operation kann ein Bit umgelegt werden (z.B. i^0b100 legt das Bit 2 (drittes Bit) in der Zahl i um).
 +  * Ein String kann mit ''a=File.read("datei")'' gelesen und mit ''File.write("datei",a)'' geschrieben werden.
 +  * Ein Hashwert kann entweder über die Kommandozeile mit ''resultat = `sha256sum datei`'' berechnet werden. Das ist zwar sehr flexibel, aber auch sehr langsam (Datei schreiben, lesen, Kommando starten).
 +  * Ein Hashwert kann auch mit Ruby-Libraries berechnet werden, {{https://ruby-doc.org/stdlib-2.1.0/libdoc/digest/rdoc/Digest.html|siehe z.B. hier}}. Das ist sehr viel schneller.
 +  * Das Histogramm kann als csv-Datei exportiert werden, wobei jede Zeile so aussieht: '128;423' (Erster Eintrag: Anzahl Bits, zweiter Eintrag: Anzahl Vorkommnisse).
 +
 +<hidden Lösungsansatz>
 +Hinweis: Code herunterladen, nicht kopieren.
 +<code ruby 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}"
 +}
 +</code>
 +Das Historgramm kann wie folgt erzeugt werden:
 +<code bash>
 +ruby hashtest.rb > test.csv
 +libreoffice test.csv
 +</code>
 +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.
 +
 +{{:efinf:blc2016:histogramm-sha256.png?direct&200|}}
 +</hidden>
 +
 +=== Anwendungen ===
 +  * Abspeichern von Passwörtern. Nicht das Passwort sondern der Hash davon wird gespeichert. Einfach überprüfbar, Passwort kann nicht ermittelt werden. Problem: Im Fall von Datenreichtum (lies Datenleak) kann eine Dixionär-Attacke gefahren werden. State of the Art: {{https://blogs.dropbox.com/tech/2016/09/how-dropbox-securely-stores-your-passwords/|Verfahren von DropBox}}. Wie man es nicht tun sollte: {{https://en.wikipedia.org/wiki/Yahoo!_data_breaches|Yahoo}} (nur einer von ganz vielen). Und zur Erheiterung: {{https://www.heise.de/newsticker/meldung/hallo-ist-meistgenutztes-deutsches-Passwort-auf-Platz-zehn-steht-ficken-3579567.html|häufigste deutsche Passwörter}} und {{http://www.passwordrandom.com/most-popular-passwords|weltweit}}.
 +  * Integrität einer Datei überprüfen (nur sinnvoll im Szenario ohne Gegner). Damit können Übertragungsfehler festgestellt werden. Ein Gegner könnte wohl auch den Hash anpassen. Lösung: Hash muss digital unterschrieben werden.
 +  * Forensik: Vor der Analyse eines Datenträgers werden Hashwerte davon hinterlegt. (Damit nachträglich Manipulation festgestellt werden könnte).
 +  * Digitale Unterschrift: Anstatt das ganze Dokument zu signieren, wird der Hash davon signiert (ist erheblich schneller).
 +  * Blockchain, für z.B. Bitcoins.
 +  * Überprüfen von Plagiaten. Nicht die Inhalte sondern Hashes (wahrscheinlich von Sätzen, Abschnitten, Seiten, ganzer Text) werden gespeichert. Beim Wiederfinden dieser Hashes kann auf die Original-Arbeit verwiesen werden.
 +
 +=== 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:
 +  - Starte mit einem Passwort $x$.
 +  - Speichere das Passwort $x$
 +  - Für $i$ von 0 bis $(n-1)$ mal (so $10^4$ oder so): $x := p_i(h(x))$
 +  - Speichere $h(x)$
 +  - Wiederhole ab Schritt 2.
 +
 +Entschlüsseln eines Passworts, gegeben Hash $y$.
 +  - Für $j$ von $n$ bis zu 0 hinunter:
 +    - Fasse $h$ als Eintrag in Spalte $j$ auf und rechne die Kette zu Ende (beginnend mit $p_j(h)$).
 +    - 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 ===
 +<hidden Code zur Abschätzung des Rechenaufwands>
 +<code ruby 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
 +
 +
 +</code>
 +</hidden>
 +===== Public-Private Key Encryption =====
 +
 +{{ :efinf:blc2016:17.01.17_1355.pdf |}}
 +
 +==== Mathematische Grundlagen ====
 +  * Rechnen in Restklassen: Nach jeder Operation wird der Rest modulo n (der Modulus) gerechnet.
 +  * Potenzieren in $\mathbb{Z} / n\mathbb{Z}$ (d.h. modulo n).
 +  * Diskreter Logarithmus ist schwierig
 +
 +$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 ===
 +  * **Input** $b$, $e$, $n$
 +  * **Output** $r=b^e \mod n$
 +  * $r=1$
 +  * Solange $e \neq 0$:
 +    * Falls Bit 0 von $e$ gesetzt (d.h. wenn ''e & 1 == 1'')
 +      * $r := r \cdot b \mod n$
 +    * $e := e/2$ (bzw. ''e= e >> 1'')
 +    * $b := b^2 \mod n$
 +  * Resultat ist $r$
 +
 +<hidden Ruby-Code>
 +<code ruby 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
 +</code>
 +</hidden>
 +==== 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) ====
 +<code bash>
 +# 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
 +
 +
 +</code>
 +
 +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: 
 +  * Austausch über weiteren Kanal (z.B. in Person, Austausch auf Papier).
 +  * Zertifizierung über vertrauenswürdige Drittstelle. Diese signiert, dass der Schlüssel zur Person (oder Server) gehört. 
 +
 +
 +==== OTR, Deniability, Forward Secrecy ====
 +  * https://en.wikipedia.org/wiki/Off-the-Record_Messaging