Analysis On Ed25519 Use Risks: Your Wallet Private Key Can Be Stolen
2022-06-17
By Max @ Safeheron Team
Recently, security issues on Ed25519 signature libraries have come into the spotlight. For details, please refer to https://github.com/MystenLabs/ed25519-unsafe-libs.
In brief, due to some library designs being ill-considered and misuse of libraries' APIs, the attackers may extract the private key with two different signatures for the same message.
For the ins and outs of this security issue, this article will give you a comprehensive and easy-to-understand analysis.

Why Use Ed25519 to Sign?

American German cryptologist, Daniel J. Bernstein, along with other experts designed the Ed25519, the Elliptic Curve Signature Algorithm based on the 25519 series of elliptic curves. In 2005, Daniel himself proposed the 25519 series of elliptic curves for the first time.
Advantages of Ed25519
  • More Open: Compared to NIST Elliptic Curves, the choosing for every parameter of the 25519 series of elliptic curves is totally open and transparent, with no more doubts.
  • More Secure: The 25519 series of elliptic curves are specially designed which minimize the error probability to have higher security. Eg. any 32-digit random number is a valid X25519 public key that avoids any malicious data attacks.
  • Faster Speed: The 25519 series of elliptic curves are currently the elliptic curves with the fastest computing.
From the above strengths, more and more blockchains choose Ed25519 to be the signature algorithm.

One Image Tells Ed25519 Signature Principle

Ed25519 Signature Principle
As shown above, the image has clearly shown the signature principle of Ed25519, including almost all details. If you want to have a better understanding of Ed25519, the image is for your perusal. And, from the above image, I think you can already feel that the design of Ed25519 is more complicated than the common ECDSA signature algorithm that these two vary a lot.

Ed25519 Signature Formulation

Let me introduce another algorithm that is related to Ed25519 — Schnoor Signature Algorithm. If you have come across with Schnorr Signature Algorithm, you can feel familiar with Ed25519.
Ed25519 can be deemed a variant of Schnorr. There are 2 major differences between them:
  • Ed25519 can use deterministic random numbers multiple times, and even adjust its private key design for this feature
  • Ed25519 can replace the elliptic curve from the common Short Elliptic Curve Secp256k1/Secp256r1 etc. to the Twisted Edwards Curve Ed25519.
Let's see the architecture of Schnorr to illustrate Ed25519 mathematical logic in the form of Schnorr.
To summarize the above image, Ed25519 can be defined as below:
SetupSetup
  • GG
    is base point of elliptic curve group
  • qq
    is the order of ​elliptic curve group
Sign(k,m)Sign(k, m)
  • Step 1:
    x=f1(k)x = f_1(k)
  • Step 2:
    A=xGA = xG
  • Step 3:
    r=f2(k,m)r = f_2(k, m)
  • Step 4:
    e=f3(R,A,m)e = f_3(R, A, m)
  • Step 5:
    R=rGR = rG
  • Step 6:
    S=r+exmodqS = r + e x \mod q
  • Step 7:
    Return (R,S)Return \space (R, S)
Therein
  • kk
    ​is private key
  • mm
    ​is the message pending to be signed
  • AA
    ​ is public key
  • f1f_1
    is a function to compute the public key
    AA
    according to the private key
    kk
  • f2f_2
    is a function to compute the private deterministic random number ​
    rr
    according to the private key
    kk
    and message ​
    mm
  • f3f_3
    is a function to compute the public deterministic random number
    ee
    according to
    RR
    , the public key ​
    AA
    ​ and message
    mm
Note
​The above three functions
f1f_1
,
f2f_2
​,
f3f_3
​ can be derivated as shown in the above image. You can derivate the formulations and I won't do a prolonged explanation on this.
There is no problem with the above algorithms.
Then, what is the problem?
Engineering implementation.

Algorithm Engineering Implementation & Private Key Extract Attacking

Variant Implementation of Ed25519 Signature

Actually, when many algorithm libraries do the Ed25519 Signature Algorithm implementation, they won't really strictly follow the above image shown to implement. For efficiency and convenience, the public key
AA
​ generally won't be re-computed but to be temporarily stored. When signing, the public key
AA
​, as one existing value, is directly used for signature computing, as shown below.
SetupSetup
  • GG
    ​ is base point of elliptic curve group
  • qq
    ​ is the order of elliptic curve group
Sign(k,m,A)Sign(k, m, A)
  • Step 1:
    x=f1(k)x = f_1(k)
  • Step 2:
    r=f2(k,m)r = f_2(k, m)
  • Step 3:
    e=f3(R,A,m)e = f_3(R, A, m)
  • Step 4:
    R=rGR = rG
  • Step 5:
    S=r+exmodqS = r + e x \mod q
  • Step 6:
    Return (R,S)Return \space (R, S)
And, the definitions of
kk
​,
AA
​,
f1f_1
,
f2f_2
​,
f3f_3
stay the same.

​Wallet Architecture

The above image presents a common wallet architecture, including mobile wallet, hardware wallet, cloud wallet (run on a server), etc. scenarios. In the wallet architecture, the private key is generally stored in a safe place which can not be accessed by outside but can participate in signature computing.

Private Key Extract Attacking

Then how the attacking starts? Only need to attack when two signatures are initiated, and to use different public keys (such as use
AA
​ and
AA'
​) separately to sign.
First Signature
The attacker enters
AA
​ and
mm
​, and the wallet enters
kk
e=f3(R,A,m)\Rightarrow e = f3(R, A, m)
S=r+exmodq\Rightarrow S = r + ex \mod q
Second Signature
The attacker enters
AA'
​ and
mm
, and the wallet enters
kk
e=f3(R,A,m)\Rightarrow e' = f3(R, A’, m)
S=r+exmodq\Rightarrow S' = r + e'x \mod q​
As
RR
,
AA
,
AA'
,
mm
,
SS
and
SS'
are all public, so
ee
and
ee'
are also public,
SS
minus
SS'
And both multiplied by the inverse of
(ee)(e-e')
x=(SS)(ee)1modqx = (S - S')(e - e')^{-1} \mod q
Then, the
xx
​ is extracted.
​What needs to be stressed is that we don't need extract 100% private key
kk
. Once the
xx
is extracted, then we can sign any message. That's to say, from the perspective of digital asset security, only extract
xx
equals to get the wallet private key which also means get the assets in the wallet.

Attacking Scope and Corresponding Solution

No matter what kind of wallets, whether mobile, cloud or hardware, as long as you design the Ed25519 Signature Algorithm, that is to provide interfaces similiar to
Sign(k,m,A)Sign(k, m, A)
, and do not verify the public key
AA
, then it's possible to be attacked.
BTW, this attacking also can attack Schnorr.
Solutions are quite simple actually and can be divided into 2 kinds:
  • Do not provide interfaces similar to
    Sign(k,m,A)Sign(k, m, A)
    . Instead, provide interfaces similar to
    Sign(k,m)Sign(k, m)
    . Compute
    AA
    ​ via the private key
    kk
    ​ to avoid invalid entering.
  • If you have to provide interfaces similar to
    Sign(k,m,A)Sign(k, m, A)
    , you must verify
    A==xG A == xG
    , to make sure that the public key you enter is the only valid one.
Though the attacking is practical, we don't need to worry too much about its threat. In most scenarios,
Sign(k,m,A)Sign(k,m,A)
​ can only be called by user self, not the third party (potential attacking party), and the public key
AA
is also valid. So, don't be too anxious about the private key extract attacking. If
Sign(k,m,A)Sign(k, m, A)
​is called by a third party, then you should be cautious about this attack.

Further Thoughts on This Attacking

What's the idea behind this attack? I think you can see that in Ed25519 and Schnorr, deterministic random numbers are used multiple times which actually can tell what's the origin for this attacking.
It's not to say that using deterministic random numbers is wrong. Rather, when all parameters in a signature system are deterministic, the system is secure. Even compared to a random signature system, the former has some safer features, like always generating the same signature for the same message. However, when part of deterministic random numbers have been compromised (typically caused by engineering implementation and use ill-considered), that's where the nightmare prevails. The residual deterministic random numbers can no longer guarantee security, and even can be exploited by the attacker who via duplicate signatures eliminates deterministic invariants to attack the whole system. The attacking towards Ed25519 and Schnorr signature algorithms can partially prove this thought.
So, to guard against this hacking, we can have a new solution, that is, use "real" random numbers to completely replace the deterministic random numbers, which is to eliminate deterministic factors to circumvent such duplicate-signature-depended private key extract attacking. I will introduce the specific application of this new solution sometime in the future.
Also, one good news I want to share is that Safeheron is going to open source our MPC-related algorithms. Welcome all to take a look and we look forward to have any feedback!

References

[1] Daniel J. Bernstein. High-speed high-security signatures
Copy link
On this page
Why Use Ed25519 to Sign?
One Image Tells Ed25519 Signature Principle
Ed25519 Signature Formulation
Algorithm Engineering Implementation & Private Key Extract Attacking
Variant Implementation of Ed25519 Signature
​Wallet Architecture
Private Key Extract Attacking
Attacking Scope and Corresponding Solution
Further Thoughts on This Attacking
References