f312e2cafa
claim_verify.py made the key, order and range checks itself and left the equation to `cryptography`; http_verify.py had its own RFC 8032 implementation; and pack_verify.py called `cryptography` alone, which accepts a key of small order, a second spelling of a key, and an R of small order. All three, and the JWP and signer verifiers through claim_verify, now call claim-conformance/_ed25519.py, written from RFC 8032 with the standard library (as http_verify's was): canonical A of large order, S < L, R decoded and not of small order, and the cofactorless equation with R compared byte for byte. It reports a bad key apart from a bad signature, keeps http_verify's --mutate small-order-key and small-order-r, and checks itself against RFC 8032's first two vectors and the three forgeries. Every committed corpus verifies unchanged: no vector's expectation moves. The OER reference keeps its own rule (oer-receipts §5). Co-Authored-By: Claude Opus 5.5 <[email protected]>
182 lines
6.8 KiB
Python
182 lines
6.8 KiB
Python
"""Ed25519 verification as WAI verifies every signature (SPEC §7 *Signatures*), written
|
|
from RFC 8032's definitions with Python's integers and nothing beyond the standard
|
|
library: the one routine the Python verifiers of WAI's corpora share. It shares no code
|
|
with wai-rs (`wai::sig`).
|
|
|
|
The rule, in order:
|
|
|
|
1. the key A decodes, and is the one canonical encoding of its point: y < p, and x = 0
|
|
never carries the sign bit (RFC 8032 §5.1.3);
|
|
2. A is not of small order (its order divides 8): under such a key the equation can
|
|
hold for a signature made without any private key;
|
|
3. S < L (RFC 8032 §5.1.7);
|
|
4. R decodes, is not of small order, and [S]B = R + [k]A holds with [S]B - [k]A encoded
|
|
and compared with R byte for byte (the cofactorless equation), k = SHA-512(R || A ||
|
|
M) mod L over the bytes of R and A as given.
|
|
|
|
`verify` returns None when every step holds, "bad_key" when step 1 or 2 fails and
|
|
"bad_signature" otherwise, so a verifier names the two outcomes with its own reasons.
|
|
|
|
The OER/2 reference verifier does not use this: oer-receipts §5 settles its own rule,
|
|
which refuses the same keys and leaves R to RFC 8032.
|
|
"""
|
|
import hashlib
|
|
|
|
P = 2 ** 255 - 19
|
|
L = 2 ** 252 + 27742317777372353535851937790883648493
|
|
D = -121665 * pow(121666, P - 2, P) % P
|
|
_SQRT_M1 = pow(2, (P - 1) // 4, P)
|
|
|
|
# The checks a verifier's own self-test may leave out, by name, to show its corpus
|
|
# catches the defect; never left out otherwise.
|
|
SKIPPABLE = ("small-order-key", "small-order-r")
|
|
|
|
|
|
def _recover_x(y, sign):
|
|
if y >= P:
|
|
return None
|
|
x2 = (y * y - 1) * pow(D * y * y + 1, P - 2, P) % P
|
|
if x2 == 0:
|
|
return None if sign else 0
|
|
x = pow(x2, (P + 3) // 8, P)
|
|
if (x * x - x2) % P:
|
|
x = x * _SQRT_M1 % P
|
|
if (x * x - x2) % P:
|
|
return None
|
|
return P - x if (x & 1) != sign else x
|
|
|
|
|
|
def decode(b):
|
|
"""RFC 8032 §5.1.3: the point `b` encodes, in extended coordinates (X, Y, Z, T), or
|
|
None when it is not the canonical encoding of a point (y >= p, x = 0 with the sign
|
|
bit set, or no x)."""
|
|
if len(b) != 32:
|
|
return None
|
|
y = int.from_bytes(b, "little")
|
|
sign, y = y >> 255, y & ((1 << 255) - 1)
|
|
x = _recover_x(y, sign)
|
|
return None if x is None else (x, y, 1, x * y % P)
|
|
|
|
|
|
def _add(p, q):
|
|
"""Twisted Edwards addition (a = -1) in extended coordinates; complete on this curve."""
|
|
a = (p[1] - p[0]) * (q[1] - q[0]) % P
|
|
b = (p[1] + p[0]) * (q[1] + q[0]) % P
|
|
c = 2 * p[3] * q[3] * D % P
|
|
d = 2 * p[2] * q[2] % P
|
|
e, f, g, h = b - a, d - c, d + c, b + a
|
|
return (e * f % P, g * h % P, f * g % P, e * h % P)
|
|
|
|
|
|
def _neg(p):
|
|
return (P - p[0], p[1], p[2], P - p[3])
|
|
|
|
|
|
def _identity(p):
|
|
return p[0] % P == 0 and (p[1] - p[2]) % P == 0
|
|
|
|
|
|
def encode(p):
|
|
zi = pow(p[2], P - 2, P)
|
|
x, y = p[0] * zi % P, p[1] * zi % P
|
|
return (y | ((x & 1) << 255)).to_bytes(32, "little")
|
|
|
|
|
|
_BY = 4 * pow(5, P - 2, P) % P
|
|
B = (_recover_x(_BY, 0), _BY, 1, _recover_x(_BY, 0) * _BY % P)
|
|
IDENTITY = (0, 1, 1, 0)
|
|
|
|
|
|
def small_order(p):
|
|
"""Whether [8]p is the identity: p's order divides 8."""
|
|
for _ in range(3):
|
|
p = _add(p, p)
|
|
return _identity(p)
|
|
|
|
|
|
def strict_key(pk):
|
|
"""Steps 1 and 2: whether `pk` is the canonical encoding of a point of large order."""
|
|
a = decode(pk)
|
|
return a is not None and not small_order(a)
|
|
|
|
|
|
def _double_mul(s, p, k, q):
|
|
"""[s]p + [k]q, one doubling per bit (Shamir's trick)."""
|
|
pq = _add(p, q)
|
|
acc = IDENTITY
|
|
for i in range(max(s.bit_length(), k.bit_length()) - 1, -1, -1):
|
|
acc = _add(acc, acc)
|
|
bs, bk = (s >> i) & 1, (k >> i) & 1
|
|
if bs and bk:
|
|
acc = _add(acc, pq)
|
|
elif bs:
|
|
acc = _add(acc, p)
|
|
elif bk:
|
|
acc = _add(acc, q)
|
|
return acc
|
|
|
|
|
|
def verify(pk, msg, sig, skip=()):
|
|
"""The whole rule over `msg`: None when every step holds, else "bad_key" (steps 1
|
|
and 2) or "bad_signature" (steps 3 and 4). `skip` names checks of SKIPPABLE to leave
|
|
out, for a verifier's self-test only."""
|
|
if len(pk) != 32:
|
|
return "bad_key"
|
|
a = decode(pk)
|
|
if a is None or (small_order(a) and "small-order-key" not in skip):
|
|
return "bad_key"
|
|
if len(sig) != 64:
|
|
return "bad_signature"
|
|
s = int.from_bytes(sig[32:], "little")
|
|
if s >= L:
|
|
return "bad_signature"
|
|
r = decode(sig[:32])
|
|
if r is None or (small_order(r) and "small-order-r" not in skip):
|
|
return "bad_signature"
|
|
k = int.from_bytes(hashlib.sha512(sig[:32] + pk + msg).digest(), "little") % L
|
|
if encode(_double_mul(s, B, k, _neg(a))) != sig[:32]:
|
|
return "bad_signature"
|
|
return None
|
|
|
|
|
|
def verifies(pk, msg, sig, skip=()):
|
|
return verify(pk, msg, sig, skip) is None
|
|
|
|
|
|
def _self_test():
|
|
"""RFC 8032 §7.1 TEST 1 and TEST 2, and the three signatures a lenient verifier
|
|
accepts and this rule refuses; a list of the checks that fail."""
|
|
fails = []
|
|
t1_pk = bytes.fromhex("d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a")
|
|
t1_sig = bytes.fromhex("e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e06522490155"
|
|
"5fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b")
|
|
t2_pk = bytes.fromhex("3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c")
|
|
t2_sig = bytes.fromhex("92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da"
|
|
"085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00")
|
|
if verify(t1_pk, b"", t1_sig) is not None or verify(t2_pk, b"\x72", t2_sig) is not None:
|
|
fails.append("rfc8032-vectors")
|
|
if verify(t2_pk, b"\x73", t2_sig) != "bad_signature":
|
|
fails.append("rfc8032-wrong-message")
|
|
one = (1).to_bytes(32, "little")
|
|
b_enc = encode(B)
|
|
long_identity = (P + 1).to_bytes(32, "little")
|
|
forged = b_enc + one # (R, S) = (B, 1): [1]B = B + [k]O under the identity
|
|
if verify(one, b"any", forged) != "bad_key" or verify(long_identity, b"any", forged) != "bad_key":
|
|
fails.append("identity-key")
|
|
if verify(one, b"any", forged, skip=("small-order-key",)) is not None:
|
|
fails.append("identity-key-is-a-forgery")
|
|
k = int.from_bytes(hashlib.sha512(one + b_enc + b"m").digest(), "little") % L
|
|
r_small = one + k.to_bytes(32, "little") # under B (scalar 1): [k]B = O + [k]B
|
|
if verify(b_enc, b"m", r_small) != "bad_signature" or verify(b_enc, b"m", r_small, skip=("small-order-r",)) is not None:
|
|
fails.append("small-order-r")
|
|
s_plus_l = t1_sig[:32] + (int.from_bytes(t1_sig[32:], "little") + L).to_bytes(32, "little")
|
|
if verify(t1_pk, b"", s_plus_l) != "bad_signature":
|
|
fails.append("s-not-reduced")
|
|
return fails
|
|
|
|
|
|
if __name__ == "__main__":
|
|
import sys
|
|
f = _self_test()
|
|
print(("PASS" if not f else "FAIL") + " Ed25519 strict rule self-test " + ",".join(f))
|
|
sys.exit(1 if f else 0)
|