We’ve now compiled all the tools that are needed for the basic goal of cryptography (which is still being subverted quite often) allowing Alice and Bob to exchange messages assuring their integrity and confidentiality over a channel that is observed or controlled by an adversary. Our tools for achieving this goal are:

The notions of security we require from these building blocks can vary as well. For encryption schemes we talk about CPA (chosen plaintext attack) and CCA (chosen ciphertext attacks), for hash functions we talk about collision-resistance, being used (combined with keys) as pseudorandom functions, and then sometimes we simply model those as random oracles. Also, all of those tools require access to a source of randomness, and here we use hash functions as well for entropy extraction.

Cryptography’s obsession with adjectives.

As we learn more and more cryptography we see more and more adjectives, every notion seems to have modifiers such as “non malleable”, “leakage-resilient”, “identity based”, “concurrently secure”, “adaptive”, “non-interactive”, etc.. etc… . Indeed, this motivated a parody web page of an automatic crypto paper title generator. Unlike algorithms, where typically there are straightforward quantitative tradeoffs (e.g., faster is better), in cryptography there are many qualitative ways protocols can vary based on the assumptions they operate under and the notions of security they provide.

In particular, the following issues arise when considering the task of securely transmitting information between two parties Alice and Bob:

Basic Key Exchange protocol

The basic primitive for secure communication is a key exchange protocol, whose goal is to have Alice and Bob share a common random secret key \(k\in{\{0,1\}}^n\). Once this is done, they can use a CCA secure / authenticated private-key encryption to communicate with confidentiality and integrity.

The canonical example of a basic key exchange protocol is the Diffie Hellman protocol. It uses as public parameters a group \({\mathbb{G}}\) with generator \(g\), and then follows the following steps:

  1. Alice picks random \(a{\leftarrow_R\;}\{0,\ldots,|{\mathbb{G}}|-1\}\) and sends \(A=g^a\).
  2. Bob picks random \(b{\leftarrow_R\;}\{0,\ldots,|{\mathbb{G}}|-1\}\) and sends \(B=g^b\).
  3. They both set their key as \(k=H(g^{ab})\) (which Alice computes as \(B^a\) and Bob computes as \(A^b\)), where \(H\) is some hash function.

Another variant is using an arbitrary encryption scheme such as RSA: 1. Alice generates keys \((d,e)\) and sends \(e\) to Bob. 2. Bob picks random \(k {\leftarrow_R\;}{\{0,1\}}^m\) and sends \(E_e(k)\) to Alice. 3. They both set their key to \(k\) (which Alice computes by decrypting Bob’s ciphertext)

