Криптографические хэш-функции

hash function -применяются в криптографии в алгоритмах шифрования, а также для формирования ЭЦП

Однонаправленной Хэш-функцией называется вычислительно необратимая функция, осуществляющая преобразование массива данных произвольного размера в блок данных фиксированного размера - Хэш-код (“цифровой отпечаток”).

Это односторонняя функция, предназначенная для получения дайджеста или "цифрового отпечатка" файла, сообщения или некоторого блока данных. Часто хэш-функции называют прямыми (необратимыми) функциями с потерей данных.

Хэш-код создается функцией Н:

H (O) = h

Где O является сообщением произвольной длины и h является хэш-кодом фиксированной длины, меньшей или равной длине О.

Таким образом, хэш-код сложным образом зависит от сообщения O и является его сжатым представлением, но не позволяет восстановить исходное сообщение.

Понятие односторонней функции было введено в теоретическом исследовании о защите входа в вычислительные системы. Функция f(x) называется односторонней (one-way function), если для всех x из ее области определения легко вычислить y=f(x), но нахождение по заданному y такого x, для которого f^--1(y)=x, вычислительно неосуществимо, то есть требуется настолько огромный объем вычислений, что за них просто и не стоит браться.

Однако существование односторонних функций не доказано. В качестве приближения была предложена Гиллом Дж. целочисленная показательная функция

f(x)=a^x mod n,

где основание a и показатель степени x принадлежат интервалу (1,n-1), а умножение ведется по модулю n. Функция вычисляется достаточно эффективно по следующей схеме. Если представление числа x в двоичной форме имеет вид

x₀2^k-1 + x₁2^k-2 +...+ x_k-12¹ + x_k2⁰,

то

y = f(x) = a^x mod n = ((...(a^xk-1)²*a^xk-2)²*...*a^x1)²*a^x0 mod n

Операция, обратная к этой, известна как операция вычисления дискретного логарифма: по заданным y, a и n найти такое целое x, что a^х mod n = y. До настоящего времени не найдено достаточно эффективных алгоритмов решения этой задачи.

Все хэш-функции выполняются следующим образом. Входное значение (сообщение, файл и т.п.) рассматривается как последовательность n-битовых блоков. Входное значение обрабатывается последовательно блок за блоком, и создается m-битовое значение хэш-кода.

Одним из простейших примеров хэш-функции является поразрядный XOR каждого блока:

H_i = b_i1 ⊕ b_i2 ⊕... ⊕ b_ik

Где

H_i - i-ый бит хэш-кода, 1 ≤ i ≤ n.
k - число n-битовых блоков входа.
b_ij - i-ый бит в j-ом блоке.
⊕ - операция XOR.

В результате получается хэш-код длины n, известный как продольный избыточный контроль. Этот метод является эффективным при случайных сбоях для проверки целостности данных.

Часто при использовании подобного продольного избыточного контроля для каждого блока выполняется однобитовый циклический сдвиг после вычисления хэш-кода. Это можно описать следующим образом.

· Установить n-битовый хэш-код в ноль.

· Для каждого n-битового блока данных выполнить следующие операции:

o сдвинуть циклически текущий хэш-код влево на один бит;

o выполнить операцию XOR для очередного блока и хэш-кода.

Это придает эффект "случайности" входным данным и уничтожает любую регулярность, которая присутствует во входных значениях.

Рассмотрим требования, которым должна соответствовать хэш-функция для того, чтобы она могла использоваться в качестве аутентификатора сообщения.

1. Хэш-функция Н должна применяться к блоку данных любой длины.

2. Хэш-функция Н создает выход фиксированной длины.

3. Н (O) относительно легко (за полиномиальное время) вычисляется для любого значения O.

4. Для любого данного значения хэш-кода h вычислительно невозможно найти O такое, что Н (O) = h – свойство необратимости.

5. Для любого данного х вычислительно невозможно найти y ≠ x, что H (y) = H (x) – защита от подделки.

6. Вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x) – стойкость к коллизиям.

Первые три свойства требуют, чтобы хэш-функция создавала хэш-код для любого сообщения. Четвертое свойство определяет требование односторонности хэш-функции: легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по данному хэш-коду. Это свойство важно, если аутентификация с использованием хэш-функции включает секретное значение. Само секретное значение может не посылаться, тем не менее, если хэш-функция не является односторонней, противник может легко раскрыть секретное значение следующим образом. Пятое свойство гарантирует, что невозможно найти другое сообщение, чье значение хэш-функции совпадало бы со значением хэш-функции данного сообщения. Это предотвращает подделку аутентификатора при использовании зашифрованного хэш-кода. В данном случае противник может читать сообщение и, следовательно, создать его хэш-код. Но так как противник не владеет секретным ключом, он не имеет возможности изменить сообщение так, чтобы получатель этого не обнаружил. Если данное свойство не выполняется, атакующий имеет возможность выполнить следующую последовательность действий: перехватить сообщение и его зашифрованный хэш-код, вычислить хэш-код сообщения, создать альтернативное сообщение с тем же самым хэш-кодом, заменить исходное сообщение на поддельное. Поскольку хэш-коды этих сообщений совпадают, получатель не обнаружит подмены.

Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Шестое свойство защищает против класса атак, известных как атака "день рождения". Свойство сопротивляемости коллизиям означает, что хотя коллизии и существуют, их невозможно обнаружить. Сильная функция хэширования является идеальным черным ящиком.

