2. Der Snefru-Algorithmus

Snefru (Name eines ägyptischen Pharaos) wurde von Ralph Merkle entworfen. Diese Einweg-Hashfunktion berechnet für beliebig lange Nachrichten einen Hashwert von 128 bzw. 256 bit Länge.

2.1 Beschreibung des Algorithmus

Blocklänge ist bei Snefru 512 - m bit, mit m= Länge des erzeugten Hashwerts: 384 bzw. 256 bit Blocklänge. Der erste Block der Nachricht wird an Nullen angehängt. Kern des Algorithmus ist eine Funktion, die aus 512 bit einen m bit langen Hashwert berechnet. An diesen Hashwert wird der nächste Nachrichtenblock angehängt. Falls der letzte Block nicht aus 512 - m bits besteht, wird er mit Nullen aufgefüllt. Der daraus berechnete Hashwert wird an eine binäre Darstellung der Nachrichtenlänge angehängt. Das bildet den letzten Nachrichtenblock, aus welchem der endgültige Hashwert berechnet wird. Die Funktion H basiert auf einer Chiffrierfunktion, die 512 bit verschlüsselt, und liefert als Ergebnis eine XOR-Verknüpfung der ersten m bit der Eingabe der Chiffrierfunktion mit den letzten m bit der Ausgabe der Chiffrierfunktion.

2.2 Sicherheit des Algorithmus

Die Blockchiffrierung randomisiert Daten in mehreren Durchläufen mit je 64 Randomisierungsrunden je Durchlauf. Außerdem werden noch Rotationen durchgeführt.

2.3 Kryptanalyse des Algorithmus

Snefru mit 128-bit-Hashwerten ist unsicher. Bei zwei Durchläufen lieferte ein Angriff mit Hilfe differentieller Kryptanalyse Nachrichtenpaare mit gleichem Hashwert innerhalb von Minuten. Bei vier Durchläufen benötigt ein Geburtstagsangriff 2 Operationen, Nachrichtenpaare mit gleichem Hashwert findet man nach 2 Operationen. Die endgültige Geschwindigkeit, mit der diese Hashfunktion gebrochen werden kann, hängt von der Hardware ab. Zur Zeit empfiehlt Merkle den Einsatz von Snefru mit mindestens acht Durchläufen. Allerdings ist der Algorithmus dann wesentlich langsamer als andere gängige Verfahren.