Applicability of birthday attack to AES brute force

Question

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.

Answer 1

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.