Что означает «безопасный» для хеша

Любая функция, отображающая вводы в выводы фиксированного размера, в конце концов отобразит два разных ввода в один и тот же вывод, ведь вводов бесконечно много, а выводов лишь конечное число. То, что хеш безопасен, не означает, что коллизий не может быть; это означает, что их нельзя найти за выполнимый объём работы. Это охватывают три отдельных свойства.

Три свойства

  • Стойкость к прообразу. По значению хеша h невыполнимо найти какой-либо ввод m с hash(m) = h. Это свойство односторонности: отпечаток не должен выдавать, что его породило. Для n-битного хеша это стоит около 2ⁿ работы.
  • Стойкость ко второму прообразу. По заданному вводу m1 невыполнимо найти другой ввод m2 с тем же хешем. Атакующий не может подделать второй документ, совпадающий с отпечатком данного. Тоже около 2ⁿ работы.
  • Стойкость к коллизиям. Невыполнимо найти любые два разных ввода, дающих одно значение хеша. Атакующий может выбрать оба, что делает это самым лёгким из трёх для атаки.

Граница дня рождения

Стойкость к коллизиям слабее двух других по тонкой причине — парадоксу дней рождения. В комнате всего из 23 человек примерно 50% вероятность, что у двоих совпадёт день рождения, потому что число пар растёт квадратично. Тот же эффект применим к хешам: найти коллизию в n-битном хеше требует лишь около 2^(n/2) попыток, а не 2ⁿ.

Это вдвое снижает эффективную стойкость к коллизиям:

  • даёт около 128 бит стойкости к коллизиям (2¹²⁸ работы), что далеко за пределами досягаемости.
  • 128-битный хеш вроде давал бы лишь около 64 бит стойкости к коллизиям, даже не будь он взломан по другим причинам, и поэтому сам размер вывода имеет значение.

Поэтому современные хеши используют 256 бит или больше: чтобы держать эту вдвое уменьшенную цифру комфортно вне досягаемости любого атакующего.

Почему найденная коллизия опасна

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

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