Integral Attacks on Reduced-Round PRESENT

Shengbao Wu1,2 and Mingsheng Wang3

1
Trusted Computing and Information Assurance Laboratory, Institute of Software,
Chinese Academy of Sciences, Beijing 100190, PO Box 8718, China
2
Graduate School of Chinese Academy of Sciences, Beijing 100190, China
3
State Key Laboratory of Information Security, Institute of Information Engineering,
Chinese Academy of Sciences, Beijing, China
wangmingsheng@iie.ac.cn

Abstract. Integral attack is a powerful technique to recover the secret

key of block ciphers by usually exploiting the fact that specific parts
of the output after several round encryptions has a zero-sum property
in a set of chosen plaintexts. In FSE 2008, bit-based integral attack
proposed by Z’aba et al. revealed that integral attacks may be not only
suitable for byte-based block ciphers but also still applied to bit-based
block ciphers. In this work, we show that integral attack against bit-
based block ciphers can be improved not only by the theorem of higher-
order differential attack but also by using specific algebraic properties of
Sboxes, and the order of plaintexts in a set, which is important in bit-
based integral attack, is not required here. We focus on the block cipher
PRESENT. Based on some algebraic properties of its Sbox, we propose
two integral distinguishers: a 5 round (4-th order) integral distinguisher
and a 7 round (16-th order) integral distinguishers, which can be used
to attack 10 (out of 31) round PRESENT. As far as we know, it is the
first time that a 7 round integral distinguisher of PRESENT is reported.
Algebraic techniques used in this paper may be also applied to other
block ciphers to improve their known integral attacks.

Keywords: Integral Attack, PRESENT, Higher Order Differential

Attack, Boolean Function.

1 Introduction

The integral attack is one of the most popular cryptanalytic tools for block
ciphers. It was first known as “Square attack” due to its efficiency in attacking
the Rijndael-predecessor Square [8]. Later, several variants of Square attack have
been proposed, including saturation attack [13] and multiset attack [5]. In FSE
2002, Knudsen and Wagner introduced the definition of integral and unified these
kinds of attacks as integral attack [11].
The basic idea of integral attack is to analyze the propagation of sums of
(many) values. Thus, it can be seen as a dual to the differential cryptanalysis.
When applying integral attack to a block cipher, an attacker first selects a d-th
order integral, that is, he/she chooses a set of 2d plaintexts, where d bit positions

S. Qing et al. (Eds.): ICICS 2013, LNCS 8233, pp. 331–345, 2013.

c Springer International Publishing Switzerland 2013
332 S. Wu and M. Wang

take on all values through the set, and the other bits are chosen to be arbitrary
constants. Then, he/she traces the evolvement of the sum of this set of plaintexts
through the encryption algorithm and builds an integral distinguisher as long as
possible. Finally, the integral distinguisher will be used to verify key guesses. In
practice, a zero-sum property in specific parts of the ciphertext is often used as
the integral distinguisher.
In quite a long time, integral attack has not been thought suitable for bit-based
block ciphers, such as Noekeon [9], Serpent [1] and PRESENT [2]. Until 2008,
Z’aba et al. proposed the bit-based integral attack [16], which was applied to
Noekeon, Serpent and PRESENT reduced up to 5, 6 and 7 rounds, respectively.
Although the bit-based integral attack does not pose a serious threat to known
block ciphers, it reveals that integral attacks may be not only suitable for byte-
based block ciphers but also still applied to bit-based block ciphers.
Many cryptanalysis methods may be not so powerful as nowadays in their
first proposals. However, with the studies getting further, they became more
and more powerful. On the one hand, new techniques may be introduced to
improve known cryptanalysis methods. For example, the partial-sum techniques
proposed by Ferguson et al. [10] enhance the ability of integral attack. On the
other hand, a cryptanalysis method may be improved using the theorem of other
cryptanalysis methods if they have some links. For example, the data complexity
of a zero-correlation attack [4] may be improved using the theorem of integral
attack [3].
Integral attack and higher-order differential attack also have some links in
constructing distinguishers. To construct a d-th order integral distinguisher with
a zero-sum property is equivalent to show that the algebraic degree of specific
parts of the ciphertext is at most d − 1, if XOR difference is considered in
the higher-order differential attack. This technique has been used, for instance,
in [15].
In this paper, we show that integral attack against bit-based block ciphers
can be improved not only by the theorem of higher-order differential attack but
also by using specific algebraic properties of Sboxes. What is more, the order
of plaintexts in a set, which is important in bit-based integral attack, is not
required here.
We focus on the bit-based block cipher PRESENT. Firstly, we analyze the
algebraic properties of PRESENT’s Sbox. We observe that the rightmost co-
ordinate of the Sbox is quadratic while other three coordinates has algebraic
degree 3. Combined it with the properties of diffusion layer, we find that, for
the rightmost bit of the output, the growth rate of its algebraic degree is slower
than other bits. Than, we propose two integral distinguishers: the first one uses
that the rightmost bit of the output after 5 rounds has a zero-sum property in
the 4 rightmost bits of the input. Similarly, the second distinguisher is based
on the fact that the rightmost bit of the output after 7 rounds has a zero-
sum property in the 16 rightmost bits of the input. Our distinguishers improve
the 3.5 round (4-th order) integral distinguisher proposed by Z’aba et al. and
the 5 round (32-th order) integral distinguisher proposed by Zhang et al [17].
 Integral Attacks on Reduced-Round PRESENT 333

