Chance of finding the right key by exhaustively searching on half of the key space

Question

An exhaustive search of half the key space requires $2^{n-1}$ work and provides the right answer 75% of the time. If the attacker finds the key, he knows the answer. If he doesn't find the key, he still has a 50% chance of guessing right simply by guessing at random. Overall, his chances of getting the right answer are therefore $0.5 + 0.5*0.5 = 0.75$.).

In this quote from Cryptography Engineering book by Bruce Schneier, section 3.4, it has been said that there is 75% probability that a particular key can be found by dividing the key space into half, exhaustively searching from this and choosing a key randomly if not found. How the $0.5+0.5*0.5$ has been derived in this case? How is the chance of randomly guessing a key from the key space in 50%? Shouldn't it be $1/2^n$ in case where key size is $n$.

Answer 1

Schneier is talking about distinguishing a block cipher from an ideal cipher - or in other words, about formal definitions for security. Think of a game, where the attacker is given a ciphertext encrypted either with a block cipher or with an ideal cipher (with equal probability), and has to guess which cipher encrypted the message.

Let's say this attacker tries 50% of the block cipher key-space, and if any key correctly decrypts the message then it guesses that the cipher that encrypted the message was the block cipher. But if no key correctly decrypts the message then the attacker guesses that the ideal cipher was used.

There's a 50% chance that the cipher used was in fact the ideal cipher. In that scenario, the attacker will always correctly guess that the ideal cipher was used - so it has a 50% chance of being correct along that branch of the probability tree.

There's also a 50% chance that the cipher was in fact the block cipher, and in that scenario there are two possible outcomes - either the key was among those that the attacker tried (in which case it will correctly guess that the block cipher was used), or the key was not among those that the attacker tried (in which case the attacker will incorrectly guess that the ideal cipher was used). Since the attacker tries half the key-space, that means the attacker has a 50% chance of guessing correctly (given that the block cipher was used). So the total contribution of this branch of the probability tree is 50% (odds that block cipher is used) * 50% (odds that key is among those tested) = 25%.

So the total probability of the attacker making a correct guess is 50% + (50%*50%) = 75%.

Answer 2

An exhaustive search of half the key space requires $2^{n-1}$ work and provides the right answer 75% of the time.

I haven't read that book, so that may deserve a caveat from me about the larger picture. However, as specified, I don't believe the conclusion above is correct, but not for the reason you think.

If you present a distinguisher with a copy of the cipher, it will give the correct answer 75% of the time. However, were that the only criteria, we could give the correct answer 100% of the time by, if we don't find the key, guessing that it was a cipher anyway.

If you present a distinguisher with a random permutation, the key search will never find the right key (presumably, if the search finds an initial match, it'll try enough additional plaintext that the probability of a spurious match is effectively 0). In this case, the above algorithm will end up guessing randomly, and it'll make the correct guess 50%, not 75%, of the time.

So, as specified, the algorithm has a distinguishing advantage of $|0.75 - 0.5| = 0.25$

We can actually do better my modifying the algorithm to always guess "random permutation" if it can't find the key; in that case, it'll be right 50% of the time if given the cipher, and always right if given a random permutation; that gives us an advantage of $|0.5 - 0.0| = 0.5$