Subject: [TLS] Verifying X.509 Certificate Chains out of order

From: Simon Josefsson <[email-masked]>
Date: Mon, 06 Oct 2008 10:51:25 +0200

All,

We've received a request to verify X.509 certificate chains out of order
in GnuTLS.  Doing that would violate the following in RFC 5246 (earlier
versions had similar language), §7.4.2:

   certificate_list
      This is a sequence (chain) of certificates.  The sender's
      certificate MUST come first in the list.  Each following
      certificate MUST directly certify the one preceding it.  Because
      certificate validation requires that root keys be distributed
      independently, the self-signed certificate that specifies the root
      certificate authority MAY be omitted from the chain, under the
      assumption that the remote end must already possess it in order to
      validate it in any case.

It is claimed that OpenSSL, IE and Firefox does not enforce the second
MUST in the paragraph above, and succeeds in verifying an
out-of-sequence chain.  I haven't verified the claim.  It appears as if
the OpenSSL developers don't consider their behaviour as a bug (see
reply below).

For more details, including the particular certificate chain in this
example, see:

http://thread.gmane.org/gmane.network.gnutls.general/1383/focus=1384

I can see several reasons to enforce the MUST recommendation here, e.g.,
covert channels, DoS-considerations, unneeded complexity.

What are others opinion on this?  I'm looking for some guidance on
whether we should modify our current behaviour.

/Simon

Peter Volkov <[email-masked]> writes:

> Is it possible to do something similar in gnutls? It looks like there
> are reasons to validate certificate with wrong order...
>
> -------- Forwarded message --------
> From: Tim Hudson <tjh AT cryptsoft  com>
> Reply-TO: [email-masked]
> TO: [email-masked]
>
> Peter Volkov wrote:
>> CC'ing openssl developers for their opinions, since I think this
>> behavior better to have consistent or configurable. Description of the
>> problem is here:
>
> Placing this in context - connect with internet explorer or firefox to 
> https://metasploit.com/ and you will see that both of those independent 
> implementations see nothing wrong with the certificate chain and handle the 
> redirect to http://metasploit.com/ without and errors or warnings.
>
> Implementations typically take the list of certificates as untrusted 
> certificates to add into the process of walking the certificate chain to a 
> trusted root certificate. There are pragmatic reasons for doing it this way.
>
>  From an interoperability point of view remember the adage - "Be strict in what 
> you generate, be liberal in what you accept"
>
> Tim.
> ______________________________________________________________________
>
>
> -- 
> Peter.
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: [email-masked] (Peter Gutmann)
Date: Mon, 06 Oct 2008 22:44:49 +1300

>the OpenSSL developers don't consider their behaviour as a bug (see

Add cryptlib to the list of implementations that don't care about the order. 
In fact I'd be kinda surprised if anyone (well, apart from GnuTLS) cared about 
cert order.

>whether we should modify our current behaviour.

I'd say modify it, in fact I'm not sure what the rationale for requiring 
ordering was in the original spec, "it's tidier that way" doesn't strike me as 
a good argument :-).

Peter.

---

From: Rob Dugal <[email-masked]>
Date: Mon, 6 Oct 2008 07:57:01 -0400

Certicom's SSL-C toolkit does verify out of order chains but will generate verification warnings that may be overridden by applications.

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of Peter Gutmann
> Sent: Monday, October 06, 2008 5:45 AM
> To: [email-masked]; [email-masked]
> Subject: Re: [TLS] Verifying X.509 Certificate Chains out of order
>

---

From: Dr Stephen Henson <[email-masked]>
Date: Mon, 06 Oct 2008 13:06:31 +0100

> In fact I'd be kinda surprised if anyone (well, apart from GnuTLS) cared about 

OpenSSL does verify chains out of order and indeed incomplete chains if
appropriate certificates are trusted.

I would say though that particular server is misconfigured.

> ordering was in the original spec, "it's tidier that way" doesn't strike me as 

This raises a point I've wondered about for a while... Various PKIX
standards allow more than one chain between a root and EE certificate
(cross certification et al) so the (possibly almost) complete one a
server presents may not be the one a client will trust. CRLs can have
distinct paths too.

The wording in the specs (to me at least) implies one unique validation
path.

The CMS standards for example don't have the ordering requirement they
merely allow a set of "useful certificates" which may contain more or
less certificates than necessary to build a chain.

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 07 Oct 2008 01:50:16 +1300

>server presents may not be the one a client will trust. CRLs can have

That's the spaghetti PKI model.  Anyone who wants to get involved in that 
madness pretty much deserves what they get :-).

>less certificates than necessary to build a chain.

I think they were bowing to the inevitable, people will stuff whatever they 
feel like into these things no matter what the spec requires.  Having said 
that I've never encountered a bunch of certs in a CMS object that didn't have 
an obvious path from the EE to some top-level CA cert.

Peter.

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 06 Oct 2008 07:41:52 -0700

At Mon, 06 Oct 2008 10:51:25 +0200,
> covert channels, DoS-considerations, unneeded complexity.

I think there are two separate issues here:

(1) Whether implementations should be required to send certificates
    in a specific order.
(2) Whether implementations should generate an error if they are
    received in another order.

Put me in the "Yes" category for (1). It makes the verifying 
implementation considerably easier. This isn't an issue if
you have a database-based verifier as is required for CMS,
but if you don't, then it's a lot easier to simply verify 
that C_n is verified by C_n+1. So, if you're doing just
a TLS stack and not a generic crypto stack, then this 
restriction helps. PureTLS cares about order.

As for (2), I think that's more debatable. The argument
against it is the usual flexibility argument. The argument
for it is early detection of nonconforming peers. Note that
I don't consider RFC 5246 to require enforcing this MUST.
It's simply silent on this point. Implementations which
verify out of order are still conforming, IMHO.

