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

From: Peter Gutmann <[email-masked]>
Date: Fri, 28 Feb 2014 12:20:47 +0000

I can has SHA-1 hashes for RFC 2409/3526 MODP groups?

The MODP groups for DH specified in RFC 2409 and 3526 seem to be widely used
in things like SSH and SSL/TLS, however unlike the RFC 5114 groups there's no
subgroup given and so no way to verify that the prime hasn't been corrupted in
some way (the generator is easy, it's always 2).  OTOH the RFC 5114 groups
have stupid generators so I don't know why anyone would use them.

In any case I'd like to have a means of verifying the validity of the data for
the RFC 2409/3526 primes as stored in memory, but if I generate my own SHA-1
hashes then there's the risk that I'm verifying flawed data.  Does anyone have
SHA-1 hash values for the RFC 2409/3526 primes, i.e. the 1024/1536/2048/etc-
bit values in the two RFCs?  The values I've got are:

RFC 2409, 1024-bit prime: c0 33 bd 43 51 fb a3 73 25 45 ea 2e 01 6d 52 b0 ...
RFC 3526, 1536-bit prime: 49 ec ab a9 72 7a 1a f0 63 60 82 c4 67 48 5a 1a ...
RFC 3526, 2048-bit prime: b9 5c 79 9a a5 dd 38 8c 6d f5 e7 23 98 cb 9d 7d ...
RFC 3526, 3072-bit prime: 94 1a 04 77 38 fe 55 33 33 69 e2 b3 86 b6 d6 18 ...

Peter.

---

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.)