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

~3 минуты · 3 примера · 2 вопроса

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

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

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

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 даёт более короткий хеш и уязвим к коллизиям. Запомни: для безопасности — только современные алгоритмы.

Проверь себя

Два вопроса по уроку. Ответы никуда не идут — это для тебя.

1Что такое лавинный эффект хеш-функции?

2Что такое коллизия хеш-функции?

Следующий урок
13 · Хеширование паролей и соль Открыть урок 13
Урок 11: Что такое хеш