Всякая хорошая хэш-функция действует так, что даже единственное изменение байта или бита в потоке данных на входе приводит к появлению на выходе хэш-значения совершенно иного вида. Иногда даже требуют, чтобы при изменении единственного бита на входе менялось не менее половины битов на выходе - это условие называют лавинным свойством (avalanche property).

При атаке на h-функцию основное внимание уделяется размеру выходных данных. Одной из универсальных является атака, в основе которой лежит парадокс задачи о днях рождения.

Так называемый "парадокс дня рождения" состоит в следующем. Предположим, количество выходных значений хэш-функции Н равно n. Каким должно быть число k, чтобы для конкретного значения X и значений Y₁, …, Y_k c вероятностью 0,5 хотя бы для одного Y_i выполнялось равенство H(X)=H(Y)?

Если хэш-код имеет длину m бит, т.е. принимает 2^m значений, то k = 2^m

Каким должно быть число k, чтобы для случайной пары (X,Y) c вероятностью 0,5 выполнялось равенство H(X)=H(Y)?

k = Ö2^m = 2^m/2

Парадокс дня рождения является стандартной статистической задачей (основанной на том факте, что в группе из 23 и более человек вероятность совпадения дня рождения хотя бы у двоих из них превышает 50%, а в группе из 57 человек достигает уже 99%):

сколько человек должно собраться в одном помещении, чтобы с вероятностью 0,5 хотя бы у кого-нибудь из них был общий с вами день рождения? Ответ – 183. А сколько должно собраться людей, чтобы с вероятностью 0,5 хотя бы у двоих из них (случайной пары) был бы общий день рождения? Ответ удивителен – всего 23. 23 человека образуют 253 различные пары à ((23-1)*(23))/ 2.

Найти кого-нибудь с тем же днем рождения – это аналогия с попыткой атаки на требование 5, в этом случае пространство значений составит 2^m. Найти случайную пару с одинаковым h – это атака на требование 6 à 2^m/2.

Вернемся к рассмотрению свойств хэш-функций. Предположим, что используется 64-битовый хэш-код. Можно считать, что это вполне достаточная и, следовательно, безопасная длина для хэш-кода. Например, если зашифрованный хэш-код h передается с соответствующим незашифрованным сообщением O, то противнику необходимо будет найти O' такое, что

Н (O') = Н (O)

для того, чтобы подменить сообщение и обмануть получателя. В среднем противник должен перебрать 2⁶⁴ сообщений для того, чтобы найти такое, у которого хэш-код равен перехваченному сообщению.

Тем не менее, возможны различного рода атаки, основанные на "парадоксе дня рождения". Возможна следующая стратегия:

1. Противник создает 2^m/2 вариантов сообщения, каждое из которых имеет некоторый определенный смысл. Противник подготавливает такое же количество сообщений, каждое из которых является поддельным и предназначено для замены настоящего сообщения.

2. Два набора сообщений сравниваются в поисках пары сообщений, имеющих одинаковый хэш-код. Вероятность успеха в соответствии с "парадоксом дня рождения" больше, чем 0,5. Если соответствующая пара не найдена, то создаются дополнительные исходные и поддельные сообщения до тех пор, пока не будет найдена пара.

3. Атакующий предлагает отправителю исходный вариант сообщения для подписи. Эта подпись может быть затем присоединена к поддельному варианту для передачи получателю. Так как оба варианта имеют один и тот же хэш-код, будет создана одинаковая подпись. Противник будет уверен в успехе, даже не зная ключа шифрования.

Таким образом, если используется 64-битовый хэш-код, то необходимая сложность вычислений составляет порядка 2³².

Очевидно, что длина хэш-кода должна быть достаточно большой. Длина, равная 64 битам, в настоящее время не считается безопасной. Предпочтительнее, чтобы длина составляла порядка 128 битНапример, количество арифметических операций, необходимых для того, чтобы найти другой блок данных, имеющий такой же хэш, как и исходный, для хэш-функции MD5, составляет приблизительно 2⁶⁴; для MD5 предполагаемое количество операций, необходимых для вычисления исходного сообщения по известному результату хэширования, равно 2¹²⁸

Практически все современные функции хэширования являются итеративными. Итеративные хэш-функции разбивают входное значение на последовательность блоков фиксированного размера b1, b2……, bk, используя некоторое правило дополнения для заполнения последнего блока. Затем блоки сообщения обрабатываются по порядкус помощью функции сжатия h’ и промежуточных состояний фиксированного размера. Этот процесс начинается с фиксированного значения H0 и определяется как Hi=h’(Hi-1, bi). Последнее значение Hk и будет результатом функции хэширования.

Итеративный алгоритм хэширования имеет существенные практические преимущества. Во-первых, его намного легче определить и реализовать по сравнению с функциями, которые напрямую работают со значениями переменной длины. Во-вторых итеративная структура позволяет начинать вычисление хэш-кода сообщения, как только появится хотя бы часть сообщения. Благодаря этому в приложениях, работающих с поточными данными, хэшировать сообщения можно прямо “на лету”, не сохраняя данные в буфере.

Примеры хэш-функций:

MD5 (128 битовое значение), MD4 (Ron Rivest), SHA (Secure Hash Algorithm)

ГОСТ Р34.11-94/256, ГОСТ Р34.10-94

Дата добавления: 2015-07-24