code review 4439070: crypto/x509: memoise chain building.

crypto/x509: memorize chain building.

I ran the new verification code against a large number of certificates
with a huge (>1000) number of intermediates.

I had previously convinced myself that a cycle in the certificate
graph implied a cycle in the hash graph (and thus, a contradiction).
This is bogus because the signatures don't cover each other.

Secondly, I managed to drive the verification into a time explosion
with a fully connected graph of certificates. The code would try to
walk the factorial number of paths.

This change switches the CertPool to dealing with indexes of
certificates rather than pointers: this makes equality easy. (I didn't
want to compare pointers because a reasonable gc could move objects
around over time.)

Secondly, verification now memorizes the chains from a given
certificate. This is dynamic programming for the lazy, but there's a
solid reason behind it: dynamic programming would ignore the Issuer
hints that we can exploit by walking up the chain rather than down.

[agl1, 2011-04-25 14:37:35]

Hello bradfitzgo (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[bradfitz, 2011-04-25 18:45:15]

LGTM

http://codereview.appspot.com/4439070/diff/8001/src/pkg/crypto/x509/cert_pool.go
File src/pkg/crypto/x509/cert_pool.go (right):

http://codereview.appspot.com/4439070/diff/8001/src/pkg/crypto/x509/cert_pool...
src/pkg/crypto/x509/cert_pool.go:55: func (s *CertPool) AddCert(cert
*Certificate) {
If s.certs is empty here, you never deference a potentially-nil cert pointer in
this function, meaning s.certs could then contain a nil and lead to a weird
stack in a later crash.

If you care.

[agl1, 2011-04-26 14:26:37]

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

crypto/x509: memorize chain building.

I ran the new verification code against a large number of certificates
with a huge (>1000) number of intermediates.

I had previously convinced myself that a cycle in the certificate
graph implied a cycle in the hash graph (and thus, a contradiction).
This is bogus because the signatures don't cover each other.

Secondly, I managed to drive the verification into a time explosion
with a fully connected graph of certificates. The code would try to
walk the factorial number of paths.

This change switches the CertPool to dealing with indexes of
certificates rather than pointers: this makes equality easy. (I didn't
want to compare pointers because a reasonable gc could move objects
around over time.)

Secondly, verification now memorizes the chains from a given
certificate. This is dynamic programming for the lazy, but there's a
solid reason behind it: dynamic programming would ignore the Issuer
hints that we can exploit by walking up the chain rather than down.

R=bradfitzgo
CC=golang-dev
http://codereview.appspot.com/4439070

http://codereview.appspot.com/4439070/diff/8001/src/pkg/crypto/x509/cert_pool.go
File src/pkg/crypto/x509/cert_pool.go (right):

http://codereview.appspot.com/4439070/diff/8001/src/pkg/crypto/x509/cert_pool...
src/pkg/crypto/x509/cert_pool.go:1: // Copyright 2011 The Go Authors. All rights
reserved.
Have changed the change description to include extra 'r's and 'z's.

http://codereview.appspot.com/4439070/diff/8001/src/pkg/crypto/x509/cert_pool...
src/pkg/crypto/x509/cert_pool.go:55: func (s *CertPool) AddCert(cert
*Certificate) {
On 2011/04/25 18:45:15, bradfitzgo wrote:
> If s.certs is empty here, you never deference a potentially-nil cert pointer
in
> this function, meaning s.certs could then contain a nil and lead to a weird
> stack in a later crash.

That would be a sad bug to have to track down so I've added a panic in this
case. Thanks!