Pomcor

In comments on the previous post at the Identity Commons mailing list and comments at the session on deployment and usability of cryptographic credentials at the Internet Identity Workshop, people have questioned the advantages of running cryptographic protocols for issuing and presenting credentials inside TLS, and argued in favor of running them instead over HTTP. I believe running such protocols inside TLS removes several obstacles that have hindered the deployment of cryptographic credentials. So in this post I will try to answer those comments.

Here are three advantages of running issuance and presentation protocols inside TLS over running them outside TLS:

1. TLS is ubiquitous. It is implemented by all browsers and all server middleware. If issuance and presentation protocols were implemented inside TLS, then users could use cryptographic credentials without having to install any applications or browser plugins, and developers of RPs and IdPs would not have to install and learn additional SDKs.
2. The PRF facility of TLS is very useful for implementing cryptographic protocols. For example, in the U-Prove presentation protocol [1], when U-Prove is used for user authentication, the verifier must send a nonce to the prover; if the protocol were run inside TLS, that step could be avoided because the nonce could be independently generated by the prover and the verifier using the PRF. The PRF can also be used to provide common pseudo-random material for protocols based on the common reference string (CRS) model [2]. (Older cryptosystems such as U-Prove [1] and Idemix [3] rely on the Fiat-Shamir heuristic [4] to eliminate interactions, but more recent cryptosystems based on Groth-Sahai proofs [5] rely instead on the CRS model, which is more secure in some sense [6].)
3. Inside TLS, an interactive cryptographic protocol can be run in a separate TLS layer, allowing the underlying TLS record layer to interleave protocol messages with application data (and possibly with messages of other protocol runs), thus mitigating the latency impact of protocol interactions.

And here are two advantages of running protocols either inside or directly on top of TLS, over running them on top of HTTP:

1. Simplicity. Running a protocol over HTTP would require specifying how protocol messages are encapsulated inside HTTP requests and responses, i.e. it would require defining an HTTP-level protocol.
2. Performance. Running a protocol over HTTP would add the overhead of sending HTTP headers, and, possibly, of establishing different TLS connections for different HTTP messages if TLS connections cannot be kept alive for some reason.

As always, comments are welcome.

References

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

Experience has shown that it is difficult to deploy cryptographic credentials on the Web and have them adopted by users, relying parties and credential issuers. This is true for privacy-friendly credentials as well as for ordinary public-key certificates, both of which have a place in the NSTIC Identity Ecosystem, as I argued in the previous post.

I believe that this difficulty can be overcome by putting the browser in charge of managing and presenting credentials, by supporting cryptographic credentials in the core Web protocols, viz. HTTP and TLS, and by providing a simple and automated process for issuing credentials.

Browsers should manage and present credentials

For credentials to be widely adopted, users must not be required to install additional software, let alone proprietary software that only runs on one operating system, such as Windows Cardspace. Therefore credentials must be managed and presented by the browser.

The browser should allow users to set up multiple personas or profiles and associate particular credentials with particular personas. Many users, for example, have a personal email address and a business email address, which could be associated with a personal profile and a business profile respectively. The user could declare one profile to be the “currently active persona” in a particular browser window or tab, and thus facilitate the selection of appropriate credentials when visiting sites in that window or tab.

People who use multiple browsers in multiple computing devices (including desktop or laptop computers, smart phones and tablets) must have access to the same credentials on all those devices. Credentials can be synced between browsers through a Web service without having to trust the service by equipping each browser with a key pair for encryption and a key pair for signature (in the same way as email can be sent with end-to-end confidentiality and origin authentication using S/MIME or PGP). Credentials can be backed up to an untrusted Web service similarly.

Cryptographic credentials should be supported by HTTP and TLS

HTTP should provide a way for the relying party to ask for particular credentials or attributes, and TLS should provide a way for the browser to present one or multiple credentials. Within TLS, the mechanism for presenting credentials should be separate from and subsequent to, the handshake, to benefit from the confidentiality and integrity offered by the TLS connection after it has been secured.

