In the usual syntax of digital signatures, the verification algorithm takes a verification key in addition to a signature and a message, whereas in ECDSA with key recovery, which is used in Ethereum, no verification key is input to the verification algorithm. Instead, a verification key is recovered from a signature and a message. In this paper, we explore BUFF security of ECDSA with key recovery (KR-ECDSA), where BUFF stands for Beyond UnForgeability Features (Cremers et al., IEEE S&P...

In this paper we explain how we implemented the Secure Hash Algorithm-3 (SHA-3) family of functions in Lean 4, a functional programming language and theorem prover. We describe how we used several Lean facilities including type classes, dependent types, macros, and formal verification, and then refined the design to provide a simple one-shot and streaming API for hashing, and Extendable-output functions (XOFs), to reduce potential for misuse by users, and formally prove properties about the...

Homomorphic Encryption (HE) enables operations on encrypted data without requiring decryption, thus allowing for secure handling of confidential data within smart contracts. Among the known HE schemes, FHEW and TFHE are particularly notable for use in smart contracts due to their lightweight nature and support for arbitrary logical gates. In contrast, other HE schemes often require several gigabytes of keys and are limited to supporting only addition and multiplication. As a result, there...

Authenticated encryption (AE) is a cryptographic mechanism that allows communicating parties to protect the confidentiality and integrity of messages exchanged over a public channel, provided they share a secret key. In this work, we present new AE schemes leveraging the SHA-3 standard functions SHAKE128 and SHAKE256, offering 128 and 256 bits of security strength, respectively, and their “Turbo” counterparts. They support session-based communication, where a ciphertext authenticates the...

Keccak acts as the hash algorithm and eXtendable-Output Function (XOF) specified in the NIST standard drafts for Kyber and Dilithium. The Keccak output is highly correlated with sensitive information. While in RSA and ECDSA, hash-like components are only used to process public information, such as the message. The importance and sensitivity of hash-like components like Keccak are much higher in Kyber and Dilithium than in traditional public-key cryptography. However, few works study Keccak...

With the standardization of NIST post-quantum cryptographic (PQC) schemes, optimizing these PQC schemes across various platforms presents significant research value. While most existing software implementation efforts have concentrated on ARM platforms, research on PQC implementations utilizing various RISC-V instruction set architectures (ISAs) remains limited. In light of this gap, this paper proposes comprehensive and efficient optimizations of Keccak, Kyber, and Dilithium on...

The field of post-quantum cryptography (PQC) is continuously evolving. Many researchers are exploring efficient PQC implementation on various platforms, including x86, ARM, FPGA, GPU, etc. In this paper, we present an Efficient CryptOgraphy CRYSTALS (ECO-CRYSTALS) implementation on standard 64-bit RISC-V Instruction Set Architecture (ISA). The target schemes are two winners of the National Institute of Standards and Technology (NIST) PQC competition: CRYSTALS-Kyber and CRYSTALS-Dilithium,...

This paper presents extensions to the OpenTitan hardware root of trust that aim at enabling high-performance lattice-based cryptography. We start by carefully optimizing ML-KEM and ML-DSA - the two primary algorithms selected by NIST for standardization - in software targeting the OTBN accelerator. Based on profiling results of these implementations, we propose tightly integrated extensions to OTBN, specifically an interface from OTBN to OpenTitan's Keccak accelerator (KMAC core) and...

Resource-constrained devices such as wireless sensors and Internet of Things (IoT) devices have become ubiquitous in our digital ecosystem. These devices generate and handle a major part of our digital data. However, due to the impending threat of quantum computers on our existing public-key cryptographic schemes and the limited resources available on IoT devices, it is important to design lightweight post-quantum cryptographic (PQC) schemes suitable for these devices. In this work, we...

We investigate shift-invariant vectorial Boolean functions on $n$ bits that are lifted from Boolean functions on $k$ bits, for $k\leq n$. We consider vectorial functions that are not necessarily permutations, but are, in some sense, almost bijective. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its lifted functions that does not depend on $n$. We show that if a Boolean function with diameter $k$ is an...

The Ascon specification defines among others an encryption scheme offering authenticated encryption with associated data (AEAD) which is based on a duplex mode of a sponge. With that it is the first of such algorithm selected and about to be standardized by NIST. The sponge size is comparatively small, 320 bits, as expected for lightweight cryptography. With that, the strength of the defined AEAD algorithm is limited to 128 bits. Albeit, the definition of the Ascon AEAD algorithm integrates...

In this paper we study the S-box known as Chi or \chi initially proposed by Daemen in 1995 and very widely used ever since in Keccak, Ascon, and many other. This type of ciphers is typically analyzed [in recent research] in terms of subspace trail attacks [TeDi19] and vector space invariants. An interesting question is then, when different spaces are mapped to each other by translations with a constant. In this paper we relax this fundamental question and we consider arbitrary sets of...

In this paper, we present efficient protected software implementations of the authenticated cipher Ascon, the recently announced winner of the NIST standardization process for lightweight cryptography. Our implementations target theoretical and practical security against second-order power analysis attacks. First, we propose an efficient second-order extension of a previously presented first-order masking of the Keccak S-box that does not require online randomness. The extension...

The substitution box (S-box) is often used as the only nonlinear component in symmetric-key ciphers, leading to a significant impact on the implementation performance of ciphers in both classical and quantum application scenarios by S-box circuits. Taking the Pauli-X gate, the CNOT gate, and the Toffoli gate (i.e., the NCT gate set) as the underlying logic gates, this work investigates the quantum circuit implementation of S-boxes based on the SAT solver. Firstly, we propose encoding methods...

We propose Reckle trees, a new vector commitment based on succinct RECursive arguments and MerKLE trees. Reckle trees' distinguishing feature is their support for succinct batch proofs that are updatable - enabling new applications in the blockchain setting where a proof needs to be computed and efficiently maintained over a moving stream of blocks. Our technical approach is based on embedding the computation of the batch hash inside the recursive Merkle verification via a hash-based...

We report on efficient and secure hardware implementation techniques for the FIPS 205 SLH-DSA Hash-Based Signature Standard. We demonstrate that very significant overall performance gains can be obtained from hardware that optimizes the padding formats and iterative hashing processes specific to SLH-DSA. A prototype implementation, SLotH, contains Keccak/SHAKE, SHA2-256, and SHA2-512 cores and supports all 12 parameter sets of SLH-DSA. SLotH also supports side-channel secure PRF computation...

Multi-user (mu) security considers large-scale attackers that, given access to a number of cryptosystem instances, attempt to compromise at least one of them. We initiate the study of mu security of the so-called GGMtree that stems from the PRG-to-PRF transformation of Goldreich, Goldwasser, and Micali, with a goal to provide references for its recently popularized use in applied cryptography. We propose a generalized model for GGM trees and analyze its mu prefix-constrained PRF security in...

Higher order differential properties constitute a very insightful tool at the hands of a cryptanalyst allowing for probing a cryptographic primitive from an algebraic perspective. In FSE 2017, Saha et al. reported SymSum (referred to as SymSum_Vec in this paper), a new distinguisher based on higher order vectorial Boolean derivatives of SHA-3, constituting one of the best distinguishers on the latest cryptographic hash standard. SymSum_Vec exploits the difference in the algebraic degree...

We introduce an efficient SNARK for towers of binary fields. Adapting Brakedown (CRYPTO '23), we construct a multilinear polynomial commitment scheme suitable for polynomials over tiny fields, including that with just two elements. Our commitment scheme, unlike those of previous works, treats small-field polynomials with no embedding overhead. We further introduce binary-field adaptations of HyperPlonk (EUROCRYPT '23)'s product and permutation checks and of Lasso ('23)'s lookup. Our binary...

