Subject: Re: POP section for next Roadmap draft

From: Juergen Walter <[email-masked]>
Date: Mon, 01 Feb 1999 17:25:43 +0100

Denis,

I agree essentially with Al´s position. I would like to add some
comments.

For non-repudiation key usage the CA must ensure that the public key is
UNIQUE. Even if the signed data includes a cert identifier the threat
described by Al remains unsolved. Substitution of certs is a minor
problem (the cert identifier encapsulation has solved the problem as you
wrote, i. e. "new" mechanism). The major problem is key uniqueness. Even
the "new" mechanism needs POP.

If CAs do not POP prior to certification then they probably allow that
two end entities share the same signature key. This may be approriate in
certain circumstances, but this is definitely not appropriate in
non-repudiation framework. The other certificate applications may be
restricted according to their usage (see Al´s key management example).

I would like to use Al´s signature key example where Alice and Mal are
involved. If I have understood correctly, a CA which does not POP may
issue two certificates with different subject identifiers (e. g.
distinguished names) and one identical public key. So, Alice may include
Mal´s identifier and sign the transaction. In the following the dispute
arises when Mal repudiated the transaction. Alice then repudiates the
possession of private key as well. Who is responsible for the
transaction? Mal?! What is about the case when there exist more than one
Mal (i. e. more than two certificates with identical public key and
different identities)?! What do you answer provided that Mal says,
sorry, it had been a joke? Is your agreement with Mal legally approved
for such cases?

Furthermore, if a person signs a document with its private key in a
non-repudiation framework, then it has accepted the information content.
When a CA signs the PRETENDED subject public key, then it has probably
accepted false information. One basic function of a CA is key
registration. But, if CAs does not verify POP, then the key is not
well-registered. So, the CA does not warrant for information contained
in the issued certificate. Why a relying party should trust such CAs? A
new certificate extension "CA has done POP" is a very bad idea (see next
para).

I think that the mechanism called "new" without POP is essentially an
attribute certification. The PRETENDED subject public key is then one of
the certified attributes. The attribute certificate binds the PRETENDED
subject public key to the end entity´s distinguished name and other
attributes if appropriate. May be, I have overseen somewhat, but your
solution is essentially a X.509 attribute certificate.

Summarizing, POP is a key registration matter. At least the
non-repudiation framework REQUIRES POP. POP SHOULD be done prior to
certification (personally, I prefer MUST). Alternatively, a CA MAY
ensure the uniqueness of the registered public keys. If a CA receives a
public key that has not been certified yet for another entity, then it
MAY drop POP (for the moment?). Those CAs that do this MUST reject a
registration request, that contains a public key always certified for a
different entity. When this registration request includes a POP and its
verification was succesful, the corresponding certificate MUST be
revoked immediately.

When entities use signature keys before they are certified by a CA or
other inappropriate key usage is another outstanding (?) key management
problem. Especially, in those cases where key pairs are generated by end
entities themselves.

Key sharing is not covered by the comments above. One may replace
entities by groups of entities where separation within the same group is
not desirable or is provided by additional certs, respectively. POP must
then be done by ALL entities who share a certain key.

Juergen

Denis Pinkas wrote:
> 
> 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
> >      private key, and act accordingly.
> >
> 
> 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 !).
> 
> > CMP requires that POP be provided for all keys, either through on-line or
> > 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:
> >
> > 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: Fri, 05 Feb 1999 14:33:47 +0100

Juergen,

Sorry for the delay. I have had difficulties to find some time available this week.

> UNIQUE.

I do not believe so. Even if this would be the case, all the CAs of the world would
not be bale to interconnect to verify this.

> Even if the signed data includes a cert identifier the threat
> described by Al remains unsolved.

You would have to be more precise.

> Substitution of certs is a minor
> two end entities share the same signature key.

If they really share the same key, then POP can be made by each entity and will not
prevent the scenario to happen. If they don't then only one (or no one) has the
corresponding private key.

> This may be approriate in

If someone manages to get a certificate containing a public key for which someone
else has the corresponding private key, then that entity has to be aware of problems
that may occur. It is up to the entity to assume the possible consequences, but the
CA does not have to be responsible.

> well-registered.

No, the CA can testify that this user wanted that public key in his certificate.

> So, the CA does not warrant for information contained

It can be used in the case where attributes are in the certificate, but this is not
the essential point. The signer has always to include a reference of its certificate
and to protect it under its signature.

> non-repudiation framework REQUIRES POP.

No. POP is made at the protocol level (by signing the certificate identifier),
rather than the registration phase.

> POP SHOULD be done prior to
> ensure the uniqueness of the registered public keys.

There is no reason for this argument.

