Что такое нечеткий хэш
Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Хруничев Р.В.
Текст научной работы на тему «Обзор методов нечеткого поиска текстовой информации»
Обзор методов нечеткого поиска текстовой информации
ассистент кафедры информационных систем
Нечеткий поиск - это поиск информации, при котором выполняется сопоставление информации заданному образцу поиска или близкому к этому образцу значению. Алгоритмы нечеткого поиска используются в большинстве современных поисковых систем, например, для проверки орфографии [1].
Рассмотрим задачу нечеткий поиск текстовой информации. В данном случае задача может принимать следующий вид: есть текстовая информация определенного размера, пусть пользователь вводит слово или фразу для поиска, необходимо найти в тексте все совпадения с заданным словом с учетом возможных допустимых различий. Например, при запросе пользователя «интернет» нужно найти «интерн», «интернат» и другие слова.
Как же можно оценить сходство двух слов в тексте? Для этого используются специальные метрики нечеткого поиска. Метрикой нечеткого поиска называют функцию расстояния между двумя словами, позволяющую оценить степень их сходства в данном контексте. В качестве метрик используют расстояния Хемминга, Левенштейна, Дамерау-Левенштейна.
Расстояние Хемминга - это число позиций, в которых соответствующие символы двух слов одинаковой длины различны [2]. Согласно определению, расстояние Хемминга имеет один существенный недостаток - сравнивать можно только слова одинаковой длины. Из-за этого данную метрику практически не применяют на практике.
Расстояние Левенштейна или расстояние редактирования -это минимальное количество операций (вставки одного символа и замены одного символа на другой), необходимых для преобразования одной строки в другую [1]. Расстояние Левенштейна применяют для исправления ошибок в словах, биоинформатике для сравнения хромосом и для полнотекстового поиска. Данная метрика имеет следующие недостатки:
при перестановке слов в предложении расстояние принимает большое значение;
расстояние Левенштейна значительно зависит от длины
Расстояние Левенштейна может быть велико для больших похожих слов, но при этом, если есть два коротких слова значительно отличающихся друг от друга, то тогда расстояние Левенштейна будет мало.
Расстояние Дамерау-Левенштейна - это мера разницы двух строк символов, определяемая как минимальное количество операций вставки, удаления, замены и перестановки соседних символов, необходимых для перевода одной строки в другую. Данная метрика отличается от расстояния Левенштейна только добавлением новой операции (перестановки).
Для расчета расстояния Левенштейна используют метод Вагнера-Фишера. Составляем матрицу преобразований по формуле указанной на рис. 1.
Рис. 1. Вычисление матрицы преобразования
2 = 0, j = 0 j = 0, г > 0 I = 0, j > о
При расчете матрицы используются обозначения: S и S2 -сравниваемые слова, 5,[/] - i-й символ слова, m(S[i], S2[/) - 1, если 5,[/] = S2[/ или 0 в противном случае. В результате будет составлена матрица преобразования символов, где ее значения - это расстояния для преобразования символов. Итоговым значением преобразования одной строки в другую будет элемент с максимальными индексами. Пример такой матрицы преобразования представлен на рис. 2.
Итоговое расстояние между словами «дагестан» и «арестант» будет равно 3.
Данный алгоритм требует довольно значительных затрат памяти и времени выполнения. Однако он может быть упрощен путем сокращения количества вычислений. Сравнение строк может происходить с учетом морфем, так могут подвергаться трансформации только суффиксы слов или окончания. Другим вариантом снижения затрат может быть использование ограничений по количеству сравнений.
Рис. 2. Матрица преобразования для двух слов
Согласно [3] при реализации данного метода для мобильного приложения для проверки корректности ввода слова, приложение работало больше минуты. При этом был использован словарь объемом 90 000 слов.
Другим вариантом реализации нечеткого поиска может служить алгоритм хеширования по сигнатуре. Данный метод основан на составлении специальных хеш-таблиц слов. При этом каждому слову в тексте в соответствие ставится битовая маска (сигнатура).
Сигнатурой sign(w) слова wбудем называть вектор размерности т, k-й элемент которого равняется единице, если в слове wесть символ а такой, что Да) = к, и нулю в противном случае. Номером
сигнатуры слова будем называть число H(w) = Zmo12isign,w)M [4].
Данный метод требует значительных временных затрат на составление хеш-таблиц. Что так же затрудняет его использование в мобильных приложениях. Однако данный метод достаточно прост при реализации и позволяет выполнять быстрый поиск как по полному совпадению слова, так и при наличии одной или двух ошибок в слове. Проблема временных затрат может быть решена путем создания готовых индексов по текстам или словарям. Так же можно перенести индексы на мобильное устройство и записать их в базу данных реализованную средствами SQLite.
Алгоритм расширения выборки основан на составлении наиболее возможных вариантов изменения слова. При этом может быть задано количество возможных ошибок. Данный метод достаточно удобен при работе со словарем. Фактически данный метод является своеобразной реализацией метода Вагнера-Фишера, но с учетом того, что будут искаться не все возможные изменения, а только часто встречаемые. Данный метод ускоряет поиск, но может не дать желаемый результат и значительно замедляется при увеличении словаря.
При сравнении двух строк или слов, с учетом максимально возможного количества расхождений можно выделить в словах (строках) общие части. После чего можно выполнять поиск по таким частям. Такой метод получил название метод N-грамм, а совпадения и являются N-граммами. Метод N-грамм состоит из нескольких этапов:
1. Составляются индексные базы по указанным N-граммам.
2. После чего введенное слово для поиска тоже разбивается на N-граммы.
3. После чего выполняется полный перебор значений по указанным N-граммам.
Пример такого метода показан на рис. 3.
Рис. 3. Поиск ошибок методом N-грамм
Метод N-грамм не всегда находит ошибки. Данная проблема происходит, например, когда пользователь ошибся в одной букве в корне слова при вводе. Так же данный метод при обращении к базе данных каждый раз будет выполнять перебор 10-20% информации. При наличии словарей больших размеров данный метод будет долго выполняться и требовать больших ресурсов и мощностей, что достаточно затруднительно при работе с мобильными устройствами.
При оптимизации нечеткого поиска часто возникает вопрос по организации данных таким образом, чтобы поиск выполнялся быстрее и тратил меньше ресурсов. Одним из вариантов подобной организации данных служат деревья В. Буркхарда и Р. Келлера (BK-деревья). Данные деревья строятся на основании метрик Левенштейна или Даме-рау-Левенштейна. Пример такого дерева представлен на рис. 4.
Данный метод позволяет сократить время выполнения поиска за счет более удобной структуры данных, однако усложняет алгоритм поиска.
В заключение хотелось бы сказать, что были рассмотрены наиболее известные методы нечеткого поиска текстовой информации:
Рис. 4. Дерево Буркхарда и Келлера
метод Вагнера-Фишера, метод N-грамм, метод хеширования по сигнатуре, алгоритм расширения выборки, деревья Буркхарда-Келлера. Каждый из данных методов имеет свои достоинства и свои недостатки.
Ключевым недостатком данных методов является время выполнения поиска. При работе с мобильными устройствами время является важным критерием работы приложения. Однако данные методы можно оптимизировать за счет их комбинаций или внесения дополнительных условий, задаваемых пользователем или разработчиком.
2. Конышева Л.К. Основы теории нечетких множеств : учеб. пособие / Л.К. Конышева, Д.М. Назаров. - СПб. : Изд-во. Питер, 2011 -192 с.
4. БойцовЛ.М. Использование хеширования по сигнатуре для поиска по сходству. Прикладная математика и информатика / Л.М. Бойцов. - М. : Изд-во факультета ВМиК, МГУ, 2000. - № 7.
В борьбе со зловредами вирусные аналитики используют множество методов и целый арсенал специального софта. Но самая первая из стоящих перед ними задач — определить, действительно ли им в руки попался вредоносный образец, или это что‑то безобидное. Решить ее помогает изучение показателя под названием «энтропия». Сегодня мы расскажем, как работает эта техника вирусного анализа.
Что такое энтропия? У этого понятия есть определения в разных областях науки, значащие в общих чертах одно и то же. В терминах информатики — это показатель хаотичности, или случайности распределения значений байтов в файле. Условимся, что под этим термином мы имеем в виду энтропию Шеннона. Того самого человека, который в 1948 году предложил использовать слово «бит» для обозначения наименьшей единицы информации.
Окунемся немного в математику. Энтропия любого файла в общем случае считается методом «скользящего окна» по всем байтам файла. Звучит страшно, но на самом деле проще, чем кажется. Чтобы понять принцип скользящего окна, достаточно взглянуть на рисунок.
Скользящее окно
Сначала рассчитываются частоты fi появления для каждого возможного значения байта (i = 0..255). Например, в первом окне значение байта согласно таблице ASCII (десятичное значение = 180) равно символу ´ . В итоге получается вот такая гистограмма по количествам вхождений определенных байтов в файле (ее ты можешь увидеть сам в любом Hex-редакторе).
Частотное распределение байтов в объекте в программе Hex Workshop
Затем найденные частоты (fi) суммируются по формуле ниже, и в результате мы получим значение энтропии.
Суть анализа энтропии заключается в том, что в скомпилированном файле обычной программы участки кода распределены более‑менее равномерно, как масло на бутерброде. При использовании кодировщиков или обфускации, упаковщиков, алгоритмов сжатия или вставок подобного рода кода в исходный файл такая равномерность нарушается. В файле появляются высокоэнтропийные области (как будто концентрированный белый шум) и области, менее подвергнутые обфускации или шифрованию (кодированию), если продолжить метафору бутерброда — комочки в масле или прослойки варенья.
Одно из характерных свойств алгоритмов сжатия — перераспределение частот встречаемости байтов кода (для всех 256 значений), что и станет заметно при анализе! В таких файлах будет высокая степень энтропии, близкая к максимальному значению 8 (2 8 = 256). То есть чем выше энтропия, тем меньше избыточности в файле.
Для закодированных (сжатых, зашифрованных) файлов на практике значение энтропии свыше семи можно считать почти 100%-м признаком применения преобразования кода, в то время как обычные файлы имеют энтропию в районе 2–6. Часто на практике энтропию в файле или выделенном фрагменте файла измеряют в процентах (тут иногда также используют понятие «избыточность»).
Показатель увеличения энтропии в зависимости от содержимого объекта
Представим, что есть какой‑то объект, в который потенциальный злоумышленник может внедрить вредоносный код. Он помещает полезную нагрузку в оригинальный файл, сжимает или зашифровывает определенный фрагмент данных, тем самым увеличивая энтропию. С точки зрения вирусного аналитика, можно быстро проверить образец и его секции на энтропию, понять, запакован он или обфусцирован, и, исходя из этой информации, выбрать методологию для анализа объекта. Итак, какие есть инструменты для подсчета энтропии?
Наиболее популярные инструменты для проведения анализа объектов по энтропии:
Воспользуемся первой программой — Detect It Easy (DIE) — и разберем пару примеров с популярным образцом Agent Tesla.
Agent Tesla — это модульное программное обеспечение для шпионажа, которое распространяется по модели malware-as-a-service под видом кейлоггера. Этот шпион способен извлекать и передавать на сервер злоумышленникам учетные данные пользователя из браузеров, почтовых клиентов и клиентов FTP, регистрировать содержимое буфера обмена, делать снимки экрана. На момент анализа официальный сайт разработчиков был недоступен.
На скриншотах интерфейса утилиты представлена следующая информация:
- тип файла;
- общая оценка энтропии;
- статус (запакован ли файл, если нет — перед нами «чистый» текст);
- подсчет энтропии искомого файла посекционно (Regions) и его статус;
- график энтропии (ось Х — смещение, ось Y — оценка энтропии).
Графики энтропии для образца Agent Tesla и еще одной его разновидности показаны ниже.
Результат анализа образца 1 в программе DIE Результат анализа образца 2 в программе DIE
Типичный пример — когда PE-заголовок читается (энтропия низкая), однако уровень энтропии оставшейся части файла очень высок, а секция кода не может быть статистически проанализирована, поскольку похожа на случайные значения. Это обычно свидетельствует о применении сжатия либо обфускации — типичного приема, чтобы сбить с толку антивирусы. По графику распределения энтропии можно на глаз определять закодированные фрагменты файла.
Примеры работы PortexAnalyzer
Помнишь, недавно мы писали о нечетком хеше SSDeep? Он не всегда отрабатывает корректно, особенно для семплов с низкой энтропией. Опытных пользователей SSDeep частенько смущает сам расчет схожести хешей и множество ложноположительных срабатываний, поэтому Вассил Руссев разработал алгоритм SDHash, который скользящим окном рассчитывает энтропию файла.
Особенность подхода — в тщательной фильтрации высоко- и низкоэнтропийных областей, а также в селекции для каждой области файла самых «редких» по энтропии участков. На основе оценки энтропии и сравнения данных по файлу в целом выбранные для сравнения объекты хешируются и с помощью фильтра Блума объединяются в единый хеш. Что такое фильтр Блума? За математическими формулировками отправляем тебя в Википедию. Если говорить кратко, он проверяет принадлежность хеша нашему множеству кусочных хешей и таким образом позволяет быстро определить принадлежность объекта к определенному множеству. В SDHash хеш (подпись) файла — это последовательность фильтров Блума, можешь использовать его для более продвинутого поиска похожих образцов.
На сегодняшний день анализ энтропии объектов используется множеством приложений и сервисов, относящихся к сфере информационной безопасности. Например, такой анализ применяется в алгоритмах машинного обучения для создания моделей оценки файла в антивирусном ПО. Также оценка энтропии используется при подсчете весов на этапе вынесения оценки вредоносности объекта в анти‑АРТ‑средствах защиты, то есть в процессе динамического анализа объектов.
Пример применения исследования энтропии на практике — модуль поведенческого анализа Polygon в составе комплекса Group-IB Threat Hunting Framework. На рисунке ниже показана часть отчета системы. В нем содержится информация об энтропии в разделе прочих поведенческих маркеров.
Часть отчета Polygon
Таким образом, анализ энтропии можно назвать базовой оценкой тестируемого объекта, которая позволяет понять, на какую секцию или часть файла следует обратить более пристальное внимание при анализе образца и понять, подозрителен ли образец в целом.
Что такое хеш
Криптографическая хеш-функция, чаще называемая просто хешем, — это математическое преобразование, переводящее произвольный входной массив данных в состоящую из букв и цифр строку фиксированной длины. Хеш считается криптостойким, если справедливо следующее:
- по хешу нельзя восстановить исходные данные;
- выполняется устойчивость к коллизиям, то есть невозможно получить из различных входных последовательностей одинаковые хеши.
MD5, SHA-1 и SHA-256 — наиболее популярные криптографические алгоритмы вычисления хеша, которые часто используются в детектировании вредоносного ПО. Еще совсем недавно вредонос опознавали только по сигнатуре (хешу) исполняемого файла.
Но в современных реалиях недостаточно знать просто хеш объекта, так как это слабый индикатор компрометации (IoC). IoC — это все артефакты, на основе которых может быть выявлен вредонос. Например, используемые им ветки реестра, подгружаемые библиотеки, IP-адреса, байтовые последовательности, версии ПО, триггеры даты и времени, задействованные порты, URL.
Рассмотрим «пирамиду боли» для атакующего, придуманную аналитиком в области информационной безопасности Дэвидом Бьянко. Она описывает уровни сложности индикаторов компрометации, которые злоумышленники используют при атаках. Например, если ты знаешь MD5-хеш вредоносного файла, его можно довольно легко и при этом точно обнаружить в системе. Однако это принесет очень мало боли атакующему — достаточно добавить один бит информации к файлу вредоноса, и хеш изменится. Таким образом вирус может переселяться бесконечно, и каждая новая его копия будет иметь отличный от других экземпляров хеш.
«Пирамида боли» Дэвида Бьянко
Если ты имеешь дело с множеством вредоносных образцов, становится понятно, что большинство из них по сути своей не уникальны. Злоумышленники нередко заимствуют или покупают исходники друг у друга и используют их в своих программах. Очень часто после появления в паблике исходных кодов какого-либо вредоносного ПО в интернете всплывают многочисленные поделки, состряпанные из доступных фрагментов.
Как же определить схожесть между разными образцами малвари одного семейства?
Для поиска такого сходства существуют специальные алгоритмы подсчета хеша, например нечеткое (fuzzy) хеширование и хеш импортируемых библиотек (imphash). Эти два подхода используют разные методы обнаружения для поиска повторно встречающихся фрагментов вредоносных программ, принадлежащих к определенным семействам. Рассмотрим эти два метода подробнее.
«Нечеткий» хеш — SSDeep
Если в криптографических хеш-функциях суть алгоритма состоит в том, что при малейшем изменении входных данных (даже одного бита информации) их хеш также значительно изменяется, то в нечетких хешах результат меняется незначительно или не изменяется вовсе. То есть нечеткие хеши более устойчивы к небольшим изменениям в файле. Поэтому подобные функции позволяют намного более эффективно обнаруживать новые модификации вредоносного ПО и не требуют больших ресурсов для расчета.
Нечеткое хеширование — это метод, при котором программа, такая как, например, SSDeep, вычисляет кусочные хеши от входных данных, то есть использует так называемое контекстно вызываемое кусочное хеширование. В англоязычных источниках этот метод называется context triggered piecewise hashing (CTPH aka fuzzy hashing).
На самом деле классификаций нечетких хешей довольно много. Например, по механизму работы алгоритмы делятся на piecewise hashing, context triggered piecewise hashing, statistically improbable features, block-based rebuilding. По типу обрабатываемой информации их можно разделить на побайтовые, синтаксические и семантические. Но если речь заходит о нечетких хешах, то это, как правило, CTPH.
Алгоритм SSDeep разработан Джесси Корнблюмом для использования в компьютерной криминалистике и основан на алгоритме spamsum. SSDeep вычисляет несколько традиционных криптографических хешей фиксированного размера для отдельных сегментов файла и тем самым позволяет обнаруживать похожие объекты. В алгоритме SSDeep используется механизм скользящего окна rolling hash. Его еще можно назвать рекурсивным кусочным хешированием.
Часто CTPH-подобные хеши лежат в основе алгоритмов локально чувствительных хешей — locality-sensitive hashing (LSH). В их задачи входит поиск ближайших соседей — approximate nearest neighbor (ANN), или, проще говоря, похожих объектов, но с чуть более высокоуровневой абстракцией. Алгоритмы LSH используются не только в борьбе с вредоносным ПО, но и в мультимедиа, при поиске дубликатов, поиске схожих генов в биологии и много где еще.
Алгоритм SSDeep
Как работает SSDeep? На первый взгляд, все довольно просто:
- он разделяет файл на более мелкие части и изучает их, а не файл в целом;
- он может определить фрагменты файлов, которые имеют последовательности одинаковых байтов, расположенных в схожем порядке, либо байты между двумя последовательностями, где они могут различаться как по значению, так и по длине.
Virus Total использует SSDeep, который выполняет нечеткое хеширование на загружаемых пользователями файлах. Пример — по ссылке.
Virus Total использует SSDeep
Итак, рубрика э-э-эксперименты! Возьмем по 18 образцов исполняемых файлов нашумевших вирусяк: среди них — MassLogger (имена образцов будут начинаться с аббревиатуры ML), Agent Tesla (AT) и Emotet (EMO). Только вот где мы найдем такое количество малвари? Да на базаре.
Мы будем работать с .EXE-семплами, у каждого из испытуемых объектов уникальная криптографическая хеш-сумма SHA-1. Перечислим их все (команда для любителей Linux: shasum ML ):
f59a138da63769720e61e37fe52030774472db19 ML1.exe bd57fd4002228352bf60186562d0dde87f4f33e5 ML2.exe 89ebb9ff3ab6c9a3330e798036bb81cec29c417f ML3.exe e9029f66cc313a41b22cb922da7f52a899ac166c ML4.exe 1dde9710a0d780b42678f41bbc949c82f13a74af ML5.exe 8c635bc0aaf4214024cf7342d5f186ebf6171652 ML6.exe 3cb9d16fa0bf3d72f12bf844e0a293d818512c54 ML7.exe 619480abce06d5221c1dd430233fa19ff7f863b5 ML8.exe ab1aed403d37d2f90f2a59505b0724927790841e ML9.exe 65e9d26cf5e6742bdf0a772f6c9692ec533aded7 ML10.exe 3e5b239ddab79130b5b8ffe623c6272d365774d8 ML11.exe c53e68fe71b695e2c7fb6c05aedb422bf5856f7b ML12.exe 6c610f5675f7fb4d78ca2b6e4be9ff43ba47c929 ML13.exe 10cf5e8f60ddac43813e5b8880aa84805e4a30d8 ML14.exe d7a1665e425fe63054c5c836b3807f58da43948a ML15.exe 98e0a38ab5db61a6eb7b50f4e09556af7f46978d ML16.exe 2c2010e2fa02f4c70ea9dd5083026d0138f655d5 ML17.exe 67ee652bc805fc8f5c9c653785b4d82baae0f78e ML18.exe
С использованием SSDeep рассчитаем кусочный хеш каждого из файлов и сохраним результат в файле командой ssdeep MassLogger/* > ML.ssd . На выходе получим следующее:
Выглядит пугающе, правда? Давай сравним объекты между собой (в выводе мы предварительно удалили дубли, оставив уникальные совпадения между семплами). Для этого используем следующую команду:
В выводе команды правый столбец — процент совпадения между семплами.
| ML10.exe matches ML.ssd:ML13.exe | (49) | | ML10.exe matches ML.ssd:ML15.exe | (49) | | ML10.exe matches ML.ssd:ML18.exe | (49) | | ML10.exe matches ML.ssd:ML6.exe | (47) | | ML10.exe matches ML.ssd:ML7.exe | (49) | | ML11.exe matches ML.ssd:ML14.exe | (49) | | ML11.exe matches ML.ssd:ML5.exe | (54) | | ML11.exe matches ML.ssd:ML9.exe | (52) | | ML13.exe matches ML.ssd:ML15.exe | (50) | | ML13.exe matches ML.ssd:ML18.exe | (50) | | ML13.exe matches ML.ssd:ML6.exe | (50) | | ML13.exe matches ML.ssd:ML7.exe | (50) | | ML14.exe matches ML.ssd:ML5.exe | (47) | | ML14.exe matches ML.ssd:ML9.exe | (47) | | ML15.exe matches ML.ssd:ML18.exe | (49) | | ML15.exe matches ML.ssd:ML6.exe | (47) | | ML15.exe matches ML.ssd:ML7.exe | (46) | | ML18.exe matches ML.ssd:ML6.exe | (60) | | ML18.exe matches ML.ssd:ML7.exe | (49) | | ML5.exe matches ML.ssd:ML9.exe | (49) | | ML6.exe matches ML.ssd:ML7.exe | (55) |
Получается, что в исследуемых семплах присутствуют стабильно кочующие участки кода, которые обеспечивают схожесть. Поскольку такой вывод, скажем честно, малоинформативен, для наглядности изобразим связи в виде графа.
Связи исследуемых семплов
Из 18 объектов оказалось всего восемь никак не связанных между собой образцов, но это пока. Тем не менее можно смело утверждать, что мы выявили целое семейство вредоносов. Теперь протестируем остальные объекты из других групп и сравним результаты.
Сразу изобразим граф связности для образцов Agent Tesla. Не будем перечислять хеш-суммы образцов, а сразу приступим к сравнению: сначала файлов между собой, затем с семплами MassLogger.
Граф связности для образцов Agent Tesla
Для Agent Tesla также обнаружено два семейства взаимосвязанных семплов и десять воинов-одиночек. Что дальше? Сравним SSDeep-хеши MassLogger с объектами Emotet. Пусто, нет совпадений. А если с Agent Tesla? Строим граф.
Сравнение MassLogger с Agent Tesla
Бинго! Совпадения есть, и взаимопроникновение фрагментов кода семейств Agent Tesla и MassLogger доказано.
Однако не всегда у исследователя достаточно семплов и образцов вредоносов других семейств — например, для семейства Emotet. На графе видно, что из всех 18 объектов 13 так или иначе связаны между собой, а семплы EMO3, EMO9, EMO11, EMO15 и EMO18 не нашли «друзей», и их мы отражать на рисунке не станем.
Взаимосвязи объектов на графе
Итак, что же в итоге у нас получилось? У групп MassLogger есть пять объектов, связанных с объектами Agent Tesla. Почему так вышло? Во-первых, это два кейлоггера, у них есть пересечения в функциональности. Во-вторых, они оба используют один и тот же загрузчик. В каждом из тестов находились связи (то есть сходства) между объектами более чем на 50%. Иными словами, из 18 образцов так или иначе были связаны между собой как минимум девять. Среди семплов нашлись по меньшей мере две группы связанных объектов, а у Emotet — сразу три группы. Теперь давай рассмотрим другой тип хеш-функций, и, возможно, мы найдем новые взаимосвязи.
TLS fingerprinting
Суть технологии в захвате элементов пакета приветствия клиента, которые остаются статичными от сеанса к сеансу для каждого клиента. На их основе можно создать «отпечаток пальца» для распознавания конкретного клиента в последующих сеансах. Записываются следующие поля:
версия записи TLS;
Кроме того, данные собираются из трех конкретных расширений (если они доступны):
алгоритм для шифрования данных;
хэш функция для проверки содержимого.
Использование такого набора данных позволяет с большой точностью идентифицировать используемый клиент (например, браузер).
Почему это круто:
Пакет приветствия клиента — это первый пакет в любом TLS-соединении. Это позволяет принимать решение о последующих мерах в начале сеанса до того, как потребуется подмена протокола или эмуляция.
Можно захватывать пакеты приветствия клиента TLS с высокой степенью точности по всем портам с абсолютно нулевым требованием для захвата обоих направлений потока. Это означает, что датчики в среде с асимметричной маршрутизацией или с ограничениями ресурсов, потенциально вызывающими отбрасывание пакетов, все равно могут собирать пакеты приветствия клиента, независимо от того, были ли они скрыты из-за работы на нестандартных портах.
Пакеты приветствия клиента возникают достаточно редко, поэтому дополнительная обработка хэшей не повлечет значительных затрат.
Наиболее очевидное использование TLS Fingerprinting – пассивное обнаружение. Технология позволяет обнаруживать широкий спектр потенциально нежелательного трафика, не требуя доступа к конечным точкам. Можно обнаруживать как конкретные вредоносы по их поведению и/или обращениям к командным центрам, так и обычный софт, используемый не по назначению или в обход действующих правил.
Например, к серверу Exchange могут обращаться только почтовые клиенты или браузер, если используется OWA, поэтому соединение из скрипта на Python будет подозрительным.
Есть несколько готовых реализаций, наиболее поддерживаемых комьюнити:
пассивный метод с использованием хэшей JA3 и JA3S;
активный инструмент снятия отпечатков пальцев с сервера TLS – хэши JARM.
Текст научной работы на тему «Применение метода ветвей и границ при решении задачи нечеткого поиска методом хеширования по сигнатуре в локальных базах данных»
Математика ft Математическое
Ссылка на статью: // Математика и Математическое моделирование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2017. № 03. С. 64-76.
Представлена в редакцию: 05.05.2017 Исправлена: 19.05.2017
© МГТУ им. Н.Э. Баумана
Применение метода ветвей и границ при решении задачи нечеткого поиска методом хеширования по сигнатуре в локальных базах данных
ХруНИЧеВ Р.В.1' ''ЬштсЬеу_гоЬег1:@та1[:ги
1Рязанский государственный радиотехнический университет, Рязань, Россия
В статье автор анализирует применение метода хеширования по сигнатуре при поиске в локальных базах данных. Указаны недостатки метода при таком типе поиска. Обоснована возможность уменьшения размера индекса сигнатуры при использовании лингвистических и статистических методов обработки текста. Показана актуальность задачи сравнения индексов запроса и образа терма в базе. Основное внимание автор уделяет анализу существующих методов сравнения индексов, обосновывается невозможность их применения к задаче нечеткого поиска. Разработана целевая функция для метода ветвей и границ, которая позволяет решить поставленную задачу при наличии разницы в одном бите индекса запроса и терма. результаты работы являются теоретическими. Автор указывает, что необходимы дальнейшие исследования в этом направлении, с целью усовершенствования алгоритма.
Ключевые слова: хеширование по сигнатуре; уменьшение размера индекса; сравнение битовых последовательностей; поиск в локальных БД; метод ветвей и границ
Важность задачи эффективного информационного поиска уже на протяжении нескольких десятков лет не теряет своей актуальности, кроме того, в связи с нарастающими объемами накопленных данных она только повышается. Поиск становится основной формой доступа к информации, причем потребность в сокращении временных затрат на отыскание нужных данных выходит на первое место [1 - 4].
Анализ существующей литературы показал, что проблема глобального поиска, решаемая и развиваемая такими компаниями, как Google, Yandex, Yahoo и др. находится на вершине научных исследований в данной области знаний, чего нельзя сказать о локальном поиске. Эксперты среди важнейших задач аналитико-синтетической обработки данных как средства информационного поиска выделяют индексирование документов и информационных запросов [5].
На данном этапе развития координатное индексирование [9] - основной метод организации поиска документов в системах разного уровня в силу простоты и быстродействия.
Сотрудник компании Яндекс Сметанин Н.И. в аналитическом обзоре [6] делает вывод о том, что при нечётком поиске алгоритм координатного индексирования "хеширование по сигнатуре" дает один из наилучших результатов с точки зрения временных затрат при поиске. Отметим, что в локальных базах данных (часто это обычный ПК, на котором хранится документация учреждения/подразделения) минимальные временные затраты при поиске, а также размер индекса являются главными характеристиками. Алгоритмы [6] индексирования анализируются только на временные затраты при поиске, в то время как задача размера индекса не освещается. Так, например, при хешировании по сигнатуре предполагается двухбайтовый формат индекса. Вероятно, на размер индекса алгоритмы не анализировались, поскольку предполагается глобальный поиск, где данный параметр не столь важен.
Основная цель работы - сократить временные и вычислительные затраты при поиске в локальных БД, посредством изменения размера индекса при хешировании, а также применением метода ветвей и границ, для которого разработать целевую функцию при заданном количестве ошибок (разнице в индексах запроса и образа терма).
В работе приведены теоретические выкладки по применению метода ветвей и границ для сравнения индексов. В пункте 1.1 приведено краткое описание метода хеширования по сигнатуре и его основные преимущества, а также обоснованы его недостатки при применении в локальных базах данных, содержащих предметную коллекцию документов. Далее в пункте 1.2 рассматриваются методы, применяя которые можно добиться сокращения размера индекса сигнатуры. Обоснование проблемы сравнения индексов при нечетком поиске, в пункте 1.3, доказывает актуальность проблемы уменьшения временных и вычислительных затрат при их обработке. В пункте 1.4, перечислены методы сравнения индексов и сделан вывод об их невозможном применении при нечетком поиске. В заключении основной части - пункте 1.5 - приведена функция предлагаемого алгоритма сравнения сумм индексов и показано, что применение метода ветвей и границ не только хорошо подходит для поставленной задачи, но и позволяет при правильном выборе параметров целевой функции добиться снижения вычислительных затрат.
1. Основная часть
Задача проводимого исследования - показать, что существующие алгоритмы, например, исключающего «ИЛИ» (побитовое сравнение), последовательного сравнения, регистра сдвига и др. не подходят для задачи нечеткого поиска, с точки зрения показателей вычислительных и временных затрат при реализации в локальных базах данных. Для метода ветвей и границ разработать и исследовать целую функцию на сравнение индексов терма запроса и его поискового образа при одном допустимом несовпадении битов.
1.1 Метод хеширования по сигнатуре
В качестве алгоритма для индексирования выделенных основ термов применим метод хеширования по сигнатуре, который обладает рядом преимуществ [10]:
- позволяет осуществлять с высоким быстродействием поиск на точное равенство и поиск, допускающий одну-две «ошибки» в задании поискового запроса;
- эффективен, как в случае «прямых» чтений с диска, так и из кэша;
- использует компактный индекс. При правильном выборе параметров объем индекса не более чем на 10-20% превышает размер файла, содержащего список терминов словаря;
- отличается простотой реализации.
Суть метода [10].Пусть задан непустой алфавит А и известны вероятности появления различных символов алфавита. Пусть также на множестве символов А задана функция /(а), отображающая буквы в числа от 1 до т. Эта функция, как несложно видеть, задает разбиение алфавита на т подмножеств.
Определение. Сигнатурой sign(ы) слова н будем называть вектор размерности т, к
- ый элемент которого равняется единице, если в слове н есть символ а такой, что / (а) = к, и нулю в противном случае. Номером сигнатуры слова будем называть число
Н(ы) = ^2i • sign(w)j+l. Н(ы) является хэш-функцией, отображающей множество
слов в отрезок целых чисел от 0 до 2т — 1, что позволяет организовать словарь в виде хеш-таблицы.
Процесс вычисления хеша: каждому биту хеша сопоставляется группа символов из алфавита. Бит 1 на позиции г в хеше означает, что в исходном слове присутствует символ из г-ой группы алфавита. Порядок букв в слове абсолютно никакого значения не имеет [11].
В таком алгоритме для полного покрытия к ошибок нужно изменять не менее 2к бит в хеше. Время работы, в среднем, при к «неполных» (вставки, удаления и транспозиции, а
также малая часть замен) ошибках: ОН|к • п / 2Н
Существующий алгоритм [6, 10, 11, 12] хеширования по сигнатуре при применении его в локальных базах данных обладает рядом недостатков:
1) обработка двухбайтовой сигнатуры требует значительных временных затрат;
2) распределение букв по группам в сигнатуре никак не обосновано (существуют битовые позиции, которые с большой долей вероятности принимают значение "0");
3) разница количества термов соответствующих различным сигнатурам велика;
4) при сравнении сигнатур терма запроса и поискового образа возможно большое количество совпадений.
1.2 Предлагаемая подход к сокращению размера индекса сигнатуры
Размер сигнатуры - одна из основных характеристик с точки зрения временных и вычислительных ресурсов на поиск при локальном поиске. Во-первых, необходимо хранить сам индекс и при добавлении новых документов в базу производить переиндексацию, что при больших размерах индекса приведет к значительным временным затратам. Во-вторых, при поиске происходит процесс вычисления значения хеш-функции и, чем больше индекс, тем больше вычислительные затраты.
Основной характеристикой локальных БД является их предметная ориентированность, поэтому применением словарей предметной области можно сократить число анализируемых термов и этим, сократить количество термов, приходящихся на одну сигнатуру.
В работах [6, 10, 11] рассматривается применение метода хеширования по сигнатуре при глобальном поиске, где применение предметных словарей не имеет смысла, поэтому количество термов на сигнатуру может быть велико. С этой точки зрения двухбайтовый формат сигнатуры обоснован, поскольку очень большое число термов на сигнатуру влияет на качество поиска. Однако, распределение символов языкового алфавита по группам в сигнатурах никак не обосновано - просто последовательное распределение. Очевидно, что, например, бит, соответствующий редко встречающимся символам «Щ» и «Ъ», в большинстве сигнатур будет принимать значение «0», т.е. хранение такого бита нецелесообразно.
При анализе локальных базах данных число участвующих в анализе термов достаточно просто сократить, применяя, например, статистические методы обработки (частотный анализ текста и закон Ципфа) [7, 8], предметные словари и лингвистическую обработку текстов. Таким образом, можно осуществить переход от двухбайтового формата к однобайтовому. Это может привести к увеличению числа термов, приходящихся на одну сигнатуру, но, поскольку поиск осуществляется в локальной базе, то их число не будет велико.
1.3. Потребность в сравнения индексов при нечетком поиске
Предварительно обозначим задачу необходимости разработки целевой функции для метода ветвей и границ с возможными изменениями в одной битопозиции (при одном пропуске/вставке, замене символов, приводящей к изменению одного бита). Ранее было показано, что уменьшение размера сигнатуры до однобайтового формата может привести к появлению нескольких термов - подмассив общего количества термов, выделенных в процессе анализа документов всей коллекции локальной базы данных, - соответствующих одной сигнатуре. Значение хеш-функции Н (), в случае безошибочного запроса, является ключом к тому подмассиву индексов термов, которые соответствуют одной сигнатуре ). В случае, если сигнатуре sign(wi) соответствует один терм, то разработка целевой функции не требуется - полученный терм удовлетворяет задаче поиска. Но если же, подмассив термов включает более одного элемента (в литературе употребляют термин
"коллизия"), то уже возникает необходимость решения задачи обработки индексов термов образов массива/подмассива на предмет соответствия индексу терма запроса.
Также отметим, что задача нечеткого поиска основана на предположении о возможном допущении ошибок (пропуске буквы или наборе лишней, замена символов) в запросе. Перестановка букв в терме не приводит к изменению сигнатуры. Но, при возможном допущении ошибки возможны следующие гипотезы:
1) изменения индекса не произошло (в запросе ещё есть символы алфавита из данной группы), что не привело к изменению сигнатуры и по ключу Н(Ж) найден под-массив, в котором один терм образ - соответствие установлено;
2) изменения индекса не произошло, что не привело к изменению сигнатуры и по ключу Н (Ж) найден подмассив, в котором несколько термов образов; требуется сравнить все индексы термов образов подмассива на соответствие индексу запроса;
4) произошло изменение одного бита сигнатуры, но алгоритм "не понимает", что совершена ошибка и вычисленному сигнатурному ключу Н(Ж) находится соответствие - подмассив, в котором нет термов, соответствующих запросу, даже с учетом возможного изменения в одном бите терма запроса; в этом случае нужно просмотреть всю базу индексов на соответствие индекса запросу;
5) произошло изменение одного бита сигнатуры, но алгоритм "не понимает", что совершена ошибка и вычисленному сигнатурному ключу Н (Ж) находится соответствие - подмассив, в котором есть термы, соответствующие запросу, с учетом того, что возможно изменение в одном бите терма запроса; в этом случае нужно просмотреть подмассив индексов на соответствие индекса запросу.
Как видим, в четырех из пяти возможных случаев, придется осуществлять сравнения индексов. Здесь и становится актуальной задача разработки оптимальной целевой функции, позволяющей сократить временные и вычислительные затраты на сравнение индексов образа терма в базе и терма запроса.
1.4 Существующих методы побитового сравнения индексов
В аналитической статье [13] автор рассматривает задачу сравнения битовых последовательностей. Рассматриваются стандартные подходы к решению задачи сравнения, например, последовательное ("шаблонное") сравнение и регистр сдвига, но здесь же делается вывод о сложности реализации и больших временных затратах при реализации.
В качестве одного из возможных решений предлагается построение конечного автомата, но он не позволяет реализовать задачу нечеткого поиска, т.е. не допускает "мягкого" поиска.
Также в литературе изложены методы побитового исключающего "ИЛИ", побитового "И", побитового "ИЛИ", побитовое "НЕ", но эти методы также основан на принципе точного соответствия, и "мягкий" поиск не реализуют [14].
1.5 Предлагаемое решение задачи нечеткого поиска при возможном изменении
одного бита индекса запроса
Решение задачи разработки целевой функции возникает при реализации любой из четырех гипотез, указанных в предыдущем пункте. Основная задача формулируется следующим образом: для метода ветвей и границ разработать целевую функцию, позволяющую решить задачу нечёткого поиска с учетом возможного изменения в одном бите (допущении ошибки в запросе, которая привела к изменению индекса). Сразу оговоримся, что при большем числе изменений в битах запроса задача становится существенно сложнее и автором не ставится цель ее решения. В этом случае возможно существенное снижение качества поиска и целесообразность исследования ставится под вопрос.
Ключ Н (^) обращает поисковый алгоритм к подмассиву, в котором хранятся индексы образов термов, выделенных в процессе анализа, или же возникает задача сравнения всех индексов массива образов термов, выделенных в процессе анализа. Индексы термов могут быть получены, например, также по сигнатурному методу, где каждому символу алфавита соответствует один бит или любому другому методу, реализацией которого является индекс терма. Задача получения индексных последовательностей термов, выделенных в процессе анализа базы документов, автором не ставится. Здесь могут быть проведены дополнительные исследования на размер индекса и его возможного уменьшения, но данная задача не является предметом рассмотрения в данной статье.
Итак, приведем реализацию целевой функции для метода ветвей и границ, применительно к задаче нечеткого поиска и поясним суть ее применения.
Не будем глубоко погружаться в детали работы SSL/TLS (далее будем говорить TLS), но кратко поясним детали.
Использование TLS само по себе благо, так как с его помощью шифруются данные. Но с обратной стороны создатели вредоносов используют его же, чтобы скрываться в шифрованном трафике (в данной статье как раз будет уклон в эту сторону) и затруднять их обнаружение и нейтрализацию.
Чтобы инициировать сеанс TLS, клиент отправляет «пакет» приветствия серверу после трёхстороннего установления связи TCP. Этот «пакет» и способ его создания зависят от пакетов и методов шифрования, используемых при создании клиентского приложения. Если сервер принимает соединение TLS, он ответит пакетом приветствия, тем самым продолжая согласование шифрования.
Поскольку согласование шифрования TLS передаётся в открытом виде, то можно отследить и идентифицировать клиентские приложения.
В этом и суть технологии TLS fingerprinting, если кратко. А теперь немного подробнее.
Борис Осепов
Специалист ИБ. Увлекаюсь средствами анализа вредоносного ПО. Люблю проверять маркетинговые заявления на практике :)
Примеры реализации
Если нет возможности или желания использовать готовые решения от Palo Alto и пр., можно реализовать в своей инфраструктуре свое средство мониторинга трафика, например, на основе Zeek (ранее назывался Bro) – популярного open-source продукта, заточенного специально для этого.
Zeek собирает огромное количество информации из первоначального согласования TLS, т.к. оно обрабатывается в открытом виде. Таким образом, хотя мы не можем видеть всё, что связано с шифрованием TLS, мы всё же можем получить общее представление о том, что происходит.
Zeek умеет выполнять снятие отпечатков TLS с помощью хэша JA3\JA3S.
Если у нас уже есть Zeek, в него попадает трафик, то для полноценного мониторинга нам понадобится SIEM (можно обойтись и без SIEM, но тогда обрабатывать логи Zeek’а придется вручную). Допустим, SIEM у нас все же есть. Помимо инструментов обработки трафика и событий Zeek нам еще потребуются списки готовых хэшей, чтобы было с чем сравнивать.
В случае в JA3 – все просто. Есть готовый инструмент, к которому можно обращаться по API для проверки выявленного хэша JA3 и принятия решения – нормально это или не очень.
Хэши JA3S, соответствующие вредоносам, достать чуть сложнее. Есть, например, небольшая подборка тут, есть и еще, нужно только искать или считать самостоятельно.
С хешами JARM еще немного сложнее, если у вас нет Palo Alto, их нужно собирать по разрозненным отчетам аналитиков или считать самостоятельно и вести собственные белые и черные списки. Но на github тоже попадаются тематические подборки, например, эта. Мы ее задействуем в дальнейшем при проработке правил по JARM.
Далее приведем некоторые описания правил, которые мы реализуем у себя. Также есть неплохой доклад от Splunk с примерами алгоритмов и правил мониторинга по хэшам JA3/JA3S. Доступен здесь. Правила можно адаптировать под любую SIEM.
Выявление признака конкретного вредоноса по хэшам JA3\JA3S. Вот, например, готовые значения для Emotet и TrickBot:
Выявления нового хэша JA3, ранее не появляющегося в сети.
Список клиентского ПО в любой сети, как правило, достаточно статичен, и, если появится что-то новенькое – это однозначно повод разобраться. Правда, это может быть новая версия уже известного ПО, тогда ее нужно добавить в белый список.
Выявления хэшей JA3 не из белого списка.
Общее правило, которое позволит обратить внимание на любую активность, которая явно не помечена заранее как разрешенная. Сюда могут попасть, как новые ранее неизвестные клиентские устройства или приложения, так и вредоносы, попавшие к вам в сеть. В любом случае – трекать это стоит.
Выявления хэшей JA3\JA3S из чёрного списка.
Это правило нацелено на выявление хэшей заведомо вредоносного ПО.
Выявление обращений к C&C по хэшам JARM.
При выявлении обращения к TLS-серверу, неизвестному нам или ранее не появляющемуся в логах, необходимо посчитать его JARM хэш (можно вручную, можно скриптом или с использованием SOAR), при совпадении с хэшем, соответствующим известному C&C серверу, блокируем соединение, изолируем хост и расследуем инцидент.
Выявление JA3 хэшей, не характерных для системы.
При появлении на хостах с Windows JA3 хэшей, характерных для Linux или смартфонов (Android/IOS), стоит обратить внимание на такие хосты. Это может являться признаком работы вредоносов (ну или запущенного эмулятора/виртуалки в режиме NAT). Кейс особенно заслуживает внимание, если выявлен на рабочей станции обычного пользователя, далекого от мира IT.
Выявление JA3 хэшей, характерных для разных браузеров одного семейства.
Сейчас достаточно сложно на один хост поставить две разные версии Firefox или Chrome (виртуальные машины в режиме NAT не в счёт). Такое выявление может свидетельствовать о том, что злоумышленники пытались адаптироваться под установленный софт, но после обновления софта не успели или забыли обновить свой Fingerprint. Хост лучше изолировать и провести расследование.
Выявление JA3 хэшей, характерных для популярных сетевых библиотек языков программирования.
Важно: Список хэшей JARM (и JA3S тоже) необходимо регулярно пополнять новыми выявленными C&C серверами, полученную самостоятельно или от сторонних исследователей.
При использовании средств защиты сети, которые умеют вычислять хэши JARM самостоятельно и на лету, соединения с серверами из черных списков можно и нужно блокировать автоматически.
В завершении хотим подчеркнуть, что развитие и популяризация технологии TLS Fingerprinting, по нашему мнению, совсем не за горами, и способствует этому внедрение TLS 1.3.
В стандарте TLS 1.3 появилась возможность шифровать имя запрашиваемого сайта – Encrypted SNI (ESNI), и безопасники потеряли возможность видеть, куда идёт обращение.
Правда ESNI уже запретили в Китае, и были попытки блокировок в России. Однако ESNI стал часто встречаться, в том числе в инструментах злоумышленников, и без TLS fingerprinting становится сложно понимать, куда происходят обращения в сети.
Авторы статьи:
Михаил Кравченко, SOC-аналитик;
Александр Минин, руководитель направления Threat Intelligence @AAMinin;
Анна Шестакова, руководитель направления мониторинга ИБ.
Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Мосалев П.М.
Хеш «четкий»
Ханс Петер Лун из IBM еще в 1940-е разрабатывал системы для анализа информации, в том числе исследовал вопросы хранения, передачи и поиска текстовых данных. Это привело его к созданию алгоритмов преобразования, а затем и к хешированию информации в качестве способа поиска телефонных номеров и текста. Так индексация и концепция «разделяй и властвуй» сделали свои первые шаги в области вычислительной техники.
Сейчас существует множество алгоритмов хеширования, отличающихся криптостойкостью, скоростью вычисления, разрядностью и другими характеристиками.
Мы привыкли ассоциировать хеш-функции с криптографическими хеш-функциями. Это распространенный инструмент, который используется для решения целого ряда задач, таких как:
- аутентификация;
- электронная подпись;
- обнаружение вредоносного ПО (как файлов, так и их маркеров компрометации).
В сегодняшней статье речь пойдет о том, как различные алгоритмы хеширования помогают нам бороться с зловредным ПО.
Хеш импортируемых библиотек — imphash
Imphash расшифровывается как import hash — «хеш импортов», то есть всех импортируемых программой библиотек, прописанных в исполняемом файле Windows Portable Executable (PE). Чтобы вычислить imphash, все импортированные библиотеки и связанные с ними функции выгружаются в строковом формате, объединяются, а затем криптографически хешируются. Virus Total также высчитывает по этому алгоритму хеш для PE-файлов.
Virus Total также использует imphash
Естественно, злоумышленники знают о таком алгоритме и могут его обойти, сделав свой вирус более модульным. Например, можно загружать каждый модуль в память только при необходимости или динамически загружать библиотеки, сохраняя объем импорта настолько малым, насколько позволяет компилятор. При этом любой импорт переносится в память только во время выполнения, а не транслируется в таблице импорта в PE-файле. Вирусы пишут люди, а люди — существа ленивые, нужно немного потрудиться, чтобы перевести работу программы в такой формат.
Перейдем к практике и найдем взаимосвязи среди наших исследуемых групп объектов. Начнем с MassLogger. Появились ли новые связи? Да, мы получили три группы связанных объектов — их imphash идентичны!
Три новые группы связанных объектов с общими imphash
Изобразим общие imphash файлов в виде графа. Тут со всеми объектами получается полносвязный граф, так что не суди строго, если какого-то ребра графа не будет! 🙂
Общие imphash файлов
Сравним с предыдущим графом из секции экспериментов с SSDeep.
Сравнение графов
Теперь объединим два получившихся графа в группы по их вершинам.
Объединим оба графа
Получается, что среди 18 образцов MassLogger не нашли себе «друзей» всего три объекта: ML1, ML2 и ML4, а это всего 17% от общего количества. Таким образом, используя две техники, мы выявили и подтвердили взаимосвязи вредоносных семплов и их «группировки».
Далее разберем остальные семейства вредоносных файлов. Agent Tesla по imphash разделился на две большие группы.
Деление Agent Tesla по imphash
Сравним с предыдущим графом из секции тестов с SSDeep.
Сравнение графа с предыдущим
Объединим два получившихся графа в группы по их вершинам.
Объединяем два графа в группы по их вершинам
Imphash дополнил связи, которые были выявлены на этапе тестирования с SSDeep, и продемонстрировал более целостную картину. Идентичный с левой группой imphash присутствует в образцах группы MassLogger — ML5, ML9, ML11 и ML14.
Далее рассмотрим группу малвари Emotet.
Группа Emotet
Сравни с предыдущим графом из секции тестов с SSDeep. Напомним, что семплы EMO3, EMO9, EMO11, EMO15 и EMO18 не нашли себе «друзей» в прошлом тесте.
Объединим два получившихся графа в группы по их вершинам.
Сравним графы, объединив их по вершинам
Опа! Недаром червь Emotet получил такое распространение. В наш тест попали довольно хитрые образцы, у которых, судя по всему, в явном виде не присутствует таблица импортов, а следовательно, отсутствует imphash. Скорее всего, в них используется одна из техник, которые мы перечисляли в разделе об этом типе хеширования.
Анализируя графы взаимосвязей, можно заметить, что благодаря комбинации imphash и SSDeep мы получили новые взаимосвязи между объектами, тем самым значительно расширив базу знаний об исследуемых образцах. И это знание позволяет с относительно малыми затратами эффективно дополнять сигнатурный анализ вредоносного ПО достаточно надежными отпечатками образцов по классу, семейству или типу малвари.
Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Хруничев Р.В.
В статье автор анализирует применение метода хеширования по сигнатуре при поиске в локальных базах данных. Указаны недостатки метода при таком типе поиска. Обоснована возможность уменьшения размера индекса сигнатуры при использовании лингвистических и статистических методов обработки текста. Показана актуальность задачи сравнения индексов запроса и образа терма в базе. Основное внимание автор уделяет анализу существующих методов сравнения индексов, обосновывается невозможность их применения к задаче нечеткого поиска. Разработана целевая функция для метода ветвей и границ , которая позволяет решить поставленную задачу при наличии разницы в одном бите индекса запроса и терма. результаты работы являются теоретическими. Автор указывает, что необходимы дальнейшие исследования в этом направлении, с целью усовершенствования алгоритма.
Method of Branches and Boundaries to Solve a Fuzzy Search Problem by Hash Signature Method in Local Databases
The article highlights a relevant problem of fuzzy information search in local databases. A choice of the hash signature method was based on the existing analysis of coordinate indexing methods for global search. When searching, it provides the least time characteristics.
Борис Осепов
Специалист ИБ. Увлекаюсь средствами анализа вредоносного ПО. Люблю проверять маркетинговые заявления на практике :)
Создатели вредоносных программ используют массу разных методов, чтобы скрыть свои творения от антивирусных средств и статических-динамических анализаторов. Однако и антивирусы не лыком шиты: для поиска «родственных» семплов они используют продвинутые алгоритмы хеширования. Сегодня мы расскажем, как работают эти алгоритмы, — с подробностями и наглядными примерами.
На практике в большинстве случаев существующая база или ядро вредоноса повторно используется для создания новой разновидности малвари. Вирусописатели особо не заморачиваются с затратной по времени разработкой новых «качественных» вирусов, а просто используют имеющиеся образцы.
Этот повторно используемый код может быть собран заново с помощью другого компилятора, из него могут быть удалены или, наоборот, в него могут быть добавлены новые функции. Обновляются некоторые библиотеки, меняется распределение кода внутри файла (при этом применяются новые компоновщики, пакеры, обфускация и так далее). Смысл таких преобразований — придать хорошо знакомой антивирусу вредоносной программе новый вид. В этом случае видоизмененная версия вируса какое-то время останется необнаруженной. Тем не менее существуют способы детектирования такого рода переупаковок и модификаций.
Эти техники обнаружения зачастую используются для анализа большого массива данных и поиска в нем общих элементов. Практическими примерами использования похожих техник могут быть глобально распределенные базы знаний, такие как Virus Total и базы антивирусных компаний, а также подходы Threat Intelligence.
JA3 и JA3S
Метод JA3 используется для сбора десятичных значений байтов для следующих полей в пакете приветствия клиента: версия TLS, набор шифров, список расширений протоколов TLS, эллиптические кривые и форматы эллиптических кривых. Затем он объединяет эти значения вместе по порядку, используя символ «,» для разграничения каждого поля и «-» для разграничения каждого значения в каждом поле.
Порядок полей следующий:
Если в ClientHello нет расширений TLS, поля остаются пустыми:
Эти строки затем хэшируются MD5. Пример отпечатка JA3:
JA3S – это хэш идентификации сервера. Метод JA3S заключается в сборе десятичных значений байтов для следующих полей в пакете приветствия сервера: версия TLS, набор шифров и список расширений протоколов TLS. После сбора значений, происходит процесс объединения этих значений вместе по порядку, используя «,» для разграничения каждого поля и «-» для разграничения каждого значения в каждом поле.
Порядок полей, следующий:
Если в Server Hello нет расширений TLS, поля остаются пустыми.
Эти строки затем хэшируются MD5 для создания 32-символьного отпечатка пальца.
Это отпечаток JA3S:
JA3 и JA3S – это методы снятия отпечатков TLS. JA3 отслеживает способ, которым клиентское приложение обменивается данными через TLS, а JA3S отслеживает ответ сервера. Вместе они создают отпечаток криптографического согласования между клиентом и сервером.
Теперь перейдем к описанию активного метода JARM.
Отпечатки JARM можно использовать:
убедиться, что все серверы в группе имеют одинаковую конфигурацию TLS;
сгруппировать разрозненные серверы в сети Интернет по конфигурации, указав, например, что сервер может принадлежать Google, Yandex или Apple;
определить приложения или инфраструктуру по умолчанию;
выявить командные центры и других вредоносные серверы в сети Интернет.
Первые 30 символов состоят из шифра и версии TLS, выбранных сервером для каждого из 10 отправленных приветствий клиента. «000» означает, что сервер отказался согласовывать приветствие с этим клиентом. Остальные 32 символа представляют собой усеченный хэш SHA256 совокупных расширений, отправленных сервером, без учета данных сертификата x509. При сравнении отпечатков JARM, если первые 30 символов совпадают, но последние 32 отличаются, это будет означать, что серверы имеют очень похожие конфигурации, принимают одинаковые версии и шифры, но используют различные расширения, что не позволяет их считать полностью идентичными.
Исторически так сложилось, что индустрия кибербезопасности была сосредоточена в основном на индикаторах компрометации (IOC) и индикаторах атаки (IOA). То есть когда вредоносное ПО/хост и т.п. будут кем-то обнаружены, исследователи или вендоры платформ TI вычленяют уникальные или не очень признаки выявленного вредоноса или атаки типа IP, домена, хэша файла и т.п. и публикуют их в «чёрных списках». Проблема в том, что к этому моменту вредоносное ПО уже распространено, и специалисты ИБ автоматически переходят в оборону.
Интернет-сканирование JARM в сочетании с другими метаданными и историческим анализом даёт возможность упреждающей идентификации IOC для новых вредоносов. Например, можно сканировать Интернет с помощью JARM, сопоставлять известные результаты JARM с историей домена, IP и репутацией вместе с данными сертификата для создания черного списка. Это позволяет перейти к возможности программного создания высокоточных списков блокировки до того, как первая вредоносная программа будет распространена.
Можно использовать JARM автоматически сканируя все хосты назначения, детектируемые в сети компании, для обогащения событий, и использовать сводную таблицу, чтобы не сканировать одни и те же хосты несколько раз. Затем можно запускать запросы заведомо плохих JARM или использовать список для корреляции.
Чтобы упростить процесс, можно использовать готовое решение. В настоящее время хэши JARM умеют считать продукты Palo Alto Networks и используют их API для обогащения целевого JARM.
Читайте также: