Cryptography

Keeping Secrets

In order to recognize the full range of distinct security mechanisms that cryptography provides in cyberspace, it is helpful to break down the idea of security into some core functionalities. The first of these is the capability to keep secrets.

Confidentiality

When asked to consider the idea of “security” of information, most people think immediately of confidentiality, which is the ability to restrict knowledge of our (confidential) information to only those whom we want to have it.

We all have secrets. A secret is not necessarily something extremely sensitive, whose revelation would lead to humiliation. Any information about yourself that you don’t want to see published in a newspaper is a secret. Anything you are happy for some people to know, but not others, is a secret. Your bank account details, your passwords, and your PINs are certainly secrets. It’s likely that your address, your date of birth, and your family photographs are also secrets. And what would happen if a stranger walked up to you in the street and demanded to know the names of your children and what you had for dinner last night? Would you tell them? If not, then these are also secrets. We all have information we don’t want everyone to know.¹

Confidentiality is often associated with the concept of privacy, which is more complex and broadly relates to the desire and ability to exclude information from others. As Eric Hughes argued in “A Cypherpunk’s Manifesto”: “A private matter is something one doesn’t want the whole world to know, but a secret matter is something one doesn’t want anybody to know. Privacy is the power to selectively reveal oneself to the world.”² Security mechanisms for providing confidentiality can be used to support privacy, but privacy itself is about more than keeping secrets.

Confidentiality is important in the physical world. We provide confidentiality for written information by sealing it in envelopes, using trusted couriers, or locking it in filing cabinets. For spoken information, we control the level of our voice to restrict who can hear information, or we discuss secrets in closed rooms.

Keeping secrets in cyberspace is a necessity. We need confidentiality whenever we give our personal details to a website; otherwise hackers attacking this website could acquire them. We need confidentiality when we make a mobile phone call, to stop anyone with a simple radio receiver from listening to the call. We need confidentiality when we make an internet payment, to stop attackers from learning our bank card details. Put simply, we need confidentiality whenever we want to store sensitive information on any computer we should not fully trust. Frankly, this is any computer at all, including your mobile phone and your car. And we need confidentiality whenever we transfer sensitive data across any network we should not fully trust. Frankly, this is any network at all, including the internet and your home Wi-Fi network.³

Hide-and-Seek

A child comes home from school with a bad report card that they don’t want their parents to see. This information urgently needs a confidentiality mechanism! The child stuffs the report card under a mattress or buries it in a drawer of clothes. In other words, they hide it.

The critical feature of hiding something is that nobody looking around the hiding place should see any obvious indication of the hidden object. The bed still looks like a bed when the report card is underneath the mattress. The clothes drawer appears its usual messy self when the report is hidden under a pile of football shirts.

Digital information can also be hidden in apparently normal digital objects. One technique is to hide information within a digital image. A computer image is made up of hundreds of individual pixels, each of which is too small to be perceived by the human eye. Each pixel is a fixed color. Just as for any other data, the pixel color is identified by a sequence of bits. Some of these bits are important, while others, the least sensitive ones, fine-tune the precise color. Changes to these least sensitive bits are invisible to a human observer; hence these bits can easily be replaced by bits representing some information we want to hide. All observers see a regular image. Someone who knows where to look can retrieve the hidden information.

We’ve all played hide-and-seek, so we all know that hiding is a risky business, since discovery is always possible. When the bedroom gets cleaned, there is a good chance the report card will be found. Likewise, if someone suspects that a digital image contains hidden information, inspecting the pixel details may uncover the secret.

Hiding information has one advantage over other confidentiality mechanisms. It not only provides confidentiality but also prevents anyone from realizing that a secret exists in the first place. Until other parents start discussing report cards in the school playground, the errant child’s parents don’t even realize a report was sent home. Nobody observing a digital image that contains hidden information has any idea that a secret is contained within.

However, hiding the existence of information is only very occasionally an advantage. If your bank decides to send you a confidential paper statement, then both you and the bank want to use the traditional postal service to dispatch the letter, sealed in a normal envelope, rather than agreeing on a hiding place where you will need to go to collect the statement. It doesn’t matter, after all, that the mail carrier knows you’re receiving a letter from your bank. What is important is that the mail carrier can’t look inside the protective envelope. Likewise, when you make a call using your mobile phone, you’re not normally worried about keeping secret the fact that you’re making a call. It’s the content of the call that’s confidential.⁴ Similarly, when you purchase goods over the internet, it’s not the fact that you’ve made a purchase that’s confidential, but rather the details of the transaction.

Indeed, in all these cases, hiding the secret information is not only unnecessary but unrealistic. Where would you hide it? When you make a phone call, you want to send only the data encoding your voice, not some other digital object in which the call information could be hidden. Any digital object in which the data could be embedded would need to be much larger than the secret voice data, which would ultimately make the whole process extremely inefficient to conduct.

In general, hiding digital information is not a particularly useful means of providing confidentiality. The study of information-hiding mechanisms is known as steganography, literally “concealed writing.”⁵ Steganography has certain niche applications. A criminal wishing to hide incriminating material on a computer might deploy steganography to prevent anyone from realizing that such data is stored on the machine.⁶ Steganography has uses in the area of digital rights protection, where producers of digital content sometimes use steganography to brand content without visibly degrading the content itself. Steganography is also potentially useful for keeping secrets from any political regime that outlaws the use of confidentiality mechanisms. It’s hard for an authoritarian regime to prosecute someone for keeping secrets when it cannot detect the existence of these secrets in the first place.⁷

Mainly, however, the most useful mechanisms for providing confidentiality are those that keep a secret but do not disguise the fact that the secret exists. This type of confidentiality mechanism can be achieved through cryptography.

Steganography is not cryptography. Indeed, steganography is arguably only really effective as a confidentiality mechanism when the hidden information is itself first protected by cryptography. You use cryptography every day. You rarely, if ever, use steganography.

Cracking Codes

Suppose we have some confidential information we want to send to someone in cyberspace. We have no need to conceal the fact that this information exists; we just want to restrict access to the information itself. Since anyone might be able to observe whatever we send, we need to mask the information in some way. In other words, we need to send the information in disguise.

How do we disguise information? What we need to do is scramble the original information into a form that makes no sense to anyone who observes it. In other words, we need an algorithm.

Let’s look at a very simple example of such an algorithm. Suppose the information we wish to protect consists of letters of the alphabet—for example, TOPSECRET. This is called the plaintext, since it is the “plain” information before being disguised. The algorithm I will use to illustrate this process is the Atbash cipher, which is a method of scrambling letters by reversing the letters of the alphabet.⁸ In other words, each plaintext letter to keep confidential is replaced by the letter in the equivalent position of the alphabet written in reverse: A is replaced by Z, B is replaced by Y, C is replaced by X, and so on. The following table depicts the complete algorithm.

Plaintext

Ciphertext

The Atbash cipher algorithm replaces each letter in the top row of this table with the letter beneath it. Hence, the plaintext TOPSECRET is converted into GLKHVXIVG. This latter sequence of letters, which does not make any apparent sense, is referred to as the ciphertext.

The ciphertext is what we send to the intended recipient of our secret message. Anyone observing this communication sees only GLKHVXIVG. The recipient, knowing that we used the Atbash cipher to convert the plaintext into ciphertext, now uses the reverse algorithm to recover the plaintext. In other words, the recipient replaces each letter in the bottom row by the equivalent letter in the top row. In this way the recipient successfully removes the disguise and reconverts the ciphertext GLKHVXIVG back into the plaintext TOPSECRET.

How effective is the Atbash cipher as a confidentiality mechanism? The Atbash is considered a very weak mechanism for many reasons, but the most significant one relates to my previous observation about making sure that we do not rely on a cryptographic algorithm being kept secret. I argued, in line with Auguste Kerckhoffs, that we should always assume everyone knows which algorithm is being used, even if, in practice, they don’t. Since in this case we are using the Atbash cipher to scramble information, it should be assumed everyone knows that Z replaces A, Y replaces B, and so on. Hence, everyone knows that the ciphertext GLKHVXIVG corresponds to the plaintext TOPSECRET. So much for confidentiality!

The problem with the Atbash cipher is simple. Anyone who knows we’re using it also knows exactly how to convert between plaintext and ciphertext, because there’s only one way of doing so. The Atbash cipher fails to provide confidentiality because there’s no variability in the way it scrambles the data. The real problem with the Atbash cipher is that it’s an algorithm without a key.

Algorithms that scramble information without using a key are often referred to as codes. While the purpose of a code is usually to transform information in some way, the motivation for doing so tends not to be keeping secrets. Arguably the best-known code is Morse code, which replaces letters by short sequences of dots and dashes.⁹ Morse code was designed to convey information by telegraph. The sequences of dots and dashes enable alphanumeric characters to be translated into short and long electromagnetic pulses. This scheme has nothing to do with confidentiality. Indeed, it would be catastrophic if a ship in distress, urgently pulsing the international emergency encoded message “dot dot dot, dash dash dash, dot dot dot” were not able to have this communication successfully decoded by a receiving vessel. This is a ciphertext whose equivalent plaintext everyone needs to understand.

Codes sometimes, misleadingly, appear to provide a veneer of confidentiality. Occasionally, you might be challenged to “crack a code” (indeed, I have lost count of the number of times it has been suggested that my job, as a cryptographer, is to do this). For centuries, Egyptian hieroglyphs presented just such a challenge to scholars researching the history of ancient Egypt. Only in the early nineteenth century did the code behind hieroglyphs once again become understood.¹⁰ Hieroglyphic writing, however, was never designed to provide confidentiality. As ancient Egyptian culture died away, people forgot the details of the algorithm that encoded ideas into hieroglyphs. Rediscovery of this algorithm was all that was necessary to render hieroglyphs meaningful. The ancient Egyptians would surely not have regarded this as a breach of their security.

