forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
hash-functions.tex
67 lines (46 loc) · 8.69 KB
/
hash-functions.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
\chapter{Криптографические хэш-функции}\label{chapter-hash-functions}
\selectlanguage{russian}
Хэш-функции возникли как один из вариантов решения задачи <<поиска по словарю>>. Задача состояла в поиске в памяти компьютера (оперативной или постоянной) информации по известному ключу. Возможным способом решения было хранение, например, всего массива ключей (и указателей на содержимое) в отсортированном в некотором порядке списке или в виде бинарного дерева. Однако наиболее производительным с точки зрения времени доступа (при этом обладая допустимой производительностью по времени модификации) стал метод хранения в виде хэш-таблиц. Этот метод ведёт своё происхождение из стен компании IBM (как и многое другое в программировании).
Метод хэш-таблиц подробно разобран в любой современной литературе по программированию~\cite{Knuth:2001:3}. Напомним лишь, что его идея состоит в разделении множества ключей по корзинам (\langen{bins}) в зависимости от значения некоторой функции, вычисляемой по значению ключа. Причём функция подбирается таким образом, чтобы в разных корзинах оказалось одинаковое число (в идеале -- не более одного) ключей. При этом сама функция должна быть быстро вычисляемой, а её значение должно легко конвертироваться в натуральное число, которое не превышает число корзин.
\emph{Хэш-функцией} (\langen{hash function}) называется отображение, переводящее аргумент произвольной длины в значение фиксированной длины.
\emph{Коллизией} хэш-функции называется пара значений аргумента, дающая одинаковый выход хэш-функции. Коллизии есть у любых хэш-функций, если количество различных значений аргумента превышает возможное количество значений результата функции (принцип Дирихле). А если не превышает, то и нет смысла использовать хэш-функцию.
\example
Приведём пример метода построения хэш-функции, называемого методом Меркла~---~Дамгарда\index{структура!Меркла~---~Дамгарда}~\cite{Merkle:1979, Merkle:1990, Damgard:1990}.
Пусть имеется файл $X$ в виде двоичной последовательности некоторой длины. Разделяем $X$ на несколько отрезков фиксированной длины, например по 256 символов: $m_{1} ~\|~ m_{2} ~\|~ m_{3} ~\|~ \ldots ~\|~ m_{t}$. Если длина файла $X$ не является кратной 256 битам, то последний отрезок дополняем нулевыми символами и обозначаем $m'_{t}$.
Обозначим за $t$ новую длину последовательности. Считаем каждый отрезок $m_i, ~ i = 1, 2, \dots, t$ двоичным представлением целого числа.
Для построения хэш-функции используем рекуррентный способ вычисления. Предварительно введём вспомогательную функцию $\chi(m, H)$, называемую функцией компрессии или сжимающей функцией. Задаём начальное значение $H_{0} = 0^{256} \equiv \underbrace{000 \ldots 0}_{256} $. Далее вычисляем:
\[ \begin{array}{l}
H_1 = \chi( m_1, H_0), \\
H_2 = \chi( m_2, H_1), \\
\dots,\\
H_t = \chi( m'_t, H_{t-1}). \\
\end{array} \]
Считаем $H_{t} = h(X)$ хэш-функцией.
\exampleend
В программировании к свойствам хорошей хэш-функции относят:
\begin{itemize}
\item быструю скорость работы;
\item минимальное число коллизий.
\end{itemize}
Можно назвать и другие свойства, которые были бы полезны для хэш-функции в программировании. К ним можно отнести, например, отсутствие необходимости в дополнительной памяти (неиспользование <<кучи>>), простоту реализации, стабильность работы алгоритма (возврат одного и того же результата после перезапуска программы), соответствие результатов работы хэш-функции результатам работы других функций, например, функций сравнения (см. например, описания функций \texttt{hashcode()}, \texttt{equals()} и \texttt{compare()} в языке программирования Java).
\emph{Однонаправленной функцией}\index{функция!однонаправленная} $f(x)$ называется функция, обладающая следующими свойствами:
\begin{itemize}
\item вычисление значения функции $f(x)$ для всех значений аргумента $x$ является \emph{вычислительно лёгкой} задачей;
\item нахождение аргумента $x$, соответствующего значению функции $f(x)$, является \emph{вычислительно трудной} задачей.
\end{itemize}
Свойство однонаправленности, в частности, означает, что если в аргументе $x$ меняется хотя бы один символ, то для любого $x$ значение функции $H(x)$ меняется непредсказуемо.
\emph{Криптографически стойкой хэш-функцией} $H(x)$ называется хэш-функция, имеющая следующие свойства:
\begin{itemize}
\item однонаправленность: \emph{вычислительно невозможно} по значению функции найти прообраз;
\item \emph{слабая устойчивость к коллизиям}\index{устойчивость к коллизиям} (слабо бесконфликтная функция): для заданного аргумента $x$ \emph{вычислительно невозможно} найти другой аргумент $y \neq x: ~ H(x) = H(y)$;
\item \emph{сильная устойчивость к коллизиям} (сильно бесконфликтная функция): \emph{вычислительно невозможно} найти пару разных аргументов $x \neq y: ~ H(x) = H(y)$.
\end{itemize}
Из требования на устойчивость к коллизиям, в частности, следует свойство (близости к) равномерности распределения хэш-значений.
При произвольной длине последовательности $X$ длина хэш-функции $H(X)$ в российском стандарте ГОСТ Р 34.11-94 равна 256 символам, в американском стандарте SHA несколько различных значений длин: 160, 192, 256, 512 символов.
\input{GOST_R_34.11-94.tex}
\input{GOST_R_34.11-2012.tex}
\input{MAC}
\section{Коллизии в хэш-функциях}
\input{collisions_probability}
\input{hash-functions_combinations}
\input{blockchain}