4
$\begingroup$

In this answer there is the mention of "weak alignment", followed by an indication that it is related to "resistance to truncated differential cryptanalysis".

What exactly is the difference between strong versus weak alignment?

How does it provide resistance to truncated differential cryptanalysis, and does it influence strength or weakness against any other techniques?

What ways can weak alignment be obtained? For example, is there a way to convert AES to have weak alignment (and would that be a good thing?)

$\endgroup$
3
$\begingroup$

Truncated differential cryptanalysis was introduced by Lars R. Knudsen at FSE 1994.

The Keccak team provides an summary of this technique as follows:

In truncated differential cryptanalysis one divides the function input, output and intermediate computation values in sub-blocks, typically of equal size (e.g. bytes). Whereas in classical differential cryptanalysis one studies propagation of differences that are fully specified, in truncated differential cryptanalysis one only specifies whether a sub-block is active (has a difference) or is passive (has no difference).

It has been applied by J. Daemen and V. Rijmen on AES, the idea is therefore to indicate if a byte has a been modified or not in order to retrieve a distinguisher.

In the case of a strong alignment, the truncated differences can be easily constrained and followed. In the case of a weak alignment, differences spread extremely fast and it makes really hard for a subdivision of the input space to be found.

On Keccak ($\iota \circ \chi \circ \rho \circ \pi \circ \theta$) we ignore the $\iota$ operation as it is irrelevant from a Xor difference point of view. Lets consider a subdivision of 5 bits (due to the size of the somewhat S-box substitution: the $\chi$ function) and assume we have a difference on that group.

We will ignore $\theta$ due to its operation being difficult to visualize, basically, the active difference is spread over the slice and the slice behind (by $z$ coordinate) in the state.

Then we have $\pi$, if a truncated difference of 5 bit is active then the slice will be set to active.

enter image description here.

So now we have 5 active truncated difference to track.

Then we have $\rho$, which spreads the differences among the $z-axis$ : enter image description here

Thus, the active truncated differences are now 25.

In other word, the number of active truncated difference in Keccak increases really quickly $\mathcal{O}(25^n)$. This what we call a weak alignment.

$\endgroup$
  • 1
    $\begingroup$ So does this help against regular differential/linear cryptanalysis too? $\endgroup$ – Ella Rose Aug 8 '16 at 21:12
  • 2
    $\begingroup$ Well sort of because your trails expands faster (see the differential cryptanalysis of Keccak by Joan Daemen and Gilles Van Assche). $\endgroup$ – Biv Aug 8 '16 at 21:16

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.