Нечеткое хеширование

Нечеткое хеширование , также известное как хеширование по сходству. ^[1] — это метод обнаружения данных, которые похожи , но не совсем совпадают с другими данными. В этом отличие от криптографических хэш-функций , которые разработаны так, чтобы иметь существенно разные хеш-функции даже при незначительных различиях. Нечеткое хеширование использовалось для идентификации вредоносного ПО ^[2]^[3] и имеет потенциал для других приложений, таких как предотвращение потери данных и обнаружение нескольких версий кода. ^[4]^[5]

Фон

Хэш -функция — это математический алгоритм, который сопоставляет данные произвольного размера с выходными данными фиксированного размера. Многие решения используют криптографические хэш-функции, такие как SHA-256, для обнаружения дубликатов или проверки известных файлов в большой коллекции файлов. ^[4] Однако криптографические хэш-функции нельзя использовать для определения того, похож ли файл на известный файл, поскольку одно из требований криптографической хэш-функции состоит в том, что небольшое изменение входных данных должно изменить хеш-значение настолько сильно, что новое хеш-значение выглядит некоррелированным со старым значением хеш-функции ( лавинный эффект ) ^[6]

Нечеткое хеширование существует для решения проблемы обнаружения данных, которые похожи, но не совсем совпадают с другими данными. Алгоритмы нечеткого хеширования специально используют алгоритмы, в которых два одинаковых входных сигнала генерируют два одинаковых значения хеш-функции. Это свойство является полной противоположностью лавинного эффекта, желаемого в криптографических хэш-функциях.

Нечеткое хеширование также можно использовать для определения того, содержится ли один объект внутри другого. ^[1]

Подходы к нечеткому хешированию

Существует несколько подходов, используемых для построения алгоритмов нечеткого хеширования: ^[7]^[5]

Частичное хеширование, запускаемое контекстом (CTPH), при котором хэш создается путем разделения входных данных на несколько частей, вычисления традиционных хэшей для каждой части, а затем объединения этих традиционных хэшей в одну строку. ^[8]
Хеширование с учетом местоположения помещает схожие входные элементы в одни и те же «корзины», которые можно использовать для кластеризации данных и поиска ближайших соседей.

Известные инструменты и алгоритмы нечеткого хеширования

spamsum — это инструмент, написанный Эндрю Триджелом , который использует нечеткое хеширование, чтобы определить, похоже ли электронное письмо на известный спам. Он работает путем создания нечеткого хеша для электронного письма, который сравнивается с нечеткими хэшами известных спам-сообщений, чтобы получить результат соответствия от 0 (полное несоответствие) до 100 (идеальное совпадение). Если результат совпадения достаточно высок, электронное письмо классифицируется как спам. ^[9] ^[10]
Nilsimsa Hash — это алгоритм хеширования, ориентированный на защиту от спама и зависящий от местоположения .
ssdeep — это инструмент нечеткого хеширования, основанный на кусочно-зависимом хешировании для сравнения файлов. ^[4]
sdhash — это инструмент нечеткого хеширования, основанный на использовании фильтров Блума для определения того, содержится ли один файл в другом или насколько два файла похожи друг на друга. ^[11]
TLSH — это схема хеширования с учетом местоположения для сравнения файлов на предмет схожести друг с другом, которая используется для кластеризации вредоносных программ. ^[12]

См. также

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Брайтингер, Франк (май 2014 г.). «Специальная публикация NIST 800-168» (PDF) . Публикации НИСТ . дои : 10.6028/NIST.SP.800-168 . Проверено 11 января 2023 г.
^ Пагани, Фабио; Делл'Амико, Маттео; Бальзаротти, Давиде (13 марта 2018 г.). «За пределами точности и отзыва» (PDF) . Материалы восьмой конференции ACM по безопасности и конфиденциальности данных и приложений . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 354–365. дои : 10.1145/3176258.3176306 . ISBN 9781450356329 . Проверено 12 декабря 2022 г.
^ Сарантинос, Николаос; Бензаид, Чафика; Арабиат, Омар (2016). «Судебно-медицинский анализ вредоносных программ: ценность алгоритмов нечеткого хеширования в выявлении сходств» . IEEE Trustcom/BigDataSE/ISPA, 2016 г. (PDF) . стр. 1782–1787. дои : 10.1109/TrustCom.2016.0274 . ISBN 978-1-5090-3205-1 . S2CID 32568938 . 10.1109/ТрастКом.2016.0274.
^ Jump up to: Перейти обратно: ^а ^б ^с Корнблюм, Джесси (2006). «Идентификация почти идентичных файлов с использованием контекстно-зависимого кусочного хеширования» . Цифровое расследование . 3, Приложение (сентябрь 2006 г.): 91–97. дои : 10.1016/j.diin.2006.06.015 . Проверено 30 июня 2022 г.
^ Jump up to: Перейти обратно: ^а ^б Оливер, Джонатан; Ченг, Чун; Чен, Янгуй (2013). «TLSH — хэш, чувствительный к местоположению» (PDF) . 2013 Четвертый семинар по киберпреступности и надежным вычислениям . IEEE. стр. 7–13. дои : 10.1109/ctc.2013.9 . ISBN 978-1-4799-3076-0 . Проверено 12 декабря 2022 г.
^ Аль-Кувари, Саиф; Давенпорт, Джеймс Х.; Брэдфорд, Рассел Дж. (2011). «Криптографические хеш-функции: последние тенденции проектирования и понятия безопасности» . Архив электронной печати по криптологии . Отчет 2011/565.
^ Оливер, Джонатан; Хаген, Иосия (2021). «Проектирование элементов схемы нечеткого хеширования» (PDF) . 2021 IEEE 19-я Международная конференция по встраиваемым и повсеместным вычислениям (EUC) . IEEE. стр. 1–6. дои : 10.1109/euc53437.2021.00028 . ISBN 978-1-6654-0036-7 . Архивировано из оригинала (PDF) 14 апреля 2021 года . Проверено 14 апреля 2021 г.
^ «Дайджесты сходства с открытым исходным кодом DFRWS, август 2016 г.» (PDF) . tlsh.org . Проверено 11 декабря 2022 г.
^ «Спам README» . Самба.орг . Проверено 11 декабря 2022 г.
^ "спамсум.с" . Самба.орг . Проверено 11 декабря 2022 г.
^ Руссев, Василий (2010). «Отпечатки данных с помощью дайджестов сходства». Достижения в цифровой криминалистике VI . ИФИП: Достижения в области информационных и коммуникационных технологий. Том. 337. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 207–226. дои : 10.1007/978-3-642-15506-2_15 . ISBN 978-3-642-15505-5 . ISSN 1868-4238 .
^ «Быстрая кластеризация многомерных данных. Кластеризация набора данных базара вредоносного ПО» (PDF) . tlsh.org . Проверено 11 декабря 2022 г.

