Лавинный эффект и коллизии

Измени в данных хотя бы один символ — и хеш изменится до неузнаваемости. Это называется лавинным эффектом.

Лавинный эффект

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

import hashlib

a = hashlib.sha256("кот".encode()).hexdigest()
b = hashlib.sha256("коТ".encode()).hexdigest()  # одна буква заглавная

print("кот:", a)
print("коТ:", b)
print("Похожи ли хеши:", a[:10] == b[:10])

Вывод:

кот: a3f...
коТ: 7c1...
Похожи ли хеши: False

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

Считаем, насколько изменился хеш

Посчитаем долю различающихся hex-символов между двумя хешами:

import hashlib

h1 = hashlib.sha256("version 1".encode()).hexdigest()
h2 = hashlib.sha256("version 2".encode()).hexdigest()

diff = sum(1 for x, y in zip(h1, h2) if x != y)
print("Различается символов:", diff, "из", len(h1))
print("Это около", round(diff / len(h1) * 100), "%")

Вывод:

Различается символов: 59 из 64
Это около 92 %

Изменили одну цифру в тексте — поменялось почти всё. Вот он, лавинный эффект во всей красе.

Что такое коллизия

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

Почему MD5 больше не используют

Старый алгоритм MD5 когда-то был популярен, но учёные научились находить для него коллизии за разумное время. Это значит, что злоумышленник может подделать данные так, чтобы хеш совпал. Поэтому MD5 считается сломанным для задач безопасности. Сегодня рекомендуют SHA-256 и новее.

import hashlib

text = "download.exe"
print("MD5    :", hashlib.md5(text.encode()).hexdigest())
print("SHA-256:", hashlib.sha256(text.encode()).hexdigest())

Вывод:

MD5    : 6b2a...короткий (128 бит)
SHA-256: 2f5e...длинный (256 бит)

MD5 даёт более короткий хеш и уязвим к коллизиям. Запомни: для безопасности — только современные алгоритмы.