Finally, we applied our distinguishers to recover the keys up to 10 (out of 31)

rounds of PRESENT. All known integral attacks on reduced-round PRESENT
are summarized in Table 1.

Table 1. Summary of integral attacks on reduced-round PRESENT

Rounds Key Size Data Time Memory Attacks & Source

5 all N · 232 CP† - - (32-th order) integral distinguisher [17]
5 80 26.4 CP 225.7 - Bit-Pattern Based Integral [16]
6 80 222.4 CP 241.7 - Bit-Pattern Based Integral [16]
7 128 224.3 CP 2100.1 277 Bit-Pattern Based Integral [16]
7 80 28.3 CP 260 217 Section 5
8 80 210.1 CP 272.6 266 Section 5
9 80 220.3 CP 260 217 Section 5
10 128 222.4 CP 299.3 281 Section 5
† N is the number of sets required in a key-recover attack.

Even though we only restrict our attention on PRESENT in this work, the
algebraic techniques used in constructing longer integral distinguishers here may
be also applied to other block ciphers to improve their known integral attacks.
Outline of This Paper. In Section 2, we introduce the encryption process
of PRESENT, the definition of boolean functions and the basic idea of integral
attack. In Section 3, we analyze the properties of PRESENT’s S-box and present
some observations on the degree of boolean functions. The integral distinguishers
are constructed in Section 4 and attacks based on them are given in Section 5.
Finally, we conclude this paper.

2 Preliminaries
In this section, we briefly describe the block cipher PRESENT, boolean functions
and the integral attack.

2.1 Description of PRESENT

PRESENT [2], proposed by A. Bogdanov et.al in CHES 2007, is a 31-round
ultra-lightweight block cipher with block length 64 bits. It has two versions
supporting key length 80 bits and 128 bits, which will be denoted as PRESENT-
80 and PRESENT-128, respectively. The underlying structure of PRESENT is
a typical SP-network which has three layers in every round: AddRoundKey,
SBoxLayer and PLayer. In the AddRoundKey layer, a round key with 64 bits
is XORed to the current state. Then, one 4-bit Sbox is applied 16 times in
parallel in the SBoxLayer. Finally, a fully wired permutation P on the 64-bit
state is employed in the PLayer. The outline of one round PRESENT is shown
in Fig. 1. Notice that there is an AddRoundKey layer after round 31. The Sbox
334 S. Wu and M. Wang

Fig. 1. One round PRESENT

Table 2. The Sbox of PRESENT

x 0 12 3 45 6 7 8 9 ABCDEF
S(x) C 5 6 B 9 0 A D 3 E F 8 4 7 1 2

and P permutation used in PRESENT are illustrated in Table 2 and Table 3,

respectively.
The key schedule of PRESENT-80 is given below. Firstly, the 80-bit key
is stored in a key register K and represented as k79 k78 . . . k0 . In round i, the
most significant 64-bit keys are extracted as the subkey K (i) , that is, K (i) =
k79 k78 . . . k16 . Then, key register K = k79 k78 . . . k0 is updated as follows:
[k79 k78 . . . k1 k0 ] = [k18 k17 . . . k20 k19 ],
[k79 k78 k77 k76 ] = S[k79 k78 k77 k76 ],
[k19 k18 k17 k16 k15 ] = [k19 k18 k17 k16 k15 ] ⊕ round counter.
We omit the key schedule of PRESENT-128 here since we do not use it in this
paper.

Table 3. The PLayer of PRESENT. Bit i of state is moved to bit position P (i).

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
P (i) 0 16 32 48 1 17 33 49 2 18 34 50 3 19 35 51
i 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
P (i) 4 20 36 52 5 21 37 53 6 22 38 54 7 23 39 55
i 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
P (i) 8 24 40 56 9 25 41 57 10 26 42 58 11 27 43 59
i 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
P (i) 12 28 44 60 13 29 45 61 14 30 46 62 15 31 47 63

2.2 Boolean Functions

