On page 46 of these lecture notes, it seems to say that if we have a Feistel cipher, and plaintexts $(L_0, R_0)$ and $(L_0^*, R_0^*)$ with corresponding encryptions, then we can determine the key? But isn't this not the case by Luby-Rackoff? I'm not entirely sure what the slides are even saying. They say that we can compute $R_3 \oplus R_3^*$, but so what? How does this help determine the key?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Can you provide a self-contained description of the claim in those lecture notes (without requiring us to click elsewhere, and without relying upon a link that could disappear at any time)? How many rounds are we talking about? What kind of Feistel cipher? $\endgroup$– D.W.Commented Jan 5, 2015 at 7:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Xor can help find bits not yet known, whether most significant or least significant; and help the adversary find more information about both ciphertext and plaintext, especially if a table of potential plain texts or even keys is stored in conjunction with bitwise Xor.
Some reading:
Although this has minor typos, the notes on Feistel networks and Xor is excellent:
https://github.com/FredericJacobs/Cryptography-Stanford-Notes/blob/master/crypto-notes.md
Luby-Rackoff, as you may already know, is a key component of the Feistel network and it is not secure in 1,2, or 3 layers. Luby-Rackoff must have a 4 independent layered Feistel network structure from independent seeds to be considered a strong pseudo-random permutation. No less than 3 independent rounds must be used to even be considered a pseudo-random permutation though it is much weaker. Some consider a 3 round Feistel to be a secure pseudo-random function, but 4 rounds proves to be more secure.
No more than 8 corresponding outputs from the 32 pairs of inputs of the Xor should exist.
I suggest learning more about Xor and differential cryptanalysis.
Please focus most on pages 4-7 and 11-16, but the whole article is interesting if you have time: http://cs.ucsb.edu/~koc/ccs130h/notes/dc1.pdf
It covers the tables and Xor technique in much better detail.
-
$\begingroup$ Would you mind elaborating further? For instance, what is icg.isy.liu.se/courses/tsit03/forelasningar/cryptolecture04.pdf trying to say? Why is 3 rounds weak because we can compute $R_3 \oplus R_{3}^{*}$? $\endgroup$– WilsonCommented Dec 26, 2014 at 16:37
-
$\begingroup$ Yes. Two known plain-text attacks are made upon L0R0 and L0R0* via R3 xor R*3 which then = the equation you see on page 46, but it is pp. 47-51 that provides the method and illustration of how this works. L3 XOR L3 gives us some n string bits in this case: 101110.Then as expected we have an expander interacting with ki that encrypts. Then the two S boxes are Xored which provides the equation on page 47 and the resulting n bit string.Then the n bit strings and provided equations can be stored, analyzed and compared in a table.The resulting digits on the left can be compared with the various Xor $\endgroup$ Commented Dec 26, 2014 at 19:41
-
$\begingroup$ Also please see new edits to my original response to you. $\endgroup$ Commented Dec 26, 2014 at 19:53