Analysis of CCMP

Jonsson [Jon03] has shown that the CCM mode of operation is a secure au-thenticated encryption scheme. He proved that CCM satisfies the two separate security notions of indistinguishability under chosen-plaintext attacks (IND-CPA) and integrity of ciphertexts (INT-CTXT); see [BN00] for their formal definitions. In Appendix A.3, we show that this is equivalent to our all-in-one definition of AE security. Thus, in order to prove the stateful AE security of CCMP, it is sufficient to reduce to the (stateless) AE security of CCM.

However, on closer inspection, we cannot, in fact, prove that CCMP is a secure stAE scheme according to Definition A.5. The reason is that the security experiment used to define stAE security in Appendix A.4, targets a different integrity semanticthan what is provided by CCMP. Namely, the security exper-iment in Figure A.4 is adapted from [Jag+12], which presented the definition in the context of analyzing TLS. But the integrity guarantees provided by the TLS Record Layer protocol are stronger than those provided by CCMP.

Specifically, in terms of integrity, the TLS Record Layer is supposed to provide protection against:

1. forgeries, 2. replays, 3. reordering, and 4. dropping of messages.

However, CCMP doesnotprovide protection against messages being dropped.

To see this, suppose a sender transmits as its first encrypted CCMP messages, the framesZ₁,Z₂ andZ₃, thus having corresponding packet numbers 2, 3 and 4 (remember that thesentcounter starts at 1). Now suppose an attacker drops messagesZ₁andZ₂, but deliversZ₃to the receiver. SinceZ₃is a validly created CCMP frame, the CCM decryption at Line 4 of theCCMP.Decprocedure will succeed. Moreover, when theCCMP.Decprocedure continues to check whether Z₃ is a replay at Line 9, then this will also succeed, since the receiver’s rcvd counter is set to 0 and so we havercvd <sent. Thus, Z₃ will be accepted by the receiver even thoughZ₁ andZ₂ were lost.

By contrast, the TLS Record Layer demands that the decryption process happens in exactly the same order as the ciphertexts were created by the en-cryption process. Thus, it does not accept any messages being dropped. Other integrity semantics are also possible by considering different combinations of the four properties listed above. Boyd et al. [Boy+16] have analyzed this question in depth.

To summarize, CCMP cannot be proven secure according to the stAE se-curity definition given in Appendix A.4 because it implies astronger integrity semantics than what CCMP achieves. Consequently, we have to consider a weakening of the stAE model that allows for messages to be dropped. Par-ticularly, at Line 7 of the Dec oracle in Figure A.4, we change the condition from

if (C, A) = S[rcvd]: if (C, A) ∈/ S[rcvd. . .sent]:

in-sync←false to

in-sync←false

whereS[i . . . j] ={S[i], S[i+ 1], . . . , S[j]}ifi≤j, and∅otherwise. Notice that this widens the scope of which messages are considered in-sync, from one mes-sageS[rcvd], to potentially a large rangeS[rcvd. . .sent]. Hence, this effectively weakens the model since it restricts the adversary more.

Let Adv^stAE_Π ^-d(A) denote the stAE advantage of an adversary A against some stAE scheme Π within this weakened model. We then have the following result.

Theorem 6.6. Let A be an adversary against the stAE security of CCMP, then we can create an adversary Bagainst the AE security of CCM, such that Adv^stAE_CCMP^-d(A)≤Adv^AE_CCM(B). (6.17)

Proof. From an adversary A that breaks the stAE security of CCMP where message drops are allowed, we can construct an algorithm B that breaks the CCM mode of operation. Specifically, algorithmB creates and maintains the counterssentandrcvdof the CCMP scheme, as well as the variablessent,rcvd, S[·], andin-syncof security gameExp^stAE_CCMP^-d(A). We writesentCCMP,rcvdCCMP

for the counters thatBmaintains for the CCMP scheme, andsent_Exp,rcvd_Exp for the counters thatB maintains for the stAE experiment.

