Certificate validation is incredibly slow with large numbers of intermediates

[dadrian]

BenchmarkGolangX509NoIntermediates-4             3000000           578 ns/op
BenchmarkGolangX509WithIntermediates-4              2000        711043 ns/op
BenchmarkGolangX509WithChain-4                     10000        158716 ns/op
BenchmarkRawX509NoIntermediates-4               10000000           193 ns/op
BenchmarkRawX509WithIntermediates-4                 1000       1032861 ns/op
BenchmarkRawX509WithChain-4                        10000        165573 ns/op
BenchmarkVerifyNSSNoIntermediates-4              2000000           656 ns/op
BenchmarkVerifyNSSWithChain-4                      10000        163489 ns/op
BenchmarkVerifyNSSWithIntermediates-4               1000       1004869 ns/op
BenchmarkVerifyNSSWithIntermediatesAsRoots-4        5000        213618 ns/op

In these benchmarks, WithIntermediates means with the set of 1.5K intermediates trusted by NSS ~May 2015, and WithChain means with the intermediates pool set to the chain served by a website (e.g. the one intermediate that matters).

RawX509 is github.com/zmap/zcrypto/x509, Verify is github.com/zmap/zcrypto/verifier, and GolangX509 is crypto/x509.

This suggests our current validation approach may be too slow for live certificate validation, and is also not appropriate for finding the set of trusted intermediates in Censys given the set of possible intermediates and a root store.

[dadrian]

This is likely solvable with some sort of caching.

[dadrian]

For further context, "current validation approach" means a priori determine all possible intermediates for a given root store, and then set the intermediate pool to that. This provides a brute-force approach to transvalidity, and allows certificates to be validated without knowledge of the chain.

[zakird]

For the record this is 1000 certificates/second.

[dadrian]

Turns out nanoseconds are not microseconds, this seems fast enough for now.