crypto/x509: introduce new robust OID type & use it for certificate policies

[rolandshoemaker]

X509 certificates use OIDs in the certificatePolicies extension to signal specific policies that apply to a certificate. These certificates may contain OIDs which have components that do not fit within an int32. Due to the design of asn1.ObjectIdentifier, these OIDs cannot be parsed, since we cap the size of a component to the max int32 in order to maintain consistent behavior across platforms.

asn1.ObjectIdentifier is simply a alias for []int, and as such it cannot be reasonable retrofitted to support these extremely (perhaps too) large components. Introducing a new type is not particularly complicated, the most straight forward approach is to simply store the DER representation in memory, rather than parsing out an integer representation, but the complexity comes with how common asn1.ObjectIdentifier usage is. Ideally we'd replace all usages with the new type, deprecating the old fields, but this would result in significant bloat all over the place.

Since (as far as I'm aware at the moment, see #58821, #30757, #38737, and #36467. #36467 relates to RDN components, but that is significantly more complicated) the only place we're currently seeing parsing errors because of giant OIDs is certificate policies, I propose that we implement this new type, and first use it to replace only the Certificate.PolicyIdentifiers field. If down the road we start encountering these large OIDs elsewhere we can take a piecemeal approach to replacing them (with the rule that any new usage of OIDs should also use the new type).

I'm open to disagreements about where the new type should be implemented. OIDs are used, a lot, for X509, but they are also all over the place in various protocols, so it might make sense to put it somewhere else. I think their original home in asn1 is slightly confusing, since it's not inherently an asn1 type, but 🤷 (as always its easier to argue where it shouldn't be, rather than where it should be).

type OID struct {
	// unexported
	der []byte
	str string
}

func (oid *OID) Equal(other *OID) bool
func (oid *OID) String() string

// Simple way to switch between the old/new formats, and for parsing
// OIDs for testing, but perhaps not strictly necessary.

func (oid *OID) ToInts() ([]int, bool)
func FromInts([]int) *OID

type Certificate {
	...

	// DEPRECATED: PolicyIdentifiers contains asn1.ObjectIdentifiers, the components
	// of which are limited to int32. If a certificate contains a policy which
	// cannot be represented by asn1.ObjectIdentifier, it will not be included in
	// PolicyIdentifiers, but will be present in Policies, which contains all parsed
	// policy OIDs.
	PolicyIdentifiers []asn1.ObjectIdentifier
	// Policies contains policy OIDs included in any certificatePolicies extensions
	// in the certificate.
	Policies []*OID
}

cc @golang/security @FiloSottile

[mateusz834]

I assume that []int in this API will be also limited to 31b, so there will be no way to create the OID struct with an integer bigger than 31b for comparasion with other OIDs. Maybe there should be something like:

func NewOID(der []*big.Int) OID,
func NewOIDFromDer(der []byte) (OID, error)

Also why not just return a OID struct instead of a pointer, like:

func FromInts([]int) OID

Same with the Policies field why not just []OID ?

[mateusz834]

Placing it in encoding/asn1 would allow in future to support parsing it in cryptobyte (avoid cyclic dependency between x509 and cryptobyte)

[rolandshoemaker]

I assume that []int in this API will be also limited to 31b, so there will be no way to create the OID struct with an integer bigger than 31b for comparasion with other OIDs.

This is what the bool on ToInts is to indicate, whether it was successfully converted or not. I should add documentation to the proposed methods to clarify this. Since there is only really one failure mode here, it seems reasonable to just use a bool rather than an error.

Also why not just return a OID struct instead of a pointer

🤷 not particularly opinionated either way, it's a small struct so copying on every method call is probably not a huge issue, and I don't think we really want OIDs to be mutable after instantiation, so value is probably fine.

Placing it in encoding/asn1 would allow in future to support parsing it in cryptobyte (avoid cyclic dependency between x509 and cryptobyte).

That is a good argument.

[mateusz834]

This is what the bool on ToInts is to indicate, whether it was successfully converted or not. I should add documentation to the proposed methods to clarify this. Since there is only really one failure mode here, it seems reasonable to just use a bool rather than an error.

I feel like you didn't get my point here. Let's say that someone wants to compare OIDs (using Equal method), then the OIDs with ints bigger than 31b are imposible to compare, since ints are limited to 31b (no way to create OID struct for this case).

[rolandshoemaker]

Oh I see, yeah I misinterpreted what you were saying. This API doesn't provide fully featured methods for parsing OIDs, mostly because the expectation is that they will essentially always be parsed from DER using encoding/asn1, or golang.org/x/crypto/cryptobyte, and as such we don't need direct parsing methods, but we could perhaps provide them.

The rationale for providing FromInts is that many people currently create OIDs for testing or comparison using asn1.ObjectIdentifier{1,2,3}, which is not a viable option due to the opaque nature of the new proposed type. These OIDs are unlikely to be ones that exceed 31 bits (or reasonably 63 bits), since these are typically ones which are dynamically generated (i.e. UUIDs etc).

I guess an open question is if we want FromInts/ToInts to be entirely compatible with asn1.ObjectIdentifier. If we do clearly FromInts/ToInts have to reject components >31 bits, so that something can be roundtripped. We could also have ToInts return two bools, for one components >31 bits and one for components >63 bits, but that seems overkill.

[rolandshoemaker]

Because the underlying format of the type would just be the DER representation of an OID, a parsing method would probably just be as simple as ParseOID([]byte) (OID, error) with a check to make sure it's actually an OID 🤷.

[mateusz834]

I feel like the API would be better like this:

1. Add EqualObjectIdentifer to OID, to avoid memory allocations when comparing directly to []int.
2. Name changes:
   • FromInts -> FromObjectIdentifier or NewOIDFromObjectIdentifier or even (ObjectIdentifier).ToOID() (OID, error) instead.
   • ToInts -> ToObjectIdentifier
3. FromObjectIdentifer needs to return an error (or boolean)
4. place it in encoding/asn1

type OID struct {/*(...)*/}
// ParseOID parsed DER-encoded Object Identifier.
// On success, der is referenced in the OID struct.
// der must not be modified after parsing.
func ParseOID(der []byte) (OID, error) 
func FromObjectIdentifier(oid ObjectIdentifier) (OID, error)
func (oid OID) Equal(other OID) bool
func (oid OID) ToObjectIdentifier) (ObjectIdentifier, bool)
func (oid OID) EqualObjectIdentifier(other ObjectIdentifier) bool
func (oid OID) String() string

I am unsure about error vs boolean in ToObjectIdentifer and FromObjectIdentifer, it probably better to use one or another consistently.

I've gived it a shot in CL 503359

[gopherbot]

Change https://go.dev/cl/503359 mentions this issue: encoding/asn1: add new OID type

[andrewharrisatcheckr]

the expectation is that they will essentially always be parsed from DER using encoding/asn1, or golang.org/x/crypto/cryptobyte, and as such we don't need direct parsing methods, but we could perhaps provide them.

I would add, the current implementation of ParseCertificate calls down to cryptobyte String.ReadASN1Element, which explicitly does not support ASN.1 tag elements with a tag number > 30.

Per the ITU-T X.680 spec that defines ASN.1 tags, it seems like it might be useful to extend cryptobyte to support OID internationalized resource identifiers (tag numbers 35 and 36) as part of this work.

Ideally, cryptobyte would support the full ASN.1 tag spec, i.e tag numbers 31-36 as defined types for now and 37+ for future spec additions, however that may be out of scope.

(chiming in because this bit me in an unrelated way earlier today, and I was hoping to find a relatively active issue about it)

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[rsc]

It sounds like we want to scope this to just use in x509 and leave "the one true oid package" for external development. It would also be good to avoid a new API with big.Int in it if possible. When would people need to construct an OID from the big.Int forms?

[mateusz834]

It would also be good to avoid a new API with big.Int in it if possible. When would people need to construct an OID from the big.Int forms?

Probably never (assuming ParseOID is exported).

[rolandshoemaker]

@mateusz834 I think if we want to scope this purely to x509, which I think we do, it makes sense to just locally define it in the crypto/x509 package, and avoid adding methods that would facilitate its use outside of the package which crypto/x509 doesn't need.

Similarly for x509 usage, I'm not sure we need To/From methods for asn1.ObjectIdentifier. FromInts method was intended to replace the existing usage of asn1.ObjectIdentifier where the type is often instantiated using asn1.ObjectIdentifier{1, 2, 3}, for testing, comparisons, or populating certificate templates. I think an equals method for asn1.ObjectIdentifier pretty much covers all of the other cases.

Since parsing will happen internally to the certificate parser, and we are scoping this type to this package/context, I don't think we need to export ParseOID, as there is no clear use case for people outside of crypto/x509. I think the one use case where ParseOID would be valuable is if people actually want to instantiate OIDs (for testing, comparison, or populating certificates) that would overflow int64s, but I'm not sure how many people actually want to do this. At least for now it seems like 90% of the problems we are seeing are due to failure to parse certificates, rather than people wanting to create certificates with these massive OIDs.

I think for usage for replacing certificate policy OIDs all we need for now is the following (these can obviously be expanded later if we decide we need additional methods):

type OID struct {
    // private fields
}

// OIDFromInts creates a new OID using ints, each integer is a separate component.
func OIDFromInts(ints []uint64) (OID, error)

// Equal returns whether two OIDs are equal.
func (oid OID) Equal(other OID) bool

// EqualASN1OID returns whether an OID equals an asn1.ObjectIdentifier. If
// asn1.ObjectIdentifier cannot represent the OID specified by oid, because
// a component of OID requires more than 31 bits, it returns false.
func (oid OID) EqualASN1OID(other asn1.ObjectIdentifier) bool

// String returns the period concatenated string representation of an OID.
func (oid OID) String() string

[mateusz834]

@rolandshoemaker

OIDFromInts needs to return also an error.

Why not? (int64 -> uint64) Signed integers are useless here.

func OIDFromInts(ints []uint64) OID

Can you update the comment on EqualASN1OID (to explain the two booleans)?

[rolandshoemaker]

Oh I meant to delete the second bool, it was initially intended to indicate if it couldn't be compared because the components would be too big, but I think it's reasonable to just fold that into the overall return (as described in the doc comment).

uint64 for OIDFromInts seems reasonable. Why would it need an error return? There should be no way to make it fail that I can see (if we kept signed ints I guess that would make sense).

[mateusz834]

Why would it need an error return? There should be no way to make it fail that I can see (if we kept signed ints I guess that would make sense).

https://github.com/golang/crypto/blob/b4ddeeda5bc71549846db71ba23e83ecb26f36ed/cryptobyte/asn1.go#L163-L170

[rolandshoemaker]

Oh bah, good point, I forgot about the arcane component rules. Updated the comment.

[mateusz834]

// EqualASN1OID returns whether an OID equals an asn1.ObjectIdentifier. If
// asn1.ObjectIdentifier cannot represent the OID specified by oid, because
// a component of OID requires more than 31 bits, it returns false.
func (oid OID) EqualASN1OID(other asn1.ObjectIdentifier) bool

Just as a note the func (ObjectIdentifier) Equal() bool, does not have such 31-bit restriction. Don't know whether is it worth limiting it (EqualASN1OID). (Only parsing of ObjectIdentifier is limited to 31 bits).

[rolandshoemaker]

I don't think it makes sense to apply the restriction across the board, since a large part of why we are introducing this new type in the first place is so that we can accommodate OIDs which are broken because of this.

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[gopherbot]

Change https://go.dev/cl/520535 mentions this issue: crypto/x509 add new OID type and use it in Certificate

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group