Subject: Re: [pkix] fyi: Sovereign Keys: an EFF proposal for more

From: Martin Rex <[email-masked]>
Date: Mon, 19 Dec 2011 20:32:05 +0100 (MET)

Michael StJohns wrote:
> 
> Encoding issues first:
> 1) The ASN1 SIGNED macro uses the signatureAlgorithm AlgorithmId value
>    in the outer wrapper to determine the signature type used to
>    validate the signature.
>
> 2) X.509 says that "signature contains the algorithm identifier for the
>    algorithm and hash function used by the CA in signing the certificate"
>    for the inside signature AlgorithmId.  That's in ADDITION to the
>    outside algorithmIdentifier and is a strong indicate tha X.509
>    expects them to be identical.

I'm not questioning the "intentions", but it certainly is a flawed assumption
to expect RPs to perform checks that are *NOT* explicitly listed in 6.1.3.
There *might* be implementations that do.

>
> 3)  RFC 5280 says (4.1.1.2)  about the certificate inside "signature field"
>     This field MUST contain the same algorithm identifier as the
>     signature field in the sequence tbsCertificate (Section 4.1.2.3).

It does *NOT* say this in 6.1.3, so it is perfectly OK for an RP
to simply not care.

>
> 4) Not all signature algorithms have NULL for their parameters field
>    (for example RSA PSS)

I know.  ITU-T X.509 11/2008 explictly calls for specification that define
AlgorithmIdentifiers to list exact constraints on valid parameters.
rfc3447 (and its predecessors 2437, 2313) specify NULL.

>
> 5) The certificate processing description in RFC5280 does not say
> "ensure the ASN1 and certificate is properly encoded" as that's pretty
> much a no-brainer.  Under your argument, I could pass in a signed object
> that just sort of looked like a certificate but had additional fields
> inside the signature wrapper and that would be OK since the signature
> just happened to verify and I was able to find all the certificate fields.

I don't think I said that.

RFC5280 certificate path validation requires you to look at details
of TBSCertificate, and when doing ASN.1 decoding, one normally does
all of the stuff that is "visible" in one go, any only the stuff
that is "ANY defined by" might get worked on in additional decoding
steps when considered relevant or necessary -- or may get ignored
otherwise.

That the SignatureAlgorithm on the Certificate structure and the
TBSCertificate structure should be the same is a "semantic" requirement,
something that is *NOT* implemented by the ASN.1 decoder, but rather
the application caller on top of the decoder.  AlgorithmIdentifier
parameters, on the other hand, are defined in a fashion that they
ought to be processed by the ASN.1 decoder.

> 
> For implementations:
> I believe at least a few implementations just do a look up of the
> encoded AlgorithmIdentifier rather than parsing out the OID in the AlgId.
> So any mucking about with the field will cause things to fail.

Curiously, a large percentage of the installed base (which is dominated
by only a few implementations) seems to not care.

> 
> So how about moving on from this rather *hackish* idea.
> The RPs that *might* accept are obviously broken.

Yes, but primarily their ASN.1 decoders seem to be broken.

-Martin

---

From: Stephen Kent <[email-masked]>
Date: Mon, 19 Dec 2011 15:41:17 -0500

At 8:32 PM +0100 12/19/11, Martin Rex wrote:
>...

Cert processing is presumed to take place using data extracted from a cert.
When cert syntax is violated, this data extraction should fail. The 
requirement that the alg ID in the cert and the alg ID in the sig 
block MUST match applies during the processing of the cert, prior to 
path processing. This might be a syntax-verified operation under the 
updated ASN.1 syntax. In any case, I agree with Mike that code that 
fails to match the two alg IDs creates a vulnerability and is non 
compliant.

>by only a few implementations) seems to not care.

Several years ago, Microsoft decided that it was not necessary to match
subject and issuer names durig  path validation. One might assume 
that MS products constitute a non-trivial part of the deployed base. 
Such behavior is still wrong.

Steve

---

From: Michael StJohns <[email-masked]>
Date: Mon, 19 Dec 2011 15:56:31 -0500

>There *might* be implementations that do.

I'm sure there are flawed implementations that do not check the match.  I am sure there are correct  implementations that do.  You can make no assumption which one your RP is.

There are any number of certificate requirements in the body of RFC5280 that are not reiterated in section 6.1.3 (or other where in 6) - that does not mean they are irrelevant for the validation of the certificate.

>steps when considered relevant or necessary -- or may get ignored

You hung your hat on 6.1.3 as being the only important part of verifying the certificate so  6.1.3(a) says 

>(a)  Verify the basic certificate information.  The certificate
>           MUST satisfy each of the following:
>
>         (1)  The signature on the certificate can be verified using
>              working_public_key_algorithm, the working_public_key, and
>              the working_public_key_parameters.
>
>         (2)  The certificate validity period includes the current time.
>
>         (3)  At the current time, the certificate is not revoked.  This
>              may be determined by obtaining the appropriate CRL
>              (Section 6.3), by status information, or by out-of-band
>              mechanisms.
>
>         (4)  The certificate issuer name is the working_issuer_name.

No where does it say that the certificate cannot have extra fields past the extensions, so by your argument since 6.1.3. is silent on the extra elements, then a certificate with extra fields - as long as it satisfies the above - would be acceptable.

If you claim that "verify the basic certificate information" covers ensuring correct ASN1 encoding of a Certificate structure, then I claim it also covers ensuring a match between the inside and outside signature algorithm.

---

From: Martin Rex <[email-masked]>
Date: Mon, 19 Dec 2011 23:33:56 +0100 (MET)

Stephen Kent wrote:
> updated ASN.1 syntax.

rfc5280 declares itself a profile of ITU-T X.509 08/2005,
and so far I have been unsuccessful to find any such requirement
in X.509.

X.509 does also not have a requirement for a CA certificate to
contain a "Basic Constraint CA=TRUE marked critical", that is something
that is specific to rfc5280 and its predecessors -- and the reason why
one might expect RPs to follow it is rfc5280 section 6.1.4 (k)

But without a requirement for comparing the two AlgIds in rfc5280
6.1.3 / 6.1.4, _no_ RP is required to perform any such comparison.

>
>                      In any case, I agree with Mike that code that 

Could you elaborate why exactly you believe this to be a security problem?

While X.509 certs and X.509 CRLs duplicate the signatureAlgorithm inside
the signed data, there is no such duplication in OCSP (rfc2560)
and CMS (the latter being reused by timestamping rfc3161).

If there was a security problem, then this probably should have been
changed prior to advancing CMS to full Internet standard (5652).

> Such behavior is still wrong.

I don't know their rationale for (not) doing this, so I can not comment
on whether it is acceptable.

ITU-T X.509 08/1997 (E) require comparison of the name chaining in
section 12.4.3 Certification Path Processing Procedure
uppper part of page 34 under (a).

rfc2459 requires the comparison of the name chaining in section
6.1 Basic Path validation, top of page 55 under (4).

rfc3280 reworded this in a (IMO less clear) fashion in
section 6.1.3 Basic Certificate Processing (a)(4) bottom of page 70.

Not comparing the names looks more like a potential evasion of
policy schemes rather than a security problem.  (Personally,
I consider all the policy stuff as part of a business model
enforcement rather than security architecture).

-Martin

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 20 Dec 2011 15:39:15 +1300

Michael StJohns <[email-masked]> writes:

>I'm sure there are flawed implementations that do not check the match. I am 
>sure there are correct implementations that do. You can make no assumption 
>which one your RP is.

Given the difficulty in locating implementations that even bothered checking 
whether the algoID parameters made any sense (the only ones that turned up 
were pretty obscure ones, no major/mainstream implementation even bothered 
checking the params), I'd say there's a pretty good likelihood that few, if 
any, will then go beyond that and check the match.

Peter.