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

[Anton Sokolov <[e-mail]>]

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