На самом деле коллизии проще, чем то, что вы перечисляете как в 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 (в отличие от х 1 ), такой что ч (х 1 ) = ч (х 2 ) .
- Нет столкновений: не должно быть возможным найти какие-либо x 1 и x 2 (отличные друг от друга) такие что ч (х 1 ) = ч (х 2 ) .
Для хэш-функции с выходом n -бит, есть общие атаки (которые работают независимо от деталей хэш-функции) в 2 n операции для двух первых свойств и 2 n / 2 операции для третьего. Если для заданной хеш-функции обнаружена атака, которая, используя специальные детали работы хеш-функции, находит прообраз, второе прообраз или столкновение быстрее, чем соответствующая общая атака, то хеш-функция называется быть "сломленным".
Однако не все виды использования хеш-функций зависят от всех трех свойств. Например, цифровые подписи начинаются с хэширования данных, которые должны быть подписаны, а затем значение хеш-функции используется в остальной части алгоритма. Это зависит от устойчивости к прообразам и вторым прообразам, но на цифровые подписи как таковые не влияют столкновения. Столкновения могут быть проблемой в некоторых конкретных сценариях подписи, когда злоумышленник выбирает данные, которые должны быть подписаны жертвой (в основном, злоумышленник вычисляет коллизию, получает одно сообщение, подписанное жертвой, и подпись становится действительной для другое сообщение также). Этому можно противодействовать, добавляя несколько случайных байтов к подписанному сообщению перед вычислением подписи (атака и решение, продемонстрированное в контексте сертификатов X.509).
Безопасность HMAC основана на другом свойстве, которое должна выполнять хеш-функция; а именно, что «функция сжатия» (элементарный блок, на котором построена хеш-функция) действует как псевдослучайная функция (PRF). Детали того, что такое PRF, довольно технические, но, грубо говоря, PRF должны быть неотличимы от Случайного Оракула . Случайный оракул моделируется как черный ящик, который содержит гнома, несколько кубиков и большую книгу. На некоторых входных данных гном выбирает случайный выход (с кубиками) и записывает в книгу входное сообщение и выход, который был выбран случайным образом. Гном использует книгу, чтобы проверить, видел ли он уже то же входное сообщение: если это так, то гном возвращает тот же вывод, что и ранее. По построению вы ничего не можете знать о выводе случайного оракула для данного сообщения, пока не попробуете его.
Модель случайного оракула позволяет количественно определить доказательство безопасности 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 Справочника по прикладной криптографии , написанного Менезесом, ван Ооршотом и Ванстоуном, обязательного к прочтению для начинающего криптографа (не путать с «Прикладной криптографией» Б. Шнайера, которая является хорошо написанным введением, но нигде не настолько исчерпывающей, как «Настольная книга»).