## CryptoDB

### Meiqin Wang

#### Affiliation: Shandong University , China

#### Publications

**Year**

**Venue**

**Title**

2021

TOSC

Accelerating the Search of Differential and Linear Characteristics with the SAT Method
Abstract

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 satisfiability modulo theories (SMT) method. This paper intends to fill this vacancy. Firstly, with the additional encoding variables of the sequential counter circuit for the original objective function in the standard SAT method, we put forward a new encoding method to convert the Matsui’s bounding conditions into Boolean formulas. This approach does not rely on new auxiliary variables and significantly reduces the consumption of clauses for integrating multiple bounding conditions into one SAT problem. Then, we evaluate the accelerating effect of the novel encoding method under different sets of bounding conditions. With the observations and experience in the tests, a strategy on how to create the sets of bounding conditions that probably achieve extraordinary advances is proposed. The new idea is applied to search for optimal differential and linear characteristics for multiple ciphers. For PRESENT, GIFT-64, RECTANGLE, LBlock, TWINE, and some versions in SIMON and SPECK families of block ciphers, we obtain the complete bounds (full rounds) on the number of active S-boxes, the differential probability, as well as the linear bias. The acceleration method is also employed to speed up the search of related-key differential trails for GIFT-64. Based on the newly identified 18-round distinguisher with probability 2−58, we launch a 26-round key-recovery attack with 260.96 chosen plaintexts. To our knowledge, this is the longest attack on GIFT-64. Lastly, we note that the attack result is far from threatening the security of GIFT-64 since the designers recommended users to double the number of rounds under the related-key attack setting.

2020

TOSC

Finding Bit-Based Division Property for Ciphers with Complex Linear Layers
📺
Abstract

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 straightforward method proposed by Sun et al. (called the S method), decomposes a complex linear layer into basic operations like COPY and XOR, then models them one by one. However, this method can easily insert invalid division trails into the solution pool, which results in a quicker loss of the balanced property than the cipher itself would. In order to solve this problem, Zhang and Rijmen propose the ZR method to link every valid trail with an invertible sub-matrix of the matrix corresponding to the linear layer, and then generate linear inequalities to represent all the invertible sub-matrices. Unfortunately, the ZR method is only applicable to invertible binary matrices (defined in Definition 3).To avoid generating a huge number of inequalities for all the sub-matrices, we build a new model that only includes that the sub-matrix corresponding to a valid trail should be invertible. The computing scale of our model can be tackled by most of SMT/SAT solvers, which makes our method practical. For applications, we improve the previous BDP for LED and MISTY1. We also give the 7-round BDP results for Camellia with FL/FL−1, which is the longest to date.Furthermore, we remove the restriction of the ZR method that the matrix has to be invertible, which provides more choices for future designs. Thanks to this, we also reproduce 5-round key-dependent integral distinguishers proposed at Crypto 2016 which cannot be obtained by either the S or ZR methods.

2020

TOSC

Beyond-Birthday-Bound Security for 4-round Linear Substitution-Permutation Networks
📺
Abstract

Recent works of Cogliati et al. (CRYPTO 2018) have initiated provable treatments of Substitution-Permutation Networks (SPNs), one of the most popular approach to construct modern blockciphers. Such theoretical SPN models may employ non-linear diffusion layers, which enables beyond-birthday-bound provable security. Though, for the model of real world blockciphers, i.e., SPN models with linear diffusion layers, existing provable results are capped at birthday security up to $2^{n/2}$ adversarial queries, where $n$ is the size of the idealized S-boxes.
In this paper, we overcome this birthday barrier and prove that a 4-round SPN with linear diffusion layers and independent round keys is secure up to $2^{2n/3}$ queries. For this, we identify conditions on the linear layers that are sufficient for such security, which, unsurprisingly, turns out to be slightly stronger than Cogliati et al.'s conditions for birthday security. These provides additional theoretic supports for real world SPN blockciphers.

2020

TOSC

Differential Attacks on CRAFT Exploiting the Involutory S-boxes and Tweak Additions
📺
Abstract

