I am somewhat confused with something I read in Dan Boneh's slides discussing the advantage of a $2^{80}$-time adversary attacking AES-256; according to Boneh, the assumption is that this advantage is bounded by $2^{-40}$ (see slide 8 here or fast forward to 7:04' in the video here).

I have been looking to a few lecture notes (e.g., Goldwasser-Bellare, pg 72, section 5.5 at cseweb.ucsd.edu/~mihir/papers/gb.pdf) and books (e.g., Boneh-Shoup cryptobook draft 0.3 chapter 4, the katz-lindell book, or the handbook of applied cryptography chapter 7), but I am still unsure about this bound. It seems unrelated to quantum attacks on the key, which may justify a square root on $2^{80}$; however, an exhaustive search for AES-256 keys should take $2^{128}$ steps on a quantum computer.

In addition, it doesn't seem to be related to the birthday paradox either. Most birthday attack related bounds in the aforementioned references were linked to a mode of operation (for example, CTR-mode attacks related to the number of blocks encrypted under the same key), proofs related to PRFs, etc. What I find confusing is the connection between the time complexity of the adversary and the PRP advantage bound, as the attack that distinguishes the PRP from a truly random permutation is unclear.

Is the $2^{-40}$ advantage assumption accurate? If so, how is it explained? Why the adversary is getting this advantage after all?


1 Answer 1


You misunderstood what Dan Boneh was trying to say. There is no known attack on AES256 that comes even close to this complexity. However, if there was a known attack that came close to this, then it would be very unwise to assume that this is the best attack. When formalizing an assumption, one needs to be conservative relative to what is known. Thus, Dan was giving an example of how one could formulate a conservative assumption about AES, and he was being very conservative (which is a good thing).


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.