Advanced
Impossible Differential Cryptanalysis on Lai-Massey Scheme
Impossible Differential Cryptanalysis on Lai-Massey Scheme
ETRI Journal. 2014. Oct, 36(6): 1032-1040
Copyright © 2014, Electronics and Telecommunications Research Institute(ETRI)
  • Received : December 24, 2013
  • Accepted : July 23, 2014
  • Published : October 01, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Rui Guo
Chenhui Jin

Abstract
The Lai-Massey scheme, proposed by Vaudenay, is a modified structure in the International Data Encryption Algorithm cipher. A family of block ciphers, named FOX, were built on the Lai-Massey scheme. Impossible differential cryptanalysis is a powerful technique used to recover the secret key of block ciphers. This paper studies the impossible differential cryptanalysis of the Lai-Massey scheme with affine orthomorphism for the first time. Firstly, we prove that there always exist 4-round impossible differentials of a Lai-Massey cipher having a bijective F-function. Such 4-round impossible differentials can be used to help find 4-round impossible differentials of FOX64 and FOX128. Moreover, we give some sufficient conditions to characterize the existence of 5- , 6- , and 7-round impossible differentials of Lai-Massey ciphers having a substitution-permutation (SP) F-function, and we observe that if Lai-Massey ciphers having an SP F-function use the same diffusion layer and orthomorphism as a FOX64, then there are indeed 5- and 6-round impossible differentials. These results indicate that both the diffusion layer and orthomorphism should be chosen carefully so as to make the Lai-Massey cipher secure against impossible differential cryptanalysis.
Keywords
I. Introduction
- 1. Background
Nowadays, the most powerful known attacks on block ciphers are differential cryptanalysis [1] and linear cryptanalysis [2] . These attacks have been efficiently applied to many known ciphers. Therefore, many block cipher structures with a provable security against differential cryptanalysis and linear cryptanalysis have been studied [3] [8] . However, a provable security against differential cryptanalysis and linear cryptanalysis is not enough to prove the security of block ciphers, because other different cryptanalyses may be applied in the future. For instance, the 3-round Feistel structure, whose round functions are bijective, has a provable security against differential cryptanalysis and linear cryptanalysis [9] , but there exists a 5-round impossible differential characteristic, which means that impossible differential cryptanalysis [10] may be much more powerful than differential cryptanalysis and linear cryptanalysis. Thus, it is necessary to evaluate the ability of each block cipher to resist also impossible differential cryptanalysis.
Impossible differential cryptanalysis, proposed by Biham and Knudsen, is one of the most popular cryptanalytic tools for use against block ciphers. The main idea behind impossible differential cryptanalysis is to use an impossible differential that shows that a particular differential characteristic can not occur for the correct key, which means that if these differential characteristics are satisfied under the tested key, then it cannot be the correct one. Moreover, impossible differential cryptanalysis has shown its superiority over differential cryptanalysis in many block ciphers, such as International Data Encryption Algorithm (IDEA) [11] , Skipjack [12] , AES [13] , FOX family [14] , and so on.
Obtaining the longest impossible differential is the key step of impossible differential cryptanalysis, and several methods have made use of the miss-in-the-middle method to do just that. Another method used to obtain the longest impossible differential is the u-method [15] proposed by Kim and others. Although the u-method can be used, in general, to find impossible differentials of various block ciphers, information relating to block ciphers is often lost in the process and hence some longer impossible differentials cannot be found by this method. Luo and others extended the idea of the u-method and proposed a more general method; namely, the UID-method [16] . The UID-method removes some limitations of the u-method and harnesses more inconsistent conditions to evaluate impossible differentials. Wu and others [17] introduced a novel tool to search impossible differentials for word-oriented block ciphers with bijective S-boxes. This tool generalizes both the u-method and the UID-method. However, those methods are so general that some information is often lost during calculating the impossible differentials. Hence, once again, some longer impossible differentials cannot be found by using those methods.
In this paper, we mainly focus on impossible differential cryptanalysis of the Lai-Massey cipher (The block ciphers are defined by iterating the Lai-Massey scheme [18] ) with affine orthomorphism. The Lai-Massey scheme was originally derived from the IDEA [19] cipher. In 2004, instancing the Lai-Massey scheme’s F-function with an SPS structure and orthomorphism [20] as or ( x,y ) = ( y,x y ), Junod and Vaudenay designed the FOX [21] family of block ciphers, also named “IDEA NXT.” Thus far, existing analysis results indicate that the FOX family of ciphers is secure enough from such attacks as differential cryptanalysis [14] [22] , integral attacks [23] , fault attacks [24] , and so on [21] . Moreover, Yun and others introduced the notion of a quasi-Feistel network [25] , which is a generalization of the Feistel network and contains the Lai-Massey scheme as an instance. They proved that the Lai-Massey scheme and Feistel structure have the same pseudorandom properties [26] and decorrelation property [27] ; however, they didn’t precisely present the ability of the Lai-Massey cipher to resist linear and differential cryptanalysis; integral attacks; statistical attacks; slide and related-key attacks; and so on. This paper firstly evaluates the Lai-Massey cipher’s ability to resist impossible differential cryptanalysis. By carefully analyzing the properties of the linear transformations, we found that the existence of impossible differentials in a Lai-Massey cipher is not only related to the diffusion layer of the F-function but also strongly related to the orthomorphism. Compared with the Feistel cipher [28] , our results indicate that Lai-Massey cipher is much more powerful to resist impossible differential cryptanalysis.
- 2. Contribution and Outline
The contribution of this paper presents the original evaluation on the impossible differentials of Lai-Massey ciphers for the first time. Firstly, we prove that 4-round impossible differential always exist if the F-function is bijective. Secondly, we give some sufficient conditions to characterize the existence of 5-, 6-, and 7-round impossible differentials of Lai-Massey ciphers having a substitution-permutation (SP) F-function and observe that if the Lai-Massey ciphers having an SP F-function use the same diffusion layer and orthomorphism as a FOX64, then there are indeed 5- and 6-round impossible differentials.
This paper is organized as follows. In Section II, we will describe the Lai-Massey scheme along with some preliminaries. The existence of the impossible differentials of the Lai-Massey cipher having either an SP or an SPS F-function will be discussed in Section III. Section IV concludes this paper.
II. Preliminaries
- 1. Lai-Massey Scheme
Definition 1 [18] . Let ( G , +) be a group. If σ : G G and x σ ( x ) − x are both permutations, then σ is an orthomorphism on G .
Definition 2 [18] . Let ( G , +) be a group. Given r F-functions,   f 1 , ... , fr , and an orthomorphism on G , σ , we can define an r -round Lai-Massey cipher that is a permutation on G 2 and that is denoted as
LM ( f 1 ,    , f r )( x 0 , y 0 )           =LM [ f 2 ,    , f r ][σ( x 0 + f 1 ( x 0 y 0 )), y 0 + f 1 ( x 0 y 0 )].
Its round functions are defined as
( x i+1 , y i+1 )=(σ( x i + f i ( x i y i )),   y i + f i ( x i y i )),
where ( x i+1 , y i+1 ) ∈ G × G denotes the output of the i th round of the Lai-Massey cipher.
In this paper, let group G = {0, 1} n . We define the group operation + as the bit-wise exclusive OR ⊕. Then, the round function can be rewritten as
( x i+1 , y i+1 )=(σ[ x i f i ( x i y i )],   y i f i ( x i y i )).
In particular, to ensure the similarity of encryption and decryption of the Lai-Massey cipher, the σ in the last round is always omitted.
- 2. Description of FOX
FOX is a family of block ciphers designed by Junod and Vaudenay in 2004, which is the result of a joint project with the company MediaCrypt AG in Switzerland. FOX adopts a modified structure of the Lai-Massey Scheme, which can be proven to have sound pseudorandom properties in the Luby-Rackoff paradigm, as well as having decorrelation in hesitance properties. FOX has two versions, both have a variable number of rounds, the exact number of which being dependent upon key sizes. The first one, FOX64/ k / r , has a 64-bit block size with a variable key length — a multiple of 8 and up to 256 bits. The second, FOX128/ k / r , uses a 128-bit block size with variable key length and round number. The original FOX design suggests these two ciphers should be iterated for 16 rounds. The round function of FOX uses a substitution-permutation-substitution (SPS) structure with three layers of sub-key addition. The key schedule of FOX is very complex as it uses the round function as a compress function to generate sub-keys from the master key. Here, we give only a brief description of the F-function, f , of FOX64, for further details we refer you to [21] .
The round function, f , comprises three main parts: a substitution part, denoted sigma 4; a diffusion part, denoted mu 4; and a round key addition part. Let f : {0, 1} 32 × {0, 1} 64 →{0, 1} 32 , for a 32-bit input x ∈{0, 1} 32 and a 64-bit round key k = k 0 || k 1 , we have
f(x,  k)=sigma4(mu4(sigma4(x k 0 )) k 1 ) k 0 .
The substitution transformation sigma 4: {0, 1} 32 →{0, 1} 32 comprises four parallel applications of a nonlinear bijective S-box for different input bytes. The linear permutation transformation mu 4: [ GF (256)] 4 → [ GF (256)] 4 considers an input ( x 0 , x 1 , x 2 , x 3 ) as a column vector ( x 0 , x 1 , x 2 , x 3 ) T over [ GF (256)] 4 and multiplies it with a maximum distance separable (MDS) matrix to output a column vector of the same size. The branch number of the MDS matrix is five. The MDS matrix is defined as follows:
( 1 1 Z α 1 Z α 1 Z α 1 1 α 1 Z 1 ),
where Z = α −1 ⊕1 and α is a root of the irreducible polynomial m ( x ) = x 8 x 7 x 6 x 5 x 4 x 3 ⊕1 over GF (2).
Moreover, the σ transformation used in FOX64 is the linear orthomorphism or ( a, b ) = ( b, a b ), which satisfies the following properties.
Property 1 [21] . The orthomorphsim or ( x, y ) = ( y, x y ) and its inverse transformation io ( x, y ) = ( x y , x ) have the following properties:
  • ▪or2(x, y) =io(x, y),io2(x, y) =or(x, y).
  • ▪io(x, y)⊕or(x, y)⊕(x, y) = (0, 0).
  • ▪or(x, y) = (x, y) if and only if (x, y) = (0, 0).
  • ▪or3(x, y) = (x, y).
