Der Recherchekompass
[ home | anleitungen | recherchen | hilfe | sitemap | index | suchen ]

Verschlüsselte Botschaften Kryptografisches Haschee

Kryptologisches Hackfleisch[1] basiert auf sogenannten Einwegfunktionen bei denen es sich um mathematische Funktionen handelt, bei der es deutlich leichter ist aus einem gegebenen y das ursprüngliche x zu berechnen, als umgekehrt. Bei einer Einwegfunktion ist letzteres nicht oder nur mit unendlichem Aufwand möglich. Mathematisch konnte noch nicht bewiesen werden, dass solche Einwegfunktionen tatsächlich existieren, aber in der praktischen Anwendung sind einige bekannt, die zumindest nach heutigen Wissensstand nicht invertiert werden können.

Zur Verschlüsselung lassen sich diese Funktionen nicht verwenden, weil es keine Möglichkeit gäbe, die ursprüngliche Nachricht wiederherzustellen. Hierzu würde eine Einwegfunktion mit Hintertür (Trapdoor-Funktion) gebraucht. Hierbei handelt es sich um eine Einwegfunktion, deren Umkehrung leicht mittels einer zusätzlichen Information (die Hintertür) berechnet werden kann, ohne diese Information jedoch nur sehr schwer. Prinzipiell basiert auf solchen Funktionstypen die gesamte asymmetrische Kryptografie. Wie bei den Einwegfunktionen ist es auch hier praktisch "unmöglich", aus einen gegebenen Geheimtext die ursprüngliche Nachricht zu ermitteln. Ist man allerdings im Besitz einer bestimmten Information (bei RSA zum Beispiel die Primzahlfaktoren), ist die Berechnung des Klartextes - sozusagen durch die Hintertür - möglich.

Einwegfunktionen dienen in der Kryptografie zur Generierung von nicht manipulierbaren Fingerabdrücken aus Nachrichten. Derartige kryptografische Funktionen, die aus einer Nachricht mit beliebiger Länge nach einem vorbestimmten Verfahren ein Komprimat - im Sinne einer kryptografischen Prüfziffer - erzeugen, nennt man Hashfunktionen. Eine Hashfunktion, welche die Eigenschaft hat, dass es sehr lange dauert eine Nachricht zu finden für die hash(m) = hash(n) gilt, nennt man kryptografische Hashfunktion. Anders als bei Prüfsummenverfahren müssen dabei nicht nur zufällig auftretende Fehler, sondern auch vorsätzliche Manipulationen sicher erkannt werden. Die wichtigsten Anforderungen an solche Funktionen lauten:

• Effizienz
  Ein Hashwert muss "einfach", d.h. leicht und schnell, zu berechnen sein.

• Kollisionsfreiheit
  Eine Hashfunktion muss "kollisionsfrei" sein, das heißt es darf nicht möglich sein, zwei Nachrichten zu konstruieren, die den gleichen Hashwert haben, da es sonst möglich wäre, eine Originalnachricht unerkannt durch eine Fälschung auszutauschen (Geburtstagsangriff).

• Repräsentativität
  Jedes Bit eines Textes muss den Hashwert beeinflussen, d. h. die Änderung auch nur eines Buchstaben eines Textes muss zu einem anderen Hashwert führen. Daher müssen auch ähnliche Texte vollkommen unterschiedliche Hashwerte ergeben.

• Kryptografische Sicherheit
  Für einen gegebenen Hashwert muss es praktisch unmöglich sein den zugehörigen Text herzustellen bzw. zurückzugewinnen.

Aufgrund der festen Länge des Hashwertes bei beliebiger Nachrichtenlänge ist es theoretisch möglich Kollisionen herbeizuführen, da stets eine unendliche Anzahl unterschiedlicher Nachrichten auf den gleichen Hashwert abgebildet werden würde. Durch hinreichend lange Hashwerte und einen geeigneten Algorithmus lässt sich dann ausschließen, dass solche Kollisionen mit praktikablen Aufwand gezielt herbeigeführt werden können.

Hashfunktionen die diese Eigenschaften erfüllen werden im Englischen als Message Digest (MD) bezeichnet. (Digest: Auszug, Zusammenfassung) Ein Message Digest ist der (digitale) Fingerabdruck einer Nachricht, bei der mit Hilfe von einfach berechenbaren Funktionen ein Wert ermittelt wird, der kürzer ist als die Originalnachricht. Die verwendete Funktion muss so beschaffen sein, dass es relativ schwierig ist eine zweite Nachricht zu erzeugen, die den gleichen Fingerabdruck hat. Die Chance, aus zwei unterschiedlichen Texten einen identischen Fingerabdruck zu generieren, sollte eins zu unendlich, kann aber nie völlig ausgeschlossen werden.

 

• Message Digest von RSA

  Nachricht: Dies ist der Klartext. MD4: MD5:

  Tabelle: Hashwerte nach MD4 und MD5.

  Ron Rivest entwickelte - zusammen mit anderen Mitarbeitern der RSA Data Security - eine Reihe von Hashfunktionen MD1(?), MD2, MD3, MD4 bis MD5, die gemeinhin auch als Synonym für den Message Digest gelten. Die Algorithmen akzeptieren als Eingabe eine Botschaft beliebiger Länge und erzeugen einen "digitalen Fingerabdruck" von 128 Bit Länge als Ausgabe. Die Chance, aus zwei unterschiedlichen Texten einen identischen Fingerabdruck zu generieren, ist beinahe unendlich, kann aber nicht völlig ausgeschlossen werden.

  Obwohl die RFC's alle im April 1992 veröffentlicht wurden, ist die Folge der Algorithmen als unterschiedliche Stadien der (Weiter-)Entwicklung zu betrachten.

  • MD1:
    Irgendwelche Informationen zu diesem Algorithmus und seinem Status sind nicht zu ermitteln.

  • MD2:
    Der Hashwert wird aus einer beliebig langen Nachricht bei einer Blocklänge von 128 Bit (16 Byte) in fünf Schritten gebildet. Zunächst wird die Nachricht auf ein Vielfaches der Blocklänge gebracht und dann eine Prüfsumme von 16 Byte Länge angehängt. Für die Berechnung wird ein 48 Byte Hilfsblock benutzt, der aus 3 Teilblöcken besteht und mit Nullen initialisiert wird. Mit jedem Nachrichtenblock werden 18 Runden ausgeführt, in denen :
    • Der aktuelle Nachrichtenblock wird in den zweiten Teil des Hilfsblocks geschrieben, der dritte Teilblock wird durch eine xor-Verknüpfung aus dem ersten und zweiten Teilblock erzeugt.
    • Jedes Byte des Hilfsblockes wird durch XOR mit einem "Zufallsbyte" verknüpft. Das Zufallsbyte einen 256 Byte langem Feld entnommen, das durch "zufällige" Permutation aus den Ziffern von PI gebildet wurde.
    Nachdem alle Blöcke der (verlängerten) Nachricht bearbeitet worden sind, bildet der erste Teilblock des Hilfsblockes den Hashwert der Nachricht. Die Sicherheit von MD2 hängt von der (pseudo-)zufälligen Bytepermutation des zweiten Schrittes ab. Schwächen des Algorithmuses wurden bisher nicht entdeckt. Allerdings ist MD2 ein langsamer Algorithmus.

  • MD3:
    Wegen einer Reihe von Mängeln wurde MD3 nie über das Experimentierstadium hinaus gebracht.

  • MD4:
    MD4 wurde mit dem Anspruch entwickelt auf 32 Bit Maschinen besonders schnell zu laufen und gleichzeitig in der Implementierung einfach zu sein. Dabei sollten natürlich die grundlegenden Anforderungen an Hashfunktionen (s.o.) erhalten bleiben. Vom Algorithmus wird zu Beginn zunächst die Länge der Nachricht auf ein Vielfaches von 512 Bit gebracht, indem eine 1 und entsprechend Nullen sowie die Länge der Ursprungsnachricht - im 64 Bit Format - angehängt werden. Dann wird Puffer, bestehend aus den 32 Bit Registern: A, B, C und D, eingerichtet und initialisiert. Jeder Nachrichtenblock wird in drei Runden mit dem Puffer verknüpft, wobei die vier Teile des Puffers 16 Mal permutiert werden. Die Funktionen für die Verwürfelung des Puffers lauten:
    1. Runde: F(X;Y;Z) = X and Y or not(X) and Z
    2. Runde: G(X;Y;Z) = X and Y or X and Z or Y and Z
    3. Runde: H(X;Y;Z) = X xor Y xor Z
    Die Operationen: "and", "or", "not" und "xor" sind bitweise Operationen. In der Verknüpfung der Funktionen werden Shift-Operationen sowie eine Addition die sicherstellt, dass das Ergebnis nicht größer als 32 Bit ist, verwendet. Der Hashwert ist am Ende gegeben durch Konkatenation der bitweise umgekehrten Werte von A, B, C und D. Trotz aller Sorgfalt zeigte sich bald, dass das Verfahren unsicher ist. Als besonders problematisch stellte sich die mangelnde Kollisionsbeständigkeit heraus. Im "Cryptobytes Journal" der Firma RSA wurde eine Methode veröffentlicht, welche innerhalb einer Stunde zwei bis auf ein Zeichen identische Nachrichten erzeugen konnte, die denselben Hashwert ergaben. Rivest selber bestätigte die Unsicherheit im RFC 1321: "MD5 Message Digest Algorithm", so dass selbst RSA vom Einsatz dieses Message Digest abrät. MD4 wurde als Public Domain lizensiert, wodurch wohl zurückzuführen ist, dass das verwendete Prinzip, zur Basis weiterer Hashfunktionen geworden ist: MD5, RIPE-MD und SHA.

  • MD5:
    MD5 ist wohl zur Zeit die am weitesten verbreitete Hashfunktion. Sie ist aus MD4 entstanden und dabei in erster Linie um deren Unsicherheiten auszuräumen. Wie bei MD4 wird zu Beginn die Länge der Nachricht auf ein Vielfaches von 512 Bit gebracht, indem eine 1 und entsprechend Nullen sowie die Länge der Ursprungsnachricht - im 64 Bit Format - angehängt werden. Auch der Puffer und dessen Initialisierung sind gleich. Erweitert wurde MD5 gegenüber MD4 durch Hinzunahme eine vierten Funktion:
    I(X,Y,Z) = Y xor (X or not(Z))
    und einer vierten Runde. Des weiteren wurde eine Tabelle mit 64 Elementen aufgenommen, deren Inhalte durch eine Sinusfunktion gegeben werden. In jedem Schritt jeder Runde wird ein zusätzliche Verknüpfung mit einem Element dieser Tabelle durchgeführt. Da auch hier jeder Schritt vom Ergebnis des vorherigen abhängt, entsteht ein schnellerer "Lawineneffekt" als bei MD4. Dadurch ist MD5 leider etwas langsamer geraten. Außerdem ist trotz dieser Erweiterungen auch bei MD5 die Beständigkeit gegenüber Kollisionen problematisch. Verwendet wird MD5 dennoch in einigen Versionen von PGP und von Privacy Enhanced Mail (PEM).

  MD2 und MD4 sind ältere Versionen dieses Hash-Algorithmus. Sie haben bekannte Schwächen und sollten daher nicht benutzt werden. MD5 hingegen wird weitgehend als sicher betrachtet und ist sehr verbreitet, obwohl auch hier eine Schwäche gefunden wurde.

  Genauere Beschreibungen der verwendbaren Verfahren finden sich in:

  RFC 1319: MD2 Message Digest Algorithm; B. Kaliski, April 1992
  RFC 1320: MD4 Message Digest Algorithm; R. Rivest, April 1992
  ___________ (überarb. Vers. RFC 1186, Okt. 1990)
  RFC 1321: MD5 Message Digest Algorithm; R. Rivest, April 1992
  
  [seitenanfang] [verweise]

   