A boolean function f of n variables is a map from Fn2 → F2 . It can be expressed
as a polynomial in F2 [x1 , . . . , xn ]/(x21 − x1 , . . . , x2n − xn ), called algebraic normal
form. That is,
 Integral Attacks on Reduced-Round PRESENT 335

f (x1 , x2 , . . . , xn ) = aΛ
 xk . (1)
Λ⊆{1,2,...,n} k∈Λ

In the subsequent discussions, we denote by B2 [x1 , x2 , . . . , xn ] the set of all

boolean functions with variables x1 , x2 , . . . , xn . The algebraic degree (or degree)
of f , denoted by deg(f ), is the number of variables in the highest order term
with nonzero coefficient. For a further step, the degree of a vectorial boolean
function from Fn2 → Fm2 is defined as the highest degree of its coordinates.

2.3 Integral Attack

Let E = E1 ◦ E0 be the encryption function of an r round block cipher, where
E0 is the first k rounds of E and E1 is the last r − k rounds. It can be written
formally as
Y = E(X, K) = E1 (E0 (X, K0 ), K1 ),
or equivalently,
E1−1 (Y, K1 ) = E0 (X, K0 ), (2)
where E1−1 is the inverse function of E1 , K is the master key, K0 and K1 are
subkeys in the first k rounds and the last r − k rounds, respectively.
In integral attacks, an attacker first selects a set of 2d plaintext, where d bit
positions of X take on all values through the set and the other bits of X are
chosen to be arbitrary constants. Then, a zero-sum property of the set of plain-
texts propagating through k round encryptions is proved, that is, an attacker
demonstrates that
E0 (X, K0 ) = 0, (3)
X∈Λ

where Λ is the set of 2 plaintexts. Finally, the subkey K1 in the last r −k rounds
d

is guessed and equation

E1−1 (Y, K1 ) = 0 (4)

X∈Λ,Y =E(X,K)

is used to verify the guess. The remaining key bits in the master key K will be
obtained by exhausting method.
Notice that, the integral distinguisher (3) can be built upon a specific parts
of the output of E0 , that is, the zero-sum property may be only valid in some
specific bits. Based on the theorem of higher-order differential attack, (3) can
be proved by showing that some specific bits of the output of E0 have degree at
most d − 1.

3 Degree of Boolean Functions and PRESENT’s Sbox

In this section, we discuss some properties for evaluating the degree of boolean
functions and then analyze the algebraic properties of PRESENT’s Sbox.
336 S. Wu and M. Wang

Some trivial bounds for operations between (vectorial) boolean functions are
summarized in Proposition 1.
Proposition 1. Suppose f, g ∈ B2 [x1 , x2 , . . . , xn ] are two boolean functions, h is
a vectorial boolean function from Fn2 → Fn2 , then the degree of composed function
f ◦ h, product f · g and sum f ⊕ g can be evaluated as

deg(f ◦ h) ≤ deg(f )deg(h),

deg(f · g) ≤ deg(f ) + deg(g),
deg(f ⊕ g) ≤ max{deg(f ), deg(g)}.

Moreover, deg(f ), deg(g), deg(f ◦ h), deg(f · g) and deg(f ⊕ g) are less than or
equal to n.
These bounds are so loose that they are unfitted in some cases. Here, we
analyze the product of boolean functions and show a tighter degree bound in a
specific situation. First, we introduce the definition of m-partition.
Definition 1. Nonempty sets U1 , . . . , Um is called an m-partition of U = {x1 ,
x2 , . . . , xn }, if U = U1 ∪ · · · ∪ Um and Ui ∩ Uj = ∅ for 1 ≤ i < j ≤ m.
Let ni be the number of variables in Ui , then n = n1 +· · ·+nm . Our observation
is given below.
Proposition 2. Suppose U1 , . . . , Um is an m-partition of U = {x1 , x2 , . . . , xn },
f1 , f2 , . . . , fk is a list of boolean functions satisfying:
1. For each fi , there exists a j ∈ {1, 2, . . . , m} such that fi ∈ B2 [Uj ],
2. deg(fi ) ≤ nj − 1,
then, for any k ≤ 2m − 1, we have

deg(f1 · f2 · · · fk ) ≤ n − 1.

Proof. This can be explained as an allocation problem. Now, we have k tokens

f1 , . . . , fk and m boxes B2 [U1 ], . . . , B2 [Um ]. When throwing k ≤ 2m − 1 tokens
to m boxes, there must exist a box with the condition that it contains no more
than one token. Without loss of generality, suppose this box is B2 [U1 ].
If it’s empty, then all fi s do not involve variables in U1 , which implies

deg(f1 · f2 · · · fk ) ≤ n − n1 ≤ n − 1.

If it contains a token fi , then, from Proposition 1, we have

deg(f1 · f2 · · · fk ) ≤ deg(fi ) + deg(f1 · · · fi−1 · fi+1 · · · fk )