Another well-publicized code features in the title of Dan Brown’s novel The Da Vinci Code, a book all about secrets, mysteries, and intrigue.¹¹ One of the main protagonists in this novel is a cryptographer, Sophie Neveu, who was allegedly educated at my current place of employment, Royal Holloway, University of London. At the time the book was riding high in the bestseller lists, many different media outlets got in touch, wanting to know more about the cryptography used in the book.

Alas, Sophie Neveu’s excellent training in cryptography seemed wasted, since there is no real cryptography in The Da Vinci Code at all. To unravel the mysteries of the book, Sophie primarily uses her lateral thinking skills to make sense of a number of puzzles. The closest she comes to true cryptography is when she realizes that one of the puzzles consists of ciphertext encoded with the Atbash cipher. Since the Atbash cipher, as you now know just as well as Sophie, doesn’t provide confidentiality, she is instantly able to determine the secret message.

So, codes are algorithms that can be used to disguise information, but normally for reasons other than providing confidentiality. If a security mechanism for providing confidentiality is required, then what is really needed is an algorithm with a key.

Redeeming the Atbash

It’s time to redeem the Atbash cipher. To convert the basic idea behind the Atbash into something more useful, plaintext letters should be scrambled in different ways. In the Atbash cipher, the only way of scrambling is to reverse the letters of the alphabet. Instead, let’s make reversing the letters of the alphabet just one of many different ways in which the plaintext letters can be scrambled. Indeed, ideally, let’s make it one of any ways of scrambling the letters. The result is known as the simple substitution cipher.

The simple substitution cipher is best also considered as a table, except that instead of the second row consisting of the reverse of the letters of the alphabet, it’s a random rearrangement of the letters of the alphabet in which every letter appears once. Just as for the Atbash, the simple substitution cipher algorithm replaces each plaintext letter in the first row with the ciphertext letter beneath it in the second. For example, if the simple substitution cipher is:

Plaintext

Ciphertext

then plaintext TOPSECRET is scrambled into ciphertext PRJWTQUTP. And if the simple substitution cipher is:

Plaintext

Ciphertext

then TOPSECRET becomes XVJBKADKX.

Is this progress? In the Atbash cipher, the scrambling algorithm replaces A by Z, B by Y, and so on. The confidentiality showstopper for the Atbash is that everyone knows the algorithm, and hence knows that plaintext A is replaced by ciphertext Z, and so on. In the preceding simple substitution cipher, the scrambling algorithm replaces A by N, B by R, C by A, and so on. Since it should be assumed that everyone knows the algorithm, is there a difference between this and the Atbash cipher?

There’s an enormous difference! The critical observation is that the scrambling algorithm in the simple substitution cipher of our last example is not: “Replace A by N, B by R, C by A, and so on.” The algorithm, which we assume everyone knows, is: “Replace the letter in the top row of the table by the letter beneath it in the bottom row.” What everyone does not know is the precise table being used. Knowledge of the precise table is what separates those whom we want to understand the plaintext from everyone else. The precise table is the key.

Let’s look at how this works. You want to send a confidential message to your friend, using the simple substitution cipher. You and your friend first need to agree on a secret key. In other words, you and your friend need to agree on a random rearrangement of the letters of the alphabet. Assume that you are able to do this somehow. Suppose you choose the same key in our most recent example—namely, the rearrangement N, R, A, . . . , U, Q, G. If you want to send the plaintext TIMEFORCAKE, then you look up the table, replacing letters in the top row by letters in the bottom row, to obtain ciphertext XOYKIVDANTK. You send XOYKIVDANTK to your friend, who uses the same table to recover the plaintext TIMEFORCAKE.

Now, let’s consider the perspective of an attacker, someone who wants to learn the secret messages. Assume that the attacker knows the algorithm, is thus aware that you’re using the simple substitution cipher, and is able to observe any ciphertext you send. Had you been using the Atbash, on seeing XOYKIVDANTK the attacker would immediately be able to work out the plaintext. However, you’re using the simple substitution cipher, so all the attacker knows is that the plaintext letters are being jumbled up by means of an unknown rearrangement of the letters of the alphabet. The ciphertext letter X could have replaced any plaintext letter of the alphabet, the letter O could represent any plaintext letter, so could the letter Y, and so on.

