ed25519 signature verification host function admits weak keys / malleable signatures

[graydon]

We probably want to have the soroban host function for ed25519 signature verification call Dalek's verify_strict rather than just verify, right? Currently it calls verify but I don't think we're currently committed to that anywhere. Are we?

See: https://github.com/dalek-cryptography/ed25519-dalek#weak-key-forgery-and-verify_strict

cc @C0x41lch0x41 and @MonsieurNicolas and @tomerweller for comments & constraints please!

[C0x41lch0x41]

Thanks for opening this issue. I agree that sounds like what we should do to mitigate risks and enforce strict validation criteria.
Looking at the code it does not sound that verify_strict would take a lot more resources than verify so I don't see any downside to that approach.

[kwantam]

👍 verify_strict is the right way to go, assuming that there is no requirement to accept every signature that RFC8032 considers valid.

Honest signers should produce signatures that verify_strict accepts, but it is possible that there are (buggy but RFC-compliant) signer implementations in the wild that do not. This probably isn't an issue most of the time, but it could be in the case that someone is forced to use a signer implementation that for whatever reason doesn't satisfy verify_strict.

My guess is that the most likely issue would be with something like an HSM, where the signing algorithm can't easily be changed. So it might be worthwhile to do a quick survey of hardware signing implementations---certainly worth checking YubiKeys, Ledgers, and other super common hardware.

---

Slightly more detail on the potential issue: the edwards25519 elliptic curve has 8*q points, where q is some 253-bit prime. This means there's a subgroup of order q (which is where we really want to run all of our cryptographic operations) plus a set of 8 points {P0, P1, ..., P7} such that P0 is the identity point, and P0 == 8*P0 == 8*P1 == 8*P2 == ... == 8*P7 (we say that all of these points have order 2, 4, or 8, but don't worry if this is meaningless jargon), and the set of 8*q points is the cartesian product of {P0, P1, ..., P7} with the elements of the subgroup of order q.

For a signature (R, S) on message M under public key A, RFC8032 defines Ed25519 verification as (essentially):

let k := Hash(ctx || R || A || Hash(M))  // 'ctx' is some fixed public string
if 8*S*B == 8*R + 8*k*A:                 // 'B' is a fixed public point
    return True
return False

This check effectively ignores any element of the set {P0, P1, ..., P7} added to R or A. To see why:

let A' := A + P3
=> 8*A' == 8*(A + P3)
=>      == 8*A + 8*P3
=>      == 8*A + P0  // P0 is the identity point
=>      == 8*A

This means I can take a signature (R, S) under public key A and produce a different-looking signature (R*, S) under public key A*, simply by adding elements of {P0, P1, ..., P7} to R and/or A. Many systems mistakenly rely on the assumption that this kind of thing is not possible, and this has led to subtle and very nasty security breaks in the past.

In contrast, verify_strict checks S*B == R + k*A (no multiplication by 8), which means that adding points from {P0, P1, ..., P7} to R and/or A doesn't work.

---

Aside: you might ask, wait, how is this a secure signature scheme if it is possible to maul signatures? The answer is that the standard definition of digital signature security does not consider it a security break if an attacker can produce a fresh signature on a message for which it has already seen a signature. A stronger definition of security does rule this out, but many signature schemes in the past were not designed with the stronger definition in mind. This is gradually changing...