• Secure Hash Algorithm (SHA)

  Zusammen mit der National Security Agency (NSA) entwickelte das NIST (National Institute of Standards and Technology) einen zum Signieren gedachten Hash-Standard und Einwegfunktion für den Digital Signature Standard (DSS). Der Standard heißt Secure Hash Standard (SHS) und spezifiziert den "Secure Hash Algorithm" (SHA) mit Hashwert der Länge 160 Bit. Der weit verbreitete Algorithmus ähnelt im Aufbau stark dem Message Digest von RSA.

  Abbildung: Rundenschema des SHA-1

  In der Vorbereitung für den SHA wird zunächst die Nachricht auf eine Länge gebracht, die einem Vielfachen von 512 Bit entspricht. Dazu wird ans Ende der Nachricht eine 1 und die Länge der Originalnachricht als 64bit-Zahl angehängt; zwischen der 1 und der Länge werden entsprechend viele Nullen aufgefüllt, um 512 Bit zu erreichen. Die Nachricht wird in 512 Bit Blöcke zerlegt, der Hashwert - bestehend aus fünf 32 Bit Wörtern - und ein Feld mit 80 Konstanten wird initialisiert.

  • Jeder Block wird in 16 "Wörter" von je 32 Bit zerlegt.
  • Es werden 64 weitere "Wörter" erzeugt, die aus xor-Verknüpfungen der ersten 16 entstehen.
  • Um in jede Runde das Ergebnis der vorherigen eingehen zu lassen, wird in den fünf 32 Bit Variablen [A, B, C, D, E] der Hashwert der vorangegangenen Runde übertragen.
  • Die Werte von A, B, C, D, E werden mit jedem der 80 aus dem Klartext gebildeten "Wörtern", einer der 80 Konstanten sowie einer von vier vorgegebenen logischen Funktionen verknüpft und mehrfach einer zyklischen Shift-Operation unterzogen (vgl. Abbildung).
  • Die auf diese Weise veränderten Werte von A bis E werden zum Hashwert der vorherigen Runde addiert und durch eine modulo-Operation wieder auf 32 Bit Länge verkürzt.

  Nach der Verarbeitung aller Blöcke ist der zuletzt erhaltene Hashwert der "Secure Hash" der Originalnachricht.

  Prinzipiell wurde von den gleichen Entwurfszielen wie beim MD4 ausgegangen. Mit seinem längeren Hashwert von 160 Bit ist SHA aber widerstandsfähiger gegen Brute-Force Angriffe. Ein Design-Fehler im 1992 veröffentlichten Algorithmus wurde im heute gebräuchlichen SHA-1 korrigiert, für den bisher keine wirkungsvollen kryptografischen Angriffe bekannt geworden sind. Durch den Einsatz einer fünften Variablen ist SHA-1 auch im Vergleich zu MD5 resistenter gegen Kollisionen geworden.

  Die genauere Beschreibung ist zu finden in:

  FIPS PUB 180-1: Secure Hash Standard (SHS), April 1995
  FIPS PUB 186: Digital Signature Standard (DSS), Mai 1994
  
  [seitenanfang] [verweise]