≤ (ni − 1) + (n − ni ) ≤ n − 1.

This property will be used for constructing integral distinguishers of

PRESENT, combining with the subsequent observations on PRESENT’s Sbox.
 Integral Attacks on Reduced-Round PRESENT 337

Proposition 3. The Sbox of PRESENT is a permutation S : F42 → F42 . It can be

expressed as a vectorial boolean function with four coordinates. Suppose its input
is a vector x = (x3 , x2 , x1 , x0 ) and output is a vector y = (y3 , y2 , y1 , y0 ), where


xi , yi ∈ F2 and 0 ≤ i ≤ 3. Then, the algebraic normal form of PRESENT’s Sbox
is:

 y3 = 1 ⊕ x0 ⊕ x1 ⊕ x3 ⊕ x1 x2 ⊕ x0 x1 x2 ⊕ x0 x1 x3 ⊕ x0 x2 x3 ;

 y2 = 1 ⊕ x2 ⊕ x3 ⊕ x0 x1 ⊕ x0 x3 ⊕ x1 x3 ⊕ x0 x1 x3 ⊕ x0 x2 x3 ;
y1 = x1 ⊕ x3 ⊕ x1 x3 ⊕ x2 x3 ⊕ x0 x1 x2 ⊕ x0 x1 x3 ⊕ x0 x2 x3 ;
y0 = x0 ⊕ x2 ⊕ x3 ⊕ x1 x2 ;

The correctness of Proposition 3 can be easily checked. From Proposition 3,

we immediately have
Corollary 1. The degree of PRESENT’s Sbox S is 3. However, its rightmost
coordinate is only quadratic, that is, deg(y0 ) = 2.

Corollary 2. Let f = cf ⊕ f0 ⊕ f2 ⊕ f3 ⊕ f1 f2 and g = cg ⊕ g0 ⊕ g2 ⊕ g3 ⊕ g1 g2 ,

where fi , gi ∈ B2 [xi ] for 0 ≤ i ≤ 3 and cf , cg ∈ F2 are constants, then we have
deg(f · g) ≤ 3.

According to the PLayer of PRESENT (see Fig. 1), all 16 quadratic coordi-
nates of Sboxes are translated to the rightmost 16 bits after one round encryp-
tion. Thus, we have

Observation. The growth rate of algebraic degree for the bits in the right side
of the output is slower than those in the left side.
After several rounds of encryption, the effect is finally accumulated to the
rightmost bit of the output. Therefore, in the subsequent discussions, we only
consider the degree for the rightmost bit of the output.

4 Integral Distinguishers of PRESENT

In this section, we proposed two integral distinguishers of PRESENT. We denote

by X (i) the state entering round i, Y (i) the state before the SBoxLayer, Z (i)
the state after the SBoxLayer and K (i) the subkey of round i. Thus, Y (i) =
X (i) ⊕ K (i) . Each state and subkey can be represented as a vector of 64 bits, for
(i) (i) (i) (i)
example, X (i) = (x63 , x62 , . . . , x0 ), where x0 is the least significant (rightmost)
(i)
bit of X . Additionally, let x[j−k] be the consecutive j − k + 1 bits of X (i) from
(i)

(i) (i) (i)

bit k to bit j, and x[j,...,k] represents several separate bits xj , . . . , xk of X (i) .

4.1 A 5 Round (4-th Order) Integral Distinguisher

In this subsection, we show a 4-th order integral distinguisher of PRESENT,

which provides us a 5-round integral distinguisher.
338 S. Wu and M. Wang

Proposition 4. Choose a set of 24 values in the input of round 2, where all

(2)
values of bits x[48,32,16,0] of input X (2) are chosen and other bits are chosen to
(6)
be arbitrary constants. Then, the rightmost bit of X (6) , that is, the bit x0 , has
a zero-sum property.

(6)
Proof. Consider x0 as a boolean function of X (2) , then we only need to prove
(6) (2) (2) (2) (2)
that x0 ∈ B2 [x48 , x32 , x16 , x0 ] has degree at most 3. The proof process is
shown in the phase T1 of Fig. 2.
(2) (2)
In round 2, since x[3−1] are fixed, then z[3−0] are affine functions with only
(2) (2) (2) (2) (2)
one variable x0 , that is, z[3−0] ∈ B2 [x0 ]. Similarly, we have z[19−16] ∈ B2 [x16 ],
(2) (2) (2) (2)
z[35−32] ∈ B2 [x32 ] and z[51−48] ∈ B2 [x48 ]. Other bits of Z (2) are constants.
(3) (2) (3) (2) (3)
In round 3, we have x[48,32,16,0] ∈ B2 [x0 ], x[52,36,20,4] ∈ B2 [x16 ], x[56,40,24,8] ∈
(2) (3) (2)
B2 [x32 ] and x[60,44,28,12] ∈ B2 [x48 ].
(4) (2) (4) (2) (4)
In round 4, we have x[12,8,4,0] ∈ B2 [x0 ], x[13,9,5,1] ∈ B2 [x16 ], x[14,10,6,2] ∈
(2) (4) (2)
B2 [x32 ] and x[15,11,7,3] ∈ B2 [x48 ].
In summary, bits marked with red color (resp. green color, blue color and
(2) (2)
purple color) in Fig. 2 are affine functions with only one variable x0 (resp. x16 ,
(2) (2)
x32 and x48 ). Other bits are not considered here since they are independent
(6)
of x0 .
In round 5, from the expression of Sbox, we have

