In this paper, we investigate the security of lightweight block ciphers, focusing on those that utilize the ADD-Rotate-XOR (ARX) and AND-Rotate-XOR (AND-RX) design paradigms. More specifically, we examine their resilience against boomerang-style attacks. First, we propose an automated search strategy that leverages the boomerang connectivity table (BCT) for AND operations ($\wedge BCT$) to conduct a complete search for boomerang and rectangle distinguishers for AND-RX ciphers. The proposed...

Transciphering (or Hybrid-Homomorphic Encryption, HHE) is an es- tablished technique for avoiding ciphertext expansion in HE applications, saving communication and storage resources. Recently, it has also been shown to be a fundamental component in the practical construction of HE-based multi-party computation (MPC) protocols, being used both for input data and intermediary results (Smart, IMACC 2023). In these protocols, however, ciphers are used with keys that are jointly generated by...

In Africacrypt 2022, Gupta \etal introduced a 64-bit lightweight \mds matrix-based \spn-like block cipher designed to encrypt data in a single clock cycle with minimal implementation cost, particularly when unrolled. While various attack models were discussed, the security of the cipher in the related-key setting was not addressed. In this work, we bridge this gap by conducting a security analysis of the cipher under related-key attacks using \milp(Mixed Integer Linear Programming)-based...

We develop and implement AlgoROM, a tool to systematically analyze the security of a wide class of symmetric primitives in idealized models of computation. The schemes that we consider are those that can be expressed over an alphabet consisting of XOR and function symbols for hash functions, permutations, or block ciphers. We implement our framework in OCaml and apply it to a number of prominent constructions, which include the Luby–Rackoff (LR), key-alternating Feistel (KAF), and...

In this paper, we provide a novel framework for constructing constrained pseudorandom functions (CPRFs) with inner-product constraint predicates, using ideas from subtractive secret sharing and related-key-attack security. Our framework can be instantiated using a random oracle or any suitable related-key-attack (RKA) secure pseudorandom function. This results in three new CPRF constructions: 1. an adaptively-secure construction in the random oracle model; 2. a selectively-secure...

HALFLOOP-96 is a 96-bit tweakable block cipher used in high frequency radio to secure automatic link establishment messages. In this paper, we concentrate on its differential properties in the contexts of conventional, related-tweak, and related-key differential attacks. Using automatic techniques, we determine the minimum number of active S-boxes and the maximum differential probability in each of the three configurations. The resistance of HALFLOOP-96 to differential attacks in the...

GIFT is a family of lightweight block ciphers based on SPN structure and composed of two versions named GIFT-64 and GIFT-128. In this paper, we reevaluate the security of GIFT-64 against the rectangle attack under the related-key setting. Investigating the previous rectangle key recovery attack on GIFT-64, we obtain the core idea of improving the attack——trading off the time complexity of each attack phase. We flexibly guess part of the involved subkey bits to balance the time cost of each...

Various message authentication codes (MACs), including HMAC-Streebog and Streebog-K, are based on the keyless hash function Streebog. Under the assumption that the compression function of Streebog is resistant to the related key attacks, the security proofs of these algorithms were recently presented at CTCrypt 2022. We carefully detail the resources of the adversary in the related key settings, revisit the proof, and obtain tight security bounds. Let $n$ be the bit length of the hash...

The related-key statistical saturation (RKSS) attack is a cryptanalysis method proposed by Li et al. at FSE 2019. It can be seen as the extension of previous statistical saturation attacks under the related-key setting. The attack takes advantage of a set of plaintexts with some bits fixed, while the other bits take all possible values, and considers the relation between the value distributions of a part of the ciphertext bits generated under related keys. Usually, RKSS distinguishers...

The block cipher GOST 28147-89 was the Russian Federation encryption standard for over 20 years, and is still one of its two standard block ciphers. GOST is a 32-round Feistel construction, whose security benefits from the fact that the S-boxes used in the design are kept secret. In the last 10 years, several attacks on the full 32-round GOST were presented. However, they all assume that the S-boxes are known. When the S-boxes are secret, all published attacks either target a small number of...

Non-malleable codes (Dziembowski, Pietrzak and Wichs, ICS 2010 & JACM 2018) allow protecting arbitrary cryptographic primitives against related-key attacks (RKAs). Even when using codes that are guaranteed to be non-malleable against a single tampering attempt, one obtains RKA security against poly-many tampering attacks at the price of assuming perfect memory erasures. In contrast, continuously non-malleable codes (Faust, Mukherjee, Nielsen and Venturi, TCC 2014) do not suffer from this...

Automated cryptanalysis has taken center stage in the arena of cryptanalysis since the pioneering work by Mouha et al. which showcased the power of Mixed Integer Linear Programming (MILP) in solving cryptanalysis problems that otherwise, required significant effort. Since its inception, research in this area has moved in primarily two directions. One is to model more and more classical cryptanalysis tools as optimization problems to leverage the ease provided by state-of-the-art solvers. The...

