The principles of good cryptographic design (Part II)

In my previous blog, I said that there were two examples of clear-thinking security professionals who had come up with a simple set of cryptographic design principles that are easy to understand, fit well with modern security thinking, and deserve to be known more widely. The first was Auguste Kerckhoffs’s six rules. In this blog I’d like to delve into five valuations that Claude Shannon enunciated as appropriate for estimating the value of a secrecy system.

Claude Shannon has been called the “father of the information age” and his achievements give strong evidence for this accolade. Shannon’s theorem showed how arbitrarily complex calculation devices could be built by combining simple building blocks, and informs microchip design to this very day. His seminal paper “A/The Mathematical Theory of Communication” gave us the tools to mathematically describe the challenges of reliable information transmission and the capacity to compress data. In additional such monumental theoretical contributions, Shannon also made numerous practical contributions to intelligent robotics and user experience.

Less famous, but equally brilliant is another of his papers “A Mathematical Theory of Cryptography” which was a classified paper inspired by Shannon’s work in WWII, a declassified version “Communication Theory of Secrecy Systems” was published in 1949. As well as providing a strong mathematical basis for describing cryptographic systems (including the fundamental ideas of confusion and diffusion), Shannon devotes section 12 of this paper to a qualitative description of the criteria that should be applied to the assessment of cryptography. It’s worth bringing these to a wider audience.

Criterion 1: Amount of secrecy

Shannon warns us not only to be aware of the amount of work to break a system, but also the data requirements. He is also aware that even when a complete break is not possible, partial information can sometimes be recovered. This foreshadows attacks such as Bleichenbacher’s oracle on malleable RSA, small subgroup attacks on discrete logarithm systems, biased nonce attacks (such as the recent PuTTY vulnerability), and sublattice information in lattice cryptography.

Criterion 2: Size of Key

Realising the value of effective key management, Shannon recognises that a key should be as small as possible. For all cryptography, there is a brute-force lower bound where adversaries are no longer able to exhaustively try every key. This is currently taken to be around 128-bits for foreseeable adversary capability. Symmetric systems are able to pretty much match this lower bound, whereas classical public key systems have to deal with keys two, four or twenty times bigger. Modern post-quantum algorithms have even larger keys, from 100x to 10,000x bigger than the brute force bound.

Criterion 3: Complexity of Enciphering and Deciphering Operations

Shannon emphasises the importance of simplicity to security. This is strongly related to Kerckhoffs’s 5th and 6th rules, which relate to agile deployment and ease of use. Shannon notes that complexity leads not just to latency but also to errors and larger instantiations. Larger implementations e.g. in terms of lines of code, increase attack surface and the cost to assure the product or service.

Criterion 4: Propagation of Errors

Shannon also tells us to be aware of how resilient a cryptographic design is to modification of the ciphertext. Although Shannon’s original motivation was in the cost of correction and possible retransmission of messages, more modern cryptanalysis has taken this line of inquiry further. Active cryptanalysis using fault-injection and tracking variations in response have provided a number of attacks on public key cryptosystems. The challenge becomes still greater with some of the newer post-quantum algorithms, where some possibility of decryption failure is almost unavoidable. These mean that attackers can seek to boost the chances of error to actively recover secrets. In turn this leads to more complex preventative measures to ensure that messages are “legitimately” generated.

Criterion 5: Expansion of Messages

Lastly, Shannon holds that cryptography where ciphertexts are significantly larger than plaintexts are undesirable. This leads to unnecessary consumption of bandwidth and an increased likelihood of errors in transmission. It is not uncommon for even quite efficient cryptography to have additional data in the form of initialisation values or authentication tags and often designers seek to produced more integrated schemes. The additive overhead of these short values is not nearly as painful as public key cryptography, where 3072-bit RSA signatures might be needed to sign 128-bits of data or 6144-bits of ML-KEM are needed to encapsulate a 128-bit key.

The alert reader will notice that Shannon’s criteria are much more easily met by symmetric cryptography than by asymmetric cryptography. This is why Arqit firmly believe that minimising the use of asymmetric cryptography is important, and why our Symmetric Key Agreement platform is based on the robust, compact, and above all simple methods of symmetric key cryptography.