herm1t LIVE!ng room - Энтропия [entries|archive|friends|userinfo]
herm1t

[ website | twilight corner in the herm1t's cave ]
[ userinfo | ljr userinfo ]
[ archive | journal archive ]

Энтропия [Nov. 3rd, 2010|04:42 pm]
Previous Entry Add to Memories Tell A Friend Next Entry
[Tags|, ]

Задумался над тем, как бы снизить энтропию шифрованного/сжатого текста до "нормальных" значений, и где она та норма? Пробежался быстренько по всем бинарям, установленным в системе и получается вот что: Энтропия для секции .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 каждого байта, получилось вот что:
Вероятность появления байта в секции .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 и разбавить мусором, хоть впритык, хоть псевдо-случайно - энтропии (но не другим эвристикам основанным на статистике - похуй). Еще лучше посмотреть насколько вероятности байт в тексте отличаются от усредненных. Потом постараюсь код набросать.
LinkLeave a comment

Comments:
From:[info]moonofnovember.livejournal.com
Date:November 4th, 2010 - 11:01 am
(Link)
я тоже когда-то собирал статистику по .text для бинарников из %SYSTEM32% - нужно было вот для чего:
- есть зашифрованный .exe, алгоритм шифрования известен, длина ключа 32 бита
- перебираем все 2^32 ключа, расшифровываем кусок длиной ~1k (примерно), считаем статистику по распределению байт
- если 00 и ff встречаются часто - запоминаем ключ как кандидат
- в итоге получалось с десяток вероятных ключей, правильный видно сразу же на глаз.

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

такой вот брутфорс со статистическим анализом :-)
[User Picture]
From:[info]herm1t
Date:November 4th, 2010 - 05:26 pm
(Link)
> такой вот брутфорс со статистическим анализом :-)

красиво. :-) хорошо, что авторы не догадались сжать код перед шифрованием.
From:[info]moonofnovember.livejournal.com
Date:November 5th, 2010 - 09:51 am
(Link)
именно, даже простой upx перед шифрованием всю затею сразу же загубил.
[User Picture]
From:[info]herm1t
Date:November 5th, 2010 - 12:11 pm
(Link)
дык, странно другое - это же азы криптографии, но тем не менее разработчики упорно наступают на одни и те же грабли. вспомнилась дурацкая софтина, которую удалось сломать "на глаз" без участия, каких бы то ни было инструментов вообще. зная, что должно быть зашифровано и где, поксорил предполагаемый открытый текст со строкой и оказался прав. в другой херне, без отладчика поискал в дизасме xor, и опять оказался прав. ну, блин, написали бы хотя бы вместо a^b, (a&(~b))|((~a)^b) - уже было бы веселее.
[User Picture]
From:[info]climber
Date:November 5th, 2010 - 05:19 am
(Link)
Возможно, так еще можно было бы автоматом детектить тип процессора...
[User Picture]
From:[info]herm1t
Date:November 5th, 2010 - 12:02 pm
(Link)
вполне. но только тип кода в бинаре, можно определить и проще. хотя наверное бывают и такие ситуации, хотя я с лету не могу представить ситуацию, где это было бы уместно. а вот если фигачит сплошной поток данных, и возникает вопрос, а что внутри? то статистика - самое оно.