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

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$.

• Which cryptographic engineering book, and at what section? Written like this it seems total nonsense, but maybe the context may help us here. Commented Jul 8, 2016 at 18:59
• I have edited the question. Commented Jul 8, 2016 at 19:08
• Still more context is needed. What exactly is the attacker trying to do? You seem to assume that the attacker tries to guess the key, but I suspect this may not be the case. Commented Jul 8, 2016 at 19:14

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%.

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$$

• Note for user36703 - poncho uses the term "distinguishing advantage", which is not the same as "chance of getting the right answer". The attacker who guesses "ideal cipher" if the key guessing fails has an "advantage" of 50% - but it has a 75% "chance of getting the right answer".
– J.D.
Commented Jul 8, 2016 at 20:57
• @J.D.: actually, that's rather my point; they have a 75% chance of getting the right answer if they were given a cipher; if they were given a random permutation, they only have a 50% chance. Ignoring the second case is not appropriate. Commented Jul 8, 2016 at 21:14
• Poncho - To clarify, I interpreted the 75% "chance of getting the right answer" as $\Pr(GuessBC | BC)\Pr(BC) + \Pr(GuessIC | IC)\Pr(IC)$, (where BC means blockcipher and IC means ideal cipher), which equals $(0.5 \cdot 0.5) + (1 \cdot 0.5) = 0.75$.
– J.D.
Commented Jul 8, 2016 at 21:40
• @J.D.: actually, given that the text specifies that you guess randomly if you don't find the key, I believe that the probability you wrote out (assuming that BC and IC were equiprobable) would be $PR(GuessBC|BC)Pr(BC) + Pr(GuessIC|IC)Pr(IC) = (0.75 \cdot 0.5) + (0.5 \cdot 0.5) =$$0.625$. Your equation would be accurate if you always guessed "IC" if you couldn't find the key (which is what I suggested, but not what the text says) Commented Jul 8, 2016 at 21:47
• The strategy you suggested is the one I had in mind. So, either I am misinterpreting the text or Schneier made an error in CE (e.g. by specifying that the attacker should 'guess randomly if the key search fails' instead of 'always guess IC if the key search fails').
– J.D.
Commented Jul 8, 2016 at 22:11