Evaluation of security level of CLEFIAAn anonymous reviewer
Version 1.0 — January 25, 20111

Evaluation of security level of CLEFIA

1

Contents
Executive Summary3

References

4

1 Introduction

8

2 CLEFIA - short

8

3 Security aspects
3.1 Brute Force Attacks . . . . . . . . . . . . . . . . . . . . . . .
3.2 Diﬀerential cryptanalysis . . . . . . . . . . . . . . . . . . . . .
3.3 Diﬀerential characteristics for CLEFIA . . . . . . . . . . . . .
3.4 Linear Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . .
3.5 Truncated diﬀerential cryptanalysis . . . . . . . . . . . . . . .
3.6 Impossible diﬀerentials . . . . . . . . . . . . . . . . . . . . . .
3.6.1 Impossible diﬀerentials for CLEFIA . . . . . . . . . . .
3.7 Integral cryptanalysis . . . . . . . . . . . . . . . . . . . . . . .
3.7.1 Integrals for CLEFIA . . . . . . . . . . . . . . . . . . .
3.8 Higher order diﬀerential cryptanalysis . . . . . . . . . . . . . .
3.8.1 Higher order diﬀerentials for CLEFIA . . . . . . . . . .
3.8.2 Boomerang attack . . . . . . . . . . . . . . . . . . . .
3.9 Interpolation cryptanalysis . . . . . . . . . . . . . . . . . . . .
3.10 Algebraic cryptanalysis . . . . . . . . . . . . . . . . . . . . . .
3.11 The key scheduling algorithm . . . . . . . . . . . . . . . . . .
3.11.1 Weak keys . . . . . . . . . . . . . . . . . . . . . . . . .
3.11.2 Related key attacks . . . . . . . . . . . . . . . . . . . .
3.12 Known key security . . . . . . . . . . . . . . . . . . . . . . . .
3.13 The overall structure . . . . . . . . . . . . . . . . . . . . . . .
3.13.1 The diﬀusion matrices . . . . . . . . . . . . . . . . . .
3.14 The number of rounds . . . . . . . . . . . . . . . . . . . . . .
3.15 Implementation aspects . . . . . . . . . . . . . . . . . . . . . .

9
9
10
11
15
16
18
18
20
21
24
24
25
25
26
27
28
30
31
32
33
33
33

2

Executive Summary
We have performed a security evaluation of the cryptographic block cipher
CLEFIA as described in [28].
We have analysed the cipher with respect to the state-of-the-art cryptanalysis and we have found no serious weaknesses or attacks. It is further
believed that the security margin is suﬃcient with respect to the currently
known attacks.
Finally we would like to point out that this report is the result of alimited-time review.

3References[1] 3GPP. 3G TS 35.202 version 4.0.0: 3rd generation partnership project;technical speciﬁcation group services and system aspects. 3G security;
speciﬁcation of the 3GPP conﬁdentiality and integrity algorithms; document 2: KASUMI speciﬁcation. Available at www.3gpp.org.
[2] E. Biham and A. Shamir. Diﬀerential Cryptanalysis of the Data Encryption Standard. Springer, 1993.
[3] E. Biham. New types of cryptanalytic attacks using related keys (extended abstract). In T. Helleseth, editor, Advances in Cryptology EUROCRYPT’93, volume 765 of Lecture Notes in Computer Science,
Springer, pages 398–409, 1994.
[4] Alex Biryukov and Dmitry Khovratovich. Related-Key Cryptanalysisof the Full AES-192 and AES-256. In M. Matsui, editor, Advancesin Cryptology - ASIACRYPT 2009, volume 5912 of Lecture Notes in
Computer Science, Springer, pages 1–18, 2009.
[5] Alex Biryukov and Orr Dunkelman and Nathan Keller and Dmitry
Khovratovich and Adi Shamir. Key Recovery Attacks of Practical Complexity on AES-256 Variants with up to 10 Rounds. In H. Gilbert, editor,
Advances in Cryptology - EUROCRYPT 2010, volume 6110 of Lecture
Notes in Computer Science, Springer, pages 299–319, 2010.
[6] C. Cid and G. Leurent. An analysis of the XSL Algorithm. In Bimal Roy,
editor, Advances in Cryptology - ASIACRYPT 2005, Lecture Notes in
Computer Science, volume 3788, pages 333-352, Springer-Verlag, Chennai - India, December 2005.
[7] Nicolas T. Courtois, Alexander Klimov, Jacques Patarin, and Adi
Shamir. Eﬃcient Algorithms for Solving Overdeﬁned Systems of Multivariate Polynomial Equations. In B. Preneel, editor, Advances in Cryptology - Eurocrypt 2000, volume 1807 of Lecture Notes in Computer
Science, pages 392–407. Springer-Verlag, 2000.
[8] Nicolas T. Courtois and Josef Pieprzyk. Cryptoanalysis of Block Cipherswith Overdeﬁned System of equations. In Y. Zheng, editor, Advances in
Cryptology -Asiacrypt 2002, volume 2501 of Lecture Notes in Computer
Science, pages 267–287. Springer-Verlag, 2002.
4

[9] Claus Diem. The XL-Algorithm and a Conjecture from Commutative
Algebra. In P .J. Lee, editor, Advances in Cryptology - ASIACRYPT
2004, volume 3329 of Lecture Notes in Computer Science, pages 323–
337, 2004.
[10] ECRYPT Network of Excellence. ECRYPT Yearly Report on Algorithms and Keysizes (2009-2010). Available at http://www.ecrypt.
eu.org/documents/D.SPA.13.pdf[11] T. Jakobsen and L. Knudsen. The interpolation attack on block ciphers.
In E. Biham, editor, Fast Software Encryption, FSE 1997, volume 1267
of Lecture Notes in Computer Science, Springer, pages 28–40, 1997.
[12] J. Kelsey, B. Schneier, and D. Wagner. Key-schedule cryptoanalysis of
IDEA, G-DES, GOST, SAFER, and Triple-DES. In N. Koblitz, editor,
Advances in Cryptology - CRYPTO’96, volume 1109 of Lecture Notes
in Computer Science, Springer, pages 237–251, 1996.
[13] L. R. Knudsen. Truncated and higher order diﬀerentials. In B. Preneel,
editor, Fast Software Encryption, FSE 1994, volume 1008 of Lecture
Notes in Computer Science, Springer, pages 196–211, 1995.
[14] L. R. Knudsen and D. Wagner. Integral cryptanalysis. In J. Daemen
and V. Rijmen, editors, Fast Software Encryption, FSE 2002, February
2002, volume 2365 of Lecture Notes in Computer Science, Springer,
pages 112–127, 2002.
[15] L. R. Knudsen and Vincent Rijmen. Known-Key Distinguishers for Some
Block Ciphers. In K. Kurosawa, editor, Advances in Cryptology - ASIACRYPT 2007, volume 4833 of Lecture Notes in Computer Science,
Springer, pages 315–324, 2007.
[16] X. Lai. Higher order derivatives and diﬀerential cryptanalysis. In
R. Blahut, editor, Communication and Cryptography, Two Sides of One
Tapestry. Kluwer Academic Publishers, 1994. ISBN 0-7923-9469-0.
[17] C.-W. Lim and K. Khoo. An Analysis of XSL Applied to BES.
A. Biryukov (ed): Lecture Notes in Computer Science, FSE 2007,(4593), pages 242–253, Springer-Verlag Heidelberg Berlin, 2007.

5

[18] M. Matsui. Linear cryptanalysis method for DES cipher. In T. Helleseth, editor, Advances in Cryptology - EUROCRYPT’93, volume 765 ofLecture Notes in Computer Science, Springer, pages 386–397, 1994.
[19] M. Matsui and A. Yamagishi. A new method for known plaintext attack of FEAL cipher. In R. Rueppel, editor, Advances in Cryptology EUROCRYPT’92, volume 658 of Lecture Notes in Computer Science,
Springer, pages 81–91, 1993.
[20] National Institute of Standards and Technology. Advanced encryption
standard. Federal Information Processing Standard (FIPS), Publication
197, U.S. Department of Commerce, Washington D.C., November 2001.
[21] National Institute of Standards and Technology. Data encryption standard. Federal Information Processing Standard (FIPS), Publication 46,
U.S. Department of Commerce, Washington D.C., January 1977.
[22] K. Nyberg and L. R. Knudsen. Provable security against a diﬀerential
attack. J. Cryptology, 8(1):27–37, 1995.
[23] X. Lai, J. L. Massey, and S. Murphy. Markov ciphers and diﬀerential cryptanalysis. In D.W. Davies, editor, Advances in Cryptology EUROCRYPT’91, volume 547 of Lecture Notes in Computer Science,
Springer, pages 17–38, 1992.
[24] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook ofApplied Cryptography. CRC Press, 1997.
[25] National Institute of Standards and Technology. Advanced encryption
standard. FIPS 197, US Department of Commerce, Washington D.C.,
November 2001.
[26] R. L. Rivest. The RC5 encryption algorithm. In B. Preneel, editor,
Fast Software Encryption, FSE 1994, volume 1008 of Lecture Notes in
Computer Science, Springer, pages 86–96, 1995.
[27] R. L. Rivest, M.J.B. Robshaw, R. Sidney, and Y.L. Yin. The RC6
block cipher. Submitted as candidate for AES. Available at http://
www.nist.gov/aes.

6[28] Sony Corporation. The 128-bit Blockcipher CLEFIA. Algorithm Speciﬁcation. Revision 1.0. January 29, 2010.
[29] Sony Corporation.
The 128-bit Blockcipher CLEFIA. Security
and Performance Evaluations Revision 1.0, June 1, 2007. Available from http://www.sony.net/Products/cryptography/clefia/
technical/data/clefia-eval-1.0.pdf[30] D. Wagner. A Generalized Birthday Problem. In M. Yung, editor,
Advances in Cryptology – Crypto 2002, volume 2442 of Lectures Notes
in Computer Science, pages 288–303. Springer, 2002.
[31] Wenying Zhang and Jing Han. Impossible Diﬀerential Analysis of Reduced Round CLEFIA. In M. Yung, P. Liu, and D. Lin, editors, Inscrypt
2008, volume 5487 of Lectures Notes in Computer Science, pages 181–
191. Springer, 2009.

7

1

Introduction

This report presents the results of a limited evaluation of the block cipher
CLEFIA. In the work order speciﬁcation it is required that CLEFIA is evaluated with respect to the following attacks:
1.

• Diﬀerential Attack (including Truncated Diﬀerential Attack, Impossible Diﬀerential Attack)• Linear Attack (including Truncated Linear Attack)• Higher Order Diﬀerential Attack• Interpolation Attack• Algebraic Attack (including XL attack and XSL attack)• Related Key Attack and• The existence of weak keys and semi-weak keys

2. (Optional) Any other attacks speciﬁc to CLEFIA and Heuristic security
In the following all these attacks are considered except for the truncatedlinear attack. We could only ﬁnd one reference about this attack and thisreference is not available to us.

2

CLEFIA - short

Here we describe CLEFIA in short. For full details the reader is referred to[28].
CLEFIA is block cipher with 128-bit blocks and a choice of 128-bit, 192bit and 256-bit keys. The structure of the cipher is a so-called generalised
Feistel network with four data lines, each carrying 32-bit words, see Figure 1.
The functions F0 and F1 both take a 32-bit subkey and a 32-bit input, andboth return a 32-bit word. First the subkey is combined with the data input
using the exclusive-or operation. The 32-bit result is split into four bytes, andthe bytes are evaluated through the S-boxes S0 and S1 , such that, two bytes
are substituted using S0 and two bytes are substituted using S1 . The orderof use of S0 and S1 is diﬀerent for F0 and F1 . The four substituted bytes
are input to a linear transformation built from MDS codes. This element
is borrowed from the AES and guarantees that the round function provides
some level of an avalanche eﬀect. Later we describe some more details about
the generation of subkeys. We refer to [28] for further details.
8

rk2i−2rk2i−1

F0

F1

rk2i

rk2i+1

F0

F1

?

?

?

?

Figure 1: The CLEFIA network with two rounds. F0 and F1 are bijective
mappings for ﬁxed values of the rki s.

3

Security aspects

In this section we report on some cryptanalytic ﬁndings in CLEFIA. CLEFIA
is an iterated cipher which runs in either 18, 22, or 26 rounds depending on
the choice of size of the key of 128, 192, respectively 256 bits.

3.1

Brute Force Attacks

We shall brieﬂy comment on brute-force attacks against the 128-bit key. The
European project ECRYPT issues a yearly report on algorithms and key
sizes [10], and we base our evaluation on this report. We refer to [10] formany more details on this topic.
When studying the security of a key against an attacker who performs a
simple brute-force attack, and exhaustive search for the key, the best thingis to get a good model of the nature of the attacker and of the computational
resources the attacker is in possession of. An attacker could be a single
human being which is trying to “hack” from a single PC, it could be acompany doing industrial spionage using hundreds of computers, or to go to
an extreme, it could be an intelligence agency with a huge budget and using
special-constructed and dedicated hardward to search the key space. The
conclusion of ECRYPT is that a 128-bit key provides long-term protection
against all these adversaries. A 128-bit key size is a good, generic application-9independent recommendation, and should provide security for at least thenext 20 years.

