Subject: Re: [TLS] I can has SHA-1 hashes for RFC 2409/3526 MODP groups?

From: Henrick Hellström <[email-masked]>
Date: Sat, 01 Mar 2014 16:01:38 +0100

On 2014-02-28 22:22, Geoffrey Keating wrote:
> I'd encourage you to do the derivation again: compute
>
> 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
>
> and verify that it's prime.  I don't think any special security
> measures were taken during the creation of RFC 3526, you'd think by
> now someone would have noticed if the 'primes' weren't prime or didn't
> match the claimed polynomial, but if everyone thinks someone else has
> checked...

There is more.

1. The MODP primes are supposed to be safe primes (i.e. primes on the 
form p = 2q+1 where q is also prime). Furthermore, 2 will be a generator 
of the large sub group of order q, rather than of the entire 
multiplicative group of order 2q.

2. Pi might be calculated using the Bailey–Borwein–Plouffe formula. I 
calculated it for the first 2048 hexadecimal digits, which was a 
sufficiently good approximation for all of the MODP groups up to the 
8192 bit one.

3. All of the MODP primes are on the form p = 2^n - 2^(n-64) + 2^64( 
[2^(n-130)pi] + k). The value k is supposed to be the least positive 
integer, such that p is a safe prime. This check is important, to rule 
out that any candidates have been deliberately skipped, because they 
lack some (hidden) property.

I have generated the primes 1024, 2048, 3072, 4096, 6144 and 8192 from 
the formulae and verified that:
a: The numbers match the numbers in the RFCs.
b: The numbers are safe primes (using both Miller-Rabin tests and Lucas 
tests on q = (p-1)/2, and then the Pocklington Criterion on p).
c: The small constant k is indeed the least positive integer such that 
the number is a safe prime. (Well, to be honest I am still running this 
test for the largest group, just make sure once more.)

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 7 Mar 2014 12:13:02 +0000

=?UTF-8?B?SGVucmljayBIZWxsc3Ryw7Zt?= <[email-masked]> writes:

>I have generated the primes 1024, 2048, 3072, 4096, 6144 and 8192 from the
>formulae and verified that:
>
>b: The numbers are safe primes (using both Miller-Rabin tests and Lucas tests
>on q = (p-1)/2, and then the Pocklington Criterion on p).
>c: The small constant k is indeed the least positive integer such that the
>number is a safe prime. (Well, to be honest I am still running this test for
>the largest group, just make sure once more.)

Ah, OK, thanks.  So we've got independent verification :-).

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 8 Mar 2014 11:57:10 +0000

Henrick Hellström <[email-masked]> writes:

>The problem with calculating the hash of the internal representation, is that
>the hash will depend on the internal representation, which is prone to be
>implementation specific. Is it little endian or big endian? Is there a zero
>valued word in the most significant position or not?

I don't need the hash of the internal representation (my code does its own
integrity checking, so once it's in the internal form it's protected, at least
from random corruption), just of the byte-string representation of p as
stored/as present in the RFC.  So for example for the 2048-bit MODP group it'd
be the SHA-1 hash of, in C notation, { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xC9, 0x0F, 0xDA, 0xA2, ... 0xFF }.

Peter.