(5) (5) (4) (4) (4) (4) (4)

yi = ki ⊕ y4i ⊕ y4i+2 ⊕ y4i+3 ⊕ y4i+1 · y4i+2 ,

(4) (2)
where y4i+j ∈ B2 [x16j ] for 0 ≤ j ≤ 3 and 0 ≤ i ≤ 3.
Finally,

(6) (5) (5) (5) (5) (5)

deg(x0 ) = deg(y0 ⊕ y2 ⊕ y3 ⊕ y1 · y2 )
(5) (5) (5) (5) (5)
≤ max{deg(y0 ), deg(y2 ), deg(y3 ), deg(y1 · y2 )}
≤ max{2, 2, 2, 3} = 3,

where the final inequation comes from Corollary 2.

A 5-round integral distinguisher is obtained by adding one round to the upper

side of the distinguisher given in Proposition 4.

Theorem 1. Choose a set of 24 values in the plaintext, where all values of

(1)
bits x[3,2,1,0] of input X (1) are chosen and other bits are chosen to be arbitrary
(6)
constants. Then, the rightmost bit of X (6) , that is, the bit x0 , has a zero-sum
property.
 Integral Attacks on Reduced-Round PRESENT 339

(1) (2)
Proof. It’s based on the fact that x[3−0] → x[48,32,16,0] is a permutation (see the
phase T2 of Fig. 2 with bold line). We have

(2) (1)
RK (5) ◦ · · · ◦ RK (2) (x[48,32,16,0] , c ) = RK (5) ◦ · · · ◦ RK (1) (x[3−0] , c),
(2) (1)
x ∈F4
2
x ∈F4
2
[48,32,16,0] [3−0]
(5)
where RK (i) is the round function with key K (i) , c is the constant chosen in the
plaintext and c is the constant deduced from c by one round encryption.

Fig. 2. 4-th order integral distinguisher of PRESENT

340 S. Wu and M. Wang

4.2 A 7 Round (16-th Order) Integral Distinguisher

In this subsection, we show a 16-th order integral distinguisher of PRESENT,

which provides us a 7-round integral distinguisher.

Proposition 5. Choose a set of 216 values in the input of round 3, where all
(3)
values of bits x4j (0 ≤ j ≤ 15) of input X (3) are chosen and other bits are
chosen to be arbitrary constants. Then, the rightmost bit of X (8) , that is, the bit
(8)
x0 , has a zero-sum property.
(8)
Proof. Consider x0 as a boolean function of X (3) , then we only need to prove
(8) (3) (3) (3) (3)
that x0 ∈ B2 [x60 , x56 , . . . , x4 , x0 ] has degree at most 15. The proof process
is shown in the phase T1 of Fig. 3.
(3) (3)
In round 3, we have z[4j+3,4j+2,4j+1,4j] ∈ B2 [x4j ] (0 ≤ j ≤ 15).
(4) (3)
In round 4, we have yi ∈ B2 [x4j ] (0 ≤ i ≤ 63), where j = i mod 16.
(5)
In round 5, from the expression of PRESENT’s Sbox, we have yi ∈
(3) (3) (3) (3) (5)
B2 [x16j+12 , x16j+8 , x16j+4 , x16j ] and deg(yi ) ≤ 3, where 0 ≤ i ≤ 63 and j = i
mod 4.
In summary, bits marked with red color (resp. green color, blue color and
(3) (3) (3) (3)
purple color) in Fig. 3 are boolean functions in B2 [x12 , x8 , x4 , x0 ] (resp.
(3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3)
B2 [x28 , x24 , x20 , x16 ], B2 [x44 , x40 , x36 , x32 ] and B2 [x60 , x56 , x52 , x48 ]) and
have degree at most 3.
(8) (8) (5)
Now, we consider x0 as a boolean function of Y (5) . Then, x0 ∈ B2 [y[63−0] ]
has representation
(8)
x0 = aΛ
 (5)
yk . (6)
Λ⊆{0,1,2,...,63} k∈Λ

