Понимание слабости столкновения ша-1

Question

Согласно различным источникам, атаки, ищущие столкновения ша-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 - это действительно большое число, но я все еще хочу понять последствия для системы, которая не подвергается атаке. Поэтому, пожалуйста, не отвечайте "не беспокойтесь об этом".

Answer 1

Хорошо, хорошие хеш-функции устойчивы к трем различным типам атак (как говорится в статье).

Наиболее важным сопротивлением в практическом смысле является 2-е сопротивление перед изображением. Это в основном означает, что при наличии сообщений M1 и Hash (M1) = H1 трудно найти M2 такой, что Hash (M2) = H1.

Если бы кто-то нашел способ сделать это эффективно, это было бы плохо. Кроме того, атака прообраза не подвержена парадоксу дня рождения, поскольку сообщение M1 для нас исправлено.

Это не атака перед изображением или вторая, а только атака по обнаружению столкновений. Чтобы ответить на ваш вопрос, никакая атака грубой силой НЕ имеет более высокой вероятности обнаружения столкновений. Это означает, что метод наивной грубой силы в сочетании с методами исследователей приводит к обнаружению столкновений после 2 ^ 52. Стандартная атака грубой силы все еще занимает 2 ^ 80.

Answer 2

Ключевой вопрос: «Может ли злоумышленник изменить сообщения 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. Должен быть безопасным для вечности, если не обнаружена атака без перебора.

Answer 3

Результатом, объявленным в вашей ссылке, является атака , последовательность осторожных, алгоритмически выбранных шагов, которые генерируют столкновения с большей вероятностью, чем случайная атака. Это не слабость в распределении хеш-функции. Что ж, да, но не в том смысле, что вероятность случайной атаки порядка 2 ^ 52 может быть успешной.

Если никто не пытается генерировать коллизии в ваших хеш-выходах, этот результат вас не затронет.