# Differential Cryptanalysis

## A Ciphers By Ritter Page

What the heck is Differential Cryptanalysis anyway?

### Contents

• 1999-01-11 Frank Gifford: "You can create a list of all possible [4 bits] input differences and see what the output differences are allowed after going through a round."
• 1999-01-13 Scott Fluhrer: "Lets see if I can go through of an example of how DC would be used against this cipher some detail...."
```
Subject: Re: Differential Cryptanalysis???
Date: 11 Jan 1999 15:50:21 -0500
From: giff@eng.us.uu.net (Frank Gifford)
Message-ID: <77do6d\$q5t@trebuchet.eng.us.uu.net>
References: <nHqm2.4035\$TO5.107922@ptah.visi.com>
Newsgroups: sci.crypt
Lines: 29

In article <nHqm2.4035\$TO5.107922@ptah.visi.com>,
Michael A. Greenly <newsgreenly@caidesign.com> wrote:
>
>    I've been trying to get a handle on differential crytptanalysis for
>the last week or two but seem to have run into a road block of sorts.  I
>think I understand most of it but there's one part the seems to elude
>me.  I don't understand how a right pair suggests a key?

Here's what I can suggest based on the educational cipher you describe on
your web page.

Notice that the input and outputs to the Left halves are affected only
by the output of the second round function.  So create some pairs of
plaintexts which differ by a known amount in their input, encrypt, and
see how the output changes.

By seeing the difference between the two left halves, you know how the
output from the second round has changed.

You can create a list of all possible [4 bits] input differences and see
what the output differences are allowed after going through a round.

Try a couple pairs by hand and see what you get.

-Giff

--
giff@uu.net       Too busy for a .sig

Subject: Re: Differential Cryptanalysis???
Date: Wed, 13 Jan 1999 03:13:21 GMT
From: Scott Fluhrer <sfluhrer@ix.netcom.com>
Message-ID: <77h2kv\$lps@sjx-ixn9.ix.netcom.com>
References: <nHqm2.4035\$TO5.107922@ptah.visi.com>
Newsgroups: sci.crypt
Lines: 97

In article <nHqm2.4035\$TO5.107922@ptah.visi.com>,
"Michael A. Greenly" <newsgreenly@caidesign.com> wrote:

>
>    I've been trying to get a handle on differential crytptanalysis for
>the last week or two but seem to have run into a road block of sorts.  I
>think I understand most of it but there's one part the seems to elude
>me.  I don't understand how a right pair suggests a key?

Lets see if I can go through of an example of how DC would be used
against this cipher some detail (and, forgive me if I go through detail
you already know -- this tiny explination might help someone else who
doesn't know as much as you).

First of all, to apply DC, you need to find differentials that hold with
(relatively) high probability.  In case you didn't know, a differential
is a pair of plaintexts whose bit differences flow through the cipher
in a predictable way.

To find such high probability differentials, you go through the sbox,
and look for differences in inputs that produce consist differences in
the output.  Going through your sbox, I (actually, a computer program:
I'm lazy) find these high probability differences:

If the input of the sbox is xored by A (1010), the output bits change
(is xored by) 4 (0100) with probability 50%

If the input of the sbox changes by 5, the output changes by 9 with
probability 37.5%

If the input of the sbox changes by 8, the output changes by 3 with
probability 37.5%

Now, using these regularities in the sbox, we can assemble high-probability
differentials:

If the input to the cipher changes by A4 (10100100), then the internal
data after the first half-round changes by 0A with probability 50% (because
the output of the sbox will change by 4 with probability 50%, and everything
else is linear).  Given that, the second half-round changes by A0 with
probability 100% (because the input to the sbox is that same in both cases).
Given that, the third half-round changes by 4A with probability 50%, giving
an input-to-output differential with probability 0.5*1*0.5 = 0.25.

Or, pictorially, the differential looks like (and, refer back to
http://www.pinenet.com/~mgreenly/twisted.gif for what goes through
the sboxes):

A   4
\ /
X      Probability 0.5
/ \
0   A
\ /
X      Probability 1
/ \
A   0
\ /
X      Probability 0.5
/ \
4   A

Now, the attacker encrypts pairs of plaintexts which differ by A4, and examine
the corresponding ciphertext.  If the ciphertexts do not differ by 4A, he
discards them (actually, he could in this case fruitfully analyze them, but
not in a real cipher, which may have differentials with probability 0.00001)
If he does find such a pair, then he knows that either:

- It was a coincidence (unlikely in this case, but a real possibility with a
real cipher).  You make sure by finding several probable diffentials; or

- This is a manifestation of the differential.  In which case, he knows that:

- The input to the first sbox was either 1, 3, 4, 6, 9, B, C or E (the 8
inputs that will cause this differential to occur).  And, since he knows
the input bits (which are the plaintext bits), he knows the first
half-round subkey bits are in one of 8 settings.  In effect, he learns
one bit from the subkey

- The input to the third sbox was either 1, 3, 4, 6, 9, B, C or E (the 8
inputs that will cause this differential to occur).  And, since he knows
the input bits (which are the ciphertext bits), he knows the third
half-round subkey bits are in one of 8 settings.  In effect, he learns
another bit from the subkey

So, by trying an average of 4 plaintext pairs, he gets 2 key bits.  Using
different differentials (eg. the 59->95 differential, which occurs at
probability 0.14), he whittles down the key to a point where he can
exhaustively search the rest of the key bits.

--
poncho

```

Terry Ritter, his current address, and his top page.

Last updated: 1999-02-20