Security Implications

[Ingo Klöcker]

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