Нечёткое хеширование
Нечёткое хеширование (англ. fuzzy hashing, также англ. similarity hashing) — это алгоритмическая технология для обнаружения данных, схожих по содержанию, но не идентичных другим данным. В отличие от криптографических хеш-функций, которые дают совершенно разные хеши даже при незначительных изменениях входных данных, нечёткое хеширование позволяет выявлять сходство между ними. Эта методика используется, например, для идентификации вредоносного ПО, а также находит применение в предотвращении утечек данных и обнаружении различных версий программного кода[1].
Предпосылки
Хеш-функция — это математический алгоритм, сопоставляющий данным произвольного размера фиксированный по размеру выходной код. Для выявления дубликатов или проверки известных файлов в больших коллекциях нередко используют криптографические хеш-функции, такие как SHA-256. Однако криптографические хеш-функции не позволяют определять степень сходства между файлами, поскольку одним из их свойств является так называемый эффект лавины — даже небольшое изменение входных данных полностью изменяет итоговое значение хеша, делая его некоррелированным с предыдущим.
Нечёткое хеширование предназначено для решения этой задачи — выявления похожих, но не идентичных данных. Для этого используются специальные алгоритмы, при которых двум схожим входным последовательностям будут соответствовать схожие значения хеша. Это свойство противоположно эффекту лавины, который необходим в криптографических алгоритмах.
Также нечёткое хеширование позволяет обнаруживать случаи, когда один объект содержится внутри другого.
Подходы
Существует несколько различных подходов к построению алгоритмов нечёткого хеширования:
- Контекстно-детектируемое поблочное хеширование — разбивает входные данные на части, вычисляет «обычный» хеш для каждой части, а затем объединяет их результаты в одну строку.
- Локально-чувствительное хеширование — размещает схожие входные объекты в одни и те же «корзины», что может быть использовано для кластеризации данных и поиска ближайших соседей.
Известные инструменты и алгоритмы
- spamsum — инструмент, написанный Андрю Триджеллом для обнаружения сходства электронной почты с известным спамом с помощью нечёткого хеширования. Для каждого письма вычисляется нечёткий хеш, который сравнивается с хешами известных спам-писем; результат сравнения выражается в диапазоне от 0 (полное несовпадение) до 100 (полное совпадение). Если результат высок, письмо классифицируется как спам.
- Нильсимса-хеш — алгоритм локально-чувствительного хеширования, фокусирующийся на борьбе со спамом.
- ssdeep — инструмент нечёткого хеширования, основанный на контекстно-детектируемом поблочном хешировании, для сравнения файлов.
- sdhash — инструмент, использующий фильтр Блума для установления того, содержится ли один файл в другом или насколько два файла похожи друг на друга.
- TLSH — схема локально-чувствительного хеширования для сравнения файлов по степени схожести, применяемая, в частности, для кластеризации вредоносных программ.
- Rspamd использует нечёткое хеширование для обнаружения спам-писем, в том числе с помощью алгоритма шинглов.
Примечания
Литература
- Kornblum J. Identifying almost identical files using context triggered piecewise hashing // Digital Investigation. 2006. Vol. 3, Supplement (сентябрь 2006), с. 91-97. doi:10.1016/j.diin.2006.06.015.
- Roussev V. Data Fingerprinting with Similarity Digests // В: Advances in Digital Forensics VI (IFIP Advances in Information and Communication Technology), берлинское изд-во Springer, 2010. Т. 337, с. 207—226. doi:10.1007/978-3-642-15506-2_15.
- Oliver J., Hagen J. Designing the Elements of a Fuzzy Hashing Scheme // 2021 IEEE 19th International Conference on Embedded and Ubiquitous Computing (EUC), IEEE, 2021. С. 1-6. doi:10.1109/euc53437.2021.00028.
- Oliver J., Cheng C., Chen Y. TLSH — A Locality Sensitive Hash // 2013 Fourth Cybercrime and Trustworthy Computing Workshop, IEEE, 2013. С. 7-13. doi:10.1109/ctc.2013.9.