How hopeless is the attacker’s situation? Well, there is always one option open to the attacker: although they don’t know the key, they could try to guess it. Since the key was chosen randomly, the attacker needs to guess a random rearrangement of the letters of the alphabet and hope to get lucky. To find the odds of success, it’s necessary to first determine how many random rearrangements there are of 26 letters. This is quite easy to calculate. The first letter can be any of the 26 letters, so there are 26 options. The second letter can be any letter other than the one chosen as the first letter, so there are 25 possibilities. Hence, there are 26 × 25 = 650 choices for the combination of the first two letters. The third letter can be any letter other than those chosen as the first and second letters, so there are 24 choices. There are thus 26 × 25 × 24 = 15,600 possibilities for the combination of the first three letters. And so on.

There are, ultimately: 26 × 25 × 24 × 23 × 22 × 21 × 20 × 19 × 18 × 17 × 16 × 15 × 14 × 13 × 12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 403,291,461,126,605,635,584,000,000 possible rearrangements of 26 letters. How big is this number? You can save data entry time on your calculator by typing “26” and looking for a button with the! symbol (referred to as the factorial function). If you have a cheap calculator, this request will probably blow the calculator’s mind and it will return an error message, indicating that the answer is too large to handle. If you own a slightly more sophisticated calculator, it will indicate that 26 factorial is something enormous. What it won’t tell you is that the answer equates to 40,000 times the number of stars in our universe. Put simply, guessing which of the 26-factorial possible secrets was chosen by you and your friend is a lost cause that the attacker should not waste time pursuing.

The Atbash cipher is just one of the 26-factorial possible instantiations of the simple substitution cipher. If you choose your key randomly, then it is very unlikely you will end up using the Atbash cipher—just as unlikely as ending up with either of the other two key tables described earlier. And each of these keys is just as unlikely as the chances of selecting one specific star from 40,000 times the number of stars in the universe. Even if, by an unbelievably rare chance, you did end up with the key corresponding to the Atbash cipher, this scenario is so mind-bogglingly unlikely that the attacker will never guess it happened.

Seen from this perspective, the simple substitution cipher seems to provide confidentiality. But before you rush off to use this cipher to safeguard secrets on your computer, a word of caution: while the simple substitution cipher does indeed have 26 factorial keys, the level of confidentiality it provides is severely limited. The reason is that there is a much easier way for an attacker to determine plaintext from ciphertext than guessing the key. For now, just accept that, unlike steganography and codes such as the Atbash cipher, the simple substitution cipher is a genuine (albeit flawed) example of a cryptographic security mechanism for providing confidentiality.

Encryption

The process of providing confidentiality using a cryptographic security mechanism is known as encryption. Any mechanism for providing encryption includes an encryption algorithm, which defines the basic process by which plaintext is scrambled, and a key, which provides the means of varying the way encryption is performed. The encryption algorithm takes as input both the plaintext and the key, and defines a process that eventually outputs the ciphertext. In the case of the simple substitution cipher, the encryption algorithm is the process of replacing letters in the top row of the table by letters in the bottom row, and the key is the random rearrangement making up the second row of the table.

The process of reversing encryption is known as decryption. In decryption, the ciphertext and a key are input into a decryption algorithm, which outputs the plaintext. The decryption algorithm is the process reversing the effect of the encryption algorithm. The decryption algorithm for the simple substitution cipher is the replacing of the bottom letter by the top letter in the table. The encryption algorithm and decryption algorithm are so intimately related to one another that it’s common to refer to just the encryption algorithm, leaving the decryption algorithm implied.

Encryption is an extremely important security mechanism for a number of reasons. For one thing, encryption is the security mechanism that cryptography has provided for the longest time. Indeed, historical uses of cryptography by the likes of Julius Caesar, Mary, Queen of Scots, and Napoleon were only to provide confidentiality by means of encryption. The world wars of the twentieth century, and the subsequent Cold War, all heavily relied on the use of encryption to provide confidentiality for clandestine communications.

Encryption is used widely in modern applications. If you have done any of the following today, then you have used encryption: made a mobile phone call, withdrawn money from an ATM, connected to Wi-Fi, bought something from a website, used a virtual private network to access your work computers from home, watched pay-per-view television, sent a message using WhatsApp, and so on.

While encryption is perhaps the most attention-grabbing use of cryptography, it is worth reminding ourselves that it provides only confidentiality. Nowadays, encryption is rarely used without being accompanied by cryptographic security mechanisms that provide additional security properties. For example, encryption of a mobile phone call happens only after cryptography has been used to identify the SIM card on the mobile phone. Encryption of bank card transactions takes place only when accompanied by the use of cryptography to make sure the messages being encrypted have not been modified in transit.

To see why encryption of a plaintext message does not provide guarantees that the received plaintext is the one the sender intended to protect, let’s again consider the simple substitution cipher. In one of our previous examples, the plaintext TOPSECRET was encrypted into the ciphertext XVJBKADKX. This process prevents an attacker who observes XVJBKADKX from knowing the meaning of the underlying plaintext.

