6
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This previous question about CBC is similar: crypto.stackexchange.com/questions/2467/… $\endgroup$
    – pg1989
    Commented May 21, 2013 at 17:40
  • 2
    $\begingroup$ These seem as notes from coursera Dan Boneh's crypto course $\endgroup$
    – curious
    Commented May 21, 2013 at 17:41
  • $\begingroup$ @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. $\endgroup$
    – makerofthings7
    Commented May 21, 2013 at 19:49

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – makerofthings7
    Commented May 22, 2013 at 1:06
  • $\begingroup$ 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? $\endgroup$
    – makerofthings7
    Commented May 22, 2013 at 1:08
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented May 22, 2013 at 2:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented May 22, 2013 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.