10 August 1999
Date: Wed, 11 Aug 1999 01:08:21 +0300 (IDT)
From: Orr Dunkelman <orrd@vipe.technion.ac.il>
To: jya@pipeline.com
Subject: Biham's Impossible Differential Analysis
The Impossible Differential Analysis method came to life when Biham researched with Shamir and Biryukov (I hope I didn't misspell) SkipJack. Later on they found out they could make the method more general and apply it to more ciphers. Also they've found Lars Knudsen used the same method to analyse DEAL.
The method of impossible differentials is based on the fact that some differentials are impossible, therefore, a key suggesting one is a false alarm. This allows the cryptanalyst to have a way of throwing away wrong keys.
Beside DEAL, which was broken using impossilbe differentials, the only impossible differential analysis that was done to an AES candidate is mine, which also deals with a simpler version (and found out that it's really bad attack for Serpent).
Now, as a rule, if there is a good mixing, I mean any bit affect after low number of rounds on all the other, impossible differentials will not be so useful. In SkipJack it worked becuase there are 24 rounds in which 16 key bits are not affecting anything at all, and again the impossible differential attack works only for 31 rounds ... there are still some problems to make it 32.
BTW, the reason I didn't post this is due to the reference to my work. I don't think it's polite to do so, so if you think the answer is good enough, you are more than welcome to put it up yourself.
Orr Dunkelman
"In Theory there is no difference between Theory and Practice, but in Practice there is"