# Ledger Donjon wins Kudelski Crypto Challenge: Behind the scene 1/3 —

Nov 21, 2018 · 4 min read

# One Fault is enough to break EdDSA

This post is part of a series of 3 where we give our solutions on Kudelski CTF. In this post, we give our solution on the 1st challenge.

Kudelski organized a Capture The Flag (CTF) during last summer. The prizes were very attractive:

A Ledger Nano S with 100 USD in Ethereum!

Kudelski CTFs are very interesting, challenging and cryptography related. At Ledger, we have the Donjon team which evaluates the security of our products, hardening them and doing security research. Our areas of expertise include Side Channel Attacks, Fault Attacks and Software Attacks on various architectures.

Even though we were quite busy this summer, we found time to try to attempt the CTF. They were quite difficult and thus we are very proud to be able to solve them. Furthermore, we were the first to do so, and we won the CTF!

We could sadly not attend DEFCON this summer, but for winning the CTF, Kudelski has sent us our precious device :)

We would like to thank Kudelski for this very smooth organization of this great challenge. Kudelski asked us to prepare a write-up explaining how we solved the challenges. You’ll find below how we solved them.

Buckle up your security belt, it’s going to be slightly technical…

After having reversed the code, we assumed that the algorithm used to generate the signature is EdDSA. The symbols were still present in the binary. The functions were renamed in order to add a bit of obfuscation.

This was a fault attack on EdDSA and as Kudelski released a paper about it called Practical fault attack against the Ed25519 and EdDSA signature schemes, we assumed this problem was about implementing one of the attacks presented in the paper.

EdDSA is one of the variations of the ECDSA algorithm, with a small difference. Whilst in ECDSA the nonce is computed randomly, in EdDSA the nonce is deterministically computed from the message and the private key. It means that the two correct signatures of the same message will be the same. Firstly, we have found the correct signature by trying to verify all the given signatures.

For example, when requesting the server to sign the message `000000`, we obtain several signatures:

`fe1f44347edb2f3561c4a04ef723d26937329e72a9e7d85a39c2f081b09f8e29a086c6dad6c6d3a9d235d2b5ece309797e4490a91c01c5396dc14a7291e1de04ca885d387ccbb150663f1580b87294849ed1cbb393aad52ced8d9f9f005f0a13cdb22ecaf52db824052ac30c0d1fce5bbb65a05b219cc589838f4884508b2603de923abb6d8308a29b1860e3f8467cc67a9ba3684761e4ae0853f3ba34ee658664388775a5584957c4bbcc656f0725b922f25e354b480a7a80b3e98f8b9bcf02 be5949a990b337d875dc9bf904a7bf0783b2e6b5f27a87b2777fbcd9dd43235c49265ab132bd58f7721a7f68edd9c0da6614da469f32234473a824198fcdd909de923abb6d8308a29b1860e3f8467cc67a9ba3684761e4ae0853f3ba34ee658664388775a5584957c4bbcc656f0725b922f25e354b480a7a80b3e98f8b9bcf02fe1f44347edb2f3561c4a04ef723d26937329e72a9e7d85a39c2f081b09f8e29a086c6dad6c6d3a9d235d2b5ece309797e4490a91c01c5396dc14a7291e1de04fe1f44347edb2f3561c4a04ef723d26937329e72a9e7d85a39c2f081b09f8e29a086c6dad6c6d3a9d235d2b5ece309797e4490a91c01c5396dc14a7291e1de04`

One can see that one signature appears several times, which probably means it is the ‘correct’ signature. Querying the server for verification shows that indeed `fe1f4434...`is a valid signature, whereas the others are faulty ones.

As we know, the DFA attacks on EdDSA could influence either one part of the signature (S), or two (both R and S). R corresponds to the first half of the above signatures, and S to the second half.

Because the faulty signatures for the same message differ in both, R and S, we assumed that the fault could have occurred either during the computation of hash line 4, or during the point multiplication line 5.

A fault on line 4 affecting r during the whole signature would not lead to an easy recovery of the private key, unless the difference with the expected hash value can be bruteforced. Therefore we tried the simpler option of a transient fault during line 5, which affects ‘R’, and yields the private key with only a little bit of arithmetic.

To get the key, we only need to solve the equation taken from the algorithm

where S and and S’ are known from the two signatures, t and t’ could be computed from

where R and R’ (faulty signature) are known from the signatures, A is the public key, m’ is the message.

The private key ‘a’ equals (S-S’).(t-t’)⁻¹ in this case. Solving the equations for two signatures, faulty and not, we got the key. This information is enough to sign the required message for the challenge.

The flag is: CTF{cryp70 15 n07 cryp70curr3ncy}

The code can be found in our GitHub.

Stay tuned for the challenge #2.

By Ledger Donjon — Jean-Baptiste Bédrune — Victor Servant —Natalia Kulatova — Charles Guillemet

Written by

Written by

## The Strategic Seventeen: Zero Trust

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just \$5/month. Upgrade