> If a CA receives a
> MAY drop POP (for the moment?).

????

> Those CAs that do this MUST reject a

I do not follow you.

> then be done by ALL entities who share a certain key.

I do not share your various conclusions.

Regards,

Denis

---

From: Juergen Walter <[email-masked]>
Date: Tue, 09 Feb 1999 19:08:33 +0100

Denis,

thanks for the response. I stick on the issue why POP-CAs ensures key
uniqueness. The other issues remains open for the moment, I apologize.

To avoid misunderstandings POP by some means is ensured when the CA has
verified the binding between the private key and the public key, that
the entity wants to be certified. The concrete means are surely policy
matters and therefore outside the scope of PKIX.

More comments follow in line.

Denis Pinkas wrote:
> I do not believe so.

I have to be more precise if I recommend public key uniqueness. More
precicely, I think that the risk of public key clashes should be
sufficiently small. This residual risk is again a policy matter and
outside the scope of PKIX work.
 
> Even if this would be the case, all the CAs of the world would

This is not necessary. But CAs can ensure public key uniqueness
implicitly. If they do POP then they ensure that no entity who does not
own the private key becomes certified (i. e. the CA issues a certificate
that contains the corresponding public key). CAs may recommend the usage
of a suitable key generator. Let me assume that this key generator works
correctly. Then the event of identical keys owned by two entities 
unlikely happens. An element of risk remains but this is certainly
small. Surely it is close to the risk of a brute force attack of the
signing key under the assumptions above. All public keys that are
distributed by CAs are (almost) unique. The distribution mechanism of
public keys is that a CA signs the entity´s certificate. All other
mechanisms like directory, repository or whatever are operational
issues.

If CAs do not POP by any means then this fact is no longer true. Then
there probably exist certified public keys that are not generated by a
suitable key generator, i. e. either the corresponding private key is
unknown or it is known to another entity. "knowledge" should be
interpreted as ability to apply the private key.

The first case leads to public key reservation that is really stupid.
(Is it analogously to the domain reservation?) 

In the second case the phenomena of public key hijacking appears, i. e.
an entity may retrieve a public key and manage the certification by a
non-POP-CA. It is not necessary that this non-POP-CA coincides with the
CA that issued the certificate for the hijacked public key.

Is public key hijacking possible when we consider non-POP-CAs? What is
about the public key distribution function of a non-POP-CA? It seems to
me there may be a lot of waste in its repository.

The possible consequences remain for further discussion if I find some
time.

[snip]

Juergen

---

From: Juergen Walter <[email-masked]>
Date: Wed, 10 Feb 1999 19:01:10 +0100

Denis,

[key uniqueness section deleted]

> You would have to be more precise.

Sorry, the precise scenario was below. 

> prevent the scenario to happen. 

The event that key sharing appears then unlikely happens, provided there
are some security measures (e. g. approved key generators, suitable key
length) in force. Nevertheless, some CAs may use POP to detect this
case.

>If they don't then only one (or no one) has the

"only one" is key uniqueness and therefore no problem at all. "no one"
does not appear, if the CA does POP. Why should a public key be certfied
by a CA, when nobody knows the corresponding private key? If a CA does,
then it allows key reservation. And in addition, there are misleading
certificates containing these "reservated keys".

> CA does not have to be responsible.

The consequences are not restricted to Mal. The relying party has the
problem that Alice is able to deny her signature.  She retrieves Mal´s
certificate and signs transaction T including Mal´s certificate. Nobody
except Alice knows that Alice has signed T. Even if transaction T
includes a signed challenge i. e. POP is done at signature generation
time the signature token includes no evidence who signed T.

> No, the CA can testify that this user wanted that public key in his certificate.

I have serious concerns about the terminology "certificate". X.509
definition does not say "pretended" public key. I think that the PKIX-1
section about POP is misleading according to the reason why CAs must do
POP.

> and to protect it under its signature.

I think that CAs doing no POP should issue attribute certificates
instead of public key certificates. Attribute certificates testify the
binding between entity´s attributes ,and either distinguished name or
certificate identifier. They are signed by a (attribute) CA. One
attribute may be entity´s pretended public key. Personally, I think that
has no worth but it may be reasonable for those CAs that do not want to
verify POP.

> rather than the registration phase.

I beg to differ. POP is a versatile matter e. g. protocol (as you
mentioned), key management, audit trail.

> There is no reason for this argument.

The reason is the following. If two entities share the same key then
they are able to generate identical signature tokens.

> > verification was succesful, the corresponding certificate MUST be

You are right. This was not correct, but we differ probably in the
reasoning. I think POP should be done prior to certification.

[snip]

Juergen