-Ekr

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 6 Oct 2008 11:33:54 -0400

On Mon, 06 Oct 2008 07:41:52 -0700

>     received in another order.
"Be conservative in what you send; be liberal in what you accept."

		--Steve Bellovin, http://www.cs.columbia.edu/~smb
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: Martin Rex <[email-masked]>
Date: Mon, 6 Oct 2008 20:45:38 +0200 (MEST)

> "Be conservative in what you send; be liberal in what you accept."

That was my first thought, too.  :)

However, the really interesting question for a customer/consumer
of a technology is actually this variant of (2):

(2a) if interoperability of two independent implementations of TLS
     fail because one side aborts with a fatal error if it receives
     an unordered certificate_list, who is to blame?

Maybe it should be reworded to say

  "You MUST fix your implementation if you fail to interoperate
   with peers that report an error when receiving an unordered list

I recently had a customer complain because he would have liked to
use SSL client cert authentication with a particular kind of
middle box from a router vendor, but found himself unable to
configure that, because that middle box did not offer a possibility
to configure an certificate_authorities list to be sent in
the CertificateRequest message.

Looking at the official protocol spec, the possibility to send an
empty list of certificate_authorities in the CertificateRequest
message was introduced as a purely optional feature with TLS v1.1.
It was _NOT_ previously allowed to send an empty list in
the SSL v3 and TLS v1.0 specifications!

I'm aware that some implementations have been violating this
requirement in the SSLv3 and TLSv1.0 spec (instead of failing on
an incomplete configuration), but I think it is a pretty dumb
engineering decision to create an implementation of SSL/TLS
where it is possible to configure the Server to request a
client Certificate and NO MEANS to configure the list of
certificate_authorities for the ClientRequest message,
because this list MUST be sent to SSLv3 and TLS v1.0 client, and
it will also be required for interoperability with TLS v1.1+
clients that do not implement support for an empty list.

-Martin

---

From: Martin Rex <[email-masked]>
Date: Mon, 6 Oct 2008 21:09:36 +0200 (MEST)

Peter Gutmann wrote:
> In fact I'd be kinda surprised if anyone (well, apart from GnuTLS) cared
> about cert order.

All implementations that seriously care about (server) performance
ought to fail with an unordered certificate_list (and not try to
reorder themselves).  Our OEM implementation does care.

> ordering was in the original spec, "it's tidier that way" doesn't
> strike me as a good argument :-).

It is a big waste to sort and sort and sort the list each time
it is processed.  The one who is persisting the data (credential holder)
can sort it once and for all.

Looking at their specs, even the WebServicesSecurity folks are prefering
the ordered list X509PKIPathv1 over the PKCS7 unordered bag of certificates.
(and someone who uses XML to build a solution does otherwise not care
 very much about performance).

-Martin

---

From: Mike <[email-masked]>
Date: Mon, 06 Oct 2008 15:57:29 -0700

> can sort it once and for all.

As another data point, my software will first attempt to validate the
certificate chain in the order it was received, but if it finds that
one certificate did not issue the previous one, it then attempts to
put them in the correct order and revalidate the chain.

I had to do this sometime last year because I couldn't connect to one
of the major credit card companies' websites with my own software, but
my browsers were able to.  An additional problem with that site was
their CRL was PEM encoded!

As has been said, be liberal in what you accept....

Mike

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 07 Oct 2008 16:12:46 +1300

Martin Rex <[email-masked]> writes:

>All implementations that seriously care about (server) performance ought to
>fail with an unordered certificate_list (and not try to reorder themselves).
>Our OEM implementation does care.

Wow, how on earth did you manage to come up with an implementation where the
overhead of doing this even registers?  It's not as if you're bubble-sorting a
million-entry database, it's typically three certs and the "sort" is swapping
a '->nextCert' pointer.

Another issue is that some implementations aren't purely SSL but are general- 
purpose security libraries that handle bag-o-certs as an abstraction for 
several security protocols.  In my code for example it's actually more work 
not to sort than to sort because I'd have to include special-case handling for 
situations where the certs might already be sorted, passing around extra 
parameters to control this, more code-flow paths to test, etc.

Peter.

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 07 Oct 2008 16:27:22 +1300

Martin Rex <[email-masked]> writes:

>Looking at the official protocol spec, the possibility to send an empty list
>of certificate_authorities in the CertificateRequest message was introduced
>as a purely optional feature with TLS v1.1. It was _NOT_ previously allowed
>to send an empty list in the SSL v3 and TLS v1.0 specifications!

Yes it is.  The minimum length 3 can be used to encode a zero-length ASN.1
SEQUENCE (using BER encoding), there's nothing there that says it has to
contain anything.  I've been sending this in my certRequest for, oh, about 10
years now without running into any problems.

(Having said that, since client certs are so rarely used if there were
problems it's unlikely you'd ever see them, but in any case it's worked fine
so far).

>I think it is a pretty dumb engineering decision to create an implementation
>of SSL/TLS where it is possible to configure the Server to request a client
>Certificate and NO MEANS to configure the list of certificate_authorities for
>the ClientRequest message

Why?  The reason I never bothered to implement this is because I can't see any
use for it, if a server asks for a cert from the client then the client will
either use whatever cert it has for that server or respond "no-cert".  Even in
the unlikely situation that the client has multiple certs all intended for SSL
client auth (most users have zero certs for SSL client auth), unless every one
of them is specially chosen to be from a different CA then specifying the CA
name will have the same effect as specifying no CA name.

All this does is add uneccessary complexity (both to the implementation itself 
and for the user who has to configure it and deal with the results) and 
increase the attack surface.  If I was able to identify a good purpose for it 
(SSH uses exactly the same auth mechanism and gets by just fine without it) 
*and* if any user ever asked for it I'd think about adding support for it, but 
until then I've left it (along with a zillion other often-incomprehensible 
bits and pieces in standards) as a TODO.

