Recently there are many competitions, take the time to look at the content of EdDSA signature, happened to encounter a topic involving the failure of its attack, is really very interesting, here to record
EdDSA signature
EdDSA is also a signature algorithm based on ECC. Usually, we see more ECDSA signatures, such as the ECDSA signature based on secP256K1 curve used by Bitcoin, and the signature based on several curves selected by NIST, etc
However, the NIST P-256 curve, also known as SECP256R1, has long been suspected of having a hidden backdoor of NSA because of the default Dual_EC_DRBG random number generator. In 2013, the Revelations of Snowden made this matter come to the forefront, so people lost their trust in this algorithm. So bitcoin chose the secP256K1 curve, which is relatively niche, for its own reasons
In addition, I want to be familiar with the ECDSA signature friend should also know that the safety of ECDSA signature algorithm is more dependent on the safety of the random number generation algorithm, if the problems of random algorithm, using the same k to sign, then an attacker can be according to recover the private key signature information has also been several such accidents in history, For example, SONY’s PS3 private key was cracked in 2010 and bitcoin was stolen in 2012 due to the influence of Java’s certain random number generation library. I have also written relevant analysis on this part of the content, which can be refer to the recovery of Ethereum private key using ECDSA signature of random number conflict, so there are still some problems in the design of ECDSA signature. This also inspired the emergence of the new EdDSA algorithm
EdDSA signature algorithm developed from Schnorr signature, can be seen in RFC8032 definition of its implementation, by the choice of different curves and parameters can be divided into Ed25519 and Ed448 algorithm, according to life, they are based on curVE25519 and CURve448 curve, respectively. Generally used more is Ed25519 algorithm, compared with Ed448 operation speed is faster, secret key and signature space is also small, the use of the two scenarios or a little different, we mainly talk about the following is Ed25519
Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 Ed25519 You can check the security indexes of elliptic curves at Safecurves. Curve25519 is one of the few curves that meet all the indexes. Curve25519 is often used in the DH algorithm of key exchange
In addition, EdDSA is much faster than ECDSA algorithm, which has obvious advantages. Cryptocurrencies such as Menlo Coin and Zcash have switched algorithms to EdDSA, and it has been confirmed as the next generation of elliptic curve algorithm
Ed25518 takes the same finite field P as curve25519, which is 2^255-19. This is also the name of this curve. There are many other parameters such as the length of the public and private key, the base point B, etc., which can be selected in different cases. As long as it meets the definition of the RFC document, you can refer to RFC7748 for more parameters
Here we take a look at the specific signature process of Ed25519, compared to ECDSA does have a great difference
The length of the private key K of Ed25519 is B bit, usually 256. The output length of the hash algorithm H used by Ed25519 is 2B bit. SHA512 is generally selected
First, hash the private key K, and get
Using the hash result we can compute the parameter A
In this way, we can get the corresponding public key A of private key K, A=aB, and B is the selected base point. Now we prepare to sign message M, and the process is as follows, where L is the order of base point B
The signature (R,S) of the message M is obtained, and the verification of the signature must satisfy the following equation
Observe the whole process of the signature, we is not hard to find, a private key k, when signing on the same message M R and S are fixed, so EdDSA signature algorithm is a certainty, not every time like ECDSA signature according to the change of selected randomly to send, so EdDSA security is no longer dependent on the random number generator
Ed25519 Ed25519 software, python implementation, or quite interesting
fault attack
A fault attack is a type of side-channel attack that involves a smart card with a processor in it. It’s a physical method, such as electromagnetic radiation. Laser interferes with the normal operation of the cryptographic chip and forces it to perform some wrong operations. The key information of the cryptographic system can be calculated effectively according to the wrong information
In fact, the emergence of fault attack is also an accident, scientists found in the research of a chip after radiation in the sensitive area of the bit reversal phenomenon, which caused the fault, but through the analysis of these information has opened the door to a new world
There are many ways to cause faults, including simple ones like changing voltage and temperature, modifying clock frequency, advanced ones like electromagnetic radiation, laser irradiation, etc., as well as some corresponding defense means and coping algorithms, which will not be expanded here. If you are interested, you can read this paper, A SURVEY ON FAULT ATTACKS
In order to improve the speed of RSA processing data, Quisquater et al. improved the operation speed of RSA algorithm by using the Chinese residual theorem, namely CRT-RSA algorithm. However, it also provides an excellent entrance for the analysis of fault attack. If you are interested, you can read this article. Analyzing RSA signature faults
In addition, DES and AES have been proposed corresponding attack methods for a long time, and there have been a lot of studies on the fault attack of ECC. The threat of fault attack is still very big, and the attack method is actually very clever
Because the key space corresponding to ECC algorithm is small and the operation speed of the new EdDSA is relatively fast, ECC has been widely applied in the field of smart card, and the corresponding threat of fault attack needs to be paid attention to
Let’s take a look at the failure attack against Ed25519
fault attack on EdDSA
This section is based on the study by Kudelski, HOW TO DEFEAT ED25519 AND EDDSA USING FAULTS
As mentioned above, EdDSA signature is characterized by the same message M, no matter how many times you sign it, the signature result is the same. Therefore, our fault attack is aimed at this feature
In the previous procedure above, if we attack the hash process of step 4, we get a wrong h value, that is, H ‘, which is the wrong signature value S ‘, then according to the relationship, we can get
Asked out a, only in the type on the h ‘is unknown, so how do we know h’ value, actually very simple, namely blasting, the key is we’ll think of some way to let the results calculated hash when attack, one in which a specific is unknown, flip the result is unknown, so we are literally section of blasting, Assuming that the h obtained in the algorithm used here is 32 bytes, the blasting process can be represented by the following pseudocode, which is also borrowed from Kudelski’s diagram
The first step in the signature process is that we need to know the last B bits of the hash of the private key to generate a new h with the message M that we want to sign
In fact, the feature of EdDSA signature is used here, which is also the most ingenious part of this fault attack. We might as well choose a random R value, regardless of the h calculated in the first step of signature, and then use this R to complete the following signature process, obtain the signature (R,S), and then carry out signature verification
Take a closer look at the entire process, it is not hard to find even if we choose r is a random value, but still can be through the signature verification, that is to say as long as know the value we can sign a fake, do not need to know the original private key, here is a already can be regarded as a private key
It can be seen that the process of fault attack on EdDSA is very interesting. Many fault attacks on ECDSA proposed before are mainly aimed at the base point in the operation process, such as changing its coordinates, so that the order of the corresponding base point will also change, probably from a large prime number to a large composite number. The security of elliptic curve requires that the order of base point is prime, so the elliptic curve used by the algorithm after the attack is actually no longer safe, and may be attacked by algorithms such as Pohlig-Hellman. I have also written relevant introduction before, briefly analyzing the ECC attack method of Pohlig-Hellman
Kudelski recently hosted a CRYPto CTF of his own, which included a topic about the Ed25519 fault attack
fault attack challenge
Competition details are here, github.com/kudelskisec…
The topic in question is challenge1, which gives four apis, as follows
Sign will return the signature of the data we sent, so let’s take a look at the signature
Is very interesting, the value of the signature in change, some of weaving the wrong signature, recurring should be the correct signature, but looking at the wrong signature we find them with the correct signature of R and S is different, if we mentioned earlier fault attack as a result, it should be the same R and S are different, so obviously it is not the same as the front is, The fault attack used here is the hash value h of the first step in the signature process. In this way, the R and S obtained later are wrong. In fact, it is simpler
Looking back at the previous calculation of a, at that time we did not know the number h ‘, but here we can directly calculate h ‘from the wrong signature R’, so direct is known, so we can directly calculate a
Take a look at the messages we need to sign
For a complete script, refer to the Ledger-Donjon team’s script and their Write Up, where the public key can be computed from a and base point B
Write in the last
I have learned a lot of new things from this study, and deeply realized the importance of knowledge. I had little understanding of EdDSA before, but the current trend has been to shift to deterministic signature mechanism, and EdDSA as a representative is naturally very important. After all, its security and speed are obvious to all
The article referred to a lot of information, not one list, IMPORTANT information I have added links in the article, at the same time, the level is limited, there may be some places not written well or even mistakes, also hope teachers more advice