The Boolean map $\chi_n^{(k)}:\mathbb{F}_{2^k}^n\rightarrow \mathbb{F}_{2^k}^n$, $x\mapsto u$ given by $u_i=x_i+(x_{(i+1)\ \mathrm{mod}\ n}+1)x_{(i+2)\ \mathrm{mod}\ n}$ appears in various permutations as a part of cryptographic schemes such as KECCAK-f, ASCON, Xoodoo, Rasta, and Subterranean (2.0). Schoone and Daemen investigated some important algebraic properties of $\chi_n^{(k)}$ in [IACR Cryptology ePrint Archive 2023/1708]. In particular, they showed that $\chi_n^{(k)}$ is not...

We propose a new method to encode the problems of optimizing S-box implementations into SAT problems. By considering the inputs and outputs of gates as Boolean functions, the fundamental idea of our method is representing the relationships between these inputs and outputs according to their algebraic normal forms. Based on this method, we present several encoding schemes for optimizing S-box implementations according to various criteria, such as multiplicative complexity, bitslice gate...

The Boolean map $\chi_n \colon \mathbb{F}_2^n \to \mathbb{F}_2^n,\ x \mapsto y$ defined by $y_i = x_i + (x_{i+1}+1)x_{i+2}$ (where $i\in \mathbb{Z}/n\mathbb{Z}$) is used in various permutations that are part of cryptographic schemes, e.g., Keccak-f (the SHA-3-permutation), ASCON (the winner of the NIST Lightweight competition), Xoodoo, Rasta and Subterranean (2.0). In this paper, we study various algebraic properties of this map. We consider $\chi_n$ (through vectorial isomorphism) as a...

Fault attacks impose a serious threat against the practical implementations of cryptographic algorithms. Statistical Ineffective Fault Attacks (SIFA), exploiting the dependency between the secret data and the fault propagation overcame many of the known countermeasures. Later, several countermeasures have been proposed to tackle this attack using error detection methods. However, the efficiency of the countermeasures, in part governed by the number of error checks, still remains a...

Authenticated encryption is a cryptographic mechanism that allows communicating parties to protect the confidentiality and integrity of message exchanged over a public channel, provided they share a secret key. Some applications require committing authenticated encryption schemes, a security notion that is not covered by the classical requirements of confidentiality and integrity given a secret key. An authenticated encryption (AE) scheme is committing in the strongest sense when it is...