Peter.

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 7 Oct 2008 11:04:03 +0100

Just agreeing on the principle that implementers should be forced to send the certificates in order but it definitely must be allowed to accept out of order chains.
As long as I can use, some or all, of the provided certificates to construct a valid path, and I'm willing to undertake the effort to do so, then it would be quite senseless to force me to reject that path.

Also, In the practical world of cross-certification and bridge CAs, it is quite possible that I in any case as relying party only will use a subset of the provided certificates.

Stefan Santesson
Senior Program Manager
Windows Security, Standards

> Sent: den 7 oktober 2008 05:27
> To: [email-masked]
> Cc: [email-masked]
> empty list

---

From: Martin Rex <[email-masked]>
Date: Tue, 7 Oct 2008 12:20:56 +0200 (MEST)

Peter Gutmann wrote:
> overhead of doing this even registers?

(It's an OEM implemenation I happen to support, not my implementation.)

In a sensible PKI implementation there are distinct datatypes for
unordered bags of certs and an ordered certificate chain, and
the certificate chain verifier operates only on the ordered chain.
better modularisation of code, less bugs, less code, faster.

It makes perfect sense to require ordered lists in procotols such as in an
SSL certificate_list and X509PKIPathv1 in WS-Security and use unordered
lists only where performance has low importance (PKCS7/CMS) or usability
is desired (User interfaces).

-Martin

---

From: [email-masked]
Date: Tue, 7 Oct 2008 12:25:03 +0200

> ordering was in the original spec, "it's tidier that way" doesn't strike 
me as 

Consider TLS on low-end or embeddede devices with limited ressources. 
Walking through the chain becomes difficult or even impossible if 
there is no order. 

regards, 
Axel Heider

---

From: Martin Rex <[email-masked]>
Date: Tue, 7 Oct 2008 12:49:03 +0200 (MEST)

> problems it's unlikely you'd ever see them, but in any case it's worked fine

The problems aren't that obvious, because hardly anyone has been
using client certificates so far.   We've been using SSL client certs
for Single Sign-On with WebBrowsers for 8 years and 10k+ users, and
we've run into various interop problems with many implementations.

The semantics for an empty list were not defined in SSLv3 and TLSv1.0,
so there's nothing in the spec that says an empty list is allowed.
So the behaviour is at best "implementation defined", but it is definitely
not standardized.

> Why?

Blindly relying on a feature that is at best "implementation defined"
is pretty much always a dumb engineering decision.

> The reason I never bothered to implement this is because I can't see any

The situation that you describe as "unlikely" is the situation that is
going to be the norm when SSL client certs start getting used in a
serious fashion.

Lets try to explain the behaviour of a server not sending
a certificate_authorities list for common people:                
                                                                   
You walk up to a restaurant for a dinner.  The guard at the door   
tells you that you need a membership card in order to enter and    
hands you a form to fill in and prove your membership    however he
refuses to tell you which membership he will consider acceptable.  
Actually    he promises you that if you happen to pick one that    
is not acceptable, he will send you away with a painful kick in    
the butt.                                                          

Look at X509 certificates as you look at credit cards, customer cards,
membership cards and all the other plastic that populates your wallet.
There is never going to be just one, because each issuer want to retain
his very own authority to revoke his card -- and that should not interfere
with the validity of any of the other cards.

In the Web-Browser scenario, where the SSL protocol was born, that
kind of use and the availability of multiple SSL client cert has
been a design feature from the beginning.

Another serious problem of the "server sends nothing" approach is
that it requires the client to blindly perform an expensive public key
operation and this may incur the overhead/incovenience of prompting
the user to insert a hardware token and/or enter a PIN to authorize
a private key operation -- which can be entirely avoided if the
server announces what CAs it trusts and there is no match to
the credentials available to the client.

-Martin

---

From: Martin Rex <[email-masked]>
Date: Tue, 7 Oct 2008 13:09:57 +0200 (MEST)

Stefan Santesson wrote:
> 
> Just agreeing on the principle that implementers should be forced to
> send the certificates in order but it definitely must be allowed
> to accept out of order chains.

I have absolutely no problem with implementations that accept an
unordered list.  However, implementations that accept an unordered
list should make sure they find a RELIABLE means to check that
they're always *SENDING* ordered lists, because a simple interop
check with their own client&server code or with other "unordered
accepting" implementations is NOT going to report bugs in
their *sending* implementation.

"Be liberal in what you accept" can be very dangerous with
careless implementors, because it will often make it more difficult
to verify whether your implementation is really conservative
with what it sends.  This may ruin the usefulness of
an originally sensible standard/spec.

>
> As long as I can use, some or all, of the provided certificates
> to construct a valid path, and I'm willing to undertake the effort
> to do so, then it would be quite senseless to force me to reject that path.

I wouldn't be surprised if some implementations of PKI would follow AIA
while building a chain from an incomplete unordered set.
*I* certainly would not want *my* servers to do that.

> 
> Also, In the practical world of cross-certification and bridge CAs,
> it is quite possible that I in any case as relying party only will
> use a subset of the provided certificates.

That's a whole different can of worms.

It should be possible to chop off the overly complexx cross-cert and
bridge-CA nonsense and treat some intermediate CAs as trust anchors
instead.  This is more likely to work and makes failures much
easier to understand.  :)

-Martin

---

From: Martin Rex <[email-masked]>
Date: Tue, 7 Oct 2008 13:43:53 +0200 (MEST)

Martin Rex wrote:
> unordered list.

Thinking about it, what exactly do you mean with unordered?

Since there isn't any additional information in the protocol to
identity the end-entity cert in the certificate_list, that certificate
will have to be the first.  Or does your code really apply heuristics
in locating the end entity cert?

