Критерии "открытого текста" для программ

Хочу открыть новую темку для обсуждения.

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

А вообще-говоря, общий вопрос остался. В криптографии он так и называется - отбраковка по критерию открытого текста (для обычного человеческого языка). Что собратья по разуму думают про решение проблемы "открытого текста" для программ? Есть ли какие-то общие методы и алгоритмы?

 

Думаю, нужно сначала определить на чем писана программа, в зависимости от этого искать присущие данному компиллятору конструкции.

 

Предположим что это уже известно. Кстати, криптографы всегда исходят из предположения, что противоположной стороне известен алгоритм, неизвестным является ключ. Поэтому это не будет сильным допущением.

Итак, известно, что программа написана на некоем языке высокого уровня и построен исполняемый файл. Будем также предполагать, что в исходном тексте нет "неожиданных" ассемблерных вставок, содержащих инструкции, не используемые компилятором.

 

А чем откомпилированный текст программы так сильно отличается от какого-либо другого неоптимально кодированного открытого текста ?

Те же неравномерности частот символов, биграмм и триграмм ... По этому делу куча книг написана.



А то, что бинарный код неоптимально кодирован, так я думаю никто с этим спорить не будет - односимвольный Хаффман его на 25-30% без проблем сжимает, а LZSS-based алгоритмы и до 45% если мне не изменяет память.



+ дополнительные отклонения от статистики могут привносить в бинарный код компиляторы, как уже сказал Broken Sword

 

Про алгоритмы у Шнаера почитай

Для программ... Компиляторы например делает пролог/эпилог ф-ции

push ebp

mov ebp, esp

...

pop ebp

leave

retn

А это уже 3 байта извесного текста. Или подставляют nop между ними

...

pop ebp

retn

NOP

push ebx

...

Это 2 байта извесного текста.

 

SteelRat

Про этот способ я уже упоминал (первое сообщение). Если знаешь свою позицию в коде, то можешь сделать предположения о том, что дальше последует. Хороший способ, но, во-первых это не критерий открытого текста, а критерий для отбраковки. Во-вторых, не всегда им можно воспользоваться, например, тебе известно:

mov eax,...

многоточие означает, что тебе неизвестен адрес, откуда загрузится регистр (а может он загрузится из другого регистра?). Сколько здесь вариантов? Дофига. Вот здесь бы и понадобился искомый критерий - перебираешь огромное количество ключей и по некоему алгоритму отсеиваешь ненужное.

 

OLS

Регулярностью, читаемостью, осмысленностью. Достаточно? Это для непосвященного - скмопилированный код похож на случайную последовательность. Неравномерность, наверное, имеет место, но она какая-то плавающая. Например, часто должен встречаться старший байт адреса сегмента данных. Я что-то не встречал анализа частот встречаемости (в том числе мультиграмм). Может просветишь, где?

 

Для Явы вот тут занимаются :

www.cs.nuim.ie/~dod/pubs/02-ire.pdf



Так а самому то не хочется прогнать штук ...дцать exe-файлов ? Кроме частотного анализа n-грамм, есть ведь еще статистики расстояний между ними. Только анализ все равно придется выполнять рассматривая поток как байт-ориентированный, иначе ты можешь попасть не на начало кода команды и вся статистика "полетит".

 

OLS

По этому делу куча книг написана

Спасибо хотя бы за кусочек кучи, почитаю.

 

OLS

Так а самому то не хочется прогнать штук ...дцать exe-файлов



Если честно, не хочется. Методы первичного анализа на основе частот встречаемости символов, пар символов и троек символов - это классика, но я не уверен (настаивать не буду, все надо проверять), что в нашем случае это будет самый лучший критерий.

 

crypto

Слушай OLSа, он дело говорит

Скомпилированные инструкции не являются случайной последовательностью, в исполняемом коде имеется избыточночть.

В принципе, правильность расшифровки можно опредлять так:

1. считаем энтропию расшифрованного куска

2. если энтропия выше некоторого порога -- берем следующий ключ

