Re: [Cfrg] Question about primes of special form and the NFS

[Daniel Kahn Gillmor <[e-mail]>]

Hi all--

On 03/30/2014 05:48 PM, Samuel Neves wrote:
> On 30-03-2014 21:43, Watson Ladd wrote:
>> Dear all,
>> draft-gillmor-tls-negotiated-dl-dhe-00 contains primes of the form
>> 2^{b}-2^{b-64}+k*2^64-1 for b a multiple of 64 and k small, and
>> recommends them as DHE groups. This is to close a security hole in TLS
>> in which no set of DHE parameters exists, and no one realized they
>> can't be validated.
>>
>> This is not as bad as primes of the form 2^b-small, for which the SNFS
>> applies trivially. However, I am worried that some of the speedups
>> might still happen. It's probably not possible, but I don't know the
>> state of the art in this area, and would appreciate any references
>> dealing with extensions of SNFS to numbers that aren't that special.
> 
> These primes do look risky. Oliver Schirokauer has done some work on discrete logarithms modulo primes with small signed binary representation [1], which applies in this case.
> 
> Manually finding small-coefficient NFS polynomials for these primes also seems plausible, which is what differentiates the SNFS from the GNFS. For example, for the 4096-bit prime p = 2^4096 - 2^4032 + 341664 * 2^64 - 1, degree 8 and m = 2^504, we obtain
> the polynomial
> 
> (2^64-1) * x^8 + (341664 * 2^64 - 1) * x,
> 
> which has significantly better coefficient sizes than a random choice of polynomial.
> 
> [1] http://eprint.iacr.org/2006/107

Thanks to Watson for raising this question to the group and thanks to
Samuel for his prompt analysis.  The choice of primes for this draft are
not set in stone, and i really value the feedback of this group in
choosing a good set.

My current selection looks for safe primes of a reasonable size that can
provide efficient forms for common operations, while avoiding re-using
discrete log groups that are already used elsewhere (to reduce the value
of any particular group as a target for a powerful adversary).

The general form of the construction used in RFC 3526 (high and low
words all-ones, with the middle bits selected by deterministic search
over a known space, with no magic numbers selected) seems reasonable to
me; if anyone has any stronger recommendations for better mechanisms to
generate groups acceptable for public use, please share them.

If there are no other concrete recommendations, i'll replace the groups
in the next draft of tls-negotiated-dl-dhe with groups with non-sparse
prime moduli derived using the binary representation of e instead of
all-zeros for the central bits (this is similar to the use of pi in the
creation of the 3526 MODP groups, but wouldn't share the groups across
protocols).

I'd be happy to hear any suggestions or concerns about this approach, or
any other commentary on the draft.

Regards,

	--dkg