What the heck is Differential Cryptanalysis anyway?
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