In 2004 I have published a paper [Crypto 2004, Santa Barbara] in which I explain the concept of the so called Bi-Linear attack on DES. The old attack was not extremely strong. It is possible to see that two conditions would be necessary for such an attack to somewhat work well in cryptanalysis of DES:

1. There must a strong connection inside the P-box so that a pair of bits goes from one S-box to another and back. Unhappily there are extremely few such cases in DES, for example the pair 3,17, and the attack is prevented by a strong P-box.
2. The P-box must have super strong LINEAR annihilators such as for example two Boolean functions inside DES would have to satisfy a condition like:

Z*(a+d)=0

Needless to say they don’t, and this attack is just unthinkable (a detailed description of one attack of this type can be found in section 11.2 of this paper). There are extremely few cases where point 1. would work and in fact the situation is far worse for point 2.. It is possible to see that the probability that Z*(a+d)=0 for a random Boolean function is

(2^-9.5)^2.

3. Moreover it is easy to show mathematically that such a Boolean function cannot be non-linear and balanced at the same time [a little theorem which we leave as an exercise for a reader, solution will be published soon].

So we have an extremely weak attack on DES which does not and cannot work due to points 1. 2. and 3. However:

Reality is More Interesting than Fiction

The idea is that we need to relax this attack a little bit and eventually the obstacles 1. 2. 3. can be removed or circumvented.

It will come as a shock to anyone who has ever studied DES but linear annihilators DO EXIST for the original DES S-boxes. For example we have these two examples:

(1+R14+R16)*(W4+X4+Y4+Z4+1+R12+R14) = 0

(1+R16+R17+R20)*(W5+X5+Y5+Z5+1+R17) = 0

Specialists of Boolean functions would say that “some output linear combinations of DES S-boxes are 1-weakly-normal” see this paper. This is actually a very strong property. Extremely few Boolean functions have this property (actually also about 2^-9.5 of all Boolean functions on 6 variables).

New Attacks

So obstacles 2. and 3. are removed. Where do we get from there?
The question really is how to remove obstacle 1. as we are NOT allowed to change the wiring of DES in order to make the job easier for us. The answer is that we need an attack able to exploit properties such as above. The existence of such an attack has been an open problem since 1985, the famous mystery paper by Adi Shamir. We are going to release such an attack in 2019.

More Observations

For now, let us look at the underlying DES facts.

Why is our property related to the one observed by Shamir? Shamir observes that for many DES S-boxes the sum of 4 outputs such as (W1+X1+Y1+Z1) for the 1-st S-box is trongly biased. If so either (W1+X1+Y1+Z1) or (1+W1+X1+Y1+Z1) will have a large number of annihilators (it is easy to see that the number of annihilators depends on the Hamming weight or the number of 1’s in the truth table of a Boolean function and nothing else, see Thm C.2. in Appendix of this paper.) Then we will not be surprised to see that for example:

R01*(R04+1)*(W1+X1+Y1+Z1)=0

Now our new properties are yet stronger, we have only one affine factor:

(1+R16+R17+R20)*(W5+X5+Y5+Z5+1+R17) = 0

Moreover the connection between the size of annihilator space and the biases works both ways. We have also accidentally discovered that not only sums of 4 outputs but also things such as

(W5+X5+Y5+Z5+1+R17) 

are strongly biased with the actual original DES S-boxes.

This is new, and was not observed before and not contained in properties presented by Shamir, or cannot be a consequence of these previously observed properties, as we added an affine function. It extends the properties discovered by Shamir with new correlations not studied before, and more importantly with linear annihilations and their applications in cryptanalysis. An actual attack which exploits this type of properties will be published in 2019.

Walsh Spectrum Connection

More generally we observe that a sum of all 4 outputs of some DES S-boxes can have more than one very strong correlation with linear functions. Is there are bigger picture we can see here? Yes, the set of all such correlations have been studied since 1970 [yes! in 1976 was already a routine tool, a proof can be found in slide 33  here] and today it is known under the name of Walsh spectrum. Here are the Walsh spectra for the sum of 4 outputs for the three DES S-boxes studied above:

W1+X1+Y1+Z1 {0: 19, 4: 27, 8: 11, 12: 3, 16: 1, 20: 1, 24: 1, 36: 1}
W4+X4+Y4+Z4 {0: 54, 16: 8, 32: 2}
W5+X5+Y5+Z5 {0: 32, 8: 30, 24: 1, 40: 1}

Extremely bad, yes? Well not quite.
We need to observe that this sort of things happen frequently even for Boolean functions chosen at random. It is clear that from the point of view of diffusion or the P-box, attacks which involve all the 4 outputs of each S-box are going to be the hardest to make, or will involve larger numbers of simultaneously active S-boxes. The fact that it happens here when all the 4 outputs are used and not with say W1+Y1, should possibly be considered as evidence that DES was designed to be particularly strong against our attacks [again an attack able to exploit such properties will be published in 2019].