mvHash-B - A New Approach for Similarity Preserving Hashing

back to overview

Reference

Breitinger, F., Astebol, K., Baier, H., & Busch, C. (2013). mvHash-B - A New Approach for Similarity Preserving Hashing. Paper presented at the IT Security Incident Management and IT Forensics (IMF).

Publication type

Paper in Conference Proceedings

Abstract

The handling of hundreds of thousands of files is a major challenge in today's IT forensic investigations. In order to cope with this information overload, investigators use fingerprints (hash values) to identify known files automatically using blacklists or whitelists. Besides detecting exact duplicates it is helpful to locate similar files by using similarity preserving hashing (SPH), too. We present a new algorithm for similarity preserving hashing. It is based on the idea of majority voting in conjunction with run length encoding to compress the input data and uses Bloom filters to represent the fingerprint. It is therefore called mvHash-B. Our assessment shows that mvHash-B is superior to other SPHs with respect to run time efficiency: It is almost as fast as SHA-1 and thus faster than any other SPH algorithm. Additionally the hash value length is approximately 0.5% of the input length and hence outperforms most existing algorithms. Finally, we show that the robustness of mvHash-B against active manipulation is sufficient for practical purposes.

Persons

Organizational Units

  • Institute of Information Systems
  • Hilti Chair for Data and Application Security

Original Source URL

Link

DOI

http://dx.doi.org/doi:10.1109/IMF.2013.18