This file is available on a Cryptome DVD offered by Cryptome. Donate $25 for a DVD of the Cryptome 10-year archives of 35,000 files from June 1996 to June 2006 (~3.5 GB). Click Paypal or mail check/MO made out to John Young, 251 West 89th Street, New York, NY 10024. Archives include all files of cryptome.org, cryptome2.org, jya.com, cartome.org, eyeball-series.org and iraq-kill-maim.org. Cryptome offers with the Cryptome DVD an INSCOM DVD of about 18,000 pages of counter-intelligence dossiers declassified by the US Army Information and Security Command, dating from 1945 to 1985. No additional contribution required -- $25 for both. The DVDs will be sent anywhere worldwide without extra cost.

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.