9 октября 2026Команда Сарнас

SequenceHash: мультихеширование для практиков

Конкатенация при хешировании коллекций и обязательств давно известна как источник неоднозначности: одна и та же строка может быть получена разными наборами фрагментов. SequenceHash предлагает хеш-агностичную альтернативу TupleHash, применимую не только к Keccak, но и к SHA2, BLAKE и другим функциям. Разбираем устройство конструкции, роль 128-битного кодирования длины и защиту от атак удлинения.

Обычный хеш-объект с методом update() не различает границы между фрагментами данных. Если скормить ему Test 0, Test 1 и Test 2 тремя отдельными вызовами, результат совпадёт с хешированием одной строки Test 0Test 1Test 2 — под капотом входные данные просто конкатенируются. Это свойство превращается в уязвимость там, где нужно хешировать коллекцию объектов или строить криптографические обязательства: неоднозначные границы позволяют открыть обязательство несколькими способами, а в zero-knowledge proofs через Fiat-Shamir transform ведут к риску подделок. Разберём, как устроена конструкция SequenceHash, которая закрывает эту проблему, чем она отличается от стандарта TupleHash и что важно знать при её реализации.

Проблема мультихеширования

При обычном хешировании входные элементы, переданные отдельными вызовами, не разделяются с точки зрения хеш-функции — они просто конкатенируются. Границы между элементами не фиксируются, поэтому одну и ту же итоговую строку можно получить разными последовательностями вызовов. Три набора — Test 0 + Test 1 + Test 2, Test 0Test 1 + Test 2 и Test 0 + пустой фрагмент + Test 1Test 2 — дают одинаковый дайджест 4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c.

На практике это эксплуатируется там, где нужно хешировать коллекцию объектов или создавать криптографическое обязательство. Если граница между секретным значением и маскирующим значением неясна, такое обязательство можно открыть несколькими разными способами. В zero-knowledge доказательствах неправильное мультихеширование вносит риск подделок.

Чем SequenceHash отличается от TupleHash

Наиболее известный стандарт мультихеширования — TupleHash, определённый в NIST SP 800-185. Он решает задачу простым способом через length-prefix encoding и обрабатывает входные данные практически неограниченного размера.

У TupleHash есть недостаток: он определён только для работы с Keccak. При замене Keccak на другую хеш-функцию некоторые важные свойства безопасности, например устойчивость к length-extension, могут исчезнуть. Без реализации Keccak под рукой использовать TupleHash невозможно. Это особенно актуально в секторе государственных контрактов, где CNSA 2.0 предписывает SHA384 и SHA512 почти для всего.

SequenceHash — это хеш-агностичная конструкция мультихеширования, аналогичная тому, как HMAC является не привязанной к хешу конструкцией MAC. Её можно использовать с любой хеш-функцией, включая всё семейство SHA2, BLAKE, RIPEMD и другие.

Как устроен SequenceHash

SequenceHash разделяет входные элементы с помощью length-encoding: каждый вход кодируется своей длиной, а не просто конкатенируется. Поэтому подача Test 0 и Test 1 в последовательные вызовы не эквивалентна подаче Test 0Test 1 в один вызов.

Длина кодируется 128-битным целым фиксированной длины, а не целым переменной длины, как в TupleHash. Считается она в байтах. После такого кодирования входные данные под капотом просто конкатенируются. Это даёт однозначность: для двух входов (A, B) гарантируется, что не существует другой последовательности входов (I₁, …, Iₜ) любой длины t, дающей тот же вход в базовую хеш-функцию.

Почему 128 бит

128-битное кодирование длины выбрано для простоты реализации на 32- и 64-битных системах — дополнение нулями легко выполняется. Предел в 2¹²⁸−1 байт превышает все практические соображения на обозримое будущее и превышает заданные ограничения самых популярных хеш-функций SHA256 и SHA512 (2⁶¹ и 2¹²⁵ байт соответственно). Байтовые счётчики выбраны для простоты, так как почти всё хеширование сегодня выполняется программно над строками из 8-, 16-, 32- или 64-битных значений.

Защита от length extension и строки кастомизации

