|
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)
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 account. 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). --Len.
|