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.