Понимание слабости столкновения ша-1
Согласно различным источникам, атаки, ищущие столкновения ша-1, были улучшены до 2^52 операций:
http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252/
То, что я хотел бы знать, - это влияние этих открытий на системы, которые не подвергаются атакам. То есть, если я хэширую случайные данные, каковы статистические шансы столкновения? Иными словами, указывают ли недавние исследования на то, что атака на день рождения методом грубой силы имеет больше шансов найти столкновения, которые первоначально предлагались?
В некоторых рецензиях, таких как приведенная выше, говорится, что для получения столкновения SHA-1 с помощью грубой силы потребуется 2 80 операций. Большинство источников говорят, что 2^80 является теоретическим числом (я полагаю, потому что никакая хеш-функция действительно не распределяется идеально даже по ее пространству дайджеста).
Так есть ли какие-либо из объявленных слабых сторон столкновения sha1 в фундаментальном распределении хэшей? Или увеличенные шансы столкновения являются только результатом управляемых математических атак?
Я понимаю, что, в конце концов, это всего лишь игра шансов, и что они представляют собой бесконечно малое изменение, которое приведет к столкновению ваших первого и второго сообщений. Я также понимаю, что даже 2^52 - это действительно большое число, но я все еще хочу понять последствия для системы, которая не подвергается атаке. Поэтому, пожалуйста, не отвечайте "не беспокойтесь об этом".
3 ответа
Результатом, объявленным в вашей ссылке, является атака, последовательность тщательно выбранных алгоритмически шагов, которые генерируют столкновения с большей вероятностью, чем случайная атака. Это не слабость в распределении хеш-функции. Ну, хорошо, это так, но не в том смысле, что вероятность случайной атаки порядка 2^52 может быть успешной.
Если никто не пытается генерировать коллизии в ваших хеш-выходах, этот результат не повлияет на вас.
Хорошие хеш-функции устойчивы к трем различным типам атак (как говорится в статье).
Самое важное сопротивление в практическом смысле - это сопротивление второго изображения. Это в основном означает, что при наличии сообщений M1 и Hash(M1)=H1 трудно найти M2 такой, что Hash(M2)=H1.
Если бы кто-то нашел способ сделать это эффективно, это было бы плохо. Кроме того, атака прообраза не подвержена парадоксу дня рождения, поскольку сообщение M1 для нас исправлено.
Это не атака перед изображением или вторым изображением, а просто атака по обнаружению столкновений. Чтобы ответить на ваш вопрос, никакая атака грубой силой НЕ имеет более высокой вероятности обнаружения столкновений. Это означает, что метод наивной грубой силы в сочетании с методами исследователей приводит к обнаружению столкновений после 2^52. Стандартная атака грубой силы все еще занимает 2^80.
Ключевой вопрос: "Может ли злоумышленник изменить сообщения m1 и m2"? Если это так, злоумышленнику нужно найти m1, m2 такой, что hash(m1) = hash(m2). Это атака на день рождения, и сложность значительно уменьшается - становится квадратным корнем. Если выход хеша равен 128 битам (MD5), сложность составляет 2^64, что вполне достижимо для текущей вычислительной мощности.
Обычный приведенный пример - продавец просит своего секретаря напечатать сообщение "Я продам его за 10 миллионов долларов". Секретарь схемы создает 2 документа, один из которых гласит: "Я продам его за 10 миллионов долларов", а другой - "Я продам его за x миллионов долларов", где х намного меньше 10, изменяет оба сообщения, добавляя пробелы и используя заглавные буквы. слова и т. д., изменяет х, пока хэш (m1) = хэш (м2). Теперь секретарь показывает правильное сообщение m1 продавцу, и он подписывает его, используя свой закрытый ключ, в результате чего получается хэш h. Секретарь переключает сообщение и отсылает (м2, ч). Только продавец имеет доступ к своему закрытому ключу, и поэтому он не может отказаться и сказать, что он не подписал сообщение.
Для SHA1, который выводит 160 бит, атака на день рождения уменьшает сложность до 2^80. Это должно быть безопасно в течение 30 лет и более. Новые правительственные постановления, спецификации 4G 3gpp начинают требовать SHA256.
Но если в вашем случае использования злоумышленник не может изменить оба сообщения (сценарии прообраза или второго прообраза), то для SHA1 сложность составляет 2^160. Должен быть безопасным для вечности, если не обнаружена атака без перебора.