Black-box attacks on white-box ECDSA

We provide an open-source automatic tool, which can be downloaded on this github link.

White-box cryptography

White-box cryptography aims at protecting the secrecy of private keys embedded in a public implementation. This feature is useful in many contexts.

For example, think about Digital Rights Managements: say your favorite content provider sends your favorite show encrypted to your phone, where the provider’s app decrypts it and allows you for a nice binge-watch in your daily commute. In order to decrypt the content, the app uses a secret key, somehow embedded within its code. What would happen if you, the end user, would be able to just read this code and extract the decryption key? You could for example allow a lot of people to decrypt the content without using the app, by sharing the key. In some cases, you could maybe also manage to decrypt content which you’re not entitled to, with the very same key.

Protection of the secrecy of the key against the user themselves is hence paramount in some contexts.

For years, big industrial groups have been presumed to have a tremendous advance on white-box topics comparing to publicly available academic research. Several recent publications have however renewed the interest of smaller players and researchers towards this topic. Cryptographers took it even some steps further, by proposing (theoretical) constructions achieving Indistiguishability Obfuscation.

WhibOx contest

The WhibOx contests are a series of contests organized by CryptoExperts aiming at sharing ideas about the design of white-box solutions. It allows participants to submit and to break white-box implementations. After two editions focused on the AES, the 2021 edition tackled the ECDSA algorithm.

Designers were asked to implement in C language an ECDSA signature, embedding a private key, and relying on the standardized curve secp256r1. Breakers were asked to recover this key from the source .c file, and the associated public key. Participants gained points depending on the time resiliency of the implementation they either submitted or broke.

At the end of the contest, running for about 3 months, 97 challenges have been submitted, and all of them have been broken.

ECDSA signature

We recall the ECDSA signature scheme:

Nonce-reuse attacks and deterministic ECDSA

In order to thwart this attack, it is mandatory to prevent the reuse of nonces, when signing different digests. One way of enforcing this is to use a deterministic ECDSA protocol (for example, RFC6979).

Attacking the challenges

WhibOx’s challenges are very diverse: some source codes contain the private key in plain sight as a string, while some others embed an encrypted virtual machine in order to obfuscate the executed code. A first approach would then be to carefully reverse the inner logic of every challenge in order to identify the moments where the key is manipulated, and extract it. Ultimately, even though this powerful approach would be perfect for complex implementations, we wanted to be able to automatize key extraction for weakest ones.

Recently, two papers have been independently published by different teams: ECDSA White-Box Implementations: Attacks and Designs from WhibOx 2021 Contest and Attacks Against White-Box ECDSA and Discussion of Countermeasures – A Report on the WhibOx Contest 2021. Both papers describe several techniques that were used by these teams in order to break most challenges. The main attack path is to modify some parts of the code in order to induce faulty behaviors.

In a similar fashion to those approaches but with a simple twist, we will show how to inject faults to recover the secret keys without even looking at the produced binary nor the source code. At the core of these attacks are so-called Differential Fault Analysis.

Differential Fault Analysis

Differential Fault Analysis (DFA) have been first described in the literature in 1996, when Eli Biham and Adi Shamir showed that they could use fault injections in order to recover the secret key used in a DES algorithm, drawing inspiration from the so-called Bellcore attack by Boneh, Demillo and Lipton on RSA.

The attack involves the injection of a perturbation in a device performing a cryptographic operation in order to deviate its results and obtain an incorrect, faulty result. By comparing this faulty result with the corresponding correct one, one can recover some information on the secret key.

As a practical example, we will describe the DFA that has the best success rate in our tool, which was proposed for example in this paper.

Applying DFA to WhibOx’s challenges

Usually, this type of faults targets embedded devices such as smart cards, and involves laser shots, power glitches, or electromagnetic injections. In our context however, we will be able to inject our fault in the binary. We wanted to stay as true as our black-box attack philosophy as possible. As such, we prevent ourselves from even looking at the source code or binary.

Our proposed approach is hence the following :

Note that our approach slightly differs with the one proposed in the previously mentioned papers. Notably, in Attacks Against White-Box ECDSA and Discussion of Countermeasures, the authors chose to systematically replace parts of the code by NOP instructions. On the contrary, our full black-box philosophy randomly aims at any part of the binary, and can produce many different effects, which we will detail in the following section. Though these different models did not allow for new attacks to occur, we still believe that this variety of models is of interest in a general setting.

In order to improve our code understandability to any new user, we implemented the differential fault attacks described in this research paper, and stayed consistent with their naming convention. For example, the classical DFA that we described in the previous section is called F(). Some of these attacks also require two pairs of correct and faulty signatures. Our tool hence generates two correct programs running on two different digest values, as well as their faulty counterparts.

Overall, our straightforward approach allows to break 84 out of the 97 challenges, in a matter of minutes. We refer the interested reader to the two mentioned papers in order to get further details about the design of resisting challenges, and possible attack paths.

About the fault effects

Instead of only replacing code instructions by NOPs, our tool allows for much more generic effects. Here are some of them:

Modification of an immediate operand (eg. challenge 8, index 0x2d42a, value 0x76):

Some challenges embed (encrypted) VMs, which modification imply faults on the result. However, in a black box approach, we can’t explain with confidence the impact of the fault.

Countermeasures and future works

Some challenges take into account these kind of attacks and embed countermeasures, for example:

For further details on the conception of the strongest challenges, we once again refer the interested users to the two research papers ECDSA White-Box Implementations: Attacks and Designs from WhibOx 2021 Contest and Attacks Against White-Box ECDSA and Discussion of Countermeasures – A Report on the WhibOx Contest 2021, which extensively describe the intricate countermeasures that were used in the contest.

Other automatic attacks could be mounted, such as using different fault models and targeting different values. Our tool can also be easily adaptable to the injection of several faults. Another attack path that could be efficient is Differential Computation Analysis. All of these ideas could obviously be improved by a careful manual inspection of the challenges’ designs.