(8) (3)

(5)  (3)

(3)
following discussions, we have to show that each term aΛ k∈Λ yk ∈ B2 [x60 , . . . ,
(3)
Notice that x0 is also a boolean function in B2 [x60 , . . . , x4 , x0 ]. Thus, in the

(3) (3)

x4 , x0 ] with aΛ = 0 has degree at most 15.
(5)
First, we show that deg( k∈Λ yk ) ≤ 15 if |Λ| ≤ 7. Here, |Λ| is the number of
(3) (3) (3)
elements in set Λ. Denote by U = {x4j |0 ≤ j ≤ 15} and Uk = {x16k+12 , x16k+8 ,
(3) (3)
x16k+4 , x16k } for 0 ≤ k ≤ 3, then U0 , . . . , U3 is a 4-partition of U . Notice that
(5)

yi (0 ≤ i ≤ 63) satisfies the condition of Proposition 2, which implies that

 (5)
deg( k∈Λ yk ) ≤ 15 if |Λ| ≤ 7. Therefore, we only need to check the terms
(5)
aΛ k∈Λ yk with aΛ = 0 and |Λ| ≥ 8.
Secondly, we show that aΛ is always zero in (6) if |Λ| > 8. According to
(6) (7)
Proposition 3 and Proposition 1, we have deg(y[15−0] ) ≤ 2, deg(y[3−0] ) ≤ 4
(8) (6) (7) (8)
and deg(x0 ) ≤ 8 if y[15−0] , y[3−0] and x0 are viewed as boolean functions in
(5)
B2 [y[63−0] ]. Thus, in (6), all aΛ = 0 if |Λ| ≥ 9, which implies that we only need
to consider the terms with |Λ| = 8.
 Integral Attacks on Reduced-Round PRESENT 341

Thirdly, we show that only one term in (6) may have |Λ| = 8. According to the
(8) (5)
algebraic normal form of PRESENT’s Sbox, x0 ∈ B2 [y[63−0] ] can be expressed
as follows.
(8) (7) (7) (7) (7) (7) (7) (7)
x0 = y0 ⊕ y2 ⊕ y3 ⊕ y1 y2  y1 y2
(7) (6) (6) (6) (6) (6) (7) (6) (6) (6) (6) (6)
= (k1 ⊕ y4 ⊕ y6 ⊕ y7 ⊕ y5 y6 )(k2 ⊕ y8 ⊕ y10 ⊕ y11 ⊕ y9 y10 )
(6) (6) (6) (6) (5) (5) (5) (5) (5) (5) (5) (5)
 y5 y6 y9 y10  y21 y22 y25 y26 y37 y38 y41 y42 ,

where  means that the terms with degree 8 can only appear in these products.
(5) (5) (5) (5) (5) (5) (5) (5)
Thus, the remaining work is to prove that y21 y22 y25 y26 y37 y38 y41 y42 is a
(3) (3) (3) (3)
boolean function with degree at most 15 in B2 [x60 , x56 , . . . , x4 , x0 ].
(5) (5) (5) (5) (5) (5) (5) (5) (3) (3) (3)
Finally, we show that y21 y22 y25 y26 y37 y38 y41 y42 ∈ B2 [x60 , . . . , x4 , x0 ]
(5) (3) (3) (3) (3)
has degree less than 15. Since y[41,37,25,21] ∈ B2 [x28 , x24 , x20 , x16 ] and
(5) (3) (3) (3) (3)
y[42,38,26,22] ∈ B2 [x44 , x40 , x36 , x32 ], we have
(5) (5) (5) (5) (5) (5) (5) (5)
deg(y21 y22 y25 y26 y37 y38 y41 y42 ) ≤ 8.


(8) (3) (3) (3) (3)
In summary, x0 ∈ B2 [x60 , x56 , . . . , x4 , x0 ] has degree
(8) (5) (5) (5) (5) (5) (5) (5) (5) (5)
deg(x0 ) = max{deg( yk ), deg(y21 y22 y25 y26 y37 y38 y41 y42 )} ≤ 15.
k∈Λ,|Λ|≤7

A 7-round integral distinguisher is obtained by adding two rounds to the

upper side of the distinguisher given in Proposition 5.

Theorem 2. Choose a set of 216 values in the plaintext, where all values of
(1)
bits x[15−0] of input X (1) are chosen and other bits are chosen to be arbitrary
(8)
constants. Then, the rightmost bit of X (8) , that is, the bit x0 , has a zero-sum
property.
(1) (3)
Proof. It’s based on the fact that x[15−0] → x[60,56,...,4,0] is a permutation. This
permutation is shown in phase T2 of Fig. 3 with bold line.

5 Integral Attack on Reduced-Round PRESENT