3.2

Diﬀerential cryptanalysis

The most general method of analysing conventional cryptosystems today is
diﬀerential cryptanalysis, published by Biham and Shamir in 1990. The
method has proved to be relatively eﬃcient and has been applied to a wide
range of iterated ciphers see e.g., [2]. Furthermore, it was the ﬁrst attack
which could (theoretically) recover DES keys in time less than the expected
cost of exhaustive search [2]. In the following a brief description of diﬀerential
cryptanalysis with respect to a general n-bit iterated cipher.
First, one deﬁnes a diﬀerence between two bit strings, s and s′ of equal
length as∆s = s ⊕ s̃−1 ,(1)where ⊕ is the group operation on the group of bit strings used to combine
the key with the text input in the round function and where t−1 is the inverse
element of t with respect to ⊕. One of the main ideas behind this is, thatthe diﬀerences between the texts before the key is inserted and the diﬀerence
between the texts after the key is inserted are equal, so the diﬀerence is independent of the key through this operation. In a strong encryption algorithm
there will be some parts of the cipher where a diﬀerence cannot hold withcertainty. In a diﬀerential attack one exploits that for certain diﬀerences in
the input to the a particular function, the distribution of output diﬀerencesof is non-uniform. One deﬁnes characteristics [2]:Deﬁnition 1 An r-round characteristic is a series of diﬀerences deﬁned as
an r + 1-tuple {α0 , α1 , . . . , αr }, where ∆c0 = α0 , ∆ci = αi for 1 ≤ i ≤ r.
Deﬁne pi as the probability that inputs of diﬀerence αi−1 lead to output of
diﬀerence αi , where the probability is taken over all choices of the round key
and the inputs to the ith round. In [23] the notion of a Markov cipher was
introduced. In a Markov cipher this probability is independent of the actual
inputs of the round and is calculated over all possible choices of the roundkey. Also in [23] it was shown that in a Markov cipher if the round keys are
independent, the pi ’s are also independent andPr(∆cr = αr | ∆c0 = α0 ) =

r
∏
i=1

10

Pr(∆ci = αi | ∆ci−1 = αi−1 ).

(2)

3.3

Diﬀerential characteristics for CLEFIA

We computed the maximum probabilities over the S-boxes of CLEFIA. From
our implementations it follows that the maximum probability of a diﬀerential
characteristic through S0 is 10/256. Also, the maximum probabilities ofdiﬀerentials over S1 are 2−6 .
One of the most eﬃcient ways to build diﬀerential characteristics is to
identify so-called iterative characteristics over a small number of rounds,
which can then be concatenated to cover more rounds. With identical inputs
to the functions F0 and F1 one gets identical outputs, hence a diﬀerential
characteristic of probability one can be established. In order to maximise
the probability of diﬀerential characteristics one often tries to maximise thenumber of probability-one transitions. Next we examine iterative characteristics.
Consider a 1-round iterative characteristic
a

b

c

F0

d
F1

a

b

c

d

1r

