(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>
_______________________________________________
Gnupg-users mailing list
Gnupg-users@gnupg.org
http://lists.gnupg.org/mailman/listinfo/gnupg-users
