Что такое хеш —
и почему это важно

Измените всего один символ — и хеш меняется полностью, а не «немного». Это специально так устроено: иначе по похожести хешей можно было бы догадываться о похожести исходных текстов.

Коллизия — когда два разных входа дают один и тот же хеш. У SHA-256 (256 бит) реальную коллизию искать дольше, чем существует Вселенная — именно это и делает его надёжным. Чтобы показать коллизию по-настоящему, а не на словах, ниже — специально слабый игрушечный хеш всего на 16 бит (65536 возможных значений). Браузер реально перебирает случайные строки, пока не найдёт совпадение:

Загадан настоящий случайный 4-значный PIN и его настоящий хеш — ничего не подстроено заранее. Ниже — честный перебор всех 10000 вариантов, но показ специально замедлен и стилизован «под кино» для наглядности (реально в браузере это происходит намного быстрее, чем можно рассмотреть глазом).

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

Лавинный эффект (шаг 2) — не просто красивое свойство. Он значит, что если у вас есть хеш «правильной», проверенной версии кода, любое постороннее изменение — хоть один символ — сразу даст совершенно другой хеш. Не нужно вручную построчно сравнивать тысячи файлов, чтобы заметить подмену.

В ноябре 2003 года кто-то без авторизации получил доступ к CVS-зеркалу репозитория ядра Linux и добавил в функцию wait4() примерно такую строку:

if ((options == (__WCLONE|__WALL)) && (current->uid = 0))
    retval = -EINVAL;

Разница с легитимным кодом — один символ: = вместо ==. Это не сравнение, а присваивание — current->uid = 0 выполняется как побочный эффект вычисления условия, то есть любой процесс, вызвавший wait4() с этими флагами, тут же становился root — независимо от того, что происходило дальше в if.

Заметили не потому, что кто-то построчно вычитал весь diff — подозрение вызвало то, что изменение попало в дерево в обход обычного процесса проверки патчей. В релиз оно не попало. Именно для таких ситуаций и нужны хеши: сравнение хеша дерева исходников с доверенной версией поймало бы это изменение мгновенно, ещё до того, как кто-то стал бы читать код глазами.