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
https://golang.org/cl/
4439070