Saturday, December 24, 2016

Why is 2-round Feistel not Secure PRP?

The theorem, Luby-Rackoff'85, describes that, 3-round Feistel is a secure PRP if f is a secure PRF. I have many questions,
  1. Why 3-round? 
  2. Is 2-round a secure PRP?
  3. Is 1-round a secure PRP? 
Now, we use the below picture to check if 1-round Feistel a secure PRP?


We specify 
Funcs [M, C] as set of all functions from M to C.

We specify 
F as the 1-round Feistel.
F: K x M ---> C, 
where 
K is a key space,
M = {0,1}^(2n), is a message space,
C = {0,1}^(2n), is a cipher text space.

f1 is a secure PRP
f1: K x {0,1}^n ---> {0,1}^n

After we input a message
m = R || L, 

,the output cipher text is
c = L1 || R.

When we check the cipher text and the message, we can say that the cipher text is produced by F because the left block of the cipher text is R that comes from the right block of the message. Therefore F is distinguishable from the Funcs. F is not sure PRP.

OK, Let's use the below picture to check if 2-round Feistel is secure PRP.


We specify 
F as the 2-round Feistel.
F: K x M ---> C, 
where 
K is a key space,
M = {0,1}^(2n), is a message space,
C = {0,1}^(2n), is a cipher text space.

f1 and f2 are secure PRP

After we input two message, ma and mb,
the output cipher text are ca, cb.

ma = R || La ---> ca = R2a1 || La1
mb = R || Lb ---> cb = R2b1 || Lb1

We observe that.

La1 = La xor f1(R)
Lb1 = Lb xor f1(R)

La1 xor Lb1 = La xor Lb ---- (formula 1)

When we check the two cipher texts and the two messages with this formula 1, we can say that they are produced by F. Therefore F is distinguishable from the Funcs. F is not sure PRP.

 -GY

1 comment:

  1. Could you please upload the pictures again? they are not visible now.

    ReplyDelete