Handle the possibility of backtracking when building a certificate path

[randombit]

Golang had a bug where if there are many intermediate CAs with the same Subject then it would iterate over all possible chains trying to find one that worked, and potentially take a lot of CPU time.

golang/go#29233
golang/go@df52396

We first build the path and then attempt to validate it so I think what will happen instead is either the cert verifies (if we happen to pick the right intermediate cert) or fails immediately; we don't backtrack trying to find another intermediate. But it would be good to confirm all this with a test.

Also worth taking a look at why Go does it this way. Are there chains in practice where you need to pick among multiple possible intermediate CAs with same Subject, only one of which is correct?

[briansmith]

Also worth taking a look at why Go does it this way. Are there chains in practice where you need to pick among multiple possible intermediate CAs with same Subject, only one of which is correct?

At least according to the specification, there is no requirement that the Subject field maps uniquely to a key. From that, it follows that there could be two (CA) certificates with the same subject and different keys. From that it follows that backtracking might be required. This is why Go's and other libraries do the backtracking.

[briansmith]

BTW, if you generalize this a little bit then you can see why backtracking is required: Sub-CA1 is cross-signed by Root-CA1 and Root-CA2. That means there are these chains:\

End-Entity <- Sub-CA1 <- Root-CA1
End-Entity <- Sub-CA1 <- Root-CA2.

You must already do backtracking to handle this case; if you didn't, then definitely certificate validation will be broken for some real-world scenerios. (This was the biggest motivation for the creation of mozilla::pkix; Firefox's original certificate path building didn't do any backtracking at all.)