However, there is nothing stopping the attacker from modifying this ciphertext before it reaches the intended recipient. The attacker could, for example, change one of the letters in the ciphertext. If they changed the first letter from X to J, then the receiver would decrypt this to the plaintext POPSECRET. Has there been a mistake? How will the receiver know? (Perhaps POPSECRET refers to the mysterious ingredient behind the recipe for Coca-Cola!) Even though the attacker does not know precisely what impact the change to the ciphertext has made, the receiver cannot be sure the plaintext they decrypt is correct.¹²

Vanilla Encryption

Returning to our security mechanisms of the physical world for a moment, in some ways encryption is a bit like the digital equivalent of locking written information inside a box. The encryption (and decryption) algorithm is the digital version of the locking mechanism itself, and the cryptographic key is the digital version of the physical key.

Importantly, there are different kinds of physical locks. The most common type of lock is one that requires the same key to both lock and unlock the box. Analogously, the default (or vanilla) type of encryption is one in which the key used to encrypt plaintext into ciphertext is the same as the key used to decrypt ciphertext into plaintext. The simple substitution cipher works in precisely this way, with the key required to encrypt and decrypt being the random rearrangement represented in the bottom row of the table. An encryption algorithm in which the same key is used to both encrypt and decrypt is described as being symmetric.

It might at first seem natural for encryption to be symmetric. Intuitively, any other keying relationship does not appear to make any sense. How can plaintext encrypted using one key be decrypted using another? However, recall that physical locks are not always symmetric. In particular, pin tumbler locks (of the type often associated with the manufacturer Yale) and padlocks are typically not locked by applying a key at all. These locks are normally just snapped shut. A key is necessary only for unlocking these locks. Fascinatingly, and significantly, there are cryptographic equivalents of pin tumbler locks and padlocks. Encryption mechanisms in which different keys are used for encryption and decryption are referred to as being asymmetric.

Until the 1970s, all encryption mechanisms were symmetric. What do Julius Caesar, Mary, Queen of Scots, and Napoleon have in common? They all only ever used symmetric encryption. Even Alan Turing, one of the people whose genius is most associated with the influential role that cryptography played during the Second World War, would possibly have regarded the idea of asymmetric encryption as a bizarre impossibility.¹³

Today, symmetric encryption remains by far the most common type of encryption. You use symmetric encryption when you encrypt all the data on your laptop. You use symmetric encryption when you use Bluetooth. You use symmetric encryption when you use all our favorite previous examples of everyday encryption: Wi-Fi, mobile phones, banking, internet shopping, and so on. In fact, whenever you want to protect data in the form of documents, spreadsheets, web forms, email, voice traffic, and the like, it is symmetric encryption you use to provide confidentiality. Most encryption is symmetric encryption. In fact, all encryption would be symmetric encryption if it weren’t for a small problem, which I’ll explain in a moment.

The algorithms used to provide symmetric encryption have evolved over time, as knowledge of how to design (and break) good encryption algorithms has improved. This progress has been by no means gradual, with knowledge moving forward in bursts, rather than incrementally.

The symmetric encryption algorithm known as the Vigenère cipher was invented in the mid-sixteenth century but was still being used during the American Civil War. It was eventually shown to be fallible to statistical analysis techniques developed in the latter half of the nineteenth century.¹⁴

The electromechanical Enigma machines implemented symmetric encryption algorithms based on electrical contact pins connected to sequences of rotors. These were used for much of the first half of the twentieth century, most famously during the Second World War.¹⁵ The effectiveness of Enigma machines as symmetric encryption mechanisms was swept aside by the communication revolution caused by the development of digital computers after the war.

Prior to the early 1970s, the main users of symmetric encryption were those with the most serious secrets to keep—namely, governments and military organizations. All this changed in the 1970s, with the arrival of commercial computing. It became apparent that there was a business need for symmetric encryption, particularly in the financial sector. At that time, and possibly to an extent today, secret organizations preferred to use secret encryption algorithms, so commercial encryption required a new and open form of symmetric encryption that everyone could use.

In 1977 the US government published a symmetric encryption algorithm called the Data Encryption Standard, better known to its many friends as DES.¹⁶ This was a truly extraordinary moment in the history of cryptography, as it marked the passing of cryptography as a largely secret business into a subject very much in the public eye. A standard is something that experts have evaluated and approved for widespread use. The establishment of an encryption standard was unprecedented and facilitated the use of DES by commercial organizations in the United States, and de facto in many other countries around the world. We now had a symmetric encryption algorithm that ordinary members of the public might interact with as part of their day-to-day lives, albeit sometimes inadvertently.

