In Differential Cryptanalysis of DES-like Cryptosystems by Biham and Shamir, they provide examples using differentials inputs such as $\Omega_p = 00\ 80\ 82\ 00\ 60\ 00\ 00\ 00_x$. Most of article is about differential cryptanalysis and presents the generic method, the way to find subkeys. But I can't find a clear explanation about how to find the differentials used in examples.

I do get the idea about feeding an S-box in order to retrieve the differentials, but these S-boxes only have 6-bit inputs for 4-bit outputs (in DES). So the memory space required in order to do such analysis is $2^6 \times 2^4 = 1024$ integers $\approx 4\ Ko$. This can be easily placed in the RAM. The method is presented in Modern Cryptanalysis (2008, Wiley Publishing; Chapter 4, pp. 122-145) by Christopher Swenson.

However, given an S-box with a bigger input such as the one used in FEAL-X (while remaining broken), we need a table of the following given size : $2^{32} \times 2^{32} = 2^{64}$ integers $\approx 2^{32}\times 16\ Go$. Such a thing is too big to store on one of today's computers.

Hence my question: how is it possible to find the right differential for bigger input round functions without the size constraint of this analysis.


1 Answer 1


If such a large Sbox with no structure were to be analysed you'd treat the analysis as a one-off precomputation.

Considering only classical differential cryptanalysis as an example, after the precomputation you'd only need to keep track of the highest probability differentials since if you combine a high probability differential with a low probability one, you've already lost quite an edge and over multiple rounds your attack will fail.

As for FEAL, there is lots of structure in the 32x32 round function and divide and conquer is the way to go.

If there was a randomly chosen huge Sbox, life would be difficult, but it is also difficult for the designer who'd have a hell of a time proving the strength of his/her randomly chosen Sbox, with any kind of guarantee. Blowfish Sboxes which are key dependent, for example, are only 8x32 (thanks @J.D.) and this helps by limiting the number of input differences that need to be considered.

  • 1
    $\begingroup$ The Blowfish s-boxes are actually 8x32. $\endgroup$
    – J.D.
    Commented Sep 24, 2016 at 4:58
  • $\begingroup$ @J.D. you're right of course. $\endgroup$
    – kodlu
    Commented Sep 24, 2016 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.