We construct non-malleable codes in the split-state model with codeword length $m + 3\lambda$ or $m+5\lambda$, where $m$ is the message size and $\lambda$ is the security parameter, depending on how conservative one is. Our scheme is very simple and involves a single call to a block cipher meeting a new security notion which we dub entropic fixed-related-key security, which essentially means that the block cipher behaves like a pseudorandom permutation when queried upon inputs sampled from a...

This paper considers the security of CRAFT and WARP. We present a practical key-recovery attack on full-round CRAFT in the related-key setting with only one differential characteristic, and the theoretical time complexity of the attack is $2^{36.09}$ full-round encryptions. The attack is verified in practice. The test result indicates that the theoretical analysis is valid, and it takes about $15.69$ hours to retrieve the key. A full-round key-recovery attack on WARP in the related-key...

One of the most popular ways to turn a keyless hash function into a keyed one is the HMAC algorithm. This approach is too expensive in some cases due to double hashing. Excessive overhead can sometimes be avoided by using certain features of the hash function itself. The paper presents a simple and safe way to create a keyed cryptoalgorithm (conventionally called "Streebog-K") from hash function Streebog $\mathsf{H}(M)$. Let $K$ be a secret key, then $\mathsf{KH}(K,M)=\mathsf{H}(K||M)$ is a...

Related-key attacks against block ciphers are often considered unrealistic. In practice, as far as possible, the existence of a known "relation" between the secret encryption keys is avoided. Despite this, related keys arise directly in some widely used keyed hash functions. This is especially true for HMAC-Streebog, where known constants and manipulated parameters are added to the secret key. The relation is determined by addition modulo $2$ and $2^{n}$. The security of HMAC reduces to the...

Automated search methods based on Satisfiability Modulo Theories (SMT) problems are being widely used to evaluate the security of block ciphers against distinguishing attacks. While these methods provide a systematic and generic methodology, most of their software implementations are limited to a small set of ciphers and attacks, and extending these implementations requires significant effort and expertise. In this work we present CASCADA, an open-source Python library to evaluate the...

GIFT-64 is a 64-bit block cipher with a 128-bit key that is more lightweight than PRESENT. This paper provides a detailed analysis of GIFT-64 against differential and linear attacks. Our work complements automatic search methods for the best differential and linear characteristics with a careful manual analysis. This hybrid approach leads to new insights. In the differential setting, we theoretically explain the existence of differential characteristics with two active S-boxes per round and...

Related-key attacks (RKA) are powerful cryptanalytic attacks, where the adversary can tamper with the secret key of a cryptographic scheme. Since their invention, RKA security has been an important design goal in cryptography, and various works aim at designing cryptographic primitives that offer protection against related-key attacks. At EUROCRYPT'03, Bellare and Kohno introduced the first formal treatment of related-key attacks focusing on pseudorandom functions and permutations. This was...

We study the provable security claims of two NIST Lightweight Cryptography (LwC) finalists, GIFT-COFB and Photon-Beetle, and present several attacks whose complexities contradict their claimed bounds in their final round specification documents. For GIFT-COFB, we show an attack using $q_e$ encryption queries and no decryption query to break privacy (IND-CPA). The success probability is $O(q_e/2^{n/2})$ for $n$-bit block while the claimed bound contains $O(q^2_e/2^{n})$. This positively...

We revisit designing AND-RX block ciphers, that is, the designs assembled with the most fundamental binary operations---AND, Rotation and XOR operations and do not rely on existing units. Likely, the most popular representative is the NSA cipher \texttt{SIMON}, which remains one of the most efficient designs, but suffers from difficulty in security evaluation. As our main contribution, we propose \texttt{SAND}, a new family of lightweight AND-RX block ciphers. To overcome the difficulty...

ZUC-256 is a stream cipher designed for 5G applications by the ZUC team. Together with AES-256 and SNOW-V, it is currently being under evaluation for standardized algorithms in 5G mobile telecommunications by Security Algorithms Group of Experts (SAGE). A notable feature of the round update function of ZUC-256 is that many operations are defined over different fields, which significantly increases the difficulty to analyze the algorithm. As a main contribution, with the tools of the...

We extend the prior provable related-key security analysis of (generalized) Feistel networks (Barbosa and Farshim, FSE 2014; Yu et al., Inscrypt 2020) to the setting of expanding round functions, i.e., n-bit to m-bit round functions with n < m. This includes Expanding Feistel Networks (EFNs) that purely rely on such expanding round functions, and Alternating Feistel Networks (AFNs) that alternate expanding and contracting round functions. We show that, when two independent keys $K_1,K_2$ are...

The introduction of the automatic search boosts the cryptanalysis of symmetric-key primitives to some degree. However, the performance of the automatic search is not always satisfactory for the search of long trails or ciphers with large state sizes. Compared with the extensive attention on the enhancement for the search with the mixed integer linear programming (MILP) method, few works care for the acceleration of the automatic search with the Boolean satisfiability problem (SAT) or...

Correlated secret randomness is a useful resource for many cryptographic applications. We initiate the study of pseudorandom correlation functions (PCFs) that offer the ability to securely generate virtually unbounded sources of correlated randomness using only local computation. Concretely, a PCF is a keyed function $F_k$ such that for a suitable joint key distribution $(k_0,k_1)$, the outputs $(f_{k_0}(x),f_{k_1}(x))$ are indistinguishable from instances of a given target correlation. An...

