Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Способы повышения стойкости хеш-функций к коллизиям

Информационная безопасность На главную Хеш-функции Шифры Оставить отзыв

Всё прочее о хеш-функциях смотрите на этом сайте ЗДЕСЬ

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

1. Длинный хеш

Как было показано здесь, вероятность найти коллизию при атаке перебором на качественную хеш-функцию зависит не только от того, сколько тыков мы делаем, но и сколько есть возможных хеш-значений.
Пусть a - отношение количества тыков (по-научному - проверяемых пар строк), p(a) - вероятность найти коллизию перебором для идеально спроектированной хеш-функции за заданное количество тыков. На рисунке ниже коричневым цветом изображён график для этой вероятности.

А теперь у нас другая хеш-функция, тоже идеально спроектированная, но длина хеша больше на 1 бит, то есть возможных хешей вдвое больше. График вероятности найти для неё коллизию показан зелёным. Разница вполне заметная.

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

По этому нехитрому принципу выясняется, что SHA-1 - хорошо спроектированная. Стало быть, для неё можно получить примерно такую кривую, как две показанные. Это будет не точной оценкой стойкости, но неплохим приближением.

2. Улучшение распределения

Распределение показывает, какова вероятность того, что выбранная наугад строка при её хешировании даст заданный хеш. Пример распределения: 30% строк хешируются в 00, 24% - в 01, 26% - в 10, 20% - в 11. Если угодно, вот даже диаграмма:

Для простых хеш-функций распределение можно оценить по теории вероятностей. Например, для хеш-функции, берущей остаток от деления суммы кодов символов строки на какую-то небольшую степень двойки (например, (c[1] +...+c[n]) mod 32), распределение равномерное.

В криптографии простые хеш-функции не применяются, потому нередко нужны экспериментальные ходы. Необязательная прямая проверка большого числа строк (использование стремления частоты к вероятности). Так, если выяснено, что стойкость хеш-функции к коллизиям близка к оптимальной (см. ГРАФИК ВЫШЕ С ДВУМЯ КРИВЫМИ), можно заключить, что распределение близко к равномерному.
Распределение хешей должно быть как можно более близким к равномерному. Это означает, что при бесконечном количестве хеширований различные хеши будут выпадать с близкой частотой.

3. Рост времени вычисления хеш-значения

Тут всё очевидно - чем дольше вычисляется хеш-значение, тем больше времени займёт проверка заданного количества пар строк при прочих равных параметрах функций. Пояснение к тексту курсивом: MD-5 более, чем в 2 раза медленнее SHA-1, но имеет в 4 с лишним млрд раз меньше возможных хешей (128-битные хеши у MD-5 против 160-битных хешей SHA-1). Ну и что же, по-вашему, лучше?

4. Сложность операций

Хеш-функция должна содержать довольно сложные операции, чтобы трудно было аналитически найти коллизию.

Допустим, легко найти коллизию, если хеш-функция просто ищет остаток от деления на какую-то степень двойки, где делимое - сумма или произведение кодов символов входной строки. В этом случае берём любую строку с длиной не менее 2 символов. Вторую строку получаем, переставив местами какие-либо два символа первой. Вот вам и коллизия.

А теперь задание на самостоятельную проработку: подберите АНАЛИТИЧЕСКИ две строки, образующие коллизию для SHA-512.

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

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

copyright © Исканцев Н.В., 2012

На главную
X