Энтропия |
[Nov. 3rd, 2010|04:42 pm] |
Задумался над тем, как бы снизить энтропию шифрованного/сжатого текста до "нормальных" значений, и где она та норма? Пробежался быстренько по всем бинарям, установленным в системе и получается вот что:
Энтропия для секции .text (CentOS 5.5 /bin/* /sbin/* /usr/bin/* /usr/sbin/*):
Average: 5.927633
Median : 5.929472
Min/Max: 5.099679 6.533445
*
*
* *
* *
** * *
** * * * * * *
* ** * ****** ***
* ** * ***** * ************ *
** ** ************************ *
* ********************************* ** *
* ************************************ * **
* **************************************** ** **
* ********************************************* **** **
** ***************************************************** **
* * ************************************************************* *
** ** ** ** *************************************************************************** ****
^ ^ ^ ^ ^ ^
5.099679 5.386432 5.673185 5.959939 6.246692 6.533445
То есть искомая норма, где-то ~5.9. Дальше. Нашел небольшую статью на эту тему ("Энтропия и ее нормализация"), в которой автор предлагает разбавлять текст нулями, положение каждого нуля псевдослучайное, до того момента пока энтропия не опустится, но почему только нулями? и сколько это "до тех пор пока"? Можно ведь и охуеть пересчитывая энтропию снова и снова, даже если инкрементально это делать. Захотел посмотреть на среднюю вероятность появления в .text каждого байта, получилось вот что:
(Максимальное значение на графике - 0.1).
И так, 00 - это действительно хороший кандидат для мусора, но так же и FF и другие байты. Основные кандидаты - 00 04 08 24 89 8b ff (для виндовых бинарей эти значения будут отличаться, хотя бы из-за 08. Почему, написано в Sys V ABI). И сколько добавить мусора? В процентах от длины текста - 0 и FF по 10%, 04 24 89 по 4%, 08 8b - 3%. То есть, как минимум нужно увеличить длину текста процентов на 40 и разбавить мусором, хоть впритык, хоть псевдо-случайно - энтропии (но не другим эвристикам основанным на статистике - похуй). Еще лучше посмотреть насколько вероятности байт в тексте отличаются от усредненных. Потом постараюсь код набросать. |
|
|
Comments: |
я тоже когда-то собирал статистику по .text для бинарников из %SYSTEM32% - нужно было вот для чего: - есть зашифрованный .exe, алгоритм шифрования известен, длина ключа 32 бита - перебираем все 2^32 ключа, расшифровываем кусок длиной ~1k (примерно), считаем статистику по распределению байт - если 00 и ff встречаются часто - запоминаем ключ как кандидат - в итоге получалось с десяток вероятных ключей, правильный видно сразу же на глаз.
ну и иногда дело упрощалось тем, что известен используемый компилятор - тогда байты в начале секции известны заранее.
такой вот брутфорс со статистическим анализом :-)
![[User Picture]](http://lj.rossia.org/userpic/191927/26445) | From: | herm1t |
Date: | November 4th, 2010 - 05:26 pm |
---|
| | | (Link) |
|
> такой вот брутфорс со статистическим анализом :-)
красиво. :-) хорошо, что авторы не догадались сжать код перед шифрованием.
именно, даже простой upx перед шифрованием всю затею сразу же загубил.
![[User Picture]](http://lj.rossia.org/userpic/191927/26445) | From: | herm1t |
Date: | November 5th, 2010 - 12:11 pm |
---|
| | | (Link) |
|
дык, странно другое - это же азы криптографии, но тем не менее разработчики упорно наступают на одни и те же грабли. вспомнилась дурацкая софтина, которую удалось сломать "на глаз" без участия, каких бы то ни было инструментов вообще. зная, что должно быть зашифровано и где, поксорил предполагаемый открытый текст со строкой и оказался прав. в другой херне, без отладчика поискал в дизасме xor, и опять оказался прав. ну, блин, написали бы хотя бы вместо a^b, (a&(~b))|((~a)^b) - уже было бы веселее.
Возможно, так еще можно было бы автоматом детектить тип процессора...
![[User Picture]](http://lj.rossia.org/userpic/191927/26445) | From: | herm1t |
Date: | November 5th, 2010 - 12:02 pm |
---|
| | | (Link) |
|
вполне. но только тип кода в бинаре, можно определить и проще. хотя наверное бывают и такие ситуации, хотя я с лету не могу представить ситуацию, где это было бы уместно. а вот если фигачит сплошной поток данных, и возникает вопрос, а что внутри? то статистика - самое оно. | |