Skip to content

crypto/rsa: some valid P1v1.5 signatures rejected by VerifyPKCS1v15 #16683

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
aaazalea opened this issue Aug 13, 2016 · 5 comments
Closed

crypto/rsa: some valid P1v1.5 signatures rejected by VerifyPKCS1v15 #16683

aaazalea opened this issue Aug 13, 2016 · 5 comments
Labels
FrozenDueToAge
Milestone
Go1.8

Comments

@aaazalea
Copy link
Contributor

Please answer these questions before submitting your issue. Thanks!

What version of Go are you using (go version)?

I'm using go version go1.6.2 darwin/amd64

What operating system and processor architecture are you using (go env)?

GOARCH="amd64"
GOBIN=""
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOOS="darwin"
GOPATH="/Users/jweisblat/gocode"
GORACE=""
GOROOT="/usr/local/Cellar/go/1.6.2/libexec"
GOTOOLDIR="/usr/local/Cellar/go/1.6.2/libexec/pkg/tool/darwin_amd64"
GO15VENDOREXPERIMENT="1"
CC="clang"
GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fno-common"
CXX="clang++"
CGO_ENABLED="1"

What did you do?

https://play.golang.org/p/Dh7S2wq-4c

This program tries to verify that one certificate is properly signed by another. The given signing certificate is the attestation certificate of a yubikey, as described on https://developers.yubico.com/PIV/Introduction/PIV_attestation.html

What did you expect to see?

I expected the program to finish successfully. The certificate is in fact properly signed - placing the certificates in the relevant files and running

openssl verify -partial_chain -CAfile /path/to/attestingCert /path/to/attestation (with openssl 1.0.2 for the partial_chain flag)

passes.

What did you see instead?

I got an error from crypto/rsa/pkcs1v15.go:293 - In particular, the check on line 285 fails, citing an incorrect "prefix".

The way go's crypto library implements this check is interesting. From crypto/rsa/pkcs1v15.go:

// These are ASN1 DER structures:
//   DigestInfo ::= SEQUENCE {
//     digestAlgorithm AlgorithmIdentifier,
//     digest OCTET STRING
//   }
// For performance, we don't use the generic ASN1 encoder. Rather, we
// precompute a prefix of the digest value that makes a valid ASN1 DER string
// with the correct contents.
var hashPrefixes = map[crypto.Hash][]byte{
    crypto.MD5:       {0x30, 0x20, 0x30, 0x0c, 0x06, 0x08, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x02, 0x05, 0x05, 0x00, 0x04, 0x10},
    crypto.SHA1:      {0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14},
    crypto.SHA224:    {0x30, 0x2d, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x04, 0x05, 0x00, 0x04, 0x1c},
    crypto.SHA256:    {0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20},
    crypto.SHA384:    {0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05, 0x00, 0x04, 0x30},
    crypto.SHA512:    {0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05, 0x00, 0x04, 0x40},
    crypto.MD5SHA1:   {}, // A special TLS case which doesn't use an ASN1 prefix.
    crypto.RIPEMD160: {0x30, 0x20, 0x30, 0x08, 0x06, 0x06, 0x28, 0xcf, 0x06, 0x03, 0x00, 0x31, 0x04, 0x14},
}

When the function which checks signatures checks that the signature is valid, rather than decoding the ASN.1 DER structure mentioned above, it checks that the structure is equal to the one it expects. However, there are in fact 2 legal ways of representing each of the above algorithms. RFC 4055 defines a set of oids for representing a digestAlgorithm:

When any of these four object identifiers appears within an
AlgorithmIdentifier, the parameters MUST be NULL. Implementations
MUST accept the parameters being absent as well as present.

The go implementation contains the ASN.1 structure corresponding to the object identifier with a NULL parameter. However, the certificates that yubikeys generate instead contain the ASN.1 structure without a NULL parameter. These examples give a digest of all zeroes, but that bitstring would normally contain the hashed value.

