# How much data can I encrypt with AES before I need to change the key in CBC mode?

In my cryptography class, the instructor suggested that in order to give the attacker a minimal advantage of $1/2^{32}$, we have to change the key after $2^{48}$ blocks are encrypted.

It seems that the advantage of $1/2 ^{32}$ is somewhat arbitrarily chosen, and I'm not sure where that comes from. Can anyone explain the reasoning of why this is chosen and when it should be higher or lower than $1/2^{32}$?

My class notes:

CBC: CPA Analysis

$q =$ # of messages encrypted with key $k$
AES uses 128 bit blocks
$L$ = length of the max message

For every adversary $A$ that attacks cbc encryption, there is a PRP adversary $B$ with

$$Adv[A,E_{cbc}] \leq 2 · Adv[B, E_{prp}] + \overbrace{2 · q^2· L^2 / |X|}^{\text{error term}}$$

So CBC is only secure as long as $q^2·L^2 \ll |X|$.

Example

The error term = $q ^ 2 · L^2 / |X| < 1/2 ^{32}$

AES: $|X| = 2^{128}$ (bits per block) So after $2^{48}$ AES blocks the key needs to be changed.

DES: $|X| = 2^64 \Rightarrow q·L < 2 ^{16}$

Also, the instructor said that DES needed a new key after $2^{16}$ blocks, and he said that means every .5 MB of data requires a change. This is the formula he wrote down, Is this correct? $2^{16} · 8 = 1/2$ MB.

-
This previous question about CBC is similar: crypto.stackexchange.com/questions/2467/… –  pg1989 May 21 '13 at 17:40
These seem as notes from coursera Dan Boneh's crypto course –  curious May 21 '13 at 17:41
@curious Yes, they are from his coursera course. It's really good and packed full of information. I discovered this 2 weeks ago and am trying to finish all the classes in 1 month so I can start the next one on time. –  makerofthings7 May 21 '13 at 19:49

## 1 Answer

The $1/2^{32}$ is an arbitrary figure, based upon one particular value for what counts as an acceptable risk.

You need to decide what is an acceptable risk. If you think that a $1/2^{32}$ probability of failure is an acceptable risk, then this calculation is relevant to you. If you think it isn't, then decide what you think is an acceptable risk and re-do the calculation based upon the number you think fits your particular situation.

Keep in mind a $1/2^{32}$ probability of failure is pretty darn small -- in many settings, it may be acceptable. It's far more likely that the next time you'll get into a car, you'll end up in a car accident: the probability of that is probably much higher than $1/2^{32}$. Also keep in mind that life is about risk: you can never completely eliminate all risk from your life. So, decide what is an acceptable risk, then you based upon that you can decide how much data you can encrypt under a single key, using a calculation similar to that one shown here.

-
Part 1 - Could this number (1/2^32) be compared to a Birthday Attack, where the distribution is non-uniform? Namely, where there there is tipping point of where 0.. to some negligible number increases rapidly to a non-negligible number? –  makerofthings7 May 22 '13 at 1:06
Part 2 - Could this "risk" be explained to management as the quantity of brute force attempts that we will tolerate? (substitute brute force for X chosen message attacks etc) and 2^64 is the minimum required due diligence? –  makerofthings7 May 22 '13 at 1:08
@makerofthings7, to understand what it means, start by understanding what 'advantage' means at a deep level. At a very rough, crude level, you can think of it as representing the probability that an attacker learns some information about the message. (However, strictly speaking, this is a simplification.) In this case, we are saying roughly "If you encrypt no more than $2^{48}$ blocks of data under the same key, the probability that the attacker learns some information about the message is at most $1/2^{32}$". Roughly. –  D.W. May 22 '13 at 2:20
Another part of risk management is assessing how big the damage is. For an IV collision with AES-CBC it's typically not very big. –  CodesInChaos May 22 '13 at 18:56