Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
