Warnung: was hier gemacht wird ist mehr oder weniger Spass, es erhebt keinen Anspruch auf cryptographische Sicherheit. Die gelieferten Erklärungen bewegen sich ebenfalls stark an der Oberfläche, um es Einsteigern nicht zu schwer zu machen - wer sich intensiver mit dem Thema beschäftigen möchte sei auf die einschlägige Literatur verwiesen.
Hash: eine Funktion, die einen Datenstrom beliebiger Länge in eine Zahl fester Länge verwandelt. Hashes werden oft als Checksummen oder zur Beschleunigung von Suchen in großen Datenbeständen benutzt. Dabei kann eine spezifische Nachricht (Datenstrom) nur in einen Hash (vom selben Typ) verwandelt werden - ein einzelner Hash kann aber auf unendlich viele Nachrichten passen.
Message Digest oder Cryptographischer Hash: ein Hash, der es sehr schwer (mgl. in der Praxis unmöglich) macht a) zu einem gegeben Hash eine passende Nachricht zu finden und (pre-image attack) b) zwei unterschiedliche Nachrichten mit dem selben Hash zu finden (collision attack).
Message Digests (MDs) sind die am häufigsten gebrauchten und am wenigsten verstandenen cryptographischen Primitive des Planeten...
Alle hier benötigten Sourcen sind frei im Netz zu finden. Für meine Beispiele habe ich die SHA-2 Implementation von Dr. Brian Gladman benutzt.
Dr. Gladmans Implementation vom 26.8.2005 hat zwei kleine Probleme, die diese Patches beheben:
patch -i 0 <$patch
Die kompletten Sourcen des Tutorials (inkl. Patches) gibt es hier.
Die Referenzimplementation und den eigentlichen SHA-Standard findet man beim amerikanischen NIST: http://csrc.nist.gov/CryptoToolkit/tkhash.html
Die wohl bekannteste Anwendung von MDs sind Checksummen - sie stellen sicher dass eine Nachricht unverändert ist, indem man sagen kann dass es sehr unwahrscheinlich ist, dass jemand eine Nachricht mit identischer Hashsumme erzeugen konnte. Der MD wird dabei in seinem einfachsten Modus verwendet: die Nachricht wird so wie sie ist gehasht:
/*die meisten Implementationen von Hashes speichern ihre Daten in einer Kontextstruktur:*/ sha256_ctx ctx; /*dieser Kontext muss initialisiert werden:*/ sha256_begin(&ctx); /*danach schreibt man die Daten hinein:*/ sha256_hash(datenarray,sizeof(datenarray),&ctx); /*schliesslich wird der Kontext finalisiert und das Ergebnis zurückgeliefert:*/ sha256_end(buf,&ctx);
(siehe auch checksumme.c)
Ein Message Authentication Code (kurz: MAC) unterscheidet sich von der Checksumme, indem er noch zusätzlich geschützt wird. Die einfachste Form einer MAC ist ein MD der Message, der entweder vor oder hinter der Message eingefügt wird bevor alles zusammen verschlüsselt wird.
Eine etwas komplexere Form der MAC, die auch einige kompliziertere Angriffe abwehrt, ist HMAC. HMAC benutzt einen zusätzlichen Schlüssel, der mit in den (doppelten) Hash eingerechnet wird:
HMAC-hash(x) = hash( K xor a || hash( K xor b || msg ))
Dabei ist hash eine beliebige MD Funktion, K ist der Schlüssel, a und b sind Konstanten mit der selben Breite, wie K und msg ist die Nachricht. Der Ausdruck x||y ist die Verkettung von x und y.
HMAC kann problemlos an eine Nachricht angehängt werden ohne selbt noch einmal verschlüsselt zu werden - K muss allerdings geschützt werden, falls es übertragen wird.
(siehe hmacsumme.c)
Die komplexeste Form eines MAC ist die digitale Signatur, sie stellt nicht nur für den Empfänger sicher, dass die Nachricht nicht verändert wurde, sondern kann auch im Nachhinein von Dritten geprüft werden, da nur einer der beiden Kommunikationspartner den privaten Schlüssel hat (haben sollte). Eine Beispielimplementation wird leider etwas zu komplex für dieses Tutorial.
MACs stellen mit Abstand die wichtigste Anwendung von Hashes dar, da sie speziell für die Integritätssicherung entwickelt wurden. Für alle anderen Anwendungen existieren meist auch andere spezialisierte Algorithmen.
In der Natur kommt meist nur schlechter Zufall vor - zwischen sehr vielen nicht zufälligen Bits gibt es ein ganz klein wenig Zufall mit mieser Verteilung. Im Computer gibt es nur falschen Zufall - er hat zwar perfekte Verteilung, ist aber immer berechenbar. Die Aufgabe ist es nun das Vorhandensein von echtem Zufall mit der perfekten Verteilung zu kombinieren.
Um natürlichen Zufall für einen Rechner brauchbar zu machen muss man ihn zunächst aufnehmen. Ein Rechner hat mehrere Quellen für Zufall: das Rauschen auf der Soundkarte, Varianzen im Tastaturanschlag, Bewegungsvarianzen der Maus, die Zeitverzögerung durch Luftwirbel in der Festplatte, etc.pp. Je nach Bedarf ist eine oder mehrere der Quellen anzuzapfen - für Unixoide Systeme dürfte die Soundkarte das einfachste sein, da man sie einfach als Datei benutzen kann:
cat /dev/dsp >meinzufall
Jetzt müssen wir den Zufall noch "packen". D.h. die vielen nichtzufälligen Bits von den zufälligen Bits trennen. Das ist leider schwerer als es klingt, da man diese oft nicht unterscheiden kann oder schlimmer noch der Zufall ist sehr dünn über sämtliche Bits verteilt.
Zunächst muss man abschätzen wieviel Zufall in den gesammelten Daten vorhanden ist. Bei einem analogen Soundeingang an dem nichts angeschlossen ist kann man davon ausgehen, dass das Rauschen im Hintergrund zufällig ist. Man muss also die Amplitude des Rauschens messen und daran die Anzahl der zufälligen Bits ermitteln. Ein vereinfachtes Verfahren ist es einfach die Anzahl der Nullen und Einsen zu zählen und dann die kleinere Zahl zu nehmen - das Rauschen hat die doppelte Amplitude (in Bits), aber da es nie wirklich weißes Rauschen ist, ist es eine durchaus annehmbare Approximation die echte Amplitude zu halbieren. Dieses Verfahren funktioniert nicht wenn ein hochvoltiges Microphon angeschlossen ist, gerade ein Signal hereinkommt oder ein Witzbold die Soundkarte auf den digitalen Eingang konfiguriert hat.
Hat man das geschafft muss der Zufall auf eine gute Verteilung gepackt werden - das kann man machen, indem man eine entsprechende Zahl Eingangsbits xor verrechnet, bis sich eine gleiche Verteilung ergibt - bei der extremen Schieflage von Sound-Rauschen gehen dabei allerdings sehr viele Bits verloren. Message Digests stellen einen sehr brauchbaren Packalgorithmus für dieses Dilemma dar: die haben gleichverteilte Bits, sind nicht umkehrbar und können beliebige Datenmengen auf eine feste Größe reduzieren.
(siehe randpack.c)
Für nahezu alle Anwendungen (auch cryptographische) reicht Zufall aus, der für Angreifer nicht vorhersagbar ist. Damit eine Vorhersage nicht möglich ist müssen aus Sicht eines Angreifers zwei Bedingungen erfüllt sein: a) kein Bit des Zufallsstroms darf aus Zuständen ableitbar sein, die bekannt sind und b) kein Bit des Zufallsstroms darf aus anderen Bits des Zufallsstroms ableitbar sein.
Bedingung a) ist erfüllbar, indem man genügend echten Zufall (evtl. mit dem Verfahren oben gepackt) als Grundlage nimmt. Bedingung b) läßt sich erfüllen, indem man MDs zur Ableitung der Blöcke benutzt. Man muss bei diesen Berechnungen allerdings aufpassen, dass man nicht den einfachsten Weg wählt und jeden Block n als den Hash des vorherigen Blocks n-1 berechnet - dann kann jeder Angreifer die selbe Operation durchführen und aus jedem Block n die nachfolgenden Blöcke berechnen. Das läßt sich vermeiden, indem es ein Element in den Hashsummen gibt, das nicht ausgeliefert wird. Die einfachste Variante ist der sog. Counter-Mode:
Block[n] = hash( Salt || n )
Wobei Salt ein beliebiger Block echten Zufalls ist. Dieses Verfahren funktioniert recht gut solange der Hash nicht knackbar ist, es versagt allerdings sobald der Hash geknackt wurde, da man dann den Salt errechnen kann.
Etwas besser verhält sich der HMAC-Mode:
Block[n] = HMAC-hash( Key, Salt || n )
Der etwas komplexere Aufbau von HMAC schützt Key und Salt etwas länger als der Hash an sich. Ein Beispiel findet sich in randextend.c.
In allen Fällen wird empfohlen nicht mehr als 20MB aus einer Runde (einem Set von Key & Salt) zu extrahieren, solange der Zufall für sicherheitskritische Anwendungen gebraucht wird. Key und Salt sollten ebenfalls genug echten Zufall enthalten - mindestens jeweils die Breite des Hashes, bei SHA256 also >=32 Byte.
Bei simplen Simulationen stört es nicht schnelle (aber unsichere) Algorithmen, die einfachere Methode oben und wesentlich mehr Output zu verwenden, da es hier lediglich auf die Statistischen Eigenschaften des Zufalls ankommt.
Warnung: dies ist nur ein Beispiel was man mit Hashes machen kann, es wird nicht empfohlen das praktisch einzusetzen. (Siehe unten)
Bei Stromchiffren wird von einer Funktion ein Strom von Zufallszahlen erzeugt, der dann xor mit den Klartextdaten veknüpft wird, um zu verschlüsseln. Stromchiffren sind grundsätzlich mathematisch symmetrisch, d.h. zum entschlüsseln wird die selbe Funktion eingesetzt.
cryptbyte[n] = klarbyte[n] xor chiffre(key, n); klarbyte[n] = cryptbyte[n] xor chiffre(key, n);
Da sich MDs gut als Zufallsgeneratoren eignen bietet es sich an sie auch als Stromchiffre zu verwenden. Eine Beispielimplementation ist in cipher.c - es kann sowohl zum ver- als auch ent-schlüsseln verwendet werden.
Allerdings ein paar Warnungen zu diesem Experiment: