DL_Group X9.42 issues

[neverhub]

@jurajsomorovsky and i were looking at https://github.com/randombit/botan/commit/10555509dae09778b8d6e1831f837423490ca2c0 and wondered, why the named groups modp/srp/1024 and modp/srp/2048 did not pass the group validation (but they should) and noticed problems with these groups and the Botan DL_Group generation process with strong primes.

The X9.42 standard defines the 3 DL_Group parameters: p: A prime defining the Galois Field GF(p), which is used as a modulus in the operations of GF(p). q: A prime factor of p-1. GF(p) has a cyclic subgroup of order q. g: A generator of q-order cyclic subgroup of GF(p), that is, an element of order q in the multiplicative group of GF(p).

When validating a X9.42 DL_Group we have to perform the following tests:

1. q is a factor of p-1: (p-1) mod q = 0
2. g has order q : g^q mod p = 1
3. q is prime
4. p is prime

The srp groups are defined in [RFC 5054]. There only g and p are specified. modp/srp/1024 and modp/srp/2048 in dl_named.cpp have q set to (p-1)/2 (which is prime). Unfortunately the given generator has order q but instead 2*q (p-1) in these groups. Therefore g^q = -1 mod p applies and the verification fails. So q should not be set for modp/srp/1024 modp/srp/2048, as the selected generators are not X9.42 compatible.

A similar issue exists, when generating a new DL_Group of type=strong. In this case Botan samples a safe prime p = 2q+1 and sets generator g = 2. Groups generated this way, may fail the validation too, as g might have order 2q (p-1) instead of q, as required by X9.42.

To be X9.42 conform Botan should ensure, that the generator g has order q. This is achieved by squaring g, if it does not have order q. Alternatively we could just omit q when generating a DL_Group with safe primes.

An additional minor issue: openssl uses the pem header/footer "X9.42 DH PARAMETERS", while Botan uses "X942 DH PARAMETERS"

[neverhub]

Quick example of Botan generating invalid X9.42 DH parameters.

./botan gen_dl_group --type=strong --pbits=512| openssl dhparam -check -text
    DH Parameters: (512 bit)
        prime:
            00:d3:6a:eb:3f:49:72:1b:ea:90:6b:ba:09:ea:45:
            72:b1:47:19:56:ad:81:bb:6c:b2:f9:58:a7:ac:73:
            93:1d:0e:23:e0:04:2c:21:6b:f3:02:a9:41:e2:27:
            d5:58:85:4d:db:76:0a:f5:d3:35:4e:93:2f:91:e1:
            19:bf:f1:e1:3b
        generator: 2 (0x2)
        subgroup order:
            69:b5:75:9f:a4:b9:0d:f5:48:35:dd:04:f5:22:b9:
            58:a3:8c:ab:56:c0:dd:b6:59:7c:ac:53:d6:39:c9:
            8e:87:11:f0:02:16:10:b5:f9:81:54:a0:f1:13:ea:
            ac:42:a6:ed:bb:05:7a:e9:9a:a7:49:97:c8:f0:8c:
            df:f8:f0:9d
the g value is not a generator
-----BEGIN X9.42 DH PARAMETERS-----
MIGIAkEA02rrP0lyG+qQa7oJ6kVysUcZVq2Bu2yy+VinrHOTHQ4j4AQsIWvzAqlB
4ifVWIVN23YK9dM1TpMvkeEZv/HhOwIBAgJAabV1n6S5DfVINd0E9SK5WKOMq1bA
3bZZfKxT1jnJjocR8AIWELX5gVSg8RPqrEKm7bsFeumap0mXyPCM3/jwnQ==
-----END X9.42 DH PARAMETERS-----

[randombit]

Thanks for the writeup. I have never read the actual X9.42, and really X9.42 in the format name was purely to refer to the existence of q, vs the PKCS3 format which omits it.

For the generation of strong groups, I think the thing to do is take the first small prime (from PRIMES table) that is a quadratic residue mod p, rather than fixing g at 2. That seems to be what the later SRP groups do, and a smaller generator is sometimes beneficial for performance.

SRP does not rely on q value in DL_Group so I think it is safe to remove q from these groups as you suggest. I also want to switch to storing P,Q,G in decimal or hex format rather than PEM blobs, for easier audit of the values being correct.

[randombit]

I still have fixing at least the generator choice and PEM header before 2.0.0

[randombit]

I think we are all set here wrt the generator choice with the merge of #818

Validation of the SRP groups still fails but I don't think it's a huge issue and have a plan for a better resolution in 2.1