Fuzzy Hashing

Als Fuzzy Hashing (auch bekannt als Similarity Hashing) werden Hashfunktionen bezeichnet, die zum Erkennen ähnlicher, jedoch nicht identischer Daten geeignet sind. Es wird unter anderem zur Erkennung von Malware oder Spam eingesetzt.

Hintergrund

Für die Duplikaterkennung oder um große Dateisammlungen auf bekannte Dateien zu überprüfen, verwenden viele Lösungen kryptografische Hashfunktionen wie SHA-256.^[1] Sie eignen sich jedoch nicht zur Feststellung, ob eine einzelne Datei einer bekannten Datei ähnelt, da eine der Anforderungen an kryptografischen Hashfunktionen der Lawineneffekt ist, durch den eine kleine Änderung der Eingabe den Hashwert stark verändert.^[2]

Fuzzy Hashing wurde entwickelt, um einzelne Dateien erkennen zu können, die anderen ähnlich sind, aber nicht genau gleichen. Dabei werden spezielle Hashfunktionen verwendet, bei denen zwei ähnliche Eingaben ähnliche Hashwerte erzeugen. Es kann auch verwendet werden, um zu erkennen, ob ein Muster in einem anderen enthalten ist.^[3] Es wird unter anderem zur Identifizierung von Malware^[4][5] oder Spam eingesetzt und hat Potenzial für andere Anwendungen, wie Data Loss Prevention oder die Erkennung von ähnlichem Quelltext.^[1][6]

Ansätze

Es gibt verschiedene Ansätze für die Erstellung von Fuzzy-Hash-Algorithmen:^[7][6]

• Context-triggered Piecewise Hashing (CTPH), bei dem ein Hash erstellt wird, indem die Eingabe in mehrere Teile aufgeteilt wird, für jeden Teil ein herkömmlicher Hash berechnet wird und diese Hashes dann zu einer einzigen Zeichenfolge kombiniert werden.^[8]
• Locality-Sensitive Hashing (LSH), bei dem ähnliche Eingabeelemente in denselben „Buckets“ abgelegt werden, die für die Clusteranalyse und die Nächste-Nachbarn-Klassifikation verwendet werden können.

Werkzeuge und Algorithmen

• spamsum ist ein von Andrew Tridgell entwickeltes Tool, das mithilfe von Fuzzy Hashing ermittelt, ob eine E-Mail bekannten Spam-Mails ähnelt. Es generiert einen Fuzzy-Hash für eine E-Mail und vergleicht diesen mit den Fuzzy-Hashes bekannter Spam-Mails, um ein Übereinstimmungsergebnis zwischen 0 (keine Übereinstimmung) und 100 (vollständige Übereinstimmung) zu ermitteln. Ist das Übereinstimmungsergebnis hoch genug, wird die E-Mail als Spam klassifiziert.^[9][10]
• Nilsimsa Hash ist ein auf Spam-Bekämpfung ausgerichteter Locality-Sensitive-Hashing-Algorithmus.
• ssdeep ist ein Fuzzy-Hashing-Tool, das auf Context-triggered-Piecewise-Hashing basiert, um Dateien zu vergleichen.^[1]
• sdhash ist ein Fuzzy-Hashing-Tool, das auf der Verwendung von Bloomfiltern basiert, um festzustellen, ob eine Datei in einer anderen enthalten ist oder wie ähnlich zwei Dateien einander sind.^[11]
• TLSH ist ein Locality-Sensitive-Hashing-Verfahren zum Vergleichen ob Dateien einander ähnlich sind. Es wird unter anderem für das Malware-Verzeichnis MalwareBazaar^[12] oder für VirusTotal verwendet.
• Rspamd setzt Fuzzy Hashing für die Erkennung von Spam-Emails ein und verwendet dafür den shingles-Algorithmus.^[13][14]