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. 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.

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. Es wird unter anderem zur Identifizierung von Malware oder Spam eingesetzt und hat Potenzial für andere Anwendungen, wie Data Loss Prevention oder die Erkennung von ähnlichem Quelltext.

Ansätze

Es gibt verschiedene Ansätze für die Erstellung von Fuzzy-Hash-Algorithmen:

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.
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.
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.
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.
TLSH ist ein Locality-Sensitive-Hashing-Verfahren zum Vergleichen ob Dateien einander ähnlich sind. Es wird unter anderem für das Malware-Verzeichnis MalwareBazaar oder für VirusTotal verwendet.
Rspamd setzt Fuzzy Hashing für die Erkennung von Spam-Emails ein und verwendet dafür den shingles-Algorithmus.

Einzelnachweise

1 2 3 Jesse Kornblum: Identifying almost identical files using context triggered piecewise hashing. In: Digital Investigation. Nr. 3. Elsevier, 2006, S. 91–97, doi:10.1016/j.diin.2006.06.015 (englisch).
↑ Saif Al-Kuwari, James H. Davenport, Russell J. Bradford: Cryptographic Hash Functions: Recent Design Trends and Security Notions. In: Report 2011/565. Cryptology ePrint Archive (englisch, iacr.org).
↑ Frank Breitinger, Barbara Guttman, Michael McCarrin, Vassil Roussev, Douglas White: Approximate Matching: Definition and Terminology. In: NIST Special Publication 800-168. National Institute of Standards and Technology, 2014, doi:10.6028/NIST.SP.800-168 (englisch).
↑ Fabio Pagani, Matteo Dell'Amico, Davide Balzarotti: Beyond Precision and Recall: Understanding Uses (and Misuses) of Similarity Hashes in Binary Analysis. In: Proceedings of the Eighth ACM Conference on Data and Application Security and Privacy. Association for Computing Machinery, 2018, ISBN 978-1-4503-5632-9, S. 354–365, doi:10.1145/3176258.3176306 (englisch, pagabuc.me [PDF]).
↑ Nikolaos Sarantinos, Chafika Benzaïd, Omar Arabiat: Forensic Malware Analysis: The Value of Fuzzy Hashing Algorithms in Identifying Similarities. In: 2016 IEEE Trustcom/BigDataSE/ISPA. Institute of Electrical and Electronics Engineers, 2016, ISBN 978-1-5090-3205-1, S. 1782–1787, doi:10.1109/TrustCom.2016.0274 (englisch, uel.ac.uk [PDF]).
1 2 Jonathan Oliver, Chun Cheng, Yanggui Chen: TLSH – A Locality Sensitive Hashing. In: 2013 Fourth Cybercrime and Trustworthy Computing Workshop. Institute of Electrical and Electronics Engineers, 2013, ISBN 978-1-4799-3076-0, S. 7–13, doi:10.1109/ctc.2013.9 (englisch, github.com [PDF]).
↑ Jonathan Oliver, Josiah Hagen: Designing the Elements of a Fuzzy Hashing Scheme. In: 2021 IEEE 19th International Conference on Embedded and Ubiquitous Computing (EUC). Institute of Electrical and Electronics Engineers, 2021, ISBN 978-1-6654-0036-7, S. 1–6, doi:10.1109/euc53437.2021.00028 (englisch, tlsh.org [PDF]).
↑ Jonathan Oliver, Chun Cheng, Yanggui Chen: Open Source Similarity Digests DFRWS August 2016. In: tlsh.org. Abgerufen am 28. September 2025 (englisch).
↑ Andrew Tridgell: spamsum README. In: Samba. Abgerufen am 28. September 2025 (englisch).
↑ Andrew Tridgell: spamsum.c. In: Samba. Abgerufen am 28. September 2025 (englisch).
↑ Vassil Roussev: Data Fingerprinting with Similarity Digests. In: Kam-Pui Chow (Hrsg.): Advances in Digital Forensics VI (= IFIP Advances in Information and Communication Technology. Band 337). Springer Nature, Berlin 2010, ISBN 978-3-642-15505-5, S. 207–226, doi:10.1007/978-3-642-15506-2_15 (englisch, hal.science).
↑ Fast Clustering of High Dimensional Data Clustering the Malware Bazaar Dataset. In: tlsh.org. Abgerufen am 28. September 2025 (englisch).
↑ Usage of fuzzy hashes. In: Rspamd. Abgerufen am 25. September 2025 (englisch).
Fuzzy check module. In: Rspamd. Abgerufen am 25. September 2025 (englisch).
↑ Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, Geoffrey G. Zweig: Syntactic clustering of the Web. In: Computer Networks and ISDN Systems. Nr. 29. Elsevier Science, 1997, S. 1157–1166, doi:10.1016/S0169-7552(97)00031-7 (englisch, ethz.ch [PDF]).

