Next: 11 Algorithms for groups Up: 10 Symmetric Cryptosystems Previous: 10.2 Modes of enciphering

## 10.3 Cryptanalytic methods

All that the above discussion gives us is various thumb rules about the options available in order to construct symmetric-key systems and certain guidelines about what to avoid (group, elements of small order, dictionary attack and so on). The actual construction of a symmetric-key ``confusion function'' is a mathematically non-unique ``Black Art''. Various ciphers with names like as DES (Data Encryption Standard), FEAL (Fast Encryption ALgorithm), IDEA, SAFER, RC5, Rijndael, Blowfish, Serpent and others have been proposed. A mathematician may balk at the question of choosing a ``best'' one from all these choices. Unlike public-key systems that are based on known hard problems in Theoretical Computer Science and Mathematics, the strength of symmetric-key systems is based on a lack of knowledge; if you can't figure out a way to crack the system then it must be secure. Thus it is imperative to know what techniques can be used to crack such systems. It is then possible to estimate how successful a given method will be based on currently available computing time and storage space.

While most cryptanalytic methods in ``real-life'' scenarios are based on partial information, it is best to examine a symmetric system as one would a ``black box''. The following tests come to mind:

Entropy of output
How random is the output given general input? One can measure the extent to which the output contains redundancies (as measured by Shannon's theory of information) for different inputs and keys.
Diffusion of input variations
Is the effect of small changes in the input localised? One can examine a large number of input pairs which differ by the same small change; is the change in the resulting output (for a fixed key) in the same place or does it ``diffuse''?
Diffusion of key variations
Is the effect of small changes in the key localised? One can examine (over a large number of inputs) how two keys that differ by a small amount cause variation in the output. Is this difference ``diffuse''?
Weak inputs and keys
Are there some simple inputs which have a lot of symmetry that produce output from which the key can be computed?
In addition, by examining the actual algorithm used one can further attempt to examine the following aspects:
Symmetries
The cryptographic operations should ``break symmetry''. If not then it may be possible to show that each key has an ``inverse'' key and such an inverse may be easily computable.
Small order
The cryptographic functions may be such that iterating them may cause the resulting permutation to be one which is easily recognised.
Partial Reverse-engineering
Is it possible to build simple black-boxes (ones that are ``crackable'') that give output that has considerable overlap with the given black-box?

Next: 11 Algorithms for groups Up: 10 Symmetric Cryptosystems Previous: 10.2 Modes of enciphering
Kapil Hari Paranjape 2002-10-20