OFFICIAL COMMENT: Gravity-SPHINCS

[Thomas Prest]

Dear all,

This mail is to inform you of a fault injection attack against SPHINCS+
and Gravity-SPHINCS.
In schemes of the SPHINCS family, the signature essentially consists of
reconstructing a bunch of Merkle trees and signing their roots with
one-time signatures (OTS).
Introducing one single random fault during the reconstruction of the
penultimate Merkle tree has the effect that one OTS signs two different
values, which can then be exploited to forge signatures for any message
for a computational cost of computing about 2^34 hashes.

More detailed information can be found here:
- Article: https://ia.cr/2018/102
- Slides: https://tprest.github.io/Slides/grafting-trees-pqcrypto.pdf
We have informed the submitters about this attack.

We want to emphasize that this is a fault injection attack: it does not
question the security of these schemes when the signing algorithm is
executed normally.

Best,
Laurent, Ange and Thomas

[Jacob Alperin-Sheriff]

Is there a good survey of fault injections (and similar) in the wild and how to defend against them? 

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.

[Reza Azarderakhsh]

Here it is: https://dl.acm.org/citation.cfm?doid=2930664

On Fri, Apr 13, 2018 at 4:38 PM Jacob Alperin-Sheriff <jaco...@gmail.com> wrote:

Is there a good survey of fault injections (and similar) in the wild and how to defend against them? 

On Fri, Apr 13, 2018, 4:27 PM Thomas Prest <thomas...@ens.fr> wrote:

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.

[Alessandro Barenghi]

________________________________________
From: Jacob Alperin-Sheriff <jaco...@gmail.com>
Sent: 13 April 2018 22:38
To: Thomas Prest
Cc: pqc-comments; pqc-forum
Subject: Re: [pqc-forum] OFFICIAL COMMENT: Gravity-SPHINCS

Is there a good survey of fault injections (and similar) in the wild and how to defend against them?

Although it's growing a bit old, a rather comprehensive one is:

https://doi.org/10.1109/JPROC.2012.2188769

Kind regards,

-- Alessandro

[D. J. Bernstein]

Jacob Alperin-Sheriff writes:
> Is there a good survey of fault injections (and similar) in the wild
> and how to defend against them? 

Here's the basic story: Take any unprotected implementation of any
cryptographic primitive, and it won't be secure against fault attacks.
The literature on fault attacks is mostly evaluating the difference
between low-cost attacks and very-low-cost attacks against unprotected
implementations.

There's also some constructive literature. The basic algorithmic
countermeasures are what you'd expect:

* Apply an error-detecting code to your computation, such as
running twice and raising alarms if there's a mismatch.

* Apply an error-correcting code to your computation, such as
running three times and taking the majority vote.

Both of these are most effective if they're done at each step of the
computation. They're cheaper for linear steps than for nonlinear steps,
cheaper for algebraic steps than for nonalgebraic steps, etc.; there
seems to be some correlation between algorithmic features reducing the
costs of fault attacks and algorithmic features reducing the costs of
countermeasures. Of course there are also physical countermeasures such
as keeping the attacker far away, monitoring temperatures, etc.

It's relatively difficult to find literature studying the security of
implementations that use the obvious countermeasures. One can easily
write down an extreme attack model that theoretically breaks every
circuit (the attacker observes the result of a fault in the last bit
operation, then induces repetitions of the computation and works
backwards through previous bit operations), but this doesn't seem to
shed any light on the question of how expensive a real attack is.

---Dan

[Alex Elsayed]

There's been some interesting work that can be found on IACR:

Instruction Duplication: Leaky and Not Too Fault-Tolerant!

Lucian Cojocar and Kostas Papagiannopoulos and Niek Timmers

https://eprint.iacr.org/2017/1082

Abstract: Fault injection attacks alter the intended behavior of micro- controllers, compromising their security. These attacks can be mitigated using software countermeasures. A widely-used software-based solution to deflect fault attacks is instruction duplication and n-plication. We explore two main limitations with these approaches: first, we examine the effect of instruction duplication under fault attacks, demonstrating that as fault tolerance mechanism, code duplication does not provide a strong protection in practice. Second, we show that instruction duplication increases side-channel leakage of sensitive code regions using a multivariate exploitation technique both in theory and in practice.

Impeccable Circuits

Anita Aghaie and Amir Moradi and Shahram Rasoolzadeh and Falk Schellenberg and Tobias Schneider

https://eprint.iacr.org/2018/203

Abstract: Active physical attacks pose a serious threat to cryptographic hardware, i.e., by injecting faults during the computation. The tools to inject such faults have evolved over the last years and are becoming increasingly powerful. A promising approach to thwart this type of attacks is employing Concurrent Error Detection (CED) schemes. They are usually based on an Error-Detecting Code (EDC) which provides the capability to detect certain injected faults. Depending on the assumed adversary model, the potency of the CED scheme can be adapted during the design phase by adjusting the underlying code. In this work, we propose a methodology to enable a correct, practical, and robust implementation of code-based CED schemes. Indeed, we show that a straightforward hardware implementation of a given code-based CED scheme very likely suffers from severe vulnerabilities and does not provide the desired level of protection against fault attacks. In particular, the propagation of faults into the combinatorial logic is often not considered in the security evaluation of these schemes. First, we formally define this detrimental effect and demonstrate its impact on the security of common CED schemes. Second, we introduce an implementation strategy to limit the negative effect of fault propagation. Third, in contrast to many other works where the fault coverage of an implementation equipped with an EDC is considered, we present a detailed implementation strategy which - based on the specification of the underlying EDC - can guarantee (i.e., 100% coverage rate) the detection of any fault. Fitting to the defined adversary model, this holds for any time of the computation and any location of the circuit - both in the data processing and in the control part. In short, we provide practical guidelines how to construct efficient CED schemes with arbitrary EDCs to achieve the desired level of protection against fault attacks. We evaluate the efficiency of our methodology in a case study considering several symmetric block ciphers (i.e., PRESENT, Skinny, Midori, GIFT, LED, and SIMON) for different design architectures and various linear EDCs with different fault detection capabilities.