Credentials should be issued automatically to the browser, through TLS

Privacy-friendly credentials have cryptographically complex interactive issuance protocols. Paradoxically, this suggests a way of simplifying the issuance process, for both PKI certificates and privacy-friendly credentials.

Since the process is interactive, it should be run directly on a transport layer connection, to avoid HTTP and application overhead. That connection should be secure to protect the confidentiality of the attributes being certified. To reduce the latency due to the cryptographic computations, the protocol interactions should be interleaved with the transmission of other data. And the cryptographic similarity of issuance and presentation protocols suggests that they should be run over the same kind of connection.

All this leads to the idea of running issuance protocols, like presentation protocols, directly over a TLS connection. TLS has a record layer specification that could be extended to define two new kinds of records, one for issuance protocol messages, the other for presentation protocol messages. TLS would then automatically interleave protocol interactions with transmission of other data. (Another benefit of TLS is that its PRF facility could be readily used to generate the common reference string used by some cryptographic protocols.)

Since TLS is universally supported by server middleware, implementing issuance protocols directly over TLS would make allow servers to issue credentials automatically without installing additional software. In particular, it would make it easy for any Web site to issue a PKI certificate as a result of the user registration process, for use in subsequent logins.

User Experiences

Once credentials are handled by browsers and directly supported by the core protocols of the Web, smooth and painless user experiences become possible.

For example, a user can open a bank account online as follows. The user accepts terms and conditions and clicks on an account creation button button. The bank asks the browser for a social security credential and a driver’s license credential. The browser presents the credentials to the bank after asking the user for permission. The bank checks the user’s credit ratings and automatically creates an account and issues a PKI certificate binding the account number to the public key component of a new key pair generated by the browser on the fly. On a return visit, the user clicks on a login button and the bank asks the browser for the certificate. The user may allow the browser to present the certificate without asking for permission each time. Double factor authentication can be achieved, for example, by keeping the private key and certificate in a password-proctected smart card.

As a second example, suppose a user visits a site to sign up for receiving coupons by email. The user accepts terms and conditions and clicks on a sign-up button. The site asks the browser for a verified email-address certificate (issued by an email service provider) and a number of self-asserted attributes, such as zip code, gender, age group, and set of shopping preferences. The browser finds in its certificate store (or in a connected smart card) an email address certificate and a personal-data credential associated with the currently active persona. The personal-data credential is a privacy-friendly credential featuring unlinkability and selective disclosure. The browser presents simultaneously the email certificate and the personal-data credential, disclosing only the personal-data attributes requested by the site. The browser may or may not ask the user for permission to present the credentials, depending on user preferences that may be persona-dependent.

Conclusions

In this series of posts I have argued that new privacy-enhancing technologies should be developed to fill the gaps in currently implemented systems and to take advantage of new techniques developed by cryptographers over the last 10 or 15 years. I have also argued that the NSTIC Identity Ecosystem should accomodate both privacy-friendly credentials and ordinary PKI certificates, because different use cases call for different kinds of credentials. Finally I have sketched above two examples of user experiences that can be provided if credentials are handled by browsers and directly supported by the core protocols of the Web.

Of course this requires major changes to the Web infrastructure, including: extensions to HTTP; a revamp of TLS to allow for the presentation of privacy-friendly credentials, the simultaneous presentation of multiple credentials, and the issuance of credentials; support of the protocol changes in browsers and server middleware; and implementation of browser facilities for managing credentials.

These changes may seem daunting. The private sector by itself could not carry them out, especially given the current reliance of technology companies on business models based on advertising, which benefit from reduced user privacy. But I hope NSTIC will make them possible.

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

In the first two posts we’ve looked at two, or rather three, privacy-enhancing authentication technologies: U-Prove, Idemix, and the Idemix Java card. The credentials provided by these technologies have some or all of the privacy features called for by NSTIC, but they have various practical drawbacks, the most serious of which is that they are not revocable by the credential issuer.

