crypto/x509: sub-quadratic name constraint checking

Previously, we implemented ~quadratic name constraint checking, wherein
we would check every SAN against every respective constraint in the
chain. This is the technique _basically everyone_ implements, because
it's easy, but it requires also capping the total number of constraint
checking operations to prevent denial of service.

Instead, this change implements a log-linear checking technique, as
originally described by davidben@google.com with some minor
modifications. The comment at the top of crypto/x509/constraints.go
describes this technique in detail.

This technique is faster than the existing quadratic approach in all but
one specific case, where there are a large number of constraints but
only a single name, since our previous algorithm resolves to linear in
that case.

Change-Id: Icb761f5f9898c04e266c0d0c2b07ab2637f03418
Reviewed-on: https://go-review.googlesource.com/c/go/+/711421
Reviewed-by: Nicholas Husin <nsh@golang.org>
Reviewed-by: Daniel McCarney <daniel@binaryparadox.net>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Roland Shoemaker <roland@golang.org>
Reviewed-by: Nicholas Husin <husin@google.com>

0 files changed, 0 insertions, 0 deletions