Свойства криптографических хэш-функций, "Подгон" хэш-значения и атака Нострадамуса - Применение хэш-функций для схемы разделения секрета, основанной на латинском квадрате

Ниже представлены общие свойства, которыми должна обладать хэш-функция:

    1. При подаче в хэш-функцию строки произвольной длины, на выходе должна быть строка фиксированной длины. 2. При подаче сообщения в хэш-функцию, значение h(x) должно вычисляться достаточно быстро. 3. Если дано хэш-значение y, то должно быть невозможно найти такое x, что h(x)=y. То есть h - стойкая к восстановлению прообраза функция 4. Если дана пара входного и выходного значений (x, y) для хэш-функции, то должно быть невозможно найти такой прообраз xў, что xў № x, но h(x) = h(xў) = y. Это свойство называется стойкостью к восстановлению второго прообраза. 5. Если даны две разные входные строки x, xў и (x № xў), то должен быть невозможен случай, что h(x) = h(xў). Это свойство стойкости к коллизиям.
"Подгон" хэш-значения и атака Нострадамуса

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

Первым шагом в реализации атаки является построение большого числа хэш-значений первого уровня: h11, h12, ..., h1w. Вторым шагом - построение промежуточных хэш-значений второго уровня: h21, h22, ..., h2w/2 таким образом, что соблюдаются следующие условия:

    - существует сообщение m11 Такое, что C(h11, m11) = h21 - существует сообщение m12 Такое, что C(h12, m12) = h21 - существует сообщение m13 такое, что C(h13, m13) = h22 - существует сообщение m14 такое, что C(h14, m14) = h22

Повторяя этот процесс, блоки сообщений оказываются связаны так, что каждое хэш-значение первого уровня может достигнуть конечное значение h (рисунок 1). Такая структура называется деревом промежуточных хэш-значений.

дерево промежуточных хэш-значений

Рисунок 1. Дерево промежуточных хэш-значений

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

M = (Префикс || M* || Суффикс),

Где Префикс - то, что было заявлено нами как известное;

М* - блок сообщений, который связывает Префикс с любым из хэш-значений первого уровня;

Суффикс - оставшиеся блоки сообщений, которые связывают М* с конечным хэш-значением.

Похожие статьи




Свойства криптографических хэш-функций, "Подгон" хэш-значения и атака Нострадамуса - Применение хэш-функций для схемы разделения секрета, основанной на латинском квадрате

Предыдущая | Следующая