# Understanding a Blowfish cryptanalysis

I'm reading a cryptanalysis on Blowfish, and I've come across something that I don't quite get. Let's denote

$$\delta = a \oplus a'$$

where a and a' are bytes that cause a collision in some S-box when entered as the position to use in said box.

The structure of Blowfish looks like this:

with N+2 positions in P, where N is the number of rounds. Every zero represents one zero-byte. For each plaintext pair where $$P \oplus P' = [0000\delta000]$$ we will get some corresponding ciphertext pairs where $$C \oplus C' = [\delta000xyzt]$$ We denote $$C = (L,R)$$ Now, the cryptanalysis claims that we have the equation $$F(L \oplus P_{N+2}) \oplus F(L \oplus P_{N+2} \oplus [\delta000]) = [xyzt]$$ This is where I get stuck. I don't really see the connection, as the last position in the subkey array P is actually never part of any input to F(), except for in the decryption function, but I don't see how we end up with this algorithm that way either. Any ideas?

The article where I found the equation can be found here.

-
Where do you get that last equation from? Are you taking it from some textbook or article? If so, you should edit your question to include a link to the original source where you got that equation from. –  D.W. Mar 18 '13 at 0:42
I got it from an article. Will add link! –  Psyberion Mar 18 '13 at 0:43

There seem to be some errors or inconsistencies in the question.

If $P \oplus P' = [0000\delta 000]$, and we use the 2-round structure shown in the picture, then the corresponding ciphertext pairs should satisfy $C \oplus C' = [xyzt\delta000]$. This is different from what you wrote (did you omit the final swap shown in the picture above?).

If we let $C=(C_L,C_R)$ and $P=(P_L,P_R)$, etc., then one correct equation is:

$$F(C_R) \oplus F(C'_R) = [xyzt].$$ This follows because, if you look at the picture, the input to the $F$-box in the second (last) round is the same as the right half of the ciphertext.

Note that this is different from what you wrote. (I cannot explain what you wrote; perhaps your notation does not match the picture you included, or something else.)

Edit: Now that you added a link to the paper where you got this from, I can explain what's going on.

First, at a high level: this is not the right first paper to learn differential cryptanalysis from. You first need to understand the fundamental concepts of differential cryptanalysis before you will be prepared to understand that article. That paper is a research paper written for expert cryptographers, who can be assumed to know those concepts. It is not intended to be understandable to someone who does not already know advanced concepts of differential cryptanalysis. Trying to explain the article to someone who does not understand those differential concepts is going to be ... challenging.

So, my primary recommendation is to go learn about differential cryptanalysis first, before trying to read that article. There are good sources on this (you can search this site). One of my favorites is Biham & Shamir's little book, Differential Cryptanalysis of the DES; it gives an excellent introduction to the topic. But there are other sources as well. Whatever source you read, make sure you understand the following concepts: differential characteristic, iterative characteristic, 1-R attack, 2-R attack, distinguishing attack, key-recovery attack.

Once you know those concepts, I can explain concisely what it is going on the particular paper you are referring to. They are using a 2-R attack on Blowfish. As a special peculiarity of Blowfish, after doing the last 2 rounds of Blowfish, you xor the output with two key values ($P_{10}$ and $P_{11}$ in this case). That's not shown in your picture. So, once you take that into account, the input to the last-round $F$-box will be $C_L \oplus P_{10}$, or $L \oplus P_{10}$ in the paper's notation. Also since the two ciphertexts satisfy $C_L \oplus C'_L = [\delta000]$ (or in the paper's notation, $L \oplus L' = [\delta000]$. Therefore, the input to the last-round $F$-box in the first encryption is $L \oplus P_{10}$, and the input to the last-round $F$-box in the second encryption is $L' \oplus P_{10} = L \oplus P_{10} \oplus [\delta000]$. The equation shown in the paper then follows.

If that didn't make sense to you, I apologize, but you'll probably need to spend more time becoming expert at differential cryptanalysis before you'll be able to follow this paper.

-
Hmm, ok. It did get a bit messy at toward the end. I'll give it a shot with paper and pen, to see if I can clear things up a bit. But it's not improbable that this is way above me; I haven't spent too much time studying differential cryptanalysis.. But I will most certainly take your advice and read up on the subject. Thank you very much! –  Psyberion Mar 18 '13 at 1:06
@Psyberion, yes, a clear pencil-and-paper picture of the last 2 rounds of Blowfish, labelled with the various quantities, will help a lot. Hint: the figure you have shown isn't quite right. It's missing the final xor done in the last round of Blowfish. It also is not labelled with $C$/$L$/$R$. (You copied a figure from the paper. That figure was intended to illustrate the iterative characteristic, not to show what's going on in the last 2 rounds.) Being able to prepare such a figure will be a very helpful stepping stone for understanding what's going on here. –  D.W. Mar 18 '13 at 1:20
Writing it down helped a lot actually. It became much clearer, and I now understand where the equation comes from, and why it looks as it does, which was my question. It will suffice for now, so many a hat off to you, and thanks once again! –  Psyberion Mar 18 '13 at 2:36