In PKCS#7 there is the the signerinfos (issuer&serial) that make the
search in the unordered and only loosely related CertificateAndCertificates
bag at least deterministic (not purely heuristic).

-Martin

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 08 Oct 2008 01:25:22 +1300

[Replying to two messages at once]

[email-masked] writes:

>Consider TLS on low-end or embeddede devices with limited ressources. Walking
>through the chain becomes difficult or even impossible if there is no order.

Again, how can you create an implementation that can run the entire SSL
protocol but can't manage a few 32-bit pointers across three or four certs?
This seems like a total red herring, it's difficult to think of an
implementation that can perform the necessary cert verification but somehow
can't manage an extra pointer swap.

(Well, I'm sure I can come up with some pathological case where you can do one
and not the other, but I'd have to apply some pretty creative thinking :-).

>The situation that you describe as "unlikely" is the situation that is going
>to be the norm when SSL client certs start getting used in a serious fashion.

Oh, in that case there's nothing to worry about, if I can wait until PKI
starts working before I need to address it then I'm OK.

>You walk up to a restaurant for a dinner.  The guard at the door tells you
>that you need a membership card in order to enter and hands you a form to
>fill in and prove your membership    however he refuses to tell you which
>membership he will consider acceptable. Actually    he promises you that if
>you happen to pick one that is not acceptable, he will send you away with a
>painful kick in the butt.

What a marvellously nonsensical example.  If I go to http://www.amazon.com I
enter the password I use for Amazon.  If I need to provide a cert, I provide
the cert I use for Amazon.  End of story.  This procedure has worked just fine
for more than ten years now for SSH, which I'm sure has a much larger and more
diverse user base than client-side SSL certs ever will.

>Another serious problem of the "server sends nothing" approach is that it
>requires the client to blindly perform an expensive public key operation and
>this may incur the overhead/incovenience of prompting the user to insert a
>hardware token and/or enter a PIN to authorize a private key operation --
>which can be entirely avoided if the server announces what CAs it trusts and
>there is no match to the credentials available to the client.

Sure, I'll admit that one's a real issue in the special situation where this
specific case applies.  OTOH I'm happy to leave things as they are until
client certs take off before I look at it further, I've got way too much other
stuff to work on that's more pressing than this.

And that's the real killer for this I think: If you're going to go with these
niche variations that almost no-one uses, you sort of have to accept that
you're going to be in a world of pain.

Peter.

---

From: Alexander Klink <[email-masked]>
Date: Tue, 7 Oct 2008 15:48:05 +0200

> while building a chain from an incomplete unordered set.

Indeed. Not sure what this has to do with the ordered/unordered
discussion, though, but Microsoft's CryptoAPI does that in certain cases
(luckily, not always), see
http://www.cynops.de/techzone/http_over_x509.html

> *I* certainly would not want *my* servers to do that.

They turned that off in the server case, I still don't like the idea of
clients sending arbitrary HTTP requests in response to some SPAM mail.

While we have someone from Microsoft on the thread - any ideas on when
this will be fixed - I reported it more than 6 months ago now and
haven't heard back from MSRC?

Cheers,
  Alex
-- 
Dipl.-Math. Alexander Klink | IT-Security Engineer |    [email-masked]
 mobile: +49 (0)178 2121703 |          Cynops GmbH | http://www.cynops.de
----------------------------+----------------------+---------------------
      HRB 7833, Amtsgericht | USt-Id: DE 213094986 |     Geschäftsführer:
     Bad Homburg v. d. Höhe |                      |      Martin Bartosch
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 07 Oct 2008 07:00:00 -0700

At Tue, 7 Oct 2008 13:43:53 +0200 (MEST),
> in locating the end entity cert?

This is an excellent point. It does seem rather problematic to
have multiple candidate EE certs, especially because in many
cases the SSL stack does not know the peer's expected name.

-Ekr

---

From: Martin Rex <[email-masked]>
Date: Tue, 7 Oct 2008 16:09:16 +0200 (MEST)

> years now without running into any problems.

Looking at the TLS v1.0 spec again:

       opaque DistinguishedName<1..2^16-1>;

       struct {
           ClientCertificateType certificate_types<1..2^8-1>;
           DistinguishedName certificate_authorities<3..2^16-1>;
       } CertificateRequest;

Would a zero-length ASN.1 SEQUENCE not require that DistinguishedName
have a zero length?

TLS v1.1 added support for an empty list with this change:

      opaque DistinguishedName<1..2^16-1>;

      struct {
          ClientCertificateType certificate_types<1..2^8-1>;
          DistinguishedName certificate_authorities<0..2^16-1>;
      } CertificateRequest;

which allows certificate_authorities to be empty, but still requires
DistinguishedName to be non-empty (if sent).

(I admit I've never implemented SSL/TLS, so I'm not deeply intimate
 with the actual code).

-Martin

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 08 Oct 2008 03:14:19 +1300

Martin Rex <[email-masked]> writes:

>Would a zero-length ASN.1 SEQUENCE not require that DistinguishedName have a
>zero length?

A zero-length BER encoding of a SEQUENCE would be 30 81 00, which meets the
minimum-length requirements of 3 bytes.

(I'd always assumed that the limit of 3 bytes was specifically to allow this
encoding of an empty DN, since it's not possible to get a DN that fits into 3
bytes).

Peter.

---

From: Peter Sylvester <[email-masked]>
Date: Tue, 07 Oct 2008 16:38:19 +0200

I am not sure that the following structure is properly defined:

Structure of this message:

      opaque ASN.1Cert<1..2^24-1>;

      struct {
          ASN.1Cert certificate_list<0..2^24-1>;
      } Certificate;

   certificate_list
      This is a sequence (chain) of certificates. 

A little bit later: 

Also, PKCS #7 defines a SET rather than a SEQUENCE, making the task
   of parsing the list more difficult. 

Still, there is no thing that indicates D|B|XER encoding of
something like  SEQUENCE OF Certificate"

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 07 Oct 2008 08:10:08 -0700

At Tue, 07 Oct 2008 16:38:19 +0200,
Peter Sylvester wrote:
> 
> [1  <multipart/signed (7bit)>]
> [1.1  <text/plain; ISO-8859-1 (7bit)>]

I don't think I understand the question: this isn't any kind of 
ASN.1 structure. It's a TLS vector DER-encoded certs. 
I.e.

24-bit length field = Y
   24-bit length field = X  \ cert 1
   encoded cert (length X)  /
   24-bit length field = W  \ cert 2
   encoded cert (length W)  /

-Ekr

---

From: Martin Rex <[email-masked]>
Date: Tue, 7 Oct 2008 17:17:57 +0200 (MEST)

> encoding of an empty DN, since it's not possible to get a DN that fits into 3

That interpretation appears quite confused to me.

First of all, the 3 bytes minimum is listed for the sequence of
DistinguishedName, and that includes a 2-byte length field for
the certificate_authorities<3..2^16-1> vector.

The zero-length BER encoding of a SEQUENCE would apply to the
DistinguishedName element only, but there the minimum length
ist listed as 1, not 3. (I was also mistaken about the actual encoding
of structure elements in TLS when I wrote my first posting on this).

But I really dislike the idea of expecting an empty DName (i.e.
one that contains no RDName elements in the ASN.1 SEQUENCE) should
have the same meaning as _NO_ DName at all!  Are you sure that
this notion is interoperable with other implementations?

-Martin

---

From: Peter Sylvester <[email-masked]>
Date: Tue, 07 Oct 2008 17:54:42 +0200

> ASN.1 structure. It's a TLS vector DER-encoded certs. 
ouups; right.

Is ASN.1Cert defined in the text.
It does not says that you have a DER encoded cert.
It could be BER, CER, DER, at least partially. But
not XER and not PEM.

Anyway, no big deal.

-- 

<http://www.edelweb.fr>
*Edel/W/eb* 	Peter SYLVESTER
Consultant Sécurité des Systèmes d'Information
-----------------------------------------------------------
EdelWeb - Groupe ON-X
15, quai de Dion-Bouton
F-92816 Puteaux Cedex
Tel : +33.1.40.99.14.14 / Fax : +33.1.40.99.99.58
www.edelweb.fr <http://www.edelweb.fr> / www.on-x.com <http://www.on-x.com>
-----------------------------------------------------------
To verify the message signature, see edelpki.edelweb.fr 
<http://edelpki.edelweb.fr/>
Cela vous permet de charger le certificat de l'autorité de racine 
<http://edelpki.edelweb.fr/cacerts/EdelPKI-ca.der>;
die Liste mit zurückgerufenen Zertifikaten finden Sie da auch.

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 7 Oct 2008 18:01:12 +0100

On the original question:

> out-of-sequence chain.  I haven't verified the claim.

A Microsoft based SSL server will insert the certificates in order. A Microsoft based SSL client doesn't require the certificates to be in order. The client simply passes these certificates to the CertGetCertificateChain API in the hAdditionalStore parameter. This will validate the subject certificate regardless of order.

Stefan Santesson
Senior Program Manager

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Simon Josefsson
> Sent: den 6 oktober 2008 10:51
> To: [email-masked]
> Subject: [TLS] Verifying X.509 Certificate Chains out of order
>
> All,
>

---

From: Martin Rex <[email-masked]>
Date: Tue, 7 Oct 2008 23:30:25 +0200 (MEST)

Stefan Santesson wrote:
> A Microsoft based SSL server will insert the certificates in order.
> A Microsoft based SSL client doesn't require the certificates to be
> in order. The client simply passes these certificates to the
> CertGetCertificateChain API in the hAdditionalStore parameter.
> This will validate the subject certificate regardless of order.

I would appreciate if we could discuss the issue with terms of simple
facts instead of in terms of a proprietary API.

My familiarity with Microsoft CryptoAPI is close to zero,
but a first glance suggests that you MUST explicitly provide
an End Entity cert to CertGetCertificateChain(), parameter pCertContext.

Either you have a hen-and-egg problem, or the certificate_list
is not as unsorted as you claim it is.  How do you know which one
is the End Entity cert without either relying that it is the first
cert (as required by all existings TLS specs) or by first doing
a manual search and applying heuristics (something that I seriously
frown upon).

-Martin

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 7 Oct 2008 23:07:06 +0100

Martin,

I'm not discussing the issue from the context of MS API. I was trying to answer a direct question.

The first certificate is the EE cert. the rest of the order does not matter for the verifier.

Stefan Santesson
Senior Program Manager

> From: Martin Rex [mailto:[email-masked]]
> Sent: den 7 oktober 2008 23:30
> To: Stefan Santesson
> Cc: [email-masked]; [email-masked]

---

From: [email-masked] (Peter Gutmann)
Date: Thu, 09 Oct 2008 01:12:40 +1300

Martin Rex <[email-masked]> writes:

>But I really dislike the idea of expecting an empty DName (i.e. one that
>contains no RDName elements in the ASN.1 SEQUENCE) should have the same
>meaning as _NO_ DName at all!  Are you sure that this notion is interoperable
>with other implementations?

Because TLS client certs are so rarely used it's hard to say, the best I can
say is "I haven't run into problems so far", but that doesn't mean much given
the very small sample size.  A side-reason for leaving things this way is that
if anyone ever does run into this then it'll break in an obvious way, they'll
get back to me, and I can then get some hard data on what they're trying to do
with it and what sort of behaviour they expect from it.

As a generalisation, you'd be amazed at the total garbage you can put into
fields in security protocols and no-one notices.  Look at the (rather out of
date) shopping-list of certificate bugs in
http://www.cypherpunks.to/~peter/T2a_X509_Certs.pdf, there have even been
cases where major CAs have put random garbage (in some cases not even valid
ASN.1) into cert fields and no-one noticed.  So it could well be that
implementations are oblivious to whatever's in the CA-DN fields.  For example
since my code can't do anything useful with them it just skips them on read,
so there could be anything in there.  It's like TLS-Ext extensions (or X.509
extensions, or CMS attributes, or ...), if you can't figure out what to do
with something optional like this and it doesn't affect the protocol operation
then you can ignore it and continue.

