111 results sorted by ID
Possible spell-corrected query: automated search
On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
Hayato Watanabe, Ryoma Ito, Toshihiro Ohigashi
Attacks and cryptanalysis
Proving resistance to conventional attacks, e.g., differential, linear, and integral attacks, is essential for designing a secure symmetric-key cipher. Recent advances in automatic search and deep learning-based methods have made this time-consuming task relatively easy, yet concerns persist over expertise requirements and potential oversights. To overcome these concerns, Kimura et al. proposed neural network-based output prediction (NN) attacks, offering simplicity, generality, and reduced...
A Deep Study of The Impossible Boomerang Distinguishers: New Construction Theory and Automatic Search Methods
Xichao Hu, Dengguo Feng, Lin Jiao, Yonglin Hao, Xinxin Gong, Yongqiang Li
Attacks and cryptanalysis
The impossible boomerang attack (IBA) is a combination of the impossible differential attack and boomerang attack, which has demonstrated remarkable power in the security evaluation of AES and other block ciphers. However, this method has not received sufficient attention in the field of symmetric cipher analysis. The only existing search method for impossible boomerang distinguishers (IBD), the core of IBAs, is the $\mathcal{UB}\text{-method}$, but it is considered rather rudimentary given...
Improved Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing
Xiaoyang Dong, Jian Guo, Shun Li, Phuong Pham, Tianyu Zhang
Attacks and cryptanalysis
The Nostradamus attack was originally proposed as a security vulnerability for a hash function by Kelsey and Kohno at EUROCRYPT 2006. It requires the attacker to commit to a hash value y of an iterated hash function H. Subsequently, upon being provided with a message prefix P, the adversary’s task is to identify a suffix S such that H(P||S) equals y. Kelsey and Kohno demonstrated a herding attack requiring $O(\sqrt{n}\cdot 2^{2n/3})$ evaluations of the compression function of H, where n...
Diving Deep into the Preimage Security of AES-like Hashing
Shiyao Chen, Jian Guo, Eik List, Danping Shi, Tianyu Zhang
Attacks and cryptanalysis
Since the seminal works by Sasaki and Aoki, Meet-in-the-Middle (MITM) attacks are recognized as an effective technique for preimage and collision attacks on hash functions. At Eurocrypt 2021, Bao et al. automated MITM attacks on AES-like hashing and improved upon the best manual result. The attack framework has been furnished by subsequent works, yet far from complete. This paper elucidates three key contributions dedicated in further generalizing the idea of MITM and refining the automatic...
New Models for the Cryptanalysis of ASCON
Mathieu Degré, Patrick Derbez, Lucie Lahaye, André Schrottenloher
Attacks and cryptanalysis
This paper focuses on the cryptanalysis of the ASCON family using automatic tools. We analyze two different problems with the goal to obtain new modelings, both simpler and less computationally heavy than previous works (all our models require only a small amount of code and run on regular desktop computers).
The first problem is the search for Meet-in-the-middle attacks on reduced-round ASCON-Hash. Starting from the MILP modeling of Qin et al. (EUROCRYPT 2023 & ePrint 2023), we rephrase...
Monte Carlo Tree Search for automatic differential characteristics search: application to SPECK
Emanuele Bellini, David Gerault, Matteo Protopapa, Matteo Rossi
Secret-key cryptography
The search for differential characteristics on block ciphers is a difficult combinatorial problem. In this paper, we investigate the performances of an AI-originated technique, Single Player Monte-Carlo Tree Search (SP-MCTS), in finding good differential characteristics on ARX ciphers, with an application to the block cipher SPECK. In order to make this approach competitive, we include several heuristics, such as the combination of forward and backward searches, and achieve significantly...
Improved Search for Integral, Impossible-Differential and Zero-Correlation Attacks: Application to Ascon, ForkSKINNY, SKINNY, MANTIS, PRESENT and QARMAv2
Hosein Hadipour, Simon Gerhalter, Sadegh Sadeghi, Maria Eichlseder
Attacks and cryptanalysis
Integral, impossible-differential (ID), and zero-correlation (ZC) attacks are three of the most important attacks on block ciphers. However, manually finding these attacks can be a daunting task, which is why automated methods are becoming increasingly important. Most automatic tools regarding integral, ZC, and ID attacks have focused only on finding distinguishers rather than complete attacks. At EUROCRYPT 2023, Hadipour et al. proposed a generic and efficient constraint programming (CP)...
Automatic Search Model for Related-Tweakey Impossible Differential Cryptanalysis
Huiqin Chen, Yongqiang Li, Xichao Hu, Zhengbin Liu, Lin Jiao, Mingsheng Wang
Secret-key cryptography
The design and analysis of dedicated tweakable block ciphers constitute a dynamic and relatively recent research field in symmetric cryptanalysis. The assessment of security in the related-tweakey model is of utmost importance owing to the existence of a public tweak. This paper proposes an automatic search model for identifying related-tweakey impossible differentials based on the propagation of states under specific constraints, which is inspired by the research of Hu et al. in ASIACRYPT...
Automatic Preimage Attack Framework on \ascon Using a Linearize-and-Guess Approach
Huina Li, Le He, Shiyao Chen, Jian Guo, Weidong Qiu
Attacks and cryptanalysis
\ascon is the final winner of the lightweight cryptography standardization competition $(2018-2023)$.
In this paper, we focus on preimage attacks against round-reduced \ascon.
The preimage attack framework, utilizing the linear structure with the allocating model, was initially proposed by Guo \textit{et al.} at ASIACRYPT 2016 and subsequently improved by Li \textit{et al.} at EUROCRYPT 2019, demonstrating high effectiveness in breaking the preimage resistance of \keccak.
In this...
Parallel SAT Framework to Find Clustering of Differential Characteristics and Its Applications
Kosei Sakamoto, Ryoma Ito, Takanori Isobe
Secret-key cryptography
The most crucial but time-consuming task for differential cryptanalysis is to find a differential with a high probability. To tackle this task, we propose a new SAT-based automatic search framework to efficiently figure out a differential with the highest probability under a specified condition. As the previous SAT methods (e.g., the Sun et al’s method proposed at ToSC 2021(1)) focused on accelerating the search for an optimal single differential characteristic, these are not optimized for...
Chosen-Key Distinguishing Attacks on Full AES-192, AES-256, Kiasu-BC, and More
Xiaoyang Dong, Shun Li, Phuong Pham
Attacks and cryptanalysis
At CRYPTO 2020, Liu et al. find that many differentials on Gimli are actually incompatible. On the related-key differential of AES, the incompatibilities also exist and are handled in different ad-hoc ways by adding respective constraints into the searching models. However, such an ad-hoc method is insufficient to rule out all the incompatibilities and may still output false positive related-key differentials. At CRYPTO 2022, a new approach combining a Constraint Programming (CP) tool and a...
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...
Classical and Quantum Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing
Zhiyu Zhang, Siwei Sun, Caibing Wang, Lei Hu
Attacks and cryptanalysis
At EUROCRYPT 2006, Kelsey and Kohno proposed the so-called chosen target forced-prefix (CTFP) preimage attack, where for any challenge prefix $P$, the attacker can generate a suffix $S$ such that $H(P\|S) = y$ for some hash value $y$ published in advance by the attacker. Consequently, the attacker can pretend to predict some event represented by $P$ she did not know before, and thus this type of attack is also known as the Nostradamus attack. At ASIACRYPT 2022, Benedikt et al. convert...
An Efficient Strategy to Construct a Better Differential on Multiple-Branch-Based Designs: Application to Orthros
Kazuma Taka, Tatusya Ishikawa, Kosei Sakamoto, Takanori Isobe
Attacks and cryptanalysis
As low-latency designs tend to have a small number of rounds to decrease latency, the differential-type cryptanalysis can become a significant threat to them.
In particular, since a multiple-branch-based design, such as Orthros can have the strong clustering effect on differential attacks due to its large internal state, it is crucial to investigate the impact of the clustering effect in such a design.
In this paper, we present a new SAT-based automatic search method for evaluating the...
2023/518
Last updated: 2024-01-18
Weak-Diffusion Structure: Meet-in-the-Middle Attacks on Sponge-based Hashing Revisited
Lingyue Qin, Boxin Zhao, Jialiang Hua, Xiaoyang Dong, Xiaoyun Wang
Secret-key cryptography
Besides the U.S. NIST standard SHA-3(Keccak), another sponge-based primitive Ascon was selected as the NIST standard for lightweight applications, recently. Exploring the security against attacks on the sponge-based hash functions is very important. At EUROCRYPT 2023, Qin et al. introduced the MitM preimage attack framework and the automatic tools for Keccak, Ascon, and Xoodyak.
In this paper, we extend Qin et al.'s MitM attack framework into collision attack and also develop various...
Evaluating the Security of Block Ciphers Against Zero-correlation Linear Attack in the Distinguishers Aspect
Xichao Hu, Yongqiang Li, Lin Jiao, Zhengbin Liu, Mingsheng Wang
Secret-key cryptography
Zero-correlation linear attack is a powerful attack of block ciphers, the lower number of rounds (LNR) which no its distinguisher (named zero-correlation linear approximation, ZCLA) exists reflects the ability of a block cipher against the zero-correlation linear attack. However, due to the large search space, showing there are no ZCLAs exist for a given block cipher under a certain number of rounds is a very hard task. Thus, present works can only prove there no ZCLAs exist in a small...
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...
Analysis of RIPEMD-160: New Collision Attacks and Finding Characteristics with MILP
Fukang Liu, Gaoli Wang, Santanu Sarkar, Ravi Anand, Willi Meier, Yingxin Li, Takanori Isobe
Attacks and cryptanalysis
The hash function RIPEMD-160 is an ISO/IEC standard and is being used to generate the bitcoin address together with SHA-256. Despite the fact that many hash functions in the MD-SHA hash family have been broken, RIPEMD-160 remains secure and the best collision attack could only reach up to 34 out of 80 rounds, which was published at CRYPTO 2019. In this paper, we propose a new collision attack on RIPEMD-160 that can reach up to 36 rounds with time complexity $2^{64.5}$. This new attack is...
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...
A Novel Automatic Technique Based on MILP to Search for Impossible Differentials
Yong Liu, Zejun Xiang, Siwei Chen, Shasha Zhang, Xiangyong Zeng
Attacks and cryptanalysis
The Mixed Integer Linear Programming (MILP) is a common method of searching for impossible differentials (IDs). However, the optimality of the distinguisher should be confirmed by an exhaustive search of all input and output differences, which is clearly computationally infeasible due to the huge search space.
In this paper, we propose a new technique that uses two-dimensional binary variables to model the input and output differences and characterize contradictions with constraints. In...
SAT-aided Automatic Search of Boomerang Distinguishers for ARX Ciphers (Long Paper)
Dachao Wang, Baocang Wang, Siwei Sun
Attacks and cryptanalysis
In Addition-Rotation-Xor (ARX) ciphers, the large domain size obstructs the application of the boomerang connectivity table. In this paper, we explore the problem of computing this table for a modular addition and the automatic search of boomerang characteristics for ARX ciphers. We provide dynamic programming algorithms to efficiently compute this table and its variants. These algorithms are the most efficient up to now. For the boomerang connectivity table, the execution time is $4^2(n −...
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...
AlgSAT --- a SAT Method for Search and Verification of Differential Characteristics from Algebraic Perspective
Huina Li, Haochen Zhang, Guozhen Liu, Kai Hu, Jian Guo, Weidong Qiu
Attacks and cryptanalysis
A good differential is a start for a successful differential attack. However, a differential might be invalid, i.e., there is no right pair following the differential, due to some contradictions in the conditions imposed by the differential. This paper presents a novel and handy method for searching and verifying differential trails from an algebraic perspective. From this algebraic perspective, exact Boolean expressions of differentials over a cryptographic primitive can be conveniently...
The SAT-Based Automatic Searching and Experimental Verification for Differential Characteristics with Application to Midori64
Yingying Li, Qichun Wang
Attacks and cryptanalysis
In this paper, we show that it is inaccurate to apply the hypothesis of independent round keys to search for differential characteristics of a block cipher with a simple key schedule. Therefore, the derived differential characteristics may be invalid. We develop a SAT-based algorithm to verify the validity of differential characteristics. Furthermore, we take the key schedule into account and thus put forward an algorithm to directly find the valid differential characteristics. All...
Finding Three-Subset Division Property for Ciphers with Complex Linear Layers (Full Version)
Debasmita Chakraborty
Attacks and cryptanalysis
Conventional bit-based division property (CBDP) and bit-
based division property using three subsets (BDPT) introduced by Todo
et al. at FSE 2016 are the most effective techniques for finding integral
characteristics of symmetric ciphers. At ASIACRYPT 2019, Wang et al.
proposed the idea of modeling the propagation of BDPT, and recently
Liu et al. described a model set method that characterized the BDPT
propagation. However, the linear layers of the block ciphers which are analyzed...
Rebound Attacks on SKINNY Hashing with Automatic Tools
Shun Li, Guozhen Liu, Phuong Pham
Attacks and cryptanalysis
In ToSC'20, a new approach combining Mix-Integer Linear Programming (MILP) tool and Constraint Programming (CP) tool to search for boomerang distinguishers is proposed and later used for rebound attack in ASIACRYPT'21 and CRYPTO'22. In this work, we extend these techniques to mount collision attacks on SKINNY-128-256 MMO hashing mode in classical and quantum settings. The first results of 17-round (and 15-round) free-start collision attack on this variant of SKINNY hashing mode are...
Simon’s Algorithm and Symmetric Crypto: Generalizations and Automatized Applications
Federico Canale, Gregor Leander, Lukas Stennes
Secret-key cryptography
In this paper we deepen our understanding of how to apply
Simon’s algorithm to break symmetric cryptographic primitives.
On the one hand, we automate the search for new attacks. Using this
approach we automatically find the first efficient key-recovery attacks
against constructions like 5-round MISTY L-FK or 5-round Feistel-FK
(with internal permutation) using Simon’s algorithm.
On the other hand, we study generalizations of Simon’s algorithm using
non-standard Hadamard matrices, with...
Throwing Boomerangs into Feistel Structures: Application to CLEFIA, WARP, LBlock, LBlock-s and TWINE
Hosein Hadipour, Marcel Nageler, Maria Eichlseder
Attacks and cryptanalysis
Automatic tools to search for boomerang distinguishers have seen significant advances over the past few years. However, most previous work has focused on ciphers based on a Substitution Permutation Network (SPN), while analyzing the Feistel structure is of great significance. Boukerrou et al. recently provided a theoretical framework to formulate the boomerang switch over multiple Feistel rounds, but they did not provide an automatic tool to find distinguishers. In this paper, by enhancing...
A Model Set Method to Search Integral Distinguishers Based on Division Property for Block Ciphers
Liu Zhang, Huawei Liu, Zilong Wang
Secret-key cryptography
In this paper, we focus on constructing an automatic search model that greatly improves efficiency with little loss of accuracy and obtains some better results in the construction of integral distinguishers for block ciphers. First, we define a new notion named BDPT Trail, which divides BDPT propagation into three parts: the division trail for K, division trail for L, and Key-Xor operation. Secondly, we improve the insufficiency of the previous methods of calculating division trails and...
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...
Related-Tweakey Impossible Differential Attack on Reduced-Round SKINNY-AEAD M1/M3
Yanhong Fan,Muzhou Li,Chao Niu,Zhenyu Lu,Meiqin Wang
Secret-key cryptography
SKINNY-AEAD is one of the second-round candidates of the Lightweight Cryptography Standardization project held by NIST. SKINNY-AEAD M1 is the primary member of six SKINNY-AEAD schemes, while SKINNY-AEAD M3 is another member with a small tag. In the design document, only security analyses of their underlying primitive SKINNY-128-384 are provided. Besides, there are no valid third-party analyses on SKINNY-AEAD M1/M3 according to our knowledge. Therefore, this paper focuses on constructing the...
A Greater GIFT: Strengthening GIFT against Statistical Cryptanalysis
Ling Sun, Bart Preneel, Wei Wang, Meiqin Wang
Secret-key cryptography
GIFT-64 is a 64-bit block cipher with a 128-bit key that is more lightweight than PRESENT. This paper provides a detailed analysis of GIFT-64 against differential and linear attacks. Our work complements automatic search methods for the best differential and linear characteristics with a careful manual analysis. This hybrid approach leads to new insights. In the differential setting, we theoretically explain the existence of differential characteristics with two active S-boxes per round and...
Exploring SAT for Cryptanalysis: (Quantum) Collision Attacks against 6-Round SHA-3 (Full Version)
Jian Guo, Guozhen Liu, Ling Song, Yi Tu
Secret-key cryptography
In this work, we focus on collision attacks against instances of SHA-3 hash family in both classical and quantum settings.
Since the 5-round collision attacks on SHA3-256 and other variants proposed by Guo et al. at JoC~2020, no other essential progress has been published.
With a thorough investigation, we identify that the challenges of extending such collision attacks on SHA-3 to more rounds lie in the inefficiency of differential trail search.
To overcome this obstacle, we develop a...
Addendum to Linear Cryptanalyses of Three AEADs with GIFT-128 as Underlying Primitives
Ling Sun, Wei Wang, Meiqin Wang
Secret-key cryptography
In ToSC 2021(2), Sun et al. implemented an automatic search with the Boolean satisfiability problem (SAT) method on GIFT-128 and identified a 19-round linear approximation with the expected linear potential being $2^{-117.43}$, which is utilised to launch a 24-round attack on the cipher. In this addendum, we discover a new 19-round linear approximation with a lower expected linear potential. However, in the attack, one more round can be appended after the distinguisher. As a result, we...
Do NOT Misuse the Markov Cipher Assumption - Automatic Search for Differential and Impossible Differential Characteristics in ARX Ciphers
Zheng Xu, Yongqiang Li, Lin Jiao, Mingsheng Wang, Willi Meier
Secret-key cryptography
Firstly, we improve the evaluation theory of differential propagation for modular additions and XORs, respectively. By introducing the concept of $additive$ $sums$ and using signed differences, we can add more information of value propagation to XOR differential propagation to calculate the probabilities of differential characteristics more precisely. Based on our theory, we propose the first modeling method to describe the general ARX differential propagation, which is not based on the...
Brute Force Cryptanalysis
Aron Gohr
Secret-key cryptography
The topic of this contribution is the cryptanalytic use of spurious keys, i.e. non-target keys returned by exhaustive key search. We show that the counting of spurious keys allows the construction of distinguishing attacks against block ciphers that are generically expected to start working at (marginally) lower computational cost than is required to find the target key by exhaustive search. We further show that if a brute force distinguisher does return a strong distinguishing signal,...
Differential Cryptanalysis of WARP
Je Sen Teh, Alex Biryukov
Secret-key cryptography
WARP is an energy-efficient lightweight block cipher that is currently the smallest 128-bit block cipher in terms of hardware. It was proposed by Banik et al. in SAC 2020 as a lightweight replacement for AES-128 without changing the mode of operation. This paper proposes key-recovery attacks on WARP based on differential cryptanalysis in single and related-key settings. We searched for differential trails for up to 20 rounds of WARP, with the first 19 having optimal differential...
Efficient and Extensive Search Linear Approximations with High for Precise Correlations of Full SNOW-V
ZhaoCun Zhou, DengGuo Feng, Bin Zhang
Secret-key cryptography
SNOW-V is a stream cipher recently designed for 5G communication system.
In this paper, we propose two efficient algorithms to evaluate the precise correlation of SNOW-V's two main nonlinear components
with linear hull effects fully considered.
Based on these algorithms, we could efficiently and extensively search much more linear masks than before.
The ideas of these algorithms can be generalized to other similar nonlinear components in symmetric cipher.
We apply our algorithms to full...
Improved Attacks on GIFT-64
Ling Sun, Wei Wang, Meiqin Wang
Secret-key cryptography
One of the well-known superiorities of GIFT-64 over PRESENT lies in the correction of the strong linear hull effect. However, apart from the investigation of the 9-round linear hull effect in the design document, we find no linear attack result on GIFT-64. Although we do not doubt the security of GIFT-64 regarding the linear cryptanalysis, the actual resistance of the cipher to the linear attack should be evaluated since it promotes a comprehensive perception of the soundness of GIFT-64....
Automatic Classical and Quantum Rebound Attacks on AES-like Hashing by Exploiting Related-key Differentials
Xiaoyang Dong, Zhiyu Zhang, Siwei Sun, Congming Wei, Xiaoyun Wang, Lei Hu
Secret-key cryptography
Collision attacks on AES-like hashing (hash functions constructed by plugging AES-like ciphers or permutations into the famous PGV modes or their variants) can be reduced to the problem of finding a pair of inputs respecting a differential of the underlying AES-like primitive whose input and output differences are the same. The rebound attack due to Mendel et al. is a powerful tool for achieving this goal, whose quantum version was first considered by Hosoyamada and Sasaki at EUROCRYPT 2020....
Improved Linear Approximations of SNOW-V and SNOW-Vi
Zhen Shi, Chenhui Jin, Yu Jin
Secret-key cryptography
Abstract. in this paper, we improve the results of linear approximation of SNOW-V and SNOW-Vi.We optimized the automatic search program by replacing the S-box part with accurate characterizations of the Walsh spectral of S-boxes, which results in a series of trails with higher correlations. On the basis of existing results, we investigate the common features of linear approximation trails with high correlation, and search for more trails by exhausting free masks. By summing up the...
A Correlation Attack on Full SNOW-V and SNOW-Vi
Zhen Shi, Chenhui Jin, Jiyan Zhang, Ting Cui, Lin Ding, Yu Jin
Secret-key cryptography
In this paper, a method for searching correlations between the binary stream of Linear Feedback Shift Register (LFSR) and the keystream of SNOW-V and SNOW-Vi is presented based on the technique of approximation to composite functions. With the aid of the linear relationship between the four taps of LFSR input into Finite State Machine (FSM) at three consecutive clocks, we present an automatic search model based on the SAT/SMT technique and search out a series of linear approximation trails...
Automatic Search for Bit-based Division Property
Shibam Ghosh, Orr Dunkelman
Secret-key cryptography
Division properties, introduced by Todo at Eurocrypt 2015,
are extremely useful in cryptanalysis, are an extension of square attack
(also called saturation attack or integral cryptanalysis). Given their im-
portance, a large number of works tried to offer automatic tools to find
division properties, primarily based on MILP or SAT/SMT. This paper
studies better modeling techniques for finding division properties using
the Constraint Programming and SAT/SMT-based automatic tools. We
use the...
Key Guessing Strategies for Linear Key-Schedule Algorithms in Rectangle Attacks
Xiaoyang Dong, Lingyue Qin, Siwei Sun, Xiaoyun Wang
Secret-key cryptography
When generating quartets for the rectangle attacks on ciphers with linear key-schedule, we find the right quartets which may suggest key candidates have to satisfy some nonlinear relations. However, some quartets generated always violate these relations, so that they will never suggest any key candidates. Inspired by previous rectangle frameworks, we find that guessing certain key cells before generating quartets may reduce the number of invalid quartets. However, guessing a lot of
key cells...
Automatic Quantum Multi-collision Distinguishers and Rebound Attacks with Triangulation Algorithm
Zhenzhen Bao, Jian Guo, Shun Li, Phuong Pham
Secret-key cryptography
In EUROCRYPT 2020, Hosoyamada and Sasaki found that differential paths with probability $2^{-2n/3}$ can be useful in quantum collision attacks, v.s. $2^{-n/2}$ for classical collision attacks. This observation led to attacks for more rounds on some AES-like hash functions. In this paper, we quantize the multi-collision distinguisher proposed by Biryukov, Khovratovich, and Nikoli{\'c} at CRYPTO 2009, and propose quantum multi-collision distinguishers. We use CP-tool to automatically search...
Linear Cryptanalyses of Three AEADs with GIFT-128 as Underlying Primitives
Ling Sun, Wei Wang, Meiqin Wang
Secret-key cryptography
This paper considers the linear cryptanalyses of Authenticated Encryptions with Associated Data (AEADs) GIFT-COFB, SUNDAE-GIFT, and HyENA. All of these proposals take GIFT-128 as underlying primitives. The automatic search with the Boolean satisfiability problem (SAT) method is implemented to search for linear approximations that match the attack settings concerning these primitives. With the newly identified approximations, we launch key-recovery attacks on GIFT-COFB, SUNDAE-GIFT, and HyENA...
Automated Search Oriented to Key Recovery on Ciphers with Linear Key Schedule: Applications to Boomerangs in SKINNY and ForkSkinny
Lingyue Qin, Xiaoyang Dong, Xiaoyun Wang, Keting Jia, Yunwen Liu
Secret-key cryptography
Automatic modelling to search distinguishers with high probability covering as many rounds as possible, such as MILP, SAT/SMT, CP models, has become a very popular cryptanalysis topic today. In those models, the optimizing objective is usually the probability or the number of rounds of the distinguishers. If we want to recover the secret key for a round-reduced block cipher, there are usually two phases, i.e., finding an efficient distinguisher and performing key-recovery attack by...
On MILP-based Automatic Search for Bit-Based Division Property for Ciphers with (large) Linear Layers
Muhammad ElSheikh, Amr M. Youssef
Secret-key cryptography
With the introduction of the division trail, the bit-based division property (BDP) has become the most efficient method to search for integral distinguishers. The notation of the division trail allows us to automate the search process by modelling the propagation of the DBP as a set of constraints that can be solved using generic Mixed-integer linear programming (MILP) and SMT/SAT solvers. The current models for the basic operations and Sboxes are efficient and accurate. In contrast, the two...
2021/452
Last updated: 2021-08-02
SAT-based Method to Improve Neural Distinguisher and Applications to SIMON
Zezhou Hou, Jiongjiong Ren, Shaozhen Chen
Cryptanalysis based on deep learning has become a hotspot in the international cryptography community since it was proposed. The key point of differential cryptanalysis based on deep learning is to find a neural differential distinguisher with longer rounds or higher probability. Therefore it is important to research how to improve the accuracy and the rounds of neural differential distinguisher. In this paper, we design SAT-based algorithms to find a good input difference so that the...
Accelerating the Search of Differential and Linear Characteristics with the SAT Method
Ling Sun, Wei Wang, Meiqin Wang
Secret-key cryptography
The introduction of the automatic search boosts the cryptanalysis of symmetric-key primitives to some degree. However, the performance of the automatic search is not always satisfactory for the search of long trails or ciphers with large state sizes. Compared with the extensive attention on the enhancement for the search with the mixed integer linear programming (MILP) method, few works care for the acceleration of the automatic search with the Boolean satisfiability problem (SAT) or...
Quantum Search for Lightweight Block Ciphers: GIFT, SKINNY, SATURNIN
Subodh Bijwe, Amit Kumar Chauhan, Somitra Kumar Sanadhya
Secret-key cryptography
Grover's search algorithm gives a quantum attack against block ciphers with query complexity $O(\sqrt{N})$ to search a keyspace of size $N$, when given a sufficient number of plaintext-ciphertext pairs. A recent result by Jaques et al. (EUROCRYPT 2020) presented the cost estimates of quantum key search attacks against AES under different security categories as defined in NIST's PQC standardization process. In this work, we extend their approach to lightweight block ciphers for the cost...
SKINNY with Scalpel - Comparing Tools for Differential Analysis
Stéphanie Delaune, Patrick Derbez, Paul Huynh, Marine Minier, Victor Mollimard, Charles Prud'homme
Secret-key cryptography
Evaluating resistance of ciphers against differential cryptanalysis is essential to define the number of rounds of new designs and to mount attacks derived from differential cryptanalysis.
In this paper, we compare existing automatic tools to find the best differential characteristic on the SKINNY block cipher. As
usually done in the literature, we split this search in two stages denoted by Step 1 and Step 2. In Step 1, each difference variable is abstracted with a Boolean variable and we...
Improved (Related-key) Differential Cryptanalysis on GIFT
Fulei Ji, Wentao Zhang, Chunning Zhou, Tianyou Ding
Secret-key cryptography
In this paper, we reevaluate the security of GIFT against differential cryptanalysis under both single-key scenario and related-key scenario. Firstly, we apply Matsui's algorithm to search related-key differential trails of GIFT. We add three constraints to limit the search space and search the optimal related-key differential trails on the limited search space. We obtain related-key differential trails of GIFT-64/128 for up to 15/14 rounds, which are the best results on related-key...
An Automatic Search Tool for Iterative Trails and its Application to estimation of differentials and linear hulls
Tianyou Ding, Wentao Zhang, Chunning Zhou, Fulei Ji
Secret-key cryptography
The design and cryptanalysis are the both sides from which we look at symmetric-key primitives. If a symmetric-key primitive is broken by a kind of cryptanalysis, it's definitely insecure. If a designer claims a symmetric-key primitive to be secure, one should demonstrate that the primitive resists against all known attacks. Differential and linear cryptanalysis are two of the most important kinds of cryptanalysis. To conduct a successful differential (linear) cryptanalysis, a differential...
Mind the Propagation of States New Automatic Search Tool for Impossible Differentials and Impossible Polytopic Transitions (Full Version)
Xichao Hu, Yongqiang Li, Lin Jiao, Shizhu Tian, Mingsheng Wang
Secret-key cryptography
Impossible differentials cryptanalysis and impossible polytopic cryptanalysis are the most effective approaches to estimate the security of block ciphers. However, the previous automatic search methods of their distinguishers, impossible differentials and impossible polytopic transitions, neither consider the impact of key schedule in the single-key setting and the differential property of large S-boxes, nor apply to the block ciphers with variable rotations.
Thus, unlike previous methods...
Automated enumeration of block cipher differentials: An optimized branch-and-bound GPU framework
Wei-Zhu Yeoh, Je Sen Teh, Jiageng Chen
Secret-key cryptography
Block ciphers are prevalent in various security protocols used daily such as TLS, OpenPGP, and SSH. Their primary purpose is the protection of user data, both in transit and at rest. One of the de facto methods to evaluate block cipher security is differential cryptanalysis. Differential cryptanalysis observes the propagation of input patterns (input differences) through the cipher to produce output patterns (output differences). This probabilistic propagation is known as a differential; the...
An Easy-to-Use Tool for Rotational-XOR Cryptanalysis of ARX Block Ciphers
Adrian Ranea, Yunwen Liu, Tomer Ashur
Secret-key cryptography
An increasing number of lightweight cryptographic primitives have been published recently. Some of these proposals are ARX primitives, which have shown a great performance in software. Rotational-XOR cryptanalysis is a statistical technique to attack ARX primitives. In this paper, a computer tool to speed up and make easier the security evaluation of ARX block ciphers against rotational-XOR cryptanalysis is shown. Our tool takes a Python implementation of an ARX block cipher and...
Automatic Verification of Differential Characteristics: Application to Reduced Gimli (Full Version)
Fukang Liu, Takanori Isobe, Willi Meier
Secret-key cryptography
Since Keccak was selected as the SHA-3 standard, more and more permutation-based primitives have been proposed. Different from block ciphers, there is no round key in the underlying permutation for permutation-based primitives. Therefore, there is a higher risk for a differential characteristic of the underlying permutation to become incompatible when considering the dependency of difference transitions over different rounds. However, in most of the MILP or SAT based models to search for...
Finding Bit-Based Division Property for Ciphers with Complex Linear Layer
Kai Hu, Qingju Wang, Meiqin Wang
Secret-key cryptography
The bit-based division property (BDP) is the most effective technique for finding integral characteristics of symmetric ciphers.
Recently, automatic search tools have become one of the most popular approaches to evaluating the security of designs against many attacks.
Constraint-aided automatic tools for the BDP have been applied to
many ciphers with simple linear layers like bit-permutation.
Constructing models of complex linear layers accurately and efficiently remains hard.
A...
Automatic Search of Meet-in-the-Middle Preimage Attacks on AES-like Hashing
Zhenzhen Bao, Xiaoyang Dong, Jian Guo, Zheng Li, Danping Shi, Siwei Sun, Xiaoyun Wang
Secret-key cryptography
The Meet-in-the-Middle (MITM) preimage attack is highly effective in breaking the preimage resistance of many hash functions, including but not limited to the full MD5, HAVAL, and Tiger, and reduced SHA-0/1/2. It was also shown to be a threat to hash functions built on block ciphers like AES by Sasaki in 2011. Recently, such attacks on AES hashing modes evolved from merely using the freedom of choosing the internal state to also exploiting the freedom of choosing the message state. However,...
Modeling for Three-Subset Division Property without Unknown Subset
Yonglin Hao, Gregor Leander, Willi Meier, Yosuke Todo, Qingju Wang
Secret-key cryptography
A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently.
In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers.
However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due...
A new method for Searching Optimal Differential and Linear Trails in ARX Ciphers
Zhengbin Liu, Yongqiang Li, Lin Jiao, Mingsheng Wang
Secret-key cryptography
In this paper, we propose an automatic tool to search for optimal differential and linear trails in ARX ciphers. It's shown that a modulo addition can be divided into sequential small modulo additions with carry bit, which turns an ARX cipher into an S-box-like cipher. From this insight, we introduce the concepts of carry-bit-dependent difference distribution table (CDDT) and carry-bit-dependent linear approximation table (CLAT). Based on them, we give efficient methods to trace all possible...
Automatic Search for the Linear (hull) Characteristics of ARX Ciphers: Applied to SPECK, SPARX, Chaskey and CHAM-64 (Full Version)
Mingjiang Huang, Liming Wang
Secret-key cryptography
Linear cryptanalysis is an important evaluation method for cryptographic primitives against key recovery attack. In this paper, we revisit the Walsh transformation for linear correlation calculation of modular addition, and an efficient algorithm is proposed to construct the input-output mask space of specified correlation weight. By filtering out the impossible large correlation weights in the first round, the search space of the first round can be substantially reduced. We introduce a new...
Automatic Tool for Searching for Differential Characteristics in ARX Ciphers and Applications (Full Version)
Mingjiang Huang, Liming Wang
Secret-key cryptography
Motivated by the algorithm of differential probability calculation of Lipmaa and Moriai, we revisit the differential properties of modular addition. We propose an efficient approach to generate the input-output difference tuples with non-zero probabilities. A novel construction of combinational DDT, which makes it possible to obtain all valid output differences for fixed input differences. According to the upper bound of differential probability of modular addition, combining the...
Improving Matsui's Search Algorithm for the Best Differential/Linear Trails and its Applications for DES, DESL and GIFT
Fulei Ji, Wentao Zhang, Tianyou Ding
Secret-key cryptography
Automatic search methods have been widely used for cryptanalysis of block ciphers, especially for the most classic cryptanalysis methods -- differential and linear cryptanalysis. However, the automatic search methods, no matter based on MILP, SMT/SAT or CP techniques, can be inefficient when the search space is too large. In this paper, we improve Matsui's branch-and-bound search algorithm which is known as the first generic algorithm for finding the best differential and linear trails by...
Implementing Grover oracles for quantum key search on AES and LowMC
Samuel Jaques, Michael Naehrig, Martin Roetteler, Fernando Virdia
Secret-key cryptography
Grover's search algorithm gives a quantum attack against block ciphers by searching for a key that matches a small number of plaintext-ciphertext pairs. This attack uses $O(\sqrt{N})$ calls to the cipher to search a key space of size $N$. Previous work in the specific case of AES derived the full gate cost by analyzing quantum circuits for the cipher, but focused on minimizing the number of qubits.
In contrast, we study the cost of quantum key search attacks under a depth restriction and...
2019/935
Last updated: 2019-08-22
Interpretable Encrypted Searchable Neural Networks
Kai Chen, Zhongrui Lin, Jian Wan, Chungen Xu
Applications
In cloud security, traditional searchable encryption (SE) requires high computation and communication overhead for dynamic search and update. The clever combination of machine learning (ML) and SE may be a new way to solve this problem. This paper proposes interpretable encrypted searchable neural networks (IESNN) to explore probabilistic query, balanced index tree construction and automatic weight update in an encrypted cloud environment. In IESNN, probabilistic learning is used to obtain...
Related-Key Boomerang Attacks on GIFT with Automated Trail Search Including BCT Effect
Yunwen Liu, Yu Sasaki
Secret-key cryptography
In Eurocrypt 2018, Cid et al. proposed a novel notion called the boomerang connectivity table, which formalised the switch property in the middle round of boomerang distinguishers in a unified approach. In this paper, we present a generic model of the boomerang connectivity table with automatic search technique for the first time, and search for (related-key) boomerang distinguishers directly by combining with the search of (related-key) differential characteristics. With the technique, we...
On MILP-Based Automatic Search for Differential Trails Through Modular Additions with Application to Bel-T
Muhammad ElSheikh, Ahmed Abdelkhalek, Amr M. Youssef
Secret-key cryptography
Using modular addition as a source of nonlinearity is frequently used in many symmetric-key structures such as ARX and Lai--Massey schemes. At FSE'16, Fu \etal proposed a Mixed Integer Linear Programming (MILP)-based method to handle the propagation of differential trails through modular additions assuming
that the two inputs to the modular addition and the consecutive rounds are independent. However, this assumption does not necessarily hold. In this paper, we study the propagation of the...
Related-Tweak Statistical Saturation Cryptanalysis and Its Application on QARMA
Muzhou Li, Kai Hu, Meiqin Wang
Statistical saturation attack takes advantage of a set of plaintext with some bits fixed while the others vary randomly, and then track the evolution of a non-uniform plaintext distribution through the cipher.
Previous statistical saturation attacks are all implemented under single-key setting, and there is no public attack models under related-key/tweak setting.
In this paper, we propose a new cryptanalytic method which can be seen as related-key/tweak statistical saturation attack by...
New Automatic search method for Truncated-differential characteristics: Application to Midori, SKINNY and CRAFT
AmirHossein E. Moghaddam, Zahra Ahmadian
Secret-key cryptography
In this paper, using Mixed Integer Linear Programming, a new automatic search tool for truncated differential characteristic is presented. Our method models the problem of finding a maximal probability truncated differential characteristic, which is able to distinguish the cipher from a pseudo random permutation.
Using this method, we analyse Midori64, SKINNY64/X and CRAFT block ciphers, for all of which the existing results are improved. In all cases, the truncated differential...
The Relationship between the Construction and Solution of the MILP Models and Applications
Lingchen Li, Wenling Wu, Yafei Zheng, Lei Zhang
Secret-key cryptography
The automatic search method based on Mix-integer Linear Programming (MILP) is one of the most common tools to search the distinguishers of block ciphers. For differential analysis, the byte-oriented MILP model is usually used to count the number of differential active s-boxes and the bit-oriented MILP model is used to search the optimal differential characteristic. In this paper, we present the influences between the construction and solution of MILP models solved by Gurobi : 1). the number...
STP Models of Optimal Differential and Linear Trail for S-box Based Ciphers
Yu Liu, Huicong Liang, Muzhou Li, Luning Huang, Kai Hu, Chenhe Yang, Meiqin Wang
Automatic tools have played an important role in designing new cryptographic primitives and evaluating the security of ciphers. Simple Theorem Prover constraint solver (STP) has been used to search for differential/linear trails of ciphers. This paper proposes general STP-based models searching for differential and linear trails with the optimal probability and correlation for S-box based ciphers. In order to get trails with the best probability or correlation for ciphers with arbitrary...
Automatic Search for A Variant of Division Property Using Three Subsets (Full Version)
Kai Hu, Meiqin Wang
Secret-key cryptography
The division property proposed at Eurocrypt'15 is a novel technique to find integral distinguishers, which has been applied to most kinds of symmetric ciphers such as block ciphers, stream ciphers, and authenticated encryption,~\textit{etc}. The original division property is word-oriented, and later the bit-based one was proposed at FSE'16 to get better integral property, which is composed of conventional bit-based division property (two-subset division property) and bit-based division...
MILP-Based Automatic Differential Searches for LEA and HIGHT
Elnaz Bagherzadeh, Zahra Ahmadian
Secret-key cryptography
In this paper we use MILP technique for automatic search for differential characteristics of ARX ciphers LEA and HIGHT. We show
that the MILP model of the differential property of modular addition with one constant input can be represented with a much less number of linear inequalities compared to the general case. Benefiting from this new developed model for HIGHT block cipher, we can achieve a reduction of 112r out of 480r in the total number of linear constraints for MILP model of r-round...
Programming the Demirci-Sel{ç}uk Meet-in-the-Middle Attack with Constraints
Danping Shi, Siwei Sun, Patrick Derbez, Yosuke Todo, Bing Sun, Lei Hu
Cryptanalysis with SAT/SMT, MILP and CP has increased in popularity among symmetric-key cryptanalysts and designers due to its high degree of automation. So far, this approach covers differential, linear, impossible differential, zero-correlation, and integral cryptanalysis. However, the Demirci-Selcuk meet-in-the-middle (DS-MITM) attack is one of the most sophisticated techniques that has not been automated with this approach. By an in-depth study of Derbez and Fouque's work on DS-MITM...
MILP-Aided Related-Tweak/Key Impossible Differential Attack and Its applications to QARMA, Joltik-BC
Rui Zong, Xiaoyang Dong
Secret-key cryptography
In this paper, we study the relation of single-key impossible differentials with the related-tweakey/key ones and propose an interesting algorithm that can efficiently derive longer related-tweakey/key impossible differentials from single-key ones. With application of the MILP technique, the algorithm can be converted an automatic tool for searching related-tweakey/key impossible differentials.
We use this automatic tool to analyze QARMA-64 and give a 11-round key recovery attack, which...
Improvements for Finding Impossible Differentials of Block Cipher Structures
Yiyuan Luo, Xuejia Lai
In this paper we improve Wu and Wang's method for finding impossible differentials of block cipher structures. This improvement is more general than Wu and Wang's method that it can find more impossible differentials with less time.
We apply it on Gen-CAST256, Misty, Gen-Skipjack, Four-Cell, Gen-MARS, SMS4, MIBS, Camellia*, LBlock, E2 and SNAKE block ciphers. All impossible differentials discovered by the algorithm are the same as Wu's method. Besides, for the 8-round MIBS block cipher, we...
Automatic Search of Bit-Based Division Property for ARX Ciphers and Word-Based Division Property
Ling Sun, Wei Wang, Meiqin Wang
Division property is a generalized integral property proposed by Todo at Eurocrypt 2015. Previous tools for automatic searching are mainly based on the Mixed Integer Linear Programming (MILP) method and trace the division property propagation at the bit level. In this paper, we propose automatic tools to detect ARX ciphers' division property at the bit level and some specific ciphers' division property at the word level.
For ARX ciphers, we construct the automatic searching tool relying on...
How to Use Metaheuristics for Design of Symmetric-Key Primitives
Ivica Nikolić
Secret-key cryptography
The ultimate goal of designing a symmetric-key cryptographic primitive often can be formulated as an optimization problem. So far, these problems mainly have been solved with trivial algorithms such as brute force or random search.
We show that a more advanced and equally versatile class of search algorithms, called metaheuristics, can help to tackle optimization problems related to design of symmetric-key primitives. We use two nature-inspired metaheuristics, simulated annealing and...
The Security of SIMON-like Ciphers Against Linear Cryptanalysis
Zhengbin Liu, Yongqiang Li, Mingsheng Wang
Secret-key cryptography
In the present paper, we analyze the security of SIMON-like ciphers against linear cryptanalysis. First, an upper bound is derived on the squared correlation of SIMON-like round function. It is shown that the upper bound on the squared correlation of SIMON-like round function decreases with the Hamming weight of output mask increasing. Based on this, we derive an upper bound on the squared correlation of linear trails for SIMON and SIMECK, which is $2^{-2R+2}$ for any $R$-round linear trail....
Optimal Differential Trails in SIMON-like Ciphers
Zhengbin Liu, Yongqiang Li, Mingsheng Wang
In the present paper, we propose an automatic search algorithm for optimal differential trails in SIMON-like ciphers. First, we give a more accurate upper bound on the differential probability of SIMON-like round function. It is shown that when the Hamming weight of the input difference $\alpha$, which is denoted by $wt(\alpha)$, is less than one half of the input size, the corresponding maximum differential probability of SIMON-like round function is less than or equal to...
Efficient Differential Trail Searching Algorithm for ARX Block Ciphers
Seojin Kim, HyungChul Kang, Deukjo Hong, Jaechul Sung, Seokhie Hong
Secret-key cryptography
In this paper, we suggest an advanced method searching for differential trails of block cipher with ARX structure. We use two techniques to optimize the automatic search algorithm of differential trails suggested by Biryukov et al. and obtain 2~3 times faster results than the previous one when implemented in block cipher SPECK.
New Automatic Search Tool for Impossible Differentials and Zero-Correlation Linear Approximations
Tingting Cui, Shiyao Chen, Keting Jia, Kai Fu, Meiqin Wang
Impossible differential and zero-correlation linear cryptanalysis are two of the most powerful cryptanalysis methods in the field of symmetric key cryptography.
There are several automatic tools to search such trails for ciphers with S-boxes. These tools focus on the properties of linear layers, and idealize the underlying S-boxes, i.e., assume any input and output difference pairs are possible. In reality, such S-box never exists, and the possible output differences with any fixed input...
Cryptanalysis of Reduced-Round Midori64 Block Cipher
Xiaoyang Dong, Yanzhao Shen
Midori is a hardware-oriented lightweight block cipher designed by Banik \emph{et al.} in ASIACRYPT 2015. It has two versions according to the state sizes, i.e. Midori64 and Midori128. In this paper, we explore the security of Midori64 against truncated differential and related-key differential attacks. By studying the compact representation of Midori64, we get the branching distribution properties of almost MDS matrix used by Midori64. By applying an automatic truncated differential search...
Automatic Search for a Maximum Probability Differential Characteristic in a Substitution-Permutation Network
Arnaud BANNIER, Nicolas BODIN, Eric FILIOL
Secret-key cryptography
The algorithm presented in this paper computes a maximum probability differential characteristic in a Substitution-Permutation Network (or SPN).
Such characteristics can be used to prove that a cipher is practically secure against differential cryptanalysis or on the contrary to build the most effective possible attack.
Running in just a few second on 64 or 128-bit SPN, our algorithm is an important tool for both cryptanalists and designers of SPN.
Automatic Search of Meet-in-the-Middle and Impossible Differential Attacks
Patrick Derbez, Pierre-Alain Fouque
Tracking bits through block ciphers and optimizing attacks at hand is one of the tedious task symmetric cryptanalysts have to deal with. It would be nice if a program will automatically handle them at least for well-known attack techniques, so that cryptanalysts will only focus on finding new attacks. However, current automatic tools cannot be used as is, either because they are tailored for specific ciphers or because they only recover a specific part of the attacks and cryptographers are...
Automatic Search for Key-Bridging Technique: Applications to LBlock and TWINE (Full Version)
Li Lin, Wenling Wu, Yafei Zheng
Secret-key cryptography
Key schedules in block ciphers are often highly simplified, which causes weakness that can be exploited in many attacks. At ASIACRYPT 2011, Dunkelman et al. proposed a technique using the weakness in the key schedule of AES, called key-bridging technique, to improve the overall complexity. The advantage of key-bridging technique is that it allows the adversary to deduce some sub-key bits from some other sub-key bits, even though they are separated by many key mixing steps. Although the...
Automatic Search for the Best Trails in ARX: Application to Block Cipher \textsc{Speck}
Alex Biryukov, Vesselin Velichkov, Yann Le Corre
We propose the first adaptation of Matsui's algorithm for finding the best differential and linear trails to the class of ARX ciphers. It is based on a branch-and-bound search strategy, does not use any heuristics and returns optimal results. The practical application of the new algorithm is demonstrated on reduced round variants of block ciphers from the \textsc{Speck} family. More specifically, we report the probabilities of the best differential trails for up to 10, 9, 8, 7, and 7 rounds...
MILP-Based Automatic Search Algorithms for Differential and Linear Trails for Speck
Kai Fu, Meiqin Wang, Yinghua Guo, Siwei Sun, Lei Hu
In recent years, Mixed Integer Linear Programming (MILP) has been successfully applied in searching for differential characteristics and linear approximations in block ciphers and has produced the significant results for some ciphers such as SIMON (a family of lightweight and hardware-optimized block ciphers designed by NSA) etc.
However, in the literature, the MILP-based automatic search algorithm for differential characteristics and linear approximations is still infeasible for block...
Automatic Differential Analysis of ARX Block Ciphers with Application to SPECK and LEA
Ling Song, Zhangjie Huang, Qianqian Yang
In this paper, we focus on the automatic differential cryptanalysis of ARX block ciphers with respect to XOR-difference, and develop Mouha et al.'s framework for finding differential characteristics by adding a new method to construct long characteristics from short ones. The new method reduces the searching time a lot and makes it possible to search differential characteristics for ARX block ciphers with large word sizes such as $n=48,64$. What's more, we take the differential effect into...
Heuristic Tool for Linear Cryptanalysis with Applications to CAESAR Candidates
Christoph Dobraunig, Maria Eichlseder, Florian Mendel
Secret-key cryptography
Differential and linear cryptanalysis are the general purpose tools to analyze various cryptographic primitives. Both techniques have in common that they rely on the existence of good differential or linear characteristics. The difficulty of finding such characteristics depends on the primitive. For instance, AES is designed to be resistant against differential and linear attacks and therefore, provides upper bounds on the probability of possible linear characteristics. On the other hand, we...
Improving Local Collisions: New Attacks on Reduced SHA-256
Florian Mendel, Tomislav Nad, Martin Schläffer
Secret-key cryptography
In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-free-start collision into a collision for 31 steps with a complexity of at most $2^{65.5}$. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential...
Exhausting Demirci-Selçuk Meet-in-the-Middle Attacks against Reduced-Round AES
Patrick Derbez, Pierre-Alain Fouque
Secret-key cryptography
In this paper, we revisit Demirci and Selçuk meet-in-the-middle attacks on AES. We find a way to automatically model SPN block cipher and meet-in-the-middle attacks that allows to perform exhaustive search of this kind of attacks. This search uses the tool developed by Bouillaguet, Derbez and Fouque at CRYPTO 2011 as a subroutine to solve specific systems. We also take into account ideas introduced by Dunkelman, Keller and Shamir at ASIACRYPT 2010 which can be seen as a new tradeoff of the...
Links among Impossible Differential, Integral and Zero Correlation Linear Cryptanalysis
Bing Sun, Zhiqiang Liu, Vincent Rijmen, Ruilin Li, Lei Cheng, Qingju Wang, Hoda Alkhzaimi, Chao Li
As two important cryptanalytic methods, impossible differential cryptanalysis and integral cryptanalysis have attracted much attention in recent years. Although relations among other important cryptanalytic approaches have been investigated, the link between these two methods has been missing. The motivation in this paper is to fix this gap and establish links between impossible differential cryptanalysis and integral cryptanalysis.
Firstly, by introducing the concept of structure and dual...
Constructing Mixed-integer Programming Models whose Feasible Region is Exactly the Set of All Valid Differential Characteristics of SIMON
Siwei Sun, Lei Hu, Meiqin Wang, Peng Wang, Kexin Qiao, Xiaoshuang Ma, Danping Shi, Ling Song, Kai Fu
In IACR ePrint 2014/747, a method for constructing mixed-integer linear programming (MILP) models whose feasible regions are exactly the sets of all possible differential (or linear) characteristics for a wide range of block ciphers is presented. These models can be used to search for or enumerate differential and linear characteristics of a block cipher automatically. However, for the case of SIMON (a lightweight block cipher designed by the U.S. National Security Agency), the method...
Improved Meet-in-the-Middle Distinguisher on Feistel Schemes
Li Lin, Wenling Wu
Improved meet-in-the-middle cryptanalysis with efficient tabulation technique has been shown to be a very powerful form of cryptanalysis against SPN block ciphers. However, few literatures show the effectiveness of this cryptanalysis against Balanced-Feistel-Networks (BFN) and Generalized-Feistel-Networks (GFN) ciphers due to the stagger of affected trail and special truncated differential trail. In this paper, we describe a versatile and powerful algorithm for searching the best improved...
Improved Differential Analysis of Block Cipher PRIDE
Qianqian Yang, Lei Hu, Siwei Sun, Kexin Qiao, Ling Song, Jinyong Shan, Xiaoshuang Ma
Secret-key cryptography
In CRYPTO 2014 Albrecht \emph{et al.} brought in a 20-round iterative lightweight block
cipher PRIDE which is based on a good linear layer for achieving a
tradeoff between security and efficiency. A recent
analysis is presented by Zhao \emph{et al.}. Inspired by their work, we use an
automatic search method to find out 56 iterative differential characteristics of PRIDE, containing 24
1-round iterative characteristics, based on three of them we construct a 15-round differential and perform a...
Improved Linear (hull) Cryptanalysis of Round-reduced Versions of SIMON
Danping Shi, Lei Hu, Siwei Sun, Ling Song, Kexin Qiao, Xiaoshuang Ma
SIMON is a family of lightweight block ciphers designed by the U.S. National Security Agency (NSA) that has attracted much attention since its publication in 2013.
In this paper, we thoroughly investigate the properties of linear approximations of the bitwise AND operation with dependent input bits. By using a Mixed-integer Linear Programming based technique presented in Aasicrypt 2014 for automatic search for characteristics, we obtain improved linear characteristics for several versions of...
Proving resistance to conventional attacks, e.g., differential, linear, and integral attacks, is essential for designing a secure symmetric-key cipher. Recent advances in automatic search and deep learning-based methods have made this time-consuming task relatively easy, yet concerns persist over expertise requirements and potential oversights. To overcome these concerns, Kimura et al. proposed neural network-based output prediction (NN) attacks, offering simplicity, generality, and reduced...
The impossible boomerang attack (IBA) is a combination of the impossible differential attack and boomerang attack, which has demonstrated remarkable power in the security evaluation of AES and other block ciphers. However, this method has not received sufficient attention in the field of symmetric cipher analysis. The only existing search method for impossible boomerang distinguishers (IBD), the core of IBAs, is the $\mathcal{UB}\text{-method}$, but it is considered rather rudimentary given...
The Nostradamus attack was originally proposed as a security vulnerability for a hash function by Kelsey and Kohno at EUROCRYPT 2006. It requires the attacker to commit to a hash value y of an iterated hash function H. Subsequently, upon being provided with a message prefix P, the adversary’s task is to identify a suffix S such that H(P||S) equals y. Kelsey and Kohno demonstrated a herding attack requiring $O(\sqrt{n}\cdot 2^{2n/3})$ evaluations of the compression function of H, where n...
Since the seminal works by Sasaki and Aoki, Meet-in-the-Middle (MITM) attacks are recognized as an effective technique for preimage and collision attacks on hash functions. At Eurocrypt 2021, Bao et al. automated MITM attacks on AES-like hashing and improved upon the best manual result. The attack framework has been furnished by subsequent works, yet far from complete. This paper elucidates three key contributions dedicated in further generalizing the idea of MITM and refining the automatic...
This paper focuses on the cryptanalysis of the ASCON family using automatic tools. We analyze two different problems with the goal to obtain new modelings, both simpler and less computationally heavy than previous works (all our models require only a small amount of code and run on regular desktop computers). The first problem is the search for Meet-in-the-middle attacks on reduced-round ASCON-Hash. Starting from the MILP modeling of Qin et al. (EUROCRYPT 2023 & ePrint 2023), we rephrase...
The search for differential characteristics on block ciphers is a difficult combinatorial problem. In this paper, we investigate the performances of an AI-originated technique, Single Player Monte-Carlo Tree Search (SP-MCTS), in finding good differential characteristics on ARX ciphers, with an application to the block cipher SPECK. In order to make this approach competitive, we include several heuristics, such as the combination of forward and backward searches, and achieve significantly...
Integral, impossible-differential (ID), and zero-correlation (ZC) attacks are three of the most important attacks on block ciphers. However, manually finding these attacks can be a daunting task, which is why automated methods are becoming increasingly important. Most automatic tools regarding integral, ZC, and ID attacks have focused only on finding distinguishers rather than complete attacks. At EUROCRYPT 2023, Hadipour et al. proposed a generic and efficient constraint programming (CP)...
The design and analysis of dedicated tweakable block ciphers constitute a dynamic and relatively recent research field in symmetric cryptanalysis. The assessment of security in the related-tweakey model is of utmost importance owing to the existence of a public tweak. This paper proposes an automatic search model for identifying related-tweakey impossible differentials based on the propagation of states under specific constraints, which is inspired by the research of Hu et al. in ASIACRYPT...
\ascon is the final winner of the lightweight cryptography standardization competition $(2018-2023)$. In this paper, we focus on preimage attacks against round-reduced \ascon. The preimage attack framework, utilizing the linear structure with the allocating model, was initially proposed by Guo \textit{et al.} at ASIACRYPT 2016 and subsequently improved by Li \textit{et al.} at EUROCRYPT 2019, demonstrating high effectiveness in breaking the preimage resistance of \keccak. In this...
The most crucial but time-consuming task for differential cryptanalysis is to find a differential with a high probability. To tackle this task, we propose a new SAT-based automatic search framework to efficiently figure out a differential with the highest probability under a specified condition. As the previous SAT methods (e.g., the Sun et al’s method proposed at ToSC 2021(1)) focused on accelerating the search for an optimal single differential characteristic, these are not optimized for...
At CRYPTO 2020, Liu et al. find that many differentials on Gimli are actually incompatible. On the related-key differential of AES, the incompatibilities also exist and are handled in different ad-hoc ways by adding respective constraints into the searching models. However, such an ad-hoc method is insufficient to rule out all the incompatibilities and may still output false positive related-key differentials. At CRYPTO 2022, a new approach combining a Constraint Programming (CP) tool and a...
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...
At EUROCRYPT 2006, Kelsey and Kohno proposed the so-called chosen target forced-prefix (CTFP) preimage attack, where for any challenge prefix $P$, the attacker can generate a suffix $S$ such that $H(P\|S) = y$ for some hash value $y$ published in advance by the attacker. Consequently, the attacker can pretend to predict some event represented by $P$ she did not know before, and thus this type of attack is also known as the Nostradamus attack. At ASIACRYPT 2022, Benedikt et al. convert...
As low-latency designs tend to have a small number of rounds to decrease latency, the differential-type cryptanalysis can become a significant threat to them. In particular, since a multiple-branch-based design, such as Orthros can have the strong clustering effect on differential attacks due to its large internal state, it is crucial to investigate the impact of the clustering effect in such a design. In this paper, we present a new SAT-based automatic search method for evaluating the...
Besides the U.S. NIST standard SHA-3(Keccak), another sponge-based primitive Ascon was selected as the NIST standard for lightweight applications, recently. Exploring the security against attacks on the sponge-based hash functions is very important. At EUROCRYPT 2023, Qin et al. introduced the MitM preimage attack framework and the automatic tools for Keccak, Ascon, and Xoodyak. In this paper, we extend Qin et al.'s MitM attack framework into collision attack and also develop various...
Zero-correlation linear attack is a powerful attack of block ciphers, the lower number of rounds (LNR) which no its distinguisher (named zero-correlation linear approximation, ZCLA) exists reflects the ability of a block cipher against the zero-correlation linear attack. However, due to the large search space, showing there are no ZCLAs exist for a given block cipher under a certain number of rounds is a very hard task. Thus, present works can only prove there no ZCLAs exist in a small...
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...
The hash function RIPEMD-160 is an ISO/IEC standard and is being used to generate the bitcoin address together with SHA-256. Despite the fact that many hash functions in the MD-SHA hash family have been broken, RIPEMD-160 remains secure and the best collision attack could only reach up to 34 out of 80 rounds, which was published at CRYPTO 2019. In this paper, we propose a new collision attack on RIPEMD-160 that can reach up to 36 rounds with time complexity $2^{64.5}$. This new attack is...
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...
The Mixed Integer Linear Programming (MILP) is a common method of searching for impossible differentials (IDs). However, the optimality of the distinguisher should be confirmed by an exhaustive search of all input and output differences, which is clearly computationally infeasible due to the huge search space. In this paper, we propose a new technique that uses two-dimensional binary variables to model the input and output differences and characterize contradictions with constraints. In...
In Addition-Rotation-Xor (ARX) ciphers, the large domain size obstructs the application of the boomerang connectivity table. In this paper, we explore the problem of computing this table for a modular addition and the automatic search of boomerang characteristics for ARX ciphers. We provide dynamic programming algorithms to efficiently compute this table and its variants. These algorithms are the most efficient up to now. For the boomerang connectivity table, the execution time is $4^2(n −...
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...
A good differential is a start for a successful differential attack. However, a differential might be invalid, i.e., there is no right pair following the differential, due to some contradictions in the conditions imposed by the differential. This paper presents a novel and handy method for searching and verifying differential trails from an algebraic perspective. From this algebraic perspective, exact Boolean expressions of differentials over a cryptographic primitive can be conveniently...
In this paper, we show that it is inaccurate to apply the hypothesis of independent round keys to search for differential characteristics of a block cipher with a simple key schedule. Therefore, the derived differential characteristics may be invalid. We develop a SAT-based algorithm to verify the validity of differential characteristics. Furthermore, we take the key schedule into account and thus put forward an algorithm to directly find the valid differential characteristics. All...
Conventional bit-based division property (CBDP) and bit- based division property using three subsets (BDPT) introduced by Todo et al. at FSE 2016 are the most effective techniques for finding integral characteristics of symmetric ciphers. At ASIACRYPT 2019, Wang et al. proposed the idea of modeling the propagation of BDPT, and recently Liu et al. described a model set method that characterized the BDPT propagation. However, the linear layers of the block ciphers which are analyzed...
In ToSC'20, a new approach combining Mix-Integer Linear Programming (MILP) tool and Constraint Programming (CP) tool to search for boomerang distinguishers is proposed and later used for rebound attack in ASIACRYPT'21 and CRYPTO'22. In this work, we extend these techniques to mount collision attacks on SKINNY-128-256 MMO hashing mode in classical and quantum settings. The first results of 17-round (and 15-round) free-start collision attack on this variant of SKINNY hashing mode are...
In this paper we deepen our understanding of how to apply Simon’s algorithm to break symmetric cryptographic primitives. On the one hand, we automate the search for new attacks. Using this approach we automatically find the first efficient key-recovery attacks against constructions like 5-round MISTY L-FK or 5-round Feistel-FK (with internal permutation) using Simon’s algorithm. On the other hand, we study generalizations of Simon’s algorithm using non-standard Hadamard matrices, with...
Automatic tools to search for boomerang distinguishers have seen significant advances over the past few years. However, most previous work has focused on ciphers based on a Substitution Permutation Network (SPN), while analyzing the Feistel structure is of great significance. Boukerrou et al. recently provided a theoretical framework to formulate the boomerang switch over multiple Feistel rounds, but they did not provide an automatic tool to find distinguishers. In this paper, by enhancing...
In this paper, we focus on constructing an automatic search model that greatly improves efficiency with little loss of accuracy and obtains some better results in the construction of integral distinguishers for block ciphers. First, we define a new notion named BDPT Trail, which divides BDPT propagation into three parts: the division trail for K, division trail for L, and Key-Xor operation. Secondly, we improve the insufficiency of the previous methods of calculating division trails and...
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...
SKINNY-AEAD is one of the second-round candidates of the Lightweight Cryptography Standardization project held by NIST. SKINNY-AEAD M1 is the primary member of six SKINNY-AEAD schemes, while SKINNY-AEAD M3 is another member with a small tag. In the design document, only security analyses of their underlying primitive SKINNY-128-384 are provided. Besides, there are no valid third-party analyses on SKINNY-AEAD M1/M3 according to our knowledge. Therefore, this paper focuses on constructing the...
GIFT-64 is a 64-bit block cipher with a 128-bit key that is more lightweight than PRESENT. This paper provides a detailed analysis of GIFT-64 against differential and linear attacks. Our work complements automatic search methods for the best differential and linear characteristics with a careful manual analysis. This hybrid approach leads to new insights. In the differential setting, we theoretically explain the existence of differential characteristics with two active S-boxes per round and...
In this work, we focus on collision attacks against instances of SHA-3 hash family in both classical and quantum settings. Since the 5-round collision attacks on SHA3-256 and other variants proposed by Guo et al. at JoC~2020, no other essential progress has been published. With a thorough investigation, we identify that the challenges of extending such collision attacks on SHA-3 to more rounds lie in the inefficiency of differential trail search. To overcome this obstacle, we develop a...
In ToSC 2021(2), Sun et al. implemented an automatic search with the Boolean satisfiability problem (SAT) method on GIFT-128 and identified a 19-round linear approximation with the expected linear potential being $2^{-117.43}$, which is utilised to launch a 24-round attack on the cipher. In this addendum, we discover a new 19-round linear approximation with a lower expected linear potential. However, in the attack, one more round can be appended after the distinguisher. As a result, we...
Firstly, we improve the evaluation theory of differential propagation for modular additions and XORs, respectively. By introducing the concept of $additive$ $sums$ and using signed differences, we can add more information of value propagation to XOR differential propagation to calculate the probabilities of differential characteristics more precisely. Based on our theory, we propose the first modeling method to describe the general ARX differential propagation, which is not based on the...
The topic of this contribution is the cryptanalytic use of spurious keys, i.e. non-target keys returned by exhaustive key search. We show that the counting of spurious keys allows the construction of distinguishing attacks against block ciphers that are generically expected to start working at (marginally) lower computational cost than is required to find the target key by exhaustive search. We further show that if a brute force distinguisher does return a strong distinguishing signal,...
WARP is an energy-efficient lightweight block cipher that is currently the smallest 128-bit block cipher in terms of hardware. It was proposed by Banik et al. in SAC 2020 as a lightweight replacement for AES-128 without changing the mode of operation. This paper proposes key-recovery attacks on WARP based on differential cryptanalysis in single and related-key settings. We searched for differential trails for up to 20 rounds of WARP, with the first 19 having optimal differential...
SNOW-V is a stream cipher recently designed for 5G communication system. In this paper, we propose two efficient algorithms to evaluate the precise correlation of SNOW-V's two main nonlinear components with linear hull effects fully considered. Based on these algorithms, we could efficiently and extensively search much more linear masks than before. The ideas of these algorithms can be generalized to other similar nonlinear components in symmetric cipher. We apply our algorithms to full...
One of the well-known superiorities of GIFT-64 over PRESENT lies in the correction of the strong linear hull effect. However, apart from the investigation of the 9-round linear hull effect in the design document, we find no linear attack result on GIFT-64. Although we do not doubt the security of GIFT-64 regarding the linear cryptanalysis, the actual resistance of the cipher to the linear attack should be evaluated since it promotes a comprehensive perception of the soundness of GIFT-64....
Collision attacks on AES-like hashing (hash functions constructed by plugging AES-like ciphers or permutations into the famous PGV modes or their variants) can be reduced to the problem of finding a pair of inputs respecting a differential of the underlying AES-like primitive whose input and output differences are the same. The rebound attack due to Mendel et al. is a powerful tool for achieving this goal, whose quantum version was first considered by Hosoyamada and Sasaki at EUROCRYPT 2020....
Abstract. in this paper, we improve the results of linear approximation of SNOW-V and SNOW-Vi.We optimized the automatic search program by replacing the S-box part with accurate characterizations of the Walsh spectral of S-boxes, which results in a series of trails with higher correlations. On the basis of existing results, we investigate the common features of linear approximation trails with high correlation, and search for more trails by exhausting free masks. By summing up the...
In this paper, a method for searching correlations between the binary stream of Linear Feedback Shift Register (LFSR) and the keystream of SNOW-V and SNOW-Vi is presented based on the technique of approximation to composite functions. With the aid of the linear relationship between the four taps of LFSR input into Finite State Machine (FSM) at three consecutive clocks, we present an automatic search model based on the SAT/SMT technique and search out a series of linear approximation trails...
Division properties, introduced by Todo at Eurocrypt 2015, are extremely useful in cryptanalysis, are an extension of square attack (also called saturation attack or integral cryptanalysis). Given their im- portance, a large number of works tried to offer automatic tools to find division properties, primarily based on MILP or SAT/SMT. This paper studies better modeling techniques for finding division properties using the Constraint Programming and SAT/SMT-based automatic tools. We use the...
When generating quartets for the rectangle attacks on ciphers with linear key-schedule, we find the right quartets which may suggest key candidates have to satisfy some nonlinear relations. However, some quartets generated always violate these relations, so that they will never suggest any key candidates. Inspired by previous rectangle frameworks, we find that guessing certain key cells before generating quartets may reduce the number of invalid quartets. However, guessing a lot of key cells...
In EUROCRYPT 2020, Hosoyamada and Sasaki found that differential paths with probability $2^{-2n/3}$ can be useful in quantum collision attacks, v.s. $2^{-n/2}$ for classical collision attacks. This observation led to attacks for more rounds on some AES-like hash functions. In this paper, we quantize the multi-collision distinguisher proposed by Biryukov, Khovratovich, and Nikoli{\'c} at CRYPTO 2009, and propose quantum multi-collision distinguishers. We use CP-tool to automatically search...
This paper considers the linear cryptanalyses of Authenticated Encryptions with Associated Data (AEADs) GIFT-COFB, SUNDAE-GIFT, and HyENA. All of these proposals take GIFT-128 as underlying primitives. The automatic search with the Boolean satisfiability problem (SAT) method is implemented to search for linear approximations that match the attack settings concerning these primitives. With the newly identified approximations, we launch key-recovery attacks on GIFT-COFB, SUNDAE-GIFT, and HyENA...
Automatic modelling to search distinguishers with high probability covering as many rounds as possible, such as MILP, SAT/SMT, CP models, has become a very popular cryptanalysis topic today. In those models, the optimizing objective is usually the probability or the number of rounds of the distinguishers. If we want to recover the secret key for a round-reduced block cipher, there are usually two phases, i.e., finding an efficient distinguisher and performing key-recovery attack by...
With the introduction of the division trail, the bit-based division property (BDP) has become the most efficient method to search for integral distinguishers. The notation of the division trail allows us to automate the search process by modelling the propagation of the DBP as a set of constraints that can be solved using generic Mixed-integer linear programming (MILP) and SMT/SAT solvers. The current models for the basic operations and Sboxes are efficient and accurate. In contrast, the two...
Cryptanalysis based on deep learning has become a hotspot in the international cryptography community since it was proposed. The key point of differential cryptanalysis based on deep learning is to find a neural differential distinguisher with longer rounds or higher probability. Therefore it is important to research how to improve the accuracy and the rounds of neural differential distinguisher. In this paper, we design SAT-based algorithms to find a good input difference so that the...
The introduction of the automatic search boosts the cryptanalysis of symmetric-key primitives to some degree. However, the performance of the automatic search is not always satisfactory for the search of long trails or ciphers with large state sizes. Compared with the extensive attention on the enhancement for the search with the mixed integer linear programming (MILP) method, few works care for the acceleration of the automatic search with the Boolean satisfiability problem (SAT) or...
Grover's search algorithm gives a quantum attack against block ciphers with query complexity $O(\sqrt{N})$ to search a keyspace of size $N$, when given a sufficient number of plaintext-ciphertext pairs. A recent result by Jaques et al. (EUROCRYPT 2020) presented the cost estimates of quantum key search attacks against AES under different security categories as defined in NIST's PQC standardization process. In this work, we extend their approach to lightweight block ciphers for the cost...
Evaluating resistance of ciphers against differential cryptanalysis is essential to define the number of rounds of new designs and to mount attacks derived from differential cryptanalysis. In this paper, we compare existing automatic tools to find the best differential characteristic on the SKINNY block cipher. As usually done in the literature, we split this search in two stages denoted by Step 1 and Step 2. In Step 1, each difference variable is abstracted with a Boolean variable and we...
In this paper, we reevaluate the security of GIFT against differential cryptanalysis under both single-key scenario and related-key scenario. Firstly, we apply Matsui's algorithm to search related-key differential trails of GIFT. We add three constraints to limit the search space and search the optimal related-key differential trails on the limited search space. We obtain related-key differential trails of GIFT-64/128 for up to 15/14 rounds, which are the best results on related-key...
The design and cryptanalysis are the both sides from which we look at symmetric-key primitives. If a symmetric-key primitive is broken by a kind of cryptanalysis, it's definitely insecure. If a designer claims a symmetric-key primitive to be secure, one should demonstrate that the primitive resists against all known attacks. Differential and linear cryptanalysis are two of the most important kinds of cryptanalysis. To conduct a successful differential (linear) cryptanalysis, a differential...
Impossible differentials cryptanalysis and impossible polytopic cryptanalysis are the most effective approaches to estimate the security of block ciphers. However, the previous automatic search methods of their distinguishers, impossible differentials and impossible polytopic transitions, neither consider the impact of key schedule in the single-key setting and the differential property of large S-boxes, nor apply to the block ciphers with variable rotations. Thus, unlike previous methods...
Block ciphers are prevalent in various security protocols used daily such as TLS, OpenPGP, and SSH. Their primary purpose is the protection of user data, both in transit and at rest. One of the de facto methods to evaluate block cipher security is differential cryptanalysis. Differential cryptanalysis observes the propagation of input patterns (input differences) through the cipher to produce output patterns (output differences). This probabilistic propagation is known as a differential; the...
An increasing number of lightweight cryptographic primitives have been published recently. Some of these proposals are ARX primitives, which have shown a great performance in software. Rotational-XOR cryptanalysis is a statistical technique to attack ARX primitives. In this paper, a computer tool to speed up and make easier the security evaluation of ARX block ciphers against rotational-XOR cryptanalysis is shown. Our tool takes a Python implementation of an ARX block cipher and...
Since Keccak was selected as the SHA-3 standard, more and more permutation-based primitives have been proposed. Different from block ciphers, there is no round key in the underlying permutation for permutation-based primitives. Therefore, there is a higher risk for a differential characteristic of the underlying permutation to become incompatible when considering the dependency of difference transitions over different rounds. However, in most of the MILP or SAT based models to search for...
The bit-based division property (BDP) is the most effective technique for finding integral characteristics of symmetric ciphers. Recently, automatic search tools have become one of the most popular approaches to evaluating the security of designs against many attacks. Constraint-aided automatic tools for the BDP have been applied to many ciphers with simple linear layers like bit-permutation. Constructing models of complex linear layers accurately and efficiently remains hard. A...
The Meet-in-the-Middle (MITM) preimage attack is highly effective in breaking the preimage resistance of many hash functions, including but not limited to the full MD5, HAVAL, and Tiger, and reduced SHA-0/1/2. It was also shown to be a threat to hash functions built on block ciphers like AES by Sasaki in 2011. Recently, such attacks on AES hashing modes evolved from merely using the freedom of choosing the internal state to also exploiting the freedom of choosing the message state. However,...
A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due...
In this paper, we propose an automatic tool to search for optimal differential and linear trails in ARX ciphers. It's shown that a modulo addition can be divided into sequential small modulo additions with carry bit, which turns an ARX cipher into an S-box-like cipher. From this insight, we introduce the concepts of carry-bit-dependent difference distribution table (CDDT) and carry-bit-dependent linear approximation table (CLAT). Based on them, we give efficient methods to trace all possible...
Linear cryptanalysis is an important evaluation method for cryptographic primitives against key recovery attack. In this paper, we revisit the Walsh transformation for linear correlation calculation of modular addition, and an efficient algorithm is proposed to construct the input-output mask space of specified correlation weight. By filtering out the impossible large correlation weights in the first round, the search space of the first round can be substantially reduced. We introduce a new...
Motivated by the algorithm of differential probability calculation of Lipmaa and Moriai, we revisit the differential properties of modular addition. We propose an efficient approach to generate the input-output difference tuples with non-zero probabilities. A novel construction of combinational DDT, which makes it possible to obtain all valid output differences for fixed input differences. According to the upper bound of differential probability of modular addition, combining the...
Automatic search methods have been widely used for cryptanalysis of block ciphers, especially for the most classic cryptanalysis methods -- differential and linear cryptanalysis. However, the automatic search methods, no matter based on MILP, SMT/SAT or CP techniques, can be inefficient when the search space is too large. In this paper, we improve Matsui's branch-and-bound search algorithm which is known as the first generic algorithm for finding the best differential and linear trails by...
Grover's search algorithm gives a quantum attack against block ciphers by searching for a key that matches a small number of plaintext-ciphertext pairs. This attack uses $O(\sqrt{N})$ calls to the cipher to search a key space of size $N$. Previous work in the specific case of AES derived the full gate cost by analyzing quantum circuits for the cipher, but focused on minimizing the number of qubits. In contrast, we study the cost of quantum key search attacks under a depth restriction and...
In cloud security, traditional searchable encryption (SE) requires high computation and communication overhead for dynamic search and update. The clever combination of machine learning (ML) and SE may be a new way to solve this problem. This paper proposes interpretable encrypted searchable neural networks (IESNN) to explore probabilistic query, balanced index tree construction and automatic weight update in an encrypted cloud environment. In IESNN, probabilistic learning is used to obtain...
In Eurocrypt 2018, Cid et al. proposed a novel notion called the boomerang connectivity table, which formalised the switch property in the middle round of boomerang distinguishers in a unified approach. In this paper, we present a generic model of the boomerang connectivity table with automatic search technique for the first time, and search for (related-key) boomerang distinguishers directly by combining with the search of (related-key) differential characteristics. With the technique, we...
Using modular addition as a source of nonlinearity is frequently used in many symmetric-key structures such as ARX and Lai--Massey schemes. At FSE'16, Fu \etal proposed a Mixed Integer Linear Programming (MILP)-based method to handle the propagation of differential trails through modular additions assuming that the two inputs to the modular addition and the consecutive rounds are independent. However, this assumption does not necessarily hold. In this paper, we study the propagation of the...
Statistical saturation attack takes advantage of a set of plaintext with some bits fixed while the others vary randomly, and then track the evolution of a non-uniform plaintext distribution through the cipher. Previous statistical saturation attacks are all implemented under single-key setting, and there is no public attack models under related-key/tweak setting. In this paper, we propose a new cryptanalytic method which can be seen as related-key/tweak statistical saturation attack by...
In this paper, using Mixed Integer Linear Programming, a new automatic search tool for truncated differential characteristic is presented. Our method models the problem of finding a maximal probability truncated differential characteristic, which is able to distinguish the cipher from a pseudo random permutation. Using this method, we analyse Midori64, SKINNY64/X and CRAFT block ciphers, for all of which the existing results are improved. In all cases, the truncated differential...
The automatic search method based on Mix-integer Linear Programming (MILP) is one of the most common tools to search the distinguishers of block ciphers. For differential analysis, the byte-oriented MILP model is usually used to count the number of differential active s-boxes and the bit-oriented MILP model is used to search the optimal differential characteristic. In this paper, we present the influences between the construction and solution of MILP models solved by Gurobi : 1). the number...
Automatic tools have played an important role in designing new cryptographic primitives and evaluating the security of ciphers. Simple Theorem Prover constraint solver (STP) has been used to search for differential/linear trails of ciphers. This paper proposes general STP-based models searching for differential and linear trails with the optimal probability and correlation for S-box based ciphers. In order to get trails with the best probability or correlation for ciphers with arbitrary...
The division property proposed at Eurocrypt'15 is a novel technique to find integral distinguishers, which has been applied to most kinds of symmetric ciphers such as block ciphers, stream ciphers, and authenticated encryption,~\textit{etc}. The original division property is word-oriented, and later the bit-based one was proposed at FSE'16 to get better integral property, which is composed of conventional bit-based division property (two-subset division property) and bit-based division...
In this paper we use MILP technique for automatic search for differential characteristics of ARX ciphers LEA and HIGHT. We show that the MILP model of the differential property of modular addition with one constant input can be represented with a much less number of linear inequalities compared to the general case. Benefiting from this new developed model for HIGHT block cipher, we can achieve a reduction of 112r out of 480r in the total number of linear constraints for MILP model of r-round...
Cryptanalysis with SAT/SMT, MILP and CP has increased in popularity among symmetric-key cryptanalysts and designers due to its high degree of automation. So far, this approach covers differential, linear, impossible differential, zero-correlation, and integral cryptanalysis. However, the Demirci-Selcuk meet-in-the-middle (DS-MITM) attack is one of the most sophisticated techniques that has not been automated with this approach. By an in-depth study of Derbez and Fouque's work on DS-MITM...
In this paper, we study the relation of single-key impossible differentials with the related-tweakey/key ones and propose an interesting algorithm that can efficiently derive longer related-tweakey/key impossible differentials from single-key ones. With application of the MILP technique, the algorithm can be converted an automatic tool for searching related-tweakey/key impossible differentials. We use this automatic tool to analyze QARMA-64 and give a 11-round key recovery attack, which...
In this paper we improve Wu and Wang's method for finding impossible differentials of block cipher structures. This improvement is more general than Wu and Wang's method that it can find more impossible differentials with less time. We apply it on Gen-CAST256, Misty, Gen-Skipjack, Four-Cell, Gen-MARS, SMS4, MIBS, Camellia*, LBlock, E2 and SNAKE block ciphers. All impossible differentials discovered by the algorithm are the same as Wu's method. Besides, for the 8-round MIBS block cipher, we...
Division property is a generalized integral property proposed by Todo at Eurocrypt 2015. Previous tools for automatic searching are mainly based on the Mixed Integer Linear Programming (MILP) method and trace the division property propagation at the bit level. In this paper, we propose automatic tools to detect ARX ciphers' division property at the bit level and some specific ciphers' division property at the word level. For ARX ciphers, we construct the automatic searching tool relying on...
The ultimate goal of designing a symmetric-key cryptographic primitive often can be formulated as an optimization problem. So far, these problems mainly have been solved with trivial algorithms such as brute force or random search. We show that a more advanced and equally versatile class of search algorithms, called metaheuristics, can help to tackle optimization problems related to design of symmetric-key primitives. We use two nature-inspired metaheuristics, simulated annealing and...
In the present paper, we analyze the security of SIMON-like ciphers against linear cryptanalysis. First, an upper bound is derived on the squared correlation of SIMON-like round function. It is shown that the upper bound on the squared correlation of SIMON-like round function decreases with the Hamming weight of output mask increasing. Based on this, we derive an upper bound on the squared correlation of linear trails for SIMON and SIMECK, which is $2^{-2R+2}$ for any $R$-round linear trail....
In the present paper, we propose an automatic search algorithm for optimal differential trails in SIMON-like ciphers. First, we give a more accurate upper bound on the differential probability of SIMON-like round function. It is shown that when the Hamming weight of the input difference $\alpha$, which is denoted by $wt(\alpha)$, is less than one half of the input size, the corresponding maximum differential probability of SIMON-like round function is less than or equal to...
In this paper, we suggest an advanced method searching for differential trails of block cipher with ARX structure. We use two techniques to optimize the automatic search algorithm of differential trails suggested by Biryukov et al. and obtain 2~3 times faster results than the previous one when implemented in block cipher SPECK.
Impossible differential and zero-correlation linear cryptanalysis are two of the most powerful cryptanalysis methods in the field of symmetric key cryptography. There are several automatic tools to search such trails for ciphers with S-boxes. These tools focus on the properties of linear layers, and idealize the underlying S-boxes, i.e., assume any input and output difference pairs are possible. In reality, such S-box never exists, and the possible output differences with any fixed input...
Midori is a hardware-oriented lightweight block cipher designed by Banik \emph{et al.} in ASIACRYPT 2015. It has two versions according to the state sizes, i.e. Midori64 and Midori128. In this paper, we explore the security of Midori64 against truncated differential and related-key differential attacks. By studying the compact representation of Midori64, we get the branching distribution properties of almost MDS matrix used by Midori64. By applying an automatic truncated differential search...
The algorithm presented in this paper computes a maximum probability differential characteristic in a Substitution-Permutation Network (or SPN). Such characteristics can be used to prove that a cipher is practically secure against differential cryptanalysis or on the contrary to build the most effective possible attack. Running in just a few second on 64 or 128-bit SPN, our algorithm is an important tool for both cryptanalists and designers of SPN.
Tracking bits through block ciphers and optimizing attacks at hand is one of the tedious task symmetric cryptanalysts have to deal with. It would be nice if a program will automatically handle them at least for well-known attack techniques, so that cryptanalysts will only focus on finding new attacks. However, current automatic tools cannot be used as is, either because they are tailored for specific ciphers or because they only recover a specific part of the attacks and cryptographers are...
Key schedules in block ciphers are often highly simplified, which causes weakness that can be exploited in many attacks. At ASIACRYPT 2011, Dunkelman et al. proposed a technique using the weakness in the key schedule of AES, called key-bridging technique, to improve the overall complexity. The advantage of key-bridging technique is that it allows the adversary to deduce some sub-key bits from some other sub-key bits, even though they are separated by many key mixing steps. Although the...
We propose the first adaptation of Matsui's algorithm for finding the best differential and linear trails to the class of ARX ciphers. It is based on a branch-and-bound search strategy, does not use any heuristics and returns optimal results. The practical application of the new algorithm is demonstrated on reduced round variants of block ciphers from the \textsc{Speck} family. More specifically, we report the probabilities of the best differential trails for up to 10, 9, 8, 7, and 7 rounds...
In recent years, Mixed Integer Linear Programming (MILP) has been successfully applied in searching for differential characteristics and linear approximations in block ciphers and has produced the significant results for some ciphers such as SIMON (a family of lightweight and hardware-optimized block ciphers designed by NSA) etc. However, in the literature, the MILP-based automatic search algorithm for differential characteristics and linear approximations is still infeasible for block...
In this paper, we focus on the automatic differential cryptanalysis of ARX block ciphers with respect to XOR-difference, and develop Mouha et al.'s framework for finding differential characteristics by adding a new method to construct long characteristics from short ones. The new method reduces the searching time a lot and makes it possible to search differential characteristics for ARX block ciphers with large word sizes such as $n=48,64$. What's more, we take the differential effect into...
Differential and linear cryptanalysis are the general purpose tools to analyze various cryptographic primitives. Both techniques have in common that they rely on the existence of good differential or linear characteristics. The difficulty of finding such characteristics depends on the primitive. For instance, AES is designed to be resistant against differential and linear attacks and therefore, provides upper bounds on the probability of possible linear characteristics. On the other hand, we...
In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-free-start collision into a collision for 31 steps with a complexity of at most $2^{65.5}$. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential...
In this paper, we revisit Demirci and Selçuk meet-in-the-middle attacks on AES. We find a way to automatically model SPN block cipher and meet-in-the-middle attacks that allows to perform exhaustive search of this kind of attacks. This search uses the tool developed by Bouillaguet, Derbez and Fouque at CRYPTO 2011 as a subroutine to solve specific systems. We also take into account ideas introduced by Dunkelman, Keller and Shamir at ASIACRYPT 2010 which can be seen as a new tradeoff of the...
As two important cryptanalytic methods, impossible differential cryptanalysis and integral cryptanalysis have attracted much attention in recent years. Although relations among other important cryptanalytic approaches have been investigated, the link between these two methods has been missing. The motivation in this paper is to fix this gap and establish links between impossible differential cryptanalysis and integral cryptanalysis. Firstly, by introducing the concept of structure and dual...
In IACR ePrint 2014/747, a method for constructing mixed-integer linear programming (MILP) models whose feasible regions are exactly the sets of all possible differential (or linear) characteristics for a wide range of block ciphers is presented. These models can be used to search for or enumerate differential and linear characteristics of a block cipher automatically. However, for the case of SIMON (a lightweight block cipher designed by the U.S. National Security Agency), the method...
Improved meet-in-the-middle cryptanalysis with efficient tabulation technique has been shown to be a very powerful form of cryptanalysis against SPN block ciphers. However, few literatures show the effectiveness of this cryptanalysis against Balanced-Feistel-Networks (BFN) and Generalized-Feistel-Networks (GFN) ciphers due to the stagger of affected trail and special truncated differential trail. In this paper, we describe a versatile and powerful algorithm for searching the best improved...
In CRYPTO 2014 Albrecht \emph{et al.} brought in a 20-round iterative lightweight block cipher PRIDE which is based on a good linear layer for achieving a tradeoff between security and efficiency. A recent analysis is presented by Zhao \emph{et al.}. Inspired by their work, we use an automatic search method to find out 56 iterative differential characteristics of PRIDE, containing 24 1-round iterative characteristics, based on three of them we construct a 15-round differential and perform a...
SIMON is a family of lightweight block ciphers designed by the U.S. National Security Agency (NSA) that has attracted much attention since its publication in 2013. In this paper, we thoroughly investigate the properties of linear approximations of the bitwise AND operation with dependent input bits. By using a Mixed-integer Linear Programming based technique presented in Aasicrypt 2014 for automatic search for characteristics, we obtain improved linear characteristics for several versions of...