Bringing order to approximate matching: Classification and attacks on similarity digest algorithms

Martín-Pérez, M. (Universidad de Zaragoza) ; Rodríguez, R.J. (Universidad de Zaragoza) ; Breitinger, F.

Resumen: Fuzzy hashing or similarity hashing (a.k.a. bytewise approximate matching) converts digital artifacts into an intermediate representation to allow an efficient (fast) identification of similar objects, e.g., for blacklisting. They gained a lot of popularity over the past decade with new algorithms being developed and released to the digital forensics community. When releasing algorithms (e.g., as part of a scientific article), they are frequently compared with other algorithms to outline the benefits and sometimes also the weaknesses of the proposed approach. However, given the wide variety of algorithms and approaches, it is impossible to provide direct comparisons with all existing algorithms. In this paper, we present the first classification of approximate matching algorithms which allows an easier description and comparisons. Therefore, we first reviewed existing literature to understand the techniques various algorithms use and to familiarize ourselves with the common terminology. Our findings allowed us to develop a categorization relying heavily on the terminology proposed by NIST SP 800-168. In addition to the categorization, this article presents an abstract set of attacks against algorithms and why they are feasible. Lastly, we detail the characteristics needed to build robust algorithms to prevent attacks. We believe that this article helps newcomers, practitioners, and experts alike to better compare algorithms, understand their potential, as well as characteristics and implications they may have on forensic investigations.

Idioma: Inglés

DOI: 10.1016/j.fsidi.2021.301120

Año: 2021

Publicado en: Forensic science international. Digital investigation 36, Suplem. (2021), 301120 [9 pp.]
ISSN: 2666-2825

Factor impacto JCR: 1.805 (2021)

Categ. JCR: COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS rank: 94 / 112 = 0.839 (2021) - Q4 - T3
Categ. JCR: COMPUTER SCIENCE, INFORMATION SYSTEMS rank: 131 / 163 = 0.804 (2021) - Q4 - T3

Factor impacto CITESCORE: 5.0 - Social Sciences (Q1) - Medicine (Q2) - Computer Science (Q2)

Factor impacto SCIMAGO: 1.23 - Computer Science Applications (Q1) - Pathology and Forensic Medicine (Q1) - Medical Laboratory Technology (Q1) - Information Systems (Q1)

Financiación: info:eu-repo/grantAgreement/ES/DGA/T21-20R-DISCO
Financiación: info:eu-repo/grantAgreement/ES/MICIU/Medrese-RTI2018-098543-B-I00
Financiación: info:eu-repo/grantAgreement/ES/MINECO-INCIBE/INCIBEC-2015-02486
Financiación: info:eu-repo/grantAgreement/ES/MINECO-INCIBE/INCIBEI-2015-27300

Tipo y forma: Artículo (Versión definitiva)

Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)