\ascon is the final winner of the lightweight cryptography standardization competition $(2018-2023)$. In this paper, we focus on preimage attacks against round-reduced \ascon. The preimage attack framework, utilizing the linear structure with the allocating model, was initially proposed by Guo \textit{et al.} at ASIACRYPT 2016 and subsequently improved by Li \textit{et al.} at EUROCRYPT 2019, demonstrating high effectiveness in breaking the preimage resistance of \keccak. In this...

Column Parity Mixers, or CPMs in short, are a particular type of linear maps, used as the mixing layer in permutation-based cryptographic primitives like Keccak-f (SHA3) and Xoodoo. Although being successfully applied, not much is known regarding their algebraic properties. They are limited to invertibility of CCPMs, and that the set of invertible CCPMs forms a group. A possible explanation is due to the complexity of describing CPMs in terms of linear algebra. In this paper, we introduce a...

Since the announcement of the NIST call for a new lightweight cryptographic standard, a lot of schemes have been proposed in response. Xoodyak is one of these schemes and is among the finalists of the NIST competition with a sponge structure very similar to the Keccak hash function – the winner of the SHA3 NIST competition. In this paper with conditional cube attack technique, we fully recover the key of Xoodyak reduced to 6 and 7 rounds with time complexity resp. 2^{42.58} and 2^{76.003}...

We introduce a new type of mixing layer for the round function of cryptographic permutations, called circulant twin column parity mixer (CPM), that is a generalization of the mixing layers in KECCAK-f and XOODOO. While these mixing layers have a bitwise differential branch number of 4 and a computational cost of 2 (bitwise) additions per bit, the circulant twin CPMs we build have a bitwise differential branch number of 12 at the expense of an increase in computational cost: depending on the...

This note provides an update on Keccak performance on the ARMv7-M processors. Starting from the XKCP implementation, we have applied architecture-specific optimizations that have yielded a performance gain of up to 21% for the largest permutation instance.

In this brief, we realize different architectural techniques towards improving the performance of post-quantum cryptography (PQC) algorithms when implemented as hardware accelerators on an application-specific integrated circuit (ASIC) platform. Having SABER as a case study, we designed a 256-bit wide architecture geared for high-speed cryptographic applications that incorporates smaller and distributed SRAM memory blocks. Moreover, we have adapted the building blocks of SABER to process...

Zero-knowledge proofs and arithmetic circuits are essential building blocks in modern cryptography, but comparing their efficiency across different implementations can be challenging. In this paper, we address this issue by presenting comprehensive benchmarking results for a range of signature schemes and hash functions implemented in Circom, a popular circuit language that has not been extensively benchmarked before. Our benchmarking statistics include prover time, verifier time, and proof...

Cryptographic hash functions are used inside many applications that critically rely on their resistance against cryptanalysis attacks and the correctness of their implementations. Nevertheless, vulnerabilities in cryptographic hash function implementations can remain unnoticed for more than a decade, as shown by the recent discovery of a buffer overflow in the implementation of SHA-3 in the eXtended Keccak Code Package (XKCP), impacting Python, PHP, and several other software projects. This...

Besides the U.S. NIST standard SHA-3(Keccak), another sponge-based primitive Ascon was selected as the NIST standard for lightweight applications, recently. Exploring the security against attacks on the sponge-based hash functions is very important. At EUROCRYPT 2023, Qin et al. introduced the MitM preimage attack framework and the automatic tools for Keccak, Ascon, and Xoodyak. In this paper, we extend Qin et al.'s MitM attack framework into collision attack and also develop various...

An important tool that has contributed to collision search on Keccak/SHA3 is the Target Difference Algorithm (TDA) and its inter- nal differential counterpart Target Internal Difference Algorithm (TIDA), which were introduced by Dinur et al. in separate works in FSE 2012 and 2013 respectively. These algorithms provide an ingenious way of extend- ing the differential trails by one round and exploiting the affine subspaces generated due to the low algebraic degree of the Keccak S-box....

In a recent presentation, we promoted the use of 12-round instances of Keccak, collectively called “TurboSHAKE”, in post-quantum cryptographic schemes, but without defining them further. The goal of this note is to fill this gap: The definition of the TurboSHAKE family simply consists in exposing and generalizing the primitive already defined inside KangarooTwelve.

This paper describes a vulnerability in several implementations of the Secure Hash Algorithm 3 (SHA-3) that have been released by its designers. The vulnerability has been present since the final-round update of Keccak was submitted to the National Institute of Standards and Technology (NIST) SHA-3 hash function competition in January 2011, and is present in the eXtended Keccak Code Package (XKCP) of the Keccak team. It affects all software projects that have integrated this code, such as...

