forked from Cactus-proj/RE-for-Beginners
-
Notifications
You must be signed in to change notification settings - Fork 0
/
main_RU.tex
137 lines (100 loc) · 9.57 KB
/
main_RU.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
% TODO png blur? too wide listings
\mysection{Информационная энтропия}
\label{entropy}
\myindex{Entropy}
\epigraph{Entropy: The quantitative measure of disorder, which in turn relates to the thermodynamic functions, temperature, and heat.}
{Dictionary of Applied Math for Engineers and Scientists}
Ради упрощения, я бы сказал, что информационная энтропия это мера, насколько хорошо можно сжать
некоторый блок данных.
Например, обычно нельзя сжать файл, который уже был сжат, так что он имеет высокую энтропию.
С другой стороны, 1MiB нулевых байт можно сжать в крохотный файл на выходе.
Действительно, в обычном русском языке, один миллион нулей можно описать просто как
``в итоговом файле 1 миллион нулевых байт''.
Сжатые файлы это обычно список инструкций для декомпрессора вроде
``выдай 1000 нулей, потом байт 0x23, потом байт 0x45, потом выдай блок длиной в 10 байт, который мы видели 500 байт назад,
итд.''
Тексты, написанные на натуральных языках, также легко могут быть сжаты, по той причине что в натуральных языках очень
много избыточности (иначе мелкая опечатка могла бы привести к непониманию, так, как любой перевернутый бит в сжатом
архиве приводит к невозможности декомпрессии),
некоторые слова используются чаще, итд.
Из обычной ежедневной речи можно выкидывать вплоть до половины слов, и всё еще можно будет что-то понять.
Код для CPU тоже может быть сжат, потому что некоторые инструкции в \ac{ISA} используются чаще других.
\myindex{x86!\Instructions!MOV}
\myindex{x86!\Instructions!PUSH}
\myindex{x86!\Instructions!CALL}
В x86 самые используемые инструкции, это \INS{MOV}/\INS{PUSH}/\INS{CALL} (\myref{correctly_disasmed_code}).
Компрессоры данных и шифры выдают результаты с очень большой энтропией.
Хорошие \ac{PRNG} также выдают данные, которые нельзя сжать
(по этому признаку можно измерять их качество).
Так что, другими словами, энтропия это мера, которая может помочь узнать содержимое неизвестного блока данных.
\input{ff/entropy/math_RU}
\subsection{Вывод}
Информационная энтропия может использоваться как простой метод для быстрого изучения неизвестных бинарных файлов.
В частности, это очень быстрый способ найти сжатые/зашифрованные фрагменты данных.
Кто-то говорит, что так же можно находить открытые/закрытые ключи \ac{RSA} (и для других несимметричных шифров)
в исполняемом коде (ключи также имеют высокую энтропию), но я не пробовал.
\subsection{Инструменты}
Удобная утилита из Linux \emph{ent} для вычисления энтропии файла\footnote{\url{http://www.fourmilab.ch/random/}}.
Неплохой онлайновый визуализатор энтропии, сделанный Aldo Cortesi,
которому я пытался подражать при помощи Mathematica: \url{http://binvis.io}.
Его статьи о визуализации энтропии тоже стоит почитать:
\url{http://corte.si/posts/visualisation/entropy/index.html},
\url{http://corte.si/posts/visualisation/malware/index.html},
\url{http://corte.si/posts/visualisation/binvis/index.html}.
\myindex{radare2}
В фреймворке radare2 есть команда \emph{\#entropy}.
Для IDA есть IDAtropy\footnote{\url{https://github.com/danigargu/IDAtropy}}.
\subsection{Кое-что о примитивном шифровании как XOR}
Интересно, что простое шифрование при помощи XOR не меняет энтропии данных.
В этой книге я показал это в примере с \emph{Norton Guide} (\myref{norton_guide}).
Обобщая: шифрования при помощи шифровании с заменой также не меняет энтропии данных
(а XOR можно рассматривать как шифрование заменой).
Причина в том, что алгоритм вычисления энтропии рассматривает данные на уровне байт.
С другой стороны, данные зашифрованные с 2-х или 4-х байтным XOR-шаблоном приведут к другому уровню энтропии.
Так или иначе, низкая энтропия это обычно верный признак слабой любительской криптографии
(которая используется в лицензионных ключах/файлах, итд).
\subsection{Еще об энтропии исполняемого кода}
Легко заметить, что наверное самый большой источник большой энтропии в исполняемом коде это
относительные смещения закодированные в опкодах.
Например, эти две последовательные инструкции будут иметь разные относительные смещения в своих опкодах,
в то время как они, на самом деле, указывают на одну и ту же ф-цию:
\begin{lstlisting}[style=customasmx86]
function proc
...
function endp
...
CALL function
...
CALL function
\end{lstlisting}
Идеальный компрессор исполняемого кода мог бы кодировать информацию так:
\emph{есть CALL в ``function'' по адресу X и такой же CALL по адресу Y} без необходимости кодировать
адрес ф-ции \emph{function} дважды.
\myindex{UPX}
Чтобы с этим разобраться, компрессоры исполняемых файлов иногда могут уменьшить энтропию здесь.
Один из примеров это UPX: \url{http://sourceforge.net/p/upx/code/ci/default/tree/doc/filter.txt}.
\subsection{\ac{PRNG}}
\myindex{GnuPG}
Когда я запускаю GnuPG для генерации закрытого (секретного) ключа, он спрашивает об энтропии \dots
\begin{lstlisting}
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.
Not enough random bytes available. Please do some other work to give
the OS a chance to collect more entropy! (Need 169 more bytes)
\end{lstlisting}
Это означает, что хороший \ac{PRNG} выдает длинные результаты с большой энтропией,
и это тоже что нужно для секретного ключа в ассиметричной криптографии.
Но \ac{CPRNG} это сложно (потому что компьютер сам по себе это очень детерменистичное устройство),
так что GnuPG просит у пользователя дополнительной случайной информации.
\subsection{Еще примеры}
Вот случай, где я делаю попытку подсчитать энтропию некоторых блоков с неизвестным содержимым: \myref{encrypted_DB1}.
\input{ff/entropy/files_RU}
\subsection{Понижение уровня энтропии}
Автор этих строк однажды видел ПО, которое хранило каждый шифрованный байт в трех байтах:
каждый имел значение {\Large $\approx \frac{byte}{3}$}, так что реконструирование шифрованного байта включало в себя
суммирование трех последовательно расположенных байт.
Выглядит абсурдно.
Но некоторые люди говорят, что это было сделано для сокрытия того самого факта, что данные имеют внутри что-то зашифрованное:
измерение энтропии такого блока покажет уровень энтропии намного ниже.