According to the paper “High-speed high-security signatures”…

Malleability. We also see no relevance of "malleability" to the standard definition of signature security.

Aside from the example, how is ed25519 malleable by the non-standard definition of signature security?

To be more specific:

I'd like to know about any malleability with signatures/keys. The example provided seems not to be a risk because the key must also change. If anything's been discovered since this paper, that would also be helpful. I'm concerned with ECDSA type malleabilities and wonder if there's anything “close”.

  • 1
    $\begingroup$ @DrLecter I suspect Gracchus wants to be sure EdDSA is not malleable, to avoid issues like the one that recently owned MtGox. $\endgroup$ – CodesInChaos Feb 27 '14 at 8:54
  • 1
    $\begingroup$ @CodesInChaos ok, I'am not so into the bitcoin world ;) But it seems that strong unforgeability (being able to produce two distinct signatures for the same message) is quite important in this setting? AFAIK, however, there is no known such vulnerability with EdDSA. $\endgroup$ – DrLecter Feb 27 '14 at 9:09
  • 2
    $\begingroup$ @DrLecter For bitcoin doesn't matter if the real signer can produce distinct signatures. They obviously can with all ElGamal derived signatures, like ECDSA, Schnorr or EdDSA. But it matters if an attacker who doesn't know the key can take a signed message and modify any part of it, including the signature. Some implementations (e.g. MtGox) falsely relied on attackers not being able to do that, but the reference implementation doesn't suffer for these issues. See Transaction Malleability on the bitcoin wiki for additional information. $\endgroup$ – CodesInChaos Feb 27 '14 at 9:44
  • 1
    $\begingroup$ @CodesInChaos I did not mean that the signer can produce different signatures. Strong unforgeability means that someone only having the public key can produce another signature for the same message given a message signature pair and thats what I meant ;) Yes, ElGamal type signatures are prone to this "malleabiltiy". Thx for the link to the bitcoin world ;) $\endgroup$ – DrLecter Feb 27 '14 at 9:48

Ed25519 in the default implementation is malleable.

  • It includes the public key $A$ in the hashed message, so it cannot be modified
  • It includes $R$ in the hashed message, so it cannot be modified
  • $S$ is encoded as a 256 bit. But since it's a scalar, $S^\prime = S + k \cdot l$ is equivalent to $S$ for any integral $k$ (where $l$ is the order of the subgroup, slightly larger than $2^{252}$).

    This means that $S$ is malleable if the implementation doesn't verify that $S < l$. I verified this malleability with the Ref10 implementation.

  • There could be equivalent values for $S$, even when verifying that $0 \leq S < l$. The paper says:

    Malleability. We also see no relevance of “malleability” to the standard definition of signature security. For example, if we slightly modified the system then replacing $S$ by $−S$ and replacing $A$ by $−A$ (a slight variant of the “attack” of [75]) would convert one valid signature into another valid signature of the same message under a new public key; but it would still not accomplish the attacker’s goal, namely to forge a signature on a new message under a target public key. One such modification would be to omit $\underline{A}$ from the hashing; another such modification would be to have $\underline{A}$ encode only |A|, rather than A.

    The way I understand this is that there are no such equivalent values.

  • $S$ malleability is implementation dependent. Other implementations or batch verification might have different properties.

  • 1
    $\begingroup$ Another attack: github.com/jedisct1/libsodium/issues/112 $\endgroup$ – orlp Feb 27 '14 at 12:33
  • 1
    $\begingroup$ @Gracchus I only checked one implementation (Ref10, the most popular one), which accepts $s \geq l$. I.e. with this implementation Ed25519 is malleable. I expect most other implementations to accept those signatures as well. => You can't rely on non malleability unless you add additional checks yourself. $\endgroup$ – CodesInChaos Feb 27 '14 at 15:31
  • 1
    $\begingroup$ @Gracchus What I listed is normal malleability. I assume you could run the same attack that hit MtGox by adding $l$ to $S$. If you want to use Ed25519 in a bitcoin like protocol, you certainly should add a $S<l$ check. Nightcracker's attack on the other hand is weirder, it certainly doesn't fit the common definition of malleability. I'm not even sure if we should classify it as an attack. (for details, see discussion on the github issue, I posted a longer comment overthere). $\endgroup$ – CodesInChaos Feb 27 '14 at 17:03
  • $\begingroup$ @Gracchus The expression $R < l - 1$ makes no sense. You can't compare group elements and scalars. Where in the paper is this? $\endgroup$ – CodesInChaos Feb 28 '14 at 8:43
  • $\begingroup$ @Gracchus There hasn't been a new version of SUPERCOP and most people wouldn't consider malleability a vulnerability of the signature scheme in the first place. $\endgroup$ – CodesInChaos Mar 10 '14 at 9:07

Your Answer