SequenceHash применяет двойное хеширование. При атаке удлинения длины злоумышленник, зная H(A), дописывает данные B и пересчитывает хеш, продолжая работу функции с уже известного промежуточного состояния. Внутренний проход завершает хеширование и выдаёт результат фиксированной длины, поэтому продолжить вычисление с этого состояния нельзя, и вычислить H(A‖B) из H(A) не удаётся.

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

SequenceHash на практике

Для последовательностей Test 0, Test 1, Test 2 при использовании SequenceHash с SHA-256 получаются три разных значения:

6eea7264b266d35bd5e483ef042189d2cebe51f9e8b764b90b0f9c82185de7ca
1469d91e90c1d9c6189f576822e900f5cc8c3cdbd2ec51256df649d37c1688f7
1800a2188e126c79dac8f7cf7e38a66e3f797654c15a5e49248a94d4e99bcaae

Обычный hashlib с SHA-256 для тех же трёх вариантов даёт одинаковый результат 4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c, потому что update просто конкатенирует байты.

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

API библиотеки

Библиотека sequencehash предоставляет два класса: SequenceHash и SequenceMAC. Объект SequenceHash создаётся вызовом sequencehash.SequenceHash.new('sha256'), где аргумент — имя алгоритма хеширования. Объект SequenceMAC создаётся вызовом sequencehash.SequenceMAC.new(KEY, digestmod='sha256'), где KEY — ключ длиной 32 байта или больше, а digestmod задаёт алгоритм.

Данные добавляются методом add(), причём каждое добавление атомарно: значение добавляется как независимый объект с кодированием длины. Результат получается методом result(), возвращающим байты, которые можно вывести через .hex(). Дополнительно SequenceHash поддерживает метод result_with_customizer(b'CUST 0'), принимающий строку кастомизации для разделения доменов.

SequenceMAC: ключевой вариант

SequenceMAC — это вариант SequenceHash с ключом, который принимает ключи длиной до 2¹²⁸−1 байт. В отличие от HMAC, где длинные ключи хешируются перед использованием и потому имеют короткое представление, SequenceMAC включает длины ключей в заголовочный блок. Поэтому длинные ключи не имеют эквивалентного короткого представления.

Требования к ключу

SequenceMAC требует ключ длиной не менее 32 байт (256 бит); при использовании более короткого ключа спецификация его запрещает. В сочетании с хорошей 256-битной хеш-функцией такой ключ даёт примерно 128-битный уровень стойкости к атакам подделки. Ключи длиной более 32 байт поддерживаются вплоть до 2¹²⁸−1 байт, но увеличение длины ключа не повышает безопасность: хеш-функция и этап предобработки ключа накладывают жёсткий предел.

Для хеш-функций с выходом меньше 256 бит уровень стойкости примерно равен половине длины хеша (112 бит для SHA224 и 80 бит для RIPEMD160), что не соответствует стойкости минимального размера ключа. Поэтому спецификация лишь запрещает короткие ключи и настоятельно не рекомендует хеш-функции с коротким выходом.

Семантика ключа и кастомизации

Изменение ключа или использование result_with_customizer с другими значениями кастомизации даёт разные выходные хеши. Для заданного в примере ключа KEY при digestmod='sha256' получены конкретные значения: для hasher.add(b'Test 0') и hasher.add(b'Test 1') — 9a24e4209dad98d2e1f1eecd62aa2908234f1eed2963395292fd9718129fe258; для hasher.add(b'Test 0Test 1') — 4e4b71b8bb7b2c80e9f9ca89cb8bff43cd77cc5b530fc5f163069e5dda2876cb; для hasher.add(b'Test 0'), hasher.add(b''), hasher.add(b'Test 1') — 6faf7818842f5a208dc306afe83ed7bea5b3fadc2a617c2208e836709f925889.

Почему длина ключа кодируется в заголовке

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

Кроме того, хвостовые нули в ключе SequenceMAC семантически значимы, что предотвращает расширение ключа. В HMAC, напротив, ключ 0xff совпадает с 0xff00 и с 0xff000000000000000000000000000000, поскольку добавление нулей не меняет ключ. Кодирование длины в заголовке не даёт представить две версии «одного» ключа в разных контекстах и тем самым блокирует атаки подмены ключа.

