Функция сжатия

Функция сжатия — это центральный компонент многих криптографических хеш-функций и некоторых конструкций блочных шифров, представляющий собой детерминированную операцию, которая преобразует входные данные фиксированной длины в выходные данные меньшей фиксированной длины. В отличие от общей функции сжатия данных (архиватора), криптографическая функция сжатия является необратимой, однонаправленной и устойчивой к коллизиям. Она лежит в основе таких повсеместно используемых алгоритмов, как MD5 (хотя он считается уязвимым), SHA-1, SHA-2 и SHA-3.

История и происхождение

Концепция функции сжатия возникла в 1970-х годах вместе с развитием криптографии с открытым ключом и необходимостью в эффективных методах цифровой подписи. Ранние хеш-функции (например, Snefru) строились на основе блочных шифров в режиме сцепления, где функция сжатия выполняла роль однонаправленного преобразования. Однако настоящий прорыв произошёл в 1989 году, когда американские криптографы Меркл и Дамгорд независимо друг от друга предложили метод итеративного построения хеш-функций, получивший название конструкция Меркла — Дамгорда. Именно в этой конструкции функция сжатия стала ключевым строительным блоком, принимающим на вход блок данных и промежуточное значение (состояние) и выдающим новое состояние.

В 1990-х годах конструкция Меркла — Дамгорда была использована в алгоритмах MD5 и SHA-1. После обнаружения атак на них (например, атаки Ван Шиюй и соавторов на MD5 в 2004 году) были разработаны алгоритмы семейства SHA-2, которые также используют ту же конструкцию, но с более сложной функцией сжатия. В 2012 году Национальный институт стандартов и технологий США (NIST) выбрал SHA-3, основанный на принципиально иной конструкции губки (sponge construction), где функция сжатия заменена на функцию перестановки.

Классификация и виды

Функции сжатия классифицируются в первую очередь по способу их построения и использования в хеш-функциях.

По типу конструкции

1. Функции в конструкции Меркла — Дамгорда. Это классический подход, где функция сжатия f принимает два аргумента: предыдущее состояние хеша (например, 256 бит) и текущий блок сообщения (например, 512 бит). Результат — новое состояние. Примеры: SHA-256, SHA-512.
2. Функции в конструкции губки. Здесь вместо функции сжатия используется функция перестановки (f), которая преобразует всё внутреннее состояние (обычно значительно большего размера, чем у Меркла — Дамгорда). Процесс делится на два этапа: впитывание (absorbing) данных и выжимание (squeezing) результата. Пример: алгоритм SHA-3 (Keccak).

По способу использования блочного шифра (режимы Дэвиса — Мейера и другие)

Исторически функции сжатия часто строились на базе блочных шифров. Наиболее известные режимы:

• Режим Дэвиса — Мейера. Состояние хеша шифруется ключом, равным блоку сообщения: new_state = E_message(old_state) XOR old_state. Использовался в хеш-функциях на базе DES и AES.
• Режим Матиаса — Мейера — Осеаса. Ключом является сочетание состояния и сообщения.
• Режим Миягути — Пренеля. new_state = E_old_state(message) XOR message. Этот режим лёг в основу хеш-функции Whirlpool.

По типу используемых математических операций

• Арифметические: включают сложение по модулю, повороты битов, XOR, нелинейные функции (например, выбор и мажоритарность в SHA-1/SHA-2).
• Алгебраические: используются в хеш-функциях на основе эллиптических кривых или теории чисел (например, VSH).
• Логические: основаны на битовых операциях без сложных арифметических вычислений (характерно для некоторых лёгких хеш-функций).

Устройство на примере SHA-256

Функция сжатия в SHA-256, обозначаемая как Compress, является сердцем алгоритма. Она принимает:

• Текущий хеш (H): 8 слов по 32 бита (256 бит).
• Блок сообщения (M): 16 слов по 32 бита (512 бит).

Внутри функции сжатия выполняются 64 раунда. На каждом раунде:

1. Расширяется блок сообщения (из 16 слов генерируется 64 слова).
2. Текущее состояние хеша обрабатывается через несколько нелинейных и линейных функций (Σ0, Σ1, Ch, Maj).
3. Используются константы (K), полученные из кубических корней простых чисел.