Under plausible assumptions, it can be shown that these protocols secure against a passive adversary Eve. The notion of security here means that, similar to encryption, if after observing the transcript Eve receives with probability \(1/2\) the value of \(k\) and with probability \(1/2\) a random string \(k'\gets{\{0,1\}}^n\), then her probability of guessing which is the case would be at most \(1/2+negl(n)\) (where \(n\) can be thought of as \(\log |{\mathbb{G}}|\) or some other parameter related to the length of bit representation of members in the group).

Authenticated key exchange

The main issue with this key exchange protocol is of course that adversaries often are not passive. In particular, an active Eve could agree on her own key with Alice and Bob separately and then be able to see and modify all future communication. She might also be able to create weird (with some potential security implications) correlations by, say, modifying the message \(A\) to be \(A^2\) etc..

For this reason, in actual applications we typically use authenticated key exchange. The notion of authentication used depends on what we can assume on the setup assumptions. A standard assumption is that Alice has some public keys but Bob doesn’t. (This is the case when Alice is a website and Bob is a user.) However, one needs to take care in how to use this assumption. Indeed, SSL (now known as TLS) - the standard protocol for securing the web - has gone through six revisions largely because of security concerns. We’ll illustrate one of those before:

Bleichenbacher’s attack on RSA PKCS #1 V1.5 and SSL V3.0

If you have a public key, a natural approach is to take the encryption-based protocol and simply skip the first step since Bob already knows the public key \(e\) of Alice. This is basically what happened in the SSL V3.0 protocol. However, as was shown by Bleichenbacher in 1998, it turned out this is suseptible to the following attack:

The particular details of the attack are somewhat messy, but the general notion is that part of the ciphertext is the RSA function value \(y = x^e \pmod{m}\), and recovering \(x\) will result in recovering the key \(k\). Now, the version of RSA (known as PKCS V1.5) used in that protocol required the value \(x\) to have a particular format, with the top two bytes having a certain form. If in the course of a protocol, a server decryped \(y\) to get a value \(x\) not of this form then it would send an error message and halt the connection. Therefore, the server basically supplied to any party an oracle that on input \(y\) outputs \(1\) iff \(y^{d} \pmod{m}\) has this form, where \(d = e^{-1} \pmod|{\mathbb{Z}}^*_m|\) is the secret decryption key. It turned out that one can use such an oracle to invert the RSA function. For a result of a similar flavor, see the (1/2 page) proof of Theorem 11.31 (page 418) in KL, where they show that an oracle that given \(y\) outputs the least significant bit of \(y^d \pmod{m}\) allows to invert the RSA function.1

For this reason, new versions of the SSL used a different variant of RSA known as PKCS #1 V2.0 which satisfies (under assumptions) chosen ciphertext security (CCA) and in particular such oracles cannnot be used to break the encryption. (Nonetheless, there are still some implementation issues that allowed to perform some attacks, see the note in KL page 425 on Manfer’s attack.)

Chosen ciphertext attack security for public key cryptography

The concept of chosen ciphertext attack security makes perfect sense for public key encryption as well. It is defined in the same way as it was in the private key setting:

Definition: A public key encryption scheme \((G,E,D)\) is chosen ciphertext attack (CCA) secure if every efficient Mallory wins in the following game with probability at most \(1/2+ negl(n)\):

In the private key setting, we achieved CCA security by combining a CPA-secure private key encryption scheme with a message authenticating code (MAC), where to CCA-encrypt a message \(m\), we first used the CPA-secure scheme on \(m\) to obtain a ciphertext \(c\), and then added an authentication tag \(\tau\) by signing \(c\) with the MAC. The decryption algorithm first verified the MAC before decrypting the ciphertext. In the public key setting, one might hope that we could repeat the same construction using a CPA-secure public key encryption and replacing the MAC with digital signatures. Alas, there is a fly in this ointment. In a signature scheme (necessarily) it is the signing key that is secret, and the verification key that is public. But in a public key encryption, the encryption key is public, and hence it makes no sense for it to use a secret signing key. (It’s not hard to see that if you reveal the secret signing key then there is no point in using a signature scheme in the first place.)

Why CCA security matters. For the reasons above, constructing CCA secure public key encryption is very challenging. But is it worth the trouble? Do we really need this “ultra conservative” notion of security? The answer is yes. Just as we argued for private key encryption, chosen ciphertext security is the notion that gets us as close as possible to designing encryptions that fit the metaphor of secure sealed envelopes. Digital analogies will never be a perfect imitation of physical ones, but such metaphors are what people have in mind when designing cryptographic protocols, which is a hard enough task even when we don’t have to worry about the ability of an adversary to reach inside a sealed envelope and XOR the contents of the note written there with some arbitrary string. Indeed, several practical attacks, including Bleichenbacher’s attack above, exploited exactly this gap between the physical metaphor and the digital realization. For more on this, please see Victor Shoup’s survey where he also describes the Cramer-Shoup encryption scheme which was the first practical public key system to be shown CCA secure without resorting to the random oracle heuristic. (The first defginition of CCA security, as well as the first polynomial-time construction, was given in a seminal 1991 work of Dolev, Dwork and Naor.)

CCA secure public key encryption in the Random Oracle Model

We now show how to convert any CPA-secure public key encryption scheme to a CCA-secure scheme in the random oracle model (this construction is taken from Fujisaki and Okamoto, CRYPTO 99). In the homework, you will see a somewhat simpler direct construction of a CCA secure scheme from a trapdoor permutation, a variant of which is known as OAEP (which has better ciphertext expansion) has been standardized as PKCS #1 V2.0 and is used in several protocols. The advantage of a generic construction is that it can be instantiated not just with the RSA and Rabin schemes, but also directly with Diffie-Hellman and Lattice based schemes (though there are direct and more efficient variants for these as well).

Theorem: The above scheme \((G,E,D)\) is CCA secure.

Proof: Suppose towards a contradiction that there exists an adversary \(M\) that wins the CCA game with probability at least \(1/2+\epsilon\) where \(\epsilon\) is non-negligible. Our aim is to show that the decryption box would be “useless” to \(M\) and hence reduce CCA security to CPA security (which we’ll then derive from the CPA security of the underlying scheme).
Consider the following box \(\hat{D}\) that will answer decryption queries \(c\|y\|z\) of the adversary as follows: * If \(z\) was returned before to the adversary as an answer to \(H'(m\|r)\) for some \(m,r\), and \(c=E_e(m\;H(m\|r))\) and \(y=m\oplus r\) then return \(m\). * Otherwise return error

Claim: The probability that \(\hat{D}\) answers a query differently then \(D\) is negligible. Proof: If \(D\) gives a non error response to a query \(c\|y\|z\) then it must be that \(z=H'(m\|r)\) for some \(m,r\) such that \(y = r\oplus m\) and \(c=E_e(r;H(m\|r))\), in which case \(D\) will return \(m\). The only way that \(\hat{D}\) will answer this question differently is if \(z=H'(m\|r)\) but the query \(m\|r\) hasn’t been asked before by the adversary. Here there are two options. If this query has never been asked before at all, then by the lazy evaluation principle in this case we can think of \(H'(m\|r)\) as being independently chosen at this point, and the probability it happens to equal \(z\) will be \(2^{-n}\). If this query was asked by someone apart from the adversary then it could only have been asked by the encryption oracle while producing the challenge ciphertext \(c^*\|y^*\|z^*\), but since the adversary is not allowed to ask this precise ciphertext, then it must be a ciphertext of the form \(c\|y\|z^*\) where \((c,y) \neq (c^*,y^*)\) and such a ciphertext would get an `error response from both oracles. QED

Note that we can assume without loss of generality that if \(m^*\) is the challenge message and \(r^*\) is the randomness chosen in this challenge, the adversary never asks the query \(m^*\|r^*\) to the its \(H\) or \(H'\) oracles, since we can modify it so that before making a query \(m\|r\), it will first check if \(E_e(m\;r)=c^*\) where \(c^*\|y^*\|z^*\) is the challenge ciphertext, and if so use this to win the game.

In other words, if we modified the experiment so the values \(R^*=H(r^*\|m)\) and \(z^*=H'(m^*\|r^*)\) chosen while producing the challenge are simply random strings chosen completely independently of everything else. Now note that our oracle \(\hat{D}\) did not need to use the decryption key \(d\). So, if the adversary wins the CCA game, then it wins the CPA game for the encryption scheme \(E_e(m) = E'_e(r;R)\| r \oplus m \| R'\) where \(R\) and \(R'\) are simply independent random strings; we leave proving that this scheme is CPA secure as an exercise to the reader. QED

Secure authenticated key exchange protocols:

There is a generic “compiler” approach to obtainined authenticated key exchange protocols:

This approach has the advantage of being modular in both the construction and the analysis. However, direct constructions might be more efficient. There are a great many potentially desirable properties of key exchange protocols, and different protocols achieve different subsets of these properties at different costs. The most common variant of authenticated key exchange protocols is to use some version of the Diffie-Hellman key exchange. If both parties have public signature keys, then they can simply sign their messages and then that effectively rules out an active attack, reducing active security to passive security (though one needs to include identities in the signatures to ensure non repeating of messages, see here).

The most efficient variants of Diffie Hellman achieve authentication implicitly, where the basic protocol remains the same (sending \(X=g^x\) and \(Y=g^y\)) but the computation of the secret shared key involves some authentication information. Of these protocols a particularly efficient variant is the MQV protocol of Law, Menezes, Qu, Solinas and Vanstone (which is based on similar principles as DSA signatures), and its variant HMQV by Krawczyk that has some improved security properties and analysis

Password authenticated key exchange.

To be completed (the most natural candidate: use MACS with a password-derived key to authenticate communication - completely fails)

Client to client key exchange for secure text messaging - ZRTP, OTR, TextSecure

To be completed. See Matthew Green’s blog , text secure, OTR.

Security requirements: forward secrecy, deniability.

Heartbleed and logjam attacks

How the NSA feels about breaking encrypted communication

How the NSA feels about breaking encrypted communication

  1. The first attack of this flavor was given in the 1982 paper of Goldwasser, Micali, and Tong. Interestingly, this notion of “hardcore bits” has been used for both practical attacks against cryptosystems as well as theoretical (and sometimes practical) constructions of other cryptosystems.

  2. Recall that it’s easy to obtain two independent random oracles \(H,H'\) from a single oracle \(H''\), for example by letting \(H(x)=H''(0\|x)\) and \(H'(x)=H''(1\|x)\).