1170322 - certutil default PQG parameters don't satisfy DSA_MIN_P_BITS

Status: RESOLVED FIXED

(NSS :: Tools, defect)

Description

[Kai Engert [:KaiE:]]

certutil -k dsa generates certificates with authKeyBits == 1022,
but DSA_MIN_P_BITS == 1023.

By default, certutil -k dsa uses embedded, fixed default_pqg_params.

Using experimental code, I tried to use tstclnt with :0037 (TLS_DH_RSA_WITH_AES_256_CBC_SHA) to connect to a selfserv that uses a mixed cert (DSA key, RSA signed).

The check in ssl3_AuthCertificate failed, because 1022 < 1023.

Should we change certutil/keystuff.c to use larger embedded P/Q/G values?

Comment 1

[Martin Thomson [:mt:]]

2048 seems like a reasonable choice today.

Comment 2

[Kai Engert [:KaiE:]]

This bug blocks bug 102794, we need larger DSA keys to test DHE_DSS, because of the recent increase of DSA_MIN_P_BITS in bug 1138554.

Comment 3

[Kai Engert [:KaiE:]]

Attachment: patch v1

generated using 
  openssl dsaparam -C 2048

Comment 4

[Martin Thomson [:mt:]]

Comment on attachment 8614013 [details] [diff] [review]
patch v1

WFM.  I'm not going to check that these are OK, since we don't actually need to concern ourselves with correctness here.  I did check that they are the right size though.

Comment 5

[Wan-Teh Chang]

Comment on attachment 8614013 [details] [diff] [review]
patch v1

Review of attachment 8614013 [details] [diff] [review]:
-----------------------------------------------------------------

Kai: you can also just take the parameters from
https://tools.ietf.org/html/rfc5114#section-2.3

