crypto/x509: multi-value RDN sequence is not properly DER-ordered

[mrogers950]

RFC 5280 defines RelativeDistinguishedName as:
RelativeDistinguishedName ::= SET SIZE (1..MAX) OF AttributeTypeAndValue

With RDN being a ‘SET OF’ AttributeTypeAndValue this means that RDNSequence should be encoded as an ordered sequence.

According to the DER ITU-T text:
https://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf#%5B%7B%22num%22%3A77%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22FitH%22%7D%2C421%5D

11.6 Set-of components
The encodings of the component values of a set-of value shall appear in ascending order, the encodings being compared as octet strings with the shorter components being padded at their trailing end with 0-octets. NOTE – The padding octets are for comparison purposes only and do not appear in the encodings.

Note while this rule is not stating explicitly length-ordered, it ends up being firstly ordered by length since the length octet will be the first differing octect to be compared, and the shorter length will be a lower value.

The RDNSequence supporting functions (ToRDNSequence() and appendRDNs()) currently do not perform any ordering by length or otherwise and accept RDNs in the provided order.

https://play.golang.org/p/bnWPNJ_xCTu
Output:

00000000  30 2c 31 1b 30 0d 06 03  55 04 0a 13 06 66 6f 6f  |0,1.0...U....foo|
00000010  62 61 72 30 0a 06 03 55  04 0a 13 03 66 6f 6f 31  |bar0...U....foo1|
00000020  0d 30 0b 06 03 55 04 03  13 04 75 73 65 72        |.0...U....user|

The correctly ordered encoding would look like:

00000000  30 2c 31 1b 30 0a 06 03  55 04 0a 13 03 66 6f 6f  |0,1.0...U....foo|
00000010  30 0d 06 03 55 04 0a 13  06 66 6f 6f 62 61 72 31  |0...U....foobar1|
00000020  0d 30 0b 06 03 55 04 03  13 04 75 73 65 72        |.0...U....user|

This can become an issue when using golang-created certificates containing multi-value RDNs against implementations that adhere to the SET OF encoding rules (like GnuTLS/libtasn1). In the case of GnuTLS, it performs a re-encoding of the certificate when acting as a TLS client, resulting in the “fixing” of the subject RDNs into an ordered set, leading to a changed certificate and thus signature invalidation.

$ go version
go version go1.9 linux/amd64
$ go env
GOARCH="amd64"
GOBIN=""
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/mrogers/go"
GORACE=""
GOROOT="/usr/lib/golang"
GOTOOLDIR="/usr/lib/golang/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build850546982=/tmp/go-build -gno-record-gcc-switches"
CXX="g++"
CGO_ENABLED="1"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"

[simo5]

Note: in case of equal length a comparison by byte of the values would have to be done.

Also note: the GNUTLS client is being fixed to account for this kind of broken client certs,
https://gitlab.com/gnutls/gnutls/merge_requests/608

[simo5]

@FiloSottile any chance you'll look at this in the near future ?

[FiloSottile]

Aiming to look into this before the end of the week.

[simo5]

thanks

[FiloSottile]

This is an encoding/asn1 issue, it should order all SET OFs before encoding them since that's what DER specifies. (Can't tell exactly how SETs should be ordered though.)

I can fix this, but I'd like first confirmation from @agl that encoding/asn1 doesn't guarantee an Unmarshal(Marshal(x)) == x invariant, because this will break it, possibly causing issues like the GnuTLS one.

[FiloSottile]

Also, do we aim to error out on valid BER but invalid DER, or do we tolerate it? (In this case, we would have to error out parsing an unsorted SET OF to be strict.)

[simo5]

The first problem is that there is no SET OF support in encoding/asn1 and that structure is defined to be a SEQUENCE instead of a SET OF, they are identical on the wire so this is not immediately evident and it generally won't show as an issue.

You will need to tolerate unordered on receiving because otherwise you will break compatibility with your older self.

The ordering is done on the encoded octet, so you need to encode the set and then order its members. See the ITU-T spec and the workaround we have in Openshift (see links above) to get it right for now.

[FiloSottile]

encoding/asn1 does support SET and SET OF via a struct tag or when the type name ends in SET (see the asn1.Unmarshal docs), and indeed here the RDN are encoded as SET. The issue is that they are not sorted automatically while marshaling.

Agreed that we'll have to keep tolerating this here, but I was curious what the default stance on DER parsing is in encoding/asn1.

[FiloSottile]

@agl confirmed we have no such invariant, so let's fix this in Marshal by properly sorting SET OF entries when serializing. Still have to figure out if SETs also have a sorting requirement (I think they don't since they can be heterogeneous?).

[simo5]

The ITU-T documents says only SET OF is ordered, afaict.

[ChadSikorra]

Not ordered the same as a SET OF, but SET does have an ordering specified in X.690, Section 10.3, which applies to DER (which then references X.680):

10.3 Set components
The encodings of the component values of a set value shall appear in an order determined by their
tags as specified in 8.6 of ITU-T Rec. X.680 | ISO/IEC 8824-1.
NOTE – Where a component of the set is an untagged choice type, the location of that component
in the ordering will depend on the tag of the choice component being encoded.

Section 8.6 of X.680 states:

8.6
The canonical order for tags is based on the outermost tag of each type and is defined as follows:
a) those elements or alternatives with universal class tags shall appear first, followed by
those with application class tags, followed by those with context-specific tags, followed by those
with private class tags;
b) within each class of tags, the elements or alternatives shall appear in ascending order of their tag
numbers.

[vanrein]

This is a blocking concern to us. We're about to develop a document push protocol on top of AMQP 1.0 and are considering Go as the language for the software. Seeing this however, it would be unsafe to use Go with security as software might break on it.

The point is obviously just a minute encoding detail, but since it breaks certificate signatures on software that adheres to the specifications, we may have to avoid Go until it is fixed. What a pitty.

Is there a due date when this will be certainly fixed? I doubt you could promise anything of that kind, right?

Until then, is there a workaround, in the form of a correctly working certificate implementation that can be used with Go without risking incompatibility with other software?

[FiloSottile]

Sorry for letting this slip. It will definitely be fixed in Go 1.14, but it's not a small enough change to push during the Go 1.13 code freeze.

FWIW, the X.509 ecosystem is full of non-DER encodings, so virtually every verifier accepts mild standard deviations like this. Indeed, Go is used in a myriad of environments and incompatibility was only ever reported against GnuTLS, which has now been fixed.

Note that this only applies to pkix.Name fields of length higher than 1, which are fairly uncommon. As for a workaround, you can simply sort the pkix.Name fields correctly in your application.

@simo5 I am not convinced by your sorting implementation. That code does simply a length sort, when instead things should be sorted lexicographically, simply sorting shorter values before longer values that start with the shorter values.

octet strings with the shorter components being padded at their trailing end with 0-octets

So for example

bar1
foo
foobar
foox
foozzz
xx

or am I misunderstanding the specification?

[simo5]

@FiloSottile you are probably misunderstanding, it was quite a while ago so I forgot details, but I had to go through the ITU documents and read extra-carefully, and when I was done I was very surprised by the outcome which was completely unintuitive.
The code I had passed interop with GnuTLS at the time.

[simo5]

I think one of the key details was that ordering was done after encoding, see the first comment here which explains exactly what paragraphs to look at and the side effects of the scheme (length becomes determinant).

[FiloSottile]

I re-read all relevant parts I can find, and I still don't see how length would become first criteria (exactly because it's first encoded with padding, then sorted).

Moreover, notice the ordering from the original issue is foo, foobar1, user.

The correctly ordered encoding would look like:

00000000  30 2c 31 1b 30 0a 06 03  55 04 0a 13 03 66 6f 6f  |0,1.0...U....foo|
00000010  30 0d 06 03 55 04 0a 13  06 66 6f 6f 62 61 72 31  |0...U....foobar1|
00000020  0d 30 0b 06 03 55 04 03  13 04 75 73 65 72        |.0...U....user|

[simo5]

Big IIRC.
You need to first encode each string, when you do that you will get a byte buffer where the first distinguishing byte is the length. When comparing byte by byte this is the first byte that differs and it is what is used to order these byte buffers.
In case strings happen to have the same length then this byte will be identical, so then the next byte (the first char of the the string) is compared.

[andybons]

@FiloSottile given this comment:

it's not a small enough change to push during the Go 1.13 code freeze.

I would assume this remains true for the 1.14 code freeze. Should this be pushed to 1.15 and marked early-in-cycle?

[FiloSottile]

@simo5 is right, the sorted value includes the length prefix. I verified by running

openssl req -x509 -multivalue-rdn -subj "/CN=zzz+CN=aaa+CN=aaa1" -newkey rsa:512

which sorted them as aaa, zzz, aaa1.

Changing asn1.Unmarshal to be stricter is too big a change to do in Go 1.14, and it's even unclear if we should be strict about this, but it should be pretty simple to make encoding do the right thing, and we shouldn't ever be off-DER in what we generate.

I'll put together a CL.

[FiloSottile]

I tried to put together a change, and due to how the encoder works, it's not actually trivial. This was my fault for not doing it earlier, sorry. Since there is a workaround (sorting the sequence in your application code), let's push to Go 1.15.

[vanrein]

This MUST then be documented quite vigorously. IMHO this is not a reasonable workaround. You are passing complexity outside the API that is supposed to conceal it, for mere reasons of implementation effort. Applications will not (all) do this and this delaying approach will only make the stampede of Go's incompatibility continue. Please put in the effort to be standards compliant, like the others (should) have.

[FiloSottile]

To be clear, I'm not saying we shouldn't fix this. Of course we shouldn't generate non-DER. I'm saying I failed to do so before the tree froze, and the change is not small enough to merge after the freeze. If you want to make sure this is fixed in Go 1.15, you can also make a CL.

(By the way, this issue is as old as encoding/asn1, but was reported only last year. There isn't a strong argument for its urgency.)

[dmitshur]

This issue is currently labeled as early-in-cycle for Go 1.15. That time is now, so friendly ping. If it no longer needs to be done early in cycle, that label can be removed.

[vanrein]

This task has been here for a long time, and all this time Go has been incompatible and causing problems for other toolkits. The sooner the better, really.

[gopherbot]

Change https://golang.org/cl/226984 mentions this issue: encoding/asn1: sort order of 'SET of' components during Marshal