llmdocsсправочник разработчика

Хеш-функция

Материал из llmdocs — справочник разработчика
Портал: Безопасность (теория)
Хеш-функция
Входданные произвольной длины
Выходдайджест фиксированной длины (например, 256 бит)
КриптографическиеSHA-256, SHA-512, SHA-3, BLAKE2, BLAKE3
УстаревшиеMD5, SHA-1 (найдены коллизии)
НекриптографическиеxxHash, MurmurHash, SipHash, CRC32
СтандартыFIPS 180-4 (SHA-2), FIPS 202 (SHA-3), ГОСТ Р 34.11-2012 «Стрибог»

Хеш-функция — функция, которая превращает данные любой длины в значение фиксированного размера, называемое хешем, дайджестом или контрольной суммой. Одинаковые входные данные всегда дают одинаковый хеш, а малейшее изменение входа меняет хеш до неузнаваемости. Хеш-функции бывают двух классов: криптографические (SHA-256, SHA-3, BLAKE3) гарантируют, что подделать данные с тем же хешем практически невозможно, и защищают целостность и подписи; некриптографические (xxHash, MurmurHash) просто быстро и равномерно распределяют ключи — например, в хеш-таблицах.[1]

Свойства криптографических хешей

Свойство Смысл
Стойкость к поиску прообраза по хешу нельзя найти входные данные
Стойкость ко второму прообразу для данного сообщения нельзя найти другое с тем же хешем
Стойкость к коллизиям нельзя найти никакую пару разных сообщений с одинаковым хешем
Лавинный эффект изменение одного бита меняет примерно половину бит хеша

Коллизии неизбежно существуют (входов бесконечно много, выходов — конечное число), но найти их должно быть вычислительно невозможно. Из-за «парадокса дней рождения» для хеша длиной $n$ бит коллизия находится примерно за $2^{n/2}$ попыток, поэтому 256 бит дают 128-битную стойкость.

История и семейства

  • MD5 (1992) — сломан: коллизии находятся за секунды; с 2008 года на его коллизиях подделывали сертификаты. Годится только для некриптографических контрольных сумм.
  • SHA-1 (1995) — практическая коллизия получена в 2017 году (атака SHAttered: два разных PDF с одинаковым хешем).[3] Браузеры и Git уходят от него — Git переходит на SHA-256.
  • SHA-2 (2001) — SHA-224/256/384/512, основной стандарт сегодня.[1]
  • SHA-3 (2015) — победитель открытого конкурса NIST, алгоритм Keccak с иной конструкцией («губка»), запасной вариант на случай слабостей SHA-2.[2]
  • BLAKE2, BLAKE3 — быстрее SHA-2 на обычных процессорах; BLAKE3 распараллеливается на много ядер.[5]
  • «Стрибог» (ГОСТ Р 34.11-2012) — российский стандарт, 256 и 512 бит.[7]

Применение

  • Целостность файлов. Публикуется хеш дистрибутива; пользователь сверяет его после загрузки. Пакетные менеджеры (pip, npm, Cargo) фиксируют хеши зависимостей в lock-файлах.
  • Адресация по содержимому. Git идентифицирует объекты по хешу, образы контейнеров — по дайджесту sha256:…, так же работают системы дедупликации и бэкапов.
  • Цифровые подписи. Подписывается не документ, а его хеш (см. Криптография с открытым ключом); на этом основаны сертификаты TLS.
  • HMAC — хеш с секретным ключом для проверки подлинности сообщений: подписи вебхуков, токены, API-запросы.[4]
  • Выработка ключей (HKDF) и генерация псевдослучайных чисел.
  • Хранение паролей — только специальными медленными функциями, а не обычными хешами (см. ниже).
sha256sum ubuntu.iso                      # Linux
shasum -a 256 ubuntu.iso                  # macOS
echo -n "hello" | sha256sum
# 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

import hashlib, hmac
hashlib.sha256(b"hello").hexdigest()
hashlib.blake2b(b"hello", digest_size=32).hexdigest()
sig = hmac.new(b"secret", b"payload", hashlib.sha256).hexdigest()
hmac.compare_digest(sig, received_sig)    # сравнение за постоянное время

Частые ошибки

  • Хранить пароли как SHA-256. Обычные хеши рассчитаны на скорость: видеокарта перебирает миллиарды вариантов в секунду. Для паролей нужны медленные функции с солью — bcrypt, scrypt, Argon2 (см. Хранение паролей (bcrypt, Argon2)).
  • Самодельный MAC вида sha256(key + message) уязвим к атаке удлинения сообщения для SHA-2; нужно использовать HMAC.
  • Сравнение хешей через == в проверке подписи даёт утечку по времени; нужно сравнение за постоянное время.
  • MD5 и SHA-1 в новых системах безопасности.

Некриптографические хеши

Для хеш-таблиц, фильтров Блума, шардирования и проверки от случайных повреждений важна скорость, а не стойкость: xxHash, MurmurHash, CityHash, CRC32. Для таблиц со входом от пользователя применяют SipHash — он защищает от атак, специально создающих коллизии для замедления сервиса; его используют Python, Rust и другие языки.[6]

См. также

Источники

  1. NIST FIPS 180-4 — Secure Hash Standard (SHA-2)
  2. NIST FIPS 202 — SHA-3 Standard
  3. Stevens et al. — The first collision for full SHA-1 (SHAttered, 2017)
  4. RFC 2104 — HMAC: Keyed-Hashing for Message Authentication
  5. BLAKE3 — specification
  6. Python — hashlib
  7. ГОСТ Р 34.11-2012 — функция хэширования (RFC 6986)
Категории: