HAIFA (kryptologisches Verfahren)

HAIFA (Abkürzung für HAsh Iterative FrAmework) ist eine von Eli Biham und Orr Dunkelman entwickelte Konstruktionsmethode für iterative kryptologische Hashfunktionen. Sie wurde 2006 veröffentlicht und seitdem in vielen Hashfunktionen verwendet.

Hintergrund

Iterative Hashfunktionen zerlegen die zu hashende Nachricht in gleich lange Blöcke, die von einer Kompressionsfunktion nacheinander verarbeitet, d. h. in einen Datenblock fester Größe eingearbeitet werden. Die Kompressionsfunktion erhält als Eingabe den Nachrichtenblock und den aktuellen Wert des Datenblocks und berechnet daraus den nächsten Wert des Datenblocks. Diesem wird am Ende der Hashwert entnommen. Die Merkle-Damgård-Konstruktion ist die verbreitetste Möglichkeit, ein solches iteratives Hashverfahren zu konstruieren.

Ein Hashverfahren nach der Merkle-Damgård-Konstruktion ist beweisbar kollisionssicher, wenn eine kollisionssichere Kompressionsfunktion genutzt wird. Ursprünglich wurde angenommen, dies gelte auch für die (second) Preimage-Resistenz, allerdings wird das in neueren Untersuchungen widerlegt. In der Folge dieser Analysen versuchte man, das Merkle-Damgård-Verfahren weiterzuentwickeln, wie beispielsweise durch HAIFA, oder durch ein anderes Verfahren zu ersetzen.

Drei von 14 Kandidaten der zweiten Runde im SHA-3-Auswahlverfahren für eine neue Hashfunktion beruhten auf der HAIFA-Konstruktion (BLAKE, SHAvite-3, ECHO).

Aufbau

HAIFA ergänzt die Merkle-Damgård-Konstruktion durch drei Neuerungen: Erstens werden der Kompressionsfunktion zusätzliche Daten eingegeben, welche die Rolle und Position jedes Schritts in der Iterationsfolge eindeutig bezeichnen. Dadurch kann ein Angreifer keine Schritte weglassen oder zusätzlich einfügen, denn die nachfolgenden Schritte würden dann anders arbeiten. Insbesondere wird der letzte Schritt (Finalisierung) eindeutig bezeichnet, um Erweiterungsangriffe zu verhindern. Dies soll unter anderem die gegen die Merkle-Damgård-Konstruktion erfolgreichen fixed point attacks erschweren. Zweitens erhält die Kompressionsfunktion Salz als zusätzliche Eingabe. Drittens wird auch die Länge des zu berechnenden Hashwertes der Kompressionsfunktion eingegeben.

Zunächst wird die Nachricht $M$ mit dem HAIFA-Padding-Scheme erweitert. Dabei darf aber keine Information verloren gehen, d. h. aus der erweiterten Nachricht muss die ursprüngliche Nachricht eindeutig rekonstruierbar sein. Zu diesem Zweck wird die Nachricht um eine 1 ergänzt, gefolgt von einer variablen Anzahl von Nullen. Daran wird noch die Länge $|M|$ der ursprünglichen Nachricht und die Länge $m$ des Hashwertes angefügt, jeweils in einem Feld fester Breite:

$N=M\;\|\;10^{r}\;\|\;|M|\;\|\;m$

Die zugrunde liegende Kompressionsfunktion erfordert eine bestimmte Nachrichten-Blocklänge $l$. Die Zahl der angefügten Nullen wird daher auf eine Zahl $r\in \{0,1,\dots ,l-1\}$ festgelegt, sodass die Länge der erweiterten Nachricht $N$ ein Vielfaches von $l$ ist.

Dann wird $N$ in Blöcke $N_{1}\dots N_{n}$ der Länge $l$ Bit geteilt. Wie bei der Merkle-Damgård-Konstruktion werden diese Nachrichtenblöcke durch aufeinanderfolgende Aufrufe einer Kompressionsfunktion $C$ iterativ verarbeitet: $C$ erhält die vorherige Ausgabe von $C$ und den jeweils nächsten Nachrichtenblock als Eingabe. Bei der HAIFA-Konstruktion werden zusätzlich zwei weitere Parameter eingegeben: Das Salz $S$ und die Zahl der bis dahin verarbeiteten Bits der ursprünglichen Nachricht $M$, einschließlich derer im aktuellen Block:

$x_{0}=C(IV,\,m,\,0,\,0)$

$x_{i}=C(x_{i-1},\,N_{i},\,S,\,L(i)),\;\;i\in \{1,\dots n\}$

mit

$L(i)={\begin{cases}i\cdot l&{\text{wenn}}\;i\cdot l\leq |M|\\|M|&{\text{wenn}}\;|M|<i\cdot l<|M|+l\\0&{\text{wenn}}\;i\cdot l\geq |M|+l\end{cases}}$

$x_{n}$ (oder ein Teil davon) ist dann der berechnete Hashwert.

