Discrete logarithm key sizes for very short term usage

Question

We have this special use case that our session typically only last for less than 30 minutes, no more than 1 hour at most, after the session finished, the information protected does not matter. Each time a new session start, a new group (p, q, g, k) choose randomly, where p=k*q + 1, g is the generator of subgroup q, p, q are both large prime, k and q coprime; I known if sizeof p = 1024, sizeof q = 160 is good enough, but it's a bit slow and consume too much power on smartphone, since our session only live very short term, I'd like to known if its safe to choose shorter group size, say p=512, q=160, or even shorter p=256, q=112?

any comments would be appreciated

Answer 1

If:

1. You're okay with the encrypted information being easily decrypted after the session
2. You have a guarantee that the session won't be very long
3. You use random and unpredictable safe primes $p$ every session

I think it should, theoretically, be okay to use slightly smaller bit lengths for $p$.

That said, in practice it is probably a bad idea, and it's better to use ECC as @CurveEnthusiast mentioned. Generating safe DH primes is non-trivial, judging by how many implementations screw it up. And in the case of smaller groups, it is absolutely crucial that you generate random and unpredictable safe primes for every session (otherwise, someone can simply do a large amount of precomputation on the group, and crack connections using that group very, very quickly -- see Logjam).

What is your threat model? How much computing power does your attacker have at his disposal?

For reference, the authors of the Logjam attack in 2015 cracked several 512 bit groups in a week. They estimated that this could be optimized by a factor of 3, and they deliberately spent more time on precomputation. How fast do you think a state actor could break a 512 bit key exchange? It's not inconceivable to think that with a huge amount of computation power, and some very clever optimizations, a state-level adversary could do it in a few hours.

In short, it's not worth the risk. You run a big risk of improperly generating the weaker DH groups. You run another big risk of reusing the weaker DH groups, or having them be predictable, thereby opening yourself up to precomputation attacks.

Try ECC curves instead, and see if they don't alleviate your time/power consumption issues.

Answer 2

The following snippet is taken from the RSA Lab website. Although this website has apparently not been revised since 2000 (so do not rely on the key size suggestions given there), I think this quote is still relevant today.

The best size for a modulus depends on one's security needs. The larger the modulus, the greater the security, but also the slower the RSA algorithm operations. One should choose a modulus length upon consideration, first, of the value of the protected data and how long it needs to be protected, and, second, of how powerful one's potential threats might be.

It is not reasonably possible for anyone to give an assessment on the "safety level" of your algorithm without taken the attacker model into consideration. That is, what is your so-called "potential threat"? Is it a state agency trying to attack you in the given 30-60 minute slot, or your little sister with pen and paper?

Having that said, although possible in some scenario's, solving crypto problems by simply reducing the security level is very dangerous territory, and should take very serious consideration. Perhaps there are better ways to solve your problems. For example, elliptic-curve cryptography could potentially achieve the same cryptographic goals with lower energy necessity.