close

Вход

Log in using OpenID

embedDownload
Meet-in-the-Middle Attacks on
Generic Feistel Constructions
Jian Guo1, Jérémy Jean,1 Ivica Nikolić1 and Yu Sasaki2
1: Nanyang Technological University Singapore
2: NTT Secure Platform Laboratories, Japan
9/December/2014 @ Asiacrypt 2014
Copyright©2014 NTT corp. All Rights Reserved.
Contents
• Block-ciphers with Feistel
• Meet-in-the-Middle Attacks (Collision Attacks)
• Key Recovery Attacks against Feistel-2
• Key Recovery Attacks against Feistel-3
• Concluding Remarks
Copyright©2014 NTT corp. All Rights Reserved.
1
Research Background
Copyright©2014 NTT corp. All Rights Reserved.
Feistel Network
• Build -bit permutation from /2-bit function

/2
∗
/2

• Advantages
•  and  can share the same network
• function → permutation
• small component → large permutation
• Useful design choice even now: Simon and LAC
Copyright©2014 NTT corp. All Rights Reserved.
3
Generic Constructions (1/2)
• Luby-Rackoff

2

2
• regarded as  = ⋅ 2 bits
/2
• Feistel-1, analyzed by Knudsen
• regarded as  = bits
• cryptanalysis makes sense
• still hard to implement
∗
/2

• provable security
• hard to implement

2

/2

/2
/2

Copyright©2014 NTT corp. All Rights Reserved.
4
Generic Constructions (2/2)
• Feistel-2
• still captures many designs
• -function can be function or
permutation. They may differ
in different rounds.
• Feistel-3
• -function consists of -bit
S-boxes and a linear map  .
/2

/2
 /
/2


1
2
/2

/2
(Classification of Feistel-x is from Isobe-Shibutani Asiacrypt2013)
Copyright©2014 NTT corp. All Rights Reserved.
5
Attack Results on Feistel-2
-function
#rounds for || =
3/2 2

any
any
bij., ident.
5
5
6
6
7
−
any


7
9
−
Method
Ref.
imp. diff.
[Knu02]
MitM(ASR) [IS13]
Integ.-like [Tod13]
 MitM
Ours
• No assumption on , e.g.  can be one-way func.
• For  = ( + 1)/2, #rounds is 4 + 2.
• Complexity is higher than previous work.
Copyright©2014 NTT corp. All Rights Reserved.
6
Attack Results on Feistel-3
-function
#rounds for || =
3/2 2

11
Method
Ref.
MitM(ASR)
[IS13]
any
7
9
any


 MitM
Ours
identical


 MitM
Ours
• Attack complexity depends on the S-box size, .
• Our attacks work for practical choices of 
e.g.  = 128,  = 8. (128-bit block, 8-bit S-boxes)
Copyright©2014 NTT corp. All Rights Reserved.
7
Framework of Meet-in-the-Middle Attacks
Copyright©2014 NTT corp. All Rights Reserved.
General Framework
• Divide the cipher into three parts.
• [Offline] Construct a distinguisher in  ,
which works for any choice of  .
• [Online] Guess  and  . The correct
subkey guess leads to an internal state value
consistent with the distinguisher.
plaintext






ciphertext
Copyright©2014 NTT corp. All Rights Reserved.
9
Distinguisher in MitM Attacks
plaintext






ciphertext
,  ⊕ 1
,  ⊕ 2
  ⊕ ( ⊕ 1 )
  ⊕ ( ⊕ 2 )
,  ⊕ 2
  ⊕ ( ⊕ 2 )
• Determine a set of 2 differences {1 , 2 , ⋯ , 2 }.
• --set: a set of 2 paired values (,  ⊕  ).
• The num of (ordered) set of 2 partial differences
after  can be smaller than all the possibilities.
Copyright©2014 NTT corp. All Rights Reserved.
10
Key Recovery Procedure
plaintext






ciphertext
Precompute:
Compute possible sets of partial differences from --set.
They are stored in a pre-computation table  .
Online:
- Collect (, ′) and , ’ . Guess  and  .
- Build a --set at the beginning of  and obtain .
- Obtain  and compute the diff at the end of  .
- Check if the result matches one of  .
Copyright©2014 NTT corp. All Rights Reserved.
11
Key Recovery Attacks against Feistel-2

