diff options
| -rw-r--r-- | cryptography/cryptography.pdf | bin | 4228765 -> 4240478 bytes | |||
| -rw-r--r-- | cryptography/cryptography.tex | 1 | ||||
| -rw-r--r-- | cryptography/lectures/lecture25.tex | 194 |
3 files changed, 195 insertions, 0 deletions
diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf Binary files differindex 4a43143..99b17fa 100644 --- a/cryptography/cryptography.pdf +++ b/cryptography/cryptography.pdf diff --git a/cryptography/cryptography.tex b/cryptography/cryptography.tex index ec4c0ba..a244ed7 100644 --- a/cryptography/cryptography.tex +++ b/cryptography/cryptography.tex @@ -42,5 +42,6 @@ \input{lectures/lecture22.tex} \input{lectures/lecture23.tex} \input{lectures/lecture24.tex} +\input{lectures/lecture25.tex} \end{document} diff --git a/cryptography/lectures/lecture25.tex b/cryptography/lectures/lecture25.tex new file mode 100644 index 0000000..c8f6f05 --- /dev/null +++ b/cryptography/lectures/lecture25.tex @@ -0,0 +1,194 @@ +% Лекция 25 (14.04.23) + +\subsection{Анализ хэш-функций} + +\paragraph{Использование парадокса <<дней рождений>>.} + +Существует два способа вскрытия однонаправленных хэш-функций грубой силой: +\begin{enumerate} + \item + Дано значение хэш-функции сообщения $H(M)$, злоумышленник хочет уметь + создавать другой документ $M'$ такой, что $H(M') = H(M)$; + \item + Злоумышленник хочет найти два случайных сообщения $M$ и $M'$ такие, что + $H(M) = H(M')$. Такой способ называется <<столкновением>> и является более + простым, чем предыдущий. + +\end{enumerate} + +Парадокс дней рождений является статистической проблемой. Сколько человек +должно собраться в одной комнате, чтобы с вероятностью $\frac{1}{2}$ хотя бы у +кого-нибудь из них был бы общий с Вами день рождения? Ответ --- 183. + +Сколько людей должно собраться, чтобы с вероятностью $\frac{1}{2}$ хотя бы у +двоих из них был бы общий день рождения? Ответ --- 23. + +23 человека, находящихся в одной комнате, образуют 253 различных пар. + +Найти кого-нибудь с тем же днём рождения --- аналогия с первым способом +вскрытия, найти двух человек с произвольным одинаковым днём рождения --- +аналогия со вторым способом, поэтому его также называют <<вскрытие в день +рождения>>. + +Предположим, что однонаправленная хэш-функция с длиной хэш-кода $n$ бит +безопасна, и лучшим способом её вскрытия является вскрытие грубой силой. + +Поиск сообщения, хэш-значение которого совпадает с заданным, в среднем +потребовал бы хэширования $2^n$ случайных сообщений. + +А для обнаружения двух сообщения с одинаковым хэш-значением потребуется только +$2^\frac{n}{2}$ случайных сообщений. + +ЭВМ, которая хэширует 1 миллион сообщения в секунду, потребовалось бы 600000 +лет, чтобы найти второе сообщение с тем же 64-битовым хэш-значений. Тот же +компьютер сможет найти пару сообщений с общим хэш-значением примерно за 1 час. + +Это означает, что если есть опасность вскрытия в день рождения необходимо +выбирать длину хэш-значения в 2 раза длиннее, чем потребовалось бы в противном +случае. + +Например, если необходимо уменьшить вероятность взлома системы до 1 шанса из +$2^{80}$, надо использовать 160-битовую однонаправленную хэш-функцию. + + +\paragraph{Атака <<встреча посередине>>.} + +Данная атака направлена на вычисление прообраза для некоторого хэш-значения. + +Атака <<встреча посередине>> считается одним из вариантов атаки, использующей +парадокс <<дней рождения>>, хотя она и используется не для поиска коллизий. + +Атака применима к алгоритмам хэширования, раздельно обрабатывающим различные +фрагменты хэшируемых сообщения, при этом возможно инвертирование данной +обработки. + +Предположим, алгоритм хэширования $\fn{hash}()$ можно представить как +совокупность алгоритма $\fn{hash1}()$, обрабатывающего первую половину сообщения, +и алгоритма $\fn{hash2}()$, обрабатывающего вторую половину (см. пример на +рисунке). + +% TODO: рис 1 + +Цель атакующего --- получение поддельного сообщения, хэш которого соответствует +заданному значению $H$ (предположим, некий документ с таким хэшем подписан +субъектом атаки). + +В атаке, использующей парадокс <<дней рождения>>, злоумышленник генерирует +множество вариантов корректного и поддельного сообщений, после чего выполняет +поиск коллизии. + +Здесь же злоумышленник генерирует множество вариантов первой половины +поддельного сообщения и множество вариантов второй половины. + +Каждый из вариантов первой половины обрабатывается алгоритмом $\fn{hash1}()$: +\begin{equation*} + T_x = \fn{hash1}(M_{1_x}, IV), +\end{equation*} +где $M_{1_x}$ --- один из вариантов первой половины сообщения; $T_x$ --- +промежуточное значение. + +Каждый из вариантов второй половины сообщения обрабатывается алгоритмом, +обратным алгоритму $\fn{hash2}()$: +\begin{equation*} + T_y = \fn{hash2}^{-1}(M_{2_y}, H), +\end{equation*} +где $M_{2_y}$ --- один из вариантов второй половины сообщения. + +Атакующий выполняет поиск совпадений значений $T$; при нахождении совпадения +неких $T_i = T_j$ можно считать, что соответствующие им половины сообщений +$M_i$ и $M_j$ формируют то самое требуемое злоумышленнику поддельное сообщение. + +Таким образом, в процессе этой атаки сравниваются на совпадение не хэш-значения, +а промежуточные варианты. + +Атака существенно более эффективна, чем описанный поиск коллизий с помощью +парадокса <<дней рождения>>. + +Противодействие подобным атакам состоит в использовании в алгоритмах хэширования +неинвертируемых преобразований. + + +\paragraph{Специфические атаки на хэш-функции, построенные на базе блочных +шифров.} + +Некоторые слабости блочных шифров не являются критичными в тех случаях, когда +шифр используется для защиты конфиденциальности; однако, они могут привести к +успешным атакам в тех случаях, когда блочный шифр используется в качестве основы +для хэш-функции. + +В качестве примера таких слабостей можно привести свойство комплементарности +ключей алгоритма шифрования DES (или свойство дополнительности шифра: $y = +E_k(x) \implies \overline{y} = E_\overline{k}(\overline(x))$, слабые ключи и +неподвижные точки (имеются в виду неподвижные точки в алгоритме шифрования, +которые определяются на определённом ключе эквивалентен самому незашифрованному +сообщению). + +Эти слабости могут привести к существенному упрощению поиска коллизий (который +становится тривиальным при использовании свойства комплементарности ключей) или +к использованию в различных целях манипуляций на уровне блоков и неподвижных +точек. + +Не менее критичным для использования блочных шифров в качестве основы для +хэш-функций являются следующие проблемы: +\begin{itemize} + \item наличие эквивалентных ключей; + \item возможность атаки на связанных ключах. +\end{itemize} + +Таким образом, использование алгоритма блочного шифрования для построения +хэш-функции является допустимым только в том случае, если алгоритм шифрования +обладает безупречной с точки зрения криптостойкости процедурой ключа. + + +\subsection{Современные криптографические хэш-функции и стандарты} + +\paragraph{MD5.} + +Хэш-функция MD5 была разработана Р. Ривестом в 1991 году как усиленный вариант +хэш-функции MD4. Необходимость замены была вызвана тем, что для хэш-функции +MD4 сложность вычисления коллизий оказалась невысокой --- около 1 минуты на +персональном компьютере. + +Длина аргумента хэш-функции может быть произвольной, длина значения --- 128 бит +(отсюда следует, что сложность нахождения коллизии не может превышать $2^{64}$ +операций вычисления хэш-функции). + +В ходе вычисления используются следующие функции 32-разрядных аргументов $u$, +$v$, $w$: +\begin{align*} + f_1(u, v, w) &= uv \lor \overline{u}w; \\ + f_2(u, v, w) &= uw \lor v\overline{w}; \\ + f_3(u, v, w) &= u \oplus v \oplus w; \\ + f_4(u, v, w) &= v \oplus (u \lor \overline{w}), +\end{align*} +% TODO: дописать?? +% где символ $\lor$ --- поразрядная дизъюнкция векторов, символ поразрядной +% коньюнкции + +С учётом равенств $\overline{a} = a \oplus 1$ и $a \lor b = a \oplus b \oplus +ab$, эти функции можно записать в терминах кольца $G_n$: +\begin{align*} + f_1(u, v, w) &= w \oplus u (v \oplus w); \\ + f_2(u, v, w) &= v \oplus w (u \oplus v); \\ + f_3(u, v, w) &= u \oplus v \oplus w; \\ + f_4(u, v, w) &= 1 \oplus v \oplus w (1 \oplus u). +\end{align*} + +Каждая из этих булевых функций является сбалансированной. Булевы функции +$f_1$, $f_2$, $f_4$ имеют нелинейность 2, булева функция $f_3$ аффинная (имеет +нелинейность 0). + +На этапе предвычислений определяются следующие параметры: +\begin{enumerate} + \item + 64 константы по 32 бита каждая: $y[j] = |\sin(j + 1)|$ для $o \leq j \leq + 63$; + \item + Три перестановки $z[\cdot]$ на множестве $(0, 1, \dots, 15)$ как + арифметические прогрессии в $\Z_{16}: z[16 \dots 31]$ --- прогрессия с + первым членом 1 и разностью 5, $z[32 \dots 47]$ --- прогрессия с первым + членом 5 и разностью 3, $z[48 \dots 63]$ --- прогрессия с первым членом 0 и + разностью 7; +\end{enumerate} + +% TODO: дописать |