Хеш-функция: что это, свойства, коллизии и примеры на Python

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

Что такое хеш-функция простыми словами

Хешем (hash) называют короткий «отпечаток» данных, а хеширование обозначает процесс, в котором хеш-функция читает данные и по своему алгоритму выдаёт результат заданного размера. У SHA-256 результат всегда 256 бит, в шестнадцатеричной записи 64 символа:

import hashlib

for text in ["hello", "Hello", ""]:
    digest = hashlib.sha256(text.encode("utf-8")).hexdigest()
    print(len(digest), digest)

64 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
64 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969
64 e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

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

Как работает хеш-функция

Сначала данные дополняют до нужной длины и режут на блоки. У SHA-256 блок 512 бит, у SHA-512 1024 бита. Затем блоки по очереди обрабатываются набором операций над словами и константами, и каждое промежуточное значение хеша зависит от предыдущего. Значение после последнего блока и есть хеш. Поэтому данные можно подавать частями через update():

h = hashlib.sha256()
h.update(b"hel")
h.update(b"lo")
print(h.hexdigest() == hashlib.sha256(b"hello").hexdigest())
print(h.block_size, h.digest_size)

True
64 32

Размеры в байтах: блок 64, результат 32. Так считают хеш больших файлов: файл в 10 ГБ читают кусками, и в памяти одновременно лежит только один кусок.

Свойства хеш-функции

От хорошей хеш-функции ждут четырёх вещей:

• детерминированность: одинаковые входные данные всегда дают одинаковый результат;
• фиксированная длина хеша при входе произвольной длины;
• высокая скорость вычислений (кроме функций для паролей);
• лавинный эффект: изменение одного бита входа меняет примерно половину битов результата.

Буквы h и H в ASCII отличаются ровно одним битом. Сравним входы и хеши побитово: на входе разница в один бит, у хешей SHA-256 в 125 битах из 256, почти половина.

def bits_diff(a: bytes, b: bytes) -> int:
    return (int.from_bytes(a) ^ int.from_bytes(b)).bit_count()

print(bits_diff(b"hello", b"Hello"))
print(bits_diff(hashlib.sha256(b"hello").digest(),
                hashlib.sha256(b"Hello").digest()))

1
125

Криптографические хеш-функции дополнительно должны выдерживать три атаки:

Некриптографическая функция, например встроенная hash() в Python, нужна для скорости в хеш-таблицах и этих гарантий не даёт.

Коллизии: почему они неизбежны

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

Здесь работает парадокс дней рождения: для хеша из n бит коллизию находят примерно за 2^(n/2) попыток, а не за 2^n. Проверим на SHA-256, у которого оставим первые 16, 24 и 32 бита:

def short_hash(text: str, hex_chars: int) -> str:
    return hashlib.sha256(text.encode("utf-8")).hexdigest()[:hex_chars]

for hex_chars in (4, 6, 8):
    seen = {}
    i = 0
    while True:
        key = f"user{i}"
        h = short_hash(key, hex_chars)
        if h in seen:
            print(f"{hex_chars * 4} бит: {seen[h]} и {key} -> {h}, попыток {i + 1}")
            break
        seen[h] = key
        i += 1

16 бит: user187 и user295 -> 57eb, попыток 296
24 бит: user9955 и user11153 -> bc7d03, попыток 11154
32 бит: user90137 и user118756 -> c29dbc05, попыток 118757

Для 16 бит вариантов 65 536, а совпадение нашлось на 296-й попытке. В среднем коллизия появляется примерно через 1,25·√N попыток: 320, 5120 и 81 920 для наших трёх размеров, конкретный прогон может отклониться в обе стороны. Для полного SHA-256 та же оценка даёт около 2^128 вычислений.

Если алгоритм хеширования ослаблен, коллизию находят намного быстрее полного перебора. Вот известная пара блоков данных по 128 байт. Они отличаются в шести байтах, MD5 у них одинаковый, а SHA-256 разный:

a = bytes.fromhex(
    "d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89"
    "55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b"
    "d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0"
    "e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70"
)
b = bytes.fromhex(
    "d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89"
    "55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b"
    "d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0"
    "e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70"
)
print(len(a), a == b, sum(x != y for x, y in zip(a, b)))
print(hashlib.md5(a).hexdigest())
print(hashlib.md5(b).hexdigest())
print(hashlib.sha256(a).hexdigest()[:16], hashlib.sha256(b).hexdigest()[:16])

