почему хороший алгоритм хеширования не позволяет злоумышленникам находить два сообщения с одинаковым хешем?

Question

Я читал википедию, и там написано

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

Но почему? Я понимаю, что вы можете поместить длинную историю Макбета в хэш-функцию и получить из нее длинный хэш. Затем вы можете добавить историю Беовульфа, чтобы снова получить из нее еще один хэш.

Так что, поскольку эта функция отображает множество вещей на более короткую длину, неизбежно будут совпадения, как я мог бы вставить в историю Хобита в хэш-функцию и получить тот же результат, что и Беовульф, хорошо, но это неизбежно верно (?), Поскольку мы производим более короткую длину вывода из нашего ввода? И даже если выход найден, почему это проблема?

Я могу представить, если я переверну его и выведу Хобита вместо Беовульфа, это будет плохо, но почему это полезно для атакующего?

Лучшее

Answer 1

Да, конечно, будут конфликты по причинам, которые вы описываете.

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

Что касается причины ...

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

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

Answer 2

Да, неизбежно, что при отображении длинного сообщения на более короткий хэш будут возникать коллизии, поскольку хэш не может содержать все возможные значения сообщения. По той же причине вы не можете «инвертировать» хеш для уникального создания либо Беовульфа, либо Хоббита - но если вы сгенерировали каждый возможный текст и отфильтровали те, которые имели ваше конкретное хеш-значение, вы найдете оба текста (среди миллиардов других ).

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

Пару лет назад голландские исследователи продемонстрировали слабости в MD5, опубликовав хэш своего "прогноза" на президентские выборы в США. Конечно, у них не было никакого способа узнать результат заранее, но с вычислительной мощью PS3 они создали файл PDF для каждого кандидата , каждый с одинаковым хеш-значением. Последствия для MD5 - уже на пути к снижению - в качестве надежного алгоритма для цифровых подписей стали еще более ужасными ...

Answer 3

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

Злоумышленник хотел бы заменить Беовульфа на Хоббита, чтобы увеличить видимость саксонской поэзии, но криптографический хеш, который используется в протоколе, не позволит ему.

Answer 4

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

В противном случае коллизии также являются проблемой с сертификатами.