Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've a couple of questions about this, the scenario is embedding a key pair in a hardware device which will speak with other hardware devices over tls. computing resources are an issue so i want to make intelligent choices about where they go on. We're using TLS to authenticate one device to another, and to ensure integrity of messages in transit. Immediate or long term confidentiality of messages is not a consideration.

  1. All the recommendations are in the case of RSA to use 2048 bit keys because that will be secure until 2030. However, in my application the RSA key is used only to provide a TLS handshake for the lifetime of that key on that device, so it doesn't need to remain secure until 2030. The AES session key is renegotiated every 24 hours and beyond that it doesn't need to be confidential. TLS is being used to ensure integrity in transport only, the communicated data doesn't need to be confidential.

    I'm aware 768 bit numbers have been factored, but my understanding is that factoring one 768 bit number does not help much to factor other 768 bit numbers. I haven't found docs to say how long it takes to factor a number of X bits with equipment Y. As an an example I'm going to say 5 years with budget X and equipment Y to factor 768 bits - then people can tell me if the following analysis is solid or not.

    E.g. my device will be in use for the next 5 years. I choose RSA 768 as key size and I change the keys every 12 months. From day 1 an attacker tries to do every attack he can on the TLS crypto. After 2.5 years technological advances mean he can recover my RSA year 1 private key. However the year 1 can no longer be used to establish a TLS session so there's no impact there. The attacker can also recover the session keys of year 1 which were negotiated with the RSA year 1 key, but as the confidentiality of year 1 data wasn't important there is similarly no impact.

    So given this why aren't RSA key size recommendations given in terms of attacker motivation, key lifetime, key usage rather than blanket recommendation of 2048?

  2. Practicalities of generating keys / certs on build machines. Being conservative I'd say this should be avoided, would it be reasonable to generate device keys via an OpenSSL script with FIPS options on an up to date build machine with appropriate controls, or should there be a hardware crypto-module ? Or put another way, would an expert witness lambast us in some possible future court case if we had generated device keys in software on a build machine or is that a reasonable way to go about things ?

  3. If I tried to factorize RSA 768 on my home PC and I was a competent mathematician, how long would it take me? Same question but I have access to a computing cluster. It seems that in 2009 the factorizing took 3 years, 6 labs, many mathematicians and hundreds of computers..

share|improve this question
Have you considered ECC? It has a better security/performance trade-off for most applications. For example a 225 bit curve has security comparable to RSA-2048. –  CodesInChaos Jan 9 at 10:01
This paper, says "a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one". This answer says that "a 512-bit RSA key ought to resist at least a few days, more probably a few weeks, even against determined attackers". $\;\;\;\;$ –  Ricky Demer Jan 9 at 10:05
thanks. i found this other answer too which says that rsa 512 is beyond an 'amateur' effort in 2012. security.stackexchange.com/questions/4518/… –  dancl Jan 9 at 10:08
ECC could be an option but not right now for other reasons, not all the devices on the network support it. I think the same question would come up though, NIST recommendations are blanket, whereas some applications do not require the same level of protection as others –  dancl Jan 9 at 10:10
I would guess that the "many mathematicians" part is something that does "help much to factor other 768 bit numbers". $\:$ (That is, if I'm right then another such factorization should not require so much expertise.) $\;\;\;$ –  Ricky Demer Jan 9 at 10:17
show 1 more comment

1 Answer

up vote 3 down vote accepted

1. To clarify: The critical time period here is one year (after wich the certs are changed). With the cracked RSA key the attacker can decrypt the traffic and do nan-in-the-middle attacks, posing as a valid hardware device.

Let us take the numbers determined by experts. In their paper on cracking the 768-bit RSA key the researchers state that they needed about $2^{67}$ instructions. When you look up current pricing for the Amazon EC2 cloud you get two Intel Xeon E5-2670 for 2.4\$ per hour. That is roughly $$2 CPUs \times 3\ GHz \times 8\ cores \times 8 FLOPS/cycle = 384\ GFLOPS$$ for 2.4\$/hour. That makes the cost of cracking a 768-bit RSA key about a quater million Dollars (on CPUs). Or 143 instances working for one month, or 1000 instances working for 4 days, etc. This is of course very simplified but gives you a rough idea.

Computing power doubles every 2 years and with special hardware, like GPU computing you can significantly lower the pricetag (modern cards operate in the order of TFLOPS see specs on AMD or NVIDIA websites).

A computer packed with 3 GeForce GTX 780 Ti (cost all together about 3000\$) can achieve 15 TFLOPS. This cracks a 768-bit key in 113 days, well under one year. So your key is definitly not safe from a moderatly determined attacker.

As for a 1024 bit key they state it would take 1000x more time or money. Very costly, but totaly out of reach in 5 years?

Other sources state a 2048 bit key would take $2^{32}$ times longer. So you are definitly save here.

But if I understand your scenario correctly you might be able to avoid the problem altogether: The computing cost of a larger RSA key only has to be paid once. During the inital handshake of the connection (generating the AES key). If you do not have a higly dynamic environment (meaning devices coming and going all the time) this cost will not matter much.

2. For generating a few certificates a year you do not need a special module. This is only neccessary if you need massive amounts of randomness/entropy (e.g. if you need to produce a cert every second). Here is command to find out the (estimated) entropy of your system on Linux:

cat /proc/sys/kernel/random/entropy_avail

I would be more worried about the entropy available on those hardware devices (needed for the TLS handshake). If they are very simple microcontroles that might be a problem.

3. Kind of answered that in question one.

Hope that helps!

share|improve this answer
that pretty much answers it - thanks. one question though, regarding the polynomial selection referred to in the factoring 768bits paper which is apparently a big chunk of the factoring effort. are the polynomials used in that paper equally useful for any 768 bit number, or does the polynomial selection effort have to be undertaken for each different number ? –  dancl Jan 9 at 21:03
Also, good point about the entropy of those devices. Is there any way to quantify that problem, what's the worst case scenario if there's poor random number generation from some of the devices on the network. I guess an attacker would determine a set of possible random numbers and brute force keys in that space.. so it comes down to is that space sufficiently small that an attacker can brute force it in the session keys lifetime –  dancl Jan 9 at 21:18
Quantifing entropy is a very difficult endavor. There are some standards FIPS 140-2 and some tools (search for rng-tools on Linux). But there is no general rule.Poor random numbers open up a whole new question. Generally it makes a range of attacks possible that drastically reduce the search space for the attacker. Generally if you can reasonably predict these values key size will not help anymore. On Computers entropy is introduced by sources that are not predictable by the Computer itself (like noise on Audio port, Network traffic, Keyboard, etc) if you do not have any entropy suffers. –  PSi Jan 9 at 22:15
While we're here, is the factoring time the worst case ? e.g. if takes 100 days to factor a N bit number does that mean that the attacker has a 50% chance to find the factors in 50 days ? –  dancl Jan 10 at 13:01
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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