4

Is a 512 bit RSA key secure when a new key gets generated and used approximately once a week? The key is only used for signing messages, not for encrypting sensitive data.

This is for a system where there are many extremely short lived connections p2p (think one UDP packet as a request, and one back as a response), and the overhead for 1024 or even 2048 bit RSA is very high.

Ali Ahmad
  • 4,784
  • 8
  • 35
  • 61
orlp
  • 391
  • 2
  • 15

3 Answers3

9

For signing only, a 512-bit RSA key ought to resist at least a few days, more probably a few weeks, even against determined attackers. This is still "reasonable" as long as you verify the signature "soon". You can imagine that from the point the public key was made public, you have a few minutes, at best hours of security, after which you must consider the key as expired and refuse to trust signatures computed with that key.

I find your use case a bit dubious, though. Generating the RSA keys will be quite expensive with regards to computing a signature. If you worry about signature size, then you should investigate DSA or its elliptic curve variants. ECDSA with a 160-bit curve will use 320-bit signatures (quite smaller than 512-bit signatures for RSA-512) while being substantially stronger (ECDSA with a 160-bit curve is still beyond the technologically feasible) and will still be competitive with regards to CPU usage.

Also, the hard part of asymmetric cryptography is key distribution (that's what PKI is about); if you generate many keys, you only make that part harder.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 1
    Thank you, ECDSA seems to be exactly what I want. I'm new to cryptography, and it seems I was trying to hammer in a screw instead of using a screwdriver :) – orlp Jan 08 '13 at 08:31
  • 1
    Actually, considering I'm writing in Python and there is a binding simply available __and__ it does what I want I think I'll settle for ed25519. – orlp Jan 08 '13 at 08:44
3

Time isn't that important. The question is how much money that attacker is willing to spend. From what I heard, breaking RSA 512 currently costs 75-150$ and 30 hours using cloud computing.

We have a very similar question on crypto.SE: Is 512-bit RSA still safe for signature generation?

But have you considered using elliptic curve crypto? For example the Curve25519 implementation in NaCl can do >10000 key-exchanges per second on a modern computer. It doesn't sign, but it uses authenticated encryption, which typically works well in a request-response scheme. If you exchange several messages with the same party, you can cache the result of the key exchange, and still authenticate all of them. If you really need to sign, you can use Ed25519 which has pretty similar performance.

Community
  • 1
CodesInChaos
  • 11,854
  • 2
  • 40
  • 50
2

The general metrics is that the key space should be big enough that the key cannot be guessed within the time the transmission should be protected.

I'm afraid I don't know off the top of my head what the average time to brute force a 512 bit RSA key is with current computers.... but that's the value I'd be looking for, and then compare that to how long you need the integrity check to be viable. For example - if the integrity check only matters for the life of a connection (minutes) then you may be fine, but if the integrity check is on a message that is stored and then later checked and trusted, after the week is over, then your key validity is really more than a week and you (probably) need a bigger key space.

bethlakshmi
  • 11,606
  • 1
  • 27
  • 58