# Lightweight primality certificates for untrusted DH parameters

Are there any light-weight techniques to generate primality certificates for custom Diffie-Hellman parameters that could be sent to the client to allow it to verify primality without needing to run its own expensive rounds of primality testing? By lightweight, I mean not significantly harder than the recommended number of Miller-Rabin rounds on the generation side, and significantly less intensive during verification (after all, there's no point if it doesn't make life easier for the client).

• I'm not qualified to answer. I'm guessing your choice to use custom parameters is to prevent attacks involving precomputation. I suspect the implementation might be too risky or inconvenient. Choosing large enough key spaces, I think, makes the DH precomputation attack I recall infeasible. I don't think the same attack works for ECC either. There are some positives to using fixed parameters. It's possible to optimize code better and may be less work to check for correctness. Your security level to resource consumption ratio can possibly be better with say curve25519. – Future Security May 16 '18 at 4:50
• @FutureSecurity Security from DH does not come from the keyspace, but you are right that the difficulty of precomputation. However, if a technique is found that can break 2048-bit DH in, say, a year for $100 million, generating custom parameters is the difference between one broken key exchange and an unlimited number of broken exchanges. – forest May 16 '18 at 5:30 • @forest Use X25519, and batch attacks don't scale like that. Plus you'll get faster cheaper safer smaller implementations. – Squeamish Ossifrage May 16 '18 at 14:10 • @SqueamishOssifrage I know that ECC can be better, but I'm not wondering what the best key exchange technique is (otherwise I would just use an x25519-NewHope hybrid handshake and call it a day). – forest May 18 '18 at 0:09 ## 1 Answer Well, one possibility to generate a moderately lightweight certificate would be to use this theorem: If we have values$p, q, g$such that: •$1 < g < p$•$q > \sqrt{p}$•$q \mid p-1$•$g^q \equiv 1 \pmod p$•$q$is prime Then$p$is prime. So, for a certificate, we would have a list of$(p_i, g_i)$values such that$p_{i-1}, p_i, g_i$meet the above conditions (as$p, q, g$), with$p_0$is the value$p$we're actually interested in proving, and the final$p_n$value is a prime small enough to make primality proving trivial (e.g. it may less than 16 bits long). Each line in the certificate (almost) halves the value of$p_i$, and so the total number of lines is managable. As for verifying the certificate, it should be fairly obvious, for each line in the certificate, we would check the first four conditions directly, and then step to the next line to verify the last condition; as the last step, you'd do a quick check that$p_n$is prime. The expensive part is the$g^q \equiv 1$condition; if you total it, it's a bit less than a single Miller-Rabin computation (but has the advantage that it is deterministic; if it validates, there is no need to do a second iteration). Whether this counts as 'significantly less' is something you'll need to decide. As for generating the certificate, you can't select a random$p$and try to generate the certificate. Instead, you would create the certificate (and the prime) from the bottom-up; select a$p_n$, and then at each step, given$p_i$, you would search for a prime value$p_{i-1}$(and$g_i$, but that's easy), eventually ending up with a$p_0$value of the desired size. The FIPS 186-4 Shawe-Taylor algorithm does exactly this (you'll just need to record the intermediate$p_i, g_i$values). As a side effect,$g_1\$ is an appropriate generator for the DH group (as it generates a large prime-sized subgroup).

On the other hand, I would second Future Security's suggestion to the ECDH instead; that uses less resources, and doesn't have any known 'solve this problem and break the entire group' attacks

• Is this a more efficient technique than, say, ECPP certificates for larger primes? – forest May 18 '18 at 1:23
• @forest: yes, both for generation, and (to a lesser extent) for verification. On the other hand, ECPP certificates can be generated for any prime; for the above procedure to work, you need to generate the prime and the certificate at the same time. – poncho May 18 '18 at 2:53