[openssl-users] openssl verify and alt_chains

[Viktor Dukhovni]

> On Dec 31, 2015, at 12:55 PM, Jakob Bohm <jb-openssl at wisemo.com> wrote:
> 
>> You're not supposed to create two different untrusted intermediate
>> certificates, include both and hope for a good outcome.  OpenSSL
>> does not try all possible untrusted intermediates at every depth
>> in the chain, that has exponential cost in the chain depth.

> I believe it would be at worst linear in the number of offered/loaded
> certificates, and in practice limited to much less by the number of
> certificates actually having multiple candidates.

I there the depth is N, and the wire chain includes 2N certificates,
2 possibilities for the issuer at each depth, then the number of
potential chains is 2^N.

> The other X509 libraries in common use (such as NSS) seem to cope just
> fine, and have presumably managed to arrange their search algorithms to
> not be subject to remote denial of service via combinatorial explosion.

The other libraries run in browsers where the trust store has many
intermediate certificates in it, not just the trust-anchor roots.

>> Cross-sign roots, not an intermediates, and include the cross-signed
>> root in the trust store.  Then if a user happens to include the
>> root CA in the chain that is not trusted but the trust store contains
>> a cross-signed intermediate, you win.

> And how would the code cope with a root that was cross signed by two
> other roots, and was not itself on the trust list?  Wouldn't that be
> indistinguishable from the OP's test scenario?

If the wire chain, possibly truncated is issued by some root or
intermediate from the trust store, it works.  The browsers have
a suitably comprehensive trust store.

In any case, there is no regression in 1.1.0, it works the same
way as 1.0.2.  Perhaps the algorithm could handle more cases, but
that would be a new feature.

-- 
	Viktor.