• Adam Langley's avatar
    crypto/x509: memorize chain building. · 8803d57f
    Adam Langley authored
    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
    8803d57f
Name
Last commit
Last update
..
Makefile Loading commit data...
cert_pool.go Loading commit data...
verify.go Loading commit data...
verify_test.go Loading commit data...
x509.go Loading commit data...
x509_test.go Loading commit data...