Fault Resilient Encoding Schemes in Software: How Far Can We Go?

Jakub Breier and Xiaolu Hou and Yang Liu

https://eprint.iacr.org/2018/218

Abstract: Cryptographic implementations are often vulnerable against physical attacks, fault injection analysis being among the most popular techniques. On par with development of attacks, the area of countermeasures is advancing rapidly, utilizing both hardware- and software-based approaches. When it comes to software encoding countermeasures for fault protection and their evaluation, there are very few proposals so far, mostly focusing on single operations rather than on cipher as a whole.

In this paper we propose an evaluation framework that can be used for analyzing the effectivity of software encoding countermeasures against fault attacks. We first formalize the encoding schemes in software, helping us to define what properties are required when designing a fault protection. These findings show that using anticodes in such countermeasure can increase its detection capabilities. We provide a way to generate a code according to user criteria and also a method to evaluate the level of protection of assembly implementations using encoding schemes. This evaluation is based on static code analysis and provides a practical information on how good will the protection be on a real device. Finally, we verify our findings by implementing a block cipher PRESENT, protected by encoding scheme based on anticodes, and provide a detailed evaluation of such implementation.

[Kevin Chadwick]

On Sat, 14 Apr 2018 18:34:48 +0000

> Abstract: Active physical attacks pose a serious threat to
> cryptographic hardware,

Serious but of 0 concern? Single event upsets such as bit flips
from solar flares are already dealt with for high availability systems.

"Active physical attacks" can only be prevented physically, any other
method denies arbitrary hw modification such as memory or cpu
modification.

> i.e., by injecting faults during the
> computation. The tools to inject such faults have evolved over the
> last years and are becoming increasingly powerful. A promising
> approach to thwart this type of attacks is employing Concurrent Error
> Detection (CED) schemes. They are usually based on an Error-Detecting
> Code (EDC) which provides the capability to detect certain injected
> faults. Depending on the assumed adversary model, the potency of the
> CED scheme can be adapted during the design phase by adjusting the
> underlying code. In this work, we propose a methodology to enable a
> correct, practical, and robust implementation of code-based CED
> schemes. Indeed, we show that a straightforward hardware
> implementation of a given code-based CED scheme very likely suffers
> from severe vulnerabilities and does not provide the desired level of
> protection against fault attacks.

It seems to me that a simpler solution to this unlikely issue is hw
redundancy such as multiple microchips/machines running the code and
doing best of three and/or a microchip(s) resetting with fresh memory
between runs?

Aren't faults that attackers can predict and leverage in a real
world secured environment, non existent?

[guido bertoni]

Some comments on the topic

a nice introduction to faults:
Hagai Bar-El et al. "The Sorcerer’s Apprentice Guide to Fault Attacks"
https://eprint.iacr.org/2004/100.pdf

an interesting book
"Fault Analysis in Cryptography"
M. Joye and M. Tunstall, from Springer

depending on the fault injection capabilities and policy implemented
to counteract fault attacks, codes and/or redundancy could not be
enough.
There is a class of attacks called safe error, where the aim of the
attacker is to observe a correct output even if the fault is injected.
You can have an example in the following paper:
"A Systematic M Safe-error Detection in Hardware Implementations of
Cryptographic Algorithms"
D. Karaklajic, J. Fan and I. Verbauwhede
https://www.esat.kuleuven.be/cosic/publications/article-2202.pdf

Fault attacks are a serious threat against secure chips. There is an
active research comunity, and the topic is covered by different
workshops such as FDTC, CHES and HOST just to mention few of them. You
can see new fault injection techniques, new attacks and mitigations.
http://www.fdtc-workshop.eu/
https://ches.iacr.org/
http://www.hostsymposium.org/

Resistance to fault attacks is a fundamental requirement to most of
the smart cards that are certified via Common Criteria
https://www.sogis.org/documents/cc/domains/sc/JIL-Application-of-Attack-Potential-to-Smartcards-v2-9.pdf

enjoy the reading....

[Aymeric Genêt]

Hello,

I evaluated SPHINCS-256 with respect to side-channel and fault attacks last year as part of my Master thesis.

If I may make a comment based on the conclusion of my analysis, the reason why the fault attack works in the case of SPHINCS is because the scheme inherited of the Goldreich's scheme structure which "reuses" a one-time signature in a clever way.

What I mean is that, during a SPHINCS signature, there are instances of OTS used to sign messages that are not supposed to change from one execution to another. In the case of CMSS (the ancestor of the XMSS structure used within SPHINCS) those messages are the roots of the intermediate Merkle trees.

While this feature is a core improvement that allows most of current hash-based schemes to be practical, I believe that OTSs were not meant to be used that way, which is what caused—in my opinion—the fault attack.

Even though I agree that any unprotected implementation of a cryptographic primitive can't be secure against fault attacks, here the defect comes from the design itself of the algorithm and not an implementation of it. Unlike, for instance, RSA where a glitch injection was possible due to the Chinese remainder theorem speed-up, there are no "algorithmic fixes" or ways to do it so the fault does not impact the security. Therefore, SPHINCS can be deployed only with a robustness enhancement that will most likely be circumvented given the adversary model.

Anyway, those were my two cents. If you're interested in my work on this subject, you can find it here: https://infoscience.epfl.ch/record/253317

Aymeric