Beim ersten Iterationsschritt wird noch kein Nachrichtenblock gehasht, sondern aus der Länge $m$ des zu berechnenden Hashwertes und einem konstanten Initialisierungsvektor IV der erste Verkettungswert $x_{0}$ gebildet. Diese Berechnung kann vorab erfolgen, wenn sich $m$ nicht ändert; $x_{0}$ ist dann konstant. Beim letzten Iterationsschritt wird $0$ anstelle der Zahl der verarbeiteten Nachrichtenbits eingegeben, wenn der letzte Block $N_{n}$ kein Bit der ursprünglichen Nachricht mehr enthält.

Aus der Eingabe in die Kompressionsfunktion kann immer eindeutig abgeleitet werden, um welchen Iterationsschritt es sich handelt und ob es bereits der letzte ist. Beim ersten Schritt wird die Eingabe $m$ so formatiert, dass sie in jedem Fall anders aussieht als die Eingabe $N_{n}$ im letzten. Wenn $L(i)\equiv 0{\pmod {l}}$ mit $L(i)>0$, handelt es sich um einen Block voll mit Bits der Ursprungsnachricht, und $L(i)/l$ ist die Iterationsnummer. Ist $L(i)\not \equiv 0{\pmod {l}}$, dann enthält der Block die letzten Nachrichtenbits, aus deren Zahl $L(i){\bmod {l}}$ auch hervorgeht, ob es sich um den letzten Block $N_{n}$ handelt. Falls $L(i)=0$, ist es der letzte Block, der die Nachrichtenlänge $|M|$ enthält, aus der sich die Iterationsnummer ergibt.

Das Salz kann aus einem festen oder für jede gehashte Nachricht verschiedenen Wert bestehen. Als Länge werden mindestens 64 Bit empfohlen, nach Möglichkeit sollte das Salz aber die halbe Länge des Verkettungswertes $x_{i}$ haben. In Fällen, in denen Salz nicht notwendig erscheint, kann $S=0$ gesetzt werden.

Eigenschaften

• Im Gegensatz beispielsweise zur ebenfalls neuen Sponge-Konstruktion ist HAIFA stark an die Merkle-Damgård-Konstruktion angelehnt und kann als eine Variation von oder Ergänzung zu dieser gelten, ähnlich wie die Wide-Pipe-Merkle-Damgård-Konstruktion. Eigenschaften wie die Kollisionssicherheit, werden beibehalten.
• Gegenüber der Merkle-Damgård-Konstruktion bietet HAIFA einen verbesserten Schutz gegen (second) Preimage-Angriffe. Die bis zum Zeitpunkt der Entwicklung bekannten Angriffe sind nicht direkt auf HAIFA übertragbar. Charles Bouillaguet und Pierre-Alain Fouque konnten 2010 die angenommene Resistenz von HAIFA gegen second Preimage-Angriffe bestätigen.
• Die HAIFA-Konstruktion ist mit vielen anderen Methoden kombinierbar, die die Sicherheitseigenschaften von Hashfunktionen verbessern sollen, wie mit RMX (randomisiertes Hashing nach Krawczyk und Halevi), enveloped Merkle-Damgård (nach Bellare und Ristenpart), RMC und ROX (nach Andreeva et al.).
• HAIFA unterstützt Hashwerte mit variablen Längen.
• HAIFA bietet die Möglichkeit des Online-Hashing: Statt der gesamten Nachricht muss nur ein Block der Nachricht im Speicher gehalten werden.

Alternative Konstruktionen zu HAIFA

Ebenfalls eng angelehnt an die Merkle-Damgård-Konstruktion ist die Wide-Pipe(Double-Pipe)-Merkle-Damgård-Konstruktion. Stefan Lucks stellte 2005 eine Konstruktion vor, bei der der interne Status der Hashfunktion größer ist als der Hashwert. Mit einer geringfügig höheren Speicheranforderung kann so eine bessere second Preimage-Resistenz erreicht werden. Viele moderne Hashfunktionen wie Grøstl, Shabal, SIMD, Blue Midnight Wish beruhen auf dieser Konstruktion.

Nicht angelehnt an die Merkle-Damgård-Konstruktion, aber ebenfalls iterativ, ist die 2007 von Guido Bertoni, Joan Daemen, Michaël Peeters und Gilles Van Assche entwickelte Sponge-Konstruktion, die neben Hashfunktionen auch in Stromchiffren verwendet werden kann. Hashfunktionen wie Keccak (SHA-3), JH, CubeHash, Fugue, Hamsi und Luffa beruhen auf dieser Konstruktion.

Hashfunktionen mit HAIFA-Konstruktion

• BLAKE
• SHAvite-3
• ECHO
• LAKE
• Sarmal
• SWIFFTX
• HNF-256
• Auch die Konstruktion von Skein (die Unique Block Iteration) weist Ähnlichkeiten mit HAIFA auf.

Weblinks

• Eli Biham und Orr Dunkelman: A Framework for Iterative Hash Functions – HAIFA. 2007 (PDF; 223 kB).
• Eli Biham und Orr Dunkelman: The SHAvite-3 Hash Funktion. Tweaked Version 23. November 2009. S. 4–9 (kurze Beschreibung von HAIFA) (PDF)
• Orr Dunkelman: Re-Visiting HAIFA and why you should visit too. 2008 (PDF; 679 kB).
• B. Denton, R. Adhami: Modern Hash Function Construction. International Conference on Security and Management. Juli 2011. (PDF)