In this paper, we reevaluate the security of GIFT against differential cryptanalysis under both single-key scenario and related-key scenario. Firstly, we apply Matsui's algorithm to search related-key differential trails of GIFT. We add three constraints to limit the search space and search the optimal related-key differential trails on the limited search space. We obtain related-key differential trails of GIFT-64/128 for up to 15/14 rounds, which are the best results on related-key...

Impossible differentials cryptanalysis and impossible polytopic cryptanalysis are the most effective approaches to estimate the security of block ciphers. However, the previous automatic search methods of their distinguishers, impossible differentials and impossible polytopic transitions, neither consider the impact of key schedule in the single-key setting and the differential property of large S-boxes, nor apply to the block ciphers with variable rotations. Thus, unlike previous methods...

We study the security of symmetric primitives against key-correlated attacks (KCA), whereby an adversary can arbitrarily correlate keys, messages, and ciphertexts. Security against KCA is required whenever a primitive should securely encrypt key-dependent data, even when it is used under related keys. KCA is a strengthening of the previously considered notions of related-key attack (RKA) and key-dependent message (KDM) security. This strengthening is strict, as we show that 2-round...

$\texttt{CRAFT}$ is a lightweight tweakable block cipher introduced in FSE 2019. One of the main design criteria of $\texttt{CRAFT}$ is the efficient protection of its implementations against differential fault analysis. While the authors of $\texttt{CRAFT}$ provide several cryptanalysis results in several attack models, they do not claim any security of $\texttt{CRAFT}$ against related-key differential attacks. In this paper, we utilize the simple key schedule of $\texttt{CRAFT}$ to...

This paper gives a new generalized key-recovery model of related-key rectangle attacks on block ciphers with linear key schedules. The model is quite optimized and applicable to various block ciphers with linear key schedule. As a proof of work, we apply the new model to two very important block ciphers, i.e. SKINNY and GIFT, which are basic modules of many candidates of the Lightweight Cryptography (LWC) standardization project by NIST. For SKINNY, we reduce the complexity of the best...

In Eurocrypt 2018, Cid et al. proposed a novel notion called the boomerang connectivity table, which formalised the switch property in the middle round of boomerang distinguishers in a unified approach. In this paper, we present a generic model of the boomerang connectivity table with automatic search technique for the first time, and search for (related-key) boomerang distinguishers directly by combining with the search of (related-key) differential characteristics. With the technique, we...

We show that chosen plaintext attacks (CPA) security is equivalent to chosen ciphertext attacks (CCA) security for key-dependent message (KDM) security. Concretely, we show how to construct a public-key encryption (PKE) scheme that is KDM-CCA secure with respect to all functions computable by circuits of a-priori bounded size, based only on a PKE scheme that is KDM-CPA secure with respect to projection functions. Our construction works for KDM security in the single user setting. Our main...

Secure multiparty computation (MPC) often relies on sources of correlated randomness for better efficiency and simplicity. This is particularly useful for MPC with no honest majority, where input-independent correlated randomness enables a lightweight “non-cryptographic” online phase once the inputs are known. However, since the amount of correlated randomness typically scales with the circuit size of the function being computed, securely generating correlated randomness forms an efficiency...

Differential attacks are one of the main ways to attack block ciphers. Hence, we need to evaluate the security of a given block cipher against these attacks. One way to do so is to determine the minimal number of active S-boxes, and use this number along with the maximal differential probability of the S-box to determine the minimal probability of any differential characteristic. Thus, if one wants to build a new block cipher, one should try to maximize the minimal number of active...

We study the *rate* of so-called *continuously* non-malleable codes, which allow to encode a message in such a way that (possibly adaptive) continuous tampering attacks on the codeword yield a decoded value that is unrelated to the original message. Our results are as follows: -) For the case of bit-wise independent tampering, we establish the existence of rate-one continuously non-malleable codes with information-theoretic security, in the plain model. -) For the case of split-state...

In this paper, we introduce a new framework for constructing public-key encryption (PKE) schemes resilient to joint post-challenge/after-the-fact leakage and tampering attacks in the bounded leakage and tampering (BLT) model, introduced by Damgård et al. (Asiacrypt 2013). All the prior formulations of PKE schemes considered leakage and tampering attacks only before the challenge ciphertext is made available to the adversary. However, this restriction seems necessary, since achieving security...

