Subject: POP section for next Roadmap draft

From: Al Arsenault <[email-masked]>
Date: Wed, 27 Jan 1999 11:34:51 -0500

Folks,

        Sean and I are working on the next draft of the PKIX Roadmap.  One of
the things that has to be done is filling in the Proof of Possession section
(section 5.2 in draft -00).  Attached is a first cut at text for that section. 
Any strong comments one way or the other on this?

POP 
Proof of Possession, or POP, means that the CA is adequately convinced that the
entity requesting a certificate containing a public key Y has access to the
private key X corresponding to that public key.  

POP is important because it provides an appropriate level of assurance in the
correct operation of the PKI as a whole.  There are those who dismiss POP as
unimportant because the most direct threat it counters is the “self-inflicted
denial of service”; that is, an entity voluntarily gets a certificate that
cannot be used to sign or encrypt/decrypt information.  However, as the
following two examples demonstrate, the true threat countered by POP is less
direct, but more important:
POP for signing keys:  it is important to provide POP for keys used to sign
material, in order to provide authentication and possibly non-repudiation of
transactions.  For example, suppose Alice legitimately has private key X and
its corresponding public key Y.  Alice has a certificate from Charlie, a CA,
containing Y.  Alice uses X to sign a transaction T.  Without POP, Mal could
also get a certificate from Charlie containing the same public key, Y.  Now,
there are two possible threats:  Mal could claim to have been the real signer
of T; or Alice can falsely deny signing T, claiming that it was instead Mal. 
Since no one can reliably prove that Mal did or did not ever possess X, neither
of these claims can be refuted, and thus the service provided by and the
confidence in the PKI has been defeated.  (Of course, if Mal really did possess
X, Alice’s private key, then no POP mechanism in the world will help, but that
is a different problem.)

POP for key management keys:  Similarly, POP for key management keys (that is,
keys used for either key agreement or key exchange) can help to prevent
undermining confidence in the PKI.  Suppose that Al is a new instructor in the
Computer Science Department of a local University.  Al has created a draft
final exam for the Introduction to Networking course he is teaching.  He wants
to send a copy of the draft final to Dorothy, the Department Head, for her
review prior to giving the exam.  This exam will of course be encrypted, as
several students have access to the computer system.  However, a quick search
of the certificate repository turns up the fact that several students have
certificates containing the same public key management key as Dorothy.  At this
point, if no POP has been done by the CA, Al has no way of knowing whether all
of the students have simply created these certificates without knowing the
corresponding private key (and thus it is safe to send the encrypted exam to
Dorothy), or whether the students have somehow acquired Dorothy’s private key
(and thus it is certainly not safe to send the exam).  Thus, the service to be
provided by the PKI - allowing users to communicate with one another, with
confidence in who can read their communications - has been totally defeated. If
the CA is providing POP, then either no students will have such certificates,
or Al can know with certainty that the students do indeed know Dorothy’s
private key, and act accordingly.

CMP requires that POP be provided for all keys, either through on-line or
out-of-band means.  There are any number of ways to provide POP, and the choice
of which to use is a local matter.  Additionally, a certificate requester can
provide POP to either a CA or to an RA, if the RA can adequately assure the CA
that POP has been performed.  Some of the acceptable ways to provide POP
include:

        POP by Out-of-band means:  
For keys generated by the CA or an RA (e.g., on a token such as a smart card or
PCMCIA card), possession of the token can provide adequate proof of possession
of the private key.

For user-generated keys, another approach can be used in environments where
“key recovery” requirements force the requester to provide a copy of the
private key to the CA or an RA.  In this case, the CA will not issue the
requested certificate until such time as the requester has provided the private
key.  This approach is in general not recommended, as it is extremely risky
(e.g., the system designers need to figure out a way to protect the private
keys from compromise while they are being sent to the CA/RA/other authority,
and how to protect them there), but it can be used. 

        POP by On-line means:
For signature keys that are generated by an end-entity, the requester of a
certificate can be required to sign some piece of data (typically, the
certificate request itself) using the private key.  The CA will then use the
requested public key to verify the signature.  If the signature verification
works, the CA can safely conclude that the requester had access to the private
key.  If the signature verification process fails, the CA can conclude that the
requester did not have access to the correct private key, and reject the
request.

