How to Make a Dierence: Early History of Dierential Cryptanalysis. Eli Biham After CRYPTO’91 a new idea came up of how to get the rst round for free, …

How to Make a Difference: Early History of Differential Cryptanalysis Eli Biham
Department of Computer Science Technion, Haifa 32000, Israel March 16, 2006

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Noah and the Ark
Take on board with you seven pairs of every clean animal, a male and a female; one pair of every unclean animal, a male and a female; and seven pairs of every kind of bird, a male and a female, to insure their survival on Earth

came in pairs to Noah and to the ship, male and female, just as God had commanded Noah

Genesis 7:23,9, The Message

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

8/8/88

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

al 1 Fe

y] um [F

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Initial Idea
The initial idea was very simple, related to the fact that addition and XOR differ only by the carries Let the carry pattern of the sum of two numbers be Cx, y x y x y

The carry patterns are highly related to the inputs eg, in many cases, knowing bits of the carry pattern leads to knowledge of bits of the input This idea led to the following observation on the F -Function of Feal: Given the XOR
difference of the inputs to the central blue S boxes, and the output XOR, there are 30 possibilities on average for the two 16-bit inputs
c Eli Biham - March 16, 2006 5 FSE 2006, Graz, Austria

Initial Idea cont
Add also that It is very easy to force the central two output bytes to remain unchanged, while changing the input of the F -function Then, it is possible to generate plaintexts for which we can predict the differences in the last round: 1 Select a plaintext P and compute P P 2 Then a 0, b and the middle two bytes of B are 0 0, 3 It is easy to predict the middle two bytes of D and all d 4 We get about 30 possibilities for the inputs to the middle two S boxes, instead of 216 5 We save a factor of about 216/30 211 in the key search, ie, 253 instead of 264
c Eli Biham - March 16, 2006 6 FSE 2006, Graz, Austria

Note
Fortunately, This analysis is made on the version of Feal from [Fumy] The whole idea would not come at all on the real Feal-4 with additional whitening

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Improvements
We got an attack with complexity 253 Can we do better?

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Improvements
cont
Improvement: Use also a third plaintext with P , where only the most significant bits of all the bytes are complemented This additional plaintext would reduce the complexity to about 245

The idea of using PAIRS as such is not yet there Using many pairs, the complexity becomes negligible

Also the idea of fixed differences is not yet explored The attacker does not even predict the full output difference B in the second round B
c Eli Biham - March 16, 2006 9 FSE 2006, Graz, Austria

Unfortunately
Unfortunately, when we got to this point, we found out that Feal already has EIGHT rounds with full whitening The whole technique as described cannot work with so many rounds

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Characteristics A Step Toward Differential Cryptanalysis
How can we extend the attack on FOUR round to EIGHT rounds? It appears that in Feal there are three differences a such that A can always be predicted probability 1, by changing only most significant bits where the carry bits are ignored Using these, and if we fix the plaintext difference, we know for sure the difference after three rounds

c Eli Biham - March 16, 2006

FSE 2006, Graz,
Austria

Characteristics cont

P 02000002 80808080x A 02000002x B 0 C 02000002x
F

a 80808080x always b 0 always

c 80808080x always

T 02000002 80808080x

But no more than three rounds can be gained At most five rounds can be attacked that way Fixing the difference seems a good idea
c Eli Biham - March 16, 2006 12 FSE 2006, Graz, Austria

Characteristics cont
P A2008000 80800000x A 02000000x B 80800000x C 0 D 80800000x E 02000000x
F

a 80800000x always b A0008000x with probability 1/4 c 0 always

d A0008000x with probability 1/4 e 80800000x always

T A2008000 80800000x
c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

8 /8 8 1/ 2

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

8 /8 8 9/ 2

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

First Run in Rosh-Hashana
The program expected time was about 12 hours I left 6 runs for a long 3-day weekend

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

8 /8 0 /1 18

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

8 /8 0 /1 18

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

8 /8 0 /1 18

c Eli Biham - March 16, 2006

FSE 2006, Graz,
Austria

8 /8 1 /1 4

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

8 /8 1 /1 4

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

8 /8 1 /1 9

c Eli Biham - M arch 16, 2006

FSE 2006, Graz, Austria

Adaption to DES
1 3-round characteristics 2 5-round characteristics 3 Attack on eight rounds

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Adaption to DES cont
4 More than eight rounds 5 Iterative characteristics The function f is not one-to-one, Davio, Desmedt, Fosseprez, Govaertz, Hulsbosch, Neutjens, Piret, Quisquater, Vandewalle, Wouters, CRYPTO83 The function f is not one-to-one for fixed K, Desmedt, Quisquater, Davio, CRYPTO84

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Adaption to DES cont
6 15 rounds with 252 chosen plaintexts, 16 rounds with 258 chosen plaintexts

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Best Previous Results
1 Chaum, Evertse, 1985 — 67 rounds 2 Davies, 1987 unpublished — 8 rounds

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

m, u ha C

tse r ve E

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

ies av D

c Eli Biham - March 16, 2006

FSE 2006, Graz,
Austria

Application of the Improved Technique to Feal
The improved techniques devised for the application to DES were applied to Feal This application used all the techniques of differential cryptanalysis, instead of some of the original ideas The results were much better than the original results, due to the new formalism of the attack

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

89 / /2 7

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

CRYPTO90
First public publication of differential cryptanalysis

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Full 16-Round DES
After CRYPTO91 a new idea came up of how to get the first round for free, and thus to attack the full 16-round DES In October 1991 the information that we have an attack was publically published The details were published only in December 1991

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

ok Bo

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

6I 5

tra lus l

ns tio

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

IBM Knew in 1974
Date: Wed, 19 Feb 92 09:43:31 EST From: Don Coppersmith copper@watsonibmcom Adi, We have kept quiet about the
following for 18 years, and decided its time to break the silence We IBM crypto group knew about differential cryptanalysis in 1974 This is why DES stood up to this line of attack; we designed the S-boxes and the permutation in such a way as to defeat it During the summer of 1974 we kept coming up with different classes of patterns that might be used against the DES whose design was still fluid at that point, and part of my job I was working here that summer was in designing criteria for the s-boxes and the permutation that would insure that no such pattern could have too large a probability of success
c Eli Biham - March 16, 2006 35 FSE 2006, Graz, Austria

IBM Knew in 1974 cont
I dont recall and the documentation that survives from that era doesnt help whether at that time we knew the trick of sending a block of messages to get past the first round We certainly knew it later, and were applying it privately to FEAL and a couple of others My contention is that, even though 247 256, still 247 chosen plaintext is not less than 256 on my own machine, and 247 chosen plaintext is not a practical threat I say this not to belittle your work with Biham which was very well executed but
to assert that what we have created is still viable We kept quiet about this for all these years because we knew that differential cryptanalysis was such a potent form of cryptanalysis, and we wished to avoid its discovery and use either for designing or for attacking on the outside; So theres my side of the story Kindest regards Don

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

Another Email with Don Coppersmith
Date: Mon, 14 Oct 91 09:12:35 EDT From: Don Coppersmith copper@watsonibmcom To: biham@cstechnionacil Subject: press reports Eli, The press reports NY Times, Oct 4 and again Oct 13 both imply a very small amount of chosen plaintext Yet my understanding of DES and differential cryptanalysis is that massive amounts of chosen plaintext is required, more like 1015, give or take an order of magnitude I understand you dont want to publicize the actual parameters But please confirm my suspicion that the reporters have misunderstood on this point; that its closer to 1015 than to 10 Thanks Don
37 FSE 2006, Graz, Austria

c Eli Biham - March 16, 2006

Another Email with Don Coppersmith cont
So, its closer to 1015 than to 10 ??? Answer: average1015, 10 5 1014 5 5
1014 Even 5 1014 is closer to 10 than to 1015 Don was wrong 247 is closer to 10 than to 1015

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

IBM Knew Before Us

c Eli Biham - March 16, 2006

FSE 2006, Graz, Austria

The End

c Eli Biham - March 16, 2006

The End

Source:idealliance.org