Introduction
Relevant readings: Katz and Lindell 1.1–1.4
What is cryptography?
A dictionary definition for cryptography would say something like “the art of writing and solving codes.” Historically, cryptography focused exclusively on ensuring private communication between two parties sharing secret information in advance using codes. It was seen as an art, in the sense that it required a lot of creativity to come up with good codes or break existing ones. This is what we refer to as classical cryptography.
Modern cryptography, on the other hand, has grown to be much more than merely what the dictionary definition portrays it to be. In addition to encryption, security mechanisms such as for integrity, key exchange, and authentication now become of interest. It is now seen as more of a science than an art, due to a “rich theory” emerged in the 1970s that allowed the rigorous study of cryptography as its own discipline. In summary:
-
Classical cryptography concerns about hidden writing, while
-
Modern cryptography concerns about provable security.
Setting the scene
Much of classical cryptography is concerned with designing codes, which we call today as cryptosystems or encryption schemes. Classical cryptosystems rely on the security of the key that is shared by both parties in advance, in which case we call this as the private-key setting.
To make this scenario more concrete, we will introduce some people. Let’s say Alice wants to send a message \(m\) privately to Bob. We call \(m\) the plaintext. Of course Alice won’t send the actual \(m\), but she will transform the plaintext into a value \(c\) (called the ciphertext), and send that \(c\) to Bob. This process is called encryption, and it is usually done by running an encryption algorithm called . Upon receiving \(c\) from Alice, Bob then runs the decryption algorithm to recover the original plaintext \(m\).
Additionally, we assume that an eavesdropper named Eve can observe the ciphertext \(c\), so the goal is for the ciphertext to be meaningless to everyone else except for Bob.
Using generic descriptions for parties such as “first person,” “receiver,” or “eavesdropper,” gets cumbersome really quick, so we use names such as Alice and Bob (and many others) to explain cryptographic mechanisms more clearly. In fact, they were introduced with the publication of the original paper describing the RSA cryptosystem in the 1980s, so these names became pretty much standardized across all cryptographic literature.
The encryption syntax
A private-key encryption scheme \(\Pi\) is defined by specifying a message space \(\mathcal{M}\) along with three algorithms: a procedure for generating keys (\(\GEN{}\)), a procedure for encrypting (\(\ENC{}\)), and a procedure for decrypting (\(\DEC{}\)). These algorithms are more formally defined as follows:
-
The key-generation algorithm \(\GEN{}\) is a randomized algorithm that outputs a key \(k\) chosen according to some distribution.
-
The encryption algorithm \(\ENC{}\) takes as input a key \(k\) and a message \(m\) and outputs a ciphertext \(c\). We denote the encryption of the plaintext \(m\) using the key \(k\) by \(\Enc{k}{m}\).
-
The decryption algorithm \(\DEC{}\) takes as input a key \(k\) and a ciphertext \(c\) and outputs a plaintext \(m\). We denote the decryption of the ciphertext \(c\) using the key \(k\) by \(\Dec{k}{c}\).
We call the set of all possible keys that can be produced by the key-generation algorithm as the key space, denoted by \(\mathcal{K}\). We can assume that uniformly chooses a key from the key space.
For an encryption scheme to work properly, encrypting a message and then decrypting the resulting ciphertext using the same key should yield the original message, so: $$\Dec{k}{\Enc{k}{m}} = m$$ for every key \(k \in \mathcal{K}\) and every message \(m \in \mathcal{M}\).
Kerckhoffs’ principle
If Eve gets a hold of the decryption algorithm \(\DEC{}\) and the key \(k\), then it’s game over. Thus it makes sense to ensure that the key is being shared securely and completely hidden from everyone else. While we’re at it, why not make \(\DEC{}\) (and maybe \(\ENC{}\)) also completely hidden?
This was the way cryptography was being done in the past 2000 years or so, but it turns out that it would be a very bad idea! In the 19th century, Auguste Kerckhoffs laid down some design principles for military ciphers, but one in particular is still very relevant today, which is now known as Kerckhoffs’ principle:
The cipher method must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience.
In other words, the security of a cryptosystem must not rely on the secrecy of its underlying algorithms; rather, the security should only rely on the secrecy of the key. That way only the key needs to be changed, and not the encryption or decryption algorithms (which are way more difficult to replace), as it is easier to change the key than to change the algorithm.
This principle is in stark contrast to the security by obscurity principle, where the security of the system is entirely dependent on the secrecy of the algorithms, and was pretty much the norm before modern cryptography. Fortunately, this principle fell out of favor when cryptographers started advocating for a more transparent approach in the cryptographic design process, so all those “proprietary” and “home-brewed” algorithms were made obsolete by their more open and “field-tested” counterparts. This is why cryptographers (the people who build) usually use the help of cryptanalysts (the people who break) in order to analyze the security of a construction. (Although cryptographers are often cryptanalysts themselves and vice versa.)
What is not cryptography?
Cryptography does not hide the fact that a secret message is being sent, and so it does not make the effort of hiding the entire communication channel. Doing so is called steganography.
Cryptography is not about making text or data “human-unreadable.” People use many techniques to try to “hide” information, namely by using encoding and decoding methods like Base64, hexadecimal, or binary strings.
| Plaintext: | this is not encrypted |
| Base64-encoded: | dGhpcyBpcyBub3QgZW5jcnlwdGVkCg== |
| Hex-encoded: | 74686973206973206e6f7420656e637279707465640a |
| Binary-encoded | 01110100 01101000 01101001 01110011 00100000 01101001 |
01110011 00100000 01101110 01101111 01110100 00100000 | |
01100101 01101110 01100011 01110010 01111001 01110000 | |
01110100 01100101 01100100 00001010 |
Such encoding methods are useful for representing binary data into a format that only supports a limited set of characters, and since it does not involve secret information (like a key), then it adds nothing in terms of security. These might look very different to humans, but to a computer, these are all the same. In short, writing something in Base64/hex/binary is not a security measure!
A word of warning (adapted from (Wong 2021))
The art of cryptography is difficult to master. It would be unwise to assume that you can build complex cryptographic protocols once you’re done with this course. This journey should enlighten you, show you what is possible, and show you how things work, but it will not make you a master of cryptography.
Do not go alone on a real adventure. Dragons can kill, and you need some support to accompany you in order to defeat them. In other words, cryptography is complicated, and this course does not permit you to abuse what you learn. To build complex systems, experts who have studied their trade for years are required. Instead, what you will learn is to recognize when cryptography should be used, or, if something seems fishy, what cryptographic primitives and protocols are available to solve the issues you’re facing, and how all these cryptographic algorithms work under the surface.
Principles of modern cryptography
Modern cryptography puts great emphasis on definitions, assumptions, and proofs.
Security definitions
Formal definitions of security are essential in the entire cryptographic design process. To put it simply,
If you don’t understand what you want to achieve, how can you possibly know when (or if) you have achieved it?
Formal definitions provide such understanding by giving a clear description of what threats are in scope and what security guarantees are desired.
In general, a security definition consists of:
-
a security guarantee that defines what the scheme is intended to prevent the attacker from doing, and
-
a threat model that describes the assumptions about the attacker’s (real-world) abilities.
Let’s consider what would a security definition look like for encryption.
Attempt 1: “It should be impossible for an attacker to recover the key.”
Suppose we have an encryption scheme where \(\Enc{k}{m} = m\). You can easily see that the resulting ciphertext does not leak the key in any way, and yet this scheme is blatantly insecure because the message is sent in the clear!
Thus we conclude that the inability to recover the key is necessary but not sufficient for security.
Attempt 2: “It should be impossible for an attacker to recover the plaintext from the ciphertext.”
A bit better, but a definition like this would also consider an encryption scheme that leaks 90% of the plaintext in the ciphertext to be secure. For real-life applications, especially those dealing with personal information, this encryption scheme would be problematic.
Attempt 3: “It should be impossible for an attacker to recover any character of the plaintext from the ciphertext.”
Close, but not good enough. This definition is “too weak” because it considers an encryption scheme secure if, for example, it reveals whether or not a person lives in a certain ZIP code area even if the full address is kept secret, which clearly we don’t want.
On the other hand, this definition is “too strong” because we cannot
rule out the chance that the attacker correctly guesses (through
sheer luck or prior information) that most letters always begin with
“Dear …” or that the last digit of your phone number is a 1. That
alone should not render an encryption scheme insecure, so the
definition should rule out those instances as successful attacks.
Attempt 4: “Regardless of any information an attacker already has, a ciphertext should leak no additional information about the underlying plaintext.”
This is the “right” approach as it addresses out previous concerns. All that’s missing is a precise mathematical formulation of this definition, which we’ll do later.
In the context of encryption, the different threat models are (sorted by increasing power of the attacker):
-
Ciphertext-only attack (COA)
The adversary observes one or more ciphertexts and attempts to determine information about the underlying plaintext(s).
-
Known-plaintext attack (KPA)
The adversary gets a hold of one or more plaintext-ciphertext pairs generated using some key, and then tries to deduce information about the underlying plaintext of some other ciphertext produced using the same key.
All historical ciphers are trivially broken by a known-plaintext attack (a notable example would be how the Enigma machine was broken).
-
Chosen-plaintext attack (CPA)
The adversary gets a hold of one or more plaintext-ciphertext pairs generated for plaintexts of their choice.
-
Chosen-ciphertext attack (CCA)
The adversary is able to obtain (at the very least, some information about) the decryption of ciphertexts of their choice, and then tries to deduce information about the underlying plaintext of some other ciphertext (whose decryption they cannot get a hold directly) produced using the same key.
Take note that none of them is better than the other, and the right one to use depends on the environment in which an encryption scheme is deployed and which captures the attacker’s true abilities.
Precise assumptions
Modern cryptography is like a “house of cards,” where proofs of security heavily rely on assumptions, most of them are unproven assumptions. This is because most modern cryptographic constructions cannot be proven secure unconditionally because proving them would entail proving one of many unsolved problems in the field of computational complexity theory (notably the \(\P\) vs. \(\NP\) problem). As such, modern cryptography requires any such assumptions to be made explicit and mathematically precise.
Proofs of security
Proofs of security give an iron-clad guarantee that no attacker will succeed, relative to the definition and assumptions. From experience, intuition is often misleading in cryptography, and can be outright disastrous. What we initially believe to be an “intuitively secure” scheme may actually be badly broken. For example, the Vigenère cipher was considered unbreakable for many centuries, until it was entirely broken in the 19th century.
References
- Wong, David. 2021. Real-World Cryptography. Manning Publications.