Пограничные случаи и ограничения

Ограничение на длину входных данных составляет 2¹²⁸−1 байт. Для ключей в варианте SequenceMAC также допускаются ключи длиной до 2¹²⁸−1 байт. Ограничение на общее количество элементов не указано отдельно; вместо этого каждый вход кодируется с указанием длины, что гарантирует, что последовательные вызовы с Test 0 и Test 1 не эквивалентны одному вызову с Test 0Test 1.

Реализацию необходимо проверять на тестовых векторах. Тестовые векторы предоставляются для того, чтобы можно было написать собственную реализацию. Среди приведённых шестнадцатеричных значений, например, 9a24e4209dad98d2e1f1eecd62aa2908234f1eed2963395292fd9718129fe258, 4e4b71b8bb7b2c80e9f9ca89cb8bff43cd77cc5b530fc5f163069e5dda2876cb, 6faf7818842f5a208dc306afe83ed7bea5b3fadc2a617c2208e836709f925889; 3e54b5cd60ef78773dcf14c5f65ed593726a981f2c80045db7fac03015cc07ad, 3c5b12ea6952714fed499796a743b103de97575fc938aab7d154cc6c605984a9, 706af798b32b12c9f508c16c3411b594227f79936a3cc521e6e1f362b1ef3a38; 6eea7264b266d35bd5e483ef042189d2cebe51f9e8b764b90b0f9c82185de7ca, 1469d91e90c1d9c6189f576822e900f5cc8c3cdbd2ec51256df649d37c1688f7, 1800a2188e126c79dac8f7cf7e38a66e3f797654c15a5e49248a94d4e99bcaae.

Почему сделано именно так

128-битное кодирование длины выбрано ради простоты реализации на 32- и 64-битных системах, поскольку дополнение нулями легко выполняется. Лимит в 2¹²⁸−1 байт превышает все практические соображения на обозримое будущее и даже превышает заданные ограничения на вход SHA256 (2⁶¹ байт) и SHA512 (2¹²⁵ байт). Если вы приближаетесь к пределам SequenceHash, вы уже вышли за пределы SHA256 и SHA512.

Байтовые счётчики выбраны для простоты, так как почти всё хеширование сегодня выполняется над строками из 8-, 16-, 32- или 64-битных значений, а системы с небайтовыми строками очень редки — предполагается, что их реализаторы сами обеспечат байтовое дополнение.

SequenceHash не привязан к конкретной хеш-функции и доступен там, где Keccak нет. TupleHash, напротив, определён только для работы с Keccak, и при замене Keccak на другую хеш-функцию некоторые важные свойства безопасности, например устойчивость к length-extension, могут исчезнуть. Кроме того, SequenceHash использует двойное хеширование, как и HMAC, что предотвращает атаки length extension и позволяет поддерживать ключевой вариант SequenceMAC.

Что из этого следует на практике

Обычный update() не различает границы фрагментов: если вы хешируете коллекцию значений или строите обязательство, конкатенация даст неоднозначный результат, который можно открыть несколькими способами.
SequenceHash кодирует длину каждого входа в 128-битное целое перед подачей в базовую хеш-функцию, поэтому разные разбиения одной и той же последовательности байт дают несвязанные хеши.
Конструкция хеш-агностична: её можно применять с SHA2, BLAKE, RIPEMD и другими, тогда как TupleHash требует Keccak.
Двойное хеширование защищает от атак удлинения длины, а строки кастомизации привязывают значение к шагу или экземпляру протокола и включаются только во внешний слой, что позволяет переиспользовать внутренний хеш.
SequenceMAC требует ключ не менее 32 байт; длина ключа кодируется в заголовке, поэтому хвостовые нули семантически значимы, а подмена ключа его хешем невозможна.
Увеличение длины ключа свыше 32 байт не повышает безопасность: предел задают хеш-функция и этап предобработки ключа.
Собственную реализацию нужно сверять с тестовыми векторами, которые включают промежуточные значения для отладки.