[SCITT] Re: Signed Statement identity when the ECDSA signature is not byte-unique

[Joel Hillier <[e-mail]>]

Anton, Henri,

Third codebase, and Henri's rule paid twice. The second time is the part worth reading, because the first repair was wrong in a way that would have shipped.

First pass. I ran the substitution against ARP's ledger constructions rather than against a receipt identifier: ES256 over P-256, 200 random keys, an ARP-shaped Settlement-Layer Ledger entry. 200 of 200 verifying twins, 200 of 200 changed the entry bytes. Three constructions were taken over signature-bearing preimages -- the Prior-Entry Hash, which chains the ledger; a Post-Seal Evaluation Record Hash defined "in its entirety, signature included"; and a Merkle leaf over a register-signed attestation. The Self-Entry Hash beside the first of those already nulled the signature position and was fine. Both rules in one bulleted list, two paragraphs apart, each defensible on its own reading. I would not have looked without Henri's sentence.

Second pass, and the reason I am writing rather than just agreeing. I had a red team attack the repair on the assumption it was wrong, and it was: **a fourth digest defeated the fix at one remove.** ARP's Reconciliation Hash is defined as excluding the *Sealing* Signature, and I had asserted on that basis, in the new security section, that it was already outside the signature and unchanged. It is not. A Reconciliation Output embeds the register's signed Partial Attestation in every Query Binding Record and the register's signature in every Non-Answer Statement, so the preimage still carried a signature after the sealing one was removed. Measured: stable in 0 of 200.

And the Reconciliation Hash is a field of every ledger entry. So it sits inside the Entry Signature payload, and therefore inside the very Prior-Entry Hash I had just fixed. Repairing the chain link while leaving a malleable digest inside the thing it commits to buys nothing at all.

Two more of the same class turned up in the same sweep: an authority-reference digest in an appendix, taken as SHA-256 over a COSE_Sign1 transparency receipt, and -- separately -- the fix's own consequences left un-updated in four places, including a paragraph still asserting "so that Entry Signatures are inside the chain" two paragraphs below the bullet that had just taken them out.

So: five constructions, not three. Four are now Signing Input Digests over the COSE Sig_structure; the Reconciliation Hash takes a different repair, replacing each embedded register signature with that signature's Signing Input Digest rather than becoming one itself.

The other thing the red team found is worse and I would rather say it than have it inferred. **My first probe's "-04" leg computed sha256(X) == sha256(X).** It rebuilt the Sig_structure from the same local it had signed, so the substitution never reached the value under test, and two further rows were printed from hardcoded literals. It reported 200 of 200 for measurements that were never taken -- including the Reconciliation Hash row that turns out to be false. The probe now recovers every reported value by parsing the two served envelopes, so a leg that does not apply the substitution cannot report stability. Same numbers where they were right, and 0 of 200 where they were not.

Henri, your instruction generalises further than a second identity rule in the same tree. It is also a second copy of the *evidence*: a measurement whose harness reuses the value it is supposed to be perturbing reports the property it was written to demonstrate. Both failures are the same shape.

On the mechanism. Your seam is the one I drew, and ARP's version is cheaper than SCITT's for a reason worth naming: ARP's protected header carries the key identifier and the algorithm identifier, and the Sig_structure covers the protected header. So the digest keeps every commitment the specification depended on and drops only the bytes that were never unique. Except that nothing in the document actually *required* alg and kid to be in a protected header rather than an unprotected one, which the Sig_structure does not cover -- so the argument was resting on a convention. It is a requirement now. The external_aad was likewise named in the definition and defined nowhere; it is fixed at the zero-length byte string, since a signing input digest a third party cannot reproduce is not an identifier.

Your "total where canonicalising is partial" is what settles the choice, and it holds: low-S removes one encoding from a set with more than one member, and the signing input has one value per signing act however many encodings exist.

Two corrections to my own citations, since this thread is careful about them. I had written that SEC1 v2.0 Section 4.1.3 permits the substitution in terms; I cannot support that from the text and have dropped it. Section 4.1.4 of SEC1 and Section 6.4.2 of FIPS 186-5 range-check r and s only, and RFC 9053 Section 2.1 constrains neither, so the substitution falls outside every check any of the three imposes -- which is the claim that is actually supportable. And RFC 8032 Section 8.4 gives non-malleability, not uniqueness of encoding; Section 5.1.7 leaves cofactored verification optional, so I have stopped saying an Ed25519 signature "has one valid encoding" and said what the section actually says.

