Trouble with diffie-hellman groups

Question

Is anyone able to point me towards a known-to-be-good diffie-hellman group? I currently use group 24 (RFC5114, 2048-bit MODP Group with 256-bit Prime Order Subgroup). It came to me that this group is not adequate even for AES-128 (this is according to www.cryptopp.com/wiki/Diffie-Hellman)...so far it seems my only options are 1) generating a diffie-hellman group myself, but I don't want to do this when I don't know whether the group I will generate has the ideal properties or 2) Have the application generate a new, adequate diffie-hellman group on the first session start... I would like to avoid this, because it introduces a lot of unnecessary complication on the already complicated system.

In short, my need is to include a pre-generated diffie-hellman group on my application, but I don't want to generate this group myself and include it (and neither do I want to generate a diffie-hellman group on the first session start).

I have also looked into RFC3526 but even the biggest group there (group 16, 8192-bit MODP Group) is not strong enough for my needs according to NIST guidelines (I need at least AES-256) the RFC also doesn't specify the strength of the prime-order subgroup, which further annoys me, it also doesn't specify how, where, when, or under what criteria those groups were generated (RFC5114 got its groups from NIST).

The only groups that satisfy are the elliptic curve diffie-hellman groups, but I do not have the necessary support for elliptic curve diffie-hellman, and already got diffie-hellman implemented.

I seem to have hit a dead end here, can anyone chime in?

Answer 1

Well, the question you should be asking "what are my security goals" and only then start addressing which cryptographical primitives (DH groups) meet them.

I rather suspect that your real security goals fall rather short of "unless someone can perform $O(2^{256})$ operations, they can't break it".

So, the real question is "can anyone who will attack my system be able to break the 2048-bit group"? Note that the largest published effort in this area was roughly equivalent to breaking a 768 bit DH key (actually, that was a factorization effort; it is believed that using Number Field Sieve, the effort involved with solving a Discrete Log on a similarly sized modulus would be approximately the same). Note that the US Government allows 2048-bit DH modulii to protect sensitive data; it would appear that that's good enough for them.

In addition, as for RFC 3526, the RFC does give estimates of the strength (see section 8; note that it gives two estimates; that's because no one is quite sure how NFS scales, and different knowledgeable people have estimated the exact strengths differently); as for how those were generated, well, those are all of the form $p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$, where $i$ is the smallest nonnegative integer such that both $p$ and $(p-1)/2$ are prime (and they also list the value of $i$). As for how that was selected (and the reasoning behind it), see RFC 2412 appendix E.