Когда безопасно использовать поврежденную хеш-функцию?
Это тривиально для использования безопасной хеш-функции как SHA-256, и продолжающий использовать MD5 для безопасности опрометчивое поведение. Однако существуют некоторые сложности к уязвимостям хеш-функции, которые я хотел бы лучше понять.
Коллизии были сгенерированы для MD4 и MD5. Согласно NIST, MD5 не является безопасной хеш-функцией. Это только берет 239 операций для генерации коллизии и никогда не должно использоваться для паролей. Однако SHA-1 уязвим для подобного нападения коллизии, в котором коллизия может быть найдена в 269 операциях, тогда как грубая сила 280. Никто не генерировал коллизию SHA-1, и NIST все еще перечисляет SHA-1 как безопасную функцию дайджеста сообщения.
Таким образом, когда безопасно использовать поврежденную хеш-функцию? Даже при том, что функция повреждается, это может все еще быть "достаточно большим". По словам Schneier хеш-функция, уязвимая для нападения коллизии, может все еще использоваться в качестве HMAC. Я полагаю, что это вызвано тем, что безопасность HMAC зависит от своего секретного ключа, и коллизия не может быть найдена, пока этот ключ не получен. После того как Вам использовали ключ в HMAC, он уже повреждается, таким образом, это - спорный вопрос. Какие уязвимости хеш-функции подорвали бы безопасность HMAC?
Давайте возьмем это свойство немного далее. Затем становится безопасно использовать очень слабый дайджест сообщения как MD4 для паролей, если соль предварительно ожидается к паролю? Следует иметь в виду MD4, и нападения на MD5 снабжают префиксом нападения, и если соль предварительно ожидается затем, взломщик не может управлять префиксом сообщения. Если соль является действительно секретом и не известна взломщику, то имеет значение, если это добавляется к паролю? Действительно ли безопасно предположить, что взломщик не может генерировать коллизию, пока все сообщение не было получено?
Вы знаете о других случаях, где поврежденная хеш-функция может использоваться в контексте защиты, не представляя уязвимость?
(Отправьте доказательство поддержки, потому что это является потрясающим!)
6 ответов
На самом деле коллизии проще, чем то, что вы указываете как в MD5, так и в SHA-1. Коллизии MD5 могут быть обнаружены во времени, эквивалентном операции 2 26,5 (где одна «операция» - это вычисление MD5 по короткому сообщению). См. эту страницу для некоторых деталей и реализации атаки (я написал этот код; он обнаруживает коллизию в среднем за 14 секунд на Core2 x86 с тактовой частотой 2,4 ГГц в 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 -битным выходом существуют общие атаки (которые работают независимо от деталей хеш-функции) в 2 n операциях для два первых свойства и 2 n / 2 операций для третьего.Если для данной хеш-функции обнаруживается атака, которая, используя специальные детали того, как работает хеш-функция, находит прообраз, второй прообраз или коллизию быстрее, чем соответствующая общая атака, то хеш-функция называется быть сломанным".
Однако не все способы использования хэш-функций полагаются на все три свойства. Например, цифровые подписи начинаются с хеширования данных, которые должны быть подписаны, а затем хеш-значение используется в остальной части алгоритма. Это зависит от устойчивости к прообразам и вторым прообразам, но на цифровые подписи сами по себе не влияют конфликты. Коллизии могут быть проблемой в некоторых конкретных сценариях подписи, когда злоумышленник может выбрать данные, которые должны быть подписаны жертвой (в основном, злоумышленник вычисляет коллизию, получает одно сообщение, подписанное жертвой, и подпись становится действительной для и другое сообщение). Этому можно противодействовать, добавив к подписанному сообщению несколько случайных байтов перед вычислением подписи (атака и решение продемонстрированы в контексте сертификатов X.509).
Безопасность HMAC основывается на другом свойстве , которое должна выполнять хэш-функция; а именно, что «функция сжатия» (элементарный блок, на котором построена хеш-функция) действует как псевдослучайная функция (PRF). Подробности о том, что такое PRF, носят технический характер, но, грубо говоря, PRF должен быть неотличим от Random Oracle . Случайный оракул представляет собой черный ящик, в котором находятся гном, игральные кости и большая книга.На некоторых входных данных гном выбирает случайный выход (с кубиками) и записывает в книгу входное сообщение и выход, который был выбран случайным образом. Гном использует книгу, чтобы проверить, видел ли он уже то же входное сообщение: если да, то гном возвращает тот же результат, что и раньше. По построению вы ничего не можете знать о выводе случайного оракула для данного сообщения, пока не попробуете это сделать.
Модель случайного оракула позволяет количественно оценить доказательство безопасности 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 Справочника по прикладной криптографии Менезеса, ван Оршота и Ванстона, которую необходимо прочитать начинающему криптографу (не его путают с «Прикладной криптографией» Б. Шнайера, которая представляет собой хорошо написанное введение, но нигде не так обстоятельно, как «Справочник»).
Сайты загрузки используют хеш MD5 в качестве контрольной суммы, чтобы определить, был ли файл поврежден во время загрузки, и я бы сказал, что сломанный хеш достаточно хорош для этой цели.
Допустим, MITM решает изменить файл (например, zip-архив или exe). Теперь злоумышленник должен сделать две вещи:
- Найти хэш-коллизию и создать из нее измененный файл
- Убедиться, что вновь созданный файл также является допустимым исполняемым файлом или zip-архивом
С неработающим хешем 1 немного проще. Но обеспечение того, чтобы коллизия одновременно соответствовала другим известным свойствам файла, требует слишком больших вычислительных затрат.
Это полностью мой собственный ответ, и я могу ужасно ошибаться.
Когда тебе все равно, безопасно это или нет.
Серьезно, не требуется дополнительных усилий, чтобы использовать безопасную хеш-функцию практически на каждом языке, а влияние на производительность незначительно, поэтому я не понимаю, почему бы вам этого не сделать.
[Редактировать после прочтения вашего вопроса]
По словам Шнайера, хеш-функция, уязвимая для коллизионной атаки, все еще может использоваться как HMAC. Я считаю, что это связано с тем, что безопасность HMAC зависит от его секретного ключа, и конфликт не может быть обнаружен, пока этот ключ не будет получен.
На самом деле, это по сути потому, что возможность генерировать коллизию для хэша не обязательно помогает вам генерировать коллизию для хеш-хэша (в сочетании с XORing, используемым HMAC).
Становится ли безопасным использовать очень слабый дайджест сообщения, такой как md4, для паролей, если к паролю добавлена соль?
Нет, нет, если хэш имеет атаку по прообразу , которая позволяет вам чтобы добавить данные к вводу. Например, если бы хеш был H (проход + соль) , нам нужна была бы атака по прообразу, которая позволяет нам найти проход 2 такой, что H (проход2 + соль) = H (проход + соль ) .
В прошлом были атаки на добавление, поэтому я уверен, что атаки на добавление возможны.
Единственный случай, когда безопасно использовать сломанную хеш-функцию, - это когда последствия коллизии безвредны или тривиальны, например при назначении файлов ведру в файловой системе.
Большая часть беспокойства по поводу использования чего-то вроде MD4 для пароля связана не столько с известными в настоящее время атаками, сколько с тем фактом, что после того, как она была проанализирована до такой степени, что генерация коллизий стала легкой, обычно предполагается, что вероятность того, что кто-то сможет использовать эти знания для создания атаки предварительного образа, значительно выше - и когда/если это произойдет, по существу все возможные варианты использования этой хэш-функции станут уязвимыми.
Ответ полностью зависит от того, для чего вы это используете. Если вам нужно предотвратить столкновение в течение нескольких миллисекунд, я буду меньше беспокоиться, чем если вам нужно предотвратить столкновение в течение нескольких десятилетий.
Какую проблему вы на самом деле пытаетесь решить?