MDS matrix

From Wikipedia, the free encyclopedia

An MDS matrix (Maximum Distance Separable) is a matrix representing a function with certain diffusion properties that have useful applications in cryptography. Technically, it is the transformation matrix of a linear code that reaches the Singleton bound. That is, it is an m×n matrix A over a finite field K representing the linear transformation f(x)=Ax from Kⁿ to K^m such that no two different (m+n)-tuples of the form (x,f(x)) coincide in n or more components.

Serge Vaudenay suggested using MDS matrices in cryptographic primitives to produce what he called multipermutations, not-necessarily linear functions with this same property. These functions have what he called perfect diffusion: changing t of the inputs changes at least m-t+1 of the outputs. He showed how to exploit imperfect diffusion to cryptanalyze functions that are not multipermutations.

MDS matrices are used for diffusion in such block ciphers as SHARK, Square, Twofish, Manta, Hierocrypt, and Camellia, and in the cryptographic hash function WHIRLPOOL.

Reed-Solomon codes have the MDS property, and a necessary and sufficient condition for a matrix to be MDS is that every possible square submatrix obtained by removing rows or columns is non-singular.

[edit] References

• Serge Vaudenay (1994-11-16). "On the Need for Multipermutations: Cryptanalysis of MD4 and SAFER" (PDF/PostScript). 2nd International Workshop on Fast Software Encryption (FSE '94): 286-297, Leuven: Springer-Verlag. Retrieved on 2007-03-05. 
• Vincent Rijmen, Joan Daemen, Bart Preneel, Anton Bosselaers, Erik De Win (1996-02). "The Cipher SHARK" (PDF/PostScript). 3rd International Workshop on Fast Software Encryption (FSE '96): 99-111, Cambridge: Springer-Verlag. Retrieved on 2007-03-06. 
• Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson (1998-06-15). "The Twofish Encryption Algorithm" (PDF/PostScript). Retrieved on 2007-03-04.