CRAFT is a lightweight tweakable block cipher proposed at FSE 2019, which allows countermeasures against Differential Fault Attacks to be integrated into the cipher at the algorithmic level with ease. CRAFT employs a lightweight and involutory S-box and linear layer, such that the encryption function can be turned into decryption at a low cost. Besides, the tweakey schedule algorithm of CRAFT is extremely simple, where four 64-bit round tweakeys are generated and repeatedly used. Due to a combination of these features which makes CRAFT exceedingly lightweight, we find that some input difference at a particular position can be preserved through any number of rounds if the input pair follows certain truncated differential trails. Interestingly, in contrast to traditional differential analysis, the validity of this invariant property is affected by the positions where the constant additions take place. We use this property to construct “weak-tweakey” truncated differential distinguishers of CRAFT in the single-key model. Subsequently, we show how the tweak additions allow us to convert these weak-tweakey distinguishers into ordinary secret-key distinguishers based on which key-recovery attacks can be performed. Moreover, we show how to construct MILP models to search for truncated differential distinguishers exploiting this invariant property. As a result, we find a 15-round truncated differential distinguisher of CRAFT and extend it to a 19-round key-recovery attack with 260.99 data, 268 memory, 294.59 time complexity, and success probability 80.66%. Also, we find a 14-round distinguisher with probability 2−43 (experimentally verified), a 16-round distinguisher with probability 2−55, and a 20-round weak-key distinguisher (2118 weak keys) with probability 2−63. Experiments on round-reduced versions of the distinguishers show that the experimental probabilities are sometimes higher than predicted. Finally, we note that our result is far from threatening the security of the full CRAFT.

2020

TOSC

On the Usage of Deterministic (Related-Key) Truncated Differentials and Multidimensional Linear Approximations for SPN Ciphers
📺
Abstract

Among the few works realising the search of truncated differentials (TD) and multidimensional linear approximations (MDLA) holding for sure, the optimality of the distinguisher should be confirmed via an exhaustive search over all possible input differences/masks, which cannot be afforded when the internal state of the primitive has a considerable number of words. The incomplete search is also a long-term problem in the search of optimal impossible differential (ID) and zerocorrelation linear approximation (ZCLA) since all available automatic tools operate under fixed input and output differences/masks, and testing all possible combinations of differences/masks is impracticable for now. In this paper, we start by introducing an automatic approach based on the constraint satisfaction problem for the exploration of deterministic TDs and MDLAs. Since we transform the exhaustive search into an inherent feature of the searching model, the issue of incomplete search is settled. This tool is applied to search for related-key (RK) TDs of AES-192, and a new related-key differential-linear (DL) distinguisher is identified with a TD with certainty. Due to the novel property of the distinguisher, the previous RK DL attack on AES-192 is improved. Also, the new distinguisher is explained from the viewpoint of differentiallinear connectivity table (DLCT) and thus can be regarded as the first application of DLCT in the related-key attack scenario. As the second application of the tool, we propose a method to construct (RK) IDs and ZCLAs automatically. Benefiting from the control of the nonzero fixed differential pattern and the inherent feature of exhaustive search, the new searching scheme can discover longer distinguishers and hence possesses some superiorities over the previous methods. This technique is implemented with several primitives, and the provable security bounds of SKINNY and Midori64 against impossible differential distinguishing attack are generalised.

2020

ASIACRYPT

An Algebraic Formulation of the Division Property: Revisiting Degree Evaluations, Cube Attacks, and Key-Independent Sums
📺
Abstract

Since it was proposed in 2015 as a generalization
of integral properties, the division property has
evolved into a powerful tool for probing the
structures of Boolean functions whose
algebraic normal forms are not available.
We capture the most essential elements for the detection of division properties
from a pure algebraic perspective, proposing a technique named as {\it monomial prediction}, which
can be employed to determine the presence or absence of a
monomial in the product of the coordinate functions of a vectorial
Boolean function $\bs f$ by counting the number of the so-called {\it monomial trails}
across a sequence of simpler functions whose composition is $\bs f$.
Under the framework of the monomial prediction, we formally prove that
most algorithms for detecting division properties in previous literature
raise no false alarms but may miss.
We also establish the equivalence between the monomial prediction and
the three-subset bit-based division property without unknown subset presented at EUROCRYPT 2020,
and show that these two techniques are perfectly accurate.
This algebraic formulation gives more insights into division properties
and inspires new search strategies. With the monomial prediction,
we obtain the {\it exact} algebraic degrees of \TRIVIUM up
to 834 rounds for the first time. In the context of cube attacks,
we are able to explore a larger search space in limited time and
recover the exact algebraic normal forms of complex superpolies
with the help of a divide-and-conquer strategy. As a result,
we identify more cubes with smaller dimensions, leading
to improvements of some near-optimal attacks against 840-, 841-
and 842-round \TRIVIUM.

2019

TOSC