Two things the change costs, stated in the document rather than discovered later. Stripping a historical Entry Signature while leaving its protected header and payload intact now moves no Prior-Entry Hash, and neither does re-signing an entry under the same key and header. A re-signature under a *different* key or algorithm still moves the chain. ARP's "an entry is signed exactly once" rule consequently has no verifier-side test any more and is now stated as an operator obligation an auditor can examine and a reader cannot. That is a real loss and it is the price of the digest being stable; I would rather a rule that is unenforceable against an honest reader than a chain that breaks for one.

It also collided with a rule added the day before on Nenad Vasic's finding, requiring a verifier to recompute a Merkle leaf from the object rather than trust the leaf a proof carries. That rule is right. Over a signed envelope it converted a substituted signature from a silent difference into a refused valid proof. Two correct-looking decisions, one made this week, and the failure existed only where they met.

Both failures are of verification rather than of authenticity, and that is what I would put in front of other implementers alongside your correction to the hardening note. A deployment reporting either as detected tampering is reporting something that did not happen.

One last thing for anyone checking their own tree. ARP's reference endpoint signs with Ed25519 and was never exposed. ARP does not require Ed25519 -- a Bilateral Register Agreement declares the supported primitives and nothing forbade an ECDSA one. "Our implementation is fine" and "the specification is fine" are different claims, and only the first was true.

Anton -- yes to the two 395-byte files. I will run them through ARP's ledger verifier and report what it does, including if it does the wrong thing.

The probe is conformance/runners/ecdsa_malleability_probe.py in github.com/Certisyn-Inc/scitt-arp-f39, no arguments, standard library plus cryptography. It measures the old and new constructions side by side and derives every value from served bytes.

On the SCRAPI point: I would resolve it rather than leave it, for a reason specific to where that document is. ARP makes a normative reference to draft-ietf-scitt-scrapi and its Note to the RFC Editor asks that ARP not publish before it. If "the same registered Signed Statement" is byte-wise, a third party can mint extra entries for one act, and any document binding to SCRAPI's registration inherits that. I would rather cite a definition than a sentence with two readings, and I am happy to say so on the record if it helps the chairs weigh it.

Joel
________________________________
From: Anton Sokolov <[e-mail]>
Sent: Tuesday, 18 August 2026 12:15:46
To: [e-mail] <[e-mail]>
Subject: [SCITT] Signed Statement identity when the ECDSA signature is not byte-unique

Hi all,

Reproduction first. Any P-256 key, OpenSSL only, about ten seconds:

openssl ecparam -genkey -name prime256v1 -noout -out k.pem
openssl ec -in k.pem -pubout -out pub.pem
printf 'one act' > msg
openssl dgst -sha256 -sign k.pem -out a.der msg

