Practical Forgeries for ORANGE

We analyze the authenticated encryption algorithm of ORANGE, a submission to the NIST lightweight cryptography standardization process. We show that it is practically possible to craft forgeries out of two observed transmitted messages that encrypt the same plaintext. The authors of ORANGE have confirmed the attack, and they discuss a fix for this attack in their second-round submission of ORANGE to the NIST lightweight cryptography competition.

Publication Details:

Christoph Dobraunig, Florian Mendel, Bart Mennink: Practical Forgeries for ORANGE. Cryptology ePrint Archive 2020

Protecting against Statistical Ineffective Fault Attacks

Recently, it was shown that Statistical Ineffective Fault Attacks (SIFA) pose a threat for many practical implementations of symmetric primitives. In particular, countermeasures against both power analysis and fault attacks typically do not prevent straightforward SIFA attacks that require only very limited knowledge about the concrete attacked implementation. Consequently, the exploration of countermeasures against SIFA that do not rely on protocols or physical protection mechanisms is of great interest. In this paper, we explore different countermeasure strategies against SIFA. First, we introduce an abstraction layer between the algorithmic specification of a cipher and its implementation in hardware or software to study and describe resistance against SIFA. We then show that by basing the masked implementation on permutations as building blocks, we can build circuits that withstand single-fault SIFA and DPA attacks. We show how this approach can be applied to 3-bit, 4-bit, and 5-bit S-boxes and the AES S-box. Additionally, we present a strategy based on fine-grained fault detection suitable for protecting any circuit against SIFA attacks. Although this approach may lead to a higher implementation cost due to the fine-grained detection needed, it can be used to protect arbitrary circuits and can be generalized to cover multi-fault SIFA.

Publication Details:

Joan Daemen, Christoph Dobraunig, Maria Eichlseder, Hannes Gross, Florian Mendel, Robert Primas: Protecting against Statistical Ineffective Fault Attacks. Cryptology ePrint Archive 2019

Algebraic Cryptanalysis of Frit

Frit is a cryptographic 384-bit permutation recently proposed by Simon et al. and follows a novel design approach for built-in countermeasures against fault attacks. We analyze the cryptanalytic security of Frit in different use-cases and propose attacks on the full-round primitive. We show that the inverse Frit^−1 of Frit is significantly weaker than Frit from an algebraic perspective, despite the better diffusion of the inverse of the used mixing functions: Its round function has an effective algebraic degree of only about 1.325. We show how to craft structured input spaces to linearize up to 4 (or, conditionally, 5) rounds and thus further reduce the degree. As a result, we propose very low-dimensional start-in-the-middle zero-sum partitioning distinguishers for unkeyed Frit, as well as integral distinguishers for round-reduced Frit and full-round Frit^−1. We also consider keyed Frit variants using Even-Mansour or arbitrary round keys. By using optimized interpolation attacks and symbolically evaluating up to 5 rounds of Frit^−1, we obtain key-recovery attacks with a complexity of either 2^59 chosen plaintexts and 2^67 time, or 2^18 chosen ciphertexts and time (about 10 seconds in practice).

Publication Details:

Christoph Dobraunig, Maria Eichlseder, Florian Mendel, Markus Schofnegger: Algebraic Cryptanalysis of Frit. SAC 2019

Fault Attacks on Nonce-based Authenticated Encryption

In the context of fault attacks on nonce-based authenticated encryption, an attacker faces two restrictions. The first is the uniqueness of the nonce for each new encryption that prevents the attacker from collecting pairs of correct and faulty outputs to perform, e.g., differential fault attacks. The second restriction concerns the verification/decryption, which releases only verified plaintext. While many recent works either exploit misuse scenarios (e.g. nonce-reuse, release of unverified plaintext), we turn the fact that the decryption/verification gives us information on the effect of a fault (whether a fault changed a value or not) against it. In particular, we extend the idea of statistical ineffective fault attacks (SIFA) to target the initialization performed in nonce-based authenticated encryption schemes. By targeting the initialization performed during decryption/verification, most nonce-based authenticated encryption schemes provide the attacker with an oracle whether a fault was ineffective or not. This information is all the attacker needs to mount statistical ineffective fault attacks. To demonstrate the practical threat of the attack, we target software implementations of the authenticated encryption schemes Keyak and Ketje. The presented fault attacks can be carried out without the need of sophisticated equipment. In our practical evaluation the inputs corresponding to 24 ineffective fault inductions were required to reveal large parts of the secret key in both scenarios.

