Monday, December 26, 2016

Is double AES more secure?

Is double AES more secure? The answer is YES, but it is not much more secure as you expect.

Do you remember why to use 3DES instead of double DES? The reason is double DES can be compromised with meet-in-the-middle-attack.

Time taken for DES with a 56 bits key size is 2^56. How about double DES with different keys? The time take is not expected to 2^112. It is smaller than 2^63 by using meet-in-the middle-attack, that is developed by Merkle and Hellman.

The result can be applied to any block ciphers including AES. For example, time taken for AES with a 128 bits key size is 2^128. Time taken with double AES with different keys is much smaller than 2^256. It is,

Time = 2^128 x log (2^128) + 2^128 x log (2^128) << 2^256

-Count

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