Ed25519

Abstract

EdDSA algorithm itself is proved secure, but some EdDSA libraries implemented API in an unsafe way that could lead to private key exposure.

Cryptography Background

Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves.

The EdDSA signature algorithm and its variants Ed25519 and Ed448 are technically described in the RFC 8032.

Private Key: k

k = A random number generated from RNG.

Derived Integer: a

Calculate the digest of Private Key:

$$H(k)=(h_0,h_1,...,h_{2b-1})$$

Then calculate the integer a:

$$a = 2^{b-2} + \sum_{\substack 3⩽i⩽b-3} 2^ih_i \in \lbrace {2^{b-2},2^{b-2}+8,...,2^{b-1}-8} \rbrace$$

Later, you'll see this a is also a number that can't be leaked since it acts like private key.

Public Key: A

$$A = aB$$

B is the base point of the Curve

Signature Generation: (R,s)

For message M:

$$r=H(h_b,...,h_{2b-1},M) \in 0,1,...2^{2b}-1$$

$$R=rB$$

$$s=(r+H(R,A,M)a)\bmod l$$

l is the order of the subgroup generated by point B.

Now we have the signature (R,s). As you can see, you can calculate any signature if you know a, the same thing as you know the private key k.

Verify the Signature

$$if\space 8sB == 8R+8H(R,A,M)A$$

​

Unsafe Implementations

Now, consider a kind of function implementations:

//PSEUDO CODE
func sign(message M, publicKey A){    
    R = rB
    S=(r+H(R,A,M)a) mod l
    return (R,S)    
}

This sign() allows a caller to input arbitrary message and public key. If he uses same M but different A, he can compute the integer a, the equivalence to private key k:

$$a=(S-S')[H(R,A,M)-H(R,A',M)]^{-1} \bmod l$$

There are many libs with this problem, you can check this list.

Summary

This is an unsafe implementation. It doesn't mean it's a bug that can 100% be exploited now but may have some unpredicted effects in the future.

Developers should be familiar enough with the underlying cryptography to avoid it.

References

https://twitter.com/kostascrypto/status/1535579208960790528

https://datatracker.ietf.org/doc/html/rfc8032