Related-Tweak Statistical Saturation Cryptanalysis and Its Application on QARMA
📺
Abstract

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 revealing the link between the related-key/tweak statistical saturation distinguishers and KDIB (Key Difference Invariant Bias) / TDIB (Tweak Difference Invariant Bias) ones. KDIB cryptanalysis was proposed by Bogdanov et al. at ASIACRYPT’13 and utilizes the property that there can exist linear trails such that their biases are deterministically invariant under key difference. And this method can be easily extended to TDIB distinguishers if the tweak is also alternated. The link between them provides a new and more efficient way to find related-key/tweak statistical saturation distinguishers in ciphers. Thereafter, an automatic searching algorithm for KDIB/TDIB distinguishers is also given in this paper, which can be implemented to find word-level KDIB distinguishers for S-box based key-alternating ciphers. We apply this algorithm to QARMA-64 and give related-tweak statistical saturation attack for 10-round QARMA-64 with outer whitening key. Besides, an 11-round attack on QARMA-128 is also given based on the TDIB technique. Compared with previous public attacks on QARMA including outer whitening key, all attacks presented in this paper are the best ones in terms of the number of rounds.

2018

TOSC

Cryptanalysis of AES-PRF and Its Dual
📺
Abstract

A dedicated pseudorandom function (PRF) called AES-PRF was proposed by Mennink and Neves at FSE 2018 (ToSC 2017, Issue 3). AES-PRF is obtained from AES by using the output of the 5-th round as the feed-forward to the output state. This paper presents extensive security analysis of AES-PRF and its variants. Specifically, we consider unbalanced variants where the output of the s-th round is used as the feed-forward. We also analyze the security of “dual” constructions of the unbalanced variants, where the input state is used as the feed-forward to the output of the s-th round. We apply an impossible differential attack, zero-correlation linear attack, traditional differential attack, zero correlation linear distinguishing attack and a meet-in-the-middle attack on these PRFs and reduced round versions. We show that AES-PRF is broken whenever s ≤ 2 or s ≥ 6, or reduced to 7 rounds, and Dual-AES-PRF is broken whenever s ≤ 4 or s ≥ 8. Our results on AES-PRF improve the initial security evaluation by the designers in various ways, and our results on Dual-AES-PRF give the first insight to its security.

2018

TOSC

More Accurate Differential Properties of LED64 and Midori64
📺
Abstract

In differential cryptanalysis, a differential is more valuable than the single trail belonging to it in general. The traditional way to compute the probability of the differential is to sum the probabilities of all trails within it. The automatic tool for the search of differentials based on Mixed Integer Linear Programming (MILP) has been proposed and realises the task of finding multiple trails of a given differential. The problem is whether it is reliable to evaluate the probability of the differential traditionally. In this paper, we focus on two lightweight block ciphers – LED64 and Midori64 and show the more accurate estimation of differential probability considering the key schedule. Firstly, an automated tool based on Boolean Satisfiability Problem (SAT) is put forward to accomplish the automatic search of differentials for ciphers with S-boxes and is applied to LED64 and Midori64. Secondly, we provide an automatic approach to detect the right pairs following a given differential, which can be exploited to calculate the differential property. Applying this technique to the STEP function of LED64, we discover some differentials with enhanced probability. As a result, the previous attacks relying upon high probability differentials can be improved definitely. Thirdly, we present a method to compute an upper-bound of the weak-key ratio for a given differential, which is utilised to analyse 4-round differentials of Midori64. We detect two differentials whose weak-key ratios are much lower than the expected 50%. More than 78% of the keys will make these two differentials being impossible differentials. The idea of the estimation for an upper-bound of the weak-key ratio can be employed for other ciphers and allows us to launch differential attacks more reliably. Finally, we introduce how to compute the enhanced differential probability and evaluate the size of keys achieving the improved probability. Such a property may incur an efficient weak-key attack. For a 4-round differential of Midori64, we obtain an improved differential property for a portion of keys.

2017

ASIACRYPT

2015

EPRINT

2010

EPRINT

Practical-time Attack on the Full MMB Block Cipher
Abstract