/2
−1

/2

+1

Copyright©2014 NTT corp. All Rights Reserved.
Approach of Constructing Distinguisher
1. Find a truncated differential characteristic
satisfying the following condition:
• Given a pair of input and output differences, the
number of possible internal state values is small.
Lemma 1
2. For each internal state value, differential
propagation from the beginning to the end of
 is uniquely computed.
Proposition 1
Copyright©2014 NTT corp. All Rights Reserved.
13
5-Round Distinguisher (Lemma 1)
Let , ′ be two non-zero
differences s.t.  ≠ ′.
 +1
The number of internal
state values for the middle
3-rounds satisfying the
differential propagation
(, ) → (, ′) in 5
rounds is only 2/2 .


+1
+2
+3
+4
+5
Feistel-2
5 rounds

+5
+6
′
Copyright©2014 NTT corp. All Rights Reserved.
14
Proof of Lemma 1 (1/2)
Input difference (, )
and output difference
(, ’) are propagated.
 +1
+2
 +3
The num of differential
characteristics is 2/2 .
, ’, ’’ are fixed, and if
 is fixed, all the
differences are fixed.
′+4
 +5

+1
+2
+3
+4
+5
+5
+1
+2
+3
+4
+5


+1

+2

+3

0

′′

0
+4 ′
+6
′
Copyright©2014 NTT corp. All Rights Reserved.
15
Proof of Lemma 1 (2/2)
For each , input and
output differences are
fixed for  functions in the
3 middle rounds.
If both of input and output
differences are fixed, only
1 state value is obtained
on average.
The num of internal state
values satisfying the diff
propagation is 2/2 .
 +1
+2
 +3
′+4
 +5

+1
+2
+3
+4
+5
+5
+1
+2
+3
+4
+5


+1

+2

+3

0

′′

0
+4 ′
+6
′
Copyright©2014 NTT corp. All Rights Reserved.
16
5-Round Distinguisher (Proposition 1)
Set  = 1 , 2 , ⋯ , 2 to
ones produced by  LSBs of  .
Let ,  ⊕  ,  ∈  be a
pair of state values satisfying
the 5-round diff. propagation.
Make --set (,  ⊕  ),
and construct a set of Δ+5
for each  . The num of such
sets is limited to 2/2 .
0 +1
 +2
∗
∗
∗
∗
--set
+1
+2
+3 
+3
+4 
+4
+5 
+5
+1
+2
+3
+4
+5
+5
difference sequence


+1
0
0
∗
∗
∗
?
+2 
+3
∗
+4
∗
+6
Copyright©2014 NTT corp. All Rights Reserved.
?
17
Intuition for Proof of Proposition 1
Approach:
For each of 2/2 internal
state values, any  at Δ
can be mapped to Δ+5
without the value of
 , +1 , and subkeys.
Intuition:
For each round, the state
value and new input diff
can yield new output diff.
Then, Δ+5 is computed.
0 +1
 +2
∗
∗
∗
∗
--set
+1
+2
+3 
+3
+4 
+4
+5 
+5
+1
+2
+3
+4
+5
+5
difference sequence


+1
0
0
∗
∗
∗
?
+2 
+3
∗
+4
∗
+6
Copyright©2014 NTT corp. All Rights Reserved.
?
18
Key Recovery for || = 

0
• 1 round is added before
the 5R distinguisher.
 1
• The attacker’s first goal
is recovering 0 .
0

0

−1

. = 2
0
−

2

--set
5-round
distinguisher

5
difference sequence
6
′
Copyright©2014 NTT corp. All Rights Reserved.
19
Precomputation Phase
Fix (, ’) and compute
2/2 possible difference
sequences of Δ+5 .
Store the result in  .
Complexity: 2/2
Repeat the above by
changing ’ 2/4 times.
(change /4 LSBs of ’)
Complexity: 23/4

0
0

0
 1

−1

. = 2
0
−

2

--set
5-round
distinguisher

6 ′
/ choices
Copyright©2014 NTT corp. All Rights Reserved.
20
5
difference sequence
Online Phase (Collecting Pairs) 1/2
• Fix 0 .
−1 
 0