Publication Details:

Christoph Dobraunig, Stefan Mangard, Florian Mendel, Robert Primas: Fault Attacks on Nonce-based Authenticated Encryption: Application to Keyak and Ketje. SAC 2018

Fault Attacks on Masked AES with Fault Countermeasures

Implementation attacks like side-channel and fault attacks are a threat for deployed devices especially if an attacker has physical access to a device. As a consequence, devices like smart cards usually provide countermeasures against implementation attacks, such as masking against side-channel attacks and detection-based countermeasures like temporal redundancy against fault attacks. In this paper, we show how to attack implementations protected with both masking and detection-based fault countermeasures by using statistical ineffective fault attacks using a single fault induction per execution. Our attacks are largely unaffected by the deployed protection order of masking and the level of redundancy of the detection-based countermeasure. Our observations refute the intuition that masking is a viable countermeasure against biased faults, statistical fault attacks, or statistical ineffective fault attacks.

Publication Details:

Christoph Dobraunig, Maria Eichlseder, Hannes Gross, Stefan Mangard, Florian Mendel and Robert Primas: Statistical Ineffective Fault Attacks on Masked AES with Fault Countermeasures. ASIACRYPT 2018

Rasta: A cipher with low ANDdepth and few ANDs per bit

Recent developments in multi party computation (MPC) and fully homomorphic encryption (FHE) promoted the design and analysis of symmetric cryptographic schemes that minimize multiplications in one way or another. In this paper, we propose with Rasta a design strategy for symmetric encryption that has ANDdepth d and at the same time only needs d ANDs per encrypted bit. Even for very low values of d between 2 and 6 we can give strong evidence that attacks may not exist. This contributes to a better understanding of the limits of what concrete symmetric-key constructions can theoretically achieve with respect to AND-related metrics, and is to the best of our knowledge the first attempt that minimizes both metrics simultaneously. Furthermore, we can give evidence that for choices of d between 4 and 6 the resulting implementation properties may well be competitive by testing our construction in the use-case of removing the large ciphertext-expansion when using the BGV scheme.

Publication Details:

Christoph Dobraunig, Maria Eichlseder, Lorenzo Grassi, Virginie Lallemand, Gregor Leander, Eik List, Florian Mendel and Christian Rechberger: Rasta: A cipher with low ANDdepth and few ANDs per bit. CRYPTO 2018

Exploiting Ineffective Fault Inductions on Symmetric Cryptography

Since the seminal work of Boneh et al., the threat of fault attacks has been widely known and new techniques for fault attacks and countermeasures have been studied extensively. The vast majority of the literature on fault attacks focuses on the ability of fault attacks to change an intermediate value to a faulty one, such as differential fault analysis (DFA), collision fault analysis, statistical fault attack (SFA), fault sensitivity analysis, or differential fault intensity analysis. The other aspect of faults—that faults can be induced and do not change a value—has been far less researched. In case of symmetric ciphers, this area is covered by ineffective fault attacks (IFA). However, IFA relies on the ability of an attacker to induce reproducible deterministic faults like stuck-at faults for a smaller intermediate structure (e.g., one bit or byte), which is often considered to be impracticable.

As a consequence, most countermeasures against fault attacks focus on the ability of faults to change intermediate values and usually try to detect such a change (detection-based), or to destroy the exploitable information if a fault happens (infective countermeasures). Such countermeasures implicitly assume that the release of “fault-free” ciphertexts in the presence of a fault-inducing attacker does not reveal any exploitable information. In this work, we challenge this assumption and show attacks that exploit the fact that intermediate values leading to such “fault-free” ciphertexts show a non-uniform distribution, while they should be uniformly distributed. The presented attacks are entirely practical and are demonstrated to work for software implementations of AES and for a hardware co-processor.

Publication Details:

Christoph Dobraunig, Maria Eichlseder, Thomas Korak, Stefan Mangard, Florian Mendel and Robert Primas: SIFA: Exploiting Ineffective Fault Inductions on Symmetric Cryptography. CHES 2018