Security Implications
Ingo Klöcker
ingo.kloecker@epost.de
Sat Dec 15 15:14:01 2001
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On Friday 14 December 2001 18:49, Ryan Malayter wrote:
> Ingo Klöcker <ingo.kloecker@epost.de> wrote:
> <snip>
>
> >But as it's much more time consuming to find the secret
> >key corresponding to a public key than to simply find
> >the session key (by brute force) nobody would ever try
> >to crack the asymmetrically encrypted session key but
> >would crack the symmetrically encrypted message
> >itself instead.
>
> <snip>
>
> That's really not true. Cracking the asymmetric keys would allow the
> attacker to read *all* of the victim's mail. Cracking the symmetric
> session key would allow him to read just one message. The
> public/private keypair is a much more attractive target.
True. But one doesn't need to intercept a message encrypted with this
persons public key if his key can be downloaded somewhere because then
it can be used for arbitrary known-plaintext attacks. So encrypting the
same message once to many people has no disadvantage compared to
encrypting the same message for each recipient separately.
> By brute-force, is completely infeasible to crack a 128-bit symmetric
> key. However, 512-bit asymmetric keys *have* been cracked by brute
> force using the General Number Field Sieve. The 1024-bit symmetric
> keys used in OpenPGP could be vulnerable to brute-force.
Obviously every key is vulnerable to brute-force attacks. Only the
degree of vulnerability in terms of the average time needed for a
brute-force attack differs.
BTW, there are more sophisticated algorithms to crack assymmetric keys
than to crack symmetric keys because the mathematics of the assymmetric
encryption is much easier and much better understood nowadays. AFAIK,
nobody (apart of the NSA?) ever managed to really understand DES. The
only reason for its weakness is its restricted key size. And the
Rijndael algorithm (aka AES) is simply to new.
If elliptic curve algorithms would be used for assymmetric keys it would
all of a sudden become much more difficult to attack assymmetric
encryption. But this is also partly due to the fact that elliptic curve
algorithms aren't really understood very well (again only AFAIK). But
at least the GNFS wouldn't help you much in this case.
> Attacks on large asymmetric keys will be possible in the near future.
> A 1024-bit asymmetric key is *not* 2^512 times as strong as a 512 bit
> key. The complexity GNFS algoritm is O(e^(1.923
> +(ln(n))^(1/3)*(ln(ln(n)))^(2/3))), so factoring a 1024-bit
> asymmetric key us only about 200,000 times as hard as factoring a
> 512-bit asymmetric key. This will probably happen within a few years,
> as computing power increases and factoring algorithms get even
> better.
For n=512 I get O(...)=107.54... and for n=1024 I get O(...)=132.26...
There must be something wrong with your formula for the complexity of
the GNFS algo.
But however, computer power doubles about every 1.5 years by "Moore's
law". log_2(200.000) is about 17.6. That means it will take about 25
years until the computer power has increased enough. Furthermore
significantly better factoring algorithms are also not very likely.
Maybe some constants (like the 1.923) can be improved a little bit. So
your few years are most likely at least 10 years.
BTW, distributed computing doesn't help much with the GNFS because the
large system of equations which is generated in the first step (which
_can_ be done via distributed computing) still has to be solved with
one (super-)computer. So only some very large corporations and secret
agencies will have enough power to crack asymmetric keys in the
foreseeable future.
> Basically, if you're attacking an OpenPGP user, and resorting to
> brute force (which you probably wouldn't have to do in practice), an
> attack on the asymmetric key is the only smart one.
Although this is true I don't think that any normal person will ever (in
the next 20 years) have enough computer power to crack a 1024-bit
asymmetric key.
Regards,
Ingo
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org
iD4DBQE8G0x6GnR+RTDgudgRAmZSAJj52zHrhYPTvwdcUxgI+ry4O1qOAKDFpMbF
GWWJdjpdmwZiPJWUjQ1e9Q==
=w3JV
-----END PGP SIGNATURE-----