::: cmd/certutil/keystuff.c
@@ +158,5 @@
>  static const unsigned char Q[] = { 0,
> +	0xC1,0xE3,0xD4,0xDC,0xED,0x72,0x07,0x9A,0xB9,0x56,0xEB,0xEB,
> +	0x91,0xFC,0xC7,0xA8,0x94,0xF4,0x4E,0xE1,0xCB,0x3F,0x0A,0x54,
> +	0x19,0xFD,0x0D,0x3D,0x36,0xE0,0xB0,0x47};
> +static const unsigned char G[] = { 0,

IMPORTANT: are you sure we need the 0 byte in G[]?

The 0 byte is only necessary if the most significant bit is 1.
That is the case for P[] and Q[] because 0xAB and 0xC1 both
have a most significant bit of 1.

But G[]'s first byte is 0x67, which has a most significant
bit of 0.

Comment 6

[Kai Engert [:KaiE:]]

Wan-Teh:

Do you mean to say, the parameters from that RFC are better?

Thanks for your hint with the initial 0, I had not paid attention, but had simply kept the zeroes. I'll fix it.

Comment 7

[Wan-Teh Chang]

Kai:

They are equally good. But we should document where they
come from. If you copy the parameters from RFC 5114, then
you can just add a comment to note that. If you generate
the parameters, then you should add a comment to note how
they were generated. This comment already exists, so you
need to update it:

/*  h:
 *      4a:76:30:89:eb:e1:81:7c:99:0b:39:7f:95:4a:65:72:
 *      c6:b4:05:92:48:6c:3c:b2:7e:e7:39:f3:92:7d:c1:3f:
 *      bf:e1:fd:b3:4a:46:3e:ce:29:80:e3:d6:f4:59:c6:92:
 *      16:2b:0e:d7:d6:bb:ef:94:36:31:c2:66:46:c5:4a:77:
 *      aa:95:84:ef:99:7e:e3:9c:d9:a0:32:42:09:b6:4e:d0:
 *      b3:c8:5e:06:df:a1:ac:4d:2d:f9:08:c2:cb:4b:a4:42:
 *      db:8a:5b:de:25:6e:2b:5b:ca:00:75:2c:57:00:18:aa:
 *      68:59:a1:94:03:07:94:78:38:bc:f8:7c:1e:1c:a3:2e
 *  SEED:
 *      b5:44:66:c9:0f:f1:ca:1c:95:45:ce:90:74:89:14:f2:
 *      13:3e:23:5a:b0:6a:bf:86:ad:cb:a0:7d:ce:3b:c8:16:
 *      7f:2d:a2:1a:cb:33:7d:c1:e7:d7:07:aa:1b:a2:d7:89:
 *      f5:a4:db:f7:8b:50:00:cd:b4:7d:25:81:3f:f8:a8:dd:
 *      6c:46:e5:77:b5:60:7e:75:79:b8:99:57:c1:c4:f3:f7:
 *      17:ca:43:00:b8:33:b6:06:8f:4d:91:ed:23:a5:66:1b:
 *      ef:14:d7:bc:21:2b:82:d8:ab:fa:fd:a7:c3:4d:bf:52:
 *      af:8e:57:59:61:1a:4e:65:c6:90:d6:a6:ff:0b:15:b1
 *  g:       1024
 *  counter: 1003
 */

I would also suggest that you keep the original format
of the P[], Q[], G[] array initializers: 8 bytes per
line, with a space between the bytes.

Thanks a lot.

Comment 8

[Kai Engert [:KaiE:]]

(In reply to Wan-Teh Chang from comment #7)
> If you generate
> the parameters, then you should add a comment to note how
> they were generated.

I mentioned that in comment 3.

That command didn't show me h/seed/g/counter values.


> This comment already exists, so you
> need to update it:

Does RFC 5114 provide the h/seed/g/counter values?

Comment 9

[Wan-Teh Chang]

(In reply to Kai Engert (:kaie) from comment #8)
>
> That command didn't show me h/seed/g/counter values.

Then you should just delete the existing comment or
replace it with:

  generated using 
    openssl dsaparam -C 2048

It seems that we should try to use an NSS command to generate
the parameters, for example, makepqg may work:
http://mxr.mozilla.org/nss/source/cmd/makepqg/makepqg.c

> Does RFC 5114 provide the h/seed/g/counter values?

I don't think so, but your can change the existing comment
to say you copied the parameters from
https://tools.ietf.org/html/rfc5114#section-2.3

Comment 10

[Kai Engert [:KaiE:]]

Thanks for the hint that makepqg exists.

Usage:  makepqg
-a   Output DER-encoded PQG params, BTOA encoded.
-b   Output DER-encoded PQG params in binary
-r   Output P, Q and G in ASCII hexadecimal. 
  -l prime-length       Length of prime in bits (1024 is default)
  -n subprime-length    Length of subprime in bits
  -o file               Output to this file (default is stdout)
  -g bits               Generate SEED this many bits long.


Unfortunately it doesn't work with a "-l 2048 -r" parameter, it exits with:

makepqg: PQG parameter generation failed.
: SEC_ERROR_BAD_DATA: security library: received bad data.

Comment 11

[Robert Relyea]

Something must be wrong, I've used makepqg to generate 2048 bit parameters.

Please use the NSS PQG gen, it uses Shawe-Taylor, so the primes are proveable primes, not just probable.

Comment 12

[Wan-Teh Chang]

Bob:

If I run makepqg -l 2048 -r, the PQG parameters are generated
successfully, but the parameter verification fails in findQfromSeed.
Could you please take a look at this? Thanks.

Comment 13

[Robert Relyea]

What are the pqg and parameters generated?

Comment 14

[Wan-Teh Chang]

Bob:

You can reproduce this in gdb with run -l 2048 -r and a breakpoint
at findQfromSeed. Here is the call stack when findQfromSeed returns
SECFailure at the end of the function:

(gdb) 
967	    return SECFailure;
(gdb) bt
#0  findQfromSeed (L=2048, N=224, g=3072, seed=0x7fffffffd470, 
    Q=0x7fffffffd280, Q_=0x7fffffffd2e0, qseed_len=0x7fffffffd204, 
    hashtypePtr=0x7fffffffd208, typePtr=0x7fffffffd20c) at pqg.c:967
#1  0x00007ffff606ec7e in PQG_VerifyParams (params=0x7fffffffd4a0, 
    vfy=0x7fffffffd460, result=0x7fffffffd414) at pqg.c:1679
#2  0x00007ffff65e5bd1 in PQG_VerifyParams (params=0x7fffffffd4a0, 
    vfy=0x7fffffffd460, result=0x7fffffffd414) at loader.c:862
#3  0x00007ffff65b97ef in sftk_handleDSAParameterObject (session=0x614a60, 
    object=0x61d640) at pkcs11.c:1461
#4  0x00007ffff65b9962 in sftk_handleKeyParameterObject (session=0x614a60, 
    object=0x61d640) at pkcs11.c:1506
#5  0x00007ffff65b9cf6 in sftk_handleObject (object=0x61d640, session=0x614a60)
    at pkcs11.c:1620
#6  0x00007ffff65ca69b in NSC_GenerateKey (hSession=1, 
    pMechanism=0x7fffffffd7f0, pTemplate=0x7fffffffd8b0, ulCount=1, 
    phKey=0x7fffffffd798) at pkcs11c.c:3996
#7  0x00007ffff7ad3909 in PK11_PQG_ParamGenV2 (L=2048, N=0, seedBytes=0, 
    pParams=0x7fffffffd998, pVfy=0x7fffffffd9a0) at pk11pqg.c:132
#8  0x0000000000402453 in main (argc=4, argv=0x7fffffffdaa8) at makepqg.c:309
(gdb)

Comment 15

[Kai Engert [:KaiE:]]

Bob, it surprises me that it works for you. Maybe you are using an older version of NSS and it has regressed?

I tried plain NSS trunk (post 3.19.1), and the mentioned command always fails with an error.

Comment 16

[Kai Engert [:KaiE:]]

If you're able to produce 2048-bit parameters with NSS, then please attach them to the bug, e.g. as a text file with the output from makepqg (including the command that you used). Thanks.

Comment 17

[Robert Relyea]

OK, I found out what is wrong. 

Kai the simple solution is to specify the seed bits manually:

makepqg -l 2048 -g 224 -r


-g has to be 512 or less or the code will fail in the verify step. 

The bug is in softoken/pkcs11c.c in nsc_parameter_gen. In the else statement it sets seedBits to primeBits if seedBits are zero before calling PQG_ParamGenV2().

It should either set seedBits to subprimeBits, or leave seedBits at zero.

We can also fix this at the NSS level by explicitly setting seedBits in PK11_PQG_ParamGenV2().

bob

Comment 18

[Kai Engert [:KaiE:]]

Thanks Bob!

I've just ran the command and produced the following parameters. I suggest we use them. I'll attach a new patch.

I suggest we start by patching certutil, to unblock the DHE bug, and fix the makepqg utility to be smarter in a separate step.