With parameter: https://lapo.it/asn1js/#3031300D0609608648016503040201050004200000000000000000000000000000000000000000000000000000000000000000
Without: https://lapo.it/asn1js/#302F300B060960864801650304020104200000000000000000000000000000000000000000000000000000000000000000

Thus, despite the certificate being valid, the go library finds the "prefix" to be incorrect and errors when validating it.

I see a few possible fixes:

  • rewrite the validation code so that it actually parses the relevant ASN.1 structures
  • add a second set of possible values and compare against both of them
  • something else?

I'd tend toward implementing the second of the above fixes, because the first seems more likely to introduce timing attacks toward breaking the relevant crypto; however, I'm not an expert and could be convinced to implement either.
@josharian josharian changed the title Some valid P1v1.5 signatures rejected by crypto.rsa.VerifyPKCS1v15 crypto/rsa: some valid P1v1.5 signatures rejected by VerifyPKCS1v15 Aug 13, 2016
@josharian josharian added this to the Go1.8 milestone Aug 13, 2016
@josharian
Copy link
Contributor

cc @agl

@agl
Copy link
Contributor

agl commented Aug 15, 2016

Specifying a complex structure for this data was a terrible mistake and has caused a lot of problems. We're doing pretty well expunging that mistake. Chrome (entirely), Android (in many places) and Google services implement RSA checking in the same fashion as Go. I don't wish to add complexity to this sensitive area of code I'm afraid.

@agl agl closed this as completed Aug 15, 2016
@aaazalea
Copy link
Contributor Author

I had already written a patch when you closed the issue, and it doesn't really increase the complexity of this function much - it adds a second hashPrefixes map corresponding to the other valid prefix for each SHA*-RSA choice. If your response was written with the goal of not implementing real ASN.1 code as opposed to an opposition to any increase in complexity at all, it might still be worth implementing in order to conform to the spec.

@agl
Copy link
Contributor

agl commented Aug 16, 2016

The spec for PKCS#1 v1.5 specifies the behaviour that Go implements. Steps 3 and 4 say to encode the expected message and compare.

Every TLS server and all but one (now two) certificates that I've seen manages to put the NULL in there. Sometimes the reality of the situation is such that concessions have to be made, but that's not the case here and there's good reason why we're strict about these things whenever possible in the security area.

The reality of implementations is that they're aimed in the general direction of a spec and then debugged until they roughly interoperate with one (or, if you're lucky, two) major implementations.

If some piece of code is inadvertently depending on some liberty of a major implementation then it might not find the problem until very late, when it fails in practice against a minor implementation. If implementations had been stricter then the problem would have been found sooner. The sooner a bug is found the cheaper the fix. (Ask the Estonian ID cards folks.)

Thus strict implementations help grow a healthy ecosystem. None the less, as shown here, the pressures are towards replicating every laxness in every implementation. That only works in the short-term however. We really want implementations that follow the spec for this as trying to parse the ASN.1 has been a disaster in practice and that means trying to defend the simple answer.

Additionally, implementations are reality, but specs are what gets analysed by researchers and proven. If there's a gap between the two then we can end up believing things that aren't actually true in reality.

So the real issue here is that OpenSSL parses signatures rather than comparing them and that has allowed Yubikey to end up inadvertently depending on it.

@davidben
Copy link
Contributor

davidben commented Aug 18, 2016 •
edited
Loading

The citation in RFC 4055, by the way, refers to OIDs like id-sha256WithRSAEncryption. That's for the signatureAlgorithm field here, and a few other similar fields in X.509. Fortunately, laxness there doesn't have as catastrophic of known consequences as with RSASSA-PKCS1-V1_5. Though it's still unfortunate it wasn't pinned down early enough.
https://tools.ietf.org/html/rfc5280#section-4.1.1.2

The DigestInfo structure in RSASSA-PKCS1-V1_5 is different and uses different OIDs (id-sha256 and friends).

@golang golang locked and limited conversation to collaborators Aug 18, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.8
Development

No branches or pull requests
5 participants
@agl @josharian @davidben @aaazalea @gopherbot