Why in brute force attack on Symmetric Algorithm there is 50 percent chance of finding the key after half of the attempts?

Question

Any cryptography text mentions that in brute force attack on Symmetric Algorithm there is 50 percent chance of finding the key after half of the attempt.

e.g. DES with 56 bit key would have 50% chance of finding the key after the first 2⁵⁵ attempts.

Why in a brute force attack against any symmetric encryption algorithm there is a 50% chance of finding the key after half of the attempts? What is the mathematical proof for it?

It's just basic probability theory - if you turn over 26 cards in a deck of 52 cards then there is a 50 per cent chance that you will have found the queen of spades. — Paul R, Oct 17 '10 at 08:17
Yes, thius is tso totally unrelated to encryption, cryptography and anything else it is not even funny (total school failure?). This is high school (at least in germany) introductory level probability (which is simple maths). — TomTom, Oct 17 '10 at 08:28
@TomTom: Being so obvious, I wanted to make sure that I am not missing anything. In my opinion, the statement should not have been in the cryptography text in the first place as it is not revealing or adding any value. There is no harm in clarifying things, correct? — Anand Patel, Oct 17 '10 at 08:34
@TomTom: It's always obvious once you know the answer. Anand is asking the right questions, and sometimes the most basic questions lead to new insights. — President James K. Polk, Oct 17 '10 at 13:08
I'm voting to close this question as off-topic because it isn't about programming, but about mathematical proofs. — Jean-François Corbett, Oct 16 '17 at 06:32

RichieHindle · Accepted Answer · 2010-10-17T08:25:22.880

5

If there are N boxes in front of you, one of which contains a prize, then on average you only have to look in half the boxes before you find it.

(Look at it another way: you'd be spectacularly unlucky if there were a lot of boxes and the prize was in the last box you tried.)

Proof: The chance of the prize being in any particular box is 1/N, and the prize is in one and only one box. If you look in half the boxes (N/2), your chance of finding it is (1/N) * (N/2) which is 1/2, or 50%.

edited Oct 17 '10 at 08:25

answered Oct 17 '10 at 08:16

RichieHindle

272,464
47
358
399

Gratulations. Contrary to the OP you did not skip basic math lessons. – TomTom Oct 17 '10 at 08:28
@TomTom: I am wondering, why you didn’t take the English class during your high school. – Anand Patel Oct 17 '10 at 08:42
2

@Anand Patel: TomTom's English is a lot better than my German. Please, guys, let's keep personal insults out of this. – RichieHindle Oct 17 '10 at 08:52
Yes. Thanks Richi - someone needs obviously to educate Anand also on the fact that not everone speaks english natively. – TomTom Oct 17 '10 at 08:54
It is only due to you guys the stackoverflow.com site is a good resource for anybody to learn. Thanks. – Anand Patel Oct 17 '10 at 09:13

score 0 · Answer 2 · answered Feb 04 '15 at 07:11

0

Each key can both encrypt and decrypt. So if there are 100 possible keys, then a brute force attack looks like:

First attempt: 1/100 chance.
Second attempt: 2/100 chance.
...
Fiftieth attempt: 50/100 (50%) chance

answered Feb 04 '15 at 07:11

Robert Christian

18,218
20
74
89

Why in brute force attack on Symmetric Algorithm there is 50 percent chance of finding the key after half of the attempts?

2 Answers2