Когда безопасно использовать сломанную хеш-функцию?
Тривиально использовать безопасную хеш-функцию, такую как SHA-256, и продолжать использовать MD5 для безопасности - это безрассудное поведение. Тем не менее, есть некоторые сложности, связанные с уязвимостями хеш-функций, которые я хотел бы лучше понять.
Столкновения были созданы для MD4 и MD5. Согласно NIST, MD5 не является безопасной хеш-функцией. Для создания коллизии требуется всего 2 39 операций, и их никогда не следует использовать для паролей. Однако SHA-1 уязвим к аналогичной атаке столкновения, в которой столкновение может быть найдено в 2 69 операциях, тогда как грубая сила составляет 2 80. Никто не генерировал коллизию SHA-1, и NIST по-прежнему перечисляет SHA-1 в качестве защищенной функции дайджеста сообщений.
Так когда же безопасно использовать сломанную хеш-функцию? Даже если функция нарушена, она все равно может быть "достаточно большой". Согласно Шнайеру, хеш-функция, уязвимая к атаке столкновений, все еще может использоваться как HMAC. Я полагаю, что это потому, что безопасность HMAC зависит от его секретного ключа, и коллизия не может быть найдена, пока этот ключ не получен. Как только у вас есть ключ, используемый в HMAC, он уже сломан, так что это спорный вопрос. Какие уязвимости хеш-функции могут подорвать безопасность HMAC?
Давайте возьмем это свойство немного дальше. Тогда станет ли безопасным использование очень слабого дайджеста сообщений, такого как MD4, для паролей, если перед паролем будет добавлена соль? Имейте в виду, что атаки MD4 и MD5 являются атаками с префиксами, и, если перед ними стоит соль, злоумышленник не может контролировать префикс сообщения. Если соль действительно является секретом и не известна злоумышленнику, то имеет ли значение, добавлена ли она к паролю? Можно ли предположить, что злоумышленник не может создать столкновение, пока не будет получено все сообщение?
Знаете ли вы о других случаях, когда сломанная хеш-функция может использоваться в контексте безопасности, не создавая уязвимости?
(Пожалуйста, опубликуйте подтверждающие доказательства, потому что это здорово!)
6 ответов
На самом деле коллизии проще, чем то, что вы перечисляете как в MD5, так и в SHA-1. Столкновения MD5 могут быть обнаружены во времени, эквивалентном 226,5 операции (где одна "операция" - это вычисление MD5 по короткому сообщению). См. Эту страницу для получения дополнительной информации и реализации атаки (я написал этот код; он обнаруживает столкновение в среднем в течение 14 секунд на 2,4 ГГц Core2 x86 в 64-битном режиме).
Точно так же самая известная атака на SHA-1 - примерно 261 операция, а не 269. Это все еще теоретическое (фактическое столкновение еще не было произведено), но оно находится в пределах возможного.
Что касается последствий для безопасности: обычно говорят, что хэш-функции имеют три свойства:
- Без прообраза: учитывая y, не должно быть возможным найти x такой, что h (x) = y.
- Никакого второго прообраза: при заданном x1 не должно быть возможным найти x2 (отличный от x1) такой, что h (x1) = h (x2).
- Нет столкновения: не должно быть возможным найти какие-либо x1 и x2 (отличные друг от друга), такие что h (x1) = h (x2).
Для хеш-функции с n- битным выходом существуют общие атаки (которые работают независимо от деталей хэш-функции) в 2n операций для двух первых свойств и 2n / 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, но обе атаки используют один и тот же источник. Тем не менее, обратите внимание, что атака подделки обошлась в 258, что довольно высоко (фактическая подделка не производилась, результат все еще теоретический), но существенно ниже, чем уровень сопротивления, ожидаемый от HMAC (с надежной хэш-функцией с n- Выходной бит, HMAC должен выдерживать до 2n рабочего фактора; n = 128 для MD4).
Таким образом, хотя коллизии сами по себе не означают слабых мест в HMAC, они являются плохой новостью. На практике коллизии являются проблемой для очень немногих установок. Но знать, влияют ли коллизии на данное использование хеш-функций, достаточно сложно, поэтому совершенно неразумно продолжать использовать хеш-функцию, для которой были продемонстрированы коллизии.
Для SHA-1 атака все еще является теоретической, и SHA-1 широко развернут. Ситуация описана так: "Сигнализация включена, но нет видимого огня или дыма. Пора идти к выходу, но не бежать".
Для получения дополнительной информации по этому вопросу начните с прочтения главы 9 " Руководства по прикладной криптографии" Менезеса, ван Ооршота и Ванстоуна, которую обязательно нужно прочитать начинающему криптографу (не путать с "Прикладной криптографией" Б. Шнейера)., что является хорошо написанным введением, но нигде не так обстоятельно, как "Справочник").
Единственный случай, когда безопасно использовать сломанную хеш-функцию, - это когда последствия столкновения безвредны или тривиальны, например, при назначении файлов в корзину в файловой системе.
Сайты загрузки используют хэш MD5 в качестве контрольной суммы, чтобы определить, был ли файл поврежден во время загрузки, и я бы сказал, что сломанный хэш достаточно хорош для этой цели.
Допустим, MITM решает изменить файл (например, zip-архив или exe-файл). Теперь злоумышленник должен сделать две вещи -
- Найдите коллизию хешей и создайте из нее измененный файл
- Убедитесь, что вновь созданный файл также является допустимым exe-файлом или zip-архивом.
С битым хешем 1 немного проще. Но обеспечение того, что столкновение одновременно отвечает другим известным свойствам файла, является слишком дорогим в вычислительном отношении.
Это полностью мой собственный ответ, и я могу быть ужасно неправ.
Когда вам все равно, безопасно это или нет.
Серьезно, не требуется никаких дополнительных усилий для использования безопасной хеш-функции практически на всех языках, а влияние на производительность незначительно, поэтому я не понимаю, почему вы этого не сделаете.
[Изменить после прочтения вашего вопроса]
Согласно Шнайеру, хеш-функция, уязвимая к атаке столкновений, все еще может использоваться как HMAC. Я полагаю, что это потому, что безопасность HMAC зависит от его секретного ключа, и коллизия не может быть найдена, пока этот ключ не получен.
На самом деле, это в основном потому, что возможность генерировать коллизию для хеша не обязательно помогает вам генерировать коллизию для хеш- кода (в сочетании с XORing, используемым HMAC).
Тогда станет ли безопасным использование очень слабого дайджеста сообщений, такого как md4, для паролей, если к паролю добавлена соль?
Нет, если у хеша есть атака прообраза, которая позволяет вам добавлять данные к входу. Например, если хеш был H(pass + salt)нам нужна предварительная атака, которая позволяет нам найти pass2 такой, что H(pass2 + salt) = H(pass + salt),
В прошлом были атаки с добавлением, так что я уверен, что возможны атаки с предварительной подготовкой.
Ответ полностью зависит от того, для чего вы его используете. Если вам нужно предотвратить столкновение с несколькими миллисекундами, я бы беспокоился меньше, чем если бы вам нужно было предотвратить столкновение в течение нескольких десятилетий.
Какую проблему вы на самом деле пытаетесь решить?
Большая часть беспокойства по поводу использования чего-то вроде MD4 для пароля связана не столько с известными в настоящее время атаками, сколько с тем фактом, что после того, как он проанализирован до такой степени, что генерация коллизий проста, обычно считается, что кто-то значительно сможет использовать эти знания для создания прообразной атаки - и когда / если это произойдет, практически все возможные варианты использования этой хэш-функции станут уязвимыми.