Modular Multiplication based Block Cipher (MMB) is a block cipher
designed by Daemen \emph{et al.} as an alternative to the IDEA block
cipher. In this paper, we give a practical-time attack on the full
MMB with adaptive chosen plaintexts and ciphertexts. By the
constructive sandwich distinguisher for 5 of the 6 rounds of MMB
with amazingly high probability 1, we give the key recovery attack
on the full MMB with data complexity $2^{40}$ and time complexity
$2^{13.4}$ MMB encryptions. Then a rectangle-like sandwich attack on
the full MMB is presented, with $2^{66.5}$ chosen plaintexts,
$2^{64}$ MMB encryptions and $2^{70.5}$ memory bytes. By the way, we
show an improved differential attack on the full MMB with data
complexity of $2^{96}$ chosen plaintexts and ciphertexts, time
complexity $2^{64}$ encryptions and $2^{66}$ bytes of memory.

2010

EPRINT

Effect of the Dependent Paths in Linear Hull
Abstract

Linear Hull is a phenomenon that there are a lot of linear paths
with the same data mask but different key masks for a block cipher.
In 1994, Nyberg presented the effect on the key-recovery attack such
as Algorithm 2 with linear hull, in which the required number of the
known plaintexts can be decreased compared with that in the attack
using individual linear path. In 2009, Murphy proved that Nyberg's
results can only be used to give a lower bound on the data
complexity and will be no use on the real linear cryptanalysis. In
fact, the linear hull have this kind of positive effect in linear
cryptanalysis for some keys instead of the whole key space. So the
linear hull can be used to improve the traditional linear
cryptanalysis for some weak keys. In the same year, Ohkuma gave the
linear hull analysis on PRESENT block cipher, and pointed that there
are $32\%$ weak keys of PRESENT which make the bias of a given
linear hull with multiple paths more than that of any individual
linear path. However, Murphy and Ohkuma have not considered the
dependency of the muti-path, and their results are based on the
assumption that the linear paths are independent. Actually, most of
the linear paths are dependent in the linear hull, and the
dependency of the linear paths means the dependency of the
equivalent key bits. In this paper, we will analyze the dependency
of the linear paths in linear hull and present the real effect of
linear hull with the dependent linear paths. Firstly, we give the
relation between the bias of a linear hull and its linear paths in
linear cryptanalysis. Secondly, we present the algorithm to compute
the rate of weak keys corresponding to the expect bias of the linear
hull. At last, we verify our algorithm by cryptanalyzing
reduced-round of PRESENT. Compared with the rate of weak keys under
the assumption of the independent linear paths, the dependency of
the linear paths will greatly reduce the rate of weak keys for a
given linear hull.

2007

EPRINT

Differential Cryptanalysis of PRESENT
Abstract

PRESENT is proposed by A.Bogdanov et al. in CHES 2007 for extremely
constrained environments such as RFID tags and sensor networks. In
this paper, we find out the differential characteristics for
r-round($5 \leq r \leq 15$), then give the differential
cryptanalysis on reduced-round variants of PRESENT. We attack
16-round PRESENT using $2^{64}$ chosen plaintexts, $2^{32}$ 6-bit
counters, and $2^{65}$ memory accesses.

#### Program Committees

- FSE 2018
- FSE 2017
- Asiacrypt 2017
- FSE 2016
- Asiacrypt 2016
- Asiacrypt 2014

#### Coauthors

- Joël Alwen (1)
- Andrey Bogdanov (5)
- Christina Boura (1)
- Huaifeng Chen (2)
- Jiazhe Chen (1)
- Tingting Cui (1)
- Zhenli Dai (1)
- Patrick Derbez (1)
- Xiaoyang Dong (1)
- Kai Fu (2)
- Yansong Gao (1)
- David Gerault (1)
- Chun Guo (1)
- Yinghua Guo (1)
- Jian Guo (2)
- Hao Guo (1)
- Lei Hu (3)
- Kai Hu (3)
- Senyang Huang (1)
- Tetsu Iwata (1)
- Keting Jia (2)
- Gregor Leander (1)
- Muzhou Li (1)
- Xiaoshuang Ma (1)
- Kaisa Nyberg (1)
- Bart Preneel (1)
- Kexin Qiao (1)
- Vincent Rijmen (1)
- Yu Sasaki (2)
- Danping Shi (2)
- Ling Song (1)
- Ling Su (1)
- Ling Sun (6)
- Yue Sun (2)
- Siwei Sun (5)
- Yao Sun (1)
- Elmar Tischhauser (1)
- Yosuke Todo (1)
- Wei Wang (5)
- Weijia Wang (1)
- Qingju Wang (2)
- Xiaoyun Wang (4)
- Lei Wang (2)
- Haoyang Wang (1)
- Peng Wang (1)
- Long Wen (5)
- Guangwu Xu (1)
- Jingyuan Zhao (3)