North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: 1024-bit RSA keys in danger of compromise (fwd)

  • From: Len Sassaman
  • Date: Mon Mar 25 19:53:03 2002

On Mon, 25 Mar 2002, Travis Pugh wrote:

> Out of curiosity, was there any indication that Bernstein's
> improvements might apply to the discrete log problem, DSA in general,

Bernstein's paper was geared toward RSA, but I believe he makes the claim
that discrete log based algorithms are susceptible as well. I'm not a
cryptographer, so my word shouldn't be taken as fact on this, but if
there is a row-reduction step in solving DL, it would apply.

> and the 1024-bit limit on key size built into NIST's DSS standard?

I'm not sure about the relative bit strength when the row reduction is
taken into account, but I suspect that if the above assumptions are true,
1024 bit would be too small.

NIST's limit was specified for purely technical reasons -- until recently,
we did not have hash functions that were of sufficiently long bit-sizes to
do provide equivalent security for DSA keys larger than 1024 bits, so DSS
was limited to that size. (SHA-1, the hash function specified in the DSS,
was 160 bits. So was RIPEMD-160).

One could now do a larger DSA with a larger hash such as SHA-512, though
an updated DSS standard has not been specified yet.

> Revoking an RSA key and re-issuing a longer one might be a pain, but
> there's no option for that in the current GPG implementation.

A few details on GnuPG, since I have intimate knowledge of that software
and OpenPGP in general:

While the current version (1.0.6) of GnuPG cannot generate RSA keys, it
*can* use them. If you have a version of PGP 7.x, you can generate RSA v4
keys up to 4096 bits, and then use them with GnuPG.

GnuPG 1.0.7 is slated to allow for the generation of RSA v4 keys. I think
it's safe for everyone to wait until that comes out, since the threat of
1024 bit keys being broken is not an immediate one for most threat models.

Also, the major attacks to protect against with OpenPGP are ones that are
undetectable by the intended users. For instance, if a flaw were found
that allowed an attacker to decrypt PGP messages simply by "doing things"
to them after they were intercepted over the wire, it would be huge.

In PGP, you have a 1024 bit DSA key as the master signing key. Breaking
this would allow an attacker to forge signatures of yours (bad, but
detectable, and only a real concern if you are using signatures in a
critical environment, such as part of an authentication scheme) or bind
new subkeys to your key.

It is the subkeys that are used for encryption, and these are ElGamal
keys, which are also based on the discrete log problem, but are up to 4096
bits in size, so Bernstein's attack shouldn't be an issue if we're
assuming they're roughly equivalent in strength to RSA, taking this into

The way an attacker would exploit this weakness in order to read encrypted
mail would be to modify your key to attach a bogus encryption subkey to
it, and hope that people you communicate with encrypt to the bogus subkey
instead of the real key. This won't go unnoticed for long, and doesn't get
him past encrypted information, either.

So, I'm not too concerned about GnuPG presently, though I am going to
bring up the issue of stronger DSA keys with the IETF working group.

Remember, the main change in opinion after Bernstein's paper is that 1024
bit keys are no longer "safe forever".

Far more frightening is that 512 bit keys are still in use, and can be
broken in weeks by anyone with a few grand to throw at it (even without
Bernstein's improvements).