Хеш-подписи и другие подходы

Как построить цифровую подпись вообще без «новой» математики — только на хеш-функциях.

Хеш-подпись — это цифровая подпись, стойкость которой опирается только на надёжность криптографической хеш-функции; известный пример — SPHINCS+, стандартизованный как SLH-DSA.

Решёточные схемы (прошлые уроки) хороши, но это относительно молодая математика. Возникает разумный вопрос: а можно ли построить постквантовую подпись на чём-то, чему мы доверяем десятилетиями? Можно — на обычных хеш-функциях. Это самый консервативный подход: если хеш стоек к коллизиям и прообразам, стойка и подпись. Поэтому хеш-подписи держат как «страховку» рядом с решёточными.

Зачем это знать защитнику

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

От одноразовой подписи к практичной

Базовый кирпичик — одноразовая подпись Лэмпорта. Идея почти наивна. Чтобы подписывать сообщение из N бит, заранее готовят 2N случайных секретных значений (пара на каждый бит: «на ноль» и «на единицу») и публикуют их хеши как открытый ключ. Чтобы подписать, для каждого бита сообщения раскрывают одно из двух секретных значений — то, что соответствует значению бита. Проверяющий хеширует раскрытые значения и сверяет с открытым ключом.

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

import hashlib

def H(x):
    return hashlib.sha256(x).hexdigest()

# Подпишем 1 бит (упрощённо): пара СЕКРЕТОВ — на значение 0 и на значение 1
sk0 = b"secret-for-bit-0"
sk1 = b"secret-for-bit-1"
public_key = (H(sk0), H(sk1))    # публикуем ТОЛЬКО хеши секретов

bit = 1                          # подписываем значение бита = 1
signature = sk1                  # раскрываем секрет, отвечающий за 1

# Проверка: хеш раскрытого секрета должен совпасть с нужной частью pk
ok = H(signature) == public_key[bit]
print("Открытый ключ:", public_key[0][:8], "/", public_key[1][:8])
print("Подпись валидна:", ok)

Вывод:

Открытый ключ: 5b0320bb / 0e90c9c8
Подпись валидна: True

Это игрушка на один бит, но в ней — вся суть: безопасность держится исключительно на невозможности обратить хеш.

Деревья Меркла и SPHINCS+

Чтобы из одноразовых подписей сделать ключ, которым можно подписать много сообщений, используют дерево Меркла. Берут множество одноразовых ключей, попарно хешируют их вверх до единственного корня — этот корень и становится одним компактным открытым ключом. Каждая подпись включает «путь» хешей до корня, доказывающий, что использованный одноразовый ключ действительно входит в дерево. Так появляются практичные схемы.

Их два семейства. Stateful (с состоянием) — например, XMSS и LMS — очень эффективны, но требуют строго помнить, какие одноразовые ключи уже израсходованы: повторное использование фатально. Это удобно для контролируемой среды (подпись прошивок на заводе), но опасно там, где состояние легко потерять (резервные копии, кластеры). Stateless (без состояния) — это и есть SPHINCS+ (стандарт SLH-DSA): он устроен так, что помнить ничего не нужно — выбор одноразовых ключей делается псевдослучайно и безопасно, поэтому подпись нельзя «случайно повторить». За это удобство платят размером подписи.

Плюсы, минусы и где применять

Вывод практичен: SPHINCS+ — не для подписи каждого TLS-пакета (там важны скорость и размер), а для редких, но критичных и долгоживущих подписей, где консервативная стойкость важнее компактности: корневые сертификаты, подпись firmware и образов ОС, нотаризация архивов на десятилетия. Часто рекомендуют гибрид: основная подпись — ML-DSA, а особо критичные артефакты подписывают дополнительно SPHINCS+ как страховку на другой математике.

Как это работает под капотом

Откуда берётся квантовая стойкость хеш-подписей? Атака на хеш — это либо найти прообраз (по хешу восстановить вход), либо коллизию (два разных входа с одним хешом). Лучшее, что даёт квант, — алгоритм Гровера с квадратичным ускорением. Как и для симметрики, это лечится длиной: хеш с достаточно длинным выходом сохраняет высокий запас стойкости даже против Гровера. Никакого аналога Шора для «обращения хорошей хеш-функции» не известно — именно поэтому подход считают особенно надёжным «по построению».

Цена — размер. Подпись несёт в себе раскрытые одноразовые значения и пути в дереве Меркла, и всё это складывается в килобайты. Для канала, где подписей мало и они редки, это терпимо; для высоконагруженного протокола — накладно. Ещё одна тонкость касается stateful-вариантов (XMSS/LMS): их безопасность критически зависит от невозможности повторно использовать одноразовый ключ, поэтому в средах с репликацией и бэкапами выбирают stateless SPHINCS+, где этот класс ошибок исключён конструктивно.

Кратко о других подходах

Помимо решёток и хешей, в постквантовом мире есть и другие семейства, у которых своя ниша:

• Code-based (на основе кодов с коррекцией ошибок, например Classic McEliece) — очень старая и доверенная идея для обмена ключом; минус — огромный открытый ключ.
• Multivariate (системы многочленов от многих переменных) — давали компактные подписи, но многие схемы были взломаны, поэтому к ним относятся осторожно.
• Isogeny-based (на изогениях эллиптических кривых) — привлекали малым размером ключа, но известная схема SIKE была сломана классической атакой в 2022 году, что лишний раз показало ценность консервативного запаса.

Эта история — лучший аргумент за разнообразие и гибриды: пока одни схемы падают, надёжный «скучный» фундамент вроде хешей остаётся опорой.

Как защититься

• Применяйте хеш-подписи там, где они сильны: редкие, долгоживущие, критичные подписи (корни доверия, firmware, архивы), а не массовый трафик.
• Предпочитайте stateless SPHINCS+ (SLH-DSA) в средах с бэкапами/репликацией; stateful XMSS/LMS — только при строгом контроле состояния.
• Закладывайте большие размеры подписи в форматы и хранилища заранее.
• Рассматривайте «двойную» подпись (ML-DSA + SPHINCS+) для самых ценных артефактов, чтобы не зависеть от одной математической основы.
• Используйте стандартные реализации и длинные хеши; помните, что от Гровера спасает длина выхода, а аналога Шора для хешей не известно.

Итоги

• Хеш-подписи строятся целиком на стойкости хеш-функции — это самый консервативный постквантовый подход; основа — одноразовая подпись Лэмпорта и деревья Меркла.
• SPHINCS+ (SLH-DSA) — stateless-схема: не требует помнить израсходованные ключи, поэтому безопасна там, где stateful XMSS/LMS опасны (бэкапы, кластеры).
• Плата за надёжность — большие и медленные подписи, поэтому их место — редкие критичные артефакты (корни CA, firmware, архивы), а не каждый пакет.
• Квантовая стойкость хеш-подписей опирается на отсутствие аналога Шора для хешей; угроза Гровера лечится длиной выхода.
• Другие семейства (code-based, multivariate, isogeny) занимают свои ниши; падение SIKE и multivariate-схем — довод в пользу разнообразия и гибридных подписей.