Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
DDH is believed hard for subgroup of $ℤ^*_p$ with order $q=(p-1)/2$ when $p$ is a safe prime chosen randomly.
What if $p$ isn't random: When parameters are shared, $p$ mightn't have been chosen randomly—primality can be tested, random sampling cannot—is DDH still believed hard, are any security concerns created/mitigated?
For a given size of $p$, random $p$ are believed safer than $p$ chosen by an adversary, at least w.r.t. the state of the art in computing Discrete Logarithms (which is enough to break DDH).
This is because for $p$ of the form $r^k\pm s$ for suitably small $r$ and $s$, a special algorithm is available for the Discrete Logarithm Problem (broadly, a DLP-oriented variant of SNFS) that is considerably faster than the best one known for most other $p$ (broadly, a DLP-oriented variant of GNFS).
As far as I understand, this 1024-bit DLP record by SNFS could have been carried with comparable ease with the 1024-bit safe primes $p=2^{1023}+1671615$ or $p=2^{1024}-1093337$, when the later record for arbitrary safe prime is 795-bit, with more effort.
Answers to this closely related question might help.
If one wants to delegate the search of a safe prime (although it's not very hard), an option would be to ask that all except say it's low-order 64 bits are output of some PRF (e.g. SHAKE-128) for a stated (or specified) input.
A similar method is used in the standard Oakley (aka MODP) groups of RFC 2409 and RFC 3526. These are intended to block SNFS, but still allow welcome simplifications and a modest speed improvement in normal use of the group.
Don't miss the important point made in that other answer that fresh $p$ are safer.
Even if we have no adversary picking the prime, a fixed public prime used often can be an issue. The time to break DH can be mostly shared across multiple instances of the problem with the same public parameters. So if the size of the prime makes it horribly expensive but not impossible to solve the problem, we might find nation states using dedicated hardware and months of crunching breaking common used values. And having only a much smaller on line phase when a specific key exchange is captured.
While using new random not commonly used paramaters would be much safer.
There are some hints in the Snowden leak suggesting this might have happened. We didn't see any cryptographic details, but the descriptions of how captured communication are sent to decryption and the partial success rate and response times are consistent with such an attack.
