Когда безопасно использовать сломанную хэш-функцию?

Ответ 1

На самом деле коллизии проще, чем то, что вы перечисляете как на MD5, так и на SHA-1. Столкновения MD5 можно найти во времени, эквивалентном операции 2 ^26.5 (где одна "операция" - это вычисление MD5 по короткому сообщению). См. эту страницу для некоторых деталей и реализации атаки (я написал этот код: он обнаруживает столкновение в среднем 14 секунд на 2.4 ГГц Core2 x86 в режиме 64 бит).

Аналогично, наиболее известная атака на SHA-1 выполняется примерно в 2 ⁶¹ а не 2 ⁶⁹. Он по-прежнему теоретический (фактического столкновения еще не было создано), но оно находится в пределах возможного.

Что касается последствий для безопасности: хеш-функции обычно называются тремя свойствами:

• Нет прообраза: если задано y, не представляется возможным найти x так, что h (x) = y.
• Нет второго прообраза: если задано x ₁, не представляется возможным найти x ₂ (отличное от x ₁) такое, что h (x ₁) = h (x ₂).
• Никакого столкновения: не должно быть возможным найти x ₁ и x ₂ (отличные друг от друга) такие, что h (x ₁) = h (x ₂).

Для хэш-функции с 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 ⁵⁸ что довольно велико (фактическая подделка не производилась, результат по-прежнему теоретический), но существенно ниже, чем ожидаемый уровень сопротивления от HMAC (с надежная хеш-функция с n-разрядным выходом, HMAC должен выдерживать до 2 ⁿ коэффициент работы, n = 128 для MD4).

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

Для SHA-1 атака все еще теоретическая, и SHA-1 широко используется. Ситуация была описана следующим образом: "Тревога включена, но нет видимого огня или дыма. Пришло время идти к выходам, но не запускать".

Для получения дополнительной информации о предмете, начните с чтения главы 9 Справочника по прикладной криптографии, Menezes, van Oorschot и Vanstone, необходимо прочитать для криптографа ученика (не путать с "Прикладной криптографией" Б. Шнайера, который является хорошо написанным введением, но нигде не столь тщательным, как "Справочник" ).

Ответ 2

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

Ответ 3

Если вам все равно, безопасно это или нет.

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

[Редактировать после фактического чтения вашего вопроса]

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

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

Будет ли безопасным использовать очень слабый дайджест сообщения, например md4 для паролей, если соль будет перенесена на пароль?

Нет, если хэш не имеет preimage attack, который позволяет вам добавлять данные на вход. Например, если хэш был H(pass + salt), нам понадобится атака с прообразом, которая позволяет нам найти pass2 таким образом, чтобы H(pass2 + salt) = H(pass + salt).

В прошлом были атаки append, поэтому я уверен, что возможны атаки в префайле.

Ответ 4

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

Предположим, что MITM решает изменить файл (например, zip-архив или exe). Теперь атакующий должен сделать две вещи -

• Найдите столкновение с хешем и создайте из него измененный файл.
• Убедитесь, что вновь созданный файл также является действительным exe или zip-архивом.

С сломанным хешем, 1 немного легче. Но обеспечение того, чтобы столкновение одновременно соответствовало другим известным свойствам файла, слишком дорого вычисляется.

Это полностью мой собственный ответ, и я мог бы быть ужасно не прав.

Ответ 5

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

Какую проблему вы пытаетесь решить?

Ответ 6

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