Peter.

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 8 Oct 2008 09:08:03 -0400

On Thu, 09 Oct 2008 01:12:40 +1300
[email-masked] (Peter Gutmann) wrote:

> >But I really dislike the idea of expecting an empty DName (i.e. one
> >that contains no RDName elements in the ASN.1 SEQUENCE) should have
> >the same meaning as _NO_ DName at all!  Are you sure that this
> >notion is interoperable with other implementations?
> 
> Because TLS client certs are so rarely used it's hard to say, the
> best I can say is "I haven't run into problems so far", but that
> doesn't mean much given the very small sample size. 

FYI, my favorite MUA (claws-mail) has support for client-side
certificates in its latest release.  I'll let you know how well they
work...

---

From: [email-masked]
Date: Wed, 8 Oct 2008 15:13:12 +0200

Peter,

> can't manage an extra pointer swap.

It's not the pointers, but the certificates that need to be stored 
temporary, too. If you sum all this little things that could be 
allowed at the cost of just some more memory, using TLS for low end 
devices becomes harder and harder - and less interesting despite it
beeing a well known standard that people really trust in.

regards,
Axel Heider

---

From: Martin Rex <[email-masked]>
Date: Fri, 10 Oct 2008 21:29:38 +0200 (MEST)

> can't manage an extra pointer swap.