N=FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
R=$(openssl asn1parse -inform DER -in a.der | sed -n '2s/.*INTEGER *://p')
S=$(openssl asn1parse -inform DER -in a.der | sed -n '3s/.*INTEGER *://p')
S2=$(echo "obase=16; ibase=16; $N - $S" | bc | tr -d '\\\n')
i(){ v=$(echo "$1" | sed 's/^\(00\)*//'); [ $((${#v} % 2)) = 1 ] && v="0$v"
case ${v:0:1} in [89A-Fa-f]) v="00$v";; esac
printf '02%02x%s' $((${#v}/2)) "$v"; }
B=$(i "$R")$(i "$S2"); printf '30%02x%s' $((${#B}/2)) "$B" | xxd -r -p > b.der

openssl dgst -sha256 -verify pub.pem -signature a.der msg
openssl dgst -sha256 -verify pub.pem -signature b.der msg
sha256sum a.der b.der

Both print "Verified OK". The two files have different SHA-256. I ran this over
200 random keys: 200/200.

No specification is violated. SEC1 v2.0 4.1.3 permits the substitution verbatim
-- "The signer may replace (r, s) with (r, -s mod n), because this is an
equivalent signature" -- and FIPS 186-5 6.4.2 and SEC1 4.1.4 range-check r and s
only. RFC 9053 2.1 enumerates the ES256 key checks and none constrain s. So this
is a profile question for SCITT, not a defect in ECDSA, in COSE, or in anyone's
library. It started with a shipping secure element emitting a high-s signature;
that device is conformant, and I mention it only to show high-s is not a lab
curiosity.

The mechanism is old and I am not claiming it. Bitcoin addressed it in BIP-62 and
BIP-146, and RFC 8032 8.4 says "Ed25519 and Ed448 signatures are not malleable due
to the verification check that decoded S is smaller than l". Closer to home,
action-state-group/scitt-cose already documents it in its hardening notes (finding
L2): "a COSE_Sign1's 64-byte signature is not byte-unique. Anyone keying
idempotency/dedup on the signature bytes ... must account for this."

What I do not think is on the record is the consequence for entry identity, plus
one correction to that same note, whose closing sentence reads: "The leaf digest --
what the transparency log commits to -- is over the full statement bytes and is
unaffected in practice for the canonical signer." Being over the full statement
bytes is precisely what makes it affected: those bytes include the signature.
Keying an entry on SHA-256(COSE_Sign1) yields two entries for one signing act;
keying on SHA-256(Sig_structure) yields one. I measured that with an instrumented
log.

And not only with software keys. A commodity secure element -- an ECDSA P-256 key
generated on-die in a PIV slot, non-extractable, with a touch policy the device
attests, so every signature required a physical touch -- produced a COSE_Sign1
whose signature is high-S. Its malleated twin verifies too:

sha256(original) = 87044ba351d8ce4aff9b3bd6c4b1a254a67b88cb43360acf2f42e66ae42b6d89
sha256(twin) = d374e5d49a5d68364cc2b1d0611e537c9477c29efcf3839e592c642e2cb81f09

One act, one hardware-held key, one human touch, two valid receipts with different
identifiers. Both files are 395 bytes and I will send them to anyone who wants
them. That device is conformant and I am not reporting a vulnerability in it --
which is the point: nothing anywhere is misbehaving.

This is not the duplicate-registration case the WG has already settled (Lasker,
Jul 2024; also PR #351). The difference is who can produce the second entry: here
it is produced by someone who does not hold the signing key, from the first, in
transit -- and a relying party cannot tell that entry apart from an
issuer-intended re-registration. Nothing is forged and no authority is bypassed;
the signer's authority is identical in both copies. It is about the arithmetic of
counting.

The first reply to this is "mandate low-S", so: measured, not argued. Ten
signatures over one Sig_structure with random k, each normalised to low-S, give
ten distinct SHA-256(COSE_Sign1) and one distinct SHA-256(Sig_structure). Low-S
removes one byte-string per act out of many. RFC 6979 does not close it either --
RFC 9053 2.1 already SHOULDs deterministic ECDSA, but determinism constrains an
honest signer's choice of k; it does not shrink the set of byte-strings that
verify, and the twin above verifies against a deterministic signature exactly as
well. A Transparency Service can observe neither property. For what it is worth,
the secure element above does not do deterministic ECDSA: five signatures over one
byte-identical structure gave five distinct r values.

The proposal, one sentence: derive the entry identifier from the Sig_structure
rather than from the enveloped bytes -- noting honestly that this is total where
canonicalising the signature is not, because the Sig_structure excludes the
signature by construction whereas a low-S rule only removes the cheapest of
infinitely many valid encodings.

The part that needs care: a Sig_structure-keyed identifier deliberately collapses
two registrations of the same act, which is a distinction the WG wanted to keep. I
would argue that is the right place for the seam -- identity of the act from the
signed bytes, identity of the registration event from an explicit registration
component, which is what at least one implementer already does (robinbryce in
issue #321: H(DOMAIN-SEPARATOR || EXTRABYTES || IDTIMESTAMP || SERIALIZEDBYTES)) --
rather than inheriting it from whatever entropy the signature happened to carry.
draft-ietf-scitt-architecture PR #145 documented the reverse direction of this
trade in an appendix that was dropped in -11.

Where it touches the documents, for what that is worth given where they are: RFC
9943 6.3 requires the unprotected header to be set to an empty map before a Signed
Statement enters a Statement Sequence -- it pins one malleable field, and the
signature is the other one. And draft-ietf-scitt-scrapi-11 2.3.1 requires a service
to "return the same Location URL for the same registered Signed Statement" without
defining "the same" byte-wise; EntryID appears four times (twice more as "entry ID"
in example errors) and is defined neither in 1.2's imported terms nor in RFC 9943.
If "the same" is meant byte-identical, the consequence is just that a third party
can mint extra entries for one act -- worth resolving either way.

I am not asking for SCRAPI to be pulled out of the RFC Editor queue. I am flagging
this for a future -bis and for implementers reading it now, and I will carry the
measurement in draft-mih-sokolov-scitt-payload-binding. Happy to open a tracker
issue instead if the chairs prefer, and happy to post the full measurement (eleven
verification paths over four verifier cores, with negative controls) if it is
useful.

Anton Sokolov
Tyche Institute, Tallinn