Хеш-функция

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

Хеш-функция принимает последовательность байтов произвольной длины и возвращает значение строго фиксированного размера — его называют хешем, дайджестом или свёрткой. SHA-256 всегда выдаёт 256 бит, MD5 — 128 бит, CRC-32 — 32 бита, и размер выхода не зависит от того, подан на вход пустой файл или образ диска на сорок гигабайт.

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

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

Свойства, по которым оценивают алгоритм

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

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

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

Односторонность. Восстановить вход по выходу можно только перебором. Для 256-битного выхода это порядка 2 в степени 256 вариантов — величина, недостижимая ни для какого мыслимого вычислителя.

Стойкость к коллизиям. Различают стойкость ко второму прообразу (по данному сообщению найти другое с тем же хешем) и стойкость к коллизиям вообще (найти любую пару). Вторая слабее из-за парадокса дней рождения: для n-битного выхода пара ищется примерно за 2 в степени n/2 операций, то есть у 128-битного дайджеста запас всего 2 в степени 64.

Отдельно оценивают скорость, и требования к ней противоположны в разных задачах. Для проверки целостности гигабайтных образов функция должна быть быстрой; для хранения паролей — намеренно медленной, иначе видеокарта переберёт словарь за минуты.

Семейства алгоритмов и производные схемы

Некриптографические хеши считаются дёшево и защищают только от случайности. Сюда относят CRC-32, Adler-32, FNV, MurmurHash, xxHash. Подогнать данные под заданный остаток — линейная задача над полем из двух элементов, решаемая за миллисекунды, поэтому циклический избыточный код ловит помехи в канале, но бесполезен против намеренной подмены. Вторая ниша таких функций — хеш-таблицы и распределение ключей по серверам, где важна только равномерность.

Криптографические функции дополнительно обязаны быть односторонними и стойкими к коллизиям. Исторический ряд: MD5 (128 бит, 1991), SHA-1 (160 бит, 1995), семейство SHA-2 с вариантами на 224, 256, 384 и 512 бит (2001), SHA-3 на конструкции Keccak (2015), BLAKE2 и BLAKE3, российский стандарт ГОСТ Р 34.11-2012 «Стрибог» с выходом на 256 и 512 бит.

Ломали их по очереди. Коллизии MD5 нашли в 2004 году, сегодня их считают за секунды на обычном ноутбуке. Практическую коллизию SHA-1 опубликовали в 2017 году под названием SHAttered, после чего алгоритм вывели из подписей и сертификатов. Для SHA-256 сопоставимых результатов нет: лучшие известные атаки работают лишь на урезанное число раундов.

Классическая схема — Меркла и Дамгора. Сообщение дополняется служебными битами до длины, кратной размеру блока (512 бит у MD5, SHA-1 и SHA-256), после чего блоки последовательно перемешиваются с внутренним состоянием функцией сжатия. Схема проста, но уязвима к атаке удлинения сообщения: зная хеш и длину входа, можно вычислить хеш продолжения, не зная самого входа.

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

Поверх голой функции строят прикладные схемы. HMAC подмешивает секретный ключ по фиксированной формуле с двумя вложенными вызовами и даёт код аутентичности сообщения — подписи вебхуков платёжных сервисов делаются именно так. Соль, случайная строка, приписываемая к данным перед хешированием, лишает атакующего заранее посчитанных таблиц. Функции выработки ключа PBKDF2, bcrypt, scrypt и Argon2 намеренно замедляют вычисление в тысячи раз и требуют памяти, чтобы обесценить перебор на видеокартах. Дерево Меркла позволяет доказать вхождение отдельного блока в большой массив, предъявив логарифмическое число хешей вместо всего массива.

Где хеш-функции работают на практике

Хеш-таблицы и шардирование. Функция превращает ключ в номер корзины или сервера, и от неё требуется скорость с равномерностью, а не криптостойкость.

Контроль целостности. Опубликованный рядом с дистрибутивом дайджест позволяет убедиться, что файл скачался целиком и не подменён по дороге.

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

Электронная подпись. Подписывают не документ, а его хеш — это на порядки быстрее и не зависит от размера файла. Российская квалифицированная подпись работает по ГОСТ Р 34.10-2012 в паре со «Стрибогом».

Идемпотентность запросов. Хеш тела запроса служит ключом идемпотентности: повторная отправка того же платежа даёт тот же ключ, и второе списание не создаётся.

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

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

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

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

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

Что такое коллизия и насколько она опасна?

Коллизия — два разных входа с одинаковым хешем. Существование коллизий неизбежно, опасна только возможность их находить. Для MD5 и SHA-1 это давно достижимо, поэтому на них нельзя строить подписи и сертификаты. Для SHA-256 и «Стрибога» практических способов найти коллизию не известно, и совпадение дайджестов считают доказательством совпадения данных.

Можно ли восстановить исходные данные по хешу?

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

Какой алгоритм выбирать сегодня?

Для целостности и подписей — SHA-256 либо SHA-512 из семейства SHA-2, для российской юридически значимой подписи — ГОСТ Р 34.11-2012. Для паролей — Argon2id или bcrypt с настроенной сложностью. Для контроля случайных искажений в канале хватает CRC. MD5 и SHA-1 в новых проектах применять не следует нигде, кроме совместимости со старыми форматами.

Контрольная цифра штрих-кода — это хеш?

Нет. Контрольная цифра EAN-13 считается по фиксированной схеме взвешенного суммирования по модулю 10 и занимает один десятичный разряд. Она ловит одиночную ошибку набора и большинство перестановок соседних цифр, но не обладает ни односторонностью, ни лавинным эффектом. Это контрольная сумма из семейства некриптографических проверок, а не хеш-функция.