128 False 6
79054025255fb1a26e4bc422aef54eb4
79054025255fb1a26e4bc422aef54eb4
8d12236e5c4ed9f4 b9fef2a8fc93b05e

Алгоритмы хеширования: MD5, SHA-1, SHA-256 и другие

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

У MD5 и SHA-1 находят коллизии, то есть пары разных входов с общим хешем. Восстановить данные по готовому хешу MD5 по-прежнему нельзя: описанная для него атака на первый прообраз требует около 2^123 операций. Контрольные суммы MD5 ещё встречаются рядом с файлами для скачивания. Но для MD5 можно заранее подготовить два разных файла с одной суммой, поэтому для проверки файлов берите SHA-256. Все эти функции, кроме Стрибога, вызываются через hashlib.new(имя, данные), например hashlib.new("sha3_256", b"hello"), а у части есть и отдельный конструктор вроде hashlib.md5(b"hello").

Хеширование в Python: hash() и hashlib

В Python для хеширования два инструмента: модуль hashlib и встроенная hash().

hashlib работает с байтами. Строку сначала кодируют, иначе программа упадёт:

try:
    hashlib.sha256("пароль")
except TypeError as e:
    print(f"TypeError: {e}")

TypeError: Strings must be encoded before hashing

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

Встроенная hash() возвращает целое число и нужна словарям и множествам, чтобы быстро найти ключ. Равные числа дают одинаковый хеш даже при разных типах, например у 1 и 1.0 он общий. Внутри одного запуска хеш строки постоянный, а между запусками меняется: хеши str и bytes солятся случайным значением при старте интерпретатора. Зафиксируем соль переменной PYTHONHASHSEED и запустим два процесса:

import os
import subprocess
import sys

for seed in ["1", "2"]:
    env = dict(os.environ, PYTHONHASHSEED=seed)
    result = subprocess.run([sys.executable, "-c", 'print(hash("hello"))'],
                            env=env, capture_output=True, text=True)
    print(seed, result.stdout.strip())

1 -1712148659304476210
2 -2276782357261739453

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

Где используется хеширование

Проверка целостности файлов

Файл открывают в двоичном режиме. С Python 3.11 есть готовая hashlib.file_digest(), в старых версиях файл читают кусками и передают в update():

from pathlib import Path

path = Path("report.txt")
for content in ["Отчёт за октябрь\n", "Отчёт за октябрь.\n"]:
    path.write_bytes(content.encode("utf-8"))
    with path.open("rb") as f:
        print(hashlib.file_digest(f, "sha256").hexdigest())
path.unlink()

889f638a9078a325d54626821d89bbb5058abca74a3ce0d5cc9a72d7866b00c2
fa0fe595271d0a056b18ae11ef2c70747f8fcf88fe297c266e7e692a7997bc18

Одна добавленная точка изменила хеш целиком. Файл записан через write_bytes: текстовый режим в Windows заменяет \n на \r\n, и на разных системах хеш вышел бы разным. Скачанный дистрибутив проверяют так же: сравнивают SHA-256 с суммой на сайте проекта.

Хеш-таблицы и словари

Словарь dict и множество set хранят данные в хеш-таблице и по хешу ключа быстро находят его при поиске. Равные объекты обязаны давать одинаковый хеш. Хеш ключа не должен меняться, иначе ключ окажется не в той ячейке таблицы. Класс с __eq__, но без __hash__ ключом словаря быть не может. Хеш-индекс в базе данных устроен на том же принципе, это один из видов индексов в SQL.

Подлинность сообщений и цифровая подпись

Обычный хеш защищает от случайной порчи. От подмены он не спасает: злоумышленник изменит данные и пересчитает хеш. Подлинность проверяют с помощью HMAC: он считает хеш с участием секретного ключа, который знают только отправитель и получатель.

import hmac

key = b"server-secret"
message = b"order=1042&sum=1990"
tag = hmac.new(key, message, hashlib.sha256).hexdigest()
print(tag)

forged = hmac.new(key, b"order=1042&sum=1", hashlib.sha256).hexdigest()
print(hmac.compare_digest(tag, forged))

364f9caedd21a3e593f499441619783ce61b29772189888847cad62f04514547
False

Цифровую подпись обычно ставят не на весь документ: сначала считают его хеш, потом подписывают этот короткий результат. Функция для подписи обязана быть стойкой к коллизиям, и MD5 там больше не допускается.

Блокчейн

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

Хеширование паролей: какую функцию выбрать

Хранить пароли в открытом виде нельзя: при утечке базы данных приложения злоумышленник получит все аккаунты сразу. Но и обычный SHA-256 не спасает. Посмотрите на двух пользователей с одинаковым паролем:

users = {"anna": "qwerty", "ivan": "qwerty"}
for login, password in users.items():
    print(login, hashlib.sha256(password.encode("utf-8")).hexdigest()[:16])

anna 65e84be33532fb78
ivan 65e84be33532fb78

Хеши совпали, и злоумышленник сразу видит, у кого общий пароль. Вторая беда в скорости: с быстрой функцией за короткое время можно перебрать миллионы вариантов по словарю. Соль, уникальная случайная строка для каждого пользователя, решает первую проблему. Скорость перебора она не меняет. Мы бы не советовали хранить sha256(соль + пароль) даже в учебном проекте: для паролей нужна медленная функция с солью, сложность которой поднимают параметрами.

В стандартной библиотеке таких две: hashlib.scrypt() и hashlib.pbkdf2_hmac(). Возьмём scrypt с параметрами n=2^17, r=8, p=1. С ними scrypt нужно 128·n·r байт, то есть 128 МиБ, а OpenSSL по умолчанию разрешает около 32 МиБ, поэтому вызов без maxmem падает:

try:
    hashlib.scrypt(b"qwerty", salt=os.urandom(16), n=2**17, r=8, p=1)
except ValueError as e:
    print(f"ValueError: {e}")

ValueError: [digital envelope routines] memory limit exceeded

Текст ошибки зависит от версии OpenSSL, у нас 3.0.18. Лимит поднимаем до 256 МиБ, соль 16 байт берём из os.urandom() и храним рядом с хешем:

import hashlib, hmac, os

SCRYPT = {"n": 2**17, "r": 8, "p": 1, "maxmem": 256 * 1024 * 1024, "dklen": 32}

def hash_password(password: str) -> bytes:
    salt = os.urandom(16)
    key = hashlib.scrypt(password.encode("utf-8"), salt=salt, **SCRYPT)
    return salt + key

def check_password(password: str, stored: bytes) -> bool:
    salt, key = stored[:16], stored[16:]
    candidate = hashlib.scrypt(password.encode("utf-8"), salt=salt, **SCRYPT)
    return hmac.compare_digest(candidate, key)

anna = hash_password("qwerty")
ivan = hash_password("qwerty")
print(len(anna), anna == ivan)
print(check_password("qwerty", anna), check_password("qwerty1", anna))

48 False
True False

Запись занимает 48 байт: 16 байт соли и 32 байта ключа. Одинаковые пароли теперь хранятся по-разному, верный пароль проходит проверку, неверный нет. Сравнение идёт через hmac.compare_digest(): оно не обрывает сравнение на первом расхождении, поэтому по времени ответа нельзя судить о содержимом.

Если можно поставить сторонний пакет, для нового проекта берите Argon2id (в Python пакет argon2-cffi) или bcrypt. У bcrypt пароль ограничен 72 байтами, а русская буква в UTF-8 занимает 2 байта, то есть в лимит входит около 36 русских букв. pbkdf2_hmac с SHA-256 используйте, только если другие варианты недоступны, и с сотнями тысяч итераций. Сам пароль генерируйте модулем secrets, как в нашем генераторе паролей на Python. А чтобы таблица с хешами не утекла через запрос к базе данных, закройте SQL-инъекции.

Частые вопросы

Можно ли расшифровать хеш?

Нет, хеш не шифр, и ключа к нему не существует. Пароль по хешу находят только перебором: считают хеши вариантов и сравнивают. С быстрым MD5 или SHA-1 перебор идёт быстро, а медленная функция вроде scrypt или Argon2id делает каждую попытку дорогой.

Чем хеширование отличается от шифрования?

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

Что выбрать для контрольной суммы файла, MD5 или SHA-256?

SHA-256. Для MD5 можно заранее подготовить два разных файла с одинаковой суммой, как в примере с коллизией выше. Если MD5 в вашей сборке Python заблокирован, а нужен он не для защиты данных, передайте usedforsecurity=False.

Можно ли посчитать хеш онлайн?

Можно, для публичных данных. Пароли, ключи и личные данные в онлайн-сервисы не вводите: команда python -c "import hashlib; print(hashlib.sha256(b'text').hexdigest())" посчитает то же самое локально.

Почему hash() в Python каждый раз разный?

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