In symmetric cryptography, block ciphers, stream ciphers and permutations often make use of a round function and many round functions consist of a linear and a non-linear layer. One that is often used is based on the cellular automaton that is denoted by $\chi$ as a Boolean map on bi-infinite sequences, $\mathbb{F}^{\mathbb{Z}}$. It is defined by $\sigma \mapsto \nu$ where each $\nu_i = \sigma_i + (\sigma_{i+1}+1)\sigma_{i+2}$. A map $\chi_n$ is a map that operatos on $n$-bit arrays...

This paper combines techniques from several previous papers with some modifications to improve the previous cryptanalysis of 3-round Keccak-256. Furthermore, we propose a fast rebuilding method to improve the efficiency of solving equation systems. As a result, the guessing times of finding a preimage for 3-round Keccak-256 are decreased from $2^{65}$ to $2^{52}$, and the solving time of each guess is decreased from $2^{9}$ 3-round Keccak calls to $2^{5.3}$ 3-round Keccak calls. We identify...

Troika is a sponge-based hash function designed by Kölbl, Tischhauser, Bogdanov and Derbez in 2019. Its specificity is that it is defined over $\mathbb{F}_3$ in order to be used inside IOTA’s distributed ledger but could also serve in all settings requiring the generation of ternary randomness. To be used in practice, Troika needs to be proven secure against state-of-the-art cryptanalysis. However, there are today almost no analysis tools for ternary designs. In this article we take a step...

The Meet-in-the-Middle (MitM) attack has been widely applied to preimage attacks on Merkle-Damg{\aa}rd (MD) hashing. In this paper, we introduce a generic framework of the MitM attack on sponge-based hashing. We find certain bit conditions can significantly reduce the diffusion of the unknown bits and lead to longer MitM characteristics. To find good or optimal configurations of MitM attacks, e.g., the bit conditions, the neutral sets, and the matching points, we introduce the bit-level...

This paper provides necessary properties to algorithmically secure first-order maskings in scalar micro-architectures. The security notions of threshold implementations are adapted following micro-processor leakage effects which are known to the literature. The resulting notions, which are based on the placement of shares, are applied to a two-share randomness-free PRESENT cipher and Keccak-f. The assembly implementations are put on a RISC-V and an ARM Cortex-M4 core. All designs are...

This paper presents two new techniques for the fast implementation of the Keccak permutation on the A-profile of the Arm architecture: First, the elimination of explicit rotations in the Keccak permutation through Barrel shifting, applicable to scalar AArch64 implementations of Keccak-f1600. Second, the construction of hybrid implementations concurrently leveraging both the scalar and the Neon instruction sets of AArch64. The resulting performance improvements are demonstrated in the example...

In this paper, we aim to present a quantum setting oriented preimage attack against 4-round Keccak-224. An important technique we called the allocating rotational cryptanalysis takes the preimage attack into the situation of 2-block preimage recovery. With the conditions on the middle state proposed by Li et al., we use the generic quantum preimage attack to deal with the finding of first preimage block. By using the newly explored propagation of rotational relations, we significantly...

