Score:5

DDH hardness with shared public parameters

ps flag
bs-

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?

Score:7
ng flag

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.

Score:6
in flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.