GHASH

GHASH — это универсальная хеш-функция, используемая в режиме аутентифицированного шифрования GCM (Galois/Counter Mode) для обеспечения целостности и аутентичности данных. GHASH основана на умножении в поле Галуа GF(2¹²⁸) и представляет собой полиномиальный хеш, вычисляемый над зашифрованным текстом и дополнительными аутентифицированными данными (AAD). В отличие от криптографических хеш-функций, таких как SHA-256, GHASH не является устойчивой к коллизиям в классическом смысле, но обеспечивает защиту от подделки сообщений при условии секретности ключа.

Математические основы

GHASH оперирует в конечном поле GF(2¹²⁸), где элементы представляются двоичными многочленами степени не выше 127. Умножение выполняется по модулю неприводимого многочлена x¹²⁸ + x⁷ + x² + x + 1. Каждый блок данных размером 128 бит интерпретируется как элемент поля, причём биты упорядочиваются от старшего к младшему (big-endian).

Ключ хеширования H вычисляется как результат шифрования нулевого блока (128 нулевых бит) на блочном шифре, используемом в GCM (обычно AES-128, AES-192 или AES-256). Этот ключ H является секретным и неизвестным атакующему.

Алгоритм вычисления

Входными данными для GHASH являются:

• A — дополнительные аутентифицированные данные (AAD), произвольной длины;
• C — зашифрованный текст, произвольной длины.

Выходом является 128-битный тег аутентичности T.

Алгоритм состоит из следующих шагов:

1. Дополнение до границы 128 бит: если длина A или C не кратна 128 битам, к ним добавляется минимальное количество нулевых бит так, чтобы общая длина стала кратной 128. Это дополнение выполняется отдельно для A и C.
2. Формирование последовательности блоков: данные разбиваются на 128-битные блоки. Пусть m — количество блоков A (после дополнения), n — количество блоков C (после дополнения). Затем формируется финальный блок L, содержащий 64-битные представления длин A и C (в битах) в порядке big-endian.
3. Инициализация: переменная Y₀ устанавливается в нулевой блок (128 нулевых бит).
4. Итеративное умножение: для каждого блока Xᵢ (в порядке: сначала блоки A, затем блоки C, затем блок L) выполняется:

Yᵢ = (Yᵢ₋₁ ⊕ Xᵢ) · H, где ⊕ — побитовое исключающее ИЛИ, а · — умножение в GF(2¹²⁸).

1. Результат: итоговое значение Y (после обработки блока L) является тегом GHASH.

Использование в GCM

В режиме GCM тег аутентичности T вычисляется как: T = GHASH(A, C) ⊕ E(K, nonce || counter₀), где E(K, nonce || counter₀) — шифрование начального счётчика на ключе K. Это обеспечивает защиту от подделки сообщений: без знания ключа K злоумышленник не может вычислить корректный тег для модифицированного текста.

Криптографические свойства

GHASH является ε-почти универсальной хеш-функцией (ε-AU): вероятность коллизии для двух различных входов при случайном ключе H не превышает ε = (m + n + 1) / 2¹²⁸, где m и n — длины входных данных в блоках. Это свойство гарантирует, что атакующий не может подделать тег с вероятностью, существенно превышающей 2⁻¹²⁸, при условии, что ключ H остаётся секретным.

Однако GHASH не является криптографически стойкой хеш-функцией: она не обладает свойством необратимости (preimage resistance) и устойчивости к коллизиям в классическом смысле. Если ключ H известен, можно легко найти коллизии или подобрать входные данные для заданного тега.

Критика и уязвимости

Атаки на основе известного ключа

Если злоумышленник получает доступ к ключу H (например, через утечку или криптоанализ блочного шифра), он может подделывать любые сообщения. В 2013 году была продемонстрирована атака на GCM с использованием слабых ключей AES, но на практике она маловероятна.

Атаки на основе длины тега

При использовании укороченных тегов (менее 128 бит) вероятность успешной подделки возрастает. Например, для 32-битного тега вероятность составляет 2⁻³², что может быть приемлемо для некоторых приложений, но не для высокозащищённых систем.

Проблемы с неоднократным использованием nonce

В GCM nonce (однократно используемое число) должен быть уникальным для каждого сообщения при одном и том же ключе. Если nonce повторяется, ключ H может быть восстановлен, что приводит к полной потере аутентичности. Это фундаментальное ограничение, вытекающее из структуры GHASH.

Атаки на основе времени

Реализации GHASH, не защищённые от атак по сторонним каналам, могут быть уязвимы к атакам по времени. Умножение в GF(2¹²⁸) может выполняться за разное время в зависимости от входных данных, что позволяет злоумышленнику извлекать информацию о ключе H. Современные реализации (например, с использованием инструкций PCLMULQDQ в процессорах x86) обеспечивают постоянное время выполнения.

Реализации

GHASH реализован во многих криптографических библиотеках, включая OpenSSL, BoringSSL, LibreSSL, а также в аппаратных модулях (например, в Intel AES-NI с инструкцией PCLMULQDQ). В программных реализациях для повышения производительности часто используется табличный метод (precomputed tables), хотя он может быть уязвим к атакам по кэшу.

Альтернативы

В современных протоколах (например, TLS 1.3) GCM с GHASH остаётся широко распространённым, но существуют альтернативы:

• Poly1305 — полиномиальный хеш, используемый в режиме ChaCha20-Poly1305, который не требует умножения в поле Галуа и часто быстрее на платформах без аппаратной поддержки.
• GMAC — вариант GHASH, используемый для аутентификации без шифрования.
• AES-GCM-SIV — модификация GCM, устойчивая к повторному использованию nonce, но с более сложной реализацией.

Источники

• McGrew, D., Viega, J. (2004). «The Galois/Counter Mode of Operation (GCM)». NIST.
• NIST Special Publication 800-38D (2007). «Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC».
• Ferguson, N. (2005). «Authentication weaknesses in GCM». Comments on NIST.
• Saarinen, M.-J. O. (2012). «Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes». FSE 2012.