- 3. Notation and Definitions
Throughout this paper, we use the following notations:
  • ▪GF(q) denotes a Galois field withqelements.
  • ▪ #Tdenotes a cardinal number of the setT.
  • ▪f∘gorfgdenotes a composite function offandg.
  • ▪Ai. jdenotes the element in theith row andjth column of matrixA.
  • ▪ ∆f(∆X) denotes the output difference of the input difference, ∆X, for the F-functionf.
  • ▪ ∆S(∆X) denotes the output difference of the input difference ∆Xfor the nonlinear transform layerS.
In this section, we give the definition and properties of the χ -function and then give the definition of the Hamming weight.
Definition 3 (χ-function). For m ≥1, let δ : GF (2 m )→ GF (2), χ : ( GF (2 m )) n →( GF (2)) n , and χ i : ( GF (2 m )) n GF (2), for 1 ≤ i n , then define
δ(x)={ 0    if x=0, 1     if x0,
χ( x 1 ,  ...  ,   x n )=δ( x 1 ),  ...  ,  δ( x n ) ,
and
χ i ( x 1 ,  ...  ,   x n )=δ( x i ) .
Therefore, for X ∈ ( GF (2 m )) n , χ i ( X ) = 1 means that there is some non-zero value at the i th position. Let ei ∈ ( GF (2 m )) n be a vector such that χ i ( ei ) = Ei , where Ei ∈ ( GF (2)) n is a vector whose i th component is one, while other [ ej = 0 ( j i )] components are zero. The χ -function adheres to the following properties outlined in Property 2:
Property 2 [28] .
  • A. For any difference ∆X∈ (GF(2m))n, we haveχ(∆S(∆X)) =χ(∆X)
  • B. LetP= (p1, ... ,pn) , wherepiis theith column vector of diffusion layerP, then if ∆X=ei, we have
  • χ(P∘ΔS(ei))=χ(P(ei))=χ(pi) .
  • C. LetX= (x1, ... ,xn),Y= (y1, ... ,yn), 1 ≤i≤n. ifxi= 0, thenχi(X⊕Y) =χi(Y) =δ(yi).
Definition 4 [28] . Let X = ( x 1 , ... , xn ) ∈ ( GF (2 m )) n , then define the number of nonzero components in X by w ( X ) = #{ i | xi ≠ 0, 1 ≤ i n ).
In this paper, we only consider the Lai-Massey scheme with affine orthomorphism σ : {0, 1} n → {0, 1} n , let τ = σ I ( I denotes the identical transformation), then στ = τσ , and we can list the properties of σ and τ as follows:
Property 3.
  • (1) (σ2⊕I)τ−1=τ;        (2) (τ2⊕I)σ−1=σ;
  • (3) (σ−1⊕I)τ−1σ=I;     (4)σ2⊕σ⊕I⊕τ2=σ.
Proof. We only prove (3); the proof of the others is a trivial exercise. Due to the fact that σ −1 is also an affine orthomorphism [20] and τ = σ I , we have ( σ −1 I ) τ −1 σ = σ −1 ( σ I ) τ −1 σ = I .                                    ■
III. Impossible Differentials Analysis of the Iterative Lai-Massey Scheme
By comprehensively analyzing the properties of the diffusion layer and the σ transformation on the Lai-Massey ciphers, some sufficient conditions will be presented that characterize the existence of 4-round impossible differentials of a Lai-Massey cipher having a bijective F-function and that characterize the existence of 5-, 6-, and 7-round impossible differentials of a Lai-Massey cipher having an SP F-function. Let ∆ i ( i = 1, 2, ... , r ) denote the input difference of the i th round. Using the miss-in-the-middle technique, we try to find the impossible differential of a Lai-Massey cipher and obtain several results as follows.
- 1. Analysis on 4-Round Lai-Massey Cipher Having a Bijective F-function
Proposition 1. Let the F-function of a Lai-Massey cipher be bijective, then ( τ −1 ( α ), τ −1 ( α )) ↛ ( σ 2 ( α ), σ ( α )) is a 4-round impossible differential of the cipher, where α ≠ 0.
Proof. As described in Fig. 1 , from the encryption direction, if ∆ 1 = ( τ −1 ( α ), τ −1 ( α )), then ∆ 2 = ( στ −1 ( α ), τ −1 ( α )) and ∆ 3 = ( σ 2 τ −1 ( α )⊕ σ ( β ), τ −1 ( α )⊕ β ), where στ −1 ( α )⊕ τ −1 ( α ) = α and β = ∆ f 2 ( α ) are the input difference and output difference of f 2 , respectively. Moreover, due to the fact that the F-function is bijective and α is nonzero, we have β ≠ 0. By Property 3, we know that
σ 2 τ 1 (α)σ(β) τ 1 (α)β             =( σ 2 I) τ 1 (α)τ(β)             =τ(α)τ(β),
which is the input difference of the third F-function, f 3 .
PPT Slide
Lager Image
Impossible differential of 4-round Lai-Massey cipher having a bijective round function.
From the decryption direction, if the output difference of the fourth round is ( σ 2 ( α ), σ ( α )), then ∆ 4 = ( σ ( α ), σ ( α )), and the input difference of f 3 is α σ ( α ) = τ ( α ). Therefore, by β ≠ 0, τ ( α )⊕ τ ( β ) = τ ( α ) is a contradiction. Hence, ( τ −1 ( α ), τ −1 ( α )) ↛ ( σ 2 ( α ), σ ( α )) is a 4-round impossible differential.                     ■
From Proposition 1, we can obtain a new kind of impossible differential of a 4-round FOX cipher as the following corollary.
Corollary 1. Let or ( x, y ) = ( y, x y ), then we have the following:
  • ▪ Ifα∈ {0, 1}32\{0}, then (α,α) ↛ (or(α),α) is a 4-round impossible differential of FOX64.
  • ▪ Ifα∈ {0, 1}32\{0} andβ∈ {0, 1}32, then (α, α, β, β) ↛ (or(α),α,or(β),β) is a 4-round impossible differential of FOX128.
In [14] , Wu proved that (0 a 0 a , 0 a 0 a ) ↛ ( bcbd , bcbd ) is a 4-round impossible differential of FOX64, where each a , b , c , and d denote one byte, and a ≠ 0. In addition, they presented a chosen plaintexts impossible differential cryptanalysis of the FOX64. In Corollary 1, the only requirement is that a ≠ 0, which implies that perhaps we can present a distinct known plaintexts attack on FOX, which is a more realistic model. Moreover, for a Feistel scheme, if the F-function is bijective, then it will have a 5-round impossible differential. In Proposition 1, we know that the Lai-Massey scheme only has a 4-round impossible differential if the F-function is bijective.
- 2. Analysis on 5-Round Lai-Massey Cipher Having an SP Round Function
From now on, let σM and τM denote the corresponding matrix of the linear transformation σ and τ , respectively.
Proposition 2. Let ϕ = P −1 σ −1 P , φ = P −1 ( τ σ −1 ), for 1 ≤ I n . If there exists 1 ≤ j i n such that χj ( τ ( ei )) = 0 and either χj ( ϕ ( ei )) = 0, χj ( φ ( ei )) = 1 or χj ( ϕ ( ei )) = 1, χj ( φ ( ei )) = 0, then ( ei , ei ) ↛ ( τ −1 σ 2 ( ei ), τ −1 σ ( ei )) is a 5-round impossible differential of the Lai-Massey cipher having an SP structure.
Proof . As described in Fig. 2 , if the input difference is ( ei , ei ), then the input difference of f 2 will be σ ( ei )⊕ ei = τ ( ei ). Let β = P S ( τ ( ei )) denote the output difference of f 2 , then ∆ 3 = ( σ 2 ( ei )⊕ σ ( β ), ei β ), and the input difference of f 3 is
σ 2 ( e i )σ(β) e i β=τ(τ( e i )β) .
Then, ∆ 5 = ( τ −1 σ ( ei ), τ −1 σ ( ei )), and the input difference of f 4 is τ −1 ( ei )⊕ τ −1 σ ( ei ) = τ −1 ( σ I )( ei ) = ei . Let γ = P S ( ei ) denote the output difference of f 4 , then ∆ 4 = ( τ −1 ( ei )⊕ γ , τ −1 σ ( ei )⊕ γ ), from which we know that the input difference of f 3 is
σ 1 τ 1 ( e i ) σ 1 (γ) τ 1 σ( e i )γ             =( σ 1 I)( e i )( σ 1 I)(γ).
Thus, the following equation holds:
τ(τ( e i )β)=( σ 1 I)( e i )( σ 1 I)(γ);namely, τPΔS(τ( e i ))=( σ 1 I)PΔS( e i )( τ 2 σ 1 I)( e i ),
which implies that ∆ S ( τ ( ei )) = ϕ S ( ei )⊕ φ ( ei ),
where φ = P −1 τ −1 ( τ 2 σ −1 I ) = P −1 ( τ σ −1 ) and ϕ = P −1 τ −1 ( σ −1 I ) P = P −1 σ −1 P . Moreover, we have χ S ( τ ( ei ))) = χ ( ϕ Δ S ( ei )⊕ φ ( ei )).
PPT Slide
Lager Image
Impossible differential of 5-round Lai-Massey cipher having an SP round function.
From Property 2, we know χ S ( τ ( ei ))) = χ ( τ ( ei )). If there exists 1 ≤ j i n such that either χj ( ϕ ( ei )) = 0, χj ( φ ( ei )) = 1 or χj ( ϕ ( ei )) = 1, χj ( φ ( ei )) = 0 then we have χj ( ϕ Δ S ( ei )⊕ φ ( ei )) = 1. Meanwhile, if χj≠i ( τ ( ei )) = 0, then this is a contradiction. Thus, ( ei , ei ) ↛ ( τ −1 σ 2 ( ei ), τ −1 σ ( ei )) is a 5-round impossible differential.                     ■
The following example implies that if the Lai-Massey ciphers having an SP structure use the same σ function and diffusion layer P as FOX64, then they will have a 5-round impossible differential.
Example 1. By the definition and property of the orthomorphism or in FOX64, we have
o r M =( 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 ),      i o M =( 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 ), P=( 1 1 1 α 1 Z α 1 Z α 1 1 α 1 Z 1 ),       P 1 =( a c d e a d e c a e c d b a a a ),
where Z = α −1 ⊕1 and a , b , c , and d are four distinct nonzero elements in GF (2 8 ).
From Proposition 2, here ϕ = P −1 orM ( ioM I ) P = P −1 ioM P , φ = P −1 orM ( orM ioM I ) = 0, and
P 1 i o M P   =( a c d e a d e c a e c d b a a a )( 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 )( 1 1 1 α 1 Z α 1 Z α 1 1 α 1 Z 1 )                            =( a c d e a d e c a e c d b a a a )( 1Z 1α 0 1α 1α 1Z Zα 0 1 1 1 α 1 Z α 1 )                            =( * * * * * * * * * * * * * * a(1Z) * ).
So, χ 4 ( τ ( e 3 )) = 0, χ 4 ( ϕ ( e 3 )) = a (1 ⊕ Z ) ≠ 0, and χ 4 ( φ ( e 3 )) = 0. Thus, ( e 3 , e 3 ) ↛ ( e 3 , io ( e 3 )) is a 5-round impossible differential.
- 3. Analysis on 6-Round Lai-Massey Scheme Having an SP Round Function
Proposition 3. For 1 ≤ i n , let
Ω i ={k|[ ( τ M ) k,i =0,   ( τ M P) k,i 0]                             [ ( τ M ) k,i 0,   ( τ M P) k,i =0]},
Λ i = { k | ϕk,i = 0}, Γ i = { k | φk,i ≠ 0}, n 1 = #(Ω i ∩ Λ i ), and n 2 = #Γ i , where
ϕ= P −1 ( τ M −1 σ M −1 ⊕ σ M )
and
φ= P −1 ( σ M −1 ⊕ τ M )P
. If n 1 > n 2 , then ( τ −1 ( ei ), τ −1 ( ei )) ↛ ( σ 2 ( ei ), σ ( ei )) is a 6-round impossible differential of a Lai-Massey cipher having an SP structure.
Proof. As described in Fig. 3 and similar to Proposition 2, when ∆ 1 = ( τ −1 ( ei ), τ −1 ( ei )), we conclude that the input difference of f 4 is
σ 3 τ 1 ( e i ) σ 2 PΔS( e i )σPΔS[τ( e i )τPΔS( e i )] PΔS[τ( e i )τPΔS( e i )] τ 1 ( e i )PΔS( e i )           =σ( e i ) τ 2 [PΔS( e i ) e i ]               τPΔS[τ( e i )τPΔS( e i )].
From the decryption direction, if the output difference of the sixth round is ( σ 2 ( ei ), σ ( ei )), then ∆ 6 = ( τ −1 ( ei )⊕ P S ( ei ), τ −1 σ ( ei )⊕ P S ( ei )). Therefore, the input difference of f 4 is
σ 2 τ 1 σ( e i ) σ 1 PΔS( e i ) τ 1 σ( e i )PΔS( e i )           =( σ 2 I) τ 1 σ( e i )( σ 1 I)PΔS( e i )           =( σ 1 I)( e i )( σ 1 I)PΔS( e i ).
Thus, the following equation holds:
σ( e i ) τ 2 [PΔS( e i ) e i ]τPΔS[τ( e i )τPΔS( e i )]           =( σ 1 I)( e i )( σ 1 I)PΔS( e i ).
Accordingly,
τPΔS[τ( e i )τPΔS( e i )]              =( σ 1 Iσ τ 2 )( e i )( σ 1 I τ 2 )PΔS( e i ).
Thus, we obtain
ΔS[τ( e i )τPΔS( e i )] P 1 ( τ 1 σ 1 σ)( e i )           = P 1 ( σ 1 τ)PΔS( e i ).
PPT Slide
Lager Image
Impossible differential of 6-round Lai-Massey cipher having an SP round function.
For 1 ≤ i n and a linear transformation P , let
Ω i ={k|[ ( τ M ) k,i =0,   ( τ M P) k,i 0]                            [ ( τ M ) k,i 0,   ( τ M P) k,i =0]},
Λ i ={k| ϕ k,i =0},  Γ i ={k| φ k,i 0},  n 1 =#( Ω i Λ i ),
n 2 = i ,    ϕ= P 1 ( τ M 1 σ M 1 σ M ),
and
φ= P 1 ( σ M 1 τ M )P .
Assume that there exist k 1 , ..., k n1 ∈ Ω i ∩ Λ i . Since k 1 , ..., k n1 ∈ Λ i , for any kj (1 ≤ j n 1 ), we have χkj ( P −1 ( τ −1 σ −1 σ )( ei )) = χkj ( ϕ ( ei )) = 0, by Property 2-A, then
χ k j (ΔS[τ( e i )τPΔS( e i )] P 1 ( τ 1 σ 1 σ)( e i ))             = χ k j (ΔS(τ( e i )τPΔS( e i )))             = χ k j (τ( e i )τPΔS( e i )).
Moreover, due to k 1 , ..., k n1 ∈ Ω i , for any kj (1 ≤ j n 1 ), there are
χ k j (τ( e i )τPΔS( e i )) ={ χ k j (( τ M ) k j ,i ( e i ))=1                        if  ( τ M ) k j ,i 0  and   (τP) k j ,i =0, χ k j ( ( τ M P) k j ,i ΔS( e i ))=1      if  ( τ M P) k j ,i 0  and   τ k j ,i =0.
For 1 ≤ j n 1 , we have
χ k j (τ( e i )⊕τPΔS( e i ))=1,
which means that
w(χ(τ( e i )⊕τPΔS( e i )))≥ n 1 ,
so
w(χ(ΔS[τ( e i )τPΔS( e i )] P 1 ( τ 1 σ 1 σ)( e i ))) n 1 .
On the other hand, assume that there exist some k 1 , ..., k n2 ∈ Γ i , by Property 2-B, then
w(χ( P 1 ( σ 1 τ)PΔS( e i )))          =w(χ( P 1 ( σ 1 τ)P( e i )))          =w( P 1 ( σ 1 τ)P( e i ))          = n 2 .
Hence, if n 1 > n 2 , then ( τ −1 ( ei ), τ −1 ( ei )) ↛ ( σ 2 ( ei ), σ ( ei )) is a 6-round impossible differential.                                                                    ■
The following example implies that if the Lai-Massey ciphers having an SP structure use the same σ function and diffusion layer as FOX64, then they will have 6-round impossible differentials.
Example 2. Similar to Example 1, by the definition and property of the orthomorphism or in FOX64, we have
ϕ =  P −1 (i o M −1 o r M −1  ⊕ i o M ​) =  P −1 o r M
and
φ =  P −1 (o r M −1  ⊕ i o M ​)P = 0;
hence, n 2 = 0. Moreover, we have
i o M P=( 1Z 1α 0 1α 1α 1Z Zα 0 1 1 1 α 1 Z α 1 _ )
and              P 1 o r M =( d e ad ce e c ae cd c d ac de a a ab 0 _ ).
We have ( ioM ) 4,4 = 0, ( ioMP ) 4,4 = 1, and ϕ 4.4 = ( P −1 orM ) 4,4 = 0, which implies that n 1 ≥ 1. Thus,
(or( e 4 ),or( e 4 )) ↛ (io( e 4 ),  or( e 4 ))
is a 6-round impossible differential.
- 4. Analysis on 7-Round Lai-Massey Scheme Having an SP Round Function
Proposition 4. For 1 ≤ i, j, k n , let
Ω i ={k| ( σ M −1 τ M ) k,i = 0;   ( σ M −1 τ M P) k,i =0}
,
A =  P −1 τ M −1 σ M ( σ M −2 ⊕ σ M −1 ⊕ σ M ⊕ σ M 2 ),
and
B= P −1 τ M −1 σ M ( σ M −2 ⊕I⊕ σ M 2 )P.
If
Ω i ≠ Ø
and there exist any k ∈ Ω i such that { ak,i , bk,i } = {0, 0} and
χ k ( P −1 σPΔS[τ( e i ) ⊕ τPΔS( e i )]) = 1,
then ( τ −1 ( ei ), τ −1 ( ei )) ↛ ( σ 2 ( ei ), σ ( ei )) is a 7-round impossible differential of the Lai-Massey cipher having an SP structure, where A = ( ai,j ) n×n , B = ( bi,j ) n×n , and ai and bi denote the i th column vectors of A and B , respectively.
Proof. As described in Fig. 4 , from the encryption direction, if Δ 1 = ( τ −1 ( ei ), τ −1 ( ei )), then the input difference of f 3 is
σ 2 τ 1 ( e i )σ(PΔS( e i )) τ 1 ( e i )PΔS( e i )             =τ( e i PΔS( e i )).
Let λ = P Δ S [ τ ( ei )⊕ τ P Δ S ( ei )] denote the output difference of f 3 . Accordingly, the input difference of f 4 is
σ 3 τ 1 ( e i ) σ 2 PΔS( e i )σλλ τ 1 ( e i )PΔS( e i )             =σ( e i ) τ 2 [PΔS( e i ) e i ]τλ.
PPT Slide
Lager Image
Impossible differential of 7-round Lai-Massey cipher having an SP round function.
From the decryption direction, if the output difference of the seventh round is ( σ 2 ( ei ), σ ( ei )), then Δ 6 = ( τ −1 ( ei ) ⊕ P Δ S ( ei ), τ −1 σ ( ei ) ⊕ P Δ S ( ei )). We denote the output difference of f 5 as β = P Δ S [ σ −1 τ ( ei P Δ S ( ei ))]. From Property 3, the input difference of f 4 is
σ 1 [ σ 1 τ 1 ( e i ) σ 1 PΔS( e i )β]β τ 1 σ( e i )PΔS( e i )           =( σ 2 τ 1 τ 1 σ)( e i )( σ 2 I)PΔS( e i )( σ 1 I)β           =[ σ 2 σ 1 I]( e i )( σ 2 I)PΔS( e i )( σ 1 I)β.
Thus, the following equation holds:
σ( e i ) τ 2 [PΔS( e i ) e i ]τλ           =( σ 2 σ 1 I)( e i )( σ 2 I)PΔS( e i )( σ 1 I)β,
which means that
τλ( σ 1 I)β           =( σ 2 σ 1 Iσ τ 2 )( e i )( σ 2 I σ 2 )PΔS( e i )           =( σ 2 σ 1 σ σ 2 )( e i )( σ 2 I σ 2 )PΔS( e i )
and
τPΔS[τ( e i )τPΔS( e i )] σ 1 τPΔS[ σ 1 τ( e i PΔS( e i ))]           =( σ 2 σ 1 σ σ 2 )( e i )( σ 2 I σ 2 )PΔS( e i ).
For 1 ≤ i, j, k n and linear transformation P , let
Ω i ={k| ( σ M 1 τ M ) k,i =0;   ( σ M 1 τ M P) k,i =0},       A= P 1 τ M 1 σ M ( σ M 2 σ M 1 σ M σ M 2 ),
and
B= P −1 τ M −1 σ M ( σ M −2 ⊕I⊕ σ M 2 )P.
If
Ω i ≠ Ø
and there exist any k ∈ Ω i such that { ak,i , bk,i } = {0, 0} then we have
χ k (ΔS[ σ 1 τ( e i PΔS( e i ))])           = χ k (A( e i )BΔS( e i ) P 1 σPΔS[τ( e i )τPΔS( e i )])           = χ k ( P 1 σPΔS[τ( e i )τPΔS( e i )]).
Here,
χ k (ΔS[ σ 1 τ( e i PΔS( e i ))])           = χ k ( σ 1 τ( e i PΔS( e i )))           =0,
which contradicts
χ k ( P −1 σPΔS[τ( e i ) ⊕ τPΔS( e i )]) = 1.
Therefore, the above proposition holds.                      ■
Toy Example . Let the σ function be an or transformation used in FOX64 and choose a diffusion layer P as follows:
P=( 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 ),   P 1 =( 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 ).
Here,
o r M −2 ⊕o r M −1 ⊕o r M ⊕o r M 2 =(o r M −2 ⊕I⊕o r M 2 )=0;
thus, A = B = 0. Moreover, we have
i o M P=( 0 1 1 1 1 1 1 0 0 1 0 1 1 _ 1 0 1 ),  o r M P=( 0 _ 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 ),
and
P 1 o r M P=( 0 _ 0 _ 0 _ 1 _ 1 0 1 1 0 1 1 1 1 0 0 1 ).
We have ( orM ) 1,1 = 0, ( orMP ) 1,1 = 0, and { a 1,1 , b 1,1 } = {0, 0}. Moreover, ( ioM ) 4,1 = 0, ( ioMP ) 4,1 = 1, ( P −1 orP ) 1,4 = 1, ( P −1 orP ) 1,1 = 0, ( P −1 orP ) 1,2 = 0, and ( P −1 orP ) 1,3 = 0, from which
χ 1 ( P −1 orPΔS[io( e 1 )⊕ioPΔS( e 1 )])=1.
Thus,
(or( e 1 ),  or( e 1 )) ↛ (io( e 1 ),  or( e 1 ))
is a 7-round impossible differential of this special Lai-Massey cipher having an SP structure.
IV. Conclusion
In this paper, we presented an impossible differential cryptanalysis on Lai-Massey ciphers. By comprehensively analyzing the properties of the diffusion layer and the σ function on the Lai-Massey ciphers, we gave some sufficient conditions that characterized the existence of 4-round impossible differentials of Lai-Massey cipher having a bijective F-function and 5-, 6-, 7-round impossible differentials of Lai-Massey ciphers having an SP F-function. These results indicate that both the diffusion layer and the σ function should be chosen carefully so as to make the Lai-Massey cipher secure against impossible differential cryptanalysis, and the propositions presented in this paper should be considered when designing a block cipher. Moreover, the problem of how to suitably design the diffusion layer and σ function of a Lai-Massey scheme so as to resist cryptanalyses is still an open one.
This work was supported by the National Natural Science Foundation of China (No. 61272488).
BIO
Corresponding Author  guorui201@sohu.com
Rui Guo received his PhD degree in cryptography from the Information Science and Technology Institute, Zhengzhou, China, in 2014. His research interests include the design and analysis of block ciphers. His works have been published in several journals and cryptology conferences.
jinchenhui@126.com
Chenhui Jin is a professor at the Information Science and Technology Institute, Zhengzhou, China. His research interests include cryptology and information security.
References
Biham E. , Shamir A. 1991 Advances in Cryptology - CRYPTO’90, LNCS Springer-Verlag Berlin, Germany “Differential Cryptanalysis of DES-like Cryptosystems,” 2 - 21
Matsui M. 1994 Advances in Cryptology - EUROCRYPT’93, LNCS Springer-Verlag Berlin, Germany “Linear Cryptanalysis Method for DES Cipher,” 386 - 397
Nyberg K. , Knudsen L.R. 1993 Advances in Cryptology - CRYPTO’92, LNCS Springer-Verlag Berlin, Germany “Provable Security against Differential Cryptanalysis,” 566 - 574    DOI : 10.1007/3-540-48071-4_41
Hong S. 2001 FSE’00, LNCS Springer-Verlag Berlin, Germany Provable Security against Differential and Linear Cryptanalysis for the SPN Structure 273 - 283
Hong S. 2002 Provable Security for 13 Round Skipjack-like Structure Inf. Proc. Lett. 82 (5) 243 - 246    DOI : 10.1016/S0020-0190(01)00276-9
Matsui M. FSE’96, LNCS 1996 Berlin, Germany New Structure of Block Ciphers with Provable Security against Differential and Linear Cryptanalysis 205 - 218
Nyberg K. 1996 Advances in Cryptology - ASIACRYPT’96, LNCS Springer-Verlag Berlin, Germany “Generalized Feistel Networks,” 91 - 104
Sung J. 2000 Advances in Cryptology - ASIACRYPT’00, LNCS Springer-Verlag Berlin, Germany: “Provable Security for the Skipjack-like Structure against Differential Cryptanalysis and Linear Cryptanalysis,” 274 - 288
Aoki K. , Ohta K. 1997 “Strict Evaluation of the Maximum Average of Differential Probability and the Maximum Average of Linear Probability,” IEICE Trans. Fundam. Electron., Commun. Comput. Sci. (1) 2 - 8
L.R. Knudsen 1998 “DEAL-A 128-bit Block Cipher,” Department Infometrics, University of Bergen Norway
Biham E. , Biryukov A. , Shamir A. 1999 FSE’99. LNCS Springer-Verlag Berlin, Germany Miss-in-the-Middle Attacks on IDEA, Khufu, and Khafre, Knudsen 124 - 138
Biham E. , Biryukov A. , Shamir A. 1999 EUROCRYPT’99. LNCS Springer-Verlag Berlin, Germany Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials 12 - 23
Daemen J. , Rijmen V. 2002 The Design of Rijndael: AES, Advanced Encryption Standard Springer-Verlag New York, USA    DOI : 10.1007/978-3-662-04722-4
Wu Z. 2009 Proc. Int. Conf., LNCS Beijing, China “Impossible Differential Cryptanalysis of FOX,” 236 - 249
Kim J. 2003 INDOCRYPT 2003, LNCS Springer-Verlag Berlin, Germany Impossible Differential Cryptanalysis for Block Cipher Structures 82 - 96
Luo Y. 2014 “A Unified Method for Finding Impossible Differentials of Block Cipher Structures,” Inf. Sci. 263 211 - 220    DOI : 10.1016/j.ins.2013.08.051
Wu S. , Wang M. INDOCRYPT 2012, LNCS Springer-Verlag Berlin, Germany “Automatic Search of Truncated Impossible Differentials for Word-Oriented Block Ciphers,” 283 - 302
Vaudenay S. 1999 Advances in Cryptology-ASIACRYPT’99, LNCS Springer-Verlag Berlin, Germany “On the Lai-Massey Scheme,” 8 - 19
Lai X. , Massey J.L. 1991 Advances in Cryptology EUROCRYPT’90, LNCS Springer-Verlag Berlin, Germany “A Proposal for a New Block Encryption Standard,” 389 - 404
1995 “Block Substitutions Using Orthomorphic Mappings,” Adv. Appl. Math. 16 (1) 59 - 71    DOI : 10.1006/aama.1995.1003
Junod P. , Vaudenay S. 2004 Selected Areas in Cryptography-SAC 2004, LNCS Springer-Verlag Berlin, Germany “FOX: A New Family of Block Ciphers,” 131 - 146
Chen J. 2012 “Differential Collision Attack on Reduced FOX Block Cipher,” China Commun. 9 (7) 71 - 76
Wu W. , Zhang W. , Feng D. 2006 “Information Security and Cryptology,” LNCS Springer-Verlag Berlin, Germany Integral Cryptanalysis of Reduced FOX Block Cipher 229 - 241
Li R. 2013 “Fault Analysis Study of the Block Cipher FOX64,” Multimedia Tools and Applications 63 (3) 691 - 708    DOI : 10.1007/s11042-011-0895-x
Yun A. , Park J.H. , Lee J. 2011 “On Lai-Massey and Quasi-Feistel Ciphers,” Design Codes Cryptography 58 45 - 72    DOI : 10.1007/s10623-010-9386-8
Luby M. , Rackoff C. 1988 “How to Construct Pseudorandom Permutations from Pseudorandom Functions,” SIAM J. Comput. 17 (2) 373 - 386    DOI : 10.1137/0217022
Vaudenay S. 1998 “Provable Security for Block Ciphers by Decorrelation,” Proc. Annual Symp. Theoretical Aspects. Comput. Sci. Paris, France 249 - 275    DOI : 10.1007/BFb0028566
Wei Y. 2010 Appl. Cryptography Netw. Security Springer-Verlag Berlin, Germany “Impossible Differential Cryptanalysis on Feistel Ciphers with SP and SPS Round Functions,” 105 - 122    DOI : 10.1007/978-3-642-13708-2_7