State of the Art in Symmetric Cryptanalysis

Cryptography is the science of hiding information. It is now a part of the computer science formally, though first cryptographers appeared thousands years before the computer. The art of recovery of the hidden information, or cryptanalysis, appeared in the very beginning, and is still one of the most intriguing part of cryptography.

Cryptanalysis starts with a search for a weakness in a cryptosystem, for a flaw that was missed by its designer. An encrypted message must not reveal any information about its origin, so the cryptosystem must make it look as random as possible. Any mistake, any missed property may become a target for a cryptanalyst and a starting point for a compromise of the cryptosystem's security - a break.

This survey is devoted to the cryptanalysis of symmetric primitives. Historically, by a symmetric encryption we understand that all the parties have the same information needed for encryption and decryption, with block and stream ciphers as the most famous examples. A block cipher transforms a large block of data with an algorithm parametrized by a secret key. A stream cipher expands a secret key into arbitrarily long sequence, which is mixed with a data stream.

Hash functions convert a data string to a fixed-length hash value, which serves as an integrity certificate. Though hash functions do not encrypt, they are designed similarly to block ciphers. Message authentication codes (MAC) produce a hash value using a secret key, so they are between ciphers and hash functions. As a result, the cryptanalysis of hash functions and MACs employs methods that were initially developed for the analysis of block ciphers. Ciphers, hash functions and MACs process arbitrarily long data streams, the access to which is sequential. This leads to the principle of an iterative design, where data is divided into blocks, and each block is processed by an algorithm with a fixed-length input. Such algorithms for hash functions are called compression functions. In contrast, by a block cipher we mean a primitive with a fixed-length input, which is used to encrypt arbitrary long data in a mode of operation.

We are primarily interested in the methods that are used in attacks on at least two different primitives. Cryptanalysis is often described as a cloud of non-related and dedicated attacks, which can be used only once. We introduce it in a more structured way.