For key management keys that are generated by the requester, the CA can send
use the requested public key, along with the CA’s own private key, to encrypt
some piece of data, and send it to the requester to be decrypted.  For example,
the CA can generate some random challenge, and require some action to be taken
after decryption (e.g., “decrypt this encrypted random number and send it back
to me”).  If the requester does not take the requested action, the CA concludes
that the requester did not possess the private key, and the certificate is not
issued.  

Another method of providing POP for key management keys is for the CA to
generate the requested certificate, and then send it to the requester in
encrypted form.  If the requester does not have access to the appropriate
private key, the requester cannot decrypt the certificate, and thus cannot use
it. After some period of time in which the certificate is not used, the CA will
revoke the certificate.  (This only works if the certificate is not made
available to any untrusted entities until after the requester has successfully
decrypted it.

Thanks,

                        Al Arsenault

-- these are my opinions only. They do not necessarily reflect the 
opinions of my employer, or of any other organization with which I have a 
relationship.

---

From: Denis Pinkas <[email-masked]>
Date: Thu, 28 Jan 1999 16:46:22 +0100

Al,

This is nice to send that section, otherwise I would not have taken a look at
the road map :-(

>  Folks,
>
> Sean and I are working on the next draft of the PKIX Roadmap.  One of the
> things that has to be done is filling in the Proof of Possession section
> (section 5.2 in draft -00).  Attached is a first cut at text for that
> section.  Any strong comments one way or the other on this?
>

Oh ! yes. I have strong opinions on this topic.

>      POP
>
> Proof of Possession, or POP, means that the CA is adequately convinced that
> the entity requesting a certificate containing a public key Y has access to
> the private key X corresponding to that public key.
>
> POP is important because it provides an appropriate level of assurance in
> the correct operation of the PKI as a whole.  There are those who dismiss
> POP as unimportant because the most direct threat it counters is the
> “self-inflicted denial of service”; that is, an entity voluntarily gets a
> certificate that cannot be used to sign or encrypt/decrypt information.

Up to here the text is fine.

There are three types of keys, each one being indicated with a different key
usage. Whether POP or is not required depends on the key usage. The three main
key usages for leaf certificates are: non repudiation, data encryption and ...
all others in particular authentication.

The case for signing key below does not match with this separation and
therefor is not adequate. You have to separate authentication from non
repudiation. You also have to consider "old" mechanisms (which contain
"errors") which mandate POP and "new" (error free) mechnisms which do not
mandate POP.

Because some people wanted to use PKIX in any context they wanted to mandate
POP. As soon as you use it with "new" mechanism POP is no more always needed
(see below).

The example you provide below is an example with an "old" mechanism. The bad
side is that many people could infer from the text that POP is always needed
whereas this is not true.

> However, as the following two examples demonstrate, the true threat
> countered by POP is less direct, but more important:
>
>      POP for signing keys:  it is important to provide POP for keys used to
>      sign material, in order to provide authentication and possibly
>      non-repudiation of transactions.  For example, suppose Alice
>      legitimately has private key X and its corresponding public key Y.
>      Alice has a certificate from Charlie, a CA, containing Y.  Alice uses X
>      to sign a transaction T.  Without POP, Mal could also get a certificate
>      from Charlie containing the same public key, Y.  Now, there are two
>      possible threats:  Mal could claim to have been the real signer of T;
>      or Alice can falsely deny signing T, claiming that it was instead Mal.
>      Since no one can reliably prove that Mal did or did not ever possess X,
>      neither of these claims can be refuted, and thus the service provided
>      by and the confidence in the PKI has been defeated.  (Of course, if Mal
>      really did possess X, Alice’s private key, then no POP mechanism in the
>      world will help, but that is a different problem.)
>

The simple solution to the problem is to include an identifier of the
certificate in the signed data. In this way the substitution is no more
possible. What you have provided is an example of an "old" mechanism whereas
my example would be refered as a "new" mechanism.

As far as authentication is concerned some "old" mechanisms cannot be changed
to include the certificate identifier. For non repudiation it is mandatory to
include it, not only because of the substitution with a certificate from
someone else but because the same signer may use different certificates all
containing the same public key but including different security attributes (in
an extension).

>
>      POP for key management keys:  Similarly, POP for key management keys
>      (that is, keys used for either key agreement or key exchange) can help
>      to prevent undermining confidence in the PKI.  Suppose that Al is a new
>      instructor in the Computer Science Department of a local University.
>      Al has created a draft final exam for the Introduction to Networking
>      course he is teaching.  He wants to send a copy of the draft final to
>      Dorothy, the Department Head, for her review prior to giving the exam.
>      This exam will of course be encrypted, as several students have access
>      to the computer system.  However, a quick search of the certificate
>      repository turns up the fact that several students have certificates
>      containing the same public key management key as Dorothy.  At this
>      point, if no POP has been done by the CA, Al has no way of knowing
>      whether all of the students have simply created these certificates
>      without knowing the corresponding private key (and thus it is safe to
>      send the encrypted exam to Dorothy), or whether the students have
>      somehow acquired Dorothy’s private key (and thus it is certainly not
>      safe to send the exam).  Thus, the service to be provided by the PKI -
>      allowing users to communicate with one another, with confidence in who
>      can read their communications - has been totally defeated. If the CA is
>      providing POP, then either no students will have such certificates, or
>      Al can know with certainty that the students do indeed know Dorothy’s

I am not convinced by this example. Alice Dorothy will be able to decrypt the
document. If the key was indeed compromised, Dorothy would have reported it
(and any way POP would not have helped, since all others were indeed knowing
the key ansd would have get their certificate by exercising POP !).

> out-of-band means.

This may be necessary in some cases, however it is not only always necessary.
A conservative measure is to mandate it but I do not think this is
appropriate. For authentication if the mechanism is designed very fast and no
protection is taken, then POP is necessary. This is true for both signing keys
and (I guess) encryption keys. When a message is encrypted so that only the
intended recipient may decipher it, POP is not needed.

For non repudiation, since some protection is always needed at the protocol
level, POP is NOT needed.

You may have (re-)opened a new long thread on that topic. Anyway thanks for
trying to clarify this issue.

If I had the time I would have propose a new text. However, I thought it was
better to provide explanations first at that stage.
You may "canibalize" my rational and re-use it in a new text if you wish.

Denis

> There are any number of ways to provide POP, and the choice of which to use
> is a local matter.  Additionally, a certificate requester can provide POP to
> either a CA or to an RA, if the RA can adequately assure the CA that POP has
> been performed.  Some of the acceptable ways to provide POP include:
>
>      For keys generated by the CA or an RA (e.g., on a token such as a smart
>      card or PCMCIA card), possession of the token can provide adequate
>      proof of possession of the private key.
>
>      For user-generated keys, another approach can be used in environments
>      where “key recovery” requirements force the requester to provide a copy
>      of the private key to the CA or an RA.  In this case, the CA will not
>      issue the requested certificate until such time as the requester has
>      provided the private key.  This approach is in general not recommended,
>      as it is extremely risky (e.g., the system designers need to figure out
>      a way to protect the private keys from compromise while they are being
>      sent to the CA/RA/other authority, and how to protect them there), but
>      it can be used.
>
>
> POP by On-line means:
>
>      For signature keys that are generated by an end-entity, the requester
>      of a certificate can be required to sign some piece of data (typically,
>      the certificate request itself) using the private key.  The CA will
>      then use the requested public key to verify the signature.  If the
>      signature verification works, the CA can safely conclude that the
>      requester had access to the private key.  If the signature verification
>      process fails, the CA can conclude that the requester did not have
>      access to the correct private key, and reject the request.
>
>      For key management keys that are generated by the requester, the CA can
>      send use the requested public key, along with the CA’s own private key,
>      to encrypt some piece of data, and send it to the requester to be
>      decrypted.  For example, the CA can generate some random challenge, and
>      require some action to be taken after decryption (e.g., “decrypt this
>      encrypted random number and send it back to me”).  If the requester
>      does not take the requested action, the CA concludes that the requester
>      did not possess the private key, and the certificate is not issued.
>
>      Another method of providing POP for key management keys is for the CA
>      to generate the requested certificate, and then send it to the
>      requester in encrypted form.  If the requester does not have access to
>      the appropriate private key, the requester cannot decrypt the
>      certificate, and thus cannot use it. After some period of time in which
>      the certificate is not used, the CA will revoke the certificate.  (This
>      only works if the certificate is not made available to any untrusted
>      entities until after the requester has successfully decrypted it.
>
>
>
>
>
>
> Thanks,
>
> Al Arsenault
>