[NIST.SP.800-168-1] Jump up to: Перейти обратно: ^а ^б Брайтингер, Франк (май 2014 г.). «Специальная публикация NIST 800-168» (PDF) . Публикации НИСТ . дои : 10.6028/NIST.SP.800-168 . Проверено 11 января 2023 г.

[Beyond_Precision_and_Recall:_Understanding_Uses_(and_Misuses)_of_Similarity_Hashes_in_Binary_Analysis-2] Пагани, Фабио; Делл'Амико, Маттео; Бальзаротти, Давиде (13 марта 2018 г.). «За пределами точности и отзыва» (PDF) . Материалы восьмой конференции ACM по безопасности и конфиденциальности данных и приложений . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 354–365. дои : 10.1145/3176258.3176306 . ISBN 9781450356329 . Проверено 12 декабря 2022 г.

[Forensic_Malware_Analysis:_The_Value_of_Fuzzy_Hashing_Algorithms_in_Identifying_Similarities-3] Сарантинос, Николаос; Бензаид, Чафика; Арабиат, Омар (2016). «Судебно-медицинский анализ вредоносных программ: ценность алгоритмов нечеткого хеширования в выявлении сходств» . IEEE Trustcom/BigDataSE/ISPA, 2016 г. (PDF) . стр. 1782–1787. дои : 10.1109/TrustCom.2016.0274 . ISBN 978-1-5090-3205-1 . S2CID 32568938 . 10.1109/ТрастКом.2016.0274.

[ssdeep-4] Jump up to: Перейти обратно: ^а ^б ^с Корнблюм, Джесси (2006). «Идентификация почти идентичных файлов с использованием контекстно-зависимого кусочного хеширования» . Цифровое расследование . 3, Приложение (сентябрь 2006 г.): 91–97. дои : 10.1016/j.diin.2006.06.015 . Проверено 30 июня 2022 г.

[tlsh-5] Jump up to: Перейти обратно: ^а ^б Оливер, Джонатан; Ченг, Чун; Чен, Янгуй (2013). «TLSH — хэш, чувствительный к местоположению» (PDF) . 2013 Четвертый семинар по киберпреступности и надежным вычислениям . IEEE. стр. 7–13. дои : 10.1109/ctc.2013.9 . ISBN 978-1-4799-3076-0 . Проверено 12 декабря 2022 г.

[Cryptographic_Hash_Functions:_Recent_Design_Trends_and_Security_Notions-6] Аль-Кувари, Саиф; Давенпорт, Джеймс Х.; Брэдфорд, Рассел Дж. (2011). «Криптографические хеш-функции: последние тенденции проектирования и понятия безопасности» . Архив электронной печати по криптологии . Отчет 2011/565.

[Designing_the_Elements_of_a_Fuzzy_Hashing_Scheme-7] Оливер, Джонатан; Хаген, Иосия (2021). «Проектирование элементов схемы нечеткого хеширования» (PDF) . 2021 IEEE 19-я Международная конференция по встраиваемым и повсеместным вычислениям (EUC) . IEEE. стр. 1–6. дои : 10.1109/euc53437.2021.00028 . ISBN 978-1-6654-0036-7 . Архивировано из оригинала (PDF) 14 апреля 2021 года . Проверено 14 апреля 2021 г.

[Open_Source_Similarity_Digests_DFRWS_August_2016-8] «Дайджесты сходства с открытым исходным кодом DFRWS, август 2016 г.» (PDF) . tlsh.org . Проверено 11 декабря 2022 г.

[spamsum_README-9] «Спам README» . Самба.орг . Проверено 11 декабря 2022 г.

[spamsum.c-10] "спамсум.с" . Самба.орг . Проверено 11 декабря 2022 г.

[sdhash-11] Руссев, Василий (2010). «Отпечатки данных с помощью дайджестов сходства». Достижения в цифровой криминалистике VI . ИФИП: Достижения в области информационных и коммуникационных технологий. Том. 337. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 207–226. дои : 10.1007/978-3-642-15506-2_15 . ISBN 978-3-642-15505-5 . ISSN 1868-4238 .

[Fast_Clustering_of_High_Dimensional_Data_Clustering_the_Malware_Bazaar_Dataset-12] «Быстрая кластеризация многомерных данных. Кластеризация набора данных базара вредоносного ПО» (PDF) . tlsh.org . Проверено 11 декабря 2022 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]