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?