После 64 раундов происходит аддитивное обновление: исходное состояние (H_old) складывается (по модулю 2^32) с результатом обработки (H_new), предотвращая потерю информации и обеспечивая необратимость.

Свойства, гарантируемые функцией сжатия

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

• Устойчивость к прообразу: По известному выходу y невозможно (статистически) найти такой вход x, что f(x) = y.
• Устойчивость ко второму прообразу: Для заданного входа x невозможно найти другой вход x', такой что f(x) = f(x').
• Устойчивость к коллизиям: Невозможно найти два различных входа x и x', дающих одинаковый выход f(x) = f(x').

Применение

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

Хеш-функции

Это основная область применения. Хеш-функции, построенные на функциях сжатия, используются:

• Проверка целостности данных (контрольные суммы).
• Цифровые подписи (DSA, ECDSA, ГОСТ Р 34.10-2012).
• Хранение паролей совместно с солью (PBKDF2, bcrypt, scrypt, Argon2).
• Верификация цепочки блоков (биткоин, эфириум).

Построение блочных шифров (с ограничениями)

Некоторые конструкции блочных шифров (например, режим Дэвиса — Мейера) прямо основываются на функциях сжатия. Однако на практике блочные шифры редко строятся таким образом, так как это приводит к узким местам производительности и потенциальным уязвимостям.

Генерация псевдослучайных чисел

Функции сжатия используются в криптографических генераторах псевдослучайных чисел (DRBG), где они перерабатывают энтропию в длинную последовательность случайных битов (например, в стандартах NIST SP 800-90A).

Атаки и критика

Основная критика в адрес функций сжатия связана с уязвимостями конструкции Меркла — Дамгорда:

1. Атаки на коллизии.

• В 2004 году китайские криптографы (Ван и соавторы) продемонстрировали практическую коллизию для MD5, чья функция сжатия считалась в то время устойчивой.
• В 2017 году компания Google объявила о первой в истории коллизии для SHA-1, используя функцию сжатия длиной 160 бит.
• Функция сжатия SHA-256 на данный момент (2025 год) считается устойчивой к коллизиям, хотя теоретические атаки на сокращённое количество раундов существуют.

1. Атаки удлинения (length extension attack).

Для хешей Меркла — Дамгорда (MD5, SHA-1, SHA-2) известно это свойство: зная H(M) и длину M, можно вычислить H(M || pad || append), не зная M. Это делает такие хеш-функции непригодными для протоколов аутентификации сообщений без дополнительного сокрытия ключа (HMAC). Функции на основе губки (SHA-3) не подвержены этой атаке.

1. Атаки на прообраз.

Создание функции сжатия, устойчивой к нахождению прообраза, является сложной задачей. Упрощённые варианты некоторых конструкций (например, Snefru-4) были сломаны.

Интересные факты

• Функция сжатия в SHA-256 использует 64 уникальные константы. Они получены как первые 32 бита дробной части кубического корня из первых 64 простых чисел (2, 3, 5, 7...). Этот выбор служит демонстрацией того, что никаких «чёрных ходов» в константы не заложено.
• В биткоине майнинг сводится к поиску такого значения Nonce (части входного блока), чтобы функция сжатия SHA-256 выдала хеш с определённым количеством ведущих нулей. Это демонстрирует, насколько вычислительно интенсивной может быть функция сжатия — миллионы и миллиарды попыток в секунду.
• Самая маленькая хеш-функция, основанная на функции сжатия, имеет размер выхода всего 8 бит и используется для демонстрационных целей. На практике минимальный размер — 128 бит (MD4), но сейчас стандартом является 256 бит и выше.

Источники

1. Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
2. Schneier, B. (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons.
3. National Institute of Standards and Technology (NIST). (2012). FIPS PUB 180-4: Secure Hash Standard (SHS).
4. National Institute of Standards and Technology (NIST). (2015). FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions.
5. Wang, X., Yu, H. (2005). "How to Break MD5 and Other Hash Functions". Advances in Cryptology – EUROCRYPT 2005.