(a, b, c, d) → (a, b, c, d),where the diﬀerences in the four 32-bit words are a, b, c, respectively d. It
follows that it must hold thata = d and b = cFFand that a →0 a ⊕ b and b →1 a ⊕ b. Since F0 and F1 are bijective mappings, it
must further hold that a ̸= 0, b ̸= 0 and a ̸= b. From these observations andfrom the properties of F0 and F1 it follows that if a has one active S-box,
then b has at least three active S-boxes. And if a has two active S-boxes,
then b has at least one. Therefore one can conclude that for a one-round
iterative characteristic there will be at least four active S-boxes per round.
10 2) ≈ 2−18 for one
Such a characteristic will have a probability of at most ( 25611round. When iterated to 12 rounds this gives a probability of approximately
2−216 .
Consider next a 2-round iterative characteristic
2r(a, b, c, d) → (a, b, c, d),which is depicted here:
a

b

c

F0

d

F1

c

b

F0

a

d

a
F1

b

c

d

It follows from this picture that the following four transitions must occur:F

a →0 b + d,
F

c →1 b + d,
F

b →1 a + c,F

d →0 a + c.
Also, if one of a, b, c, or d is zero, then the other three will also be zeros. In
other words,
if a = 0 then (b, c, d) = (0, 0, 0),
if b = 0 then (a, c, d) = (0, 0, 0),
if c = 0 then (a, b, d) = (0, 0, 0),
if d = 0 then (a, b, c) = (0, 0, 0).
12

As an example, if a = 0 then b = d, which follows from the ﬁrst transition,
since F0 is a bijection. If b = d, then c = 0, which follows from the second
transition and from the fact that F1 is a bijection. If c = 0, then b = 0, which
follows from the third transition and it follows that then also d = 0.
If all four words are zero, then we have a trivial characteristic over two
rounds with equal inputs and equal outputs. Therefore, to be of any use incryptanalysis all four words must be nonzero. We conjecture, without proof,that the number of active S-boxes in such a 2-round characteristic must be
at least six. Such a characteristic will have a probability of at most 2−28 for
two rounds. When iterated to twelve rounds this gives a probability of at
most 2−168 . Note that this is a bound and there is no guarantee that one canﬁnd such a characteristic.
Extending the above analysis to three rounds is possible but the numberof possibilities to examine grows. Instead one can do a computer search fordiﬀerential characteristics just counting the number of active S-boxes. This
does not always lead to a real diﬀerential characteristic but it gives bounds
for the best diﬀerential characteristics possible.
This computer search program starts from a number of active S-boxes ineach of the four words of the plaintext diﬀerence. Then it allows for diﬀerent
transitions through the functions F0 and F1 . Since the branch number ofboth these functions is ﬁve, with one active S-box in the input, there will
be four active S-boxes in the output. With two active S-boxes in the input,
there can be three or four active S-boxes in the output. With three active
S-boxes in the input, there can be two, three or four active S-boxes in the
output. And with four active S-boxes in the input, there can be between one
and four active S-boxes in the output. The program tries all possibilities.
Also, the xor operation of the right half of the round input and the otuputof the Fi (i = 0, 1) functions can cancel active S-boxes or create new ones.
Again, the program tries all possibilities. Our search shows that the numberof active S-boxes for any 4-round diﬀerential characteristic is at least 6, forany 5-round diﬀerential characteristic the number is at least 8, and for any
6-round diﬀerential characteristic the number is at least 12. A 6-round dif10 12
ferential characteristic will then have a probability of at most ( 256) ≈ 2−56 .
When iterated to 12 rounds one gets a probability of at most 2−112 . Thisis low enough to conclude that any attack based on traditional diﬀerential
characteristic will not be able to cryptanalyse any variant of CLEFIA.
Note that the above 6-round or 12-round characteristics might not exist
and if they do they could be hard to ﬁnd. Next we consider a 3-round
13

0

b

0

F0

b

F1

0

d

F0

e

0
F1

d

f

F0

0

d

b
F1

f

0

e

Figure 2: A 3-round diﬀerential characteristic.
iterative characteristic
3r(a, b, c, d) → (a, b, c, d),for which we can easily bound the exact number of active S-boxes. Consider
Figure 2.
We have chosen a = c = 0. Then, for some values of e and f , if thefollowing transitions holdF

b →0 e,F

e →0 d,F

d →1 f,F

f →1 b,14

then one can specify the following 3-round characteristic
3r(0, b, 0, d) → (0, f, 0, e).
This characteristic concatenated to itself yields a six-round iterative characteristic
6r(0, b, 0, d) → (0, b, 0, d).
It follows that to be useful in cryptanalysis both b and d must be nonzero.
If b = 0, then e = 0, but then d = 0, and then f = 0. Similarly, if d = 0,then f = 0, but then b = 0, and then e = 0.
It is rather easy to estimate the number of active S-boxes for the above
four transitions. The branch numbers of F0 and F1 are both ﬁve, so thenumber of active S-boxes for b and e in unison is ﬁve, and ﬁve also for dand f in unison. Consequently, there will be at least ten active S-boxes in
10 10
the 3-round characteristic and the probability will be at most ( 256) ≈ 2−48 .
When iterated to 12 rounds one gets a probability of at most 2−192 .
It is safe to conjecture that there are no useful diﬀerential characteristics
for any variants of CLEFIA.

3.4

Linear Cryptanalysis

Linear cryptanalysis was proposed by Matsui in 1993 [18]. A preliminary
version of the attack on FEAL was described in 1992 [19]. Linear cryptanalysis is a known plaintext attack in which the attacker exploits linear
approximations of some bits of the plaintext and ciphertext. In the attackon iterated ciphers the linear approximations are obtained by combining approximations for each round under the assumption of independent roundkeys. The attacker hopes in this way to ﬁnd an expression(m · α) = (c · β)(3)where α, β are n-bit strings and where ‘·’ denotes the dot product, whichholds with probability p ̸= 12 over all keys, such that |p − 21 |, called the bias,
is maximal. As in diﬀerential cryptanalysis one can deﬁne characteristics to
be used in linear cryptanalysis. The number of known plaintexts needed suchthat the relation (3) can be eﬀectively detected is approximately |p − 1/2|−2 .
We computed the maximum linear probabilities over the S-boxes of CLEFIA. From our implementations it follows that the maximum correlation of15

a linear characteristic through S0 is (2 · 28/256)2 ≃ 2−4.39 . 1 Also, themaximum correlations of linear characteristics over S1 are 2−6 .
The detection of linear characteristics is very similar to the detection of
diﬀerential characteristics. Since the highest correlation through one S-box
is very close to the highest probability of a diﬀerential characteristic for one
S-box (10/256 ≈ 2−4.67 ). Therefore, we feel that it is safe to conjecture that
there are no useful linear characteristics for any of the variants of CLEFIA.

3.5

Truncated diﬀerential cryptanalysis

In some ciphers it is possible and advantageous to predict the values of only
parts of the diﬀerences after each round of the cipher. Let {α0 , α1 , . . . , αs },be an s-round characteristic. Then {α0′ , α1′ , . . . , αs′ } is called a truncatedcharacteristic, if αi′ is a subsequence of αi . Truncated characteristics wereused to some extent in [2] but only in the outer rounds of a cipher. Notethat a truncated characteristic is a collection of characteristics and therefore
reminiscent of a diﬀerential. A truncated characteristic contains all characteristics {α0′′ , α1′′ , . . . , αs′′ } for which trunc(αi′′ ) = αi′ , where trunc(x) is thetruncated value of x, where the truncation is not further speciﬁed here. The
notion of truncated characteristics extends in a natural way to truncateddiﬀerentials introduced in [13].
We ﬁrst restrict ourselves to truncated diﬀerentials with diﬀerences split
into four 32-bit words, and the diﬀerence in each word is either zero or
nonzero. It follows by easy computer simulations, that there is a ﬁve-roundtruncated diﬀerential of this type for CLEFIA. With equal values in the ﬁrst
(leftmost), the third and the fourth (rightmost) words, and diﬀerent values
in the second words, one gets that there is always a nonzero diﬀerence inthe fourth words of the ciphertexts after ﬁve rounds of encryption. Consider
Figure 3.
It follows thatb ̸= 0 ⇒ c ̸= 0,c ̸= 0 ⇒ d ̸= 0, andd ̸= 0 ⇒ e ≠ 0This correlation is defined as (2(p − 12 ))2 where p − 12 denotes the bias of the linear
approximation
1

16

0

b

0

F0

b

F1

0

0

F0

c

0

F0

b

F0

c
F1

b

f

F0

g

b
F1

0

e

0
F1

0

d

0

d
F1

f

h

e

Figure 3: A 5-round truncated diﬀerential characteristic, where b ̸= 0 ande ̸= 0.
17

Evidently there is the possibility to split each word into four bytes andconsidering byte-diﬀerences. However, since the four bytes in each 32-bit
word are mixed in a strong way via eight-bit S-boxes and MDS-matrices,
there is little chance that the above ﬁve-round structure can be iterated tomore than a few extra rounds. In our opinion it is safe to conclude thatfor CLEFIA reduced to ten rounds, there are no useful truncated diﬀerentials. As as special case of truncated diﬀerentials are the so-called impossible
diﬀerentials, which we consider next.

3.6

Impossible diﬀerentials

Impossible diﬀerentials is another name for diﬀerential characteristics ofprobability zero. These diﬀerentials can be used in diﬀerential cryptanalysis and are in general as eﬀective as high-probability diﬀerentials. However,diﬀerentials of very low probability are not trivial to ﬁnd. One popularmethod is as follows. Imagine that a cipher can split into two parts, e0 ande1 . Assume that one can ﬁnd a diﬀerential through e0 , e.g.,
e

0
α→
β

with probability one, and assume that one can ﬁnd a diﬀerential through theinverse of e1 , e.g.,
e−1

1
γ →
η

also with probability one. Then if β ̸= η one can establish a diﬀerential ofprobability zero through e1 ◦ e0 :e ◦e

α 1→0 γof probability zero.
3.6.1

Impossible diﬀerentials for CLEFIA

We implemented a search for impossible diﬀerentials for CLEFIA, or rather
for ciphers with the same structure as CLEFIA, the generalized type-2 transformation. Our tests identify there are impossible diﬀerentials over 9 roundsof CLEFIA. Next we explain this phenomenon. Consider the 5-round trun-

18

e′

b

d′

F0

c′

F1

d′

0

F0

0

c′

b

F0

F1

b

0

F0

b

b
F1

0

0

f′

0
F1

0

0

0

Figure 4: A 4-round truncated diﬀerential characteristic for the decryption
operation, where b ̸= 0.
19

cated diﬀerential of Figure 3 and the 4-round truncated diﬀerential of Figure 4. If we concatenate the two diﬀerentials, we require that
g
f
h
e

=
=
=
=

b,
e′ ,
d′ , andf ′.

Note also, that b ̸= 0 and e ̸= 0. Consequently, it must be the case that
two inputs to F0 of nonzero diﬀerence e in the ﬁfth round of the diﬀerential
lead to equal outputs. However, since F0 is a bijection for a ﬁxed key, this is
impossible. Hence the 9-round truncated diﬀerential
9r(0, b, 0, 0) → (b, 0, 0, 0)
has probability zero. This conﬁrms the analysis made in [29].
Also, our tests conﬁrm that for 10 rounds (or more) of this structure there
are no impossible diﬀerentials. We stress that our tests were conducted withrandomly chosen bijections (F -functions) in the round functions. Such testsfor (real) CLEFIA would require computational resources out of our reach.
The 9-round impossible diﬀerentials can be used to recover key material
for reduced-round versions of CLEFIA. The best such known attack appears
to be the one of [31], which speciﬁes a key-recovery attack for a variant of
CLEFIA reduced to 14 rounds with a 128-bit key but where the key-whitening
layers have been ignored.

3.7

Integral cryptanalysis

Let S be a multiset of vectors. An integral over S is deﬁned as the sum of
all vectors in S. In other words, the integral is
∫
∑
S=
v,
v∈S

where the summation is deﬁned in terms of a particular group operation, for
CLEFIA we consider the exclusive-or operation.
In an attack, one tries to predict the values in the integrals after a certain
number of rounds of encryption. For this purpose it is advantageous to20

distinguish between the three cases: where all ith words are equal, where all
ith words are pairwise distinct, or where all ith words sum to a certain value
predicted in advance.
Let us introduce the following symbols for words in an integral. For aﬁrst-order integral, the symbol ‘C’ (for “Constant”) in the ith entry, meansthat the values of all ith words in the collection of texts are equal. The
symbol ‘A’ (for “All”) means that all words in the collection of texts are
diﬀerent, and the symbol ‘B’ (for “Balanced”) means that the exclusive-or
sum of all ith words is zero. Finally, we will write ‘?’ when the sum of words
can not be predicted. For more details, please consult [14].
3.7.1

Integrals for CLEFIA

We have identiﬁed a structure which can be used to distinguish CLEFIA
from a randomly chosen permutation after eight rounds of encryption. The
structure can be used in a key-recovery attack on CLEFIA reduced to nine
and ten rounds of encryption.
There is the following six-round integral with 232 texts
6R(C, A, C, C) → ( ? , ? , ? , B),
where each symbol is indicating the values of particular 32-bit words. The
round transitions are as follows:
1r(C, A, C, C) → (A, C, C, C)
1r→ (A, C, C, A)
1r→ (A, C, A, A)
1r→ (A, A, B, A)
1r→ (B, B, ? , A)
1r

→ ( ? , ? , ? , B)
This integral can be used to construct a seven-round integral with 264 chosen
plaintexts, which holds with probability one. Note that the rightmost and2nd rightmost words of the inputs to one round map to the 2nd leftmost
and 2nd rightmost words of the inputs to the following round. Consider astructure of 264 chosen plaintexts which have constant values in the two leftmost words but which are pairwise diﬀerent in the remaining 64 bits. Then
21

after one round of encryption one has a structure of 264 chosen plaintexts
which have constant values in leftmost and rightmost words but are pairwise
diﬀerent in the middle 64 bits. Thus this structure contains 232 structuresof each 232 texts, and each such structure forms an integral with notation(C, A, C, C). Since the texts in each of these structures are balanced in therightmost words after six rounds of encryption, so is the sum of all 232 structures. Thus there is a 7-round integral of the form
7R

(C, C, A, A) → ( ? , ? , ? , B).
Using similar arguments one can show that there is an eight-round integral
for CLEFIA which requires 296 chosen plaintexts and which holds with probability one. It has the notation
8R(A, C, A, A) → ( ? , ? , ? , B).
This structure can be used in a key-recovery attack on CLEFIA reduced tonine rounds of encryption. The attack requires a structure of 296 chosen
plaintexts and a running time of 296 simple operations and ﬁnds 32 bits ofthe secret subkeys.
Attack on 9-round CLEFIA. The attack is constructed as follows.
1. Construct a set of 296 chosen, diﬀerent plaintexts xi for i = 1, . . . , 296 ,such that these texts have equal values in the second leftmost 32-bit
word. Request the encryptions, yi of xi for i = 1, . . . , 296 .
2. Compute the exclusive-or of the rightmost 32-bit words of all yi s. Name
this sum Y .
3. Count the frequencies of the values in the second rightmost 32-bit wordsof all ciphertexts. Make a list, L, of those 32-bit values which have odd
frequencies. (Since we are computing exclusive-or sums of all words,
those which occur an even number of times will cancel out).
4. For all values, t, of the last-round subkey rk2r−1 , here r = 9, do thefollowing:(a) Compute the exclusive-or, Z, of the values F1 (t, z) for all valuesz ∈ L.
22

(b) If Z = Y , then t is a candidate value for rk2r−1 . If Z ̸= Y , then t
is not the correct value for rk2r−1 .
Note that for the correct value of rk2r−1 one gets Z = Y , since the integral
promises that the exclusive-or of the fourth words after eight rounds is zero.
For an incorrect value of rk2r−1 we assume that one gets Z = Y only with aprobability of 2−32 . If more than one value of rk2r−1 remains after the above
procedure, the attack can be repeated on another structure of 296 plaintexts.
Note that in step three above, we need not consider values of z which occur
an even number of times, since the exclusive-or of these results through F1
is zero.
The attack can be extended to CLEFIA reduced to ten rounds whichﬁnds 64 bits of the subkeys.
Attack on 10-round CLEFIA. The attack goes as follows.
1. Construct a set of 296 chosen, diﬀerent plaintexts xi for i = 1, . . . , 296 ,such that these texts have equal values in the second leftmost 32-bit
word. Request the encryptions, yi of xi for i = 1, . . . , 296 .
2. Compute the exclusive-or, Y , of the rightmost 32-bit words of all yi s.
3. For all values, t1 , of the last-round subkey rk2r−2 , and for all values, t2 ,of the subkey wk2 ⊕ rk2r−3 , here r = 10, do the following:(a) For each ciphertext ci = (ci,0 , ci,1 , ci,2 , ci,3 ) compute
Zi = F0 (rk2r−1 , ci,0 ) ⊕ ci,1 ,then computeYi = F1 (rk2r−3 , Zi ) ⊕ ci,2 .
∑Compute the exclusive-or of all Yi , Y = i Yi .
(b) If Y = 0, then (t1 , t2 ) are candidate values for rk2r−2 , and wk2 ⊕rk2r−3 . If Y ̸= 0, then (t1 , t2 ) are not the correct values for rk2r−2 ,and wk2 ⊕ rk2r−3 .
Each incorrect 64-bit value (t1 , t2 ) will be a candidate value with a probabilityof 2−32 . Therefore the attack needs to be repeated at least once with adiﬀerent set of chosen plaintexts. This attack ﬁnds 64 bits of information
about the round keys. Note that for each key guess (64 bits) one needs to do23

at most 232 evaluations of F0 and 232 evaluations of F1 , and thus the overall
complexity is close to 2128 evaluations of the function F .
In an extension to 11 rounds of CLEFIA, it appears that one has to guesson ﬁve subkeys of each 32 bits. Given the large amount of chosen plaintexts
needed in this attack, such an attack is completely out of reach for even themost powerful attackers.

3.8

Higher order diﬀerential cryptanalysis

In [16] a deﬁnition of higher order derivatives of discrete functions was given.
Later higher order diﬀerentials were used to cryptanalyse ciphers presumably
secure against conventional diﬀerential attacks [13] and further developed in[11].
A dth order diﬀerential is a collection of 2d (ﬁrst-order) diﬀerentials. The
main idea in the higher order diﬀerential attack is the fact that a dth order
diﬀerential of a function of nonlinear order d is a constant. Consequently, ad+1st order diﬀerential of the function is zero. Assume that (a subset of) the
output bits of the reduced cipher are expressible as a low-degree polynomial
p(x) ∈ GF (2)[x1 , x2 , . . . , xi ], where x1 , x2 , . . . , xi is a subset of input bits to
the reduced cipher. If this polynomial has degree not higher than d, then∑p(x) = c,x∈Ldwhere Ld denotes a d-dimensional subspace of GF (2)n and c a constant.
This method was applied to the cipher example given in [22]. This cipher is“provably secure” against a diﬀerential attack but can be broken in a higher
order diﬀerential attack with relatively low complexity.
3.8.1

Higher order diﬀerentials for CLEFIAThe success of attacks based on higher order diﬀerentials depends on thealgebraic degrees of the nonlinear components in the cipher. The algebraic
degrees of the bijective four-bit S-boxes, SSi , are three, thus the algebraic
degree of S0 is at most six. For comparison, a randomly chosen, invertible
eight to eight bit S-box has algebraic degree seven with high probability. We
found no indication that the algebraic degree of six for S0 is a weakness for
CLEFIA. The algebraic degree of S1 is seven. The two S-boxes used are both24

8-bit bijections. It is known that seven is the maximum attainable algebraic
degree for bijective eight-bit S-boxes.
It is not clear how the degrees will grow with the number of rounds in
CLEFIA, but it appears that with 18 rounds of encryption it is extremely
unlikely that attacks based on higher order diﬀerentials will prove successful.
3.8.2

Boomerang attack

The boomerang attack is a special case of a second-order diﬀerential. The
boomerangs are eﬀective in particular for ciphers for which a subpart (e.g.,half) of the cipher has high-probability diﬀerentials. The penalty in theboomerang attack is the requirement for four diﬀerential paths throughout
the particular subparts of the cipher. The very conservative estimates of differential probabilities are already low enough to conclude that the boomerang
attack will not be superior to a classical diﬀerential attack.
The ampliﬁed boomerang attack and the rectangle attack are variants ofthe boomerang attack and we are convinced that these attacks are no threat
for CLEFIA with the speciﬁed number of rounds.

3.9Interpolation cryptanalysis

In [11] the interpolation attack was introduced based on the following wellknown formula. Let R be a ﬁeld. Given 2n elements x1 , . . . , xn , y1 , . . . , yn ∈R, where the xi s are distinct. Deﬁnef (x) =

n
∑
i=1

yi

∏

x − xj.
x
i − xj1≤j≤n,j̸=i(4)

f (x) is the only polynomial over R of degree at most n−1 such that f (xi ) = yi
for i = 1, . . . , n. Equation (4) is known as the Lagrange interpolation formula.
In the interpolation attack an attacker constructs polynomials using inputs and outputs of the reduced cipher. This is particularly easy if thecomponents in the cipher can be easily expressed as mathematical functions.
The idea in the attack is, that if the constructed polynomials have a small
degree, only few plaintexts and their corresponding ciphertexts are necessary to solve for the (key-dependent) coeﬃcients of the polynomial. In an
extended version of the attack meet-in-middle techniques are used to further
reduce the degrees of the used polynomials [11].
25The interpolation attacks are reminiscent of attacks based on higher order
diﬀerentials and are eﬀective mostly on ciphers for which all components canbe written as polynomials in the inputs with few coeﬃcients. Since this isclearly not the case for the S-boxes used in CLEFIA, there is no reason tobelieve that the interpolation attack is applicable to more than a few numberof rounds of CLEFIA.

3.10

Algebraic cryptanalysis

The XL [7] and XSL [8] cryptanalytic attacks and variations of these areoften also referred to as “algebraic attacks”. Here one writes polynomial
expressions in the inputs and outputs of each round of a cipher, then tries
to solve these to ﬁnd the secret key. The complexity of such an attack grows
with the number of nonlinear components in the cipher. These methods are
surrounded by controversy although there seems to be consensus that the XL
method has some merit [6, 9, 17].
Here we ﬁrst investigate algebraic expressions over the S-boxes in CLEFIA. The 8 × 8-bit S-box S0 is constructed from four 4 × 4-bit S-boxes
SS0 , SS1 , SS2 , SS3 .
Let x be an eight-bit input, then the eight-bit output is computed as follows,
where an eight-bit word, a, is divided into two four-bit words a0 and a1 , cf.
[28].
w := SS0 (x0 ) | SS1 (x1 ),v := L(w0 , w1 ),y := SS2 (v0 ) | SS3 (v1 ),where L is a linear transformation. First of all, it has been conﬁrmed that
there are no deterministic relations of degrees maximum two in the bits of the
input x and the bits of the output y of S0 . However, it is nonetheless possible
to establish a set of equations of degree at most two over S0 . It is well-known
that there are at least 21 deterministic relations of degrees maximum two in
the bits of the input and output of a four to four bit S-box. This follows
from the fact that from the constant one and from the eight bit variables
one can form 37 terms of degrees at (most) two. There are one term of degree8zero, eight terms of degree one and 2 = 28 terms of degree 2. Since there
26

are only 16 pairs of input and output over the S-box, one can establish 16
equations in 37 unknowns and the result follows. It was conﬁrmed that for
all four S-boxes SSi there are exactly 21 quadratic equations in the input
and output bits.
Therefore there are 21 quadratic equations over the bits in x0 and w0 and
21 quadratic equations over the bits in x1 and w1 . Similarly there are 21
quadratic equations over the bits in y0 and v0 and 21 quadratic equations
over the bits in y1 and v1 . In total, one can establish a set of 84 quadratic
equations in 24 bits, the eight bits of x, y, and v. Note that the bits of w andv are related by linear equations.
Also, it has been conﬁrmed that there are 39 deterministic relations ofdegrees two in the input bits and output bits of S1 .
Algebraic attacks on block ciphers are surrounded by controversy and noreal-life ciphers have yet been proved to be vulnerable to such an approach.
For CLEFIA with 18 rounds, a total of 144 S-boxes are used. The Advanced
Encryption Standard uses a total of 144 S-boxes in nine rounds of encryption.
One might expect that the complexity of an algebraic attack on 18-round
CLEFIA is similar to the complexity of an algebraic attack on 9-round AES[25].
Thus, it is safe to conclude that a breakthrough in algebraic cryptanalysisof CLEFIA also would mean a breakthrough in algebraic cryptanalysis of the
AES. And it seems that an algebraic attack on AES is very far from being arealistic threat.

3.11

The key scheduling algorithm

The key schedules of the most popular ciphers can be categorised as follows.
1. Linear key schedules. These are where the round keys or subkeys arederived as aﬃne transformations of the main key. Examples include
the key schedules of DES [21] and KASUMI [1].
2. Non-linear key schedules. These are where the round keys or subkeys
are generated as (simple) non-linear transformations of the main key.
A prominent example is the key schedules of AES [20].
3. Complex key schedules. These are where the round keys or subkeys
are generated as a complex, non-linear transformations of the main27

key. Examples include the key schedules of RC5 [26] and CLEFIA
among many others.
Here we describe brieﬂy the 128-bit key schedule of CLEFIA. The userselected key is denoted K. The whitening keys and the round keys are derived
from a number of 128-bit values, denoted here by Ai .
First a derived key L is obtained, which is 128-bit value computed as theencryption of K in a 12-round cipher with a chosen constant as the key.
Then
A0 = K,
A1 = L ⊕ C1 ,and the rest of the values are computed as follows:
A2i = Σ2i−1 (L) ⊕ K ⊕ C2i ,A2i+1 = Σ2i (L) ⊕ C2i+1

for i = 1, . . . , 4, where Cj are the constants deﬁned in the key schedule. Σ is a
bit permutation, which consists of two swaps (“The DoubleSwap Function”).
3.11.1

Weak keys

For some ciphers there is a, usually small, subclass of keys which can be
regarded weak as compared to other keys. E.g., in the Data Encryption
Standard, DES, four values of the key have been identiﬁed for which theencryption operation equals the decryption operation, and it is not recommended to use these values with DES.
For CLEFIA we did identify pairs of keys for which many of the corresponding subkeys are related. We illustrate our ﬁndings on the 128-bit key
version of CLEFIA, the key-schedules for the other key sizes have similar
properties. The user-selected key K of 128 bits is encrypted (using constants
as encryption keys) to generate a 2nd key L, also of 128 bits. The encryption
used is invertible, such that given L, one can ﬁnd a unique value of K. The
36 subkeys rki for i = 0, . . . , 35 each of 32 bits and the four whitening keys
wkj for j = 0, . . . , 3 each of 32 bits are generated from K and L, such that28

wkj depend only on K, rki for i = 8k, . . . , 8k + 3 depend only on L, and rki
for i = 8k + 4, . . . , 8k + 7 depend on both K and L, where k ≥ 0.
Consider the value of K for which L = 0, let us call this value K0 . In
this case, it follows that for i = 0, . . . , 4:
A2i = K0 ⊕ C2i ,A2i+1 = C2i+1 ,where Cj are the constants deﬁned in the key schedule. Another example,
is the value of K, say K1 , for which L = 1, meaning the string consisting of
128 1-bits.
In this case, it follows that for i = 0, . . . , 4:Ã2i = K1 ⊕ C2i ,Ã2i+1 = C2i+1 ,Consequently, if one considers the exclusive-or of all Ai keys for the two
keys K0 and K1 one gets a series of values Xi = Ai ⊕ Ãi :
X2i = K0 ⊕ K1 ⊕ 1,
X2i+1 = 1,
where 1 is the string of 128 1-bits. We found no reason to discourage the useof these keys for CLEFIA used for encryption.
Consider further two keys K and K ′ and the corresponding derived keys
L and L′ . Imagine that L and L′ are diﬀerent in s bits, in other words,
the Hamming distance between the two strings is s. L and L′ are bothtransformed using DoubleSwap a total of eight times. It follows that theHamming distances of L and L′ after each of these tranformations remains. Thus if s is small, this means that all subkeys which depend on only L
and L′ have a small Hamming distance. The Hamming distances in all othersubkeys on the other hand are expected to look random. We have found noway of exploiting these properties of related keys and they are not likely topose a problem for CLEFIA when used for encryption.
Finally we report on a related-key property involving more than two keys.
Consider the four pairwise, diﬀerent keys K0 , K1 , K2 , K3 , where K0 ⊕ K1 ⊕29

K2 ⊕ K3 = 0. Also, assume that the derived keys L0 , L1 , L2 , L3 have thesimilar property that L0 ⊕ L1 ⊕ L2 ⊕ L3 = 0. Consider the four whitening
keys wk0 for the four keys. It follows that the exclusive-or of these keys iszero. A similar property holds for any of the whitening keys and for any of the
32-bit round keys (rki ). As an example, the key words rk12 , rk13 , rk14 , rk15
are derived from σ 3 (L) ⊕ K plus some constants. But
σ 3 (L0 ) ⊕ K0 ⊕ σ 3 (L1 ) ⊕ K1 ⊕ σ 3 (L2 ) ⊕ K2 ⊕ σ 3 (L3 ) ⊕ K3 =
3
3
∑
∑
3
σ (Li ) ⊕Ki = 0.
i=0i=0Note that the constants in the key-schedule cancel out above. Also notethat similar properties hold for sets of any even number of keys. One canﬁnd such sets of 2j keys eﬃciently for larger values of j using the techniquesdeveloped in [30]. However it is clear that for encryption such sets of keys
are not likely to be used in practice and we have found no way of exploitingthese properties of related keys and they are not likely to pose a problem for
CLEFIA.
One possible drawback of the key scheduling algorithm is the use of many
diﬀerent constants, which must be stored or generated on the ﬂy.
3.11.2

Related key attacks

There are several variants of this attack depending on how powerful theattacker is assumed to be.
1. Attacker gets encryptions under one key.
2. Attacker gets encryptions under several keys.
(a) Known relation between keys.
(b) Chosen relation between keys.
The concept of related-key attacks is from [3]. Later, related key attacks
were reported on several other block ciphers [12] and latest a series of papers
regarding the AES [4, 5].
Attacks based on related keys are regarded by some as impractical, sinceoften it is required that an attacker can obtain the encryption of many chosen
plaintexts, sometimes encrypted using many diﬀerent, related keys. Usually30

in cryptanalytic attacks on block ciphers it is assumed that the key is secret
and that it is chosen uniformly at random. For the attacks of 2b above it isclear that this assumption can no longer be used. Nonetheless, many blockciphers are designed to (try to) avoid these attacks and the cryptographic
community seems to support related-key attack results.
We have examined the key scheduling algorithm of CLEFIA, but foundno evidence that this enables eﬃcient related-key attack of any type. The
above ﬁndings illustrate that there are collection of keys for which one caneasily predict the relations between many subkeys. However, keys used forencryption should be chosen uniformly at random, and even if one allows
for an attacker to choose an oﬀset, say α, and get encryption under the
keys k and k ⊕ α, the L-values are likely to be highly unpredictable andthus the relations between the subkeys for k and k ⊕ α are likely to lookrandom. Therefore, related-key attacks seem to be extremely hard to mounton CLEFIA.

3.12

Known key security

The known-key security concept was introduced in [15]. In this scenario it isassumed that the key is known and the task of the attacker is to ﬁnd some“statistical weakness” in the block cipher using the particular key.
Consider the integral of Section 3.7.1.
1r(C, A, C, C) → (A, C, C, C)
1r→ (A, C, C, A)
1r→ (A, C, A, A)
1r→ (A, A, B, A)
1r→ (B, B, ? , A)
1r

→ ( ? , ? , ? , B)
This speciﬁes that for a set of texts all diﬀerent in the second words but withequal values in all other words, the exclusive-or of the rightmost ciphertext
words after six rounds of encryption is zero.
One can also specify integrals through the decryption operation. It follows
by easy calculations that the following integral through the decryption rounds

31

can be established.
(C, C, A, C)

1r−1

→

(A, C, C, A)

1r−1

→

(A, A, A, C)

1r−1

→

(A, A, B, A)

1r−1

→

( ? , A, B, B)

1r−1( ? , ? , B, ? )→When the key is known one can combine the two integrals and specify an
11-round integral
5r( ? , ? , B, ? ) → (C, A, C, C)
6r→ ( ? , ? , ? , B)
Note that after the ﬁrst ﬁve rounds the halves are swapped, which is thereason why the above 5-round decryption integral is not identical to theﬁrst ﬁve rounds of the 11-round integeral. The existence of the 11-roundintegral means that if one knows the value of the key one can ﬁnd a setof 232 texts such that the second rightmost words of the plaintexts and therightmost words of the ciphertexts are balanced. The time to ﬁnd this setof texts is equivalent to doing 232 evaluations of the cipher with a ﬁxed key.
If one has (oracle) access to a “randomly chosen” 128-bit bijection, then it
is not too diﬃcult to ﬁnd a set of 232 inputs such that the rightmost wordsof both inputs and outputs are balanced. If one considers one call to theoracle access as computationally equivalent to one encryption of the blockcipher (for a ﬁxed key), then the complexity is close to 232 but very likely
strictly larger than 232 . So the 11-round integral is a distinguisher for theblock cipher used with a ﬁxed key. One can get stronger distinguishers for
fewer rounds of the cipher by considering fewer rounds of the above integral.
Also one can possibly extend the distinguishers to one additional round byconsidering integrals with 264 or 296 texts, but the relevance of such knownkey distinguishers can be discussed and one is nowhere near a distinguisher
on the full 18-round CLEFIA.

3.13

The overall structure

The high-level structure of CLEFIA is well-known as a generalised Feistel
type construction. Also, this structure was used in the design of the block32

cipher RC6 [27]. This structure appears to be sound and no important weaknesses are known for it.
3.13.1The diﬀusion matrices

The matrices M0 and M1 are similar in nature to the diﬀusion matrices of
the AES and have they same strong properties. No (serious) weakness isknown for these constructions.

3.14

The number of rounds

The strongest on reduced-round variants of CLEFIA seems to be the ones
based on impossible diﬀerentials. There are impossible diﬀerentials for CLEFIA reduced to up to nine rounds, but not for more than nine rounds. Let ddenote the maximum number of rounds for which eﬀective attacks exist fora block cipher. It is a well-known principle to choose the number of rounds
in block ciphers well over d, one straight-forward, known rule of thumb isto choose 2d rounds. Since CLEFIA seems to be a very secure cipher whenused with 18 rounds and at the same fast in implementation, we feel that
this choice is justiﬁed. Adding four more rounds for the 192-bit key version and another four rounds for the 256-bit key version are natural choices
and in correspondence with the choice made for the Advanced Encryption
Standard (AES), where two rounds are added, and one round of AES has asimilar complexity to two rounds of CLEFIA. Note that one round of CLEFIA modiﬁes only half the block, while one round of the AES modiﬁes thewhole block.

3.15

Implementation aspects

The round function in CLEFIA bears some resemblance with the round function of the AES. From the latter it is known that the use eight-bit S-boxes
together with the diﬀusion matrices allow for fast implementation in software.
A similar technique can been used in the implementation of CLEFIA. As aresult one gets a compact and fast implementation of CLEFIA in software.
One point to mention is that an implementation on a 64-bit architecture does
not seem to provide a signiﬁcant speed-up compared to an implementation
on a 32-bit architecture.

33