Given these drawbacks, it is natural to ask the question: are privacy-friendly credentials really necessary for NSTIC? My answer is: they are not needed in many important use cases, and they are useful but not indispensable in other important cases; but they are essential in cases that are key to the success of NSTIC.

Use Cases Where Privacy-Enhancing Technologies Are Not Needed

The most common use case of Web authentication is the case where a user registers anonymously with a Web site and later logs in as a returning user. Traditionally, the user registers a username and a password with the site and later uses them as credentials to log in. Today, third-party login is becoming popular as a way of mitigating the proliferation or reuse of passwords: the user logs in with username and password to a third-party identity provider, and is then redirected to the Web site, which plays the role of relying party. But there is a way of avoiding passwords altogether: the Web site can issue a cryptographic credential to the user upon registration, which the user can submit back to the Web site upon login. In that case there is no third party involvement and no privacy issues. The cryptographic credential can therefore be an ordinary PKI certificate. No privacy-enhancing technologies are needed.

Update. The PKI certificate binds the newly created user account to the public key component of a key pair that the browser generates on the fly.

Other cases where privacy-enhancing technologies are not needed are those where a credential demonstrates that the user possesses an attribute whose value uniquely identifies the user, and the relying party needs to know the value of that attribute. (One example of such an attribute is an email address.) Privacy-enhancing technologies are not useful in such cases because a uniquely-identifying attribute communicated to relying parties can be used to track the user no matter what type of credential is used to communicate the attribute.

Use Cases Where Privacy-Enhancing Technologies Are Useful but not Essential

Privacy-enhancing technologies are useful but not essential when the attributes certified by a credential do not uniquely identify the user, and the user has a choice of credential issuers. They are useful in such cases because they prevent the issuer from tracking the user’s activities by sharing data with the relying parties. They are not essential, however, because the user may be able to choose a credential issuer that she trusts. (Most privacy-enhancing technologies also prevent relying parties from collectively tracking the user by sharing their login information, without involvement of the credential issuer, but the risk of this happening may be more remote.)

Examples of non-identifying attributes are demographic attributes (city of residence, gender, age group), shopping interests, hobby interests, etc.; such attributes are usually self-asserted, but they can be supplied by an identity provider, chosen by the user, as a matter of convenience, so that the user does not have to reenter them and maintain them uptodate at each relying party. Examples of sites that may ask for such attributes are dating sites, shopping deal sites, hobbyist sites, etc.

Of course, a credential that contains non-identifying attributes will not by itself allow a user to log in to a site. But it can be used in addition to a PKI certificate issued by the site itself to recognize repeat visitors.

Use Cases Where Privacy-Enhancing Technologies Are Necessary

Privacy-enhancing technologies are necessary when the relying party does not require uniquely identifying information, and there is only one credential issuer. That one credential issuer could be the government. Non-uniquely-identifying information provided by government-issued credentials could include assertions that the user is old enough to buy wine, or is a resident of a particular state, or is licensed to practice some profession in some state, or is a US citizen, or has the right to work in the US.

I find it difficult to find examples where people would have a reasonable fear of being tracked through their use of government-issued credentials. But the right to privacy is a human right that is held dear in the United States, and has been found to be implicitly protected by the US constitution. Government-issued credentials will only be acceptable if they incorporate all available privacy protections. That makes the use of privacy-enhancing technologies essential to the success of NSTIC.

Wanted: Efficiently-Revocable Privacy-Friendly Credentials

So: privacy-friendly credentials are necessary; but, in my opinion, the drawbacks of existing privacy-enhancing technologies make them impractical. Therefore we need new privacy-enhancing technologies. Those new technologies should have issue-show and multi-show unlinkability; they should provide partial information disclosure, including proofs of inequality relations involving numeric attributes; and they should be efficiently revocable.

