On March 13th, 2023, Euler Finance, a DeFi project on the Ethereum blockchain, fell victim to a security breach, leading to a staggering loss of approximately $200 million US dollars to the attacker.
To complicate the investigation and evade detection, the Euler hacker transferred 100 ETH to Lazarus, the hacker group who had previously stolen over $625 million from Ronin. Lazarus then seized the opportunity to send a coded message on-chain to the Euler hacker, accompanied by a 2 ETH gift.
The message content was a hint for the Euler Exploiter to decrypt the message using eth-ecies.
Disclosure
In theory, if the Ronin Exploiter just wanted to encrypt communication in a public environment, using public-key encryption would be the simplest solution.
- Public-key encryption: C = {rG, M + rQ} = {C1, C2}
- Private key decryption: M = M + r(dG) − d(rG) = C2 − d(C1)
The protocol is very simple, where the ciphertext C, public key Q, private key d, random number r, and message M are used. The encryption process does not require the private key, so there is no path for private key leakage.
Was the use of eth-ecies for encryption for convenience or was there another purpose? Soon after, someone pointed out that there is a security vulnerability in eth-ecies, and the Ronin Exploiter may want to steal the private key of the Euler Exploiter.
Was this the real reason behind the message? Let us first analyze the type of vulnerability that exists in eth-ecies.
Twist Attack Vulnerability
Upon analysis, it has been discovered that the JavaScript elliptic curve library “elliptic”: “⁶.4.0” used by eth-ecies, is vulnerable to multiple security threats, including the twisted curve attack vulnerability (twist attacks). This vulnerability arises due to the failure of verifying whether the other party’s public key is on the curve when calculating the ECDH shared key. This allows attackers to construct a public key on a small subgroup curve and trick the victim into computing the shared key, ultimately leading to the compromise of the victim’s private key.
However, the exploit difficulty of this vulnerability is high and requires a very specific scenario to launch an attack. Did the Ronin Exploiter have the opportunity to launch a twist attack?
Risks with the ECDH Algorithm
ECDH algorithm is a key exchange algorithm based on elliptic curve cryptography. Similar to the traditional Diffie-Hellman (DH) algorithm, it uses mathematical operations on elliptic curves to achieve key exchange, thus providing higher security.
The steps of the ECDH algorithm are as follows:
- Generate an elliptic curve: Before initiating the key exchange, both parties must agree on a suitable elliptic curve that satisfies certain mathematical properties, such as the discrete logarithm problem.
- Generate private and public keys: Each party needs to generate a pair of private and public keys. The private key is a random number used to calculate the public key. The public key is a point on the elliptic curve, calculated from the private key.
- Exchange public keys: The two parties exchange their public keys.
- Calculate shared key: The two parties use the other party’s public key and their own private key to calculate a shared key. This shared key can be used to encrypt data in communication, ensuring the confidentiality of the communication.
For ease of description, let’s assume that Alice and Bob represent the two parties mentioned above, and G is the base point. Suppose:
Alice’s private key is a, so Alice’s public key is A = aG.
Bob’s private key is b, so Bob’s public key is B = bG.
The key to ECDH algorithm lies in the method of calculating the shared key. Using the commutative law of group multiplication, the parties can calculate the shared key as long as they have the other party’s public key.
S = aB = a(bG) = b(aG) = bA
If Alice wants to obtain Bob’s private key, she can select a curve point H with a very small order q (very few points), which is not the public key corresponding to any specific private key (but Bob does not know this). As the group is a cyclic group, when Bob calculates S’ = bH, the resulting S’ will be within this small point group. Alice does not know Bob’s private key b, but can obtain x that satisfies S’ = xH through brute force, and then b ≡ x mod q. Clearly, x is very small, at most q.
Knowing only one congruence is not enough to determine the private key, as the private key is a very large number, up to
, and a congruence in this range can have many solutions. Therefore, multiple such twisted points H need to be given to Bob for computation, so that a unique solution can be obtained through computation.
How many twisted points are needed? This depends on the order q chosen each time. The product of the orders needs to exceed the maximum value of the private key, that is, satisfy:
If a larger q is choosen each time, the number of interactions required n can be reduced, but the larger q means that the difficulty of exhaustive search increases. Therefore, a trade-off needs to be made based on Alice’s computational performance.
Event Analysis
Above, we analyzed the risks and attack principles of the ECDH algorithm. Let’s return to the eth-ecies library. In fact, it uses an algorithm similar to ECDH. It uses a temporary key when constructing the shared private key, and does not require the private key of the encryption party, so it does not pose a risk to the encryption party.
It is possible that the Ronin Exploiter may try to use social engineering tactics to guide the Euler Exploiter to use other vulnerable tools, such as the well-known PGP encryption protocol.
Coincidentally, we discovered that the widely used open-source library openpgpjs still uses a lower version of “@openpgp/elliptic”: “⁶.5.1” in its latest version, v5.7.0. What’s even more surprising is that it supports ECDH protocol based on Curve25519. The story seemed to have reached its climax, but upon analysis, we found that the ECDH protocol of openpgpjs introduces temporary keys, similar to the Ecies protocol. Even if the encryption party introduces the private key, it is only used for message signing and will not be used to construct shared keys.
With the story coming to an end, it seems unlikely that the Ronin Exploiter utilized the vulnerability in the older version of elliptic to covertly steal the Euler Explorer’s private key. As for the on-chain message, it may have genuinely been for the purpose of collaborating on a plan. Any further malicious intentions would require more advanced social engineering techniques. However, the Euler Exploiter is already aware of the situation and is staying vigilant.
Additional Information
Above, we mentioned the principles of twist attacks. However, there are still several problems that need to be solved in the actual implementation:
- How to construct twisted points?
- When Bob uses the shared key S’ to encrypt messages, he does not transmit S’ to Alice because, according to the protocol, Bob believes that Alice already knows the key. So, how can Alice obtain S’?
- Assuming the worst-case scenario, Alice eventually obtains a series of shared keys
What method can she use to recover Bob’s private key?
Taking the Curve25519 curve as an example, its curve equation is:
If we arbitrarily change one of the parameters, we get a new curve, such as:
We can use the sagemath mathematical software to represent it:
Then we calculate its order and factorize it:
End result:
We choose the moderately size number 19442993 and create a subgroup with 19442993 elements using the Chinese Remainder Theorem:
So here we have obtained the first twisted point, which we send to Bob as the public key, and Bob can calculate the first shared secret key:
Bob encrypted a message M using
and sent it to Alice. Alice does not know
or the message M, but she knows that M is definitely human-readable natural language. So she starts to enumerate
:
Using
, Alice decrypts the ciphertext, and if the resulting plaintext is natural language, then
=
,
.
Using the same method as above, we can obtain
. In my experiment, I used the following curves:
The final result can be represented as:
The private key b can be calculated using the Chinese Remainder Theorem:
Summary
In this article, we delved into the twisted curve attack in elliptic curve encryption algorithms through an unconventional dialogue. We analyzed the underlying cause of this vulnerability and although its exploit scenarios are limited, it is still a valuable vulnerability to be aware of. We hope our exploration inspires further learning and research in this field.
Lastly, we extend our gratitude to Safeheron, a leading one-stop digital asset self-custody service provider, for their invaluable technical guidance.