During the last two decades of the twentieth century, anyone using symmetric encryption to provide confidentiality of data was most likely to be using DES. An exception was any application requiring especially fast encryption of real-time traffic, such as voice data. Symmetric encryption in such environments is often accomplished by special encryption algorithms known as stream ciphers, which encrypt each bit of the plaintext data individually and immediately. Stream ciphers are symmetric encryption algorithms optimized for speed and efficiency. In contrast, DES is an example of a much more general class of symmetric encryption algorithms known as block ciphers, because they process data in chunks (blocks) of bits at a time.

By the late twentieth century, DES was no longer deemed an effective symmetric encryption algorithm, mainly because computing power had steadily increased to the point that DES no longer provided sufficient security. However, DES is such an influential encryption algorithm that it has become embedded in many systems to an extent that removing it completely from some remains hard. There is a decent chance that you have indirectly used a form of DES in the last few days to encrypt some data, especially if you have paid for anything with a bank card.

Made in Belgium

Modern symmetric encryption enlists a range of different symmetric encryption algorithms. The banking networks still heavily rely on DES, but, recognizing that a single application of DES is no longer regarded as secure enough, they tend to encrypt data three separate times by means of an extension of the basic DES encryption algorithm known as Triple DES.¹⁷ Increasingly, however, applications requiring symmetric encryption use a block cipher known as the Advanced Encryption Standard, or AES.¹⁸

The AES represents yet another milestone in the history of cryptography. In the mid-1990s, it was widely recognized that a new symmetric encryption algorithm was required that could be recommended for use by the increasingly wide range of applications requiring confidentiality.

Several significant changes had occurred in the world of cryptography between the 1970s, when DES was designed, and the 1990s. One was the rise of the internet and the World Wide Web, both of which had increased demand for conducting business, and indeed everyday life, in cyberspace. At the same time there was an increase in the diversity of technologies connecting to cyberspace. When DES was developed, symmetric encryption was intended primarily for dedicated computers within the likes of banking networks, so the design of DES was specifically tailored for implementation on hardware. By the 1990s, there was a demand not just for symmetric encryption in hardware but also for symmetric encryption that could be implemented efficiently in software. There was also a greater range of hardware platforms requiring symmetric encryption. In the 1970s all computers were fairly similar. By the 1990s, there was a requirement for cryptography on both supercomputers and tiny devices such as smartcards (plastic cards with an embedded chip like your credit card).

Another significant change was in cryptographic expertise. In the 1970s, most cryptographers worked for governments or military organizations. Indeed, knowledge of cryptography was largely confined to employees in these sectors. The US government turned to IBM, one of the few commercial companies with an interest in cryptography in the 1970s, for the design of DES. By the 1990s, there was a flourishing community of cryptographers in both academia and the private sector, particularly in telecommunications companies, who were building commercial empires that relied on the effectiveness of cryptography.

The US National Institute of Standards and Technology (NIST) was the agency tasked with procuring a new symmetric encryption algorithm standard fit for the twenty-first century. NIST decided to harness the cryptographic community outside of government by holding an open competition for the design of the new AES algorithm. Recognizing that this new symmetric encryption algorithm would find its way into products all over the world, the AES competition permitted international entries, not just designs from the United States.¹⁹

This was a radically new approach to designing cryptographic algorithms, and most of the leading experts in symmetric encryption engaged with the competition. My only personal contribution to this process was trying to persuade my Belgian office colleague Vincent Rijmen to rename the candidate algorithm he had co-designed with friend Joan Daemen. I couldn’t believe that any algorithm with the name Rijndael, crafted from a merger of the inventors’ surnames and the fictional valley of Rivendell, could possibly be taken seriously. I was ignored, but the algorithm wasn’t. In 2001, the Belgian symmetric encryption algorithm Rijndael became the AES.

The AES is elegantly simple in its design—a feature that makes it efficient to implement and that played a significant role in Rijndael’s selection as the competition winner. You might imagine that contemporary encryption algorithms need to be mathematically sophisticated, well beyond the comprehension of nonexperts. It’s true that the precise algorithm design details are subtle and require expertise to appreciate, but you might be surprised to discover that the basic idea behind the AES is quite accessible. In order to demystify modern encryption somewhat, I will try to explain (roughly) how AES encryption works.

Recall that an encryption algorithm is a recipe that takes two core ingredients—namely, some plaintext and a key—and mixes them up to produce a ciphertext. The AES algorithm conducts this scrambling operation as follows:

Format the plaintext. The plaintext is first converted into bytes. The first 16 bytes are then arranged into a 4×4 square (4 bytes by 4 bytes).²⁰ If there is more plaintext to encrypt, then a second square is formed, then a third, and so on. If there’s not enough plaintext to complete a 4×4 square of bytes, then the square is filled with redundant information known as padding. The plaintext is now ready to encrypt.

Change all the bytes. The first step in mixing up the plaintext is to replace each byte in the square with a new byte that is determined by rules specified as part of the AES algorithm, so that everyone knows how to do this. At the end of this step, a new square of 16 bytes has been formed.

