2
$\begingroup$

I saw the several articles about MDS matrices. They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks. My question is:

For example in the case of linear attack, is constructing the bias table of MDS matrices behavior impossible? Or the values of biases are such a way that linear attack is not applicable and its complexity is higher that brute force attack?

$\endgroup$
3
$\begingroup$

They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks.

That would probably depend on the cipher, but in generally, pretty accurate.

is constructing the bias table of MDS matrices behavior impossible?

Actually, it's trivial; MDS matrices are completely linear, and so they have probability 1 linear and differential trails.

So then, if MDS matrices, in themselves, offer no protections against linear and differential cryptanalysis, why are they said to help greatly?

Well, it's because they help other components within the cipher work a lot more effectively, as it forces any linear/differential characteristic to go through most of the cipher.

Consider this simple design:

     |       |      |      |
   sbox    sbox   sbox   sbox
     |       |      |      |
    ------ MDS Matrix ------
     |       |      |      |
   sbox    sbox   sbox   sbox
     |       |      |      |

Then, for any linear characteristic, that characteristic must go through at least 5 of the sboxes; that's because for any nonzero change, the MDS matrix ensures that the number of input lines changed plus the number of output lines changed is at least 5. So, if the sbox have a best linear characteristic of $\epsilon$, then the best path here is at most $\epsilon^5$.

If we scale this toy example up into something realistic (e.g. AES), then any path must go through a huge number of sboxes, and so any path is effectively dampened out.

$\endgroup$
  • 1
    $\begingroup$ Not only that but as I explained in my answer to crypto.stackexchange.com/questions/35823/… the full Weight distribution of MDS codes is known thus the probability that the best path is $\varepsilon^5$ can be upper bounded by calculating the number of codewords of weight 5 and dividing by $(2^8)^4$ the total number of codewords, which gives a probability less than $2^{-18}$. The no. Of codewords of weight $i$ is $$ A_i= \binom{n}{i} \sum_{j=0}^{i-d} (-1)^{j}\binom{i}{j} \left( q^{i+1-d-j}-1\right), $$ $5\leq i\leq 8,$ and $q=2^8.$ $\endgroup$ – kodlu May 7 '17 at 22:32

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.