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 scheme using a variant of based on .

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

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

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

PreviousECDSA random numbers NextZero-knowledge Proof

Last updated 2 years ago