2
$\begingroup$

I understand what a linear operation is and what a non-linear operation is, but I would like an explanation of specifically how a non-linear operation on input data mitigates differential crytanalysis attacks. Please note that I am asking this question in the context of developing a cipher rather than simply understanding generically linear vs. differential cryptanalysis.

$\endgroup$
1
$\begingroup$

If you have a linear function $F$ then the output difference corresponding to the input difference $d$ is $$ F(x\oplus d) \oplus F(x)=F(x)\oplus F(d) \oplus F(x)=F(d), $$ for any value of $x,$which is a devastating differential characteristic holding with probability one.

You can take $F$ to be an sbox, or a parallel set of sboxes which make up part of a round. Iterating, you can get a differential characteristic with probability one for the whole cipher since differential characteristics are independent of key addition. This completely breaks the cipher.

Now let $n$ be the input and output bitlength of $F$ and let $F$ be a nonlinear permutation i.e., a proper sbox. The goal is to have many different output differentials, each holding with small probability, corresponding to each input differential.

The best possible case is that each output differential which holds occurs for exactly $2$ out of $2^n$ $x$ values. Note that in binary the output differential corresponding to some $d$ and a fixed $x$ also occurs for $x'=x\oplus d,$ i.e., they come in pairs.

Such a function is called almost perfect nonlinear (APN) but exists only for $n$ odd, thus is not much used since sboxes of byte or multiple byte or nibble length are popular. AES snoxes have maximal differential characteristic probability $2^{2-n}$ instead of the optimal $2^{1-n}$ which an APN sbox would give.

$\endgroup$
1
$\begingroup$

Using linear operations in cryptography causes transforming some characteristics about the plaintext. For example, a very simple characteristic can be the number of odd or even of bits of plaintext. With using these linear operations, characteristics like that can be transferred through the cipher rounds and reach to the ciphertext. One of the important characteristics is the differential of input data. By using the correct form of these nonlinear operations, this characteristic can be mitigated. For Example, in a 4 *4 SBox by substituting one word with another word, this characteristic will not be conveyed because of the changing word of including this characteristic. These characteristics like differential of input data that conveyed to the ciphertext, cause ciphertext no to be completely random form and an attacker can use it.

$\endgroup$

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.