Pseudorandom functions and chosen-plaintext attacks – Encryption and Decryption
4.5.3 Pseudorandom functions and chosen-plaintext attacks
Being secure against passive eavesdropping is oftentimes not enough in practice. Encryption schemes must also be secure against so-called chosen-plaintext attacks. In a nutshell, a chosen-plaintext attack describes the situation where Eve can ask Alice or Bob to encrypt multiple messages of Eve’s choice, and do so in an adaptive manner. That means Alice is made to encrypt specific plaintext messages based on the ciphertexts that resulted from the encryption before. Cryptographers refer to such a setting as an oracle (in our case, an encryption oracle).
The practical relevance of chosen-plaintext attacks is due to the fact that many modern systems interact with users who, in turn, determine what data is being processed or transmitted by these systems. For example, web servers send and receive information based on external requests by users accessing these web servers. In a real-life attack, malicious JavaScript loaded from Mallory’s server can induce Eve’s browser to repeatedly resume a previous TLS session with Bob’s server, thereby sending encrypted session cookies to Bob.
When trying to defend encryption schemes against chosen-plaintext attacks, we are using so-called pseudorandom functions. According to the Encyclopedia of Cryptography and Security [95], ”A pseudorandom function is a deterministic function of a key and an input that is indistinguishable from a truly random function of the input”.
This means we are looking at a function F that has two input parameters: K (the key) and a second input x (the data variable). At first sight, this looks a lot like the encryption functions from Section 4.2. But here, we are not interested in the confidentiality of x, but in the output FK(x), which should look random for any random choice of K and any input x, that is: the function FK should not be distinguishable from some truly random function g having the same domain and co-domain as FK.
It can be mathematically shown that pseudorandom functions exist if and only if pseudorandom generators exist. As a result, pseudorandom functions are built using the same hard mathematical problems that pseudorandom generators are based on.
Equipped with a pseudorandom function, we can now build an encryption scheme shown in Figure 4.13 that is computationally secure against chosen-plaintext attacks. The pseudorandom function F takes a key K and, for every new message m, a fresh value r as inputs, and outputs a pseudorandom string k, the equivalent of the pad in the original one-time pad scheme. It is important that the r− values do not repeat, that is, they should be so called nonces (numbers used once). In principle, nonces can be generated using simple counters, but other constructions are also possible. Finally, the plaintext message m is encrypted using the XOR operation with k to obtain the ciphertext c. Because the nonces are not allowed to repeat, the string k (essentially, the pad) is independent from the pads used in previous encryptions.
Figure 4.13: Encryption scheme secure against chosen-plaintext attacks
Because a fresh value of r is used for every new message m, the encryption scheme in Figure 4.13 is probabilistic: encrypting the same message m twice will result in two completely different ciphertexts (as long as r is not reused). Therefore, it is not possible for an attacker to predict what the next ciphertext will look like.
4.6 Summary
In this chapter, we covered a lot of ground. With the goal of confidentiality in mind, we have formally defined symmetric cryptosystems and have seen that perfectly secure cryptosystems do exist. Inspired by the prime example of a perfectly secure cipher, the one-time pad, we looked for less expensive ways to achieve a desired level of security. This led us to weaken the concepts of perfect security and true randomness and to look at computational security and pseudorandomness instead. These concepts will be important tools in what’s to follow.
In the next chapter, we will look at another important security objective from the CIA triad, namely authentication.