Der Verschlüsselungs-Algorithmus NTRU, welcher im Rahmen des QUASIKOM Projekts implementiert wird, besteht aus einer Vielzahl von Komponenten, von denen im Wesentlichen zwei performance-kritisch sind, d.h. einen erheblichen Einfluss auf die Laufzeit des Algorithmus haben. Die erste dieser Komponenten ist die Polynom-Arithmetik, die bereits in einem früheren Blog-Eintrag ausführlich erklärt wurde. Die zweite Komponente, die sich wesentlich auf die Laufzeit von NTRU auswirkt und das Thema dieses Blog-Eintrages darstellt, ist die kryptografische Hashfunktion SHA-256. Eine Hashfunktion (oder Streuwertfunktion) ist in der deutschsprachigen Wikipedia ganz allgemein definiert als "eine Funktion, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet". In vielen Anwendungen werden Hashwerte als eine Art "digitaler Fingerabdruck" von elektronischen Daten verwendet. Welche konkreten Eigenschaften kryptografische Hashfunktionen erfüllen müssen wird im Laufe dieses Beitrages näher erläutert. Zunächst wird aber kurz darauf eingegangen, was man mit einer kryptografischen Hashfunktion anfangen kann und danach wird erklärt, wie die Hashfunktion SHA-256 im Rahmen des Projekts implementiert und optimiert wurde.

Bevor es ins Detail geht, sollte zuerst erwähnt werden, dass nicht jede Hashfunktion für kryptografische Anwendungen geeignet ist. Kryptografische Hashfunktionen stellen nämlich nur eine Teilmenge aller Hashfunktionen dar, d.h. es gibt auch außerhalb der Kryptografie etliche Bereiche der Informatik in denen Hashfunktionen zu Einsatz kommen. Ein Beispiel für solche Anwendungsgebiete sind Datenbanken, in denen sogenannte Hashtabellen verwendet werden, um eine effiziente Indizierung einzelner Datenobjekte zu ermöglichen, womit sich dann in der Folge schnelle Such- und Zugriffsverfahren für große Datenmengen realisieren lassen. Die dabei zum Einsatz kommende Hashfunktion berechnet zu jedem Datenobjekt einen Hashwert, der dann als Index in der Tabelle verwendet wird. Einige der in der Praxis vorkommenden Hashfunktionen sind extrem einfach; so umfasst z.B. der Quellcode der Hashfunktion DJBX33A, welche in der Skriptsprache PHP die Hashtabellen berechnet, lediglich drei Zeilen. Verglichen dazu sind kryptografische Hashfunktionen wesentlich komplizierter.

Eine kryptografische Hashfunktion ist ein Algorithmus, der aus einem beliebig großen Datensatz eine Zeichenkette mit einer fixen Länge, den sogenannten Hashwert, erzeugt. Der Datensatz kann nicht nur beliebig groß sein, er kann auch eine beliebige Form haben, d.h. kann von einem einfachen ASCII-String über Binärdateien bis hin zum Inhalt einer CD oder DVD alles Mögliche umfassen. Auf der anderen Seite werden die Hashwerte zumeist als Hex-Strings dargestellt, wobei Längen von 256, 384 und 512 Bits üblich sind. Eine Minimalanforderung, die in der Regel sowohl kryptografische Hashfunktionen als auch Hashfunktionen für nicht-kryptografische Anwendungen erfüllen, ist dass identische Datensätze immer in identischen Hashwerten resultieren müssen. Darüber hinaus sollten kryptografische Hashfunktion noch zwei weiteren Anforderungen gerecht werden. Die erste dieser zusätzlichen Anforderungen ist Kollisionsresistenz, d.h. zwei unterschiedliche Datensätze sollten auch unterschiedliche Hashwerte ergeben. Ist dies nicht der Fall (d.h. führen unterschiedliche Datensätze zum selben Hashwert) dann spricht man von einer Kollision. Kollisionen lassen sich, zumindest theoretisch, nie ganz vermeiden da eine Hashfunktion mit einer endlichen Länge von n Bits nur 2^n unterschiedliche Hashwerte liefern kann, es aber unendlich viele verschiedene Datensätze gibt. Mathematisch ausgedrückt können Kollisionen nicht 100% ausgeschlossen werden weil eine Hashfunktion nicht injektiv ist. Moderne kryptografische Hashfunktionen sind aber so konstruiert, dass Kollisionen in der Praxis de fakto nicht vorkommen. Eine weitere Anforderung an eine kryptografische Hashfunktion ist effiziente Berechenbarkeit der Hashwerte, d.h. der Rechenaufwand sollte nur linear mit der Größe des zu hashenden Datensatzes ansteigen. Auf der anderen Seite soll ein Hashwert keine Informationen über den ürsprünglichen Datensatz preisgeben und es soll auch praktisch nicht möglich sein, aus einem gegebenen Hashwert den ursprünglichen Datensatz (oder einen anderen Datensatz der den selben Hashwert liefert) zurück zu berechnen. Dabei bedeutet praktisch nicht möglich, dass es keine effizientere Methode zur Berechnung als Brute Force gibt, d.h. der Aufwand zum Finden des Datensatzes steigt exponentiell mit der Länge des Hashwertes an. Deshalb werden kryptografische Hashfunktion auch als Einweg-Hashfunktionen bezeichnet.

Die im Rahmen des QUASIKOM Projekts realisierte Implementierung von SHA-256 stellt sowohl eine High-Level- als auch eine Low-Level-Programmierschnittstelle (API) zur Verfügung, wobei Erstere nur aus einer einzigen Funktion besteht, nämlich sha256_hash(). Auf der anderen Seite realisiert das Low-Level-API eine sogenannte I-U-F Schnittstelle (d.h. besteht aus den üblichen sha256_init(), sha256_update() und sha256_final() Funktionen) und wird im Allgemeinen zum Hashen großer oder fragmentierter Daten bevorzugt. Die High-Level-Funktion sha256_hash() benötigt die gesamten zu hashenden Daten im RAM, was in gewissen Situationen problematisch sein kann. Zum Beispiel ist es mit der High-Level-Funktion nicht möglich, eine Datei zu hashen, deren Größe die verfügbare RAM-Kapazität übersteigt. Bei Verwendung des Low-Level-API kann jedoch eine große Datei in kleineren Teilen verarbeitet werden, indem die Teile einfach ins RAM geladen und sha256_update() aufgerufen wird, bis die gesamte Datei gehashed ist. Auf diese Weise ist es möglich, Daten beliebiger Größe mit konstanter Speichernutzung zu hashen. Ein anderes Beispiel für das das Low-Level-API zeigt, ist Online-Processing, insbesondere Streaming-Anwendungen, bei denen die zu hashenden Daten in Streams empfangen werden und daher fragmentiert sind. Die Verwendung der High-Level-Funktion sha256_hash() würde erfordern, dass der Empfänger die gesamten Daten zwischenspeichert (d.h. puffert), was leicht die verfügbare RAM-Kapazität übersteigen kann. Wenn jedoch die Low-Level-API zum Einsatz kommt, können die Datenblöcke unabhängig voneinander verarbeitet werden indem einfach die Funktion sha256_update() aufgerufen wird, wodurch es nicht notwendig ist, große Datenmengen zu puffern.