Pros and Cons of U-Prove for NSTIC

This is the first of a series of posts on the prospects for using privacy-enhancing technologies in the NSTIC Identity Ecosystem.

NSTIC calls for the use of privacy-friendly credentials, and NSTIC documents [1] [2] refer to the existence of privacy-enhancing technologies that can be used to implement such credentials. Although those technologies are not named, they are widely understood to be U-Prove and Idemix.

There is confusion regarding the capabilities of privacy-enhancing technologies and the contributions that they can make to NSTIC. For example, I sometimes hear the opinion that “U-Prove has been oversold”, but without technical arguments to back it up. To help clear some of the confusion, I’m starting a series of posts on the prospects for using privacy-enhancing technologies in the NSTIC Identity Ecosystem. This first blog is on the pros and cons of U-Prove, the second one will be on the pros and cons of Idemix, and there will probably be two more after that.

U-Prove is described in the U-Prove Cryptographic Specification V1.1 [3] and the U-Prove Technology Overview [4]. It is based on cryptographic techniques described in Stefan Brands’s book [5].

Privacy Feature Coverage

Three features of privacy-friendly credentials are informally described in NSTIC documents:

1. Issuance of a credential cannot be linked to a use, or “show,” of the credential even if the issuer and the relying party share information, except as permitted by the attributes certified by the issuer and shown to the relying party.
2. Two shows of the same credential to the same or different relying parties cannot be linked together, even if the relying parties share information.
3. The user agent can disclose partial information about the attributes asserted by a credential. For example, it can prove that the user if over 21 years of age based on a birthdate attribute, without disclosing the birthdate itself.

Here I will not discuss how desirable these features are; I leave that for a later post in the series. In this post I will only discuss the extent to which U-Prove provides these features.

U-Prove provides the first feature, which is called untraceability in the U-Prove Technology Overview [4]. A U-Prove credential consists of a private key, a public key, a set of attributes, and a signature by the credential issuer. The signature is jointly computed by the issuer and the user agent in the course of a three-turn interactive protocol, the issuance protocol, where the issuer sees the attributes but not the public key nor the signature itself. Therefore the issue of a credential can be linked to a show of the credential only on the basis of the attribute information disclosed during the show.

U-Prove, on the other hand, does not provide the second feature, because all relying parties see the same public key and the same signature. Stefan Brands acknowledges this in Section 2.2 of [6], where he compares the system of his book [5] to the system of Camenisch and Lysianskaya, i.e. U-Prove to Idemix, acknowledging that the latter provides multi-show unlinkability but the former does not.

Unfortunately, the U-Prove Technology Overview [4] is less candid. It does discuss the fact that multiple shows of the same U-Prove credential (U-Prove token) are linkable, in Section 4.2, but the section is misleadingly entitled Unlinkability. It starts as follows:

Similarly, the use of a U-Prove token cannot inherently be correlated to uses by the same Prover of other U-Prove tokens, even if the Issuer identified the Prover and issued all of the Prover’s U-Prove tokens at the same time.

This is saying that different U-Prove tokens are not linkable! Which is a vacuous feature: why would different tokens be linkable? The section goes on to argue that that the issuer should issue many tokens to the user agent (the Prover) with the same attributes, one for each relying party (each Verifier). On the Web, this is utterly impractical. There are millions of possible relying parties: how many tokens should be issued? How can all those tokens be stored on a smart card? What if the user agent runs out of tokens? And how does the user agent know if two parties are different or the same? (Is example.com the same relying party as xyz.example.com?)

Update. Stefan Brands has pointed out that a U-Prove token does not take up any storage in a smart card if the private key splitting technique featured by U-Prove (which I refer to below) is used.

As for the third feature of privacy-friendly credentials, partial information disclosure, U-Prove provides it to a certain extent. When showing a credential, the user agent can disclose only some of the attributes in the credential, proving to the relying party that those attributes were certified by the credential issuer without disclosing the other attributes. However, U-Prove does not support the “age over 21” example found in several NSTIC documents. That would require the ability to prove that a value is contained in an interval without disclosing the value. Appendix 1 of the U-Prove Technology Overview [4] lists the ability to perform such a proof as one of the “U-Prove features” that have not been included in Version 1.1, suggesting that it could be included in a future version. In Section 3.7 of his book [5], Stefan Brands does suggest a method for proving that a secret is contained in an interval. However, it dismisses it as involving “a serious amount of overhead”, because it requires executing many auxiliary proofs of knowledge. (I believe that proving “age over 21” would require at least 30 auxiliary proofs, which is clearly impractical.)

An interesting feature of U-Prove is the ability to split the private key of a credential between the user agent and a device such as a smart card. The device must then be present for the credential to be usable, thus providing two-factor authentication; but the device only has to perform a limited amount of cryptographic computations, most of the cryptographic computations being carried out by the user agent. This makes it possible to use slower, and hence cheaper, devices than if all the cryptographic computations were carried out by the device (as is the case, for example, in an Idemix smart card).

Update. A non-Microsoft implementation of U-Prove on a MULTOS smart card, where all the cryptographic computations are carried out by the card with impressive performance (close to 0.3 seconds in some cases), can be found in [8].

Revocation

The ability to revoke credentials is usually taken for granted. In the case of privacy-friendly credentials, however, it is difficult to achieve. An ordinary CRL (Certificate Revocation List) cannot be used, since it would require some kind of credential identifier known to both the issuer and the relying parties, which would defeat unlinkability.

U-Prove credentials have a Token Identifier, which is a hash of the public key and the signature. Because U-Prove does not provide multi-show unlinkability, the Token Identifier, like the public key and the signature, is known to all the relying parties. The user agent could therefore revoke the credential by including the Token Identifier in a CRL. However, because U-Prove provides issue-show unlinkability, the credential issuer does not know the Token Identifier, nor the public key or the signature, and therefore cannot use it to revoke the credential.

Section 5.2 of the U-Prove Technology Overview [4] says that an identifier could be included in a special attribute called the Token Information Field for the purpose of revocation, and “blacklisted using the same methods that are available for X.509 certificates”; this, however, would destroy the only unlinkability feature of U-Prove credentials, viz. issuance-show unlinkability (which [4] calls untraceability).

Section 5.2 of [4] also suggests using on-demand credentials. However that does not seem practical: the user agent would have to authenticate somehow to the issuer, then conduct a three-turn interactive issuance protocol with the issuer to obtain the token, then conduct a presentation protocol with the relying party. The latency of all these computations and interactions would too high; and since the issuance computations would have to be carried out each time the credential is used, the cost for the issuer would be staggering. Furthermore, on-demand credentials may allow linking of issuance to show by timing correlation.

A workaround to the revocation problem is suggested in Section 6.2 of [4], for cases where the credential is protected by a device such as a smart card by splitting the private key between the user agent and the device. In those cases the Issuer could revoke the device rather than a particular credential protected by the device, by adding an identifier of the device to a revocation list. However this would require downloading the revocation list to the device in a Device Message when the credential is used, so that the device can check if its own identifier is in the list. Since a revocation list can have hundreds of thousands of entries (e.g. the state of West Virginia revokes about 90,000 driver licenses per year [7]), downloading it to a smart card each time the smart card is used is not a viable option.

Update. Stefan Brands has pointed out that only a revocation list increment needs to be downloaded to the card.

Appendix 1 of [4] includes an “issuer-driven revocation” feature in a list of U-Prove features not yet implemented:

An Issuer can revoke one or more tokens of a known Prover by blacklisting a unique attribute encoded in these tokens (even if it is never disclosed at token use time).

How this can be achieved is not explained in the appendix, nor in Brands’s book [5]. However it is explained in [6], where Brands proposes a new system and compares it to his previous system of [5], i.e. to U-Prove. He says that [5] “allows an issuer to invisibly encode into all of a user’s digital credentials a unique number that the issuer can blacklist in order to revoke that user’s credentials” adding that the blacklist technique “consists of repeating a NOT-proof for each blacklist element”. In other words, the idea is to prove a formula stating that the unique number is NOT equal to the first element of the blacklist, and NOT equal to the second element, and NOT equal to the third element, etc., without revealing the unique number. That can be done but, as Brands further says in [6], it is “not practical for large blacklists”. Indeed, based on Section 3.6 of [5], proving a formula with multiple negated subformulas requires proving separately each negated subformula. So if the blacklist has 100,000 elements, 100,000 proofs would have to be performed each time a credential is used.

By the way, the system of [6] is substantially different from U-Prove and not well suited for use on the Web, since it requires the set of relying parties to be known at system-setup time.

Update. Stefan Brands has told me that the cryptosystem described in [6] is considered part of the U-Prove technology, and that the revocation technique of [6] could be integrated into the existing U-Prove implementation to provide issuer-driven revocation.

Conclusions

I will save my conclusions for the last post in the series, but of course any comments are welcome now.

References

[1]	The White House. National Strategy for Trusted Identities in Cyberspace. April 2011. Available at http://www.whitehouse.gov/sites/default/files/rss_viewer/NSTICstrategy_041511.pdf.
[2]	Howard A. Schmidt. The National Strategy for Trusted Identities in Cyberspace and Your Privacy. April 26, 2011. White House blog post, available at http://www.whitehouse.gov/blog/2011/04/26/national-strategy-trusted-identities-cyberspace-and-your-privacy.
[3]	Christian Paquin. U-Prove Cryptographic Specification V1.1 Draft Revision 1. February 2011. No http URL seems to be available for this document, but it can be downloaded from the Specifications and Documentation page, which itself is available at http://www.microsoft.com/u-prove.
[4]	Christian Paquin. U-Prove Technology Overview V1.1 Draft Revision 1. February 2011. No http URL seems to be available for this document, but it can be downloaded from the Specifications and Documentation page, which itself is available at http://www.microsoft.com/u-prove.
[5]	Stefan Brands. Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy 2000. MIT Press, Cambridge, MA, USA, 2000. ISBN 0262024918. Available for free download at http://www.credentica.com/the_mit_pressbook.php
[6]	Stefan Brands, Liesje Demuynck and Bart De Decker. A practical system for globally revoking the unlinkable pseudonyms of unknown users. In Proceedings of the 12th Australasian Conference on Information Security and Privacy, ACISP’07. Springer-Verlag, 2007. ISBN 978-3-540-73457-4. Preconference technical report available at http://www.cs.kuleuven.be/publicat ies/rapporten/cw/CW472.pdf.
[7]	West Virginia Department of Transportation, Division of Motor Vehicles. Annual Report 2010. Available at http://www.transportation.wv.gov /business-manager/Finance/Financial%20Reports/DMV_AR_2010.pdf.
[8]	Update. W. Mostowski and P. Vullers. Efficient U-Prove Implementation for Anonymous Credentials on Smart Cards. Available at http://www.cs.ru.nl/~pim/publications/2011_securecomm.pdf.