code review 3990043: crypto/dsa: add support for DSA

crypto/dsa: add support for DSA

[agl1, 2011-01-20 16:37:59]

Brad: if you don't mind, I'll send the OpenPGP reviews to you as rsc has more
than enough!

[r, 2011-01-20 18:54:08]

just some cosmetic stuff. i'll leave the semantics to brad

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go
File src/pkg/crypto/dsa/dsa.go (right):

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode26
src/pkg/crypto/dsa/dsa.go:26: // Private Key represents a DSA private key
s/ K/K//

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode34
src/pkg/crypto/dsa/dsa.go:34: func (_ invalidPublicKeyError) String() string {
s/_ //

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode46
src/pkg/crypto/dsa/dsa.go:46: L2048N224 ParameterSizes = iota
second and subsequent lines can be just
   name1
   name2
etc.

the type and initializer are copied

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcod...
src/pkg/crypto/dsa/dsa.go:144: // GenerateKey generates a public, private key
pair. The Parameters of the
maybe s/public, private/(&)/

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcod...
src/pkg/crypto/dsa/dsa.go:148: return os.ErrorString("crypto/dsa: parameters not
setup before generating key")
s/setup/set up/ (not a noun)

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcod...
src/pkg/crypto/dsa/dsa.go:171: // Sign signs a arbitary length message in hashed
(which should be the result
s/arbitary/arbitrary/

[bradfitzgoog, 2011-01-21 06:34:38]

I can look at this more tomorrow.  (I need to adjust my gmail filters to archive
some stuff less.  Missed this.)

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go
File src/pkg/crypto/dsa/dsa.go (right):

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode53
src/pkg/crypto/dsa/dsa.go:53: func GenerateParameters(params *Parameters, rand
io.Reader, sizes ParameterSizes) (err os.Error) {
you worry at all about people passing in the wrong (PRNG) rand here, rather than
crypto/rand?  too obvious to be worth checking for?  or makes that's acceptable
in some cases?

[agl1, 2011-01-21 12:51:47]

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go
File src/pkg/crypto/dsa/dsa.go (right):

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newco...
src/pkg/crypto/dsa/dsa.go:26: // Private Key represents a DSA private key
On 2011/01/20 18:54:09, r wrote:
> s/ K/K//

Done.

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newco...
src/pkg/crypto/dsa/dsa.go:34: func (_ invalidPublicKeyError) String() string {
On 2011/01/20 18:54:09, r wrote:
> s/_ //

Done.

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newco...
src/pkg/crypto/dsa/dsa.go:46: L2048N224 ParameterSizes = iota
On 2011/01/20 18:54:09, r wrote:
> second and subsequent lines can be just
>    name1
>    name2
> etc.
> 
> the type and initializer are copied

Done.

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newco...
src/pkg/crypto/dsa/dsa.go:53: func GenerateParameters(params *Parameters, rand
io.Reader, sizes ParameterSizes) (err os.Error) {
On 2011/01/21 06:34:38, bradfitzwork wrote:
> you worry at all about people passing in the wrong (PRNG) rand here, rather
than
> crypto/rand?  too obvious to be worth checking for?  or makes that's
acceptable
> in some cases?

It's not too much of a problem here, it's during signing that a bad RNG is
sudden death (just ask Sony). We could remove the |rand| parameter from the API
and always use crypto/rand, but I don't really like that and it's different from
all the other crypto APIs. (Although I'm not strongly against it if you feel
that it's bound to bite someone.)

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newco...
src/pkg/crypto/dsa/dsa.go:144: // GenerateKey generates a public, private key
pair. The Parameters of the
On 2011/01/20 18:54:09, r wrote:
> maybe s/public, private/(&)/

Done.

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newco...
src/pkg/crypto/dsa/dsa.go:148: return os.ErrorString("crypto/dsa: parameters not
setup before generating key")
On 2011/01/20 18:54:09, r wrote:
> s/setup/set up/ (not a noun)

Done.

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newco...
src/pkg/crypto/dsa/dsa.go:171: // Sign signs a arbitary length message in hashed
(which should be the result
On 2011/01/20 18:54:09, r wrote:
> s/arbitary/arbitrary/

Done.

[nsz_port70.net, 2011-01-21 15:46:32]

* agl@golang.org <agl@golang.org> [2011-01-20 16:37:59 +0000]:
> Description:
> crypto/dsa: add support for DSA
> 
> Please review this at http://codereview.appspot.com/3990043/
hello
i looked into it as i've already implemented this once

> func GenerateParameters(params *Parameters, rand io.Reader, sizes
ParameterSizes) (err os.Error) {
i wonder if it's ok to allocate the parameters inside
then it's nicer to use it with := like
 p, err := dsa.GenerateParameters(r, siz)
(p does not have to be declared)

(same for key generation)

> 		_, err = io.ReadFull(rand, qBytes)
> 		if err != nil {
> 			return
> 		}
> 		qBytes[len(qBytes)-1] |= 1
> 		qBytes[0] |= 0x80
> 		q.SetBytes(qBytes)
the methods in fips 186-3 A.1 section use a hash when
generating p, q and g eg.
 seed = rand()
 U = hash(seed) mod 2^N
 q = U | 2^(N-1) | 1
i guess that's not essential, but it makes possible to
verify the generated primes with another implementation
using the same rand and hash

(imho the code is cleaner without the hashing but then
it is worth a mention in the comments that this does not
follow the standard verifiable p,q,g generation)

> 		if !big.ProbablyPrime(q, 20) {
> 			continue
> 		}

> 			if !big.ProbablyPrime(p, 20) {
> 				continue
> 			}
the standard recommends more iterations (C.1 table in appendix C.3)
as the generated parameters are supposed to be reused many times
(and thus this function is called rarely)

the standard might be overkill, but a few more iterations
should not hurt here

> 		if x.Sign() != 0 && x.Cmp(priv.Q) < 0 {
you used "x.Sign() != 0" checks in other places as well
i used "x.BitLen() != 0" in my code so far
i wonder what's the conventional go way to check for 0..

in Sign:
> 		k := new(big.Int)
> 		buf := make([]byte, n)
> 		for {
> 			_, err = io.ReadFull(rand, buf)
> 			if err != nil {
> 				return
> 			}
> 			k.SetBytes(buf)
> 			if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
> 				break
> 			}
> 		}
crypto/rsa has similar randomNumber function
(except that may generate 0 as well)
maybe a big.Random(rand,max) can be useful in other places as well

[bradfitzgoog, 2011-01-21 19:24:44]

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go
File src/pkg/crypto/dsa/dsa.go (right):

https://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newco...
src/pkg/crypto/dsa/dsa.go:53: func GenerateParameters(params *Parameters, rand
io.Reader, sizes ParameterSizes) (err os.Error) {
On 2011/01/21 12:51:47, agl1 wrote:
> On 2011/01/21 06:34:38, bradfitzwork wrote:
> > you worry at all about people passing in the wrong (PRNG) rand here, rather
> than
> > crypto/rand?  too obvious to be worth checking for?  or makes that's
> acceptable
> > in some cases?
> 
> It's not too much of a problem here, it's during signing that a bad RNG is
> sudden death (just ask Sony). We could remove the |rand| parameter from the
API
> and always use crypto/rand, but I don't really like that and it's different
from
> all the other crypto APIs. (Although I'm not strongly against it if you feel
> that it's bound to bite someone.)

I was just thinking of logging a big fat warning if you detect a PRNG io.Reader
(here and/or elsewhere), without changing the function signatures.

[rsc, 2011-01-21 19:43:44]

only read the comments

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/Makefile
File src/pkg/crypto/dsa/Makefile (right):

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/Makefile#newc...
src/pkg/crypto/dsa/Makefile:7: TARG=crypto/dsa
add to pkg/Makefile

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go
File src/pkg/crypto/dsa/dsa.go (right):

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode5
src/pkg/crypto/dsa/dsa.go:5: // dsa implements the Digital Signature Algorithm,
as defined in FIPS 186-3
begin with capital letter: Package dsa ...
end with period.

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode20
src/pkg/crypto/dsa/dsa.go:20: // PublicKey represents a DSA public key
s/$/./

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode26
src/pkg/crypto/dsa/dsa.go:26: // Private Key represents a DSA private key
s/$/./

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode41
src/pkg/crypto/dsa/dsa.go:41: // in a set of DSA parameters. See FIPS 186-3,
section 4.2
s/$/./

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcod...
src/pkg/crypto/dsa/dsa.go:171: // Sign signs a arbitary length message in hashed
(which should be the result
s/message in hashed/hash/
and s/hashed/hash/ in parameters
same with Verify
?

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa_test.go
File src/pkg/crypto/dsa/dsa_test.go (right):

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa_test.go#n...
src/pkg/crypto/dsa/dsa_test.go:66: // This test is too slow to run all the time.
return?

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa_test.go#n...
src/pkg/crypto/dsa/dsa_test.go:75: // These values can
...

[agl1, 2011-01-22 17:30:51]

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/Makefile
File src/pkg/crypto/dsa/Makefile (right):

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/Makefile#newc...
src/pkg/crypto/dsa/Makefile:7: TARG=crypto/dsa
On 2011/01/21 19:43:44, rsc wrote:
> add to pkg/Makefile

Done.

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go
File src/pkg/crypto/dsa/dsa.go (right):

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode5
src/pkg/crypto/dsa/dsa.go:5: // dsa implements the Digital Signature Algorithm,
as defined in FIPS 186-3
On 2011/01/21 19:43:44, rsc wrote:
> begin with capital letter: Package dsa ...
> end with period.

Done.

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode20
src/pkg/crypto/dsa/dsa.go:20: // PublicKey represents a DSA public key
On 2011/01/21 19:43:44, rsc wrote:
> s/$/./

Done.

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode26
src/pkg/crypto/dsa/dsa.go:26: // Private Key represents a DSA private key
On 2011/01/20 18:54:09, r wrote:
> s/ K/K//

Done.

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode41
src/pkg/crypto/dsa/dsa.go:41: // in a set of DSA parameters. See FIPS 186-3,
section 4.2
On 2011/01/21 19:43:44, rsc wrote:
> s/$/./

Done.

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcode53
src/pkg/crypto/dsa/dsa.go:53: func GenerateParameters(params *Parameters, rand
io.Reader, sizes ParameterSizes) (err os.Error) {
On 2011/01/21 19:24:44, bradfitzwork wrote:
> I was just thinking of logging a big fat warning if you detect a PRNG
io.Reader
> (here and/or elsewhere), without changing the function signatures.

There's nothing wrong with using a PRNG here. /dev/urandom is a PRNG and it's
reasonable to use it as a cryptographic RNG given the limitations of
/dev/random. So I'm not clear what could be reasonably done to detect weak RNGs.

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa.go#newcod...
src/pkg/crypto/dsa/dsa.go:171: // Sign signs a arbitary length message in hashed
(which should be the result
On 2011/01/21 19:43:44, rsc wrote:
> s/message in hashed/hash/
> and s/hashed/hash/ in parameters
> same with Verify
> ?

Done.

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa_test.go
File src/pkg/crypto/dsa/dsa_test.go (right):

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa_test.go#n...
src/pkg/crypto/dsa/dsa_test.go:66: // This test is too slow to run all the time.
On 2011/01/21 19:43:44, rsc wrote:
> return?

Done.

http://codereview.appspot.com/3990043/diff/1/src/pkg/crypto/dsa/dsa_test.go#n...
src/pkg/crypto/dsa/dsa_test.go:75: // These values can
On 2011/01/21 19:43:44, rsc wrote:
> ...

Opps, deleted.

[r, 2011-01-22 17:50:36]

http://codereview.appspot.com/3990043/diff/14001/src/pkg/crypto/dsa/dsa.go
File src/pkg/crypto/dsa/dsa.go (right):

http://codereview.appspot.com/3990043/diff/14001/src/pkg/crypto/dsa/dsa.go#ne...
src/pkg/crypto/dsa/dsa.go:32: type invalidPublicKeyError int
of the several errors returned by the code here, why is this one singled out as
a special type?  if there's a good reason, it's worth explaining

http://codereview.appspot.com/3990043/diff/14001/src/pkg/crypto/dsa/dsa.go#ne...
src/pkg/crypto/dsa/dsa.go:38: var InvalidPublicKeyError =
invalidPublicKeyError(0)
arguably this needs a doc comment, although it's self-explanatory

[agl1, 2011-01-22 18:05:30]

http://codereview.appspot.com/3990043/diff/14001/src/pkg/crypto/dsa/dsa.go
File src/pkg/crypto/dsa/dsa.go (right):

http://codereview.appspot.com/3990043/diff/14001/src/pkg/crypto/dsa/dsa.go#ne...
src/pkg/crypto/dsa/dsa.go:32: type invalidPublicKeyError int
On 2011/01/22 17:50:36, r wrote:
> of the several errors returned by the code here, why is this one singled out
as
> a special type?  if there's a good reason, it's worth explaining

The other errors returned are of the "you screwed up" variety (i.e. generating a
key without parameters). Catching them isn't useful because as soon as you know
about them, you don't need to catch them because they won't happen.

However, the invalid key case might need to be handled because keys can be
generated by other code and loaded by Go programs. So it can occur in correct
programs.

http://codereview.appspot.com/3990043/diff/14001/src/pkg/crypto/dsa/dsa.go#ne...
src/pkg/crypto/dsa/dsa.go:38: var InvalidPublicKeyError =
invalidPublicKeyError(0)
On 2011/01/22 17:50:36, r wrote:
> arguably this needs a doc comment, although it's self-explanatory

Done.

[r, 2011-01-22 19:05:29]

LGTM

[agl1, 2011-01-25 17:25:50]

Hello bradfitzgo, r, bradfitzwork, nsz@port70.net, rsc (cc:
golang-dev@googlegroups.com),

I'd like you to review this change.

[agl1, 2011-01-25 17:26:08]

*** Submitted as http://code.google.com/p/go/source/detail?r=e5c75402ae02 ***

crypto/dsa: add support for DSA

R=bradfitzgo, r, bradfitzwork, nsz, rsc
CC=golang-dev
http://codereview.appspot.com/3990043