3. пытаемся дизассемблировать расшифрованный код (проверяем корректность длин инструкций, опкодов и т.п.)



"правильных" открытых текстов может быть несколько -- все зависит от длины шифртекста и избыточности кода...

 

Спасибо хотя бы за кусочек кучи, почитаю.



Я имел в виду книг по анализу биграмм и триграмм вообще.

 

flankerx

если энтропия выше некоторого порога



Вот как бы порог этот определить?



"правильных" открытых текстов может быть несколько



Я бы сказал даже - один с точностью до эквивалентных ключей (алгоритм считается известным)



Такими методами пользуются криптографы при первичном анализе. Мне кажется, что для программного кода можно придумать нечто значительно лучшее. Какие-то мысли смутно бродят в голове, но я никак не могу их четко обозначить. Наверное, слишком мало материала...

 

2crypto

ты строишь модель бинарного откомпилированного кода



при построении любой модели есть два подхода :



- эмпирический : наблюдаем (в данном случае) за большим количеством программ и строим закономерности исходя из увиденного, не вдаваясь в логику, почему именно такие закономерности наблюдаются



- аналитический : анализируем синтаксис языка высокого уровня, логику транслятора, набор инструкций микропроцессора (в двоичном виде) и как результат получаем модель, построенную "сверху вниз" (видимо именно это и хочешь сделать ты)



ну и конечно есть промежуточные варианты ...

 

OLS

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



По поводу аналитического ты все хорошо сказал, я согласен с подходом, вот только как бы все это математически формализовать. Тут думать надо, сказал чукча.

 

Имелся в виду нешифрованный бинарный код. То есть тебе нужно посчитать энропию для программ похожих на расшифровываемую и понять насколько они отличаются от случайного набора байт. Порог должен быть выбран таким, чтобы пресловутые программы имели бОльшую энропию, а случайные наборы байт - меньшую.

 

Как показывает практика, большинство программ (32-битный код) в TOP-10 самых популярных байтов имеют: 00, FF, 88..8B (mov /r), E8 (call), 8D (lea), 90/CC (зависит от компилера), 83 (add/or/adc/sbb/and/sub/xor/cmp), 24 (х/з почему, но популярна), 10, 04 (аналогично).

На разных компилерах статистика прыгает, но 00, FF, 88..8B и E8 очень часто в TOP-5 оказываются.

 

Ща глянул на 24 -- оказывается эта популярность проистекает от обращения к стековым переменным ч/з esp, можно сказать, что 24 -- это 'самый-популярный-SIB'. 04 популярен в качестве displacement, как и 10, который еще любит встречаться в позиции modregr/m.

 

2RElf

Всё именно так.

Уважаемый RElf, позволь только поправить твою опечатку :

программы будут иметь меньшую энтропию, а случайные наборы байт - бОльшую.



_BC_

Интересно ...

1) а ты для биграмм не пробовал ?

2) а компилятор можно определить по такому статистическому "профилю" ?

 

OLS

Как ни странно, N-граммы не так показательны, как обычный побайтовый частотный анализ. Из биграмм популярны комбинации 00 00 и FF FF (нули можно встретить где угодно -- в imm-операндах, в адресах, в смещениях, и тд и тп. Байт FF популярен и как опкод (call/jmp [], push [], inc/dec []), и в командах типа 'call/jmp/jcc назад' и в операндах типа [ebp-xxxx]). А популярная команда mov /r на биграммах дает большой разброс из-за разных значений байта modregr/m.



Определить компилятор таким образом теоретически можно, но наверное надежнее всё же будет определять по сигнатурам...



Еще один характерный байт -- 45h (и отчасти 85h), который участвует в обращениях к стековым переменным с помощью EBP (можно сказать, противоположность 24h).

Также в TOP-5 частенько прорывается старший байт ImageBase (стат. переменные, адреса в switch'ах и тд).



В целом, можно довольно надежно определять по частоте встречаемости байт, является ли фрагмент кодом или нет.