Subject: Comments on draft-ietf-pkix-tac-00.txt

From: "Denis Pinkas"<[email-masked]>
Date: Thu, 26 Jun 2008 09:55:32 +0200

This draft is about certificates containing pseudonyms and how to make them traceable 
to a subset of the registration information (not “the identity”), if both the RA and the CA cooperate. 

The scheme that is described is lacking replay protection in several exchanges. 
Interruptions in the protocol are not addressed either.
The main properties can be retained without the threshold signature scheme (section 5). 

Hereafter is a sketch of a simplified (and slightly different) protocol taking into consideration 
replay protection. It involves less key management than the proposed scheme. 

The RA maintains a database which contains: 

- the registration information of every entity, 
- a UserKey chosen by the RA which consists of a date and time concatenated with a random number. 

This information is kept by the RA during x hours. 
If the CA is not contacted within x hours by the CA, that information is deleted. 

The RA sends the UserKey to the CA (through a secure channel). 
The CA verifies the timeliness of the UserKey and keeps it in a cache for x hours. 

The entity is informed that the information will be kept for x hours. 
If the CA cannot be immediately contacted, the entity is informed that a delay may exist 
before the UserKey can be used against the CA. 

The CA receives from the entity:
 
- the UserKey chosen by the RA, 
- the OID of the certificate policy under which the certificate should be issued, 
- a proposed pseudonym, 
- a public key and the associated algorithm. 

If the UserKey is not in the cache of the CA, the request is rejected. 
If the pseudonym is not unique, the request is rejected and the CA proposes a different pseudonym. 
In that case, the entity makes a second request with the same UserKey. Otherwise the CA contacts the RA 
to make sure that the registration information kept by the RA will not be deleted, generates the PKC 
and sends it back to the entity. 

In that case, the CA maintains a database which contains: 

- the UserKey chosen by the RA, 
- the PKC issued to the entity. 

To trace the PKC back to the entity, a party contacts the CA and demonstrates that it has some arguments 
to get a subset of the registration information kept by the CA. 

Then, the CA generates a nonce which consists of a date and time concatenated with a random number 
and sends it together with the UserKey to the RA (through a secure channel).  

The RA verifies the timeliness of the nonce and, if correct, uses the UserKey to find the appropriate information 
in the data base. It transfers a subset of the registration information (e.g. name, first name, postal address) 
in another cache together with the nonce. 

The CA sends back the nonce to the party that may be used within y hours. If the RA cannot be contacted, 
the party is informed that a delay may exist before the nonce can be used against the CA. 

The party presents the nonce to the RA and, if present in the cache, receives back a subset of the registration information. 

All nonces kept in the cache older than y hours are deleted by the RA together with the registration information subset. 

Now the real question is: how can a relying party know that a separation of duties between the RA and the CA exits ? 
It would seem that an extension to the certificate might be useful to advertise it. 

Finally, about the vocabulary: 

1) the use of the names Anonymous Issuer (AI) and Blind Issuer (BI) is not necessary and is confusing. 

2) “Anonymous certificate” is confusing. An alternative wording for the title of this document would be:
 “Traceable certificates containing a pseudonym”. 

Denis

---

From: Stephen Kent <[email-masked]>
Date: Thu, 26 Jun 2008 22:52:41 -0400

At 9:55 AM +0200 6/26/08, Denis Pinkas wrote:
>This draft is about certificates containing 
>pseudonyms and how to make them traceable
>to a subset of the registration information (not 
>“the identity”), if both the RA and the CA 
>cooperate.
>

Most of the messages exchanges are to be 
performed over TLS, as recommended throughout the 
I-D, and TLS protects against intra-session 
replays.  Looking at figure 1, steps is not 
affected by this suggestion; in  step 2 the user 
could make use of a time stamp embedded in the 
token to detect a replay, but we don't  require 
an on-the-wire exchange here, if the exchange is 
not in person, then use of TLS would prevent a 
session level replay, so I see no problem here.
In step 3 the CA could use a time stamp in the 
Token to reject a replayed request, but in step 5 
the RA could detect the reuse of the Token and 
reject it, so the time stamp is only speeding up 
the detection of the replay here. (I guess we 
need to be explicit about this re-use check in 
the description  of step 5.) Nonetheless, a time 
stamp in the Token might prove useful. There is 
no need for the time stamp in steps 5+6, as they 
are conducted over a TLS (or equivalent) 
connection, and the BI will reject a reused 
token, as noted above. I step 7, the user is 
getting a cert in response to his request, via a 
TLS channel, and thus should be immune to session 
level replay as well.

So the bottom line is that adding a time stamp to 
the UserKey does offer some advantages in 
speeding up detection of session-level replay 
attacks in one place. It's a simple change to 
make and probably worthwhile.

>Interruptions in the protocol are not addressed either.

not sure what you mean here.

>threshold signature scheme (section 5).

not really, see comments below.

>Hereafter is a sketch of a simplified (and 
>slightly different) protocol taking into 
>consideration
>- a UserKey chosen by the RA which consists of a 
>date and time concatenated with a random number.

OK, a simple change, probably worthwhile. We'll 
put it in te next rev of the I-D.

>CA, that information is deleted.

That feature does allow the RA to forget 
registration data that don't result in cert 
issuance, a nice feature.  Thanks for the 
suggested change. I think it should be 
incorporated into the next rev of the I-D.

>If the CA cannot be immediately contacted, the 
>entity is informed that a delay may exist