• For all 2n/2 choices of  −1 ,
0


−

. = 
query (0 ,∗) and (0 ⊕ ,∗).
0
2 pairs are generated.
 1
0 
--set
• Pick up pairs satisfying 2n/4
choices of (0, ′). 2n/4 pairs
will be obtained.
5-round
n/4
• Iterate the above 2 times
distinguisher
by changing the value of 0 .
2n/2 pairs are expected.
Data Complexity: 23/4

6 ′
/ choices
Copyright©2014 NTT corp. All Rights Reserved.
21
5
difference sequence
Online Phase (Collecting Pairs) 2/2
• Fix 0 .
−1 
 0
• For all 2n/2 choices of  −1 ,
0


−

. = 
query (0 ,∗) and (0 ⊕ ,∗).
0
2 pairs are generated.
 1
0 
--set
• Pick up pairs satisfying 2n/4
choices of (0, ′). 2n/4 pairs
will be obtained.
5-round
n/4
• Iterate the above 2 times
distinguisher
by changing the value of 0 .
2n/2 pairs are expected.
Data Complexity: 23/4

6 ′
/ choices
Copyright©2014 NTT corp. All Rights Reserved.
22
5
difference sequence
Online Phase (Recovery of 0 )
• For each of 2n/2 pairs,
obtain 1 solution of 0
that maps  to . This
leads to 0 .
• Make a --set at 0 ,
and compute the
corresponding −1 with
the recovered 0 .
• Check the sequence of
Δ5 of the ciphertexts,
and check the match
with pre-computed  .

0
0
−1

0
 1

 . = − 
0 
--set
5-round
distinguisher

6 ′
/ choices
Copyright©2014 NTT corp. All Rights Reserved.
23
5
difference sequence
Evaluation of Attacks
• 23/4 difference sequences are stored in  offline.
• 2/2 difference sequences are computed online.
• In total, 25/4 matching candidates. Each match
succeeds with Pr. = 2 ⋅ 2−/2 .
• With  = 2, the right key is obtained.
• Offline: (Data, Time, Mem.) = (0, 23/4 , 23/4 )
• Online: (Data, Time, Mem.) = (23/4 , 23/4 , 23/2 )
Copyright©2014 NTT corp. All Rights Reserved.
24
More Discussion on Feistel-2
• Once 0 is recovered, recovering all the other
subkeys is quite easy.
• Generalization in terms of ||
#rounds for dist.


5
+3
(/2)
#rounds for key recov.
1
−1
• Optimization with time-memory tradeoff
Similarly to the prev work on AES, trunc diff chara is
relaxed. Data decreases, but Time, Mem increase.
Copyright©2014 NTT corp. All Rights Reserved.
25
Summary of MitM Attacks on Feistel-3
• Sophisticated trunc. diff.
chara with rebound attack.
• If  is identical in particular
2 rounds, the attack can be
improved by applying
equivalent transformation.
• Attack complexity depends
on the ratio of the block
size  and the S-box size .
--set
 +1
S
 +2

 +3

 +4

 +5

 +6
′
 +7
 +8

P
S
S
S
S
S

P 

−

−

S
P
P
P
P

+1 

+2 

+3 

+4 

′
+5

P-1
+6 
P 
difference
sequence

′
+7

P
Copyright©2014 NTT corp. All Rights Reserved.
26
Concluding Remarks
Feistel-3
Feistel-2
We improved generic attacks on Feistel with the MitM attack.
-function
#rounds for || =
3/2
2

any
any
bij., ident.
5
5
6
6
7
−
7
9
−
any



MitM
Ours
any
7
9
11
MitM(ASR)
[IS13]
any
identical






MitM
MitM
Ours
Ours
Method
Ref.
imp. diff.
MitM(ASR)
Integ.-like
[Knu02]
[IS13]
[Tod13]
Future work: application to concrete designs
application to other variants of Feistel
Copyright©2014 NTT corp. All Rights Reserved.
27
Thank you for your attention !!
Copyright©2014 NTT corp. All Rights Reserved.
28
1/--pages
Пожаловаться на содержимое документа