Fortunately, that’s not too much to ask. U-Prove and Idemix have been pioneering technologies, but they are now dated. U-Prove is based on research carried out in the mid-nineties, and the core cryptographic scheme later used in Idemix was described in a paper written in 2001. A lot of research has been done in cryptography since then, and several new cryptographic schemes have been proposed that could be used to provide privacy-friendly credentials.

I don’t think a scheme meeting all the requirements, including efficient revocation, has been designed yet. (I would love to be corrected if I’m wrong!) But possible ingredients for such a system have been proposed, including methods for proving non-revocation in time proportional to the square root of the number of revoked credentials [1] or even in practically constant time [2].

Update. Stefan Brands has told me that the cryptosystem described in [1] is considered part of the U-Prove technology, and that the revocation technique of [1] could be integrated into the existing U-Prove implementation to provide issuer-driven revocation. If that were done and the resulting system proved to be suitably efficient, the only ingredient missing from that system would be multi-show unlinkability.

Once a scheme with all the ingredients has been designed and mathematically verified, it still needs to be implemented. Cryptographic implementations are few and far between, but that does not mean that they are difficult. Recently, for example, three different systems of privacy-friendly credentials were implemented just for the purpose of comparing their performance [3].

Next and Last: Usability and Deployment

To conclude the series, in the next post I’ll try to respond to a comment made by Anthony Nadalin on the Identity Commons mailing list: “if it’s not useable or deployable who cares?”.

References

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

In the previous post I discussed the pros and cons of U-Prove , so naturally I should now discuss the pros and cons of Idemix, the other privacy-enhancing technology thought to have inspired NSTIC. This post, like the previous one, is based on a review of the public literature. If I’ve missed or misinterpreted something, please let me know in a comment.

By the way, a link to the previous post that I posted to the Identity Commons mailing list triggered a wide-ranging discussion on NSTIC and privacy, which can be found in the mailing list archives .

Idemix is an open-source library implemented in Java. It is described in the Idemix Cryptographic Specification [1], and the academic paper [2]. It is mostly based on the cryptographic techniques of [3]. Curiously, although Idemix is provided by IBM, the main Idemix site is located at idemix.wordpress.com and disclaims to be an official IBM site.

There is also a smart card that implements a “light-weight variant of Idemix”. I discuss it at the end of this post.

Feature Coverage

Idemix provides all three privacy features alluded to in NSTIC documents [4] [5] and discussed in the previous post:

1. Issuance-show unlinkability,
2. Multi-show unlinkability, and
3. Partial information disclosure.

The third feature includes both selective disclosure of attributes and the ability to prove inequalities such as the value of a birthdate attribute being less than today’s date minus 21 years without disclosing that birthdate attribute value.

Idemix also includes other features, such as the ability to prove that two attributes have the same value without disclosing that value, and the ability to prove that a certain attribute certified by the issuer has been encrypted under the public key of a third party, which may decrypt it under some circumstances. It could be argued that Idemix is over-engineered for the purpose of Web authentication, including features that add complexity but are not useful for that purpose.

Performance

The richer feature set of Idemix may come at a cost in terms of performance. From the data in Table 1 of [2], it follows that it would take about 12 seconds for the user to submit a credential with one attribute to a relying party that checks for expiration, and about 28 seconds to submit a credential with 20 attributes. The paper dates back to 2002, and the processor used was a relatively slow 1.1GHz Pentium III. (The authors say 1.1MHz but I assume they mean 1.1GHz.) But on the other hand the modulus size was 1024 bits, and Idemix currently uses a 2048 modulus [2]. The paper also promises optimizations that have no doubt been implememted by now. Unfortunately, I haven’t been able to find performance data in the Idemix site. A search for the word performance restricted to the site produces no results. If you know of any recent performance data, please let me know in a comment.

Revocation