In this section, we attack reduced-round PRESENT using the 4-th order integral
distinguisher and 16-th order integral distinguisher.
The general attack procedure is given as follows.
1. Choose a set of 2n (n = 4 or n = 16) plaintexts to construct a structure,
where the rightmost n bits take all possible values of Fn2 while other bits are
chosen to be arbitrary constants over F2 . Obtain the corresponding cipher-
texts after r-round encryption.
342 S. Wu and M. Wang

Fig. 3. 16-th order differential characteristics of PRESENT

 Integral Attacks on Reduced-Round PRESENT 343

2. For every guessing of the corresponding subkeys in the last (r − m) rounds,

 
(m+1)
decrypt the ciphertexts to obtain the one bit state y0 after the m-th
round, where m is the length of integral distinguishers.
(m+1) (m+1)
3. Check whether Λ y0 (= Λ x0 ) is zero, where Λ with |Λ| = 2n
is the set of chosen plaintexts. If the equation is not satisfied, we know the
guessed subkey is wrong. Then, we guess another subkey and repeat until
the correct subkey is found.
4. Recover the remaining key bits in the master key by exhausting method.
Suppose we need to guess k bit subkey in the last (r − m) rounds, the com-


plexity of this attack can be estimated as follows. Step 1 needs about 2n plain-
texts which requires 2n encryptions. In step 2 and step 3, a subkey needs about
(m+1)
r × 2 encryptions. For a wrong subkey guess, equation
r−m n
Λ y0 = 0 holds
1
with probability 2 . Therefore, to discard all the wrong k-bit subkey guesses, we
need about k plaintext structures. Suppose the master key has |K| bits, then
the time complexity of step 4 is about 2|K|−k r-round encryptions.
Thus, the data complexity is about k × 2n chosen plaintexts. The time com-
plexity in recovering these k key bits is about
k
r−m k 1 r−m
(2n + 2n × 2 × ( )i−1 ) ≈ × 2n+k+1 (7)
i=1
r 2 r

n+k+1 |K|−k
r-round encryptions. So, the final time complexity is max{ r−mr ×2 ,2 }.
k
A total of 2 bits are required to keep track of possible values for the k key bits,
so the memory complexity is 2k−3 bytes.
(m+2)
To attack r = m + 2 round PRESENT, we need to guess 4 key bits k[48,32,16,0]
(m+3) (m+1)
in K (m+2) , 16 key bits k4j for 0 ≤ j ≤ 15 in K (m+3) to obtain state y0 .
Thus, when considering the 4-th order integral attack, we have n = 4, m = 5,
r = 7 and k = 20. In this case, we can recover 20 bit keys of 7-round PRESENT
with data complexity 20×24 ≈ 28.3 , time complexity 27 ×24+20+1 ≈ 223.2 7-round
encryptions and memory 217 bytes. To recover the master key of PRESENT-80,
we have to exhaust the remaining 60 key bits. Thus, the final time complexity is
260 . Similarly, when considering 16-th order differential attack, we can recover
20 bit keys of 9-round PRESENT with data complexity 220.3 , time complexity
234.8 9-round encryptions and memory 217 bytes. To recover the master key of
PRESENT-80, the final time complexity is 260 .
To attack r = m + 3 round PRESENT, we need to guess all of 64 key
bits in K (m+4) additionally, totally guessing 84 key bits. Utilizing the 16-th
order integral, we can attack 10 rounds of PRESENT-128 with data complex-
ity 222.4 , time complexity 299.3 10-round encryptions and memory 281 bytes.
The remaining 44 key bits can be obtained easily by exhausting method. To
attack 8 rounds of PRESENT-80 using 4-th order integral, we need some prop-
erties of the key schedule. After examining the key schedule for 80-bit keys, we
(m+3) (m+2)
find that bits k4j for j = 0 or 5 ≤ j ≤ 15 in K (m+3) and bits k[48,16,0] in
K (m+2) are given from guessing all of K (m+4) . Thus, in total we need to guess
344 S. Wu and M. Wang

64 + (16 − 12) + (4 − 3) = 69 bits of key, which leads to an attack of 8-round

PRESENT-80 with data complexity 210.1 , time complexity 272.6 8-round encryp-
tions and memory 266 bytes. The remaining 11 key bits can be obtained easily
by exhausting method.

6 Discussions and Conclusions

