5

While pondering a question on SO about efficiently generating signed private-content URLs for CloudFront I decided to check what sorts of savings could be found by using a shorter RSA key. With the 2048-bit key AWS generates, our signing method runs in around ~1550µs on my laptop; using a 512-bit key cuts this down to ~113µs.

We sign the links to grant paid users access to media files for a given number of minutes, and have already been using the equivalent SHA-1 HMAC signing process for gating access to the same files on S3. The vast majority of the requests our server fills are for these signed URLs.

How acceptable/unacceptable is it to use a short length for a key dedicated to this purpose? What qualifies as acceptably long/short?

1 Answer 1

5

Right now (July 2015), the current record for RSA key breaking is for a 768-bit modulus, and it took two years of computations with a lot of machines, and, importantly, with some very fine brains too. A notable point is that the best known RSA-breaking method (that was used for RSA-768) is integer factorization with the General Number Field Sieve; GNFS does not benefit from any kind of "precomputation". This means that the people who factored the 768-bit RSA key, if faced with another 768-bit RSA key to break, would again have to spend two years on the job.

As for 1024-bit RSA keys:

  • they are currently unbroken;
  • they could be broken with existing technology, but it would require throwing at the problem a non-negligible number of millions of dollars to build a dedicated machine that would be good only at breaking 1024-bit RSA;
  • ... and even that machine, if it is ever built, would still need a lot of time (months, possibly years) to break a RSA key.

In your case, if signatures only need to resist for a few minutes, then you could generate a new RSA key every day, and this will defeat GNFS-based attackers as long as breaking a 1024-bit RSA key takes more than a day, a property which is quite likely to hold for the next few decades. A good point (for you) is that since your signatures become obsolete quickly, you "just" have to keep track of scientific and technological advances: the day some people succeed at breaking a 1024-bit RSA key, you can switch to 2048-bit keys; you do not have to do it in advance.

4
  • Thank you for giving both a lucid answer to the immediate question and enough insight into your reasoning that it should be easy to apply even as the specifics change.
    – abathur
    Commented Jul 22, 2015 at 13:26
  • The only caveat to that is a patient attacker that is logging all traffic on the network. They could then use the keys to decrypt the traffic even years later, so those paid-content media files could be decrypted after enough time. If that's a problem, then a higher-strength encryption level would be better.
    – Aaron D
    Commented Jul 22, 2015 at 13:54
  • 1
    @AaronD The media files themselves are not encrypted (HTML5 video, etc.) The generated signature is just used by CloudFront to verify that the time-limited URL used was both generated by us, and hasn't been tampered with.
    – abathur
    Commented Jul 22, 2015 at 14:41
  • 2
    @AaronD: that's the point: we are not talking about encryption but signatures. If a new key is generated every day, then it does not matter if an attacker breaks a key that was used two years before -- it won't be accepted anyway. This highlights that encryption and signatures use really distinct security models.
    – Tom Leek
    Commented Jul 22, 2015 at 15:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .