Hey all,
Recently I was reading the OG paper from Shamir and Biham regarding the attack and I am lost about of the details:
If we craft pairs that are special and supposed to fit the 13-round characteristic starting at round 2, we deal only with 2\^13 plaintexts with their cross product creating 2\^24 pairs. These have 2\^12 possible results, since we are interested in matching our given P' to cancel out F(R). F is the round function and R is the right 32 bit in the 1st round.
Now, they argue that because each "structure" (still not sure what they mean) contains 2\^12 pairs, we get that on average we'll need \~2\^35 pairs in order to get a "right" pair.
1. I don't understand the trick here, obviously there is one.
2. I don't understand why we still need 2\^47 chosen plaintexts and similar running time? (The paper actually states 2\^36 running time, but wikipedia says something like 2\^47)
I am sure I don't understand all too, well, so correct my assumption if needed.
Thanks! (: