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

https://stackoverflow.com/questions/2889473

04-10-2019
|

Вопрос

Использовать безопасную хеш-функцию, такую как SHA-256, тривиально, а продолжать использовать MD5 для обеспечения безопасности — безрассудное поведение.Однако существуют некоторые сложности, связанные с уязвимостями хэш-функций, которые мне хотелось бы лучше понять.

Столкновения были создано для MD4 и MD5.Согласно NIST, MD5 не является безопасной хэш-функцией.Это займет всего 2³⁹ операции по созданию столкновения и никогда не должно быть используется для паролей.Однако SHA-1 уязвим для аналогичная атака столкновением в котором столкновение можно найти за 2⁶⁹ операций, тогда как грубая сила равна 2⁸⁰.Никто не сгенерировал коллизию SHA-1 и NIST по-прежнему называет SHA-1 функцией безопасного дайджеста сообщений..

Итак, когда безопасно использовать сломанную хэш-функцию?Даже если функция сломана, она все равно может быть «достаточно большой». По мнению Шнайера хеш-функция, уязвимая для атаки коллизией, все еще может использоваться в качестве HMAC.Я считаю, что это связано с тем, что безопасность HMAC зависит от его секретного ключа, и коллизию невозможно обнаружить, пока этот ключ не будет получен.Если у вас есть ключ, используемый в HMAC, он уже сломан, так что это спорный вопрос.Какие уязвимости хэш-функции могут подорвать безопасность HMAC?

Давайте продвинем это свойство немного дальше.Станет ли тогда безопасным использовать для паролей очень слабый дайджест сообщения, такой как MD4, если к паролю добавляется соль?Имейте в виду, что атаки MD4 и MD5 являются префиксными атаками, и если перед ними добавлена соль, злоумышленник не сможет контролировать префикс сообщения.Если соль действительно является секретом и не известна злоумышленнику, имеет ли значение, добавлена ли она к паролю?Можно ли с уверенностью предположить, что злоумышленник не сможет создать коллизию, пока не будет получено все сообщение?

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

(Пожалуйста, опубликуйте подтверждающие доказательства, потому что это потрясающе!)

Решение

На самом деле коллизии проще, чем то, что вы указываете как в MD5, так и в SHA-1.Коллизии MD5 можно найти за время, эквивалентное 2^26.5 операция (где одна «операция» — это вычисление MD5 по короткому сообщению).Видеть эта страница некоторые подробности и реализацию атаки (я написал этот код;он обнаруживает коллизию в среднем за 14 секунд на процессоре Core2 x86 с частотой 2,4 ГГц в 64-битном режиме).

Аналогично, самая известная атака на SHA-1 произошла примерно через 2⁶¹ операции, не 2⁶⁹.Это все еще теоретическое решение (реального столкновения еще не произошло), но оно находится в пределах осуществимого.

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

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

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

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

Безопасность HMAC опирается на другой свойство, которое должна выполнять хэш-функция;а именно, что «функция сжатия» (элементарный кирпичик, на котором построена хеш-функция) действует как Псевдослучайная функция (ПРФ).Подробности о том, что такое PRF, весьма технические, но, грубо говоря, PRF должен быть неотличим от PRF. Случайный оракул.Случайный оракул моделируется как черный ящик, в котором лежат гном, несколько игральных костей и большая книга.Для некоторых входных данных гном выбирает случайный выход (с помощью игральной кости) и записывает в книгу входное сообщение и выход, который был выбран случайным образом.Гном использует книгу, чтобы проверить, видел ли он уже такое же входное сообщение:если да, то гном возвращает тот же результат, что и раньше.По своей конструкции вы ничего не можете знать о выводе случайного оракула для данного сообщения, пока не попробуете это сделать.

Модель случайного оракула позволяет количественно оценить доказательство безопасности HMAC при вызовах PRF.По сути, доказательство утверждает, что HMAC невозможно взломать, не вызывая PRF огромное количество раз, и под «огромным» я имею в виду вычислительную невозможность.

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

Если функция сжатия представляет собой PRF затем хеш-функция автоматически устойчива к коллизиям.Это часть магии PRF. Поэтому, если мы сможем найти коллизии для хеш-функции, то мы знаем, что внутренняя функция сжатия не является PRF.Это не превращает коллизии в атаку на HMAC.Возможность генерировать коллизии по своему желанию не помогает взломать HMAC.Однако эти коллизии показывают, что доказательство безопасности, связанное с HMAC, не применимо.Гарантия недействительна.Это то же самое, что и портативный компьютер:открытие корпуса не обязательно приведет к поломке машины, но после этого вы будете предоставлены сами себе.

в Ким-Бирюков-Пренель-Хонг В статье представлены некоторые атаки на HMAC, в частности атака с подделкой HMAC-MD4.Атака использует недостатки MD4 (его «слабости»), которые делают его не-PRF.Варианты тех же уязвимостей использовались для генерации коллизий на MD4 (MD4 полностью сломан;некоторые атаки генерируют коллизии быстрее, чем вычисление самой хэш-функции!).Таким образом, коллизии не подразумевают атаку HMAC, но обе атаки используют один и тот же источник.Однако учтите, что атака с подделкой стоила 2⁵⁸, что довольно высоко (реальной подделки не было, результат все еще теоретический), но существенно ниже уровня устойчивости, ожидаемого от HMAC (с надежной хеш-функцией с н-битный вывод, HMAC должен сопротивляться до 2^н фактор работы; п = 128 для MD4).

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

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

Для получения дополнительной информации по этому вопросу начните с прочтения главы 9 Справочник по прикладной криптографии, Менезеса, ван Ооршота и Ванстона, книгу, которую обязательно должен прочитать начинающий криптограф (не путать с «Прикладной криптографией» Б.Шнайера, которое представляет собой хорошо написанное введение, но далеко не такое подробное, как «Справочник»).

Другие советы

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

Когда тебе все равно, безопасно это или нет.

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

[Изменить после прочтения вашего вопроса]

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow