Re: How does X.509 really work?

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Threaded View
[My upstream news service refused to accept such a widely crossposted
article.  I've trimmed the crossposting.]

Quoted text here. Click to load it

Whoever wrote that should be taken out and shot.

Quoted text here. Click to load it

This betrays a fundamental misunderstanding.  Public-key encryption and
digital signatures are not particularly related.

In the early years of public-key cryptography, it was believed that
digital signature schemes and public-key encryption schemes were related
-- that a signature scheme was basically an encryption scheme `run
backwards'.  In 1984, Taher ElGamal described both a digital signature
scheme that wasn't an encryption scheme run backwards, and an encryption
scheme that couldn't be run backwards to make digital signatures.  (This
wasn't the main point of his paper, admittedly.)

Nowadays, we understand that the two are very different.  They offer
very different security properties, and have different theoretical
foundations.  (In particular, digital signature scheme require only
one-way functions for existence, whereas public-key encryption schemes
require trapdoor one-way functions.)  Pioneering work, in particular
Diffie and Hellman's 1977 `New Directions' paper, confused the two --
they assumed that the notion of trapdoor one-way permutations, which are
sufficient but not (as ElGamal showed) necessary for constructing /both/
signatures and encryption, was fundamental.  The fact that Rivest,
Shamir and Adleman constructed a trapdoor one-way permutation shortly
afterwards reinforced this confusion.

I have encountered many people whose confusion on these subjects led
them to make serious mistakes.  Don't be one of them.

Quoted text here. Click to load it

The above description is unhelpful because it's too specific.  All of
the mess with message digests is unnecessary to a high-level

The important concept is that of a `digital signature scheme with
appendix'.  (This is the usual kind, and most people won't pedantically
provide the `... with appendix' part.)  There are three operations:

  * Key generation.  One feeds in some parameters, and obtains a pair of
    keys called the `public key' and the `private key'.

  * Signing.  One feeds in a message, and a private key, and obtains a

  * Verification.  One feeds in a message, a public key, and a
    signature, and obtains a `yes' or `no' answer.

The properties we want are:

  * Correctness: if I sign a message with a private key, and verify that
    message with the corresponding public key and the signature, I
    should get a `yes' answer.

  * Security: it should be hard for an adversary without the private key
    to construct a message and signature for which the verification
    operation says `yes', even if he is allowed to obtain correct
    signatures for many messages of his choosing.

The text quoted above describes a particular kind of signature scheme,
which happens to use a message digest function as part of its signing
and verification operations.

Quoted text here. Click to load it

X.509 is a bad place to start.  For the horrible truth, see Peter
Gutmann's X.509 Style Guide.

Quoted text here. Click to load it

Let's suppose Alice wants to obtain a certificate.

She constructs a `certificate request', which contains various pieces of
information pretty much as she wants them to appear in the actual
certificate, including her name and public key -- all expressed in a
completely demented encoding.  She signs this request using her private
key and sends the whole lot to the CA along with a pile of cash.

We're now expected to believe that the CA puts a lot of effort into
making sure that the key really belongs to Alice and not to someone else
who is merely pretending to be Alice -- rather than, say, simply
assuming that she's honest and trousering the cash on the grounds that
dishonest people's money works just as well in practice.  Regardless,
our Alice is indeed honest, and so the CA will construct and sign the
certificate and hand it and the signature to Alice.  She now has a dent
in her bank account and a small string of bits which is an X.509

(This misses out all the amusement with registration authorities and

Quoted text here. Click to load it

Basically right.  If Alice wants to sign a message, she uses her private
key to sign it, and sends on the message, her signature, and her shiny
new certificate.  She may also send along the CA's own certificate.

However, there is no encryption happening here.

Quoted text here. Click to load it

Suppose the recipient, Bob, has Alice's certificate, the CA's
certificate her message, and her signature.  He verifies the CA's
signature on Alice's certificate, and extracts Alice's public key; he
then verifies Alice's signature on her message using this public key.
If all is well:

  * he knows that the message was signed by the private key
    corresponding to the one he dug out of the certificate;

  * the certificate says that the public key is the counterpart to a
    secret signing key held by Alice;

  * and the certificate is in turn signed by a CA.

If he trusts the CA to tell him things like `this is the public key
corresponding to Alice's private key' then he'll be happy that the
message came from Alice.  Quite why he trusts the CA to tell him such
things is, frankly, something of a mystery to me: after all, there's not
much he can do about it if the CA turns out to be dishonest.

Quoted text here. Click to load it

Certificates form chains.  Each link has the form:

        (Y says that Kfoo is the public key of X) signed by Kbar

Stack this together with

        (Z says that Kbar is the public key of Y) signed by Kquux

and similar, and you can get from knowing that Z's key is Kquux to
deducing that Kfoo is the public key of X -- if you trust Z and Y when
they say such things.

Somewhere the chain has to end (or form a loop).  In fact, for reasons
which currently escape me, X.509 certificate chains actually loop at the
end -- the top-level certificate is `self-signed'.  I've no idea what
good this is supposed to do.

Typically, Alice will send not only her own certificate, but her CA's
certificate and so on, all the way up to a self-signed `root' key at the
top.  Typically, Bob already has most of this stuff if he trusts the CA
in question -- and if he doesn't, he doesn't have any particularly good
reason to believe `Alice' when she says that the top-level certificate
belongs to a reputable CA.  So sending it all was a waste of time and
bandwidth -- but it gets sent anyway.

Also, none of this explains why Bob thinks that Alice is someone he's
interested in talking to.  Presumably he's been given Alice's name by
someone else -- who mysteriously neglected to give him Alice's public
key at the same time, leaving that job to the CA who otherwise wouldn't
have any even-slightly-plausible reason for asking Alice for their hard-
earned fees.

Quoted text here. Click to load it

Again, there's no decryption going on here.

Quoted text here. Click to load it

Simple answer: Bob's certificate contains Bob's public key.  Alice
doesn't know Bob's private key (we hope!), and therefore (if the
cryptography works!) can't sign messages using Bob's private key.  So if
Alice sends Charles Bob's certificate, and a message, she doesn't have
any way of making a signature which Charles can verify correctly using
Bob's public key -- which is the one on the certificate.  In particular:

  * she can't sign with Bob's private key because Bob won't let her, and
    the cryptography is too good; and

  * she can't mess with Bob's certificate to substitute her own public
    key because the certificate is signed by the CA, and she can't sign
    with the CA's private key either.

Her best bets are to break into Bob's computer (he's probably not up-to-
date with his patches) or to start up a new dishonest CA of her own.  In
practice, most people just click the `Yeah, whatever' buttons on all the
`I've never heard of this certificate' warning boxes anyway.

-- [mdw]

Re: How does X.509 really work?

Mark Wooding wrote:
Quoted text here. Click to load it

Good for it.  I wish more rejected anything over 3 crossposts.

 [mail]: Chuck F (cbfalconer at maineline dot net)
 [page]: <
            Try the download section.

Site Timeline