We present a cryptographic primitive $\mathcal{P}$ satisfying the following properties: -- Rudich's seminal impossibility result (PhD thesis '88) shows that $\mathcal{P}$ cannot be used in a black-box manner to construct an injective one-way function. -- $\mathcal{P}$ can be used in a non-black-box manner to construct an injective one-way function assuming the existence of a hitting-set generator that fools deterministic circuits (such a generator is known to exist based on the worst-case...

A non-malleable code is an unkeyed randomized encoding scheme that offers the strong guarantee that decoding a tampered codeword either results in the original message, or in an unrelated message. We consider the simplest possible construction in the computational split-state model, which simply encodes a message $m$ as $k||E_k(m)$ for a uniformly random key $k$, where $E$ is a block cipher. This construction is comparable to, but greatly simplifies over, the one of Kiayias et al. (ACM CCS...

In this article, we propose a new method to protect block cipher implementations against Differential Fault Attacks (DFA). Our strategy, so-called ``Tweak-in-Plaintext'', ensures that an uncontrolled value (`tweak-in') is inserted into some part of the block cipher plaintext, thus effectively rendering DFA much harder to perform. Our method is extremely simple yet presents many advantages when compared to previous solutions proposed at AFRICACRYPT 2010 or CARDIS 2015. Firstly, we do not need...

Deoxys is a third-round candidate of the CAESAR competition. This paper presents the first impossible differential cryptanalysis of Deoxys-BC-256 which is used in Deoxys as an internal tweakable block cipher. First, we find a 4.5-round ID characteristic by utilizing a miss-in-the-middle-approach. We then present several cryptanalyses based upon the 4.5 rounds distinguisher against round-reduced Deoxys-BC-256 in both single-key and related-key settings. Our contributions include impossible...

Motivated by the history of randomness failures in practical systems, Paterson, Schuldt, and Sibborn (PKC 2014) introduced the notion of related randomness security for public key encryption. In this paper, we firstly show an inherent limitation of this notion: if the family of related randomness functions is sufficiently rich to express the encryption function of the considered scheme, then security cannot be achieved. This suggests that achieving security for function families capable of...

In this paper, we introduce a new concept of digital signature that we call \emph{fuzzy signature}, which is a signature scheme that uses a noisy string such as biometric data as a private key, but \emph{does not require user-specific auxiliary data} (which is also called a helper string in the context of fuzzy extractors), for generating a signature. Our technical contributions are three-fold: (1) We first give the formal definition of fuzzy signature, together with a formal definition of a...

After the introduction of some stream ciphers with the minimal internal state, the design idea of these ciphers (i.e. the design of stream ciphers by using a secret key, not only in the initialization but also permanently in the keystream generation) has been developed. The idea lets to design lighter stream ciphers that they are suitable for devices with limited resources such as RFID, WSN. We present necessary conditions for designing a secure stream cipher with the minimal internal state....

Due to the vast number of successful related-key attacks against existing block-ciphers, related-key security has become a common design goal for such primitives. In these attacks, the adversary is not only capable of seeing the output of a function on inputs of its choice, but also on related keys. At Crypto 2010, Bellare and Cash proposed the first construction of a pseudorandom function that could provably withstand such attacks based on standard assumptions. Their construction, as well...

The iterated Even--Mansour (EM) ciphers form the basis of many block cipher designs. Several results have established their security in the CPA/CCA models, under related-key attacks, and in the indifferentiability framework. In this work, we study the Even--Mansour ciphers under key-dependent message (KDM) attacks. KDM security is particularly relevant for block ciphers since non-expanding mechanisms are convenient in setting such as full disk encryption (where various forms of...

Midori is a family of lightweight block cipher proposed by Banik et al. in ASIACRYPT 2015 and it is optimized with respect to the energy consumed by the circuit per bit in encryption or decryption operation. Midori is based on the Substitution-Permutation Network, which has two variants according to the state sizes, i.e. Midori64 and Midori128. It attracted a lot of attention of cryptanalyst since its release. For Midori64, the first meet-in-the-middle attack was proposed by Lin and Wu,...

We present a generalized tweakable blockcipher HPH, which is constructed from a public random permutation $P$ and an almost-XOR-universal (AXU) hash function $H$ with a tweak and key schedule $(t_1,t_2,K)\in \mathcal{T}\times \mathcal{K}$, and defined as $y=HPH_K((t_1,t_2),x)=P(x\oplus H_K(t_1))\oplus H_K(t_2)$, where the key $K$ is chosen from a key space $\mathcal{K}$, the tweak $(t_1,t_2)$ is chosen from a tweak space $\mathcal{T}$, $x$ is a plaintext, and $y$ is a ciphertext. We prove...

Cogliati et al. introduced the tweakable Even-Mansour cipher constructed from a single permutation and an almost-XOR-universal (AXU) family of hash functions with tweak and key schedule. Most of previous papers considered the security of the (iterated) tweakable Even-Mansour cipher in the single-key setting. In this paper, we focus on the security of the tweakable Even-Mansour cipher in the multi-key and related-key settings. We prove that the tweakable Even-Mansour cipher with...

$\mathcal{F}$-Related-Key Attacks (RKA) on cryptographic systems consider adversaries who can observe the outcome of a system under not only the original key, say $k$, but also related keys $f(k)$, with $f$ adaptively chosen from $\mathcal{F}$ by the adversary. In this paper, we define new RKA security notions for several cryptographic primitives including message authentication code (MAC), public-key encryption (PKE) and symmetric encryption (SE). This new kind of RKA notions are called...

The concrete security bounds for some blockcipher-based constructions sometimes become worrisome or even vacuous; for example, when a light-weight blockcipher is used, when large amounts of data are processed, or when a large number of connections need to be kept secure. Rotating keys helps, but introduces a ``hybrid factor'' $m$ equal to the number of keys used. In such instances, analysis in the ideal-cipher model (ICM) can give a sharper picture of security, but this heuristic is called...

KDM$[\mathcal{F}]$-CCA secure public-key encryption (PKE) protects the security of message $f(sk)$, with $f \in \mathcal{F}$, that is computed directly from the secret key, even if the adversary has access to a decryption oracle. An efficient KDM$[\mathcal{F}_{\text{aff}}]$-CCA secure PKE scheme for affine functions was proposed by Lu, Li and Jia (LLJ, EuroCrypt2015). We point out that their security proof cannot go through based on the DDH assumption. In this paper, we introduce a new...

We prove the related-key security of the Iterated Even-Mansour cipher under broad classes of related key derivation (RKD) functions. Our result extends the classes of RKD functions considered by Farshim and Procter (FSE, 15). Moreover, we present a far simpler proof which uses techniques similar to those used by Cogliati and Seurin (EUROCRYPT, 15) in their proof that the four-round Even-Mansour cipher is secure against XOR related-key attacks---a special case of our result and the result of...

Midori is a hardware-oriented lightweight block cipher designed by Banik \emph{et al.} in ASIACRYPT 2015. It has two versions according to the state sizes, i.e. Midori64 and Midori128. In this paper, we explore the security of Midori64 against truncated differential and related-key differential attacks. By studying the compact representation of Midori64, we get the branching distribution properties of almost MDS matrix used by Midori64. By applying an automatic truncated differential search...

We present a new tweakable block cipher family SKINNY , whose goal is to compete with NSA recent design SIMON in terms of hardware/software performances, while proving in addition much stronger security guarantees with regards to differential/linear attacks. In particular, unlike SIMON, we are able to provide strong bounds for all versions, and not only in the single-key model, but also in the related-key or related-tweak model. SKINNY has flexible block/key/tweak sizes and can also benefit...

Functional encryption (FE) enables fine-grained control of sensitive data by allowing users to only compute certain functions for which they have a key. The vast majority of work in FE has focused on deterministic functions, but for several applications such as privacy-aware auditing, differentially-private data release, proxy re-encryption, and more, the functionality of interest is more naturally captured by a randomized function. Recently, Goyal et al. (TCC 2015) initiated a formal study...

Kiasu-BC is a tweakable block cipher presented within the TWEAKEY framework at AsiaCrypt 2014. Kiasu-BC is almost identical to AES-128, the only difference to AES-128 is the tweak addition, where the 64-bit tweak is xored to the first two rows of every round-key. The security analysis of the designers focuses primarily on related-key related-tweak differential characteristics and meet-in-the-middle attacks. For other attacks, they conclude that the security level of Kiasu-BC is similar to...

The related-key model is now considered an important scenario for block cipher security and many schemes were broken in this model, even AES-192 and AES-256. Recently were introduced efficient computer-based search tools that can produce the best possible related-key truncated differential paths for AES. However, one has to trust the implementation of these tools and they do not provide any meaningful information on how to design a good key schedule, which remains a challenge for the...

We formally study ``non-malleable functions'' (NMFs), a general cryptographic primitive which simplifies and relaxes ``non-malleable one-way/hash functions'' (NMOWHFs) introduced by Boldyreva et al. (Asiacrypt 2009) and refined by Baecher et al. (CT-RSA 2010). NMFs focus on basic functions, rather than one-way/hash functions considered in the literature of NMOWHFs. We mainly follow Baecher et al. to formalize a game-based definition for NMFs. Roughly, a function $f$ is non-malleable if...

In the ordinary security model for signature schemes, we consider an adversary that may forge a signature on a new message using only his knowledge of other valid message and signature pairs. To take into account side channel attacks such as tampering or fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In RKA for signature schemes, the adversary can also manipulate the signing key and obtain...

Qin, Liu, Yuen, Deng, and Chen (PKC 2015) gave a new security notion of key-derivation function (KDF), continuous non-malleability with respect to $\Phi$-related-key attacks ($\Phi$-CNM), and its application to RKA-secure public-key cryptographic primitives. They constructed a KDF from cryptographic primitives and showed that the obtained KDF is $\Phi_{hoe\&iocr}$-CNM, where $\Phi_{hoe\&iocr}$ contains the identity function, the constant functions, and functions that have high output-entropy...

Recent advances in block-cipher theory deliver security analyses in models where one or more underlying components (e.g., a function or a permutation) are {\em ideal} (i.e., randomly chosen). This paper addresses the question of finding {\em new} constructions achieving the highest possible security level under minimal assumptions in such ideal models. We present a new block-cipher construction, derived from the Swap-or-Not construction by Hoang et al. (CRYPTO '12). With $n$-bit block...

In this work, we provide a new algebraic framework for pseudorandom functions which encompasses many of the existing algebraic constructions, including the ones by Naor and Reingold (FOCS'97), by Lewko and Waters (CCS'09), and by Boneh, Montgomery, and Raghunathan (CCS'10), as well as the related-key-secure pseudorandom functions by Bellare and Cash (Crypto'10) and by Abdalla et al. (Crypto'14). To achieve this goal, we introduce two versions of our framework. The first, termed linearly...

We present XPX, a tweakable blockcipher based on a single permutation P. On input of a tweak (t_{11},t_{12},t_{21},t_{22}) in T and a message m, it outputs ciphertext c=P(m xor Delta_1) xor Delta_2, where Delta_1=t_{11}k xor t_{12}P(k) and Delta_2=t_{21}k xor t_{22}P(k). Here, the tweak space T is required to satisfy a certain set of trivial conditions (such as (0,0,0,0) not in T). We prove that XPX with any such tweak space is a strong tweakable pseudorandom permutation. Next, we consider...

In this article, we provide the first third-party security analysis of the PRINCE lightweight block cipher, and the underlying PRINCE_core. First, while no claim was made by the authors regarding related-key attacks, we show that one can attack the full cipher with only a single pair of related keys, and then reuse the same idea to derive an attack in the single-key model for the full PRINCE_core for several instances of the $\alpha$ parameter (yet not the one randomly chosen by the...

For constrained devices, standard cryptographic algorithms can be too big, too slow or too energy-consuming. The area of lightweight cryptography studies new algorithms to overcome these problems. In this paper, we will focus on symmetric-key encryption, authentication and hashing. Instead of providing a full overview of this area of research, we will highlight three interesting topics. Firstly, we will explore the generic security of lightweight constructions. In particular, we will discuss...

In IACR ePrint 2014/747, a method for constructing mixed-integer linear programming (MILP) models whose feasible regions are exactly the sets of all possible differential (or linear) characteristics for a wide range of block ciphers is presented. These models can be used to search for or enumerate differential and linear characteristics of a block cipher automatically. However, for the case of SIMON (a lightweight block cipher designed by the U.S. National Security Agency), the method...

At ASIACRYPT 1991, Even and Mansour introduced a block cipher construction based on a single permutation. Their construction has since been lauded for its simplicity, yet also criticized for not providing the same security as other block ciphers against generic attacks. In this paper, we prove that if a small number of plaintexts are encrypted under multiple independent keys, the Even-Mansour construction surprisingly offers similar security as an ideal block cipher with the same block and...

The iterated Even-Mansour cipher is a construction of a block cipher from $r$ public permutations $P_1,\ldots,P_r$ which abstracts in a generic way the structure of key-alternating ciphers. The indistinguishability of this construction from a truly random permutation by an adversary with oracle access to the inner permutations $P_1,\ldots,P_r$ has been investigated in a series of recent papers. This construction has also been shown to be (fully) indifferentiable from an ideal cipher for a...

Related-Key Attacks (RKAs) allow an adversary to observe the outcomes of a cryptographic primitive under not only its original secret key e.g., $s$, but also a sequence of modified keys $\phi(s)$, where $\phi$ is specified by the adversary from a class $\Phi$ of so-called Related-Key Derivation (RKD) functions. This paper extends the notion of non-malleable Key Derivation Functions (nm-KDFs), introduced by Faust et al. (EUROCRYPT'14), to \emph{continuous} nm-KDFs. Continuous nm-KDFs have the...

ITU{\scriptsize{BEE}} is a software oriented lightweight block cipher, which is first proposed at LightSec 2013. The cipher is especially suitable for limited resource application, such as sensor nodes in wireless sensor networks. To evaluate the security level of the cipher, we perform differential attacks on ITU{\scriptsize{BEE}} reduced to 10 rounds and 11 rounds with the time complexities ${2^{65.97}}$ and ${2^{79.03}}$, respectively. To our best knowledge, our analysis is the...

PRIDE is a lightweight block ciphers designed by Albrecht et al., appears in CRYPTO 2014. The designers claim that the construction of linear layers is nicely in line with a bit-sliced implementation of the Sbox layer and security. In this paper, we find 8 2-round iterative related-key differential characteristics, which can be used to construct 18-round related-key differentials. Then, by discussing the function $g^{(1)}_r$, we also find 4 2-round iterative related-key differential...

We consider a public and keyless code $(\Enc,\Dec)$ which is used to encode a message $m$ and derive a codeword $c = \Enc(m)$. The codeword can be adversarially tampered via a function $f \in \F$ from some tampering function family $\F$, resulting in a tampered value $c' = f(c)$. We study the different types of security guarantees that can be achieved in this scenario for different families $\F$ of tampering attacks. Firstly, we initiate the general study of tamper-detection codes, which...

The simplicity and widespread use of blockciphers based on the iterated Even--Mansour (EM) construction has sparked recent interest in the theoretical study of their security. Previous work has established their strong pseudorandom permutation and indifferentiability properties, with some matching lower bounds presented to demonstrate tightness. In this work we initiate the study of the EM ciphers under related-key attacks which, despite extensive prior work, has received little attention....

We propose the TWEAKEY framework with goal to unify the design of tweakable block ciphers and of block ciphers resistant to related-key attacks. Our framework is simple, extends the key-alternating construction, and allows to build a primitive with arbitrary tweak and key sizes, given the public round permutation (for instance, the AES round). Increasing the sizes renders the security analysis very difficult and thus we identify a subclass of TWEAKEY, that we name STK, which solves the size...

In this paper, we investigate the Mixed-integer Linear Programming (MILP) modelling of the differential and linear behavior of a wide range of block ciphers. We point out that the differential behavior of an arbitrary S-box can be exactly described by a small system of linear inequalities. ~~~~~Based on this observation and MILP technique, we propose an automatic method for finding high probability (related-key) differential or linear characteristics of block ciphers. Compared with Sun {\it...

Related-key attacks (RKAs) concern the security of cryptographic primitives in the situation where the key can be manipulated by the adversary. In the RKA setting, the adversary's power is expressed through the class of related-key deriving (\RKD) functions which the adversary is restricted to using when modifying keys. Bellare and Kohno (Eurocrypt 2003) first formalised RKAs and pin-pointed the foundational problem of constructing RKA-secure pseudorandom functions (RKA-PRFs). To date there...

In a related-key attack (RKA) an adversary attempts to break a cryptographic primitive by invoking the primitive with several secret keys which satisfy some known relation. The task of constructing provably RKA secure PRFs (for non-trivial relations) under a standard assumption has turned to be challenging. Currently, the only known provably-secure construction is due to Bellare and Cash (Crypto 2010). This important feasibility result is restricted, however, to linear relations over...

Most implementations of Yao's garbled circuit approach for 2-party secure computation use the {\em free-XOR} optimization of Kolesnikov \& Schneider (ICALP 2008). We introduce an alternative technique called {\em flexible-XOR} (fleXOR) that generalizes free-XOR and offers several advantages. First, fleXOR can be instantiated under a weaker hardness assumption on the underlying cipher/hash function (related-key security only, compared to related-key and circular security required for...

In this paper, we present a construction of public key encryption secure against related key attacks from hash proof systems in the standard model. We show that the schemes presented by Jia et al. (Provsec2013) are special cases of our general theory, and also give other instantiations based on the QR and DCR assumptions. To fulfill the related key security, we require the hash proof systems to satisfy the key homomorphism and computational finger-printing properties. Compared with the...

TWINE is a lightweight block cipher proposed in SAC 2012 by Suzaki et al. TWINE operates on 64-bit block and supports 80 or 128-bit key, denoted as TWINE-80 and TWINE-128 respectively. TWINE has attracted some attention since its publication and its security has been analyzed against several cryptanalytic techniques in both single-key and related-key settings. In the single-key setting, the best attack so far is reported by Boztaş et al. at LightSec'13, where a splice-and-cut attack on...

In this paper we study the security of hash-based MAC algorithms (such as HMAC and NMAC) above the birthday bound. Up to the birthday bound, HMAC and NMAC are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an $n$-bit MAC is built from a hash function with a $l$-bit state ($l \ge n$), there is a well-known existential forgery attack with complexity $2^{l/2}$. However, the remaining security after $2^{l/2}$ computations is not well understood. In...

Several recent and high-profile incidents give cause to believe that randomness failures of various kinds are endemic in deployed cryptographic systems. In the face of this, it behoves cryptographic researchers to develop methods to immunise - to the extent that it is possible - cryptographic schemes against such failures. This paper considers the practically-motivated situation where an adversary is able to force a public key encryption scheme to reuse random values, and functions of those...

Wee (PKC'12) proposed a generic public-key encryption scheme in the setting of related-key attacks. Bellare, Paterson and Thomson (Asiacrypt'12) provided a framework enabling related-key attack (RKA) secure cryptographic primitives for a class of non-linear related-key derivation functions. However, in both of their constructions, the instantiations to achieve the full (not weak) RKA security are given under the scenario regarding the private key composed of single element. In other words,...

It is well known that the classical three- and four-round Feistel constructions are provably secure under chosen-plaintext and chosen-ciphertext attacks, respectively. However, irrespective of the number of rounds, no Feistel construction can resist related-key attacks where the keys can be offset by a constant. In this paper we show that, under suitable reuse of round keys, security under related-key attacks can be provably attained. Our modification is substantially simpler and more...

In this paper, we propose a new lightweight block cipher named RECTANGLE. The main idea of the design of RECTANGLE is to allow lightweight and fast implementations using bit-slice techniques. RECTANGLE uses an SP-network. The substitution layer consists of 16 4 x 4 S-boxes in parallel. The permutation layer is composed of 3 rotations. As shown in this paper, RECTANGLE offers great performance in both hardware and software environment, which provides enough flexibility for different...

So far, low probability differentials for the key schedule of block ciphers have been used as a straightforward proof of security against related-key differential attacks. To achieve the resistance, it is believed that for cipher with $k$-bit key it suffices the upper bound on the probability to be $2^{-k}$. Surprisingly, we show that this reasonable assumption is incorrect, and the probability should be (much) lower than $2^{-k}$. Our counter example is a related-key differential analysis...

We propose a tool for automatic search for differential trails in ARX ciphers. By introducing the concept of a partial difference distribution table (pDDT) we extend Matsui's algorithm, originally proposed for DES-like ciphers, to the class of ARX ciphers. To the best of our knowledge this is the first application of Matsui's algorithm to ciphers that do not have S-boxes. The tool is applied to the block ciphers TEA, XTEA, SPECK and RAIDEN. For RAIDEN we find an iterative characteristic on...

Circular security is an important notion for public-key encryption schemes and is needed by several cryptographic protocols. In circular security the adversary is given an extra ``hint'' consisting of a cycle of encryption of secret keys i.e., (E_{pk_1}(sk_2),..., E_{pk_n}(sk_1)). A natural question is whether every IND-CPA encryption scheme is also circular secure. It is trivial to see that this is not the case when n=1. In 2010 a separation for n=2 was shown by [ABBC10,GH10] under standard...

Related key attacks (RKAs) are powerful cryptanalytic attacks where an adversary can change the secret key and observe the effect of such changes at the output. The state of the art in RKA security protects against an a-priori unbounded number of certain algebraic induced key relations, e.g., affine functions or polynomials of bounded degree. In this work, we show that it is possible to go beyond the algebraic barrier and achieve security against arbitrary key relations, by restricting the...

We propose two systematic methods to describe the differential property of an S-box with linear inequalities based on logical condition modelling and computational geometry respectively. In one method, inequalities are generated according to some conditional differential properties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box. For the second method, we develop a greedy algorithm...

We construct secret-key encryption (SKE) schemes that are secure against related-key attacks and in the presence of key-dependent messages (RKA-KDM secure). We emphasize that RKA-KDM security is not merely the conjunction of individual security properties, but covers attacks in which ciphertexts of key-dependent messages under related keys are available. Besides being interesting in their own right, RKA-KDM secure schemes allow to garble circuits with XORs very efficiently (Applebaum, TCC...

Counting the number of active S-boxes is a common way to evaluate the security of symmetric key cryptographic schemes against differential attack. Based on Mixed Integer Linear Programming (MILP), Mouha et al proposed a method to accomplish this task automatically for word-oriented symmetric-key ciphers with SPN structures. However, this method can not be applied directly to block ciphers of SPN structures with bitwise permutation diffusion layers (S-bP structures), due to its ignorance of...

We examine the security of the 64-bit lightweight block cipher PRESENT-80 against related-key differential attacks. With a computer search we are able to prove that no related-key differential characteristic exists with probability higher than $2^{-64}$ for the full-round PRESENT-80. To overcome the exponential (in the state and key sizes) computational complexity we use truncated differences, however as the key schedule is not nibble oriented, we switch to actual differences and apply early...

MISTY1 is a block cipher designed by Matsui in 1997. It is widely deployed in Japan where it is an e-government standard, and is recognized internationally as a NESSIE-recommended cipher as well as an ISO standard and an RFC. Moreover, MISTY1 was selected to be the blueprint on top of which KASUMI, the GSM/3G block cipher, was based. Since its introduction, and especially in recent years, MISTY1 was subjected to extensive cryptanalytic efforts, which resulted in numerous attacks on its...

This paper provides a (standard-model) notion of security for (keyed) hash functions, called UCE, that we show enables instantiation of random oracles (ROs) in a fairly broad and systematic way. Goals and schemes we consider include deterministic PKE, message-locked encryption, hardcore functions, point-function obfuscation, OAEP, encryption secure for key-dependent messages, encryption secure under related-key attack, proofs of storage and adaptively-secure garbled circuits with short...

While the symmetric-key cryptography community has now a good experience on how to build a secure and efficient fixed permutation, it remains an open problem how to design a key-schedule for block ciphers, as shown by the numerous candidates broken in the related-key model or in a hash function setting. Provable security against differential and linear cryptanalysis in the related-key scenario is an important step towards a better understanding of its construction. Using a structural...

This paper introduces key-versatile signatures. Key-versatile signatures allow us to sign with keys already in use for another purpose, without changing the keys and without impacting the security of the original purpose. This allows us to obtain advances across a collection of challenging domains including joint Enc/Sig, security against related-key attack (RKA) and security for key-dependent messages (KDM). Specifically we can (1) Add signing capability to existing encryption capability...

We prove a security theorem without collision-resistance for a class of 1-key hash-function-based MAC schemes that includes HMAC and Envelope MAC. The proof has some advantages over earlier proofs: it is in the uniform model, it uses a weaker related-key assumption, and it covers a broad class of MACs in a single theorem. However, we also explain why our theorem is of doubtful value in assessing the real-world security of these MAC schemes. In addition, we prove a theorem assuming...

Message Authentication Code (MAC) is one of most basic primitives in cryptography. After Biham (EUROCRYPT 1993) and Knudsen (AUSCRYPT 1992) proposed related-key attacks (RKAs), RKAs have damaged MAC's security. To relieve MAC of RKA distress, Bellare and Cash proposed pseudo-random functions (PRFs) secure against multiplicative RKAs (CRYPTO 2010). They also proposed PRFs secure against additive RKAs, but their reduction requires sub-exponential time. Since PRF directly implies Fixed-Input...

RAKAPOSHI is a hardware oriented stream cipher designed by Carlos Cid et al. in 2009. The stream cipher is based on Dynamic Linear Feedback Shift Registers, with a simple and potentially scalable design, and is particularly suitable for hardware applications with restricted resources. The RAKAPOSHI stream cipher offers 128-bit security. In this paper, we point out some weaknesses in the cipher. Firstly, it shows that there are 2^192 weak (key, IV) pairs in RAKAPOSHI stream cipher. Secondly,...