SHA-3 is considered to be one of the most secure standardized hash functions. It relies on the Keccak-f[1 600] permutation, which operates on an internal state of 1 600 bits, mostly represented as a 5×5×64-bit matrix. While software implementations process the state sequentially in chunks of typically 32 or 64 bits, the Keccak-f[1 600] permutation can benefit a lot from speedup through parallelization. This paper is the first to explore the full potential of parallelization of Keccak-f[1...

Masking is a popular secret-sharing technique that is used to protect cryptographic implementations against physical attacks like differential power analysis. So far, most research in this direction has focused on finding efficient Boolean masking schemes for well-known symmetric cryptographic algorithms like AES and Keccak. However, especially with the advent of post-quantum cryptography (PQC), arithmetic masking has received increasing attention from the research community. In practice,...

This paper provides improved preimage analysis on round-reduced Keccak-384/512. Unlike low-capacity versions, Keccak-384/512 outputs from two parts of its state: an entire 320-bit plane and a 64/192-bit truncation of a second plane. Due to lack of degrees of freedom, most existing preimage analysis can only control the first 320-bit plane and achieve limited results. By thoroughly analyzing the algebraic structure of Keccak, this paper proposes a technology named ``extra linear dependence'',...

In this paper, we investigate permutation rotation-symmetric (shift-invariant) vectorial Boolean functions on n bits that are liftings from Boolean functions on k bits, for k≤n. These functions generalize the well-known map used in the current Keccak hash function, which is generated via the Boolean function on 3 variables, x1+(x2+1)x3. We provide some general constructions, and also study the affine equivalence between rotation-symmetric S-boxes and describe the corresponding relationship...

The Keccak sponge function family, designed by Bertoni et al. in 2007, was selected by the U.S. National Institute of Standards and Technology (NIST) in 2012 as the next generation of Secure Hash Algorithm (SHA-3). Due to its theoretical and practical importance, cryptanalysis against SHA-3 has attracted an increasing attention. To the best of our knowledge, the most powerful collision attack on SHA-3 up till now is the linearisation technique proposed by Jian Guo et al. However, that...

The performance of higher-order masked implementations of lattice-based based key encapsulation mechanisms (KEM) is currently limited by the costly conversions between arithmetic and boolean masking. While bitslicing has been shown to strongly speed up masked implementations of symmetric primitives, its use in arithmetic-to-Boolean and Boolean-to-arithmetic masking conversion gadgets has never been thoroughly investigated. In this paper, we first show that bitslicing can indeed accelerate...

This paper considers the capability of 4-round Keccak-224/256/384/512 against the cryptanlysis involved by the quantum algorithm. In order to effectively find the corresponding rotational number for the rotational counterpart of preimage, we first establish a probabilistic algorithm based on the Grover search to guess a possible rotational number by using the fixed relations of bits pairs in some coordinates. This is committed to achieving that each iteration of searching the rotational...

The generation of pseudorandom binary sequences is of a great importance in numerous applications stretching from simulation and gambling to cryptography. Pseudorandom bit generators (PRBGs) can be split into two classes depending on their claimed security. The first includes PRBGs that are provably secure (such as the Blum-Blum-Shub one). Security of the second class rests on heuristic arguments. Sadly, PRBG from the first class are inherently inefficient and some PRBG are insecure against...

SHA-3 is considered to be one of the most secure standardized hash functions. It relies on the Keccak-f[1,600] permutation, which operates on an internal state of 1,600 bits, mostly represented as a $5\times5\times64{-}bit$ matrix. While existing implementations process the state sequentially in chunks of typically 32 or 64 bits, the Keccak-f[1,600] permutation can benefit a lot from speedup through parallelization. This paper is the first to explore the full potential of parallelization of...

The area is one of the most important criteria for an S-box in hardware implementation when designing lightweight cryptography primitives. The area can be well estimated by the number of gate equivalent (GE). However, to our best knowledge, there is no efficient method to search for an S-box implementation with the least GE. Previous approaches can be classified into two categories, one is a heuristic that aims at finding an implementation with a satisfying but not necessarily the smallest...

Performance in hardware has typically played a significant role in differentiating among leading candidates in cryptographic standardization efforts. Winners of two past NIST cryptographic contests (Rijndael in case of AES and Keccak in case of SHA-3) were ranked consistently among the two fastest candidates when implemented using FPGAs and ASICs. Hardware implementations of cryptographic operations may quite easily outperform software implementations for at least a subset of major...

Mixed Integer Linear Programming (MILP) solvers have become one of the most powerful tools for searching cryptographic characteristics, including differentials, impossible differentials, and division trails. Generally, one MILP problem can be formulated by several different MILP models, and the models with fewer constraints and variables are usually easier to solve. How to model a subset of $Z_2^n$ with the least number of constraints is also an interesting mathematical problem. In this...

Correct application of masking on hardware implementation of cryptographic primitives necessitates the instantiation of registers in order to achieve the non-completeness (commonly said to stop the propagation of glitches). This sometimes leads to a high latency overhead, making the implementation not necessarily suitable for the underlying application. As a concrete example, this holds for Keccak. Application of d + 1 Domain Oriented Masking (DOM) on a round-based implementation of Keccak...

In this paper, we present preimage attacks on 4-round Keccak-224/256 as well as 4-round Keccak[$r = 640,c = 160,l = 80$] in the preimage challenges. We revisit the Crossbred algorithm for solving the Boolean multivariate quadratic (MQ) system, propose a new view for the case $D = 2$ and elaborate the computational complexity. The result shows that the Crossbred algorithm outperforms brute force theoretically and practically with feasible memory costs. In our attacks, we construct Boolean MQ...

At SODA 2017 Lokshtanov et al. presented the first worst-case algorithms with exponential speedup over exhaustive search for solving polynomial equation systems of degree $d$ in $n$ variables over finite fields. These algorithms were based on the polynomial method in circuit complexity which is a technique for proving circuit lower bounds that has recently been applied in algorithm design. Subsequent works further improved the asymptotic complexity of polynomial method-based algorithms for...

Masking schemes are among the most popular countermeasures against Side-Channel Analysis (SCA) attacks. Realization of masked implementations on hardware faces several difficulties including dealing with glitches. Threshold Implementation (TI) is known as the first strategy with provable security in presence of glitches. In addition to the desired security order d, TI defines the minimum number of shares to also depend on the algebraic degree of the target function. This may lead to...

The differential-linear attack, combining the power of the two most effective techniques for symmetric-key cryptanalysis, was proposed by Langford and Hellman at CRYPTO 1994. From the exact formula for evaluating the bias of a differential-linear distinguisher (JoC 2017), to the differential-linear connectivity table (DLCT) technique for dealing with the dependencies in the switch between the differential and linear parts (EUROCRYPT 2019), and to the improvements in the context of...

We present the first complete implementation of the offline Simon's algorithm, and estimate its cost to attack the MAC Chaskey, the block cipher PRINCE and the NIST lightweight candidate AEAD scheme Elephant. These attacks require a reasonable amount of qubits, comparable to the number of qubits required to break RSA-2048. They are faster than other collision algorithms, and the attacks against PRINCE and Chaskey are the most efficient known to date. As Elephant has a key smaller than its...

The protection of cryptographic implementations against power analysis attacks is of critical importance for many applications in embedded systems. The typical approach of protecting against these attacks is to implement algorithmic countermeasures, like masking. However, implementing these countermeasures in a secure and correct manner is challenging. Masking schemes require the independent processing of secret shares, which is a property that is often violated by CPU microarchitectures in...

Protection against Side-Channel (SCA) and Fault Attacks (FA) requires two classes of countermeasures to be simultaneously embedded in a cryptographic implementation. It has already been shown that a straightforward combination of SCA and FA countermeasures are vulnerable against FAs, such as Statistical Ineffective Fault Analysis (SIFA) and Fault Template Attacks (FTA). Consequently, new classes of countermeasures have been proposed which prevent against SIFA, and also includes masking for...

Performance in hardware has typically played a major role in differentiating among leading candidates in cryptographic standardization efforts. Winners of two past NIST cryptographic contests (Rijndael in case of AES and Keccak in case of SHA-3) were ranked consistently among the two fastest candidates when implemented using FPGAs and ASICs. Hardware implementations of cryptographic operations may quite easily outperform software implementations for at least a subset of major performance...

Since Keccak was selected as the SHA-3 standard, more and more permutation-based primitives have been proposed. Different from block ciphers, there is no round key in the underlying permutation for permutation-based primitives. Therefore, there is a higher risk for a differential characteristic of the underlying permutation to become incompatible when considering the dependency of difference transitions over different rounds. However, in most of the MILP or SAT based models to search for...

Stateful hash-based signature schemes are among the most efficient approaches for post-quantum signature schemes. Although not suitable for general use, they may be suitable for some use cases on constrained devices. LMS and XMSS are hash-based signature schemes that are conjectured to be quantum secure. In this work, we compared multiple instantiations of both schemes on an ARM Cortex-M4. More precisely, we compared performance, stack consumption, and other figures for key generation,...

In this paper, we present an instruction set coprocessor architecture for lattice-based cryptography and implement the module lattice-based post-quantum key encapsulation mechanism (KEM) Saber as a case study. To achieve fast computation time, the architecture is fully implemented in hardware, including CCA transformations. Since polynomial multiplication plays a performance-critical role in the module and ideal lattice-based public-key cryptography, a parallel polynomial multiplier...

Since its selection as the winner of the SHA-3 competition, Keccak, with all its variants, has found a large number of applications. It is, for instance, a common building block in schemes submitted to NIST's post-quantum cryptography project. In many of these applications, Keccak processes ephemeral secrets. In such a setting, side-channel adversaries are limited to a single observation, meaning that differential attacks are inherently prevented. If, however, such a single trace of Keccak...

Since Keccak was selected as the SHA-3 standard, both its hash mode and keyed mode have attracted lots of third-party cryptanalysis. Especially in recent years, there is progress in analyzing the collision resistance and preimage resistance of round-reduced Keccak. However, for the preimage attacks on round-reduced Keccak-384/512, we found that the linear relations leaked by the hash value are not well exploited when utilizing the current linear structures. To make full use of the...

Post-quantum cryptography has received increased attention in recent years, in particular, due to the standardization effort by NIST. One of the second-round candidates in the NIST post-quantum standardization project is Picnic, a post-quantum secure signature scheme based on efficient zero-knowledge proofs of knowledge. In this work, we present the first FPGA implementation of Picnic. We show how to efficiently calculate LowMC, the block cipher used as a one-way function in Picnic, in...

In this paper, we present new preimage attacks on KECCAK-384 and KECCAK-512 for 2, 3 and 4 rounds. The attacks are based on non-linear structures (structures that contain quadratic terms). These structures were studied by Guo et al. and Li et al. to give preimage attacks on round reduced KECCAK. We carefully construct non-linear structures such that the quadratic terms are not spread across the whole state. This allows us to create more linear equations between the variables and hash values,...

RISC-V is a promising free and open-source instruction set architecture. Most of the instruction set has been standardized and several hardware implementations are commercially available. In this paper we highlight features of RISC-V that are interesting for optimizing implementations of cryptographic primitives. We provide the first optimized assembly implementations of table-based AES, bitsliced AES, ChaCha, and the Keccak-$f$[1600] permutation for the RV32I instruction set. With respect...

Conditional cube attack was proposed by Huang et al. at EUROCRYPT 2017 to attack Keccak keyed mode. Inspired by dynamic cube attack, they reduce the degree by appending key bit conditions on the initial value (IV). Recently, Li et al. proposed new conditional cube attacks on Keccak keyed mode with extremely small degrees of freedom. In this paper, we find a new property on Li et al.'s method, and modify the new conditional cube attack for lightweight encryption algorithms using a 8-2-2...

The conditional cube attack on round-reduced \textsc{Keccak} keyed modes was proposed by Huang~\emph{et al.} at EUROCRYPT 2017. In their attack, a conditional cube variable was introduced, whose diffusion was significantly reduced by certain key bit conditions. The attack requires a set of cube variables which are not multiplied in the first round while the conditional cube variable is not multiplied with other cube variables (called ordinary cube variables) in the first two rounds. This has...

We present new preimage attacks on standard Keccak-224 and Keccak-256 that are reduced to 3 and 4 rounds. An allocating approach is used in the attacks, and the whole complexity is allocated to two stages, such that fewer constraints are considered and the complexity is lowered in each stage. Specifically, we are trying to find a 2-block preimage, instead of a 1-block one, for a given hash value, and the first and second message blocks are found in two stages, respectively. Both the...

At Real World Crypto 2017, Joan Daemen won the Levchin Prize and announced that he believed permutation-based crypto was the future of symmetric cryptography. At the same conference Mike Hamburg introduced Strobe, a symmetric protocol framework capable of protecting sessions as well as building symmetric cryptographic primitives for the single cost of Joan Daemen’s permutation Keccak. The next year, at Real World Crypto 2018 Trevor Perrin came to talk about the Noise protocol framework, a...

The KECCAK hash function is the winner of the SHA-3 competition (2008 -- 2012) and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced SHA-3 and some KECCAK variants. Following the framework developed by Dinur et al. at FSE~2012 where 4-round collisions were found by combining 3-round differential trails and 1-round connectors, we extend the connectors to up to three rounds and hence achieve collision attacks for up to 6...

Internet-of-Things (IoT) applications often require constrained devices to be deployed in the field for several years, even decades. Protection of these tiny motes is crucial for end-to-end IoT security. Secure boot and attestation techniques are critical requirements in such devices which rely on public key Sign/Verify operations. In a not-so-distant future, quantum computers are expected to break traditional public key Sign/Verify functions (e.g. RSA and ECC signatures). Hash Based...

In this paper, we present a cryptanalysis of round reduced Keccak-384 for 2 rounds. The best known preimage attack for this variant of Keccak has the time complexity $2^{129}$. In our analysis, we find a preimage in the time complexity of $2^{89}$ and almost same memory is required.

Threshold Implementations are well-known as a provably firstorder secure Boolean masking scheme even in the presence of glitches. A precondition for their security proof is a uniform input distribution at each round function, which may require an injection of fresh randomness or an increase in the number of shares. However, it is unclear whether violating the uniformity assumption causes exploitable leakage in practice. Recently, Daemen undertook a theoretical study of lossy mappings to...

Cube-attack-like cryptanalysis on round-reduced Keccak was proposed by Dinur et al. at EUROCRYPT 2015. It recovers the key through two phases: the preprocessing phase for precomputing a look-up table and online phase for querying the output and getting the cube sum with which the right key can be retrieved by looking up the precomputed table. It was shown that such attacks are efficient specifically for Keccak-based constructions with small nonce or message block size. In this paper, we...

Recently the CAESAR competition has announced several finalists among the submitted authenticated encryption algorithms, after an open selection process during the last 5 years. Applications using these algorithms are rapidly increasing today. Devices implementing these applications are enormously susceptible to physical attacks, which are able to retrieve secret data through side-channel information such as the power consumption or the electromagnetic radiations. In this work we present a...

In this paper, we introduce an alternative method to find ordinary cube variables for Keccak-MAC by making full use of the key-independent bit conditions. First, we select some potential candidates for ordinary cube variables by properly adding key-independent bit conditions, which do not multiply with the chosen conditional cube variables in the first two rounds. Then, we carefully determine the ordinary cube variables from the candidates to establish the conditional cube tester. Finally,...

We study instantiating the random permutation of the block-cipher mode of operation IAPM (Integrity-Aware Parallelizable Mode) with the public random permutation of Keccak, on which the draft standard SHA-3 is built. IAPM and the related mode OCB are single-pass highly parallelizable authenticated-encryption modes, and while they were originally proven secure in the private random permutation model, Kurosawa has shown that they are also secure in the public random permutation model assuming...

Cube-attack-like cryptanalysis was proposed by Dinur et al. at EUROCRYPT 2015, which recovers the key of Keccak keyed modes in a divide-and-conquer manner. In their attack, one selects cube variables manually, which leads to more key bits involved in the key-recovery attack, so the complexity is too high unnecessarily. In this paper, we introduce a new MILP model and make the cube attacks better on the Keccak keyed modes. Using this new MILP tool, we find the optimal cube variables for...

Keccak is the final winner of SHA-3 competition and it can be used as message authentic codes as well. The basic and balanced divide-and-conquer attacks on Keccak-MAC were proposed by Dinur et al. at Eurocrypt 2015. The idea of cube attacks is used in the two attacks to divide key bits into small portions. In this paper, by carefully analysing the mappings used in Keccak-MAC, it is found that some cube variables could divide key bits into smaller portions and so better divide-and-conquer...

Decision of whether a Boolean equation system has a solution is an NPC problem and finding a solution is NP hard. In this paper, we present a quantum algorithm to decide whether a Boolean equation system F has a solution and compute one if F does have solutions with any given success probability. The complexity of the algorithm is polynomial in the size of F and the condition number of F. As a consequence, we have achieved exponential speedup for solving sparse Boolean equation systems if...

Masking is a widely used countermeasure against Side-Channel Attacks (SCA), but the implementation of these countermeasures is challenging. Experimental security evaluation requires special equipment, a considerable amount of time and extensive technical knowledge. So, to automate and to speed up this process, a formal verification can be performed to asses the security of a design. Multiple theoretical approaches and verification tools have been proposed in the literature. The majority of...

Glitches entail a great issue when securing a cryptographic implementation in hardware. Several masking schemes have been proposed in the literature that provide security even in the presence of glitches. The key property that allows this protection was introduced in threshold implementations as non-completeness. We address crucial points to ensure the right compliance of this property especially for low-latency implementations. Specifically, we first discuss the existence of a flaw in DSD...

Cellular Automata (CA) represent an interesting approach to design Substitution Boxes (S-boxes) having good cryptographic properties and low implementation costs. From the cryptographic perspective, up to now there have been only ad-hoc studies about specific kinds of CA, the best known example being the $\chi$ nonlinear transformation used in Keccak. In this paper, we undertake a systematic investigation of the cryptographic properties of S-boxes defined by CA, proving some upper bounds on...

In this paper, we propose a new MILP modeling to find better or even optimal choices of conditional cubes, under the general framework of conditional cube attacks. These choices generally find new or improved attacks against the keyed constructions based on Keccak permutation and its variants, including Keccak-MAC, KMAC, Keyak, and Ketje, in terms of attack complexities or the number of attacked rounds. Interestingly, conditional cube attacks were applied to round-reduced Keccak-MAC, but not...

In this paper, we give the first pre-image attack against 1- round KECCAK-512 hash function, which works for all variants of 1- round KECCAK. The attack gives a preimage of length less than 1024 bits by solving a system of 384 linear equations. We also give a collision attack against 1-round KECCAK using similar analysis.

This note analyzes the security of Kravatte against the cube attack. We provide an analysis result which recovers the master key of the current version of full Kravatte with data and time complexities $2^{136.01}$, and negligible memory. The same could be applied to the first version of Kravatte with complexities of $2^{38.04}$, which could be carried out in practice. These results are possible thanks to a clever way of constructing affine spaces bypassing the first permutation layer of...

This paper evaluates the security level of the River Keyak against the cube-like attack. River Keyak is the only lightweight scheme of the Keccak-permutation-based Authenticated Encryption Cipher Keyak, which is one of the 16 survivors of the 3rd round CAESAR competition. Dinur et al. gave the seven-round cube-like attack on Lake Keyak (1600-bit) using the divide-and-conquer method at EUROCRYPT 2015, then Huang et al. improved the result to 8-round using a new conditional cube attack at...

In recent years, many leakage-resilient schemes have been published. These schemes guarantee security against side-channel attacks given bounded leakage of the underlying primitive. However, it is a challenging task to reliably determine these leakage bounds from physical properties. In this work, we present a novel approach to find reliable leakage bounds for side channels of cryptographic implementations when the input data complexity is limited such as in leakage-resilient schemes. By...

Masking provides a high level of resistance against side-channel analysis. However, in practice there are many possible pitfalls when masking schemes are applied, and implementation flaws are easily overlooked. Over the recent years, the formal verification of masked software implementations has made substantial progress. In contrast to software implementations, hardware implementations are inherently susceptible to glitches. Therefore, the same methods tailored for software implementations...

Keccak-based algorithms such as Secure Hash Algorithm-3 (SHA-3) will be widely used in crypto systems, and evaluating their security against different kinds of attacks is vitally important. This paper presents an efficient differential fault analysis (DFA) method on all four modes of SHA-3 to recover an entire internal state, which leads to message recovery in the regular hashing mode and key retrieval in the message authentication code (MAC) mode. We adopt relaxed fault models in this...

Conditional cube attack is an efficient key-recovery attack on Keccak keyed modes proposed by Huang et al. at EUROCRYPT 2017. By assigning bit conditions, the diffusion of a conditional cube variable is reduced. Then, using a greedy algorithm (Algorithm 4 in Huang et al.'s paper), Huang et al. find some ordinary cube variables, that do not multiply together in the 1st round and do not multiply with the conditional cube variable in the 2nd round. Then the key-recovery attack is launched. The...

The Keccak hash function is the winner of the SHA-3 competition and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced Keccak hash function, and two main results are achieved: the first practical collision attacks against 5-round Keccak-224 and an instance of 6-round Keccak collision challenge. Both improve the number of practically attacked rounds by one. These results are obtained by carefully studying the algebraic...

The efficient protection of security critical devices against side-channel analysis attacks is a fundamental need in the age of Internet of Things and ubiquitous computing. In this work, we introduce a configurable hardware design of Keccak (SHA-3) which can be tailored to fulfill the needs of a wide range of different applications. Our Keccak design is therefore equipped with generic side-channel protection capabilities. The design can thus be synthesized for any desired protection level by...