7
$\begingroup$

Is the following snippet from a recently published cryptography book correct?

EDIT: Expand the snippet from the book to make the context (symmetric key search) more clear.

You can apply this to other cryptographic issues as well. Let's return to the DES algorithm. Recall that it has 72,057,594,037,927,936 possible keys. To guarantee that you find the correct key, you may need to check all 72,057,594,037,927,936 possibilities. However, if all you are seeking is a greater than 50 percent chance of finding the right key, you can try $1.774 \sqrt{72,057,594,037,927,936}$ possible keys -- only 476,204,499 possible keys. This is far more manageable. In fact, again referring to our earlier scenario with DES, if you can attempt 1 million keys per second, you have a 50 percent chance of finding the right key in 7.9 minutes. Although 1 million keys per second is beyond the capability of your standard personal computer, it is well within the capabilities of supercomputers or even computing clusters.

The birthday paradox is one reason why larger key sizes are necessary for security. If we move our attention from DES to an AES 128-bit key, there are approximately $3.402 * 10^{38}$ possible keys. Applying the birthday paradox gives us $1.774 * \sqrt{3.402 * 10^{38}}$, or 32,724,523,986,760,744,567 keys that need to be attempted to have a 50 percent chance of finding a match. This number is large enough that it is computationally infeasible to break it through brute-force methods, even with the birthday paradox.

$\endgroup$
  • 6
    $\begingroup$ To get 50 percent chance of finding the right key, you need to try half the key space, not square root of key space? Birthday attack would apply to hash collisions, not AES brute force? $\endgroup$ – Thomas Byrd Feb 26 '16 at 2:53
  • $\begingroup$ Yes, a birthday attack scenario comes when a user generates many keys, and an attacker need only collide with one at random. $\endgroup$ – Stephen Touset Feb 26 '16 at 3:15
  • 1
    $\begingroup$ @otus Sure, it's on page 324 of this book: Modern Cryptography $\endgroup$ – Thomas Byrd Feb 26 '16 at 10:03
  • 1
    $\begingroup$ Usually this kind of statement is only true if you have a significant amount of ciphertext (in this case created by multiple keys). That would mean you would also require a very large lookup table in memory. It would not work for just any attack vector. $\endgroup$ – Maarten Bodewes Feb 26 '16 at 13:43
  • 2
    $\begingroup$ It's very upsetting to see such horrible errors in a textbook... $\endgroup$ – Yehuda Lindell Feb 28 '16 at 11:17
5
$\begingroup$

The citation as now expanded is clearly in the context of key search for a cipher, and grossly wrong, including time estimate to find a DES key with odds 50% with 1 million keys tested per second (that is over 11 centuries where 7.9 minutes is stated). In other contexts, the explanation could be right except for a moderate factor erring straight on the unsafe side, or vaguely related to a relevant phenomenon. In all cases, that's wrong; as well as the estimate of key test rate: one million DES keys per second on a consumer desktop CPU was already feasible circa 1997.

As pointed in comment by the question's author, in the context of key search we need to search half of the key space to find a particular key with odds 50% (baring equivalent keys, and shortcuts to search). The birthday bound is irrelevant. After we searched the number of keys indicated in the citation ($1.774\sqrt n$ where $n$ is the size of the keyspace), our odds of having found the right key (assumed randomly chosen and initially unknown) is the ratio of the number of (distinct) keys tested, to the size of the keyspace; and that's in the order of $1.774/\sqrt n$, which is negligibly small, rather than 50% as stated.

The multiplicative constant for the birthday bound should be $\sqrt{\log4}\approx1.1774$ where the citation gives $1.774$, and uses it, making even the leftmost digit of both birthday bounds stated wrong, and erring on the unsafe side; see final note. Except for that, the explanation would have been right if the issue had been to guard against finding collisions for a one-way function such as $H:\{0,1\}^{128}\to\{0,1\}^{128};\; H(K)=\operatorname{AES-128}_K(0)$.

If we consider the security of a block cipher such as DES or AES in CBC mode, it is correct to invoke the birthday bound for collisions over the block size space; and for AES-128 this is the same as the key space, which makes the order of magnitude of the numbers in the second half of the citation relevant; however in that context the explanation does not justify "why larger key sizes are necessary"; only why larger block sizes are necessary.

As a practical illustration of the relevance of the birthday bound for CBC mode, consider a 40 GiB file, that is suspected to be the result of enciphering with 3DES in CBC mode a movie file directly extracted from a Blu-ray disk (perhaps with a little random added at the end of the file to hide the exact length of the original). The encrypted file is large enough that with odds better than 50%, two enciphered 64-bit blocks are identical. This implies that the eXclusive-OR of the two corresponding blocks in the original is equal to the eXclusive-OR of the preceding blocks in the encrypted file. That observation makes it feasible to demonstrate beyond reasonable doubt the nature of the encrypted file if the original is available, even if we have to decide among thousands of potential originals.


Note: The actual birthday bound for 56-bit (resp. 64-bit and 128-bit) values is 316,058,597 (resp. 5,056,937,541 and 21,719,381,355,163,562,492). That's applying David Brink: A (Probably) Exact Solution to the Birthday Problem (in The Ramanujan Journal, June 2012, Volume 28, Issue 2, pp 223-238), conjecturing that the number of uniformly chosen values among $n\ge1$ at which odds of collision reaches 50% is $$\left\lceil\sqrt{n\log4}+{3-\log4\over6}+{9-\log^2 4\over72\sqrt{n\log4}}-{\log^2 4\over270n}\right\rceil$$ which in cryptography we tend to approximate with $1.1774\sqrt n$ or just $\sqrt n$, with both erring somewhat on the safe side from the legitimate user's perspective.

$\endgroup$
  • $\begingroup$ Does your 2nd paragraph claim that "we need to search half of the key space to find a given key with odds 50%"? If yes, I have a problem with my logic: Following the birthday problem, keep generating randomly keys, test them for correctness and independent of result put them into a room, until the number of keys there achieves the collision estimate. Now consider the right key enters that room. Isn't it that with a 50% chance it will find that there is an already existing copy of it? If so, what 's wrong with the other argument of needing trying keys of a number of half of the key space? $\endgroup$ – Mok-Kong Shen Feb 27 '16 at 9:00
  • $\begingroup$ @fgrieu: Ok. But, if the number of keys already in the room is twice the collision estimate, would my argument be ok? $\endgroup$ – Mok-Kong Shen Feb 27 '16 at 10:39
  • $\begingroup$ @fgrieu: Perhaps I yet misunderstood you. I meant that with key number of twice the collision estimate one highly probably ensures that all the keys in the room would contain distinct keys of a number equal to that estimate (which was the condition not satisfied in my first comment according to your original critique). $\endgroup$ – Mok-Kong Shen Feb 27 '16 at 10:58
  • $\begingroup$ @fgrieu: Would that imply that there might be other estimates relevant for crypto that are similarly affected? $\endgroup$ – Mok-Kong Shen Feb 27 '16 at 11:29
  • 2
    $\begingroup$ @Mok-Kong Shen I think you are making the same logical mistake as the author of the book. As the accepted answer by fgrieu explains, the birthday bound does not apply when you start talking about finding collisions with "the right key". It applies to the question: Given n randomly chosen keys, what is the probability that there is a duplicate? Note that this does not place any additional constraints on this duplicate, such as that it should be "the right key". Once you specify such a constraint, the birthday bound no longer applies. $\endgroup$ – Thomas Byrd Feb 27 '16 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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