377548 - NSS QA test program certutil's default DSA prime is only 512 bits

Status: RESOLVED FIXED

(NSS :: Tools, enhancement, P4)

Description

[georgi - hopefully not receiving bugspam]

short default dsa cert

last time i checked nss certutil generates default dsa cert with prime of length 512 bits.

this does not seem enough long:
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0702&L=nmbrthry&T=0&P=194
Discrete logarithms in GF(p) --- 160 digits
(note: decimal digits)

the above post claims that an university has done discrete logs for
529 bits strong prime in:
single 3.2 GHz Xeon64: 3.3 (CPU?) years + 14 CPU years

18 CPU years are too low for known botnets totalling 2.6M machines:
http://www.shadowserver.org/wiki/pmwiki.php?n=Stats.BotCounts

assuming it scales and 20 CPU years

days1=365*20/(2.600*10^6)
%6 = 0.002807692307692307692307692307

assuming 2600 bots:

days2=365*20/(2.600*10^3)
2.807692307692307692307692307

Comment 1

[Daniel Veditz [:dveditz]]

Should we open up this bug? Hopefully anyone using this tool will select an appropriate key length and not rely on the default, and if not publicizing the problem might make that more likely. There's no knowledge in this bug that makes attacks more likely to succeed.

Comment 2

[georgi - hopefully not receiving bugspam]

(In reply to comment #1)
> Should we open up this bug? Hopefully anyone using this tool will select an
> appropriate key length and not rely on the default, and if not publicizing the
> problem might make that more likely. There's no knowledge in this bug that
> makes attacks more likely to succeed.
> 

sure, open it up.

i was just playing safely.

the rationale is that users of the tool may not know what is the right key length.

Comment 3

[Nelson Bolyard (seldom reads bugmail)]

I'm opening this bug.  I confirm what Georgi reports, and I thank him for 
being cautious, but I want to offer a different perspective on this issue.  

1. (background) Unlike RSA, where key generation involves finding two large 
prime numbers which must be kept secret/private, in DSA, the prime numbers,
P and Q, are both public information, part of a set of public "parameters" 
known as "PQG parameters."  Using PQG parameters, generation of a DSA key 
pair is very quick.

Normally, a CA who issues DSA certs provides a single set of PQG parameters 
that are to be used in generating the public keys for any certificates that 
it signs.  The CA's PQG parameters are found in the CA's own DSA cert.  
Such CAs generally do not accept CSRs that use any PQG params but theirs.

certutil is able to input a file of PQG parameters and use them in the 
generation of key pairs for certs and CSRs.  certutil can generate DSA keys 
for any valid set of DSA PQG parameters.

2. certutil is a QA test program used to test NSS libraries in QA test scripts.
It's not intended to be used as a real CA tool, for real CAs to issue certs.
Its ability to generate self-issued certs is intended only for QA purposes.  
For most QA test purposes, it is sufficient to test with 512-bit PQG params,
and certutil has a built-in "default" set of 512-bit PQG params that it uses
when no other PQG params are supplied.  

NSS also supplies another QA test program, makepqg, for generating files of
PQG parameters of any valid length.  (The only valid lengths are:
512, 576, 640, 704, 768, 832, 896, 960, and 1024 bits.)  The default length
for primes generated by makepqg is 1024 bits.

3. People who use certutil to issue "self-signed" (self-issued) certs take 
FULL responsibility for their own security.  It's entirely up to them to 
select algorithms and key sizes adequate for their security needs.

4. Cryptography experts agree that 1024-bit RSA *AND* DSA keys are not strong enough to protect any *existing* secrets past the year 2010, and will not 
be strong enough to protect *any* secrets at all beginning in the year 2010.  
See, for example:
http://csrc.nist.gov/publications/nistpubs/800-52/SP800-52.pdf
http://www.imes.boj.or.jp/english/publication/edps/2006/06-E-08.pdf

Since DSA only allows primes between 512 and 1024 bits, and isn't defined 
to use larger primes, it's lifetime is effectively over, or will be in 2010.  
Rather than "fix" DSA, NIST has chosen to switch to Elliptic Curve DSA (ECDSA)
as their standard for the future.  

5. NSS supports Elliptic Curve algorithms such as EC DSA and EC DH.  
No more enhancements to/for the DSA code are planned.  
IIRC, there are NO unexpired DSA roots in mozilla products.

Georgi, if you know of some secret cabal of users of self-signed DSA certs,
please encourage them to stop using DSA soon.

Comment 4

[Nelson Bolyard (seldom reads bugmail)]

Output of one run of makepqg -r:

    Prime:
        98:ef:3a:ae:70:98:9b:44:db:35:86:c1:b6:c2:47:7c:
        b4:ff:99:e8:ae:44:f2:eb:c3:be:23:0f:65:d0:4c:04:
        82:90:a7:9d:4a:c8:93:7f:41:df:f8:80:6b:0b:68:7f:
        af:e4:a8:b5:b2:99:c3:69:fb:3f:e7:1b:d0:0f:a9:7a:
        4a:04:bf:50:9e:22:33:b8:89:53:24:10:f9:68:77:ad:
        af:10:68:b8:d3:68:5d:a3:c3:eb:72:3b:a0:0b:73:65:
        c5:d1:fa:8c:c0:7d:aa:52:29:34:44:01:bf:12:25:fe:
        18:0a:c8:3f:c1:60:48:db:ad:93:b6:61:67:d7:a8:2d
    Subprime:
        b5:b0:84:8b:44:29:f6:33:59:a1:3c:be:d2:7f:35:a1:
        76:27:03:81
    Base:
        04:0e:83:69:f1:cd:7d:e5:0c:78:93:d6:49:6f:00:04:
        4e:0e:6c:37:aa:38:22:47:d2:58:ec:83:12:95:f9:9c:
        f1:f4:27:ff:d7:99:57:35:c6:64:4c:c0:47:12:31:50:
        82:3c:2a:07:03:01:ef:30:09:89:82:41:76:71:da:9e:
        57:8b:76:38:37:5f:a5:cd:32:84:45:8d:4c:17:54:2b:
        5d:c2:6b:ba:3e:a0:7b:95:d7:00:42:f7:08:b8:83:87:
        60:e1:e5:f4:1a:54:c2:20:da:38:3a:d1:b6:10:f4:cb:
        35:da:97:92:87:d6:a5:37:62:b4:93:4a:15:21:a5:10

    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

Comment 5

[Nelson Bolyard (seldom reads bugmail)]

Attachment: patch v1

Preliminary patch.  Need to see if all.sh passes with this.

Comment 6

[georgi - hopefully not receiving bugspam]

from quick reading of docs had the impression that "certutil" was the primary tool for key/cert generation.

feel free to resolve as invalid.

i am too lame to understand the crypto stuff, so can't respond to the other points.

Comment 7

[Nelson Bolyard (seldom reads bugmail)]

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

review request for trunk

Comment 8

[Robert Relyea]

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

r+ 
I'm assuming makepqg did, in fact, generate the pqg parameters. Anyone who cares can verify h SEED cand counter and see if the indeed produce pqg.

Comment 9

[Robert Relyea]

re comment 6

Certutil is both a testing tool and a management tools. It's useful for producing certs to test with, It's also useful for producing certificate requests for a server (In this case, the CA should provide P Q and G).

Nelson's comments are targetted to discouraging use of certutil for building or managing a CA itself. Certutil can certainly handle the obvious primitives of creating self signed CA certs and signing certificate requests, but there is usually a lot more you want from a CA (like keeping track of the certs issued, managing revoked certificates, managing how the certs are issued to make sure the conform to the various standards--like not issuing multiple certs with the same issuer and serial number). There are full blown CA products which are built on NSS and handle these things appropriately.

In any case, it's quite appropriate to make the default DSA key size in the test tool 1024 bits. Definately thanks for the bug.

bob

Comment 10

[Nelson Bolyard (seldom reads bugmail)]

On trunk:
Checking in keystuff.c; new revision: 1.16; previous revision: 1.15