11 September 1998
Date: Fri, 11 Sep 1998 07:20:57 +0200 From: Anonymous <email@example.com> Subject: Re: Impossible Analysis Paper at Crypto98 To: firstname.lastname@example.org > There's talk of a paper given at Crypto98 on "Impossible > Differential Analysis" which got the NSA people scribbling > like mad taking notes as though this was something that > had never come up at the agency and they'd better get > right on it. > > Roughly, as I heard it (and I may be way off), the premise is > that instead of using differential analysis for finding weaknesses > in a cipher, to flip that to determine what could not possibly be > a weakness in a cipher and build one with just those attributes. > > Is this report correct, and is there a source for that paper? This was presented at the rump session and apparently there is no paper writeup yet. Biham's home page at http://www.cs.technion.ac.il/~biham/ has a place you can register to be notified when new material comes out. With conventional differential cryptanalysis, you look for pairs of inputs which have differences (xors usually) such that after a certain number of rounds, the ciphertexts have certain differences with excess probability. With "impossible" differential cryptanalysis, you look for inputs with differences which lead to ciphertext differences that are "impossible", or at least have reduced probability. It's the same basic idea but you look for diminution rather than enhancement of the probability of later differences. Because of the reversal of the effect, the techniques for identifying differentials, exploiting them, and designing against them are rather different. As a result ciphers which were designed to resist differential cryptanalysis may be vulnerable to impossible differentials. This technique has apparently led to an improved attack on SkipJack, announced on Biham's web page above as "coming soon". There was also a moderate improvement in attacks on reduced-round IDEA (not effective against the full number of rounds though). At Crypto everyone was scurrying off to see if any of the AES candidates could be knocked out by the new technique.