Ответ 1
На самом деле коллизии проще, чем то, что вы перечисляете как на MD5, так и на SHA-1. Столкновения MD5 можно найти во времени, эквивалентном операции 2 26.5 (где одна "операция" - это вычисление MD5 по короткому сообщению). См. эту страницу для некоторых деталей и реализации атаки (я написал этот код: он обнаруживает столкновение в среднем 14 секунд на 2.4 ГГц Core2 x86 в режиме 64 бит).
Аналогично, наиболее известная атака на SHA-1 выполняется примерно в 2 61 а не 2 69. Он по-прежнему теоретический (фактического столкновения еще не было создано), но оно находится в пределах возможного.
Что касается последствий для безопасности: хеш-функции обычно называются тремя свойствами:
- Нет прообраза: если задано y, не представляется возможным найти x так, что h (x) = y.
- Нет второго прообраза: если задано x 1, не представляется возможным найти x 2 (отличное от x 1) такое, что h (x 1) = h (x 2).
- Никакого столкновения: не должно быть возможным найти x 1 и x 2 (отличные друг от друга) такие, что h (x 1) = h (x 2).
Для хэш-функции с n-разрядным выходом существуют общие атаки (которые работают независимо от деталей хеш-функции) в двух операциях n для двух первых свойств, а 2 n/2 для третьего. Если для данной хэш-функции найдена атака, которая, используя специальные сведения о функционировании хэш-функции, находит прообраз, второй прообраз или столкновение быстрее, чем соответствующая общая атака, тогда хеш-функция называется быть "сломан".
Однако не все использование хэш-функций зависит от всех трех свойств. Например, цифровые подписи начинаются с хэширования данных, которые должны быть подписаны, а затем хэш-значение используется в остальной части алгоритма. Это зависит от сопротивления прообразам и вторых прообразов, но цифровые подписи сами по себе не подвержены столкновениям. Коллизии могут быть проблемой в некоторых сценариях подписи, где злоумышленник выбирает данные, которые должны быть подписаны жертвой (в основном, злоумышленник вычисляет столкновение, имеет одно сообщение, подписанное жертвой, и подпись становится действительной для другое сообщение). Это может быть предотвращено путем добавления некоторых случайных байтов к подписанному сообщению перед вычислением подписи (атака и решение, которое демонстрируется в контексте сертификатов X.509).
Безопасность HMAC зависит от другого свойства, которое должна выполнять хеш-функция; а именно, что "функция сжатия" (элементарный кирпич, на котором построена функция хэша) действует как псевдослучайная функция (PRF). Подробности о том, что PRF является довольно техническим, но, грубо говоря, PRF должен быть неотличим от случайного Oracle. Случайный оракул моделируется как черный ящик, в котором содержится гном, некоторые кости и большая книга. На некоторых входных данных gnome выбирает случайный выход (с костями) и записывает в книгу входное сообщение и вывод, который был выбран случайным образом. Гном использует книгу, чтобы проверить, видел ли он то же самое входное сообщение: если это так, то gnome возвращает тот же вывод, что и ранее. По построению вы ничего не знаете о выходе случайного оракула по данному сообщению, пока не попробуете его.
Случайная модель оракула позволяет количественно определять доказательства безопасности HMAC в вызовах PRF. В принципе, доказательство гласит, что HMAC не может быть разбит, не называя PRF огромное количество раз, а "огромным" я имею в виду вычислительно неосуществимый.
К сожалению, у нас нет случайных оракулов, поэтому на практике мы должны использовать хэш-функции. Нет никаких доказательств существования хеш-функций с свойством PRF; прямо сейчас у нас есть только кандидаты, т.е. функции, для которых мы пока не можем доказать, что их функции сжатия не являются PRF.
Если функция сжатия является PRF, хеш-функция автоматически устойчива к столкновениям. Эта часть магии PRF. Поэтому, если мы можем найти столкновений для хэш-функции, то мы знаем, что внутренняя функция сжатия не является PRF. Это не превращает столкновения в атаку на HMAC. Возможность генерировать коллизии по желанию не помогает в нарушении HMAC. Однако эти столкновения показывают, что доказательство безопасности, связанное с HMAC, не применяется. Гарантия недействительна. Это то же самое, что и переносной компьютер: открытие корпуса не обязательно разбивает машину, но потом вы сами по себе.
В статье Kim-Biryukov-Preneel-Hong представлены некоторые атаки на HMAC, в частности, подделка на HMAC-MD4. Атака использует недостатки MD4 (ее "недостатки" ), которые делают ее не-PRF. Варианты одинаковых недостатков были использованы для создания коллизий на MD4 (MD4 полностью разрушен, а некоторые атаки создают коллизии быстрее, чем вычисление самой хеш-функции!). Таким образом, столкновения не подразумевают атаку HMAC, но обе атаки питаются одним и тем же источником. Обратите внимание, однако, что атака подделки стоила 2 58 что довольно велико (фактическая подделка не производилась, результат по-прежнему теоретический), но существенно ниже, чем ожидаемый уровень сопротивления от HMAC (с надежная хеш-функция с n-разрядным выходом, HMAC должен выдерживать до 2 n коэффициент работы, n = 128 для MD4).
Итак, хотя столкновения сами по себе не подразумевают слабые стороны HMAC, это плохая новость. На практике столкновение является проблемой для очень немногих установок. Но зная, влияет ли столкновение на определенное использование хеш-функций, достаточно сложно, что довольно неразумно продолжать использовать хеш-функцию, для которой были продемонстрированы столкновения.
Для SHA-1 атака все еще теоретическая, и SHA-1 широко используется. Ситуация была описана следующим образом: "Тревога включена, но нет видимого огня или дыма. Пришло время идти к выходам, но не запускать".
Для получения дополнительной информации о предмете, начните с чтения главы 9 Справочника по прикладной криптографии, Menezes, van Oorschot и Vanstone, необходимо прочитать для криптографа ученика (не путать с "Прикладной криптографией" Б. Шнайера, который является хорошо написанным введением, но нигде не столь тщательным, как "Справочник" ).