WhenAmakes an encryption query (M₀, M₁, A),Bfirst incrementssentCCMP

and creates a nonceNfromsentCCMPaccording Equation (6.14). It then queries theEnc oracle in its own AE security game on (N, M₀, M₁, A). B returns the resulting ciphertextCtogether withsentCCMP toA, and updates the variables sent_Exp andS[sent_Exp] accordingly.

WhenAmakes a decryption query (sentC, A),Bfirst increments the value of the counterrcvd_Exp by 1 and then proceeds as follows.

• If (sentC, A) ∈ S[rcvd_Exp. . .sent], then B returns ⊥ to A (since this query is in-sync).

• Else, B creates the nonce N ← flagsU sent, and queries (N, C, A) to the Dec oracle in its own AE security game to produce a message M. If M =⊥then B stops its simulation and outputs 1 to its AE security game. Otherwise,Breturns⊥to A.

Finally, when Astops with some output b, then B stops and outputs the same bit to its AE security game.

Notice that when the secret bit in B’s own AE security game is 0, then B perfectly simulates the “left-world” of experimentExp^stAE_CCMP^-d(A), i.e., where the encryption query returns the encryption ofM₀ and the decryption query always returns⊥. This is because in this scenarioB’s own AE decryption oracle always returns ⊥, and so Banswers all of A’s decryption queries with⊥ too.

Moreover, B’s simulation of A’s encryption queries is perfect no matter what the value of the secret bit in its own AE security game is. This is because B properly creates the nonceN from the countersent_CCMP, which it creates and maintains itself.

Thus, it only remains to argue that B perfectly simulates the decryption query of the “right-world” of experiment Exp^stAE_CCMP^-d(A) when the secret bit in B’s own AE security game is 1. To this end, it is sufficient to note that B forwards the decryption query to its own AE security game exactly when the query is out-of-sync according to the requirements of gameExp^stAE_CCMP^-d(A).

This is so because B itself has created and maintains the counter rcvd_Exp in accordance withExp^stAE_CCMP^-d(A). Moreover, ifB’s own decryption oracle returns something other than⊥, which for instance could happen ifAreplays an old

ciphertext but with a new countersentsuch thatrcvd_Exp<sent, thenBstops and immediately wins in its AE security game.⁴

To summarize: B perfectly simulates the Exp^stAE_CCMP^-d(A) game for A, and wins in its own AE security against CCM with at least the same probability

asA.

Since CCMP maintains a 48 bit counter sent in order to create the nonces for CCM, it can technically be used to encrypt up to 2⁴⁸IEEE 802.11 frames.

The maximum allowable IEEE 802.11 frame size is around 2¹³ bytes = 8 kB, so a total of 2⁴⁸⁺¹³ bytes can be encrypted under the same key. However, the CCM security bound proven by Jonsson [Jon03] includes a “birthday bound”

term of the form c·²·2^−κb, where c is a small constant, is the number of invocations of the underlying block cipher, and κ_b is the block length. In CCMP the block cipher is AES, so κ_b = 128. Moreover, since CCM makes roughly 2 block cipher calls per input block, this implies that an IEEE 802.11 frame ofB bytes will involve around 2B/16 =B/8 block cipher calls. If we set c= 1, then in order for²·2^−κbto stay below , we need (B/8)²·2⁻¹²⁸≤ . In other words, no more than 2⁶⁷·B⁻¹· ^1/2 frames ofB bytes can be encrypted under the same key.

For example, if we set the frame size to be B = 2¹⁰ bytes = 1 kB, and we want <2⁻⁶⁰, then Jonsson’s bound only justifies up to 2²⁷ IEEE 802.11 frames being encrypted with the same key, or roughly 2³⁷ ≈137 GB of data.

Alternatively, if the requirement is reduced to <2⁻⁵⁰, then we get the more tolerable bound of ≈ 4 TB of data; while if the requirement is increased to <2⁻⁷⁰, we get virtually no guarantees (≈4 GB of data).

6.4 Multi-ciphersuite and negotiation security