It all depends on the PKI software (and the modularization of APIs
and datatypes of that PKI software) how much wasted effort there is.

Since Stefan mentioned it lets take a look at Microsoft SChannel/CryptoAPI
how it might be working there.

I don't know the detail, but Stefan mentioned that "CertGetCertificateChain"
is called used at some point.

Looking at the (relevant) input and output parameters:
  CertGetCertificateChain
       PCCERT_CONTEXT        pCertContext,
       HCERTSTORE            hAdditionalStore,
       PCCERT_CHAIN_CONTEXT* ppChainContext

So in order to pass any additional certs besides the initial
end entity cert from the certificate_list of the SSL/TLS handshake
message, one must first create a "HCERTSTORE" and parse&store
the additional certificates from the certificate_list there.

The output of CertGetCertificateChain() is a CERT_CHAIN_CONTEXT
that contains one (or more) CERT_SIMPLE_CHAIN.  I don't see it in
the documentation (and its not obvious from the function name),
but I assume that the signatures on the output certificate chain has
also been verified.

Lacking experience I don't know how many duplicates of unparsed
certificates are being created in this process.

An optimized approach with a differently modeled PKI Software would
have built a CERT_SIMPLE_CHAIN kind of structure straight from the
SSL/TLS handshake exactly as it falls out of the ASN.1 parser
and use and then called a certificate chain verifier that
looks for a trust anchor matching this chain and checks the
relevant certificate attributes and signatures on the path
from the chosen trust anchor down to the end entity cert.

It may be less generic, but certainly it will be more efficient
in terms of CPU cycles.

While it might not need a lot of pointer-swapping to reorder
certificates in the chain, it will require a significant amount
of non-trivial comparisons to determine what the correct order is.

I haven't benchmarked the MS-CryptoAPI approach, but I assume that
the vast number of features that are offered come at a cost.

-Martin

---

From: Nelson B Bolyard <[email-masked]>
Date: Sat, 11 Oct 2008 14:40:54 -0700

Peter Gutmann wrote, On 2008-10-08 05:12 PDT:
>> that contains no RDName elements in the ASN.1 SEQUENCE) should have the
>> same meaning as _NO_ DName at all!  Are you sure that this notion is 
>> interoperable with other implementations?
> 
> Because TLS client certs are so rarely used it's hard to say, the best I
> can say is "I haven't run into problems so far", but that doesn't mean
> much given the very small sample size.

Since I work on TLS for Mozilla products, I can offer some perspective
on the issue of the frequency or rarity of client authentication requests.

Mozilla's products (browsers and email MUAs) have always implemented client
cert authentication.  They offer the users a choice of what to do when
a server requests client certs, and the choices include:

- Automatic selection.  The product selects a cert automatically based on
issuer name matching the server's list of CA names, (empty list of CA names
treated like a wildcard).  Basically, the first cert with matching issuer
name and appropriate KU and EKU is used. If the user has no cert from an
appropriate issuer, send no_certificate response.  This is all silent (no
user interaction) unless the user's private key requires authentication for
every use.

- manual selection.  If the user has any cert(s) whose issuer matches the
server's list of CA names, with appropriate KU and EKU, the product presents
the user with a list of such certs, and lets the user choose one.
An empty list of CA names from the server is treated like a wildcard.
Certs with no EKU extension are presumed to be valid for all EKUs.
Even if the user has only one cert that matches, he is prompted to choose.
He can also choose not to send any cert, but to send a no_certificate
response.  If the user has NO certs that match, then the user is not
presented with any list, and a no_certificate response is silently sent.

(Pre-configured per-server selection of client cert (including "none")
is in development.)

Until recently, the default for both browsers and MUAs was automatic
selection.  But this was recently changed in both types of clients,
for separate reasons.

For browsers, there arose a concern that automatic and silent client cert
authentication allows a web site to request cert authentication even when
the user has no business relationship with the site, and could be used for
user tracking, defeating anonymity of browsing.  So the default setting in
browsers was changed to manual selection to avoid silent user tracking.

This change caused a LOT of users to begin to have a very different user
experience with their browsers and MUAs.  Requests for client certs were
apparently MUCH more common and wide spread than we had previously known.
Users who had their own certs for email purposes, certs whose KU and EKU
also permitted them to be used for TLS client authentication, suddenly
found themselves being inundated with requests to select a cert for
client authentication.

For MUAs, the reason for making manual selection the default was different.
A number of popular free email server products that offer SMTP and IMAP
(or POP) over TLS have recently begun to exhibit the following behaviors:

- No TLS session cache.  A full handshake is done on every connection.
- Client certs are requested in EVERY handshake.
- The list of CA names in the server's cert request is empty, with no
  way for the server admin to change that.
- If the server receives a client certificate that it does not recognize
  as being authorized to authenticate any user, instead of ignoring the
  cert, and going on to request authentication using one of the other
  methods (e.g. user name and password), it drops the connection, usually
  without sending any alert.

MUA users who possessed their own email certs found themselves unable to
successfully connect to their mail servers because their MUAs would
automatically send their email cert to the server for client authentication,
and the server then dropped the connection.  The immediate workaround for
them was to configure their MUA for manual selection of certs for TLS
client authentication, and then choose to send a no-certificate response
when prompted.  However, this was not entirely satisfactory because they
found themselves having to manually choose to send no certificate on
EVERY connection.  For IMAPS users, this meant encountering the cert
selection dialog every time they change to view a different IMAP folder.
It also meant encountering the dialog on every message sent.

The MTA administrators are generally unaware of client authentication.
They are unaware that they have the ability to associate a certificate
with each user account, thereby allowing the cert to be used in lieu of
name and password Identification and authentication.  They have no way
to change the behavior of their MTA server product.  Therefore, they
perceive the unfortunate MUA user experience to be an MUA bug, not an
MTA server bug.

ANY of the following changes would mitigate these problems:
- servers implementing TLS session caches, and then not performing FULL
handshakes on every connection.
- servers sending non-empty lists of CA names.
- CAs issuing email certs with EKU extensions that disallow use for client
authentication.  However, this dual use is considered a feature by CAs.

In trying to persuade MTA administrators to enable TLS session caching in
their servers, we found that there is widespread misunderstanding and fear
that TLS session caching somehow allows clients to have access to accounts
on servers without having authenticated to the servers.  They seem to
believe that with a TLS server session cache enabled, any client can reuse
a previously cached TLS session without authentication.  They are fearful
to the session caches, and see the session caches as part of the problem,
not as part of the solution.

Believing that these problems will not be quickly solved, Mozilla is working
on implementing the ability for the client to remember the
association of a user-chosen cert with a server, so that it can repeat
that choice thereafter without bothering the user again.  However, this
will certainly mask the issues of servers not reusing TLS sessions.
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: [email-masked] (Peter Gutmann)
Date: Sun, 12 Oct 2008 20:05:48 +1300

>apparently MUCH more common and wide spread than we had previously known.

Actually I should provide some $0.02 on that: I agree that requests for client
certs are more common than you'd think, however many sites will request a
client cert whether they need it or not.  I ran into this problem some time
ago, since client cert requests were expected to be fairly rare I'd made them
an exception condition, which caused lots of user complaints when they started
encountering sites that always asked for client certs.  A (very brief) survey
of some admins at some of the known sites that did this yielded the equivalent
of a giant shoulder-shrug from the site admins, they didn't even know that
their servers were doing this and had no idea what to do with the certs even
if they'd been sent them.  They were also (in most cases) unaware of how to
disable the behaviour in the servers.  So I changed my code to just reply with
a no-op no-cert response and the user complaints went away.

Sorry, I'd forgotten about this bit of history trivia, but your comment just
brought it to mind.  Here's the code comment covering handling of server cert
requests:

  We don't really care what's in the cert request since the contents are
  irrelevant, in a number of cases servers have been known to send out
  superfluous cert requests without the admins even knowning that they're
  doing it, in other cases servers send out requests for every CA they know of
  (150-160 CAs) which is pretty much meaningless since they can't possibly
  trust all of those CAs to authorise access to their site.  Because of this,
  all we do here is perform a basic sanity check and remember that we may need
  to submit a cert later on.

  Although the spec says that at least one CA name entry must be present, some
  implementations send a zero-length list, so we allow this as well.  The spec
  was changed in late TLS 1.1 drafts to reflect this practice.

So that provides some more insight into why I treat cert requests the way I
do.

>[...]

Hmm, that's new, the behaviour I saw was that the servers always asked for
certs but when sent a no-cert response they continued as normal.  What you're
seeing could just be a variant of the same broken behaviour, only now the
server does a bit more checking and fails on the cert it doesn't know it's
asked for rather than just ignoring it.

>The MTA administrators are generally unaware of client authentication. They
>are unaware that they have the ability to associate a certificate with each
>user account, thereby allowing the cert to be used in lieu of name and
>password Identification and authentication.  They have no way to change the
>behavior of their MTA server product.  Therefore, they perceive the
>unfortunate MUA user experience to be an MUA bug, not an MTA server bug.

Been there, done that.  This situation is a real mess, there's such a random
jumble of broken behaviour around client certs that you can't really rely on
anything working the way it should.  The reason I mostly turned the client
cert request into a no-op was based on a quick user survey, they didn't want
to be bothered with noise from the server, and just sending the cert if there
was one present was deemed acceptable.  So my code currently does:

if( cert request from server )
  ignore CA name list but record that a cert was requested;

[...]

if( cert was requested by server )
  if( user cert present )
    send cert, etc;
  else
    send no-cert response;

This dropped the negative user responses back almost to nothing, so that's
what I've stuck with so far.

Peter.

---

From: "Ben Laurie" <[email-masked]>
Date: Sun, 12 Oct 2008 21:28:41 +0100

