Хеш — криптографическая функция сжатия данных¶
Хеш (от англ. hash — «рубить, измельчать») — это функция преобразования входных данных произвольной длины в фиксированную последовательность битов, называемую хеш-значением или хеш-суммой. Хеш-функция обладает свойством необратимости: по хеш-значению восстановить исходные данные практически невозможно. Широко применяется в криптографии, информационной безопасности, базах данных и системах контроля целостности.
¶Основные свойства
Надёжная криптографическая хеш-функция должна удовлетворять ряду требований:
- Детерминированность — одни и те же входные данные всегда дают один и тот же хеш.
- Необратимость (устойчивость к обращению) — вычислить входные данные по известному хешу вычислительно неосуществимо.
- Сопротивление коллизиям — найти два разных набора данных, дающих одинаковый хеш, должно быть крайне трудно.
- Эффект лавинного изменения — изменение хотя бы одного бита входных данных приводит к радикальному изменению хеш-значения.
- Авалантность — хеш-значение выглядит как псевдослучайная последовательность битов, не выдающая структуры исходных данных.
¶Классификация
¶Некриптографические хеш-функции
Используются для быстрого сопоставления данных: хеш-таблицы в программировании, дедупликация файлов, проверка целостности при загрузке. Примеры: CRC32, MurmurHash, xxHash. Для этих задач криптографическая устойчивость не требуется, важна скорость.
¶Криптографические хеш-функции
Рассчитаны на противодействие злоумышленнику, который может подбирать входные данные с целью получить нужное хеш-значение. Основные применяемые на практике алгоритмы:
| Алгоритм | Длина хеша (бит) | Год | Примечание |
|---|---|---|---|
| MD5 | 128 | 1992 | Уязвим к коллизиям, не рекомендуется для защиты |
| SHA-1 | 160 | 1995 | Коллизии найдены в 2017 году (атака SHAttered) |
| SHA-2 (SHA-256, SHA-512) | 256–512 | 2001 | Основной стандарт на практике |
| SHA-3 (Keccak) | 224–512 | 2015 | Стандарт NIST, иная конструкция (sponge) |
| ГОСТ Р 34.11-2012 (Стрибог) | 256, 512 | 2012 | Национальный стандарт РФ |
В России для криптографических целей применяется стандарт ГОСТ Р 34.11-2012 («Стрибог»), разработанный под руководством В. Б. Маркова и утверждённый Федеральной службой по техническому и экспортному контролю. Он является обязательным при использовании криптосредств в государственных информационных системах и в соответствии с требованиями ФСТЭК.
¶Принцип работы
Хеш-функции устроены по-разному, но большинство современных алгоритмов используют итеративную конструкцию: входные данные разбиваются на блоки фиксированной длины, каждый блок «смешивается» с промежуточным состоянием через серию раундов перестановок, побитовых операций и арифметики по модулю. Промежуточное состояние передаётся в следующий раунд, пока не будет обработан весь вход. Результат финального состояния и есть хеш.
В алгоритмах семейства SHA-2 используется конструкция Меркла — Дамгора, в SHA-3 — губчатая конструкция (sponge construction), предложенная Гвидо Бертони и коллегами.
¶Применение
¶Хранение паролей
Пароли пользователей в базах данных хранятся не в открытом виде, а в виде хешей. При входе вводимый пароль хешируется и сравнивается с сохранённым значением. Для защиты от перебора применяются медленные функции (bcrypt, scrypt, Argon2) или быстрые хеши с «солью» — случайным дополнением к паролю перед хешированием.
¶Проверка целостности
Хеш-сумма файла позволяет обнаружить повреждение или несанкционированное изменение. Распространены утилиты MD5sum, sha256sum; пакетные менеджеры Linux (dpkg, rpm) проверяют хеши пакетов при установке.
¶Цифровые подписи и блокчейны
Подпись документа часто вычисляется не от самого документа, а от его хеша — это ускоряет процесс и не раскрывает содержимое. В криптовалюте Bitcoin транзакции идентифицируются хешами (SHA-256, двойное применение — SHA-256d), а блоки связаны в цепочку через хеш предыдущего блока.
¶Электронные системы документооборота
В России хеш-суммы применяются в системах ЭДО и при электронной подписи в соответствии с Федеральным законом № 63-ФЗ «Об электронной подписи».
¶Коллизии и криптоанализ
Исторически MD5 считался устойчивым, но в 2004 году Вэйдай и Ван продемонстрировали практическую атаку на коллизии. В 2017 году исследователи из Google и Лёвенского католического университета опубликовали первую практическую коллизию для SHA-1. После этого браузеры и центры сертификации отказались от SHA-1 в пользу SHA-2 и SHA-3.
¶Интересные факты
Хеш-функции иногда используются для генерации псевдослучайных чисел, в игровых механиках (процедурная генерация мира) и для проверки уникальности данных при дедупликации в файловых системах (например, Btrfs).
Источники:
- ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хеширования»
- NIST FIPS 180-4: Secure Hash Standard (SHS)
- Менялов В. С. «Основы криптографии»
- Stallings W. «Cryptography and Network Security: Principles and Practice»