It's possible to forge messages that crypto_sign_open verifies if the public key is zero.

[orlp]

If the public key is zero, the signature is zero and the message is a randomly generated public key there is a chance the message will verify.

Example code: https://gist.github.com/nightcracker/8597602

I think the solution is simple, and that is to check for a zero public key. That's never a valid public key anyway, and I don't think this attack generalizes outside of zero public keys.

[sneves]

You've hit a point of order 4 on the curve. In twisted Edwards curves (0, -1) is a point of order 2, and (..., 0) is a point of order 4 when a is a square (it is here). Public keys are represented as their y coordinate plus a sign bit.

[orlp]

@sneves Is my thought that this attack never generalizes beyond the all-zero public key correct, or must we check for more things? I'm also going to have to fix this in my ed25519 repository.

P.S.: I forgot to note that this attack was not discovered by me, but I was notified of it by Mikkel Fahnøe Jørgensen.

[sneves]

EdDSA's signature verification checks that a signature (R,s) is valid if sB = R + H(m,..) A, where A = aB is the public key.

When you make s = 0 and R and A points of order 4, the equation becomes O = R + H(m,..) A => -R = H(m,...) A. Since R and A are both points of order 4, the chance of them being equal (up to sign) are high. R and A need not be (..., 0); the point (..., 2^255-20) should work better, even.

Try replacing zero_public_key and signed_message[0:32] with {0xEC, 0xFF, 0xFF, ..., 0xFF, 0x7F}.

[orlp]

@sneves That's bad news, or, well, it means my simple proposed solution is not sufficient. I'm rather unfamiliar with the inner details of elliptic curves, what solution would you propose?

[sneves]

I suppose one way is to blacklist all points of order 2, 4, and 8. Another is to multiply by 7237005577332262213973186563042994240857116359379907606001950938285454250989 and check that the result is the point at infinity. I suggest you ask the NaCl/EdDSA authors.

[orlp]

@sneves djb was notified by this at the same time as I got notified, a while back by Mikkel Fahnøe Jørgensen. AFAIK he did not reply (he is probably very busy).

I don't feel competent with elliptic curve cryptography enough to write a patch for this, could you whip something up?

[sneves]

It's unclear that this needs to be fixed. The above attack relies on conferring way too much powers to an attacker, namely that of choosing both the signature and the public key. With such powers, it's always possible to forge signatures by the obvious way: generate a public key from a known secret key, and generate signatures as normal. Under which circumstances does the above attack work and what I just described doesn't?

[CodesInChaos]

Originally I though that this should not count as an attack since for pretty much the same reasons @sneves listed:

You could consider this a "weak key" (probably all points with order <= 8 have similar issues). Being able to produce a message/signature pair under these "weak" public keys doesn't look very different from being able to produce message/signature pairs for any public key for which the attacker knows the private key.

A related argument in the Ed25519 paper:

Weak keys. Forgeries are trivial if A is a known multiple of B. For example,
an attacker who knows that A = 37B can choose r and compute S = (r +
37H(R,A,M)) mod ‘. As an even more extreme example, an attacker who knows
that A = 0B can choose r and compute S = r mod ‘, independently of M. We
could declare that 0B and 37B are “broken” by these two “attacks” and that
users must check for, and reject, these “weak keys”; but the same confused
logic would require rejecting all keys in all cryptosystems, and would have no
relevance to the standard definition of signature security.

Legitimate users choose A = aB, where a is a random secret; the derivation of
a from H(k) ensures adequate randomness. These users have negligible chance
of generating any particular multiple of B targeted by the attacker (and no
chance of generating 0B). The chance of the attacker randomly guessing a is
far smaller than the chance of the attacker computing a by known discrete-
logarithm algorithms; standard elliptic-curve security criteria are designed so
that the latter algorithms have negligible chance of succeeding in any reasonable
amount of time.

This also doesn't fall into one of transformation categories described in this paper:

Digital Signatures Do Not Guarantee Exclusive Ownership
T. Pornin, J. P. Stern, Applied Cryptography and Network Security - ACNS 2005, LNCS 3531, Springer-Verlag, 2005.

But there is one property one might expect of a signature scheme, which this does not fulfill:

The attacker chooses produces a public key and a signature. Normally this commits them to one particular message. But with these "weak public keys", an attacker can find many messages matching a fixed signature and fixed public key.

While I don't know any protocols/applications relying on this property, it doesn't seem far stretched that there are some. Similarly one usually doesn't require non malleability from a signature scheme, but some applications still rely on that (e.g. MtGox relied on bitcoin transactions being non malleable).

As a stronger property one could require that it's infeasible to find public keys A, A', messages m, m' which share the same signature s. This is pretty similar to the collision resistance we require of cryptographic hashes.

[orlp]

@CodesInChaos Surely you meant "Originally I thought that this should NOT count as an attack"?

[jedisct1]

Following the irtf-cfrg-eddsa draft, the 0<S<l test was reintroduced.

Even though the security implications of a small order R are unclear, points of order <= 8 are now rejected.