This design envisions a CA (instance) that issues 
certs only under one, anonymous policy, so the 
feature is not strictly required.

>- a proposed pseudonym,

The RA must not know the pseudonym that will 
appear in the cert, as that would allow it to map 
the issued cert to the user. This is NOT OK.

I didn't comment on the rest of the design 
because the RA-supplied pseudonym undermines the 
anonymity guarantees.  Also, having the CA issue 
the cert unilaterally undermines the separation 
of duties and the two-party collusion aspects of 
the design.

I think we can make two changes based on your 
observations, as noted above, to improve the 
protocol, but the threshold signature and blind 
signature elements are still needed, which makes 
the BI/AI terminology appropriate.

Steve

---

From: "Denis Pinkas"<[email-masked]>
Date: Fri, 27 Jun 2008 10:40:50 +0200

Steve,

Responses are embedded.

De : Stephen Kent 
À : denis.pinkas 
Date : 2008-06-27, 04:52:41
Sujet : Re: Comments on draft-ietf-pkix-tac-00.txt

The scheme that is described is lacking replay protection in several exchanges.
Most of the messages exchanges are to be performed over TLS, as recommended throughout the I-D, 
and TLS protects against intra-session replays.  Looking at figure 1, steps is not affected by this suggestion; 
in  step 2 the user could make use of a time stamp embedded in the token to detect a replay, 
but we don't  require an on-the-wire exchange here, if the exchange is not in person, then use of TLS 
would prevent a session level replay, so I see no problem here.

In step 3 the CA could use a time stamp in the Token to reject a replayed request, but in step 5 the RA 
could detect the reuse of the Token and reject it, so the time stamp is only speeding up the detection 
of the replay here. (I guess we need to be explicit about this re-use check in the description  of step 5.) 
Nonetheless, a time stamp in the Token might prove useful. There is no need for the time stamp in steps 5+6, 
as they are conducted over a TLS (or equivalent) connection, and the BI will reject a reused token, as noted above. 
I step 7, the user is getting a cert in response to his request, via a TLS channel, and thus should be immune to session level replay as well.

So the bottom line is that adding a time stamp to the UserKey does offer some advantages in speeding up 
detection of session-level replay attacks in one place. It's a simple change to make and probably worthwhile.

Denis :  you got the point.

Denis : it is the next point you agree with: a mechanism for garbage collection.

- the registration information of every entity,
- a UserKey chosen by the RA which consists of a date and time concatenated with a random number.
OK, a simple change, probably worthwhile. We'll put it in te next rev of the I-D.

This information is kept by the RA during x hours.
If the CA is not contacted within x hours by the CA, that information is deleted.
That feature does allow the RA to forget registration data that don't result in cert issuance, a nice feature.  
Thanks for the suggested change. I think it should be incorporated into the next rev of the I-D.

Denis :  you got the point.

 
- the UserKey chosen by the RA,
- the OID of the certificate policy under which the certificate should be issued,
This design envisions a CA (instance) that issues certs only under one, anonymous policy, so the feature is not strictly required.

- a proposed pseudonym,
The RA must not know the pseudonym that will appear in the cert, as that would allow it to map the issued cert to the user. 
This is NOT OK.

Denis :  in the above exchanges, the RA does not know the pseudonym. The mapping is only done using the UserKey.
The threshold signature and blind signature elements are not fundamental.

I didn't comment on the rest of the design because the RA-supplied pseudonym undermines the anonymity guarantees.

Denis :  awaiting your comments on the remaining of the comments. 
  
Also, having the CA issue the cert unilaterally undermines the separation of duties and the two-party collusion aspects of the design.

I think we can make two changes based on your observations, as noted above, to improve the protocol, 
but the threshold signature and blind signature elements are still needed, which makes the BI/AI terminology appropriate.

Steve

---

From: Stephen Kent <[email-masked]>
Date: Mon, 30 Jun 2008 13:43:58 -0400

Denis,

>...
>
>Denis :  in the above exchanges, the RA does not know the pseudonym. 
>The mapping is only done using the UserKey.

Sorry that I misread your text, inferring that the RA supplied the 
pseudonym. Although my comment about the source of the pseudonym wa 
wrong, it doesn't change my conclusion (see below).

The next part of your proposed redesign is as follows:

>In that case, the entity makes a second request with the same 
>UserKey. Otherwise the CA contacts the RA

In the design you propose, the CA issued the cert to the user by 
itself (from a crypto perspective), which undermines the two-party 
issuance model in the I-D. The split signing key procedure described 
in the I-D requires that the RA also sign the hash of the cert, which 
prevents the CA from acting unilaterally (which would yield a 
non-traceable cert). Having both the CA and RA sign the cert yields a 
stronger system, and the blind signature by the CA is needed to 
enable the split key signing without disclosing the hash value to the 
RA.

So, unless one wants to weaken the guarantees provided by the 
two-party signing, I think the split key and blind signing aspects of 
the design need to be retained.  Also, as I noted earlier given the 
split key and blind signature aspects of the design in the I-D, the 
terms AI and BI are appropriate.

I agree that if one did not want to have the crypto security offered 
by the split key approach (which then necessitates the blind 
signature function), the design here could be simplified. But, my 
co-authors see this form of crypto security as a central, motivating 
aspect of the design, so I believe it should remain.  Thanks, though, 
for your suggestions re inclusion of a time stamp in the Token and 
the timeout notion to help with garbage collection.

Steve