GPG's vulnerability to brute force [WAS: Re: GPG's vulnerability to quantum cryptography]

[Peter Lebbing]

(This mail originally got dropped by the list managing software because
I had accidentally misused a new webmail plugin. I'm resending it
with all original identifiers so it hopefully threads correctly. I'm
also completely ignoring section 3.6.6 of RFC 2822, but who cares? ;)

-------

I suddenly realised something about Rob's Crypto FAQ[1]. You state that 
you need 64 bitflips per attempt, because otherwise your attacker can 
simply adapt his key to the order in which you try them. But to save on 
those 64 bitflips, you could also simply do the whole keyspace in 
order[2]. Your expected number of computations does rise from 2^127 to 
2^128, because obviously everybody will then use the key 2^128-1, which 
is the last one you try ;).

The save of 64 bits to 1 bit loses you 6 bits exponential complexity, 
the increase of the expected number of tries increases it again by 1 
bit, so you have saved 2^5 = 32 = 10^1.5 on the numbers Rob gives. When 
I'm quickly reading through the calculations, it seems we changed it 
from 100 nuclear warheads to only 3, to scan the whole keyspace.

However, this whole thing completely falls apart. We were able to save 
63 bitflips per trial in exchange for a twofold increase in total work. 
In the math done in [1], this changes the feel of the numbers radically, 
because to us, the difference between 3 and 100 is big (it's not when 
discussing exponential complexity). But that is because (at least) one 
very large source of bitflips is not looked at: the number of bitflips 
one trial of a key actually takes. Leo called it 10^5, Rob called it 
10^3. If you save 63 bitflips on a total of a million, that doesn't 
change the final numbers in the least. Pull out some hairs and you still 
have a beard: 10^3 - 63 = 10^3. Incidentally, we went from 100 nuclear 
warheads to 3 to 1000[3].

The thing I'm saying is: the explanation for taking 10^2 as the amount 
of bitflips for a single try doesn't seem convincing. It makes it seem 
that you can actually save computation by linearly searching your 
keyspace.

Peter.

[1] http://sixdemonbag.org/cryptofaq.xhtml#entropy
[2] Actually, make that Gray code order, which actually achieves 1 
bitflip changes per succession, unlike normal binary encoding.
[3] Or 10,000 depending on whether 2^128 is better approximated by 
10^38 or 10^39, when you're really nitpicking. Which you shouldn't do 
when discussing exponential complexity. Let's say that with exponential 
complexity, your fingers are too large to pick a nit.

-- 
I use the GNU Privacy Guard (GnuPG) in combination with Enigmail.
You can send me encrypted mail if you want some privacy.
My key is available at 
<http://digitalbrains.com/2012/openpgp-key-peter>