4

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?

4

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.

  • 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 Jul 22 '15 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 Jul 22 '15 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 Jul 22 '15 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 Jul 22 '15 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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