[ssdeep-1] 1 2 3 Jesse Kornblum: Identifying almost identical files using context triggered piecewise hashing. In: Digital Investigation. Nr. 3. Elsevier, 2006, S. 91–97, doi:10.1016/j.diin.2006.06.015 (englisch).

[cryptographic-hash-functions-2] Saif Al-Kuwari, James H. Davenport, Russell J. Bradford: Cryptographic Hash Functions: Recent Design Trends and Security Notions. In: Report 2011/565. Cryptology ePrint Archive (englisch, iacr.org).

[NIST.SP.800-168-3] Frank Breitinger, Barbara Guttman, Michael McCarrin, Vassil Roussev, Douglas White: Approximate Matching: Definition and Terminology. In: NIST Special Publication 800-168. National Institute of Standards and Technology, 2014, doi:10.6028/NIST.SP.800-168 (englisch).

[beyond-precision-recall-4] Fabio Pagani, Matteo Dell'Amico, Davide Balzarotti: Beyond Precision and Recall: Understanding Uses (and Misuses) of Similarity Hashes in Binary Analysis. In: Proceedings of the Eighth ACM Conference on Data and Application Security and Privacy. Association for Computing Machinery, 2018, ISBN 978-1-4503-5632-9, S. 354–365, doi:10.1145/3176258.3176306 (englisch, pagabuc.me [PDF]).

[forensic-malware-analysis-5] Nikolaos Sarantinos, Chafika Benzaïd, Omar Arabiat: Forensic Malware Analysis: The Value of Fuzzy Hashing Algorithms in Identifying Similarities. In: 2016 IEEE Trustcom/BigDataSE/ISPA. Institute of Electrical and Electronics Engineers, 2016, ISBN 978-1-5090-3205-1, S. 1782–1787, doi:10.1109/TrustCom.2016.0274 (englisch, uel.ac.uk [PDF]).

[tlsh-6] 1 2 Jonathan Oliver, Chun Cheng, Yanggui Chen: TLSH – A Locality Sensitive Hashing. In: 2013 Fourth Cybercrime and Trustworthy Computing Workshop. Institute of Electrical and Electronics Engineers, 2013, ISBN 978-1-4799-3076-0, S. 7–13, doi:10.1109/ctc.2013.9 (englisch, github.com [PDF]).

[designing-the-elements-7] Jonathan Oliver, Josiah Hagen: Designing the Elements of a Fuzzy Hashing Scheme. In: 2021 IEEE 19th International Conference on Embedded and Ubiquitous Computing (EUC). Institute of Electrical and Electronics Engineers, 2021, ISBN 978-1-6654-0036-7, S. 1–6, doi:10.1109/euc53437.2021.00028 (englisch, tlsh.org [PDF]).

[open-source-similarity-8] Jonathan Oliver, Chun Cheng, Yanggui Chen: Open Source Similarity Digests DFRWS August 2016. In: tlsh.org. Abgerufen am 28. September 2025 (englisch).

[spamsum_README-9] Andrew Tridgell: spamsum README. In: Samba. Abgerufen am 28. September 2025 (englisch).

[spamsum.c-10] Andrew Tridgell: spamsum.c. In: Samba. Abgerufen am 28. September 2025 (englisch).

[sdhash-11] Vassil Roussev: Data Fingerprinting with Similarity Digests. In: Kam-Pui Chow (Hrsg.): Advances in Digital Forensics VI (= IFIP Advances in Information and Communication Technology. Band 337). Springer Nature, Berlin 2010, ISBN 978-3-642-15505-5, S. 207–226, doi:10.1007/978-3-642-15506-2_15 (englisch, hal.science).

[fast-clustering-12] Fast Clustering of High Dimensional Data Clustering the Malware Bazaar Dataset. In: tlsh.org. Abgerufen am 28. September 2025 (englisch).

[rspamd-doc-13] Usage of fuzzy hashes. In: Rspamd. Abgerufen am 25. September 2025 (englisch).
Fuzzy check module. In: Rspamd. Abgerufen am 25. September 2025 (englisch).

[syntactic-clustering-14] Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, Geoffrey G. Zweig: Syntactic clustering of the Web. In: Computer Networks and ISDN Systems. Nr. 29. Elsevier Science, 1997, S. 1157–1166, doi:10.1016/S0169-7552(97)00031-7 (englisch, ethz.ch [PDF]).