617 results sorted by ID
Ultrametric integral cryptanalysis
Tim Beyne, Michiel Verbauwhede
Secret-key cryptography
A systematic method to analyze \emph{divisibility properties} is proposed.
In integral cryptanalysis, divisibility properties interpolate between bits that sum to zero (divisibility by two) and saturated bits (divisibility by $2^{n - 1}$ for $2^n$ inputs).
From a theoretical point of view, we construct a new cryptanalytic technique that is a non-Archimedean multiplicative analogue of linear cryptanalysis. It lifts integral cryptanalysis to characteristic zero in the sense that, if all...
LINE: Cryptosystem based on linear equations for logarithmic signatures
Gennady Khalimov, Yevgen Kotukh, Maksym Kolisnyk, Svitlana Khalimova, Oleksandr Sievierinov
Public-key cryptography
The discourse herein pertains to a directional encryption cryptosystem predicated upon logarithmic signatures interconnected via a system of linear equations (we call it LINE). A logarithmic signature serves as a foundational cryptographic primitive within the algorithm, characterized by distinct cryptographic attributes including nonlinearity, noncommutativity, unidirectionality, and factorizability by key. The confidentiality of the cryptosystem is contingent upon the presence of an...
White-box filtering attacks breaking SEL masking: from exponential to polynomial time
Alex Charlès, Aleksei Udovenko
Attacks and cryptanalysis
This work proposes a new white-box attack technique called filtering, which can be combined with any other trace-based attack method. The idea is to filter the traces based on the value of an intermediate variable in the implementation, aiming to fix a share of a sensitive value and degrade the security of an involved masking scheme.
Coupled with LDA (filtered LDA, FLDA), it leads to an attack defeating the state-of-the-art SEL masking scheme (CHES 2021) of arbitrary degree and number of...
LPN-based Attacks in the White-box Setting
Alex Charlès, Aleksei Udovenko
Attacks and cryptanalysis
In white-box cryptography, early protection techniques have fallen to the automated Differential Computation Analysis attack (DCA), leading to new countermeasures and attacks. A standard side-channel countermeasure, Ishai-Sahai-Wagner's masking scheme (ISW, CRYPTO 2003) prevents Differential Computation Analysis but was shown to be vulnerable in the white-box context to the Linear Decoding Analysis attack (LDA). However, recent quadratic and cubic masking schemes by Biryukov-Udovenko...
Differential Cryptanalysis of a Lightweight Block Cipher LELBC
Manjeet Kaur, Tarun Yadav, Manoj Kumar, Dhananjoy Dey
Attacks and cryptanalysis
In this study, we investigate the newly developed low energy lightweight block cipher (LELBC), specifically designed for resource-constrained Internet of Things (IoT) devices in smart agriculture. The designers conducted a preliminary differential cryptanalysis of LELBC through mixed-integer linear programming (MILP). This paper further delves into LELBC’s differential characteristics in both single and related-key frameworks using MILP, identifying a nine-round differential characteristic...
Algorithms for Matrix Code and Alternating Trilinear Form Equivalences via New Isomorphism Invariants
Anand Kumar Narayanan, Youming Qiao, Gang Tang
Attacks and cryptanalysis
We devise algorithms for finding equivalences of trilinear forms over finite fields modulo linear group actions. Our focus is on two problems under this umbrella, Matrix Code Equivalence (MCE) and Alternating Trilinear Form Equivalence (ATFE), since their hardness is the foundation of the NIST round-$1$ signature candidates MEDS and ALTEQ respectively.
We present new algorithms for MCE and ATFE, which are further developments of the algorithms for polynomial isomorphism and alternating...
Algebraic Algorithm for the Alternating Trilinear Form Equivalence Problem
Lars Ran, Simona Samardjiska, Monika Trimoska
Attacks and cryptanalysis
The Alternating Trilinear Form Equivalence (ATFE) problem was recently used by Tang et al. as a hardness assumption in the design of a Fiat-Shamir digital signature scheme ALTEQ. The scheme was submitted to the additional round for digital signatures of the NIST standardization process for post-quantum cryptography.
ATFE is a hard equivalence problem known to be in the class of equivalence problems that includes, for instance, the Tensor Isomorphism (TI), Quadratic Maps Linear...
Practical Attack on All Parameters of the DME Signature Scheme
Pierre Briaud, Maxime Bros, Ray Perlner, Daniel Smith-Tone
Attacks and cryptanalysis
DME is a multivariate scheme submitted to the call for additional signatures recently launched by NIST. Its performance is one of the best among all the candidates. The public key is constructed from the alternation of very structured linear and non-linear components that constitute the private key, the latter being defined over an extension field. We exploit these structures by proposing an algebraic attack which is practical on all DME parameters.
A generic algorithm for efficient key recovery in differential attacks – and its associated tool
Christina Boura, Nicolas David, Patrick Derbez, Rachelle Heim Boissier, María Naya-Plasencia
Secret-key cryptography
Differential cryptanalysis is an old and powerful attack against block ciphers. While different techniques have been introduced throughout the years to improve the complexity of this attack, the key recovery phase remains a tedious and error-prone procedure. In this work, we propose a new algorithm and its associated tool that permits, given a distinguisher, to output an efficient key guessing strategy. Our tool can be applied to SPN ciphers whose linear layer consists of a bit-permutation...
Polynomial-Time Key-Recovery Attack on the ${\tt NIST}$ Specification of ${\tt PROV}$
River Moreira Ferreira, Ludovic Perret
Attacks and cryptanalysis
In this paper, we present an efficient attack against ${\tt PROV}$, a recent variant of the popular Unbalanced Oil and Vinegar (${\tt UOV}$) multivariate signature scheme, that has been submitted to the ongoing ${\tt NIST}$ standardization process for additional post-quantum signature schemes. A notable feature of ${\tt PROV}$ is its proof of security, namely, existential unforgeability under a chosen-message attack (${\tt EUF-CMA}$), assuming the hardness of solving the system formed by the...
Revisiting Differential-Linear Attacks via a Boomerang Perspective with Application to AES, Ascon, CLEFIA, SKINNY, PRESENT, KNOT, TWINE, WARP, LBlock, Simeck, and SERPENT
Hosein Hadipour, Patrick Derbez, Maria Eichlseder
Attacks and cryptanalysis
In 1994, Langford and Hellman introduced differential-linear (DL) cryptanalysis, with the idea of decomposing the block cipher E into two parts, EU and EL, such that EU exhibits a high-probability differential trail, while EL has a high-correlation linear trail.Combining these trails forms a distinguisher for E, assuming independence between EU and EL. The dependency between the two parts of DL distinguishers remained unaddressed until EUROCRYPT 2019, where Bar-On et al. introduced the DLCT...
Don’t Use It Twice! Solving Relaxed Linear Code Equivalence Problems
Alessandro Budroni, Jesús-Javier Chi-Domínguez, Giuseppe D'Alconzo, Antonio J. Di Scala, Mukul Kulkarni
Attacks and cryptanalysis
The Linear Code Equivalence (LCE) Problem has received increased attention in recent years due to its applicability in constructing efficient digital signatures. Notably, the LESS signature scheme based on LCE is under consideration for the NIST post-quantum standardization process, along with the MEDS signature scheme that relies on an extension of LCE to the rank metric, namely Matrix Code Equivalence (MCE) Problem. Building upon these developments, a family of signatures with additional...
Improving Linear Key Recovery Attacks using Walsh Spectrum Puncturing
Antonio Flórez-Gutiérrez, Yosuke Todo
Secret-key cryptography
In some linear key recovery attacks, the function which determines the value of the linear approximation from the plaintext, ciphertext and key is replaced by a similar map in order to improve the time or memory complexity at the cost of a data complexity increase. We propose a general framework for key recovery map substitution, and introduce Walsh spectrum puncturing, which consists of removing carefully-chosen coefficients from the Walsh spectrum of this map. The capabilities of this...
Improved Linear Key Recovery Attacks on PRESENT
Wenhui Wu, Muzhou Li, Meiqin Wang
Secret-key cryptography
PRESENT is an ultra-lightweight block cipher designed by Bogdanov et al., and has been widely studied since its proposal. It supports 80-bit and 128-bit keys, which are referred as PRESENT-80 and PRESENT-128, respectively. Up to now, linear cryptanalysis is the most effective method on attacking this cipher, especially when accelerated with the pruned Walsh transform. Combing pruned Walsh transform with multiple linear attacks, one can recover the right key for 28-round PRESENT-80 and -128....
Partial Key Exposure Attack on Common Prime RSA
Mengce Zheng
Attacks and cryptanalysis
In this paper, we focus on the common prime RSA variant and introduces a novel investigation into the partial key exposure attack targeting it. We explore the vulnerability of this RSA variant, which employs two common primes $p$ and $q$ defined as $p=2ga+1$ and $q=2gb+1$ for a large prime $g$. Previous cryptanalysis of common prime RSA has primarily focused on the small private key attack. In our work, we delve deeper into the realm of partial key exposure attacks by categorizing them into...
Lattice-Based Functional Commitments: Fast Verification and Cryptanalysis
Hoeteck Wee, David J. Wu
Foundations
A functional commitment allows a user to commit to an input $\mathbf{x} \in \{0,1\}^\ell$ and later open up the commitment to a value $y = f(\mathbf{x})$ with respect to some function $f$. In this work, we focus on schemes that support fast verification. Specifically, after a preprocessing step that depends only on $f$, the verification time as well as the size of the commitment and opening should be sublinear in the input length $\ell$, We also consider the dual setting where the user...
Integral Cryptanalysis Using Algebraic Transition Matrices
Tim Beyne, Michiel Verbauwhede
Secret-key cryptography
In this work we introduce algebraic transition matrices as the basis for
a new approach to integral cryptanalysis that unifies monomial trails (Hu et al., Asiacrypt 2020) and parity sets (Boura and Canteaut, Crypto 2016). Algebraic transition matrices allow for the computation of the algebraic normal form of a primitive based on the algebraic normal forms of its components by means of well-understood operations from linear algebra. The theory of algebraic transition matrices leads to better...
Cryptanalysis of Lattice-Based Sequentiality Assumptions and Proofs of Sequential Work
Chris Peikert, Yi Tang
Attacks and cryptanalysis
This work *completely breaks* the sequentiality assumption (and broad generalizations thereof) underlying the candidate lattice-based proof of sequential work (PoSW) recently proposed by Lai and Malavolta at CRYPTO 2023.
In addition, it breaks an essentially identical variant of the PoSW, which differs from the original in only an arbitrary choice that is immaterial to the design and security proof (under the falsified assumption).
This suggests that whatever security the original PoSW may...
An Improved Method for Evaluating Secret Variables and Its Application to WAGE
Weizhe Wang, Haoyang Wang, Deng Tang
Attacks and cryptanalysis
The cube attack is a powerful cryptanalysis technique against symmetric ciphers, especially stream ciphers. The adversary aims to recover secret key bits by solving equations that involve the key. To simplify the equations, a set of plaintexts called a cube is summed up together. Traditional cube attacks use only linear or quadratic superpolies, and the size of cube is limited to an experimental range, typically around 40. However, cube attack based on division property, proposed by Todo et...
Reduction from sparse LPN to LPN, Dual Attack 3.0
Kévin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich
Public-key cryptography
The security of code-based cryptography relies primarily on the hardness of decoding generic linear codes. Until very recently, all the best algorithms for solving the decoding problem were information set decoders ($\mathsf{ISD}$). However, recently a new algorithm called RLPN-decoding which relies on a completely different approach was introduced and it has been shown that RLPN outperforms significantly $\mathsf{ISD}$ decoders for a rather large range of rates. This RLPN decoder relies on...
New Security Proofs and Complexity Records for Advanced Encryption Standard
Orhun Kara
Secret-key cryptography
Common block ciphers like AES specified by the NIST or KASUMI (A5/3) of GSM are extensively utilized by billions of individuals globally to protect their privacy and maintain confidentiality in daily communications. However, these ciphers lack comprehensive security proofs against the vast majority of known attacks. Currently, security proofs are limited to differential and linear attacks for both AES and KASUMI. For instance, the consensus on the security of AES is not based on formal...
Cryptanalysis of TS-Hash
Aleksei Udovenko
Secret-key cryptography
This note presents attacks on the lightweight hash function TS-Hash proposed by Tsaban, including a polynomial-time preimage attack for short messages (at most n/2 bits), high-probability differentials, a general subexponential-time preimage attack, and linearization techniques.
Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple Collisions
Fukang Liu, Abul Kalam, Santanu Sarkar, Willi Meier
Attacks and cryptanalysis
Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important technique in FHE to address the issue of ciphertext expansion and reduce the client-side computational overhead. To apply the transciphering framework to the CKKS FHE scheme,...
Full Round Distinguishing and Key-Recovery Attacks on SAND-2 (Full version)
Zhuolong Zhang, Shiyao Chen, Wei Wang, Meiqin Wang
Attacks and cryptanalysis
This paper presents full round distinguishing and key recovery attacks on lightweight block cipher SAND-2 with 64-bit block size and 128-bit key size, which appears to be a mixture of the AND-Rotation-XOR (AND-RX) based ciphers SAND and ANT. However, the security arguments against linear and some other attacks are not fully provided. In this paper, we find that the combination of a SAND-like nibble-based round function and ANT-like bit-based permutations will cause dependencies and lead to...
Revisiting the Boomerang Attack from a Perspective of 3-differential
Libo Wang, Ling Song, Baofeng Wu, Mostafizar Rahman, Takanori Isobe
Secret-key cryptography
In this paper, inspired by the work of Beyne and Rijmen at CRYPTO 2022, we explore the accurate probability of $d$-differential in the fixed-key model. The theoretical foundations of our method are based on a special matrix $-$ quasi-$d$-differential transition matrix, which is a natural extension of the quasidifferential transition matrix. The role of quasi-$d$-differential transition matrices in polytopic cryptananlysis is analogous to that of correlation matrices in linear cryptanalysis....
Another Look at Differential-Linear Attacks
Orr Dunkelman, Ariel Weizman
Attacks and cryptanalysis
Differential-Linear (DL) cryptanalysis is a well known cryptanalytic technique that combines differential and linear cryptanalysis. Over the years, multiple techniques were proposed to increase its strength and applicability. Two relatively recent ones are: The partitioning technique by Leurent and the use of neutral bits adapted by Beierle et al. to DL cryptanalysis.
In this paper we compare these techniques and discuss the possibility of using them together to achieve the best possible...
Revisit Two Memoryless State-Recovery Cryptanalysis Methods on A5/1
Yanbin Xu, Yonglin Hao, Mingxing Wang
Attacks and cryptanalysis
At ASIACRYPT 2019, Zhang proposed a near collision attack on A5/1 claiming to recover the 64-bit A5/1 state with a time complexity around $2^{32}$ cipher ticks with negligible memory requirements. Soon after its proposal, Zhang's near collision attack was severely challenged by Derbez \etal who claimed that Zhang's attack cannot have a time complexity lower than Golic's memoryless guess-and-determine attack dating back to EUROCRYPT 1997. In this paper, we study both the guess-and-determine...
On Linear Equivalence, Canonical Forms, and Digital Signatures
Tung Chou, Edoardo Persichetti, Paolo Santini
Public-key cryptography
The LESS signature scheme, introduced in 2020, represents a fresh research direction to obtain practical code-based signatures. LESS is based on the linear equivalence problem for codes, and the scheme is entirely described using matrices, which define both the codes, and the maps between them. It makes sense then, that the performance of the scheme depends on how efficiently such objects can be represented.
In this work, we investigate canonical forms for matrices, and how these can be...
Rigorous Foundations for Dual Attacks in Coding Theory
Charles Meyer-Hilfiger, Jean-Pierre Tillich
Attacks and cryptanalysis
Dual attacks aiming at decoding generic linear codes have been found recently to outperform for certain parameters information set decoding techniques which have been for $60$ years the dominant tool for solving this problem and choosing the parameters of code-based cryptosystems. However, the analysis of the complexity of these dual attacks relies on some unproven assumptions that are not even fully backed up with experimental evidence.
These dual attacks can actually be viewed as the...
Cryptanalysis of Elisabeth-4
Henri Gilbert, Rachelle Heim Boissier, Jérémy Jean, Jean-René Reinhard
Attacks and cryptanalysis
Elisabeth-4 is a stream cipher tailored for usage in hybrid homomorphic encryption applications that has been introduced by Cosseron et al. at ASIACRYPT 2022. In this paper, we present several variants of a key-recovery attack on the full Elisabeth-4 that break the 128-bit security claim of that cipher. Our most optimized attack is a chosen-IV attack with a time complexity of $2^{88}$ elementary operations, a memory complexity of $2^{54}$ bits and a data complexity of $2^{41}$ bits.
Our...
CSI-Otter: Isogeny-based (Partially) Blind Signatures from the Class Group Action with a Twist
Shuichi Katsumata, Yi-Fu Lai, Jason T. LeGrow, Ling Qin
Public-key cryptography
In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme.
While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure.
Specifically, our protocol does not fit into the "linear identification protocol" abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT'19), which was used to generically construct...
LOL: A Highly Flexible Framework for Designing Stream Ciphers
Dengguo Feng, Lin Jiao, Yonglin Hao, Qunxiong Zheng, Wenling Wu, Wenfeng Qi, Lei Zhang, Liting Zhang, Siwei Sun, Tian Tian
Secret-key cryptography
In this paper, we propose LOL, a general framework for designing blockwise stream ciphers, to achieve ultrafast software implementations for the ubiquitous virtual networks in 5G/6G environments and high-security level for post-quantum cryptography. The LOL framework is structurally strong, and all its components as well as the LOL framework itself enjoy high flexibility with various extensions. Following the LOL framework, we propose new stream cipher designs named LOL-MINI and LOL-DOUBLE...
Combined Fault and Leakage Resilience: Composability, Constructions and Compiler
Sebastian Berndt, Thomas Eisenbarth, Sebastian Faust, Marc Gourjon, Maximilian Orlt, Okan Seker
Real-world cryptographic implementations nowadays are not only attacked via classical cryptanalysis but also via implementation attacks, including passive attacks (observing side-channel information about the inner computation) and active attacks (inserting faults into the computation). While countermeasures exist for each type of attack, countermeasures against combined attacks have only been considered recently.
Masking is a standard technique for protecting against passive side-channel...
Algebraic Attacks on RAIN and AIM Using Equivalent Representations
Fukang Liu, Mohammad Mahzoun, Morten Øygarden, Willi Meier
Attacks and cryptanalysis
Designing novel symmetric-key primitives for advanced protocols like secure multiparty computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK), has been an important research topic in recent years. Many such existing primitives adopt quite different design strategies from conventional block ciphers. Notable features include that many of these ciphers are defined over a large finite field, and that a power map is commonly used to construct the nonlinear...
Cryptanalysis and Improvement of a Flexible and Lightweight Group Authentication Scheme
Ali Rezapour, Zahra Ahmadian
Attacks and cryptanalysis
Shamir’s secret sharing scheme is one of the substantial threshold primitives, based on which many security protocols are constructed such as group authentication schemes. Notwithstanding the unconditional security of Shamir's secret sharing scheme, protocols that are designed based on this scheme do not necessarily inherit this property. In this work, we evaluate the security of a lightweight group authentication scheme, introduced for IoT networks in IEEE IoT Journal in 2020, and prove its...
ACORN-QRE: Specification and Analysis of a Method of Generating Secure One-time Pads for Use in Encryption
Roy S Wikramaratna
Secret-key cryptography
REAMC Report-007(2023)
ACORN-QRE: Specification and Analysis of a Method of Generating Secure One-time Pads for Use in Encryption
Roy S Wikramaratna (email: rwikramaratna@gmail.com)
Abstract
The Additive Congruential Random Number (ACORN) generator is straightforward to implement; it has been demonstrated in previous papers to give rise to sequences with long period which can be proven from theoretical considerations to approximate to being uniform in up to k dimensions (for any given...
An STP-based model toward designing S-boxes with good cryptographic properties
Zhenyu Lu, Sihem Mesnager, Tingting Cui, Yanhong Fan, Meiqin Wang
Secret-key cryptography
The substitution box (S-box) is an important nonlinear component in most symmetric cryptosystems and thus should have good properties. Its difference distribution table (DDT) and linear approximation table (LAT) affect the security of the cipher against differential and linear cryptanalysis. In most previous work, differential uniformity and linearity of an S-box are two primary cryptographic properties to impact the resistance against differential and linear attacks. In some cases, the...
Cryptanalysis of rank-metric schemes based on distorted Gabidulin codes
Pierre Briaud, Pierre Loidreau
Public-key cryptography
In this work, we introduce a new attack for the Loidreau scheme [PQCrypto 2017] and its more recent variant LowMS. This attack is based on a constrained linear system for which we provide two solving approaches:
- The first one is an enumeration algorithm inspired from combinatorial attacks on the Rank Decoding (RD) Problem. While the attack technique remains very simple, it allows us to obtain the best known structural attack on the parameters of these two schemes.
- The second one is...
CryptAttackTester: high-assurance attack analysis
Daniel J. Bernstein, Tung Chou
Attacks and cryptanalysis
Quantitative analyses of the costs of cryptographic attack algorithms play a central role in comparing cryptosystems, guiding the search for improved attacks, and deciding which cryptosystems to standardize. Unfortunately, these analyses often turn out to be wrong. Sometimes errors are not caught until years later.
This paper introduces CryptAttackTester (CAT), a software framework for high-assurance quantification of attack effectiveness. CAT enforces complete definitions of attack...
The QARMAv2 Family of Tweakable Block Ciphers
Roberto Avanzi, Subhadeep Banik, Orr Dunkelman, Maria Eichlseder, Shibam Ghosh, Marcel Nageler, Francesco Regazzoni
Secret-key cryptography
We introduce the QARMAv2 family of tweakable block ciphers. It is a redesign of QARMA (from FSE 2017) to improve its security bounds and allow for longer tweaks, while keeping similar latency and area.
The wider tweak input caters to both specific use cases and the design of modes of operation with higher security bounds. This is achieved through new key and tweak schedules, revised S-Box and linear layer choices, and a more comprehensive security analysis. QARMAv2 offers competitive...
General Results of Linear Approximations over Finite Abelian Groups
Zhongfeng Niu, Siwei Sun, Hailun Yan, Qi Wang
Secret-key cryptography
In recent years, progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) motivate people to explore symmetric-key cryptographic algorithms, as well as corresponding cryptanalysis techniques (such as differential cryptanalysis, linear cryptanalysis), over general finite fields $\mathbb{F}$ or the additive group induced by $\mathbb{F}^n$. This investigation leads to the break of some MPC/FHE/ZK-friendly...
Advancing the Meet-in-the-Filter Technique: Applications to CHAM and KATAN
Alex Biryukov, Je Sen Teh, Aleksei Udovenko
Attacks and cryptanalysis
Recently, Biryukov et al. presented a new technique for key recovery in differential cryptanalysis, called meet-in-the-filter (MiF). In this work, we develop theoretical and practical aspects of the technique, which helps understanding and simplifies application. In particular, we show bounds on MiF complexity and conditions when the MiF-enhanced attack may reach them. We present a method based on trail counting which allows to estimate filtering strength of involved rounds and perform...
Simplified Modeling of MITM Attacks for Block Ciphers: new (Quantum) Attacks
André Schrottenloher, Marc Stevens
Attacks and cryptanalysis
The meet-in-the-middle (MITM) technique has led to many key-recovery attacks on block ciphers and preimage attacks on hash functions. Nowadays, cryptographers use automatic tools that reduce the search of MITM attacks to an optimization problem. Bao et al. (EUROCRYPT 2021) introduced a low-level modeling based on Mixed Integer Linear Programming (MILP) for MITM attacks on hash functions, which was extended to key-recovery attacks by Dong et al. (CRYPTO 2021). However, the modeling only...
BAKSHEESH: Similar Yet Different From GIFT
Anubhab Baksi, Jakub Breier, Anupam Chattopadhyay, Tomáš Gerlich, Sylvain Guilley, Naina Gupta, Takanori Isobe, Arpan Jati, Petr Jedlicka, Hyunjun Kim, Fukang Liu, Zdeněk Martinásek, Kosei Sakamoto, Hwajeong Seo, Rentaro Shiba, Ritu Ranjan Shrivastwa
Secret-key cryptography
We propose a lightweight block cipher named BAKSHEESH, which follows up on the popular cipher GIFT-128 (CHES'17). BAKSHEESH runs for 35 rounds, which is 12.50 percent smaller compared to GIFT-128 (runs for 40 rounds) while maintaining the same security claims against the classical attacks.
The crux of BAKSHEESH is to use a 4-bit SBox that has a non-trivial Linear Structure (LS). An SBox with one or more non-trivial LS has not been used in a cipher construction until DEFAULT...
Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives
Shiyao Chen, Chun Guo, Jian Guo, Li Liu, Meiqin Wang, Puwen Wei, Zeyu Xu
Secret-key cryptography
Symmetric-key primitives designed over the prime field $\mathbb{F}_p$ with odd characteristics, rather than the traditional $\mathbb{F}_2^{n}$, are becoming the most popular choice for MPC/FHE/ZK-protocols for better efficiencies. However, the security of $\mathbb{F}_p$ is less understood as there are highly nontrivial gaps when extending the cryptanalysis tools and experiences built on $\mathbb{F}_2^{n}$ in the past few decades to $\mathbb{F}_p$.
At CRYPTO 2015, Sun et al. established...
2023/737
Last updated: 2023-06-06
Differential properties of integer multiplication
Koustabh Ghosh, Joan Daemen
Secret-key cryptography
In this paper, we study the differential properties of integer multiplication between two $w$-bit integers, resulting in a $2w$-bit integer. Our objective is to gain insights into its resistance against differential cryptanalysis and asses its suitability as a source of non-linearity in symmetric key primitives.
On Perfect Linear Approximations and Differentials over Two-Round SPNs
Christof Beierle, Patrick Felke, Gregor Leander, Patrick Neumann, Lukas Stennes
Secret-key cryptography
Recent constructions of (tweakable) block ciphers with an embedded cryptographic backdoor relied on the existence of probability-one differentials or perfect (non-)linear approximations over a reduced-round version of the primitive. In this work, we study how the existence of probability-one differentials or perfect linear approximations over two rounds of a substitution-permutation network can be avoided by design. More precisely, we develop criteria on the s-box and the linear layer that...
Comprehensive Preimage Security Evaluations on Rijndael-based Hashing
Tianyu Zhang
Attacks and cryptanalysis
The Meet-in-the-Middle (MITM) attack is one of the most powerful cryptanalysis techniques, as seen by its use in preimage attacks on MD4, MD5, Tiger, HAVAL, and Haraka-512 v2 hash functions and key recovery for full-round KTANTAN. An efficient approach to constructing MITM attacks is automation, which refers to modeling MITM characteristics and objectives into constraints and using optimizers to search for the best attack configuration. This work focuses on the simplification and renovation...
Cryptanalysis of SPEEDY
Jinliang Wang, Chao Niu, Qun Liu, Muzhou Li, Bart Preneel, Meiqin Wang
Secret-key cryptography
SPEEDY is a family of ultra-lightweight block ciphers designed by Leander et al. at CHES 2021. There are three recommended variants denoted as SPEEDY-$r$-192 with $r$∈{5,6,7}. All of them support the 192-bit block and the 192-bit key. The main focus during its design is to ensure hardware-aware low latency, thus, whether it is designed to have enough security is worth to be studied. Recently, the full-round security of SPEEDY-7-192 is announced to be broken by Boura et al. at EUROCRYPT 2023...
Neural-Linear Attack Based on Distribution Data and Its Application on DES
Rui Zhou, Ming Duan, Qi Wang, Qianqiong Wu, Sheng Guo, Lulu Guo, Zheng Gong
Attacks and cryptanalysis
The neural-differential distinguisher proposed by Gohr boosted the development of neural aided differential attack. As another significant cryptanalysis technique, linear attack has not been developing as rapidly in combination with deep learning technology as differential attack. In 2020, Hou et al. proposed the first neural-linear attack with one bit key recovery on 3, 4 and 5-round DES and restricted multiple bits recovery on 4 rounds, where the effective bits in one plain-ciphertext pair...
A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium
Roberto La Scala, Federico Pintore, Sharwan K. Tiwari, Andrea Visconti
Foundations
In this paper we introduce a multistep generalization of the guess-and-determine or hybrid strategy for solving a system of multivariate polynomial equations over a finite field. In particular, we propose performing the exhaustive evaluation of a subset of variables stepwise, that is, by incrementing the size of such subset each time that an evaluation leads to a polynomial system which is possibly unfeasible to solve. The decision about which evaluation to extend is based on a preprocessing...
Algebraic Cryptanalysis of HADES Design Strategy: Application to POSEIDON and Poseidon2
Tomer Ashur, Thomas Buschman, Mohammad Mahzoun
Attacks and cryptanalysis
Arithmetization-Oriented primitives are the building block of advanced cryptographic protocols such as Zero-Knowledge proof systems. One approach to designing such primitives is the HADES design strategy which aims to provide an efficient way to instantiate generalizing substitution-permutation networks to include partial S-box rounds. A notable instance of HADES, introduced by Grassi \emph{et al.} at USENIX Security '21, is Poseidon. Because of its impressive efficiency and low arithmetic...
Multivariate Correlation Attacks and the Cryptanalysis of LFSR-based Stream Ciphers
Isaac A. Canales-Martínez, Igor Semaev
Attacks and cryptanalysis
Cryptanalysis of modern symmetric ciphers may be done by using linear equation systems with multiple right hand sides, which describe the encryption process. The tool was introduced by Raddum and Semaev where several solving methods were developed. In this work, the probabilities are ascribed to the right hand sides and a statistical attack is then applied. The new approach is a multivariate generalisation of the correlation attack by Siegenthaler. A fast version of the attack is provided...
A New Linear Distinguisher for Four-Round AES
Tomer Ashur, Erik Takke
Attacks and cryptanalysis
In SAC’14, Biham and Carmeli presented a novel attack on DES, involving
a variation of Partitioning Cryptanalysis. This was further extended in ToSC’18
by Biham and Perle into the Conditional Linear Cryptanalysis in the context of
Feistel ciphers. In this work, we formalize this cryptanalytic technique for block
ciphers in general and derive several properties. This conditional approximation is
then used to approximate the inv : GF(2^8) → GF(2^8) : x → x^254 function which
forms the...
SALSA PICANTE: a machine learning attack on LWE with binary secrets
Cathy Li, Jana Sotáková, Emily Wenger, Mohamed Malhou, Evrard Garcelon, Francois Charton, Kristin Lauter
Attacks and cryptanalysis
Learning with Errors (LWE) is a hard math problem underpinning many proposed post-quantum cryptographic (PQC) systems. The only PQC Key Exchange Mechanism (KEM) standardized by NIST is based on module~LWE, and current publicly available PQ Homomorphic Encryption (HE) libraries are based on ring LWE. The security of LWE-based PQ cryptosystems is critical, but certain implementation choices could weaken them. One such choice is sparse binary secrets, desirable for PQ HE schemes for efficiency...
CNF Characterization of Sets over $\mathbb{Z}_2^n$ and Its Applications in Cryptography
Hu Xiaobo, Xu Shengyuan, Tu Yinzi, Feng Xiutao
Attacks and cryptanalysis
In recent years, the automatic search has been widely used to search differential characteristics and linear approximations with high probability/correlation. Among these methods, the automatic search with the Boolean Satisfiability Problem (SAT, in short) gradually becomes a powerful cryptanalysis tool in symmetric ciphers. A key problem in the automatic search method is how to fully characterize a set $S \subseteq \{0,1\}^n$ with as few Conjunctive Normal Form (CNF, in short) clauses as...
Efficient Detection of High Probability Statistical Properties of Cryptosystems via Surrogate Differentiation
Itai Dinur, Orr Dunkelman, Nathan Keller, Eyal Ronen, Adi Shamir
Secret-key cryptography
A central problem in cryptanalysis is to find all the significant deviations from randomness in a given $n$-bit cryptographic primitive. When $n$ is small (e.g., an $8$-bit S-box), this is easy to do, but for large $n$, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems...
A MIQCP-Based Automatic Search Algorithm for Differential-Linear Trails of ARX Ciphers(Long Paper)
Guangqiu Lv, Chenhui Jin, Ting Cui
Attacks and cryptanalysis
Differential-linear (DL) cryptanalysis has undergone remarkable advancements since it was first proposed by Langford and Hellman \cite{langford1994differential} in 1994. At CRYPTO 2022, Niu et al. studied the (rotational) DL cryptanalysis of $n$-bit modulo additions with 2 inputs, i.e., $\boxplus_2$, and presented a technique for evaluating the (rotational) DL correlation of ARX ciphers. However, the problem of how to automatically search for good DL trails on ARX with solvers was left open,...
Exploiting Non-Full Key Additions: Full-Fledged Automatic Demirci-Selcuk Meet-in-the-Middle Cryptanalysis of SKINNY
Danping Shi, Siwei Sun, Ling Song, Lei Hu, Qianqian Yang
Attacks and cryptanalysis
The Demirci-Sel{\c{c}}uk meet-in-the-middle (DS-MITM) attack is
a sophisticated variant of differential attacks.
Due to its sophistication, it is hard to efficiently find the best
DS-MITM attacks on most ciphers \emph{except} for AES.
Moreover, the current automatic tools
only capture the most basic version of DS-MITM attacks, and the
critical techniques developed for enhancing the attacks
(e.g., differential enumeration and key-dependent-sieve) still rely
on manual work. In...
On Two Factors Affecting the Efficiency of MILP Models in Automated Cryptanalyses
Shengyuan Xu, Xiutao Feng, Yongxing Wang
Foundations
In recent years, mixed integer linear programming (MILP, in short) gradually becomes a popular tool of automated cryptanalyses in symmetric ciphers, which can be used to search differential characteristics and linear approximations with high probability/correlation. A key problem in the MILP method is how to build a proper model that can be solved efficiently in the MILP solvers like Gurobi or Cplex. It is known that a MILP problem is NP-hard, and the numbers of variables and inequalities...
Quantum Linear Key-recovery Attacks Using the QFT
André Schrottenloher
Attacks and cryptanalysis
The Quantum Fourier Transform is a fundamental tool in quantum cryptanalysis. In symmetric cryptanalysis, hidden shift algorithms such as Simon's (FOCS 1994), which rely on the QFT, have been used to obtain structural attacks on some very specific block ciphers. The Fourier Transform is also used in classical cryptanalysis, for example in FFT-based linear key-recovery attacks introduced by Collard et al. (ICISC 2007). Whether such techniques can be adapted to the quantum setting has remained...
Fully Automated Differential-Linear Attacks against ARX Ciphers
Emanuele Bellini, David Gerault, Juan Grados, Rusydi Makarim, Thomas Peyrin
Attacks and cryptanalysis
In this paper, we present a fully automated tool for differential-linear attacks using Mixed-Integer Linear Programming (MILP) and Mixed-Integer Quadratic Constraint Programming (MIQCP) techniques, which is, to the best of our knowledge, the very first attempt to fully automate such attacks. We use this tool to improve the correlations of the best 9 and 10-round differential-linear distinguishers on Speck32/64, and reach 11 rounds for the first time. Furthermore, we improve the latest...
TS-Hash: a lightweight cryptographic hash family based on Galois LFSRs
Itay Bookstein, Boaz Tsaban
Applications
We study a novel family of cryptographic hash functions based on Galois linear feedback shift registers (LFSRs),
and identify initial guidelines for choosing secure parameters for this family.
These hash functions are extremely simple, efficient, and suitable for implementation in
constrained environments.
A Key-Recovery Attack against Mitaka in the t-Probing Model
Thomas Prest
Attacks and cryptanalysis
Mitaka is a lattice-based signature proposed at Eurocrypt 2022. A key advertised feature of Mitaka is that it can be masked at high orders efficiently, making it attractive in scenarios where side-channel attacks are a concern. Mitaka comes with a claimed security proof in the t-probing model.
We uncover a flaw in the security proof of Mitaka, and subsequently show that it is not secure in the t-probing model. For any number of shares d ≥ 4, probing t < d variables per execution allows an...
Combining MILP Modeling with Algebraic Bias Evaluation for Linear Mask Search: Improved Fast Correlation Attacks on SNOW
Xinxin Gong, Yonglin Hao, Qingju Wang
Attacks and cryptanalysis
The Mixed Integer Linear Programming (MILP) technique has been widely applied in the realm of symmetric-key cryptanalysis. In this paper, we propose a new bitwise breakdown MILP modeling strategy for describing the linear propagation rules of modular addition-based operations. We apply such new techniques to cryptanalysis of the SNOW stream cipher family and find new linear masks:
we use the MILP model to find many linear mask candidates among which the best ones are identified with...
SoK: Modeling for Large S-boxes Oriented to Differential Probabilities and Linear Correlations (Long Paper)
Ling Sun, Meiqin Wang
Attacks and cryptanalysis
Automatic methods for differential and linear characteristic search are well-established at the moment. Typically, the designers of novel ciphers also give preliminary analytical findings for analysing the differential and linear properties using automatic techniques. However, neither MILP-based nor SAT/SMT-based approaches have fully resolved the problem of searching for actual differential and linear characteristics of ciphers with large S-boxes. To tackle the issue, we present three...
Practical Preimage Attack on 3-Round Keccak-256
Xiaoen Lin, Le He, Hongbo Yu
Attacks and cryptanalysis
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...
Systematically Quantifying Cryptanalytic Non-Linearities in Strong PUFs
Durba Chatterjee, Kuheli Pratihar, Aritra Hazra, Ulrich Rührmair, Debdeep Mukhopadhyay
Attacks and cryptanalysis
Physically Unclonable Functions~(PUFs) with large challenge space~(also called Strong PUFs) are promoted for usage in authentications and various other cryptographic and security applications. In order to qualify for these cryptographic applications, the Boolean functions realized by PUFs need to possess a high non-linearity~(NL). However, with a large challenge space~(usually $\geq 64$ bits), measuring NL by classical techniques like Walsh transformation is computationally infeasible. In...
Mind Your Path: On (Key) Dependencies in Differential Characteristics
Thomas Peyrin, Quan Quan Tan
Attacks and cryptanalysis
Cryptanalysts have been looking for differential characteristics in ciphers for
decades and it remains unclear how the subkey values and more generally the Markov
assumption impacts exactly their probability estimation. There were theoretical
efforts considering some simple linear relationships between differential characteristics
and subkey values, but the community has not yet explored many possible nonlinear
dependencies one can find in differential characteristics. Meanwhile, the...
Linear Cryptanalysis of Reduced-Round Simeck Using Super Rounds
Reham Almukhlifi, Poorvi Vora
Attacks and cryptanalysis
The Simeck family of lightweight block ciphers was proposed by Yang et al. in 2015, which combines the design features of the NSA-designed block ciphers Simon and Speck. Linear cryptanalysis using super-rounds was proposed by Almukhlifi and Vora to increase the efficiency of implementing Matsui’s second algorithm and achieved good results on all variants of Simon. The improved linear attacks result from the observation that, after four rounds of encryption, one bit of the left half of the...
Meet-in-the-Middle Preimage Attacks on Sponge-based Hashing
Lingyue Qin, Jialiang Hua, Xiaoyang Dong, Hailun Yan, Xiaoyun Wang
Secret-key cryptography
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...
Cryptanalysis of Ivanov-Krouk-Zyablov cryptosystem
Kirill Vedenev, Yury Kosolapov
Public-key cryptography
Recently, F.Ivanov, E.Krouk and V.Zyablov proposed new cryptosystem based of Generalized Reed--Solomon (GRS) codes over field extensions. In their approach, the subfield images of GRS codes are masked by a special transform, so that the resulting public codes are not equivalent to subfield images of GRS code but burst errors still can be decoded. In this paper, we show that the complexity of message-recovery attack on this cryptosystem can be reduced due to using burst errors, and the secret...
Robustness of Affine and Extended Affine Equivalent Surjective S-Box(es) against Differential Cryptanalysis
Shah Fahd, Mehreen Afzal, Dawood Shah, Waseem Iqbal, Atiya Hai
Foundations
A Feistel Network (FN) based block cipher relies on a Substitution Box (S-Box) for achieving the non-linearity. S-Box is carefully designed to achieve optimal cryptographic security bounds. The research of the last three decades shows that considerable efforts are being made on the mathematical design of an S-Box. To import the exact cryptographic profile of an S-Box, the designer focuses on the Affine Equivalent (AE) or Extended Affine (EA) equivalent S-Box. In this research, we argue that...
The Security of Quasigroups Based Substitution Permutation Networks
George Teseleanu
Secret-key cryptography
The study of symmetric structures based on quasigroups is relatively new and certain gaps can be found in the literature. In this paper, we want to fill one of these gaps. More precisely, in this work we study substitution permutation networks based on quasigroups that make use of permutation layers that are non-linear relative to the quasigroup operation. We prove that for quasigroups isotopic with a group $\mathbb{G}$, the complexity of mounting a differential attack against this type of...
Polynomial-Time Cryptanalysis of the Subspace Flooding Assumption for Post-Quantum $i\mathcal{O}$
Aayush Jain, Huijia Lin, Paul Lou, Amit Sahai
Attacks and cryptanalysis
Indistinguishability Obfuscation $(i\mathcal{O})$ is a highly versatile primitive implying a myriad advanced cryptographic applications. Up until recently, the state of feasibility of $i\mathcal{O}$ was unclear, which changed with works (Jain-Lin-Sahai STOC 2021, Jain-Lin-Sahai Eurocrypt 2022) showing that $i\mathcal{O}$ can be finally based upon well-studied hardness assumptions. Unfortunately, one of these assumptions is broken in quantum polynomial time. Luckily, the line work of...
A New Higher Order Differential of RAGHAV
Naoki Shibayama, Yasutaka Igarashi
Attacks and cryptanalysis
RAGHAV is a 64-bit block cipher proposed by Bansod in 2021. It supports 80-, and 128-bit secret keys. The designer evaluated its security against typical attack, such as differential cryptanalysis, linear cryptanalysis, and so on. On the other hand, it has not been reported the security of RAGHAV against higher order differential attack, which is one of the algebraic attacks. In this paper, we applied higher order differential cryptanalysis to RAGHAV. As a results, we found a new full-round...
Quantum Speed-Up for Multidimensional (Zero Correlation) Linear Distinguishers
Akinori Hosoyamada
Secret-key cryptography
This paper shows how to achieve a quantum speed-up for multidimensional (zero correlation) linear distinguishers.
A previous work by Kaplan et al. has already shown a quantum quadratic speed-up for one-dimensional linear distinguishers.
However, classical linear cryptanalysis often exploits multidimensional approximations to achieve more efficient attacks, and in fact it is highly non-trivial whether Kaplan et al.'s technique can be extended into the multidimensional case.
To remedy this,...
MILP-aided Cryptanalysis of the FUTURE Block Cipher
Murat Burhan İlter, Ali Aydin Selcuk
Secret-key cryptography
FUTURE is a recently proposed, lightweight block cipher. It has an AES-like, SP-based, 10-round encryption function, where, unlike most other lightweight constructions, the diffusion layer is based on an MDS matrix. Despite its relative complexity, it has a remarkable hardware performance due to careful design decisions.
In this paper, we conducted a MILP-based analysis of the cipher, where we incorporated exact probabilities rather than just the number of active S-boxes into the model....
Improved Differential and Linear Trail Bounds for ASCON
Solane El Hirch, Silvia Mella, Alireza Mehrdad, Joan Daemen
Attacks and cryptanalysis
ASCON is a family of cryptographic primitives for authenticated encryption and hashing introduced in 2015. It is selected as one of the ten finalists in the NIST Lightweight Cryptography competition. Since its introduction, ASCON has been extensively cryptanalyzed, and the results of these analyses can indicate the good resistance of this family of cryptographic primitives against known attacks, like differential and linear cryptanalysis.
Proving upper bounds for the differential...
Revisiting Higher-Order Differential-Linear Attacks from an Algebraic Perspective
Kai Hu, Thomas Peyrin, Quan Quan Tan, Trevor Yap
Secret-key cryptography
The Higher-order Differential-Linear (HDL) attack was introduced by Biham \textit{et al.} at FSE 2005, where a linear approximation was appended to a Higher-order Differential (HD) transition.
It is a natural generalization of the Differential-Linear (DL) attack.
Due to some practical restrictions, however, HDL cryptanalysis has unfortunately attracted much less attention compared to its DL counterpart since its proposal.
In this paper, we revisit HD/HDL cryptanalysis from an algebraic...
2022/1279
Last updated: 2023-04-17
Improved Neural Distinguishers with Multi-Round and Multi-Splicing Construction
Jiashuo Liu, Jiongjiong Ren, Shaozhen Chen, ManMan Li
Attacks and cryptanalysis
In CRYPTO 2019, Gohr successfully applied deep learning to differential cryptanalysis against the NSA block cipher Speck32/64, achieving higher accuracy than traditional differential distinguishers. Until now, the improvement of neural differential distinguishers is a mainstream research direction in neuralaided cryptanalysis. But the current development of training data formats for neural distinguishers forms barriers: (1) The source of data features is limited to linear combinations of...
Farasha: A Provable Permutation-based Parallelizable PRF
Najwa Aaraj, Emanuele Bellin, Ravindra Jejurikar, Marc Manzano, Raghvendra Rohit, Eugenio Salazar
Secret-key cryptography
The pseudorandom function Farfalle, proposed by Bertoni et al. at ToSC 2017, is a permutation based arbitrary length input and output PRF. At its core are the public permutations and feedback shift register based rolling functions. Being an elegant and parallelizable design, it is surprising that the security of Farfalle has been only investigated against generic cryptanalysis techniques such as differential/linear and algebraic attacks and nothing concrete about its provable security is...
DEEPAND: In-Depth Modeling of Correlated AND Gates for NLFSR-based Lightweight Block Ciphers
Amit Jana, Mostafizar Rahman, Dhiman Saha
Attacks and cryptanalysis
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...
Tighter trail bounds for Xoodoo
Joan Daemen, Silvia Mella, Gilles Van Assche
Attacks and cryptanalysis
Determining bounds on the differential probability of differential trails and
the squared correlation contribution of linear trails forms an important part of the
security evaluation of a permutation. For Xoodoo such bounds were proven with a
dedicated tool (XooTools), that scans the space of all r-round trails with weight
below a given threshold $T_r$. The search space grows exponentially with the value of
$T_r$ and XooTools appeared to have reached its limit, requiring huge amounts...
Weak Subtweakeys in SKINNY
Daniël Kuijsters, Denise Verbakel, Joan Daemen
Secret-key cryptography
Lightweight cryptography is characterized by the need for low implementation cost, while still providing sufficient security. This requires careful analysis of building blocks and their composition.
SKINNY is an ISO/IEC standardized family of tweakable block ciphers and is used in the NIST lightweight cryptography standardization process finalist Romulus. We present non-trivial linear approximations of two- round SKINNY that have correlation one or minus one and that hold for a large...
Finding All Impossible Differentials When Considering the DDT
Kai Hu, Thomas Peyrin, Meiqin Wang
Secret-key cryptography
Impossible differential (ID) cryptanalysis is one of the most important attacks on block ciphers.
The Mixed Integer Linear Programming (MILP) model is a popular method to determine whether a specific difference pair is an ID.
Unfortunately, due to the huge search space (approximately $2^{2n}$ for a cipher with a block size $n$ bits), we cannot leverage this technique to exhaust all difference pairs, which is a well-known long-standing problem.
In this paper, we propose a systematic...
Allocating Rotational Cryptanalysis based Preimage Attack on 4-round Keccak-224 for Quantum Setting
Runsong Wang, Xuelian Li, Juntao Gao, Hui Li, Baocang Wang
Attacks and cryptanalysis
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...
Deep Learning based Cryptanalysis of Lightweight Block Ciphers, Revisited
Hyunji Kim, Sejin Lim, Yeajun Kang, Wonwoong Kim, Hwajeong Seo
Attacks and cryptanalysis
Cryptanalysis is to infer the secret key of cryptography algorithm. There are brute-force attack, differential attack, linear attack, and chosen plaintext attack.
With the development of artificial intelligence, deep learning-based cryptanalysis has been actively studied. There are works in which known-plaintext attacks against lightweight block ciphers, such as S-DES, have been performed. In this paper, we propose a cryptanalysis method based on the-state-of-art deep learning technologies...
Differential Cryptanalysis in the Fixed-Key Model
Tim Beyne, Vincent Rijmen
Secret-key cryptography
A systematic approach to the fixed-key analysis of differential probabilities is proposed. It is based on the propagation of 'quasidifferential trails', which keep track of probabilistic linear relations on the values satisfying a differential characteristic in a theoretically sound way. It is shown that the fixed-key probability of a differential can be expressed as the sum of the correlations of its quasidifferential trails.
The theoretical foundations of the method are based on an...
Block Cipher's Substitution Box Generation Based on Natural Randomness in Underwater Acoustics and Knight's Tour Chain
Muhammad Fahad Khan, Khalid Saleem, Tariq Shah, Mohmmad Mazyad Hazzazi, Ismail Bahkali, Piyush Kumar Shukla
Secret-key cryptography
The protection of confidential information is a global issue and block encryption algorithms are the most reliable option for securing data. The famous information theorist, Claude Shannon has given two desirable characteristics that should exist in a strong cipher which are substitution and permutation in their fundamental research on "Communication Theory of Secrecy Systems.” block ciphers strictly follow the substitution and permutation principle in an iterative manner to generate a...
Revisiting Related-Key Boomerang attacks on AES using computer-aided tool
Patrick Derbez, Marie Euler, Pierre-Alain Fouque, Phuong Hoa Nguyen
Attacks and cryptanalysis
In recent years, several MILP models were introduced to search automatically for boomerang distinguishers and boomerang attacks on block ciphers. However, they can only be used when the key schedule is linear. Here, a new model is introduced to deal with nonlinear key schedules as it is the case for AES. This model is more complex and actually it is too slow for exhaustive search. However, when some hints are added to the solver, it found the current best related-key boomerang attack on...
New method for combining Matsui’s bounding conditions with sequential encoding method
Senpeng Wang, Dengguo Feng, Bin Hu, Jie Guan, Kai Zhang, Tairong Shi
Secret-key cryptography
As the first generic method for finding the optimal differential and linear characteristics, Matsui's branch and bound search algorithm has played an important role in evaluating the security of symmetric ciphers. By combining Matsui's bounding conditions with automatic search models, search efficiency can be improved. In this paper, by studying the properties of Matsui's bounding conditions, we give the general form of bounding conditions that can eliminate all the impossible solutions...
Cryptanalysis of Three Quantum Money Schemes
Andriyan Bilyk, Javad Doliskani, Zhiyong Gong
Public-key cryptography
We investigate the security assumptions behind three public-key quantum money schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces of the vector space $\mathbb{F}_2^n$ in 2012. It was conjectured by Pena et al in 2015 that the hard problem underlying the scheme can be solved in quasi-polynomial time. We confirm this conjecture by giving a polynomial time quantum algorithm for the underlying problem. Our algorithm is based on computing the Zariski tangent space of a...
Synthesizing Quantum Circuits of AES with Lower T-depth and Less Qubits
Zhenyu Huang, Siwei Sun
Secret-key cryptography
The significant progress in the development of quantum computers has made the study of cryptanalysis based on quantum computing an active topic. To accurately estimate the resources required to carry out quantum attacks, the involved quantum algorithms have to be synthesized into quantum circuits with basic quantum gates. In this work, we present several generic synthesis and optimization techniques for circuits implementing the quantum oracles of iterative symmetric-key ciphers that are...
Cryptanalysis of Reduced Round SPEEDY
Raghvendra Rohit, Santanu Sarkar
Secret-key cryptography
SPEEDY is a family of ultra low latency block ciphers proposed by Leander, Moos, Moradi and Rasoolzadeh at TCHES 2021. Although the designers gave some differential/linear distinguishers for reduced rounds, a concrete cryptanalysis considering key recovery attacks on SPEEDY was completely missing. The latter is crucial to understand the security margin of designs like SPEEDY which typically use low number of rounds to have low latency. In this work, we present the first third-party...
Revamped Differential-Linear Cryptanalysis on Reduced Round ChaCha
Sabyasachi Dey, Hirendra Kumar Garai, Santanu Sarkar, Nitin Kumar Sharma
Secret-key cryptography
In this paper, we provide several improvements over the existing differential-linear attacks on ChaCha. ChaCha is a stream cipher which has $20$ rounds. At CRYPTO $2020$, Beierle et al. observed a differential in the $3.5$-th round if the right pairs are chosen. They produced an improved attack using this, but showed that to achieve a right pair, we need $2^5$ iterations on average.
In this direction, we provide a technique to find the right pairs with the help of listing. Also, we provide a...
HARPOCRATES: An Approach Towards Efficient Encryption of Data-at-rest
Md Rasid Ali, Debranjan Pal, Abhijit Das, Dipanwita Roychowdhury
Secret-key cryptography
This paper proposes a new block cipher called HARPOCRATES, which is different from traditional SPN, Feistel, or ARX designs. The new design structure that we use is called the substitution convolution network. The novelty of the approach lies in that the substitution function does not use fixed S-boxes. Instead, it uses a key-driven lookup table storing a permutation of all 8-bit values. If the lookup table is sufficiently randomly shuffled, the round sub-operations achieve good confusion...
Characteristic Automated Search of Cryptographic Algorithms for Distinguishing Attacks (CASCADA)
Adrián Ranea, Vincent Rijmen
Secret-key cryptography
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...
A Bit-Vector Differential Model for the Modular Addition by a Constant and its Applications to Differential and Impossible-Differential Cryptanalysis
Seyyed Arash Azimi, Adrián Ranea, Mahmoud Salmasizadeh, Javad Mohajeri, Mohammad Reza Aref, Vincent Rijmen
Secret-key cryptography
ARX algorithms are a class of symmetric-key algorithms constructed by Addition, Rotation, and XOR. To evaluate the resistance of an ARX cipher against differential and impossible-differential cryptanalysis, the recent automated methods employ constraint satisfaction solvers to search for optimal characteristics or impossible differentials. The main difficulty in formulating this search is finding the differential models of the non-linear operations. While an efficient bit-vector differential...
New Key-Recovery Attack on Reduced-Round AES
Navid Ghaedi Bardeh, Vincent Rijmen
Secret-key cryptography
A new fundamental 4-round property of AES, called the zero-difference property, was introduced by R{\o}njom, Bardeh and Helleseth at Asiacrypt 2017. Our work characterizes it in a simple way by exploiting the notion of related differences which was introduced and well analyzed by the AES designers. We extend the 4-round property by considering some further properties of related differences over the AES linear layer, generalizing the zero-difference property. This results in a new...
A systematic method to analyze \emph{divisibility properties} is proposed. In integral cryptanalysis, divisibility properties interpolate between bits that sum to zero (divisibility by two) and saturated bits (divisibility by $2^{n - 1}$ for $2^n$ inputs). From a theoretical point of view, we construct a new cryptanalytic technique that is a non-Archimedean multiplicative analogue of linear cryptanalysis. It lifts integral cryptanalysis to characteristic zero in the sense that, if all...
The discourse herein pertains to a directional encryption cryptosystem predicated upon logarithmic signatures interconnected via a system of linear equations (we call it LINE). A logarithmic signature serves as a foundational cryptographic primitive within the algorithm, characterized by distinct cryptographic attributes including nonlinearity, noncommutativity, unidirectionality, and factorizability by key. The confidentiality of the cryptosystem is contingent upon the presence of an...
This work proposes a new white-box attack technique called filtering, which can be combined with any other trace-based attack method. The idea is to filter the traces based on the value of an intermediate variable in the implementation, aiming to fix a share of a sensitive value and degrade the security of an involved masking scheme. Coupled with LDA (filtered LDA, FLDA), it leads to an attack defeating the state-of-the-art SEL masking scheme (CHES 2021) of arbitrary degree and number of...
In white-box cryptography, early protection techniques have fallen to the automated Differential Computation Analysis attack (DCA), leading to new countermeasures and attacks. A standard side-channel countermeasure, Ishai-Sahai-Wagner's masking scheme (ISW, CRYPTO 2003) prevents Differential Computation Analysis but was shown to be vulnerable in the white-box context to the Linear Decoding Analysis attack (LDA). However, recent quadratic and cubic masking schemes by Biryukov-Udovenko...
In this study, we investigate the newly developed low energy lightweight block cipher (LELBC), specifically designed for resource-constrained Internet of Things (IoT) devices in smart agriculture. The designers conducted a preliminary differential cryptanalysis of LELBC through mixed-integer linear programming (MILP). This paper further delves into LELBC’s differential characteristics in both single and related-key frameworks using MILP, identifying a nine-round differential characteristic...
We devise algorithms for finding equivalences of trilinear forms over finite fields modulo linear group actions. Our focus is on two problems under this umbrella, Matrix Code Equivalence (MCE) and Alternating Trilinear Form Equivalence (ATFE), since their hardness is the foundation of the NIST round-$1$ signature candidates MEDS and ALTEQ respectively. We present new algorithms for MCE and ATFE, which are further developments of the algorithms for polynomial isomorphism and alternating...
The Alternating Trilinear Form Equivalence (ATFE) problem was recently used by Tang et al. as a hardness assumption in the design of a Fiat-Shamir digital signature scheme ALTEQ. The scheme was submitted to the additional round for digital signatures of the NIST standardization process for post-quantum cryptography. ATFE is a hard equivalence problem known to be in the class of equivalence problems that includes, for instance, the Tensor Isomorphism (TI), Quadratic Maps Linear...
DME is a multivariate scheme submitted to the call for additional signatures recently launched by NIST. Its performance is one of the best among all the candidates. The public key is constructed from the alternation of very structured linear and non-linear components that constitute the private key, the latter being defined over an extension field. We exploit these structures by proposing an algebraic attack which is practical on all DME parameters.
Differential cryptanalysis is an old and powerful attack against block ciphers. While different techniques have been introduced throughout the years to improve the complexity of this attack, the key recovery phase remains a tedious and error-prone procedure. In this work, we propose a new algorithm and its associated tool that permits, given a distinguisher, to output an efficient key guessing strategy. Our tool can be applied to SPN ciphers whose linear layer consists of a bit-permutation...
In this paper, we present an efficient attack against ${\tt PROV}$, a recent variant of the popular Unbalanced Oil and Vinegar (${\tt UOV}$) multivariate signature scheme, that has been submitted to the ongoing ${\tt NIST}$ standardization process for additional post-quantum signature schemes. A notable feature of ${\tt PROV}$ is its proof of security, namely, existential unforgeability under a chosen-message attack (${\tt EUF-CMA}$), assuming the hardness of solving the system formed by the...
In 1994, Langford and Hellman introduced differential-linear (DL) cryptanalysis, with the idea of decomposing the block cipher E into two parts, EU and EL, such that EU exhibits a high-probability differential trail, while EL has a high-correlation linear trail.Combining these trails forms a distinguisher for E, assuming independence between EU and EL. The dependency between the two parts of DL distinguishers remained unaddressed until EUROCRYPT 2019, where Bar-On et al. introduced the DLCT...
The Linear Code Equivalence (LCE) Problem has received increased attention in recent years due to its applicability in constructing efficient digital signatures. Notably, the LESS signature scheme based on LCE is under consideration for the NIST post-quantum standardization process, along with the MEDS signature scheme that relies on an extension of LCE to the rank metric, namely Matrix Code Equivalence (MCE) Problem. Building upon these developments, a family of signatures with additional...
In some linear key recovery attacks, the function which determines the value of the linear approximation from the plaintext, ciphertext and key is replaced by a similar map in order to improve the time or memory complexity at the cost of a data complexity increase. We propose a general framework for key recovery map substitution, and introduce Walsh spectrum puncturing, which consists of removing carefully-chosen coefficients from the Walsh spectrum of this map. The capabilities of this...
PRESENT is an ultra-lightweight block cipher designed by Bogdanov et al., and has been widely studied since its proposal. It supports 80-bit and 128-bit keys, which are referred as PRESENT-80 and PRESENT-128, respectively. Up to now, linear cryptanalysis is the most effective method on attacking this cipher, especially when accelerated with the pruned Walsh transform. Combing pruned Walsh transform with multiple linear attacks, one can recover the right key for 28-round PRESENT-80 and -128....
In this paper, we focus on the common prime RSA variant and introduces a novel investigation into the partial key exposure attack targeting it. We explore the vulnerability of this RSA variant, which employs two common primes $p$ and $q$ defined as $p=2ga+1$ and $q=2gb+1$ for a large prime $g$. Previous cryptanalysis of common prime RSA has primarily focused on the small private key attack. In our work, we delve deeper into the realm of partial key exposure attacks by categorizing them into...
A functional commitment allows a user to commit to an input $\mathbf{x} \in \{0,1\}^\ell$ and later open up the commitment to a value $y = f(\mathbf{x})$ with respect to some function $f$. In this work, we focus on schemes that support fast verification. Specifically, after a preprocessing step that depends only on $f$, the verification time as well as the size of the commitment and opening should be sublinear in the input length $\ell$, We also consider the dual setting where the user...
In this work we introduce algebraic transition matrices as the basis for a new approach to integral cryptanalysis that unifies monomial trails (Hu et al., Asiacrypt 2020) and parity sets (Boura and Canteaut, Crypto 2016). Algebraic transition matrices allow for the computation of the algebraic normal form of a primitive based on the algebraic normal forms of its components by means of well-understood operations from linear algebra. The theory of algebraic transition matrices leads to better...
This work *completely breaks* the sequentiality assumption (and broad generalizations thereof) underlying the candidate lattice-based proof of sequential work (PoSW) recently proposed by Lai and Malavolta at CRYPTO 2023. In addition, it breaks an essentially identical variant of the PoSW, which differs from the original in only an arbitrary choice that is immaterial to the design and security proof (under the falsified assumption). This suggests that whatever security the original PoSW may...
The cube attack is a powerful cryptanalysis technique against symmetric ciphers, especially stream ciphers. The adversary aims to recover secret key bits by solving equations that involve the key. To simplify the equations, a set of plaintexts called a cube is summed up together. Traditional cube attacks use only linear or quadratic superpolies, and the size of cube is limited to an experimental range, typically around 40. However, cube attack based on division property, proposed by Todo et...
The security of code-based cryptography relies primarily on the hardness of decoding generic linear codes. Until very recently, all the best algorithms for solving the decoding problem were information set decoders ($\mathsf{ISD}$). However, recently a new algorithm called RLPN-decoding which relies on a completely different approach was introduced and it has been shown that RLPN outperforms significantly $\mathsf{ISD}$ decoders for a rather large range of rates. This RLPN decoder relies on...
Common block ciphers like AES specified by the NIST or KASUMI (A5/3) of GSM are extensively utilized by billions of individuals globally to protect their privacy and maintain confidentiality in daily communications. However, these ciphers lack comprehensive security proofs against the vast majority of known attacks. Currently, security proofs are limited to differential and linear attacks for both AES and KASUMI. For instance, the consensus on the security of AES is not based on formal...
This note presents attacks on the lightweight hash function TS-Hash proposed by Tsaban, including a polynomial-time preimage attack for short messages (at most n/2 bits), high-probability differentials, a general subexponential-time preimage attack, and linearization techniques.
Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important technique in FHE to address the issue of ciphertext expansion and reduce the client-side computational overhead. To apply the transciphering framework to the CKKS FHE scheme,...
This paper presents full round distinguishing and key recovery attacks on lightweight block cipher SAND-2 with 64-bit block size and 128-bit key size, which appears to be a mixture of the AND-Rotation-XOR (AND-RX) based ciphers SAND and ANT. However, the security arguments against linear and some other attacks are not fully provided. In this paper, we find that the combination of a SAND-like nibble-based round function and ANT-like bit-based permutations will cause dependencies and lead to...
In this paper, inspired by the work of Beyne and Rijmen at CRYPTO 2022, we explore the accurate probability of $d$-differential in the fixed-key model. The theoretical foundations of our method are based on a special matrix $-$ quasi-$d$-differential transition matrix, which is a natural extension of the quasidifferential transition matrix. The role of quasi-$d$-differential transition matrices in polytopic cryptananlysis is analogous to that of correlation matrices in linear cryptanalysis....
Differential-Linear (DL) cryptanalysis is a well known cryptanalytic technique that combines differential and linear cryptanalysis. Over the years, multiple techniques were proposed to increase its strength and applicability. Two relatively recent ones are: The partitioning technique by Leurent and the use of neutral bits adapted by Beierle et al. to DL cryptanalysis. In this paper we compare these techniques and discuss the possibility of using them together to achieve the best possible...
At ASIACRYPT 2019, Zhang proposed a near collision attack on A5/1 claiming to recover the 64-bit A5/1 state with a time complexity around $2^{32}$ cipher ticks with negligible memory requirements. Soon after its proposal, Zhang's near collision attack was severely challenged by Derbez \etal who claimed that Zhang's attack cannot have a time complexity lower than Golic's memoryless guess-and-determine attack dating back to EUROCRYPT 1997. In this paper, we study both the guess-and-determine...
The LESS signature scheme, introduced in 2020, represents a fresh research direction to obtain practical code-based signatures. LESS is based on the linear equivalence problem for codes, and the scheme is entirely described using matrices, which define both the codes, and the maps between them. It makes sense then, that the performance of the scheme depends on how efficiently such objects can be represented. In this work, we investigate canonical forms for matrices, and how these can be...
Dual attacks aiming at decoding generic linear codes have been found recently to outperform for certain parameters information set decoding techniques which have been for $60$ years the dominant tool for solving this problem and choosing the parameters of code-based cryptosystems. However, the analysis of the complexity of these dual attacks relies on some unproven assumptions that are not even fully backed up with experimental evidence. These dual attacks can actually be viewed as the...
Elisabeth-4 is a stream cipher tailored for usage in hybrid homomorphic encryption applications that has been introduced by Cosseron et al. at ASIACRYPT 2022. In this paper, we present several variants of a key-recovery attack on the full Elisabeth-4 that break the 128-bit security claim of that cipher. Our most optimized attack is a chosen-IV attack with a time complexity of $2^{88}$ elementary operations, a memory complexity of $2^{54}$ bits and a data complexity of $2^{41}$ bits. Our...
In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme. While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure. Specifically, our protocol does not fit into the "linear identification protocol" abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT'19), which was used to generically construct...
In this paper, we propose LOL, a general framework for designing blockwise stream ciphers, to achieve ultrafast software implementations for the ubiquitous virtual networks in 5G/6G environments and high-security level for post-quantum cryptography. The LOL framework is structurally strong, and all its components as well as the LOL framework itself enjoy high flexibility with various extensions. Following the LOL framework, we propose new stream cipher designs named LOL-MINI and LOL-DOUBLE...
Real-world cryptographic implementations nowadays are not only attacked via classical cryptanalysis but also via implementation attacks, including passive attacks (observing side-channel information about the inner computation) and active attacks (inserting faults into the computation). While countermeasures exist for each type of attack, countermeasures against combined attacks have only been considered recently. Masking is a standard technique for protecting against passive side-channel...
Designing novel symmetric-key primitives for advanced protocols like secure multiparty computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK), has been an important research topic in recent years. Many such existing primitives adopt quite different design strategies from conventional block ciphers. Notable features include that many of these ciphers are defined over a large finite field, and that a power map is commonly used to construct the nonlinear...
Shamir’s secret sharing scheme is one of the substantial threshold primitives, based on which many security protocols are constructed such as group authentication schemes. Notwithstanding the unconditional security of Shamir's secret sharing scheme, protocols that are designed based on this scheme do not necessarily inherit this property. In this work, we evaluate the security of a lightweight group authentication scheme, introduced for IoT networks in IEEE IoT Journal in 2020, and prove its...
REAMC Report-007(2023) ACORN-QRE: Specification and Analysis of a Method of Generating Secure One-time Pads for Use in Encryption Roy S Wikramaratna (email: rwikramaratna@gmail.com) Abstract The Additive Congruential Random Number (ACORN) generator is straightforward to implement; it has been demonstrated in previous papers to give rise to sequences with long period which can be proven from theoretical considerations to approximate to being uniform in up to k dimensions (for any given...
The substitution box (S-box) is an important nonlinear component in most symmetric cryptosystems and thus should have good properties. Its difference distribution table (DDT) and linear approximation table (LAT) affect the security of the cipher against differential and linear cryptanalysis. In most previous work, differential uniformity and linearity of an S-box are two primary cryptographic properties to impact the resistance against differential and linear attacks. In some cases, the...
In this work, we introduce a new attack for the Loidreau scheme [PQCrypto 2017] and its more recent variant LowMS. This attack is based on a constrained linear system for which we provide two solving approaches: - The first one is an enumeration algorithm inspired from combinatorial attacks on the Rank Decoding (RD) Problem. While the attack technique remains very simple, it allows us to obtain the best known structural attack on the parameters of these two schemes. - The second one is...
Quantitative analyses of the costs of cryptographic attack algorithms play a central role in comparing cryptosystems, guiding the search for improved attacks, and deciding which cryptosystems to standardize. Unfortunately, these analyses often turn out to be wrong. Sometimes errors are not caught until years later. This paper introduces CryptAttackTester (CAT), a software framework for high-assurance quantification of attack effectiveness. CAT enforces complete definitions of attack...
We introduce the QARMAv2 family of tweakable block ciphers. It is a redesign of QARMA (from FSE 2017) to improve its security bounds and allow for longer tweaks, while keeping similar latency and area. The wider tweak input caters to both specific use cases and the design of modes of operation with higher security bounds. This is achieved through new key and tweak schedules, revised S-Box and linear layer choices, and a more comprehensive security analysis. QARMAv2 offers competitive...
In recent years, progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) motivate people to explore symmetric-key cryptographic algorithms, as well as corresponding cryptanalysis techniques (such as differential cryptanalysis, linear cryptanalysis), over general finite fields $\mathbb{F}$ or the additive group induced by $\mathbb{F}^n$. This investigation leads to the break of some MPC/FHE/ZK-friendly...
Recently, Biryukov et al. presented a new technique for key recovery in differential cryptanalysis, called meet-in-the-filter (MiF). In this work, we develop theoretical and practical aspects of the technique, which helps understanding and simplifies application. In particular, we show bounds on MiF complexity and conditions when the MiF-enhanced attack may reach them. We present a method based on trail counting which allows to estimate filtering strength of involved rounds and perform...
The meet-in-the-middle (MITM) technique has led to many key-recovery attacks on block ciphers and preimage attacks on hash functions. Nowadays, cryptographers use automatic tools that reduce the search of MITM attacks to an optimization problem. Bao et al. (EUROCRYPT 2021) introduced a low-level modeling based on Mixed Integer Linear Programming (MILP) for MITM attacks on hash functions, which was extended to key-recovery attacks by Dong et al. (CRYPTO 2021). However, the modeling only...
We propose a lightweight block cipher named BAKSHEESH, which follows up on the popular cipher GIFT-128 (CHES'17). BAKSHEESH runs for 35 rounds, which is 12.50 percent smaller compared to GIFT-128 (runs for 40 rounds) while maintaining the same security claims against the classical attacks. The crux of BAKSHEESH is to use a 4-bit SBox that has a non-trivial Linear Structure (LS). An SBox with one or more non-trivial LS has not been used in a cipher construction until DEFAULT...
Symmetric-key primitives designed over the prime field $\mathbb{F}_p$ with odd characteristics, rather than the traditional $\mathbb{F}_2^{n}$, are becoming the most popular choice for MPC/FHE/ZK-protocols for better efficiencies. However, the security of $\mathbb{F}_p$ is less understood as there are highly nontrivial gaps when extending the cryptanalysis tools and experiences built on $\mathbb{F}_2^{n}$ in the past few decades to $\mathbb{F}_p$. At CRYPTO 2015, Sun et al. established...
In this paper, we study the differential properties of integer multiplication between two $w$-bit integers, resulting in a $2w$-bit integer. Our objective is to gain insights into its resistance against differential cryptanalysis and asses its suitability as a source of non-linearity in symmetric key primitives.
Recent constructions of (tweakable) block ciphers with an embedded cryptographic backdoor relied on the existence of probability-one differentials or perfect (non-)linear approximations over a reduced-round version of the primitive. In this work, we study how the existence of probability-one differentials or perfect linear approximations over two rounds of a substitution-permutation network can be avoided by design. More precisely, we develop criteria on the s-box and the linear layer that...
The Meet-in-the-Middle (MITM) attack is one of the most powerful cryptanalysis techniques, as seen by its use in preimage attacks on MD4, MD5, Tiger, HAVAL, and Haraka-512 v2 hash functions and key recovery for full-round KTANTAN. An efficient approach to constructing MITM attacks is automation, which refers to modeling MITM characteristics and objectives into constraints and using optimizers to search for the best attack configuration. This work focuses on the simplification and renovation...
SPEEDY is a family of ultra-lightweight block ciphers designed by Leander et al. at CHES 2021. There are three recommended variants denoted as SPEEDY-$r$-192 with $r$∈{5,6,7}. All of them support the 192-bit block and the 192-bit key. The main focus during its design is to ensure hardware-aware low latency, thus, whether it is designed to have enough security is worth to be studied. Recently, the full-round security of SPEEDY-7-192 is announced to be broken by Boura et al. at EUROCRYPT 2023...
The neural-differential distinguisher proposed by Gohr boosted the development of neural aided differential attack. As another significant cryptanalysis technique, linear attack has not been developing as rapidly in combination with deep learning technology as differential attack. In 2020, Hou et al. proposed the first neural-linear attack with one bit key recovery on 3, 4 and 5-round DES and restricted multiple bits recovery on 4 rounds, where the effective bits in one plain-ciphertext pair...
In this paper we introduce a multistep generalization of the guess-and-determine or hybrid strategy for solving a system of multivariate polynomial equations over a finite field. In particular, we propose performing the exhaustive evaluation of a subset of variables stepwise, that is, by incrementing the size of such subset each time that an evaluation leads to a polynomial system which is possibly unfeasible to solve. The decision about which evaluation to extend is based on a preprocessing...
Arithmetization-Oriented primitives are the building block of advanced cryptographic protocols such as Zero-Knowledge proof systems. One approach to designing such primitives is the HADES design strategy which aims to provide an efficient way to instantiate generalizing substitution-permutation networks to include partial S-box rounds. A notable instance of HADES, introduced by Grassi \emph{et al.} at USENIX Security '21, is Poseidon. Because of its impressive efficiency and low arithmetic...
Cryptanalysis of modern symmetric ciphers may be done by using linear equation systems with multiple right hand sides, which describe the encryption process. The tool was introduced by Raddum and Semaev where several solving methods were developed. In this work, the probabilities are ascribed to the right hand sides and a statistical attack is then applied. The new approach is a multivariate generalisation of the correlation attack by Siegenthaler. A fast version of the attack is provided...
In SAC’14, Biham and Carmeli presented a novel attack on DES, involving a variation of Partitioning Cryptanalysis. This was further extended in ToSC’18 by Biham and Perle into the Conditional Linear Cryptanalysis in the context of Feistel ciphers. In this work, we formalize this cryptanalytic technique for block ciphers in general and derive several properties. This conditional approximation is then used to approximate the inv : GF(2^8) → GF(2^8) : x → x^254 function which forms the...
Learning with Errors (LWE) is a hard math problem underpinning many proposed post-quantum cryptographic (PQC) systems. The only PQC Key Exchange Mechanism (KEM) standardized by NIST is based on module~LWE, and current publicly available PQ Homomorphic Encryption (HE) libraries are based on ring LWE. The security of LWE-based PQ cryptosystems is critical, but certain implementation choices could weaken them. One such choice is sparse binary secrets, desirable for PQ HE schemes for efficiency...
In recent years, the automatic search has been widely used to search differential characteristics and linear approximations with high probability/correlation. Among these methods, the automatic search with the Boolean Satisfiability Problem (SAT, in short) gradually becomes a powerful cryptanalysis tool in symmetric ciphers. A key problem in the automatic search method is how to fully characterize a set $S \subseteq \{0,1\}^n$ with as few Conjunctive Normal Form (CNF, in short) clauses as...
A central problem in cryptanalysis is to find all the significant deviations from randomness in a given $n$-bit cryptographic primitive. When $n$ is small (e.g., an $8$-bit S-box), this is easy to do, but for large $n$, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems...
Differential-linear (DL) cryptanalysis has undergone remarkable advancements since it was first proposed by Langford and Hellman \cite{langford1994differential} in 1994. At CRYPTO 2022, Niu et al. studied the (rotational) DL cryptanalysis of $n$-bit modulo additions with 2 inputs, i.e., $\boxplus_2$, and presented a technique for evaluating the (rotational) DL correlation of ARX ciphers. However, the problem of how to automatically search for good DL trails on ARX with solvers was left open,...
The Demirci-Sel{\c{c}}uk meet-in-the-middle (DS-MITM) attack is a sophisticated variant of differential attacks. Due to its sophistication, it is hard to efficiently find the best DS-MITM attacks on most ciphers \emph{except} for AES. Moreover, the current automatic tools only capture the most basic version of DS-MITM attacks, and the critical techniques developed for enhancing the attacks (e.g., differential enumeration and key-dependent-sieve) still rely on manual work. In...
In recent years, mixed integer linear programming (MILP, in short) gradually becomes a popular tool of automated cryptanalyses in symmetric ciphers, which can be used to search differential characteristics and linear approximations with high probability/correlation. A key problem in the MILP method is how to build a proper model that can be solved efficiently in the MILP solvers like Gurobi or Cplex. It is known that a MILP problem is NP-hard, and the numbers of variables and inequalities...
The Quantum Fourier Transform is a fundamental tool in quantum cryptanalysis. In symmetric cryptanalysis, hidden shift algorithms such as Simon's (FOCS 1994), which rely on the QFT, have been used to obtain structural attacks on some very specific block ciphers. The Fourier Transform is also used in classical cryptanalysis, for example in FFT-based linear key-recovery attacks introduced by Collard et al. (ICISC 2007). Whether such techniques can be adapted to the quantum setting has remained...
In this paper, we present a fully automated tool for differential-linear attacks using Mixed-Integer Linear Programming (MILP) and Mixed-Integer Quadratic Constraint Programming (MIQCP) techniques, which is, to the best of our knowledge, the very first attempt to fully automate such attacks. We use this tool to improve the correlations of the best 9 and 10-round differential-linear distinguishers on Speck32/64, and reach 11 rounds for the first time. Furthermore, we improve the latest...
We study a novel family of cryptographic hash functions based on Galois linear feedback shift registers (LFSRs), and identify initial guidelines for choosing secure parameters for this family. These hash functions are extremely simple, efficient, and suitable for implementation in constrained environments.
Mitaka is a lattice-based signature proposed at Eurocrypt 2022. A key advertised feature of Mitaka is that it can be masked at high orders efficiently, making it attractive in scenarios where side-channel attacks are a concern. Mitaka comes with a claimed security proof in the t-probing model. We uncover a flaw in the security proof of Mitaka, and subsequently show that it is not secure in the t-probing model. For any number of shares d ≥ 4, probing t < d variables per execution allows an...
The Mixed Integer Linear Programming (MILP) technique has been widely applied in the realm of symmetric-key cryptanalysis. In this paper, we propose a new bitwise breakdown MILP modeling strategy for describing the linear propagation rules of modular addition-based operations. We apply such new techniques to cryptanalysis of the SNOW stream cipher family and find new linear masks: we use the MILP model to find many linear mask candidates among which the best ones are identified with...
Automatic methods for differential and linear characteristic search are well-established at the moment. Typically, the designers of novel ciphers also give preliminary analytical findings for analysing the differential and linear properties using automatic techniques. However, neither MILP-based nor SAT/SMT-based approaches have fully resolved the problem of searching for actual differential and linear characteristics of ciphers with large S-boxes. To tackle the issue, we present three...
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...
Physically Unclonable Functions~(PUFs) with large challenge space~(also called Strong PUFs) are promoted for usage in authentications and various other cryptographic and security applications. In order to qualify for these cryptographic applications, the Boolean functions realized by PUFs need to possess a high non-linearity~(NL). However, with a large challenge space~(usually $\geq 64$ bits), measuring NL by classical techniques like Walsh transformation is computationally infeasible. In...
Cryptanalysts have been looking for differential characteristics in ciphers for decades and it remains unclear how the subkey values and more generally the Markov assumption impacts exactly their probability estimation. There were theoretical efforts considering some simple linear relationships between differential characteristics and subkey values, but the community has not yet explored many possible nonlinear dependencies one can find in differential characteristics. Meanwhile, the...
The Simeck family of lightweight block ciphers was proposed by Yang et al. in 2015, which combines the design features of the NSA-designed block ciphers Simon and Speck. Linear cryptanalysis using super-rounds was proposed by Almukhlifi and Vora to increase the efficiency of implementing Matsui’s second algorithm and achieved good results on all variants of Simon. The improved linear attacks result from the observation that, after four rounds of encryption, one bit of the left half of the...
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...
Recently, F.Ivanov, E.Krouk and V.Zyablov proposed new cryptosystem based of Generalized Reed--Solomon (GRS) codes over field extensions. In their approach, the subfield images of GRS codes are masked by a special transform, so that the resulting public codes are not equivalent to subfield images of GRS code but burst errors still can be decoded. In this paper, we show that the complexity of message-recovery attack on this cryptosystem can be reduced due to using burst errors, and the secret...
A Feistel Network (FN) based block cipher relies on a Substitution Box (S-Box) for achieving the non-linearity. S-Box is carefully designed to achieve optimal cryptographic security bounds. The research of the last three decades shows that considerable efforts are being made on the mathematical design of an S-Box. To import the exact cryptographic profile of an S-Box, the designer focuses on the Affine Equivalent (AE) or Extended Affine (EA) equivalent S-Box. In this research, we argue that...
The study of symmetric structures based on quasigroups is relatively new and certain gaps can be found in the literature. In this paper, we want to fill one of these gaps. More precisely, in this work we study substitution permutation networks based on quasigroups that make use of permutation layers that are non-linear relative to the quasigroup operation. We prove that for quasigroups isotopic with a group $\mathbb{G}$, the complexity of mounting a differential attack against this type of...
Indistinguishability Obfuscation $(i\mathcal{O})$ is a highly versatile primitive implying a myriad advanced cryptographic applications. Up until recently, the state of feasibility of $i\mathcal{O}$ was unclear, which changed with works (Jain-Lin-Sahai STOC 2021, Jain-Lin-Sahai Eurocrypt 2022) showing that $i\mathcal{O}$ can be finally based upon well-studied hardness assumptions. Unfortunately, one of these assumptions is broken in quantum polynomial time. Luckily, the line work of...
RAGHAV is a 64-bit block cipher proposed by Bansod in 2021. It supports 80-, and 128-bit secret keys. The designer evaluated its security against typical attack, such as differential cryptanalysis, linear cryptanalysis, and so on. On the other hand, it has not been reported the security of RAGHAV against higher order differential attack, which is one of the algebraic attacks. In this paper, we applied higher order differential cryptanalysis to RAGHAV. As a results, we found a new full-round...
This paper shows how to achieve a quantum speed-up for multidimensional (zero correlation) linear distinguishers. A previous work by Kaplan et al. has already shown a quantum quadratic speed-up for one-dimensional linear distinguishers. However, classical linear cryptanalysis often exploits multidimensional approximations to achieve more efficient attacks, and in fact it is highly non-trivial whether Kaplan et al.'s technique can be extended into the multidimensional case. To remedy this,...
FUTURE is a recently proposed, lightweight block cipher. It has an AES-like, SP-based, 10-round encryption function, where, unlike most other lightweight constructions, the diffusion layer is based on an MDS matrix. Despite its relative complexity, it has a remarkable hardware performance due to careful design decisions. In this paper, we conducted a MILP-based analysis of the cipher, where we incorporated exact probabilities rather than just the number of active S-boxes into the model....
ASCON is a family of cryptographic primitives for authenticated encryption and hashing introduced in 2015. It is selected as one of the ten finalists in the NIST Lightweight Cryptography competition. Since its introduction, ASCON has been extensively cryptanalyzed, and the results of these analyses can indicate the good resistance of this family of cryptographic primitives against known attacks, like differential and linear cryptanalysis. Proving upper bounds for the differential...
The Higher-order Differential-Linear (HDL) attack was introduced by Biham \textit{et al.} at FSE 2005, where a linear approximation was appended to a Higher-order Differential (HD) transition. It is a natural generalization of the Differential-Linear (DL) attack. Due to some practical restrictions, however, HDL cryptanalysis has unfortunately attracted much less attention compared to its DL counterpart since its proposal. In this paper, we revisit HD/HDL cryptanalysis from an algebraic...
In CRYPTO 2019, Gohr successfully applied deep learning to differential cryptanalysis against the NSA block cipher Speck32/64, achieving higher accuracy than traditional differential distinguishers. Until now, the improvement of neural differential distinguishers is a mainstream research direction in neuralaided cryptanalysis. But the current development of training data formats for neural distinguishers forms barriers: (1) The source of data features is limited to linear combinations of...
The pseudorandom function Farfalle, proposed by Bertoni et al. at ToSC 2017, is a permutation based arbitrary length input and output PRF. At its core are the public permutations and feedback shift register based rolling functions. Being an elegant and parallelizable design, it is surprising that the security of Farfalle has been only investigated against generic cryptanalysis techniques such as differential/linear and algebraic attacks and nothing concrete about its provable security is...
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...
Determining bounds on the differential probability of differential trails and the squared correlation contribution of linear trails forms an important part of the security evaluation of a permutation. For Xoodoo such bounds were proven with a dedicated tool (XooTools), that scans the space of all r-round trails with weight below a given threshold $T_r$. The search space grows exponentially with the value of $T_r$ and XooTools appeared to have reached its limit, requiring huge amounts...
Lightweight cryptography is characterized by the need for low implementation cost, while still providing sufficient security. This requires careful analysis of building blocks and their composition. SKINNY is an ISO/IEC standardized family of tweakable block ciphers and is used in the NIST lightweight cryptography standardization process finalist Romulus. We present non-trivial linear approximations of two- round SKINNY that have correlation one or minus one and that hold for a large...
Impossible differential (ID) cryptanalysis is one of the most important attacks on block ciphers. The Mixed Integer Linear Programming (MILP) model is a popular method to determine whether a specific difference pair is an ID. Unfortunately, due to the huge search space (approximately $2^{2n}$ for a cipher with a block size $n$ bits), we cannot leverage this technique to exhaust all difference pairs, which is a well-known long-standing problem. In this paper, we propose a systematic...
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...
Cryptanalysis is to infer the secret key of cryptography algorithm. There are brute-force attack, differential attack, linear attack, and chosen plaintext attack. With the development of artificial intelligence, deep learning-based cryptanalysis has been actively studied. There are works in which known-plaintext attacks against lightweight block ciphers, such as S-DES, have been performed. In this paper, we propose a cryptanalysis method based on the-state-of-art deep learning technologies...
A systematic approach to the fixed-key analysis of differential probabilities is proposed. It is based on the propagation of 'quasidifferential trails', which keep track of probabilistic linear relations on the values satisfying a differential characteristic in a theoretically sound way. It is shown that the fixed-key probability of a differential can be expressed as the sum of the correlations of its quasidifferential trails. The theoretical foundations of the method are based on an...
The protection of confidential information is a global issue and block encryption algorithms are the most reliable option for securing data. The famous information theorist, Claude Shannon has given two desirable characteristics that should exist in a strong cipher which are substitution and permutation in their fundamental research on "Communication Theory of Secrecy Systems.” block ciphers strictly follow the substitution and permutation principle in an iterative manner to generate a...
In recent years, several MILP models were introduced to search automatically for boomerang distinguishers and boomerang attacks on block ciphers. However, they can only be used when the key schedule is linear. Here, a new model is introduced to deal with nonlinear key schedules as it is the case for AES. This model is more complex and actually it is too slow for exhaustive search. However, when some hints are added to the solver, it found the current best related-key boomerang attack on...
As the first generic method for finding the optimal differential and linear characteristics, Matsui's branch and bound search algorithm has played an important role in evaluating the security of symmetric ciphers. By combining Matsui's bounding conditions with automatic search models, search efficiency can be improved. In this paper, by studying the properties of Matsui's bounding conditions, we give the general form of bounding conditions that can eliminate all the impossible solutions...
We investigate the security assumptions behind three public-key quantum money schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces of the vector space $\mathbb{F}_2^n$ in 2012. It was conjectured by Pena et al in 2015 that the hard problem underlying the scheme can be solved in quasi-polynomial time. We confirm this conjecture by giving a polynomial time quantum algorithm for the underlying problem. Our algorithm is based on computing the Zariski tangent space of a...
The significant progress in the development of quantum computers has made the study of cryptanalysis based on quantum computing an active topic. To accurately estimate the resources required to carry out quantum attacks, the involved quantum algorithms have to be synthesized into quantum circuits with basic quantum gates. In this work, we present several generic synthesis and optimization techniques for circuits implementing the quantum oracles of iterative symmetric-key ciphers that are...
SPEEDY is a family of ultra low latency block ciphers proposed by Leander, Moos, Moradi and Rasoolzadeh at TCHES 2021. Although the designers gave some differential/linear distinguishers for reduced rounds, a concrete cryptanalysis considering key recovery attacks on SPEEDY was completely missing. The latter is crucial to understand the security margin of designs like SPEEDY which typically use low number of rounds to have low latency. In this work, we present the first third-party...
In this paper, we provide several improvements over the existing differential-linear attacks on ChaCha. ChaCha is a stream cipher which has $20$ rounds. At CRYPTO $2020$, Beierle et al. observed a differential in the $3.5$-th round if the right pairs are chosen. They produced an improved attack using this, but showed that to achieve a right pair, we need $2^5$ iterations on average. In this direction, we provide a technique to find the right pairs with the help of listing. Also, we provide a...
This paper proposes a new block cipher called HARPOCRATES, which is different from traditional SPN, Feistel, or ARX designs. The new design structure that we use is called the substitution convolution network. The novelty of the approach lies in that the substitution function does not use fixed S-boxes. Instead, it uses a key-driven lookup table storing a permutation of all 8-bit values. If the lookup table is sufficiently randomly shuffled, the round sub-operations achieve good confusion...
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...
ARX algorithms are a class of symmetric-key algorithms constructed by Addition, Rotation, and XOR. To evaluate the resistance of an ARX cipher against differential and impossible-differential cryptanalysis, the recent automated methods employ constraint satisfaction solvers to search for optimal characteristics or impossible differentials. The main difficulty in formulating this search is finding the differential models of the non-linear operations. While an efficient bit-vector differential...
A new fundamental 4-round property of AES, called the zero-difference property, was introduced by R{\o}njom, Bardeh and Helleseth at Asiacrypt 2017. Our work characterizes it in a simple way by exploiting the notion of related differences which was introduced and well analyzed by the AES designers. We extend the 4-round property by considering some further properties of related differences over the AES linear layer, generalizing the zero-difference property. This results in a new...
