11
$\begingroup$

I created my PGP key in 2000. I’ve revoked the older, weaker sub-keys in favor of a 4096-bit RSA one, but the primary key is 1024-bit DSA. I read on Wikipedia that…

NIST 800-57 recommends lengths of 2048 for keys with security lifetimes extending beyond 2010.

  1. Should I consider my primary key insecure?
  2. If so, is there any way to replace it without revoking my entire key and creating a new one?
  3. If my primary key were compromised, the attacker would be able to create signatures as me, but they wouldn’t be able to decrypt information that was encrypted to my public key, right?
$\endgroup$
3
  • 3
    $\begingroup$ Not a direct answer, but I generally use keylength.com (NIST and ECRYPT recommendations) as good indicators for key strength. $\endgroup$
    – Maarten Bodewes
    Aug 20, 2013 at 19:21
  • 2
    $\begingroup$ I don't know if the PGP software you use supports this, but given that the trust system conforms to the "web of trust" model, the best way to replace your key would probably be to first generate a new key, then use your existing key to authenticate your new key to your contacts, before you revoke the old one. $\endgroup$ Aug 23, 2013 at 6:14
  • 1
    $\begingroup$ What's the size of the subgroup q? If it's only 160 bits, this is probably a weaker point than the 1024 bit modulus. If it's 224 bits it's clearly strong enough. $\endgroup$ Jun 19, 2014 at 12:38

2 Answers 2

8
$\begingroup$

"Secure" is not a binary, black-and-white thing. Instead, it's about risk management. Instead of asking whether something is secure, it's better to ask whether it is "secure enough for such-and-such purpose". On the one hand, 1024-bit keys are uncomfortably close to what can be cracked, given lots of computational resources. On the other hand, for casual use, it's probably fine, and there's no need to go through a painful exercise to replace your key. But if you're generating new keys, these days it'd be a good call to use a 2048 bit key.

On your third question, someone who recovers your 1024-bit private signing key today would not be able to decrypt past ciphertexts, but they would be able to mount man-in-the-middle attacks on you in the future (which would let them decrypt information that anyone encrypts to you in the future), assuming they are willing to mount active attacks.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer. Could you add a sentence or two addressing my second question? $\endgroup$
    – bdesham
    Aug 21, 2013 at 20:45
  • $\begingroup$ @bdesham, sorry, I don't know the answer to your second question. I don't know of any way to replace it without revoking it and creating a whole new key, but maybe someone else will know. $\endgroup$
    – D.W.
    Aug 22, 2013 at 0:44
4
$\begingroup$

1 . Should I consider my primary key insecure?

It depends who you are trying to protect yourself from. AIUI based on the best known cryptanalysis 1024 bit RSA and DSA keys could be cracked by a well-funded attacker (I've seen the math run for RSA, not sure about DSA but AIUI they give similar security at a given key length) but it would probablly be cheaper to track you down and beat the key out of you.

Of course it is possible that government spooks have discovered cracking algorithms that are more efficient than the best ones that are publicly known.

For new keys generated now 2048 bit RSA is considered the minimum with the more security-paranoid groups generally recommending 4096 bit. Some prominent cryptographers even recommend going higher than that.

2 . If so, is there any way to replace it without revoking my entire key and creating a new one?

No, there is no way to replace the primary key other than creating a new one from scratch and telling your contacts to use it. Depending on how paranoid those you communicate with are they may accept a transition statement signed by your old key or they may require you to confirm the key is yours by out of band means.

It's also considered good pratice to sign the new key with the old key (but not vice-versa).

AFAIC most people don't revoke the old key immediately but I'm not sure what the pros/cons of that are.

3 . If my primary key were compromised, the attacker would be able to create signatures as me,

Yes

but they wouldn’t be able to decrypt information that was encrypted to my public key, right?

AIUI encrypted messages are encrypted to a particular subkey. The attacker would not be able to decrypt messages encrypted with your existing subkey.

They could mark your existing subkey as revoked, add a new subkey and upload the result to the keyservers. People who downloaded the updated key would then encrypt messages to the attacker's subkey. However unless they had total control of your communications it would be very hard for them to do this while remaining undetected.

$\endgroup$
1
  • 3
    $\begingroup$ AFAIK a DSA cracker requires a few hundred times the RAM of an RSA cracker, so I'd assume that cracking a DSA key is a few hundred times more expensive than cracking an RSA key of the same size. Further evidence towards DSA being stronger is that the largest solved discrete logarithms over prime fields are smaller than the largest factored semi-primes. $\endgroup$ Jun 19, 2014 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.