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

О поиске коллизий для хеш-функций

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

1. Что такое коллизия и с чем её едят

Коллизия - это когда на входе хеш-функции разные тексты (строки), а на выходе - одинаковые хеш-значения.

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

Коллизии дают возможность некоторых махинаций с электронными документами. Допустим, документы контролируются по хешам. Тогда можно составить два документа с одинаковым хешем и в нужный момент сделать подмену.

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

2. Задача поиска коллизий

Данная задача предполагает найти два разных входных текста (строки), которые для заданной хеш-функции дадут одинаковый хеш. Как правило, нужна только одна коллизия, потому атака считается успешной при первой найденной коллизии.

3. Атаки по парадоксу дней рождения

Есть такая задачка: сколько человек нужно взять, чтобы вероятность найти двух с одинаковым днём рождения была не менее 50%? Если полагать, что в году 365 дней, и в разные дни рождается примерно одинаковое число народу, то правильный ответ: 23. Это может показаться несколько странным, но сомневающийся может изучить авторитетную литературу... Или решить задачу сам!

Наверное, возник вопрос - а при чём тут коллизии? Проводим аналогию: человек - своего рода вход для хеш-функции, день рождения - хеш-значение. В этом случае аналог совпадения дней рождения - коллизия.

Итак, берём какое-то множество строк S и перебираем всевозможные пары строк из этого множества. Для сокращения числа вариантов учитываем, что пары (s, t) и (t, s) одинаковые, поскольку перестановка левой и правой части не делает неравные величины равными или равные неравными. Если солидным языком - отношение коллизии симметрично. Ну и разумеется, нельзя проверять коллизию строки с самой собой, то есть брать пару вида (s, s).

Среднее число проверок получается квадратичным от |S|, то есть количества строк во множестве S (имеется (|S| - 1) + (|S| - 2) + ... + 3 + 2 + 1 проверяемых пар).

Посчитано, что для получения коллизии с вероятностью, близкой к 50%, нужно взять число строк, примерно равное корню квадратному от |S|. Это грубая оценка, но она даёт общее представление о возможностях алгоритма.

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

4. Двусторонние атаки

Берём два множества строк P и Q, причём эти множества не пересекаются, то есть нет строки, которая участвовала бы в обоих множествах. Перебираем всевозможные пары (p, q), где p из P, а q - из Q, то есть проверяем декартово произведение P x Q.

Удобство такого рода атак - просто распараллелить. Разбиваем P на непересекающиеся подмножества P(i), i = 1...n, где n - число параллельных процессов. Тогда i-ый процесс проверяет P(i) x Q. Можно разбивать Q, а не P, по такому же принципу.

Пусть h - количество возможных хешей, a=|P x Q|/h. Тогда вероятность найти коллизию для оптимальной хеш-функции будет иметь следующий график:

Под оптимальной хеш-функцией в данном случае имеем в виду максимально устойчивую к попыткам найти коллизии. Как видно по графику, даже огромные P и Q не гарантируют, что коллизия будет найдена. Тем не менее вероятность провалить атаку в конце концов становится микроскопической.

Чтобы с вероятностью 50% найти коллизию для оптимальной хеш-функции, требуется a около 0,69. Если вдуматься, это не так уж мало. Так, SHA-1 близка к оптимальной и имеет 160-битный хеш. Возведите 2 в степень 160 и итог умножьте на 0,69. Целая часть числа будет иметь более 40 цифр. Ясно, что тут не обойтись без параллельных вычислений.

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

На главную
X