We saw in the previous post that unlinkability makes revocation difficult. U-Prove credentials can be revoked by users because they do not have multi-show unlinkability, but cannot be revoked by issuers because they have issue-show unlinkability. Idemix credentials, which have both multi-show unlinkability and issue-show unlinkability, are revocable neither by users nor by issuers. I am not saying that unlinkability makes revocation impossible. Cryptographic techniques have been devised to allow revocation of unlinkable credentials, which I will discuss later in this series of posts. But those techniques are not used by U-Prove or Idemix.

Idemix has a credential update feature that can be used to extend the validity period of a credential that has expired. This facilitates the use of short-term credentials that may not need to be revoked. But the Idemix Cryptographic Specification [1] should not claim as it does that the credential-update feature can be used to implement credential revocation. Waiting for a credential to expire is not the same as revoking it. Short term credentials are an alternative to revocation. And, as an alternative, they have serious drawbacks: they are costly to implement for the issuer; they impose a logistic burden on the user agent; they may become unavailable if the issuer is down when the validity period needs to be extended; and the user agent may be overwhelmed by the need to renew many credentials at once if it has not been operational for an extended period of time. If a short-term credential is renewed on demand, just before it is used, renewal and use of the credential may be linkable by timing correlation.

The Idemix Java Card

The Idemix Java Card was intended as a smart identity card. Its implementation on the Java Card Open Platform (JCOP) is described in [6].

The cryptographic system in an Idemix card is described in the Idemix site as a “light-weight variant of Identity Mixer” (i.e. Idemix). But it is very different from the original Idemix system. According to [6], an implementation of the original system in a Java card would be impractical because credential submission could take 70 to 100 seconds. To make it less impractical, the issuer of a credential to a Java card certifies only that it trusts the Java card. The card is then free to present any attributes it wants to the relying party. (A different way of handling attributes is possible but not recommended, presumably because of the time it takes; see Footnote 5 of [6].) Security for the relying party depends on the issuer downloading the correct attributes and software to the card, and the user not being able to modify those attributes and software. The card must therefore be tamper resistant against the user. (Or at least tamper responsive, i.e. able to detect tampering and respond by zeroing out storage.)

Whereas a U-Prove smart card performs only a small portion of the cryptographic computations, the Idemix Java card is an autonomous system that performs all the cryptographic computations by itself, without help from the user’s computer. This takes time: 10.453 seconds for a transaction, i.e. for submitting a credential to a relying party, according to Table 2 of [6]; or 11.665 seconds according to Table 3. (In both cases, with a 1536-bit modulus, and not counting a 1.474 second revocation check; revocation is discussed below; the discrepancy between the two figures is not explained.) Some of the computations in Table 2 are labeled as precomputations, but no precomputations can take place if the card is not plugged in. The authors of [6] consider that a 10 second transaction time would be adequate. But I don’t think many Web users will be happy waiting 10 seconds each time they want to log in to a site.

Update. It is possible to implement full-blown privacy-friendly credentials systems very efficiently on a smart card. A non-Microsoft implementation of U-Prove on a MULTOS smart card [8], where all the cryptographic computations are carried out by the card, achieves credential-show times close to 0.3 seconds.

The Idemix card features a revocation mechanism. A card can be revoked by including its secret key in a revocation list. But the secret key is generated in the card when the card is “set up”, and it is not known to the party that sets up the card, nor to the issuers of credentials to the card, nor to the user who owns the card. The secret key can only be obtained by breaching the tamper pretection of the card, hence can only become known to an adversary. So the revocation feature seems useless.

Where does the peculiar idea of listing secret keys in a revocation list come from? It turns out that the cryptographic system of the Idemix card is derived from the cryptographic system of [7] which was designed for media copyright protection, e.g. to authenticate the Trusted Platform Module (TPM) in a DVD player before downloading a protected movie to the player. Apparently hackers extract secret keys of TPMs and publish them on the Web. Copyright owners find those secret keys and blacklist them. Blacklisting secret keys makes sense for copyright protection, but not as a revocation technique for smart cards.

Coming Next…

After reading this post and the previous post, you may be thinking whether privacy-enhanced technologies are really a good idea. I will try to answer that question in the next post.

References