> "Be conservative in what you send; be liberal in what you accept."

I thought we'd given up on that as a useful generalisation since it
introduces security problems in some circumstances, for example HTTP
header stuffing. Which is not to say I am opposed to this particular
change, but that adage is an entirely insufficient justification.
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: "Ben Laurie" <[email-masked]>
Date: Sun, 12 Oct 2008 21:34:41 +0100

> handshakes on every connection.

FWIW, Apache-SSL does its own caching of client certs because (at
least at the time) OpenSSL's cache didn't store them. I'm not sure if
this has been fixed.
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: "Jeffrey A. Williams" <[email-masked]>
Date: Sat, 11 Oct 2008 17:58:30 -0700

Ben and all,

  I fullu agree with you Ben.  I for one am often willing to send
what I feel is appropriate wheather or not others believe so
or not, as long as it is in context and in keeping with the
theme or topic at hand.

> change, but that adage is an entirely insufficient justification.

Regards,

Spokesman for INEGroup LLA. - (Over 281k members/stakeholders strong!)
"Obedience of the law is the greatest freedom" -
   Abraham Lincoln

"Credit should go with the performance of duty and not with what is
very often the accident of glory" - Theodore Roosevelt

"If the probability be called P; the injury, L; and the burden, B;
liability depends upon whether B is less than L multiplied by
P: i.e., whether B is less than PL."
United States v. Carroll Towing  (159 F.2d 169 [2d Cir. 1947]
===============================================================
Updated 1/26/04
CSO/DIR. Internet Network Eng. SR. Eng. Network data security IDNS.
div. of Information Network Eng.  INEG. INC.
ABA member in good standing member ID 01257402 E-Mail
[email-masked]
My Phone: 214-244-4827

---

From: Martin Rex <[email-masked]>
Date: Mon, 13 Oct 2008 21:53:48 +0200 (MEST)

Nelson B Bolyard wrote:
> [interesting description snipped]
> 

One of the very few features that I like about MSIE is that is has been
memorizing the users decision on a per-server basis for many years already.

With the help of this decision memorizing, MSIE also implements another
useful feature: it closes the SSL connection while it is prompting the
user for a decision.  Leaving the connection open and stalling the
server in the SSL handshake while showing the user a Popup UI for
an indeterminate amount of time is de-facto running a DoS on the server.

There were, however, also two real problems with this approach in MSIE
(I haven't check the current situation):
 1) on first connect to a server, when a CertificateRequest handshake
    message was received, MSIE tried to complete the SSL handshake
    by sending a "No Certificate" Alert or empty ClientCertificate
    handshake message.

    the OK-part:
      When the SSL server terminated the handshake with a fatal error
      after not receiving a certificate, MSIE closed the connection
      and prompted the user with a client certificate selection
      Message box (or tries automatic selection and
      suppress empty selection dialog box in MSIE >5.0).
    the NOT OK-part:
      When the SSL handshake completed successfully without client cert,
      then MSIE would never tell the user that the server asked for a
      client certificate and not offer the user to use one.

 2) if a server for which MSIE memorized to access without client cert
      suddenly would change his behaviour and fail the SSL-handshake
      when receiving the "no client Certificat" alert or empty ClientCert
      handshake message, MSIE would show a popup reporting
      "Unkown SSL error ..." instead of prompting the user to select
      a client certificate.

The only method to request a client certificate from MSIE after
a server lets him pass the SSL handshake without client cert is
to do a renegotiate and ask for the client certificate there.
This will not result in the "Unknown SSL error ...".

Looking at the issue of "what can or should TLS peers memorize", there
seems to be a shortcoming in how IIS caches sessions where it asked
for a client cert (via renegotiate) but didn't receive a client certificate.
Although resuming that session works, IIS will force the handshake through
a renegotiate asking for a client cert on each and every resume (and
by doing the renegotiate, it will issue a new SSL session ID -- which
is going to fill up the session cache of the server and client
significantly...

-Martin

---

From: Nelson B Bolyard <[email-masked]>
Date: Mon, 13 Oct 2008 17:56:20 -0700

> asked for rather than just ignoring it.

I think we've been seeing the behaviors of the same product.
As you say, if you send a no-certificate response, the server continues
in the "normal" (no client auth) fashion.  But if you DO provide a client
cert, then the server drops the connection.
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 14 Oct 2008 17:36:08 +1300

Nelson B Bolyard <[email-masked]> writes:

>I think we've been seeing the behaviors of the same product. As you say, if
>you send a no-certificate response, the server continues in the "normal" (no
>client auth) fashion.  But if you DO provide a client cert, then the server
>drops the connection.

I've had a quick look through the logs and this problem has been around for a
long time, the first reports I can find are from 2002-2003 and cover not just
MTAs but also things like SSL-enabled FTP servers.  It also affects quite a
shopping-list of services running a variety of implementations, including ones
with a user base in the 10-million-plus region.  This is why I switched to the
"don't-bother-the-user" default behaviour, it's easier than convincing (say) a
large multinational to change the behaviour of their servers.

(I'll send a few names in private mail to see if they match what you're
seeing).

Peter.

---

From: Nelson B Bolyard <[email-masked]>
Date: Wed, 15 Oct 2008 18:40:25 -0700

> the OpenSSL developers don't consider their behaviour as a bug (see

I confirm the claim for Firefox and any other NSS-based applications.

NSS holds on to the first cert presented, and throws the rest into a
bucket, into which it has also thrown all locally trusted (i.e., root)
CA certs, and into which the application may have placed CA certs from
other cert chains that were successfully validated in the recent past.
Then beginning with the first cert that it received from the TLS peer,
NSS attempts to reconstruct a cert chain from the certs in that bucket,
one that leads to a locally trusted CA cert, and if it succeeds, it tests
the validity of that chain.  (This description is somewhat oversimplified.)
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls