Trail of Bits’ SequenceHash Turns Hash-Concatenation Bugs Into a Specification Problem
Trail of Bits released SequenceHash, a hash-agnostic way to hash several inputs without ambiguity. I rebuilt it from the spec, ran 4,992 test vectors, counted collisions across 54,241 sequences, and...
On October 2, Trail of Bits released SequenceHash and its keyed sister function SequenceMAC, a pair of constructions for hashing several byte strings together without letting the boundaries between them blur. The firm’s announcement calls the underlying problem “a common stumbling point when cryptographers try to use hashes.” The fix is not exotic: put a length next to every item and wrap the result in two hash calls, the way HMAC does. What is new is that the fix now exists as a written specification with test vectors, hosted by the Community Cryptography Specification Project (C2SP), plus Rust, Go, and Python implementations that, the announcement says, work with SHA-256, SHA-512, BLAKE2, and other hashes.
Table Of Content
- What Trail of Bits released
- The four features
- How the construction works
- The bug class: ambiguous encodings, and a real victim
- A real victim: tss-lib and the dollar sign
- Rebuilding SequenceHash from the specification
- Does it match the sources?
- The 4,992 test vectors
- What the encoding actually does
- The HMAC key quirk it also closes
- What it costs
- Where adoption could snag
- The API breaks the hashlib contract on purpose
- Packaging on day two
- What it does not fix
- What to do with it
- Sources and method
To see what that changes, I rebuilt SequenceHash from the specification in 47 lines of Python, ran it against the 4,992 published test vectors, and counted collisions across 54,241 short sequences under six different encodings. The result shapes the argument below. The encoding is what removes the ambiguity, and a plain length byte in front of every item did the same job in my test. What Trail of Bits adds is one agreed encoding, one set of vectors, and a set of extras around them. That moves the open questions from cryptography to specification and adoption: how the API behaves, what it costs, how it is packaged, and what it leaves for you to get right.
What Trail of Bits released
The announcement, written by Opal Wright, points to a specification at C2SP (version 1.0.0, with Wright and Scott Arciszewski listed as authors), test vectors in C2SP’s CCTV repository, and three initial implementations: Rust, Go, and Python. The specification calls SequenceHash “a TupleHash-like construction for unambiguously hashing sequences of bytestrings.”
TupleHash is the standard it is modeled on. NIST’s SP 800-185 describes it as “designed to simply hash a tuple of input strings, any or all of which may be empty strings, in an unambiguous way,” and Trail of Bits calls it “a great tool” when you can use it. The catch the post names is that TupleHash is “only defined to work with Keccak,” the function underneath SHA-3. That matters, it says, and is “especially true in the government contracting sector, where CNSA 2.0 has mandated SHA384 and SHA512 for nearly everything.” (NSA’s CNSA 2.0 document returned HTTP 403 to every fetcher I tried, so that reading of it is Trail of Bits’, not something I checked.) SequenceHash is hash-agnostic in the way HMAC is.
The four features
- Unambiguous input encoding. Every item has its length appended before it is hashed. Trail of Bits states the guarantee as: no other sequence of inputs, of any length, produces the same input to the underlying hash. Empty items count, because “Note that empty bytestrings are NOT ignored. They are encoded as having length zero.”
- Length-extension prevention. The specification says “SequenceHash outputs are not subject to length-extension attacks, even when an underlying hash function is.” The announcement credits the HMAC-style double hash described below. I did not attack this property; I report it as the specification states it.
- Built-in customization strings. A domain-separation string goes into the outer hash only, so the inner hash can be reused when the same data is hashed for several purposes.
- A keyed mode. SequenceMAC takes keys of at least 32 bytes and commits to the key length, which closes some quirks in HMAC’s key handling (reproduced below).
How the construction works
Both functions are one general function with a different function indicator and key. The inner hash covers a key block, a header block, and every item followed by its 16-byte little-endian length. The outer hash covers a second key block, a second header block, a derived customization block, the item count, the output length, and the inner digest:
SequenceFunction(H, K, S, F; M1 ... Mn) =
H( K_O || HeaderO || S' || n || L ||
H( K_I || HeaderI || M1 || len(M1) || ... || Mn || len(Mn) ) )The key blocks are the key (or its hash, when it is longer than a block) padded to one hash block with its first byte XORed with 0x55 for the inner hash and 0xaa for the outer one, which the specification describes as “in a manner similar to HMAC key processing.” The customization string is processed the same way. The headers carry a label (SEQHSH_I or SEQHSH_O), the function indicator, and the key length, with the outer header adding the customization string’s length; n and L are 16-byte big-endian integers. The outer hash consumes only the finished inner digest, the HMAC-style structure the announcement credits for its length-extension protection.
The bug class: ambiguous encodings, and a real victim
Python’s hashlib is a good place to see the problem, because in the documentation’s words “Repeated calls are equivalent to a single call with the concatenation of all the arguments.” Feeding the same bytes in three different groupings therefore gives one digest. The groupings are the example Trail of Bits uses, rerun here, followed by the delimiter case discussed below:
# step1_ambiguity.py
import hashlib
def feed(parts):
h = hashlib.new("sha256")
for p in parts:
h.update(p)
return h.hexdigest()
groupings = [
[b"Test 0", b"Test 1", b"Test 2"],
[b"Test 0Test 1", b"Test 2"],
[b"Test 0", b"", b"Test 1Test 2"],
]
print("hashlib.sha256, update() called with three groupings of the same bytes")
for g in groupings:
print(" ", feed(g), [x.decode() for x in g])
print()
print("A delimiter join in the style of tss-lib: b'$'.join(parts)")
for g in ([b"a$", b"b"], [b"a", b"$b"]):
joined = b"$".join(g)
print(" ", [x.decode() for x in g], "->", joined.decode(), hashlib.sha256(joined).hexdigest()[:16])hashlib.sha256, update() called with three groupings of the same bytes
4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c ['Test 0', 'Test 1', 'Test 2']
4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c ['Test 0Test 1', 'Test 2']
4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c ['Test 0', '', 'Test 1Test 2']
A delimiter join in the style of tss-lib: b'$'.join(parts)
['a$', 'b'] -> a$$b 6af6151534adb8c1
['a', '$b'] -> a$$b 6af6151534adb8c1Nothing is wrong with SHA-256 here; the grouping simply never reaches the hash function. Whenever a protocol hashes several fields and those fields vary in length, an attacker who controls a field can shift a boundary and keep the digest. The announcement lists the improvisations the firm sees across open-source code and in its own audits: separator characters that can also appear in the inputs, base64 values joined with dollar signs, and “some hash inputs are length-encoded, but not all.” Its summary is that “nobody seems to have landed on a consistent, standard solution to this problem.”
A real victim: tss-lib and the dollar sign
Wright’s 2024 post “YOLO” is not a valid hash construction says of the separator pattern: “This is not a hypothetical issue, either: it has been used to break the security of widely used libraries.” The link goes to Verichains’ TSSHOCK research. According to Verichains, BNB Chain’s tss-lib, a widely used threshold-signature library, “uses an ambiguous encoding scheme”: it joined input values with a $ delimiter, so the byte-array tuples ["a$", "b"] and ["a", "$b"] could hash to the same value. The last lines of the output above reproduce that pair with SHA-256.
The history is the instructive part. Verichains says Kudelski Security reported the issue to Binance in a 2019 audit as “KS-BTL-F-09: SHA512_256 interface prone to collisions” and that the report rated it Low severity; that a September 2019 fix did not remove the root cause; and that Kudelski flagged the same collision again when it audited io.Finnet’s fork, which led to CVE-2022-47931. The National Vulnerability Database describes that record in one line, “IO FinNet tss-lib before 2.0.0 allows a collision of hash values,” and its own CVSS 3.1 score is 9.1 (a second source on the record scores it 6.5). In November 2022 Verichains turned the ambiguity into a key-extraction attack it called α-shuffle, one of three attacks in TSSHOCK. Its page classifies the issue as an “ambiguous encoding scheme” exploited “to recover private key, not hash collision,” and lists tss-lib’s ambiguity as fixed, based on patches from io.Finnet.
Our Merkle tree tutorial reproduces a cousin of this bug: two different leaf lists that produce the same root, fixed with the prefix bytes and tree shape of RFC 6962. The common thread is a hash input that does not record where one piece ends and the next begins.
Rebuilding SequenceHash from the specification
The specification is short enough to implement from. The setup below needs only a virtual environment, PyCryptodome (used as a TupleHash control in two steps), and Trail of Bits’ Python file for cross-checks. On Linux or macOS the interpreter is .venv/bin/python.
python -m venv .venv
.venv/Scripts/python -m pip install pycryptodome
curl -L -o sequencehash.py https://raw.githubusercontent.com/trailofbits/sequencehash-py/main/sequencehash.pyI wrote the code below from the specification text, using only hashlib. It is 74 lines, 47 of them code. The optional sizes argument only records how many bytes each hash call consumed; the cost section uses it.
# seqhash_ref.py
"""SequenceHash and SequenceMAC written from the C2SP specification (v1.0.0), using only hashlib."""
import hashlib
F_SEQMAC, F_SEQHSH = 1, 2
# Block size b in bytes (for SHA-3 it is the rate), copied from the spec's table
BLOCK = {"sha1": 64, "sha256": 64, "sha384": 128, "sha512": 128,
"sha3_256": 136, "sha3_384": 104, "sha3_512": 72,
"blake2b": 128, "blake2s": 64}
def msbf(n):
return n.to_bytes(16, "big") # OverflowError if n < 0 or n >= 2**128
def lsbf(n):
return n.to_bytes(16, "little")
def pad(x, b):
if len(x) == 0:
return bytes(b) # the empty string pads to a full block
if len(x) % b == 0:
return x
return x + bytes(b - len(x) % b)
def encode(x):
return x + lsbf(len(x)) # the length goes AFTER the item (a suffix)
def derive(i, name, b, tweak):
block = pad(i, b) if len(i) <= b else pad(hashlib.new(name, i).digest(), b)
return bytes([block[0] ^ tweak]) + block[1:]
def header_i(b, func, key):
return pad(b"SEQHSH_I" + msbf(func) + msbf(len(key)), b)
def header_o(b, func, custom, key):
return pad(b"SEQHSH_O" + msbf(func) + msbf(len(custom)) + msbf(len(key)), b)
def inner_digest(name, key, func, items, sizes=None):
b = BLOCK[name]
data = (derive(key, name, b, 0x55) + header_i(b, func, key)
+ b"".join(encode(m) for m in items))
if sizes is not None:
sizes["inner"] = len(data) # bytes the inner hash consumed
return hashlib.new(name, data).digest()
def sequence_function(name, key, custom, func, items, sizes=None):
b = BLOCK[name]
if func == F_SEQMAC and len(key) < 32:
raise ValueError("SequenceMAC keys must be at least 32 bytes")
out_len = hashlib.new(name).digest_size
outer = (derive(key, name, b, 0xAA) + header_o(b, func, custom, key)
+ derive(custom, name, b, 0x00)
+ msbf(len(items)) + msbf(out_len)
+ inner_digest(name, key, func, items, sizes))
if sizes is not None:
sizes["outer"] = len(outer) # bytes the outer hash consumed
return hashlib.new(name, outer).digest()
def sequence_hash(name, items, custom=b"", sizes=None):
return sequence_function(name, b"", custom, F_SEQHSH, items, sizes)
def sequence_mac(name, key, items, custom=b"", sizes=None):
return sequence_function(name, key, custom, F_SEQMAC, items, sizes)Two details are easy to get wrong. The length goes after each item as 16 little-endian bytes (lsbf), while the item count and output length in the outer hash are 16 big-endian bytes (msbf). And the key, customization string, and headers are each padded to a full hash block, with an empty string padding to a full block of zeros.
Now the same three groupings that collided under plain hashlib, hashed as sequences:
# step1b_same_inputs.py
from seqhash_ref import sequence_hash
groupings = [
[b"Test 0", b"Test 1", b"Test 2"],
[b"Test 0Test 1", b"Test 2"],
[b"Test 0", b"", b"Test 1Test 2"],
]
print("SequenceHash (SHA-256), the same three groupings")
for g in groupings:
print(" ", sequence_hash("sha256", g).hex(), [x.decode() for x in g])
print()
print("The tss-lib pair, hashed as sequences instead of joined")
first, second = [b"a$", b"b"], [b"a", b"$b"]
print(" ", sequence_hash("sha256", first).hex()[:16], "vs", sequence_hash("sha256", second).hex()[:16])SequenceHash (SHA-256), the same three groupings
6eea7264b266d35bd5e483ef042189d2cebe51f9e8b764b90b0f9c82185de7ca ['Test 0', 'Test 1', 'Test 2']
ba1ceb5fac99894d5ebc52b220977fb263fa1880295323bdd850426cfc23af3b ['Test 0Test 1', 'Test 2']
67903724b27852e51e7b5fb3e503e67eadbd29e531241917a3ad2171e5018568 ['Test 0', '', 'Test 1Test 2']
The tss-lib pair, hashed as sequences instead of joined
3e20ccb3b25efd3b vs e551b7367fec6bd4Does it match the sources?
The first check uses what the sources print. The specification’s support-function examples and its two worked examples (one SequenceHash, one SequenceMAC) all passed, as did all nine digests printed in Trail of Bits’ announcement, which also confirms I copied them correctly:
PASS Encode('AAA')
PASS Encode('')
PASS Encode('SEQUENCEHASH')
PASS Pad('', 64)
PASS Pad('JJJ', 64)
PASS Derive('', SHA-256, 0x00)
PASS Derive('W'*64, SHA-256, 0xff)
PASS Derive('W'*65, SHA-256, 0x5a)
PASS spec worked example: SequenceHash
PASS spec worked example: SequenceMAC
PASS blog: three separate items
PASS blog: one concatenated item
PASS blog: two items
PASS blog: customizer 'CUST 0'
PASS blog: customizer 'CUST 1'
PASS blog: customizer 'CUST 2'
PASS blog: SequenceMAC, items 'Test 0', 'Test 1'
PASS blog: SequenceMAC, one item 'Test 0Test 1'
PASS blog: SequenceMAC, 'Test 0', '', 'Test 1'
19 of 19 checks passedThe 4,992 test vectors
The second check is stronger. C2SP’s test vectors cover SequenceHash across seven hash functions and SequenceMAC across six, 384 vectors per file, and they include intermediate values: the inner hash and both header blocks. The script below runs every vector through my code and through Trail of Bits’ own Python file. Vectors flagged must_fail are ones a correct implementation has to refuse. All 768 of them turned out to be SequenceMAC vectors with keys shorter than 32 bytes, since that is the only condition my code refuses.
# step3_vectors.py
import json
import pathlib
import urllib.request
import warnings
import seqhash_ref as ref
import sequencehash as tob # Trail of Bits' own single-file Python implementation
warnings.simplefilter("ignore") # the library warns about SHA-1 and about key length != digest size
BASE = "https://raw.githubusercontent.com/C2SP/CCTV/main/sequencehash"
FILES = {
"hash": ["blake2b", "blake2s", "sha1", "sha256", "sha3_256", "sha3_512", "sha512"],
"mac": ["blake2b", "blake2s", "sha256", "sha3_256", "sha3_512", "sha512"],
}
cache = pathlib.Path("vectors")
cache.mkdir(exist_ok=True)
def load(kind, name):
path = cache / f"{kind}_{name}.json"
if not path.exists():
request = urllib.request.Request(f"{BASE}/{kind}/vectors_{name}.json",
headers={"User-Agent": "Mozilla/5.0"})
path.write_bytes(urllib.request.urlopen(request, timeout=60).read())
return json.loads(path.read_text())
def run_ref(v):
key, custom = bytes.fromhex(v["key"]), bytes.fromhex(v["customizer"])
items = [bytes.fromhex(x) for x in v["inputs"]]
return ref.sequence_function(v["hash_name"], key, custom, v["function_id"], items).hex()
def run_tob(v):
key, custom = bytes.fromhex(v["key"]), bytes.fromhex(v["customizer"])
if v["function_id"] == 2:
h = tob.SequenceHash.new(v["hash_name"])
else:
h = tob.SequenceMAC.new(key, digestmod=v["hash_name"])
for x in v["inputs"]:
h.add(bytes.fromhex(x))
return h.result_with_customizer(custom).hex()
def attempt(fn, v):
try:
return fn(v), None
except Exception as exc: # a rejected key, for example
return None, type(exc).__name__
def middle_fields_match(v):
b = ref.BLOCK[v["hash_name"]]
key, custom = bytes.fromhex(v["key"]), bytes.fromhex(v["customizer"])
items = [bytes.fromhex(x) for x in v["inputs"]]
inner = ref.inner_digest(v["hash_name"], key, v["function_id"], items).hex()
return (inner == v["inner_hash"]
and ref.header_i(b, v["function_id"], key).hex() == v["inner_header"]
and ref.header_o(b, v["function_id"], custom, key).hex() == v["outer_header"])
print(f"{'file':<16}{'vectors':>8}{'must fail':>10}{'must succeed':>13}{'mine ok':>9}{'tob ok':>8}{'intermediates':>14}")
grand = dict(total=0, must=0, mine=0, tob=0, mid=0)
for kind, names in FILES.items():
for name in names:
vectors = load(kind, name)
must = mine = theirs = mid = 0
for v in vectors:
got_ref, err_ref = attempt(run_ref, v)
got_tob, err_tob = attempt(run_tob, v)
if v["must_fail"]:
must += 1
mine += err_ref is not None # a correct implementation refuses these
theirs += err_tob is not None
else:
mine += got_ref == v["final_output"]
theirs += got_tob == v["final_output"]
mid += middle_fields_match(v)
print(f"{kind + '/' + name:<16}{len(vectors):>8}{must:>10}{len(vectors) - must:>13}{mine:>9}{theirs:>8}{mid:>14}")
for key_, val in (("total", len(vectors)), ("must", must), ("mine", mine), ("tob", theirs), ("mid", mid)):
grand[key_] += val
print(f"{'all files':<16}{grand['total']:>8}{grand['must']:>10}{grand['total'] - grand['must']:>13}{grand['mine']:>9}{grand['tob']:>8}{grand['mid']:>14}")file vectors must fail must succeed mine ok tob ok intermediates
hash/blake2b 384 0 384 384 384 384
hash/blake2s 384 0 384 384 384 384
hash/sha1 384 0 384 384 384 384
hash/sha256 384 0 384 384 384 384
hash/sha3_256 384 0 384 384 384 384
hash/sha3_512 384 0 384 384 384 384
hash/sha512 384 0 384 384 384 384
mac/blake2b 384 128 256 384 384 256
mac/blake2s 384 128 256 384 384 256
mac/sha256 384 128 256 384 384 256
mac/sha3_256 384 128 256 384 384 256
mac/sha3_512 384 128 256 384 384 256
mac/sha512 384 128 256 384 384 256
all files 4992 768 4224 4992 4992 4224Both implementations agree with all 4,992 vectors. They refuse the 768 that must fail, and for the other 4,224 they produce the published final output; mine also reproduces the published inner hash and both header blocks. The vectors came from commit 50a8ecf of the CCTV repository and the Python file from commit e64f202 of sequencehash-py. That is the property that matters for a specification: someone outside the project can implement it from the text and get the published values.
What the encoding actually does
The vectors show that the construction is implementable. They do not show why it matters, so the next script counts. It builds every item over a two-character alphabet, a and the tss-lib delimiter $, up to three characters long (15 items), then every sequence of up to four items (54,241 sequences), and asks how many distinct digests each scheme produces. Six schemes compete: plain concatenation; a $ join; a length on the first item only, as a stand-in for “some hash inputs are length-encoded, but not all”; one length byte before every item; NIST’s TupleHash128 through PyCryptodome; and SequenceHash with SHA-256.
# step4_universe.py
import hashlib
import itertools
from collections import Counter
from Crypto.Hash import TupleHash128 # pip install pycryptodome
from seqhash_ref import sequence_hash
# Every item is a string over two characters ('a' and the tss-lib delimiter '$'), 0 to 3 long.
# Every sequence holds 0 to 4 items. That is 15 items and 54,241 sequences.
items = ["".join(p) for n in range(4) for p in itertools.product("a$", repeat=n)]
sequences = [tuple(s.encode() for s in seq)
for n in range(5) for seq in itertools.product(items, repeat=n)]
print(f"{len(items)} distinct items, {len(sequences):,} distinct sequences")
def sha(data):
return hashlib.sha256(data).hexdigest()
def concat(seq):
return sha(b"".join(seq))
def delimiter(seq):
return sha(b"$".join(seq))
def first_item_length_only(seq): # a length on the first item, nothing on the rest
return sha((bytes([len(seq[0])]) + seq[0] if seq else b"") + b"".join(seq[1:]))
def length_before_every_item(seq): # one length byte before every item
return sha(b"".join(bytes([len(m)]) + m for m in seq))
def tuplehash(seq): # NIST SP 800-185 TupleHash128 through PyCryptodome
t = TupleHash128.new(digest_bytes=32)
for m in seq:
t.update(m)
return t.hexdigest()
def sequencehash(seq):
return sequence_hash("sha256", list(seq)).hex()
schemes = [
("concatenate the items", concat),
("join with '$' (tss-lib style)", delimiter),
("length on the first item only", first_item_length_only),
("one length byte before every item", length_before_every_item),
("TupleHash128 (NIST SP 800-185)", tuplehash),
("SequenceHash (SHA-256)", sequencehash),
]
def show(seq):
return "(" + ", ".join(repr(m.decode()) for m in seq) + ")"
print()
print(f"{'scheme':<36}{'distinct digests':>17}{'lost to collisions':>20}{'largest group':>15}")
for label, fn in schemes:
groups = {}
for seq in sequences:
groups.setdefault(fn(seq), []).append(seq)
lost = len(sequences) - len(groups)
biggest = max(groups.values(), key=len)
print(f"{label:<36}{len(groups):>17,}{lost:>20,}{len(biggest):>15}")
print()
print("One colliding pair from each scheme that has them")
for label, fn in schemes[:3]:
groups = {}
for seq in sequences:
groups.setdefault(fn(seq), []).append(seq)
pair = next(g for g in groups.values() if len(g) > 1 and all(len(s) > 1 for s in g[:2]))
print(f" {label}: {show(pair[0])} and {show(pair[1])}")
print()
print("Empty sequence versus one empty item")
for label, fn in schemes:
print(f" {label:<36}{'same digest' if fn(()) == fn((b'',)) else 'different digests'}")15 distinct items, 54,241 distinct sequences
scheme distinct digests lost to collisions largest group
concatenate the items 8,191 46,050 55
join with '$' (tss-lib style) 19,076 35,165 50
length on the first item only 15,346 38,895 15
one length byte before every item 54,241 0 1
TupleHash128 (NIST SP 800-185) 54,241 0 1
SequenceHash (SHA-256) 54,241 0 1
One colliding pair from each scheme that has them
concatenate the items: ('a', 'aaa') and ('aa', 'aa')
join with '$' (tss-lib style): ('', 'aa$') and ('$aa', '')
length on the first item only: ('', 'a') and ('', '', 'a')
Empty sequence versus one empty item
concatenate the items same digest
join with '$' (tss-lib style) same digest
length on the first item only different digests
one length byte before every item different digests
TupleHash128 (NIST SP 800-185) different digests
SequenceHash (SHA-256) different digestsRead the table as a lower bound on how ugly this gets, not as a realistic rate: a two-letter alphabet is built to collide, and real fields are more varied. The shape still holds. Plain concatenation maps 54,241 sequences onto 8,191 digests, which is exactly the number of strings of length 0 to 12 over two letters and so the most it can tell apart. That means 46,050 sequences, 84.9 percent, were “lost to collisions” in the table’s sense: an earlier sequence had already produced their digest. The largest group is 55 different sequences with a single digest. The $ join leaves 19,076 distinct digests (64.8 percent lost) and the first-item-only length leaves 15,346 (71.7 percent lost). The three schemes that encode every item’s length, including the one-byte version, lose none. The last block of the output shows the smallest case, which several designs miss: an empty sequence and a sequence holding one empty item hash identically under concatenation and the $ join, and differently everywhere else.
Our reading: this is the main finding. The unambiguous encoding removes the collisions. TupleHash does it with a length prefix measured in bits, SequenceHash with a length suffix measured in bytes, and a naive length byte does it for items this short (it would overflow at 256 bytes, which my tiny universe never reaches). The choice among them is therefore not about whether the collisions go away. It is about what comes with the encoding: a width that cannot overflow, the double hash, the item count and output length bound into the outer hash, customization strings, a keyed mode, a hash-agnostic specification, and test vectors.
The HMAC key quirk it also closes
HMAC has its own boundary problem, in the key. RFC 2104 says to “append zeros to the end of K to create a B byte string” when the key is shorter than the hash block, and that applications using keys longer than the block “will first hash the key using H and then use the resultant L byte string as the actual key to HMAC.” Two consequences follow: keys that differ only by trailing zero bytes are the same key, and a long key equals its own hash. Trail of Bits calls these key pseudocollisions. The script below reproduces both with Python’s hmac module and shows that SequenceMAC, whose headers commit to the key length, tells the keys apart.
# step5_hmac_keys.py
import hashlib
import hmac
from seqhash_ref import sequence_mac
msg = b"transfer 100 to account 42"
def hmac_sha256(key):
return hmac.new(key, msg, hashlib.sha256).hexdigest()[:16]
print("HMAC-SHA256 with keys that differ only by trailing zero bytes")
for label, key in (("0xff (1 byte)", b"\xff"),
("0xff00 (2 bytes)", b"\xff\x00"),
("0xff then 15 zero bytes (16 bytes)", b"\xff" + bytes(15))):
print(f" {label:<38}{hmac_sha256(key)}")
key32 = bytes(range(32))
print()
print("A 32-byte key and the same key plus one zero byte")
print(" HMAC-SHA256 :", hmac_sha256(key32), hmac_sha256(key32 + b"\x00"))
print(" SequenceMAC :", sequence_mac("sha256", key32, [msg]).hex()[:16],
sequence_mac("sha256", key32 + b"\x00", [msg]).hex()[:16])
long_key = bytes(range(100))
print()
print("A 100-byte key and the SHA-256 digest of that key (HMAC hashes keys longer than the 64-byte block)")
print(" HMAC-SHA256 :", hmac_sha256(long_key), hmac_sha256(hashlib.sha256(long_key).digest()))
print(" SequenceMAC :", sequence_mac("sha256", long_key, [msg]).hex()[:16],
sequence_mac("sha256", hashlib.sha256(long_key).digest(), [msg]).hex()[:16])
print()
try:
sequence_mac("sha256", b"\xff" * 16, [msg])
except ValueError as exc:
print("SequenceMAC with a 16-byte key ->", exc)HMAC-SHA256 with keys that differ only by trailing zero bytes
0xff (1 byte) 8616e3f1dcb99566
0xff00 (2 bytes) 8616e3f1dcb99566
0xff then 15 zero bytes (16 bytes) 8616e3f1dcb99566
A 32-byte key and the same key plus one zero byte
HMAC-SHA256 : 6a8436721bbe0c89 6a8436721bbe0c89
SequenceMAC : 7f3aba05884b70f1 b7f53995845cf03f
A 100-byte key and the SHA-256 digest of that key (HMAC hashes keys longer than the 64-byte block)
HMAC-SHA256 : 8609ae93874af395 8609ae93874af395
SequenceMAC : 1a4577e5273c8bad a253cea194867da1
SequenceMAC with a 16-byte key -> SequenceMAC keys must be at least 32 bytesThe 16-byte key in the last line is refused outright, because SequenceMAC’s minimum key length is 32 bytes, which both implementations enforced on all 768 must-fail vectors.
What it costs
SequenceHash pays for its safety in fixed overhead. Both the inner and outer hashes start with whole hash blocks of key and header material, so a SHA-256 computation over a short sequence takes several compression-function calls where plain concatenation takes one or two. The first table below counts them from the padding rule (the message, a 0x80 byte, and an 8-byte length, rounded up to 64-byte blocks). The second measures wall-clock time on this machine, Python 3.13.14 on Windows 11. The block counts are exact; the timings come from one machine on one afternoon.
SHA-256 compression-function calls (block counts follow from the padding rule)
input plain concat inner outer total ratio
empty sequence 1 3 5 8 8.00x
two 32-byte items 2 4 5 9 4.50x
eight 32-byte items 5 9 5 14 2.80x
one 1 MiB item 16385 16387 5 16392 1.00x
Wall-clock time per call on this machine (microseconds, best of 5 repeats)
input hashlib my sketch tob library TupleHash128
two 32-byte items 0.30 2.91 4.07 6.75
eight 32-byte items 0.37 3.51 5.09 12.26
one 1 MiB item 259.65 677.99 230.31 1530.55
Reusing the inner hash across customization strings
add() of 32 MiB 8.3 ms
1,000 result_with_customizer() calls 1.8 ms (1000 distinct digests)
1,000 full re-hashes would cost about 8268 msThe overhead is a constant, not a rate. For two 32-byte items SequenceHash needs 9 blocks against 2, which is 4.5 times as many; for eight items, 14 against 5; for a 1 MiB item the extra 7 blocks vanish into 16,385. Wall-clock time follows the same pattern with Python’s overhead added. Trail of Bits’ library took 4.1 to 4.3 microseconds for two 32-byte items against 0.30 to 0.34 microseconds for a bare hashlib call, a ratio between 12.7 and 13.6 across four runs. For eight items the ratio was 13.3 to 14.1, and at 1 MiB it was between 0.89 and 1.06. The gap beyond the 4.5 times block ratio is most likely the cost of running the construction in Python (object setup, copies, and several method calls); I did not profile it. The TupleHash128 column is not a construction-to-construction comparison, because it pits PyCryptodome’s Keccak against Python’s SHA-256, so it mostly measures the hash function.
The one place the design is cheap is the customization string. It goes only into the outer hash, so the specification notes that “the inner hash of a SequenceHash computation does not incorporate the customization string,” and the inner hash can be reused. That held in the library: after one add() of 32 MiB (8.3 milliseconds here), 1,000 calls to result_with_customizer() took 1.8 milliseconds and produced 1,000 distinct digests, where re-hashing the data each time would have cost about 8.3 seconds. (The last line of the table extrapolates 1,000 times the first measurement; it was not run.)
When is the cost not worth paying? When every field has a fixed width, concatenation cannot shift a boundary. An RFC 6962 Merkle node hashes a type byte followed by two fixed-width child hashes, as in the Merkle tutorial above, and the X25519 and ML-KEM key exchange tutorial concatenates two 32-byte secrets, where the hazard it demonstrates is order, not boundaries. SequenceHash earns its blocks where lengths vary and an attacker may choose them.
Where adoption could snag
The API breaks the hashlib contract on purpose
The Python README says the APIs “strive to be nearly drop-in replacements for the hashlib and hmac modules.” The factory shape is familiar (SequenceHash.new("sha256")), but the object is not a hashlib object. It has add(), result(), and result_with_customizer() where hashlib has update(), digest(), and hexdigest(). That is deliberate. The library’s October 1 commit message says it replaced update with add “to better reflect the atomicity of the operation,” and the announcement explains that “each time you write a value to a hashing object, it will be added to the hash as an independent, length-encoded object.” The specification’s implementation guidance states the trade plainly: “Matching streaming APIs can introduce compatibility problems when users rely on concatenation behavior.”
# step7_api_surface.py
import hashlib
import warnings
import sequencehash
warnings.simplefilter("ignore")
def public(obj):
return [n for n in dir(obj) if not n.startswith("_")]
print("hashlib.sha256() object:", public(hashlib.sha256()))
print("SequenceHash object :", public(sequencehash.SequenceHash.new("sha256")))
sh = sequencehash.SequenceHash.new("sha256")
print("has update/digest/hexdigest:", [hasattr(sh, n) for n in ("update", "digest", "hexdigest")])
print()
print("add() with several arguments versus add() on the concatenation")
one = sequencehash.SequenceHash.new("sha256")
one.add(b"ab", b"cd")
two = sequencehash.SequenceHash.new("sha256")
two.add(b"ab")
two.add(b"cd")
three = sequencehash.SequenceHash.new("sha256")
three.add(b"abcd")
print(" add(b'ab', b'cd') ", one.result().hex()[:16])
print(" add(b'ab'); add(b'cd') ", two.result().hex()[:16])
print(" add(b'abcd') ", three.result().hex()[:16])
print()
print("The SequenceMAC snippet from the repository README, run as printed")
readme_snippet = r"""
my_key = b'\x00' * 32
hasher = sequencehash.SequenceMAC.new(mykey, digestmod='sha512')
hasher.add(b'Test')
print(hasher.result().hex())
"""
try:
exec(readme_snippet, {"sequencehash": sequencehash})
except Exception as exc:
print(" ", type(exc).__name__ + ":", exc)hashlib.sha256() object: ['block_size', 'copy', 'digest', 'digest_size', 'hexdigest', 'name', 'update']
SequenceHash object : ['add', 'block_size', 'copy', 'digest_size', 'func_id', 'hash_func', 'inner_hash', 'inner_init', 'item_count', 'key_len', 'outer_hash', 'outer_init', 'reset', 'result', 'result_with_customizer']
has update/digest/hexdigest: [False, False, False]
add() with several arguments versus add() on the concatenation
add(b'ab', b'cd') db972883a869d94f
add(b'ab'); add(b'cd') db972883a869d94f
add(b'abcd') 12714159e45e2865
The SequenceMAC snippet from the repository README, run as printed
NameError: name 'mykey' is not definedThere are two practical consequences. Code that expects a hashlib-shaped object, such as a helper that calls .update() on whatever hash it is handed, cannot take a SequenceHash without an adapter. And each item has to be handed over whole: the post says suffix encoding “allows implementers to develop streaming APIs when they need to support hashing data with length that isn’t known ahead of time,” but the Python object has no method for feeding one item in pieces, so a large file has to be a single add() argument.
The README also has a small trap. Its SequenceMAC snippet assigns my_key and then passes mykey, so run as printed it raises a NameError, as the last lines of the output show. That is a documentation typo, not a flaw in the construction, but it is the sort of friction a new library has to clear.
Packaging on day two
The announcement says the implementations are “ready to use today.” This is what I found when I checked on October 3:
- Python: a single file,
sequencehash.py, with Apache 2.0 license text (GitHub’s license detector reports “NOASSERTION”). PyPI returns 404 forsequencehashandsequencehash-py, so installation is a file copy. Its last code commit is dated October 1, the day before the announcement. - Rust: the repository was created on October 2 with one commit, “Initial commit.”, holding a
Cargo.toml(packagesequencehash, version 0.1.0), asrcfolder, and a.gitignore. There was no license file or README, and crates.io returns 404 forsequencehash. - Go: a README, a license file, and
hash,mac, andinternalpackages, butgo.moddeclares the bare module pathsequencehashrather than a GitHub path. Its September 26 commit says it moved from a length prefix to a length suffix “to bring in compliance with 1.0.0 spec,” so digests from earlier snapshots of that code would differ from the final specification’s. - The Python and Go repositories’ GitHub descriptions still read “ElementMAC and ElementHash,” which appears to be the project’s earlier name.
None of this is a criticism of a two-day-old release. It defines what “ready to use” means today: copy a file, pin the commit, and run the vectors before trusting your build.
What it does not fix
The announcement is candid about limits. “It’s a tool, not a panacea,” it says, and “You still need to make sure you’re hashing the right inputs.” Being able to decode a value does not mean two programs encode it the same way, so a JSON object with reordered fields, or text in two character encodings, still hashes differently. In Fiat-Shamir transcripts the omission problem remains: you “still have to be careful about including all your inputs,” the post says, linking the paper Weak Fiat-Shamir Attacks on Modern Proof Systems (Wright is one of its four authors), whose abstract reports finding “36 weak F-S implementations affecting 12 different proof systems.” Ambiguous encoding and omitted inputs are different failures, and SequenceHash addresses only the first.
There are other limits. There is no extendable-output variant yet: “We haven’t specified SequenceXOF,” the post says, though it is “something we’re thinking about.” The specification says its guarantees “do not apply if the underlying hash functions are not secure,” and, for SequenceMAC, the post says the specification “strongly discourages the use of hash functions with short outputs.” I also found no mention in the announcement or the specification of a published security proof or an outside review of the construction. Version 1.0.0 is marked stable, but the strength of the design rests, as the specification itself says, on the underlying hash and on its resemblance to HMAC, not on a published analysis that I could find.
What to do with it
- Find the call sites. Search for hashes over several variable-length fields: separators, joins, a mix of prefixed and raw fields, string formatting before hashing. Those are where the collisions in the table come from.
- Prefer a vetted encoding over a new one. Trail of Bits’ own 2024 advice is to use TupleHash where Keccak is available, or to serialize with Protocol Buffers, CBOR, or BCS, which all produce unambiguous encodings. SequenceHash is for the case where you need SHA-2 or BLAKE and a fixed, documented encoding.
- Leave fixed-width fields alone. Concatenating two 32-byte values is safe; adding a type byte or a customization string is what keeps different uses apart.
- Pin and test. Pin the specification version and the implementation commit, and run the CCTV vectors in CI, because the repositories were still changing in the week before release.
- Treat customization strings as protocol design. The post says they exist to “bind hashed values to a particular step in the protocol,” which only helps if each step gets its own string.
Trail of Bits says SequenceHash helps cryptographers follow the Horton principle: “you are hashing what you mean, and meaning what you hash.” The code needed to do that is small, as the 47 lines above show. The slower work is the part the title names: getting one encoding specified, implemented in several languages, packaged, and adopted. By the evidence of day two, the specification and its vectors are ahead of the packaging.
Sources and method
I read the specification (the editor’s copy in the C2SP repository, commit 3bc97b2, checked against the stable page for every sentence quoted here), Trail of Bits’ announcement and its 2024 post, NIST SP 800-185, RFC 2104, Verichains’ TSSHOCK page, the NVD record for CVE-2022-47931, the Weak Fiat-Shamir abstract, and the three implementation repositories on October 3, 2026. The lab ran on Python 3.13.14 with PyCryptodome 3.23.0. I read the public method names and the add() docstring of Trail of Bits’ Python file before writing my version and did not copy its code. Measured numbers are from my runs; everything else is attributed to its source above.
No Comment! Be the first one.