11 September 1998

Date: Fri, 11 Sep 1998 07:20:57 +0200
From: Anonymous <nobody@replay.com>
Subject: Re: Impossible Analysis Paper at Crypto98
To: cypherpunks@cyberpass.net

> 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.