$ makepqg -l 2048 -g 224 -r
makepqg: PQG parameter generation completed.
    Prime:
        c6:2a:47:73:ea:78:fa:65:47:69:39:10:08:55:6a:dd:
        bf:77:e1:9a:69:73:ba:66:37:08:93:9e:db:5d:01:08:
        b8:3a:73:e9:85:5f:a7:2b:63:7f:d0:c6:4c:dc:fc:8b:
        a6:03:c9:9c:80:5e:ec:c6:21:23:f7:8e:a4:7b:77:83:
        02:44:f8:05:d7:36:52:13:57:78:97:f3:7b:cf:1f:c9:
        2a:a4:71:9d:a8:d8:5d:c5:3b:64:3a:72:60:62:b0:b8:
        f3:b1:e7:b9:76:df:74:be:87:6a:d2:f1:a9:44:8b:63:
        76:4f:5d:21:63:b5:4f:3c:7b:61:b2:f3:ea:c5:d8:ef:
        30:50:59:33:61:c0:f3:6e:21:cf:15:35:4a:87:2b:c3:
        f6:5a:1f:24:22:c5:eb:47:34:4a:1b:b5:2e:71:52:8f:
        2d:7d:a9:96:8a:7c:61:db:c0:dc:f1:ca:28:69:1c:97:
        ad:ea:0d:9e:02:e6:e5:7d:ad:e0:42:91:4d:fa:e2:81:
        16:2b:c2:96:3b:32:8c:20:69:8b:5b:17:3c:f9:13:6c:
        98:27:1c:ca:cf:33:aa:93:21:af:17:6e:5e:00:37:d9:
        34:8a:47:d2:1c:67:32:60:b6:c7:b0:fd:32:90:93:32:
        aa:11:ba:23:19:39:6a:42:7c:1f:b7:28:db:64:ad:d9
    Subprime:
        e6:a3:c9:c6:51:92:8b:b3:98:8f:97:b8:31:0d:4a:03:
        1e:ba:4e:e6:c8:90:98:1d:3a:95:f4:f1
    Base:
        70:32:58:5d:b3:bf:c3:62:63:0b:f8:a5:e1:ed:eb:79:
        ac:18:41:64:b3:da:4c:a7:92:63:b1:33:7c:cb:43:dc:
        1f:38:63:5e:0e:6d:45:d1:c9:67:f3:cf:3d:2d:16:4e:
        92:16:06:59:29:89:6f:54:ff:c5:71:c8:3a:95:84:b6:
        7e:7b:1e:8b:47:9d:7a:3a:36:9b:70:2f:d1:bd:ef:e8:
        3a:41:d4:f3:1f:81:c7:1f:96:7c:30:ab:f4:7a:ac:93:
        ed:6f:67:b0:c9:5b:f3:83:9d:a0:d7:b9:01:ed:28:ae:
        1c:6e:2e:48:ac:9f:7d:f3:00:48:ee:0e:fb:7e:5e:cb:
        f5:39:d8:92:90:61:2d:1e:3c:d3:55:0d:34:d1:81:c4:
        89:ea:94:2b:56:33:73:58:48:bf:23:72:19:5f:19:ac:
        ff:09:c8:cd:ab:71:ef:9e:20:fd:e3:b8:27:9e:65:b1:
        85:cd:88:fe:d4:d7:64:4d:e1:e8:a6:e5:96:c8:5d:9c:
        c6:70:6b:ba:77:4e:90:4a:b0:96:c5:a0:9e:2c:01:03:
        be:bd:71:ba:0a:6f:9f:e5:db:04:08:f2:9e:0f:1b:ac:
        cd:bb:65:12:cf:77:c9:7d:be:94:4b:9c:5b:de:0d:fa:
        57:dd:77:32:f0:5b:34:fd:19:95:33:60:87:e2:a2:f4

    h: 1 (0x1)
    SEED:
        d2:0b:c5:63:1b:af:dc:36:b7:7c:b9:3e:36:01:a0:8f:
        0e:be:d0:38:e4:78:d5:3c:7c:9e:a9:9a:d2:0b:c5:63:
        1b:af:dc:36:b7:7c:b9:3e:36:01:a0:8f:0e:be:d0:38:
        e4:78:d5:3c:7c:9e:c7:70:d2:0b:c5:63:1b:af:dc:36:
        b7:7c:b9:3e:36:01:a0:8f:0e:be:d0:38:e4:78:d5:3c:
        7c:9e:aa:3e
    g:       672
    counter: 0

makepqg: PQG parameters passed verification.

Comment 19

[Kai Engert [:KaiE:]]

Attachment: 1170322-v2.patch

Comment 20

[Robert Relyea]

You have the correct priorities in comment 18

Comment 21

[Robert Relyea]

Comment on attachment 8620473 [details] [diff] [review]
1170322-v2.patch

Review of attachment 8620473 [details] [diff] [review]:
-----------------------------------------------------------------

r+ rrelyea

Comment 22

[Kai Engert [:KaiE:]]

https://hg.mozilla.org/projects/nss/rev/983e0063a342