6
$\begingroup$

Most of article about differential cryptanalysis present the generic method, the way to find sub keys. But I can't find a clear explanation about how to find the differentials used in examples. In Differential Cryptanalysis of DES-like Cryptosystems by Biham and Shamir, the provide examples using differentials inputs such as $\Omega_p = 00\ 80\ 82\ 00\ 60\ 00\ 00\ 00_x$. I do get the idea about feeding S-box in order to retrieve the differentials but these S-box are only 6 bit input 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 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 thing can't be stored on current sized computer.

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

$\endgroup$
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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