In this paper, we discuss the integral attack against bit-based block ciphers.
We focus on the block cipher PRESENT and show that integral attack can
be improved not only by the theorem of higher-order differential attack but
also by using specific algebraic properties of Sboxes. What is more, the order
of plaintexts in a set, which is important in bit-based integral attack, is not
required here.
Combined with the algebraic properties of PRESENT’s Sbox and its diffusion
layer, we proposed two integral distinguishers: one 5 round (4-th order) integral
distinguisher and one 7 round (16-th order) integral distinguisher, where the
latter is the longest integral distinguisher of PRESENT as far as we know. Based
on the integral distinguishers proposed in this paper, 10 (out of 31) rounds of
PRESENT can be attacked.
Although the number of attack rounds in this paper are not so impressive
as other statistical attacks [6,7,14], it is the first time that some new algebraic
properties for constructing integral distinguishers of PRESENT are reported.
For a further step, the algebraic techniques used in constructing longer integral
distinguishers here may be also applied to other block ciphers to improve their
known integral attacks.

Acknowledgements. We are grateful to the anonymous reviewers for their

valuable comments on this paper. This work was supported by the National
Basic Research Program of China (Grant No. 2013CB834203 and Grant No.
2013CB338002) and the National Natural Science Foundation of China (Grant
No. 11171323).

References
1. Anderson, R., Biham, E., Knudsen, L.: Serpent: A Proposal for the Advanced
Encryption Standard. NIST AES Proposal (1998),
http://www.cl.cam.ac.uk/rja14/serpent.html
2. Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw,
M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: An ultra-lightweight block cipher.
In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466.
Springer, Heidelberg (2007)
3. Bogdanov, A., Leander, G., Nyberg, K., Wang, M.: Integral and Multidimen-
sional Linear Distinguishers with Correlation Zero. In: Wang, X., Sako, K. (eds.)
ASIACRYPT 2012. LNCS, vol. 7658, pp. 244–261. Springer, Heidelberg (2012)
4. Bogdanov, A., Rijmen, V.: Linear Hulls with Correlation Zero and Linear Crypt-
analysis of Block Ciphers. Designs, Codes and Cryptography (2012)
 Integral Attacks on Reduced-Round PRESENT 345

5. Biryukov, A., Shamir, A.: Structural Cryptanalysis of SASAS. In: Pfitzmann, B.

(ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 394–405. Springer, Heidelberg
(2001)
6. Cho, J.Y.: Linear Cryptanalysis of Reduced-Round PRESENT. In: Pieprzyk, J.
(ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 302–317. Springer, Heidelberg (2010)
7. Collard, B., Standaert, F.X.: A Statistical Saturation Attack against the Block
Cipher PRESENT. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473,
pp. 195–210. Springer, Heidelberg (2009)
8. Daemen, J., Knudsen, L., Rijmen, V.: The block cipher Square. In: Biham, E. (ed.)
FSE 1997. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (1997)
9. Daemen, J., Peeters, M., Van Assche, G., Rijmen, V.: Nessie Proposal: NOEKEON.
In: First Open NESSIE Workshop (2000), http://gro.noekeon.org/
10. Ferguson, N., Kelsey, J., Lucks, S., Schneier, B., Stay, M., Wagner, D., Whiting,
D.: Improved cryptanalysis of Rijndael. In: Schneier, B. (ed.) FSE 2000. LNCS,
vol. 1978, pp. 213–230. Springer, Heidelberg (2001)
11. Knudsen, L., Wagner, D.: Integral Cryptanalysis. In: Daemen, J., Rijmen, V. (eds.)
FSE 2002. LNCS, vol. 2365, pp. 112–127. Springer, Heidelberg (2002)
12. Lai, X.: Higher order derivatives and differential cryptanalysis. In: Proc. Sympo-
sium on Communication, Coding and Cryptography, in Honor of J. L. Massey on
the Occasion of his 60th Birthday, Kluwer Academic Publishers, Dordrecht (1994)
13. Lucks, S.: Attacking seven rounds of Rijndael under 192-bit and 256-bit keys. In:
Proc. 3rd AES Candidate Conf., pp. 215–229 (2000)
14. Wang, M.: Differential Cryptanalysis of reduced-round PRESENT. In: Vaudenay,
S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 40–49. Springer, Heidelberg
(2008)
15. Yu, X., Wu, W., Li, Y., Zhang, L.: Cryptanalysis of Reduced-Round KLEIN Block
Cipher. In: Wu, C.-K., Yung, M., Lin, D. (eds.) Inscrypt 2011. LNCS, vol. 7537,
pp. 237–250. Springer, Heidelberg (2012)
16. Z’aba, M.R., Raddum, H., Henricksen, M., Dawson, E.: Bit-pattern based integral
attack. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 363–381. Springer,
Heidelberg (2008)
17. Zhang, W., Su, B., Wu, W., Feng, D., Wu, C.: Extending Higher-Order Integral:
An Efficient Unified Algorithm of Constructing Integral Distinguishers for Block
Ciphers. In: Bao, F., Samarati, P., Zhou, J. (eds.) ACNS 2012. LNCS, vol. 7341,
pp. 117–134. Springer, Heidelberg (2012)