Slide the rows. This second mixing step couldn’t be simpler. Each row of the square is shifted along a specified number of positions, with entries that drop off the right end of the row being reinserted back into the left end.

Transform the columns. The 4 bytes of each column are now transformed according to another mixing rule specified by the AES algorithm. Each result is a new column, again consisting of 4 bytes. The overall result is a new square of 16 bytes.

Add the key. Each of the previous steps jumbles the plaintext in a different way, not unlike the way a dealer uses a mix of techniques to shuffle a deck of cards. The key, however, has not yet been mixed into the process. To do so, the AES algorithm specifies how to take the key and define from it a separate 4×4 square of 16 bytes known as a subkey. The square of mixed-up plaintext bytes is now added to the subkey square to form yet another square of 16 bytes.

Do it all again. Once a square of bytes that is a blend of the plaintext and the key has been produced, the button on the blender can be pressed again. The latest square of 16 bytes is inserted back into the “Change all the bytes” step, and the entire process is repeated (Change all the bytes, Slide the rows, Transform the columns, Add the key). And Do it all again, until the AES specifies that everything has been mixed enough. For the most basic version of AES (there are three versions, each with a different length of key), this process is repeated ten times. Each pass through these different mixing operations is known as one round of AES.

Output the ciphertext. The final 4×4 square of bytes is our ciphertext.

To decrypt ciphertext back into plaintext, the entire process is performed in reverse.

This is the idea anyway. I’ve left out a few subtleties, and spared you some details. The reason for spelling out the core idea behind AES is to show that, at its heart, the AES encryption algorithm consists of a series of relatively simple operations, the combined effect of which produces a ciphertext that preserves the confidentiality of the plaintext. Hopefully you agree that AES has a simple, even elegant, design. You should not, however, even for a moment, think that coming up with an encryption algorithm such as the AES is easy.²¹

The AES is used to provide confidentiality in many modern technologies. For example, you probably use it whenever you make a secure connection from your web browser to a website (of course, you don’t personally choose to use the AES; your web browser does this for you). The AES has been so well studied and evaluated that it is likely we’ll continue to keep secrets by sliding rows and transforming columns for the foreseeable future.

If anyone asks you what Belgium is famous for, now you know. Frites, beer, chocolate, and fictional detectives are fine, but Belgium should be better known for its cryptography.

The Ubiquitous Block Cipher

The AES is not the only block cipher available today for symmetric encryption. A considerable number of block ciphers have been proposed over the years, including some excellent competition finalists that narrowly missed selection as the AES. There are block ciphers named after animals, Norse gods, Belgian beers, and the downright obscure (everyone’s favorite is the Hasty Pudding cipher). There are an astonishing number of block ciphers named after fish.²² However, only a few of these block ciphers are ever deployed in real products, and the AES is arguably the most important of these.

One of the reasons block ciphers are the most common mechanisms for conducting symmetric encryption is that they are so flexible in how they can be implemented. Recall that a block cipher encrypts a block (a group of bits, with 128 bits being a typical group size) of plaintext into a block of ciphertext. We often want to encrypt more than 128 bits, since 128 bits represents only about 16 characters of text. Encrypting longer plaintext by first chopping it up into blocks, and then encrypting each block separately, is not a wise idea.

The main problem is that recurrences of the same plaintext block will always encrypt using a specific encryption key into the same ciphertext block. A commonly occurring plaintext block might thus become recognizable to an attacker who analyzes the frequency of occurrence of ciphertext blocks. Worse, if an attacker somehow discovers the plaintext corresponding to a particular ciphertext block, any subsequent occurrence of that ciphertext block will immediately reveal to the attacker that the known plaintext has been sent again.

To counter this risk, more sophisticated methods exist for encrypting plaintexts of more than one block. These modes of operation of a block cipher link together the encryptions of separate blocks in different ways. In doing so, modes of operation enable a block cipher such as AES to achieve different properties, beyond just providing confidentiality. For example, some modes of operation remove the need for padding the final block, other modes enable the detection of changes to the ciphertext, and there are modes of operation specifically tailored for particular applications, such as encrypting hard drives. Indeed, in many applications more suited to the use of a stream cipher, encryption is performed by a block cipher deployed in a special mode of operation that effectively converts it into a stream cipher.²³

Symmetric encryption is the most common cryptographic means of providing confidentiality, block ciphers are the most widely deployed symmetric encryption mechanisms, and AES is by far the most used block cipher. Consequently, we heavily rely on AES for security in cyberspace.

Does the ubiquity of AES create a problem? After all, biodiverse ecosystems tend to be the healthiest, and reliance on single genetic strains of food crops can have disastrous consequences. Should there not be greater cryptodiversity?

