IET Information Security
Research Article
Division cryptanalysis of block ciphers with a
binary diffusion layer
ISSN 1751-8709
Received on 8th January 2017
Revised 21st April 2018
Accepted on 24th July 2018
E-First on 2nd November 2018
doi: 10.1049/iet-ifs.2018.5151
www.ietdl.org
Wenying Zhang
1
, Vincent Rijmen
2
1
School of Information Science and Engineering, Shandong Normal University, Jinan, People's Republic of China
2
Department Electrical Engineering (ESAT), KU Leuven and Imec, Leuven, Belgium
E-mail: wenyingzh@sohu.com
Abstract: In this study, the authors propose an accurate approach to model the propagation of the division property of linear
layers by the smallest amount of inequalities. The solutions of the inequalities are exactly the division trails of a linear
transformation. Therefore, the description is compact and optimal. As applications of their results, they present a 7-round
integral distinguisher for both Midori64 and Midori128. The designers of Midori only obtained a 3.5-round integral characteristic.
For Skinny64, they find a 10-round integral distinguisher which was previously found by the designers. It is well to remind that
their result proves that 7 rounds and 10 rounds are the upper bounds of Midori and Skinny64 correspondingly when searching
for integral distinguishers based on division property. The significance of their result lies in that they shed light on how far
division cryptanalysis can influence the security analysis of block ciphers with a binary diffusion layer, and their technique can be
used to prove security against division cryptanalysis.
1 Introduction
Recently, in order to reduce the energy consumed in data
processing, block cipher designers have started to use binary
matrices on finite fields as the diffusion layer. The most typical
examples are Midori [1], proposed at ASIACRYPT 2015 and
Skinny [2], proposed at CRYPTO 2016. The main goal of Skinny
is to offer an alternative to the National Security Agency (NSA)
design SIMON in terms of hardware/software performance [3].
With their reputation for reaching the requirements of low latency
as well as fast diffusion [2], the diffusion layer of SKINNY is an
important highlight of its design strategy. Therefore, it is of great
importance to evaluate the resistance of ciphers using binary
matrices to known cryptanalysis and to give a proof of their
security.
The division property [4] is a generalised integral property
initially proposed by Todo at EUROCRYPT 2015. At FSE 2016,
Todo and Morii proposed the bit-based division property and
applied it to find a 14-round integral distinguisher for SIMON32
[5]. At CRYPTO 2016, Boura and Canteaut [6] came up with a
new approach by introducing the notion of parity sets, permitting
the formulation and characterisation of the division property of any
order in a simple way, especially for the construction of the
division trails of S-boxes. At ASIACRYPT 2016, Xiang et al. [7]
proposed a method to characterise the bit-based division property
with the mixed integer linear programming (MILP) model, which
successfully overcomes the difficulty of huge time and memory
complexities of utilising the bit-based division property in a
security evaluation. They accurately described the division-
property propagations by choosing an appropriate objective
function and analysed six block ciphers with bit-permutation
diffusion layers. They left the feasibility of MILP method applied
to ciphers with diffusion layers that are not bit permutations as a
future work. Soon after, Sun et al. [8, 9] handled the feasibility of
MILP-aided division property for primitives with non-bit-
permutation linear layers. They successfully extended the MILP
method to exclusive-OR (XOR)-based and Addition-Rotation-
XOR operation (ARX)-based structures by introducing some
intermediate variables in the linear layer, building 2n inequalities
for the n-bit linear layers.
However, we found that the solutions of linear inequalities in
[8] contain some impossible division trails, which may eventually
lead the search for integral trails to a premature end and result in a
shorter integral distinguisher. In the following, for block ciphers
with a binary linear layer, we will give a compact description [10]
of the propagation of the division property through the linear layer.
Combined with our compact description, the method in [8, 9] will
be more precise and closer to perfection.
1.1 Our contributions
i. We model the propagation of the division property through a
linear layer by constructing linear inequalities from the XOR
operations described by the matrix of the linear layer, so that
their solutions exactly represent all division trails of the linear
layer. Just like for an S-box, the solutions set of the linear
inequalities is equal to the set of division trails of the linear
transformation when taking the linear transformation as a big
S-box. We find that there is a one-to-one map from the vectors
in the division trails of a linear transformation to invertible
submatrices of the matrix M, and we can give a simple
description of the invertibility of the submatrices by some
inequalities.
ii. As applications of our methodology, we propose compact
representations for the division properties through the linear
layer of Midori and Skinny. We describe exactly all division
trails of their linear layers without any extra parasitical one. As
for Midori64 and Midori128, the designers have obtained a
3.5-round integral characteristic. In comparison with the
former method, we find 7-round integral characteristics, twice
what the former method achieves, for both Midori64 and
Midori128. In Eurocrypt 2017, Sasaki and Todo [11] found a
7-round truncated impossible differential for Midori128 by an
automated tool, but there is no corresponding result for
Midori64. For Skinny64, we find the same 10-round integral
distinguisher for Skinny64 that the designers have found. The
designers of Skinny mentioned in their security analysis that
the division property can probably be used to slightly extend
their results. Our results, however, show that any improvement
in the length of the integral distinguisher using the division
property is impossible. A summary of the comparisons of our
results with the previous integral characteristics is shown in
Table 1.
IET Inf. Secur., 2019, Vol. 13 Iss. 2, pp. 87-95
© The Institution of Engineering and Technology 2018
87