Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Fuzzy hashing
open-in-new
<h2 id="background">Background</h2> <p>A <a href="/facts/Hash_function/rk6MlCt3">hash function</a> is a mathematical algorithm which maps arbitrary-sized data to a fixed size output. Many solutions use <a href="/facts/Cryptographic_hash_functions/cuxkgbST">cryptographic hash functions</a> like <a href="/facts/SHA-256/P59oPeGq">SHA-256</a> to detect duplicates or check for known files within large collection of files.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> However, cryptographic hash functions cannot be used for determining if a file is <i>similar</i> to a known file, because one of the requirements of a cryptographic hash function is that a small change to the input should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value (<a href="/facts/Avalanche_effect/hpYX5zu5">avalanche effect</a>) <a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>Fuzzy hashing exists to solve this problem of detecting data that is similar, but not exactly the same, as other data. Fuzzy hashing algorithms specifically use algorithms in which two similar inputs will generate two similar hash values. This property is the exact opposite of the avalanche effect desired in cryptographic hash functions. </p><p>Fuzzy hashing can also be used to detect when one object is contained within another.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p> <h2 id="approaches-for-fuzzy-hashing">Approaches for fuzzy hashing</h2> <p>There are a few approaches used for building fuzzy hash algorithms:<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a><a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <ul><li>Context Triggered Piecewise Hashing (CTPH), which constructs a hash by splitting the input into multiple pieces, calculating traditional hashes for each piece, and then combining those traditional hashes into a single string.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li><a href="/facts/Locality_Sensitive_Hashing/hj8UllQG">Locality Sensitive Hashing</a> places similar input items into the same "buckets", which can be used for <a href="/facts/Cluster_analysis/HUeDnWPt">data clustering</a> and <a href="/facts/Nearest_neighbor_search/R6QTyAph">nearest neighbor searches</a></li></ul> <h2 id="notable-fuzzy-hashing-tools-and-algorithms">Notable fuzzy hashing tools and algorithms</h2> <ul><li>spamsum is a tool written by <a href="/facts/Andrew_Tridgell/TdEys7vd">Andrew Tridgell</a> that uses fuzzy hashing to determine whether an email is similar to known spam. It operates by generating a fuzzy hash for an email that it compares against the fuzzy hashes from known spam emails to generate a match result between 0 (complete mismatch) to 100 (perfect match). If the match result is high enough, the email is classified as spam.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> <a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li> <li><a href="/facts/Nilsimsa_Hash/HL4FnVaI">Nilsimsa Hash</a> is an anti-spam focused <a href="/facts/Locality-sensitive_hashing/hj8UllQG">locality-sensitive hashing</a> algorithm.</li> <li>ssdeep is a fuzzy hashing tool based on context-piecewise triggered hashing to compare files. <a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a></li> <li>sdhash is a fuzzy hashing tool based on using <a href="/facts/Bloom_filter/Gq2WVE37">bloom filters</a> to determine whether one file is contained within another or how similar two files are to each other.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a></li> <li>TLSH is a locality sensitive hashing scheme for comparing whether files are similar to each other and has been used for malware clustering.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Nilsimsa_Hash/HL4FnVaI">Nilsimsa Hash</a></li> <li><a href="/facts/Locality-sensitive_hashing/hj8UllQG">Locality-sensitive hashing</a></li> <li><a href="/facts/Checksum/AqxQ0I8g">Checksum § Fuzzy checksum</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Breitinger, Frank (May 2014). "NIST Special Publication 800-168" (PDF). NIST Publications. doi:10.6028/NIST.SP.800-168. Retrieved January 11, 2023. <a href="https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-168.pdf" target="_blank">https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-168.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Pagani, Fabio; Dell'Amico, Matteo; Balzarotti, Davide (2018-03-13). "Beyond Precision and Recall" (PDF). Proceedings of the Eighth ACM Conference on Data and Application Security and Privacy. New York, NY, USA: ACM. pp. 354–365. doi:10.1145/3176258.3176306. ISBN 9781450356329. Retrieved December 12, 2022. <a href="9781450356329" target="_blank">9781450356329</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Sarantinos, Nikolaos; Benzaïd, Chafika; Arabiat, Omar (2016). "Forensic Malware Analysis: The Value of Fuzzy Hashing Algorithms in Identifying Similarities". 2016 IEEE Trustcom/BigDataSE/ISPA (PDF). pp. 1782–1787. doi:10.1109/TrustCom.2016.0274. ISBN 978-1-5090-3205-1. S2CID 32568938. 10.1109/TrustCom.2016.0274. <a href="978-1-5090-3205-1" target="_blank">978-1-5090-3205-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Kornblum, Jesse (2006). "Identifying almost identical files using context triggered piecewise hashing". Digital Investigation. 3, Supplement (September 2006): 91–97. doi:10.1016/j.diin.2006.06.015. Retrieved June 30, 2022. <a href="https://www.sciencedirect.com/science/article/pii/S1742287606000764" target="_blank">https://www.sciencedirect.com/science/article/pii/S1742287606000764</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Oliver, Jonathan; Cheng, Chun; Chen, Yanggui (2013). "TLSH -- A Locality Sensitive Hash" (PDF). 2013 Fourth Cybercrime and Trustworthy Computing Workshop. IEEE. pp. 7–13. doi:10.1109/ctc.2013.9. ISBN 978-1-4799-3076-0. Retrieved December 12, 2022. <a href="978-1-4799-3076-0" target="_blank">978-1-4799-3076-0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Kornblum, Jesse (2006). "Identifying almost identical files using context triggered piecewise hashing". Digital Investigation. 3, Supplement (September 2006): 91–97. doi:10.1016/j.diin.2006.06.015. Retrieved June 30, 2022. <a href="https://www.sciencedirect.com/science/article/pii/S1742287606000764" target="_blank">https://www.sciencedirect.com/science/article/pii/S1742287606000764</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Al-Kuwari, Saif; Davenport, James H.; Bradford, Russell J. (2011). "Cryptographic Hash Functions: Recent Design Trends and Security Notions". Cryptology ePrint Archive. Report 2011/565. <a href="https://eprint.iacr.org/2011/565" target="_blank">https://eprint.iacr.org/2011/565</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Breitinger, Frank (May 2014). "NIST Special Publication 800-168" (PDF). NIST Publications. doi:10.6028/NIST.SP.800-168. Retrieved January 11, 2023. <a href="https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-168.pdf" target="_blank">https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-168.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Oliver, Jonathan; Hagen, Josiah (2021). "Designing the Elements of a Fuzzy Hashing Scheme" (PDF). 2021 IEEE 19th International Conference on Embedded and Ubiquitous Computing (EUC). IEEE. pp. 1–6. doi:10.1109/euc53437.2021.00028. ISBN 978-1-6654-0036-7. Archived from the original (PDF) on 14 April 2021. Retrieved 14 April 2021. <a href="978-1-6654-0036-7" target="_blank">978-1-6654-0036-7</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Oliver, Jonathan; Cheng, Chun; Chen, Yanggui (2013). "TLSH -- A Locality Sensitive Hash" (PDF). 2013 Fourth Cybercrime and Trustworthy Computing Workshop. IEEE. pp. 7–13. doi:10.1109/ctc.2013.9. ISBN 978-1-4799-3076-0. Retrieved December 12, 2022. <a href="978-1-4799-3076-0" target="_blank">978-1-4799-3076-0</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>"Open Source Similarity Digests DFRWS August 2016" (PDF). tlsh.org. Retrieved December 11, 2022. <a href="https://github.com/trendmicro/tlsh/blob/master/TLSH_Introduction.pdf" target="_blank">https://github.com/trendmicro/tlsh/blob/master/TLSH_Introduction.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>"spamsum README". samba.org. Retrieved December 11, 2022. <a href="https://www.samba.org/ftp/unpacked/junkcode/spamsum/README" target="_blank">https://www.samba.org/ftp/unpacked/junkcode/spamsum/README</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>"spamsum.c". samba.org. Retrieved December 11, 2022. <a href="https://download.samba.org/pub/unpacked/junkcode/spamsum/spamsum.c" target="_blank">https://download.samba.org/pub/unpacked/junkcode/spamsum/spamsum.c</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Kornblum, Jesse (2006). "Identifying almost identical files using context triggered piecewise hashing". Digital Investigation. 3, Supplement (September 2006): 91–97. doi:10.1016/j.diin.2006.06.015. Retrieved June 30, 2022. <a href="https://www.sciencedirect.com/science/article/pii/S1742287606000764" target="_blank">https://www.sciencedirect.com/science/article/pii/S1742287606000764</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Roussev, Vassil (2010). "Data Fingerprinting with Similarity Digests". Advances in Digital Forensics VI. IFIP Advances in Information and Communication Technology. Vol. 337. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 207–226. doi:10.1007/978-3-642-15506-2_15. ISBN 978-3-642-15505-5. ISSN 1868-4238. <a href="978-3-642-15505-5" target="_blank">978-3-642-15505-5</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>"Fast Clustering of High Dimensional Data Clustering the Malware Bazaar Dataset" (PDF). tlsh.org. Retrieved December 11, 2022. <a href="https://tlsh.org/papersDir/n21_opt_cluster.pdf" target="_blank">https://tlsh.org/papersDir/n21_opt_cluster.pdf</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> </ol>