Loading AI tools
Aus Wikipedia, der freien Enzyklopädie
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.
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.[1][2] 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).[3]
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.[4] 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 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 der ursprünglichen Nachricht und die Länge des Hashwertes angefügt, jeweils in einem Feld fester Breite:
Die zugrunde liegende Kompressionsfunktion erfordert eine bestimmte Nachrichten-Blocklänge . Die Zahl der angefügten Nullen wird daher auf eine Zahl festgelegt, sodass die Länge der erweiterten Nachricht ein Vielfaches von ist.
Dann wird in Blöcke der Länge Bit geteilt. Wie bei der Merkle-Damgård-Konstruktion werden diese Nachrichtenblöcke durch aufeinanderfolgende Aufrufe einer Kompressionsfunktion iterativ verarbeitet: erhält die vorherige Ausgabe von und den jeweils nächsten Nachrichtenblock als Eingabe. Bei der HAIFA-Konstruktion werden zusätzlich zwei weitere Parameter eingegeben: Das Salz und die Zahl der bis dahin verarbeiteten Bits der ursprünglichen Nachricht , einschließlich derer im aktuellen Block:
mit
(oder ein Teil davon) ist dann der berechnete Hashwert.
Beim ersten Iterationsschritt wird noch kein Nachrichtenblock gehasht, sondern aus der Länge des zu berechnenden Hashwertes und einem konstanten Initialisierungsvektor IV der erste Verkettungswert gebildet. Diese Berechnung kann vorab erfolgen, wenn sich nicht ändert; ist dann konstant. Beim letzten Iterationsschritt wird anstelle der Zahl der verarbeiteten Nachrichtenbits eingegeben, wenn der letzte Block 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 so formatiert, dass sie in jedem Fall anders aussieht als die Eingabe im letzten. Wenn mit , handelt es sich um einen Block voll mit Bits der Ursprungsnachricht, und ist die Iterationsnummer. Ist , dann enthält der Block die letzten Nachrichtenbits, aus deren Zahl auch hervorgeht, ob es sich um den letzten Block handelt. Falls , ist es der letzte Block, der die Nachrichtenlänge 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 haben. In Fällen, in denen Salz nicht notwendig erscheint, kann gesetzt werden.
Ebenfalls eng angelehnt an die Merkle-Damgård-Konstruktion ist die Wide-Pipe(Double-Pipe)-Merkle-Damgård-Konstruktion. Stefan Lucks stellte 2005[6] 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.[7] Hashfunktionen wie Keccak (SHA-3), JH, CubeHash, Fugue, Hamsi und Luffa beruhen auf dieser Konstruktion.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.