To some extent, reliance on AES is a gamble, but it’s a defensible one. Although there will never be an absolute guarantee that AES is secure, a standardized cryptographic algorithm such as AES is scrutinized much more than any other block cipher. As a result, as time goes by without anyone reporting a problem, confidence in AES increases.

There are occasions in life when there is a case for demonstrating individual flair, such as choosing what to wear to a party, or deciding how to decorate a room. When purchasing something purely functional, however, such as a dishwasher, going with a reliable brand and model trumps high fashion any day. In this respect, encryption mechanisms are much more like a dishwasher than like a ball gown. If, one day, an unexpected critical flaw is discovered in AES, then it will be in the whole world’s interest to act swiftly to do something about it. Using a less fashionable block cipher might expose you less to this particular danger, but it runs the greater risk that your less scrutinized block cipher is not as secure as you hoped it might be.

The Key-Distribution Problem

Symmetric encryption is a wonderful tool, which we use all the time to keep secrets in cyberspace. However, there is an obvious catch involved with using symmetric encryption. Anyone who scrambles plaintext into ciphertext needs a secret key. But anyone who wishes to unscramble this ciphertext back into plaintext also needs this same secret key. Symmetric encryption works, as long as, somehow, everyone who needs the secret key can get hold of it.

But how is this distribution of secrets accomplished? We can’t simply send someone a secret key whenever one is needed, by any old means, because secret keys (by definition) are themselves secrets. Most communication channels in cyberspace, such as the internet, are easy for an attacker to access. What do we normally do when we need to send someone a secret in cyberspace? We encrypt it, of course! And before we encrypt anything, we need . . . a key. You heard right. To send someone a key, we first need a key. It’s a sort of cryptographic version of the chicken-or-the-egg dilemma.²⁴

When we use keys in the physical world, we rarely have significant problems transporting the keys to where they are required. When we lock something, we are often the ones who need to unlock it later, in which case the keys don’t need to go anywhere other than our own pockets. We don’t tend to send one another secret messages in locked boxes, so we never have to worry about how someone else is going to get hold of the key to unlock such a box. In other words, we don’t come across the significant key-distribution problem that users of symmetric encryption face.

Symmetric encryption keys are not always difficult to distribute. In the physical world, on the rare occasion when we need to give someone else a physical key, we normally rely on physical proximity to do so. If you want to lend a visitor your front-door key, you just hand it to them when you meet. If for some reason a meeting is not possible, you leave the key somewhere nearby (say, underneath a flowerpot).

Likewise, some applications of symmetric encryption rely on physical proximity to distribute keys. A good example is a home Wi-Fi network. All devices connecting to Wi-Fi have their connections to the Wi-Fi protected by symmetric encryption. The critical information needed to create the key used to encrypt traffic is the master key used to access the Wi-Fi network. The owner of the network should be able to generate this master key. While the owner has often written the critical password on a piece of paper (which they usually can’t find when you ask for it), the password is often more reliably found printed on the box controlling the Wi-Fi network. Any new device wanting to join the network and use symmetric encryption needs to be supplied with this password. This master key can either be typed into the device manually, or it can be installed automatically if the new device is brought physically close to the Wi-Fi box. Both solutions are workable because any device connecting to the Wi-Fi needs to be in close proximity to the box (or the owner).²⁵

In the physical world, sometimes we need a new physical key for something. We usually collect new keys from a “trusted party,” meaning someone with whom we have at least a business relationship. For example, we normally obtain the key to a new house from the real-estate agent (whether we fully trust real-estate agents is a moot point). Likewise, we collect the key to a new car from the sales center, which we trust enough that we hand over cash for wheels. Many real-world applications of symmetric encryption to protect secrets rely on the use of a trusted party of some sort to support the distribution of keys. We get the symmetric key for our credit card directly from our bank when we’re sent the card. We receive the symmetric key on the SIM card of our mobile phone either directly from the mobile-network operator, or indirectly from an agent selling contracts on the operator’s behalf. Notably, in both examples we obtain encryption keys well in advance of the time we need to use them.

However, sometimes in cyberspace we need to do something we are rarely required to do with locks and keys in the physical world. In cyberspace, we often need to use locks and keys to share secrets with a stranger. As a concrete example, suppose you decide to purchase a widget from an online store you have never previously visited. Because you want the payment details to be kept confidential from the outside world, you have a sudden need for a cryptographic key. You are not close to the store, so you can’t just stop by to agree on a key. Nor do you and the store necessarily have any prior business relationship, during which you could have previously agreed on a key (for example, the store could have equipped you with a loyalty card with a key on the chip). Worse, you want to buy the widget now and are probably unwilling to wait for a key to be delivered by some (expensive) physical means.

Sharing a secret with a stranger at first appears an impossible problem to solve. But, like many seemingly impossible problems, cryptography can be used to solve it. To do so, however, a radically different type of encryption is required.