Convenient One-, Two- and Three-factor Authentication for Mobile Devices

Authentication methods used today on mobile devices are both inconvenient and insecure.

Ordinary passwords are difficult to type on small touch-screen displays that require switching keyboards for entering digits or punctuation. They provide even less security on mobile devices than on desktops or laptops. Due to the difficulty of typing on mobile keyboards, each character is prominently displayed after it is typed, circumventing the security provided by password input boxes that displays dots in lieu of characters. And users are motivated to choose shorter and simpler passwords, which have less entropy.

One-time passwords are often used on mobile devices due to the lack of security of ordinary passwords. Authenticating with a one-time password requires entering a PIN, obtaining the one-time password from a hard token, a soft token, a text message, or an email message, and entering the one-time password. This is a very cumbersome procedure. A one-time password is a two-factor authentication method, and is thus more secure than an ordinary password. But they have limited entropy, and they can be replayed within a time-window of several minutes. An attacker who observes or intercepts a one-time password has several minutes during which he or she can use it to log in as the legitimate user.

Social login avoids some of the inconvenience of ordinary and one-time passwords by outsourcing authentication to a social network. If the user is already logged in to the social network, he or she does not have to enter a password again. Current standards for social login are a mess, as I said in the previous post, and as confirmed by the recent resignation of the editor of the OAuth protocol. In the previous post I linked to a white paper where we propose a better social login protocol, SAAAM, well suited for mobile devices.

But while social login is useful in some cases, it is not always appropriate. There is no reason why applications should always rely on social networks to authenticate their users, or why a user should have to surrender his or her privacy to a social network in order to authenticate to an unrelated application. Also, social login does not completely solve the authentication problem, since the user still has to authenticate to the social network.

So there is a need for good authentication methods on mobile devices that do not rely on a third party. We have just written a white paper proposing one-, two- and three-factor authentication methods for mobile devices that provide strong security and are more convenient to use than ordinary or one-time passwords. They are particularly well suited for enterprise use, but are suitable for consumer use as well.

The proposed authentication methods are based on public key cryptography, but they are easy to implement and deploy. They are easy to implement because all cryptography is encapsulated in black boxes, so that developers do not have to program any cryptographic operations. They are easy to deploy because they avoid the use of certificates and do not require a public-key infrastructure.

In our one-factor authentication method the user does not have to provide any input. The device authenticates by demonstrating knowledge of a private key. A hash of the associated public key is stored in a device record, which is linked to a user record in an enterprise directory or user database.

In our two-factor authentication method, the user provides a PIN, which is used to regenerate the key pair. Because any PIN results in a well-formed key pair, the user’s PIN is not exposed to an exhaustive offline guessing attack by an attacker who steals the mobile device, opens it, and reads its persistent memory.

In our three-factor authentication method, the user provides a PIN and a biometric such as an iris scan. No biometric template is stored in the mobile device. Instead, the device contains an auxiliary string that is used in conjunction with the biometric to provide a biometric key. The biometric key is used to regenerate the key pair. The auxiliary string is encrypted by the PIN for additional security.

NSTIC Is Not Low-Hanging Fruit

In a recent tweet, Ian Glazer quoted Patrick Gallagher, director of NIST, saying at a recent White House meeting on NSTIC that the “current suite of technologies we rely on are insufficient”.

The identity technologies used today both in federal agencies and on the Web at large are indeed insufficient:

  • SSL client certificates have failed to displace passwords for Web authentication since they were introduced 17 years ago.
  • Credentials in PIV cards have failed to displace passwords in federal agencies eight years after HSPD 12; a GAO report does a good job of documenting the many obstacles faced by agencies in implementing the directive, ranging from the fact that some categories of agency employees do not have PIV cards, to the desire by employees to use Apple MAC computers and mobile devices that lack card readers. I’m glad that we don’t live in the Soviet Union and heads of agencies are not sent to the Gulag when they ignore unreasonable orders.
  • Third-party login solutions such as OpenID, as currently used on the Web, not only do not eliminate passwords, they make the password security problem worse, by facilitating phishing attacks. They also impinge on the user’s privacy, because the identity provider is told what relying parties the user logs in to.
  • Social login solutions based on OAuth, e.g. “login with Facebook”, worsen the privacy drawback of third party login by limiting the user’s choice of identity providers to those that the relying party has registered with, and by broadcasting the user’s activities to the user’s social graph. Eric Sachs of Google said at the last Internet Identity Workshop that users participating in usability testing were afraid of logging in via Facebook or Google+ because “their friends would be spammed”.

But some proponents of NSTIC do not seem to realize that. In a recent interview, Howard Schmidt went so far as to say that NSTIC is “low-hanging fruit”, because “the technology is there”. What technology would that be? In a blog post that he wrote last year shortly after the launch of NSTIC, it was clear that the technology he was considering for NSTIC was privacy-enhancing cryptography, used by Microsoft in U-Prove and by IBM in Idemix. He used the words “privacy-enhancing” in the interview, so he may have been referring to that technology in the interview as well.

(Credentials based on privacy-enhancing cryptography provide selective disclosure and unlinkability. Selective disclosure refers to the ability to combine multiple attributes in a credential but disclose only some of them when presenting the credential. Unlinkability, in the case of U-Prove, refers to the impossibility of linking the use of a credential to its issuance; Idemix also makes it impossible to link multiple uses of the same credential.)

But Idemix has never been deployed commercially, and an attempt at deploying U-Prove within the Information Cards framework failed when Microsoft discontinued CardSpace, two months before the launch of NSTIC.

Credentials based on privacy-enhancing cryptography, sometimes called anonymous credentials, have inherent drawbacks. One of them is that unlinkability makes revocation of such credentials harder than revocation of public key certificates, as I pointed out in a blog post on U-Prove and another blog post on Idemix. The difficulty of revoking credentials based on privacy-enhancing cryptography has led ABC4Trust, which can be viewed as the European counterpart of NSTIC, to propose arresting users for the purpose of revoking their credentials! See page 23, end of last paragraph, of the ABC4Trust document Architecture for Attribute-based Credential Technologies.

Another inherent drawback is that it is difficult to keep the owner of an anonymous credential from making it available for use online by others who are not entitled to it. For example, it would be difficult to prevent the owner of a proof-of-drinking-age anonymous credential (a use case often cited by proponents of anonymous credentials) from letting minors use it for a fee.

The mistaken belief that “the technology is there” explains why the NSTIC NPO has made little effort to improve on existing technology. Instead of requesting funding for research, it requested funding for pilots; a pilot is usually intended to demonstrate the usability of a newly developed technology; it assumes that the technology already exists. After the launch of NSTIC, the NPO announced three workshops, on governance, privacy and technology. The first two were held, but the workshop on technology, which was supposed to take place in September of last year, was postponed by six months and merged with the yearly NIST IDtrust workshop, which took place in March of this year. The IDtrust workshop usually includes a call for papers. But this year there was none: new ideas were not solicited.

The NSTIC NPO has been trying to “bring relying parties to the table”. Ian Glazer dubbed the recent White House meeting the NSTIC Relying Party Event. The meeting was about getting a bigger table according to the NPO blog post on the event, and about “getting people to volunteer” according the Senator Mikulski as quoted by the blog post. Earlier, Jim Sheire of the NPO convened a session entitled NSTIC How do we bring relying parties to the table? at the last Internet Identity Workshop.

One idea mentioned in the report on the IIW session for bringing relying parties to the table is to target 100 “top relying parties” in the hope of creating a snowball effect. But it’s not clear what it would mean for those 100 relying parties and any additional ones caught in the snowball, to “come to the table”. What would they do at the table? What technology would they use? OpenID? OAuth? Smart cards? Information cards? Anonymous credentials? NSTIC has not proposed any specific technology. Or would they come to the table just to talk?

There are many millions of Web sites that use passwords for user authentication. The goal should be to get all those sites to adopt an identity solution that eliminates the security risk of passwords. Web site developers will do that of their own initiative once a solution is available that is more secure and as easy to deploy as password authentication.

While the technology is not there, various technology ingredients are there, and missing ingredients could be developed. It is not difficult to conceive a roadmap that could lead to one or more good identity solutions. But success would require a concerted effort by many different parties: not only relying parties and identity and attribute providers, but also standards bodies, browser vendors, vendors of desktop and mobile operating systems, vendors of smart cards and other hardware tokens, perhaps biometric vendors, and the providers of the middleware, software libraries, and software development tools used on the Web. When I first heard of NSTIC I hoped that it would provide the impetus and the forum needed for such a concerted effort. But that has yet to happen.

One-Click OpenID: A Solution to the NASCAR Problem

OpenID allows the user to choose any identity provider, even one that the relying party has never heard of. This freedom of choice is, in my opinion, the most valuable feature of OpenID. Unfortunately, this feature comes with a difficult challenge: how to provide the relying party with the information it needs to interact with the identity provider.

OAuth does not have this problem because the relying party has to preregister with the identity provider, typically a social site, and therefore must know of the identity provider. An OAuth relying party displays one or a few buttons labeled with the logos of the social sites it supports, e.g. Facebook and Twitter, and the user chooses a site by clicking on a button. But of course freedom of choice is lost: the user can only use as identity provider a social site supported by the relying party.

The traditional OpenID user interface consists of an input box where the user types in an OpenID identifier, which serves as the starting point of an identity provider discovery process. To compete with the simplicity of picking a social site by clicking on a button, some OpenID relying parties present the user with many buttons labeled by logos of popular OpenID identity providers, in addition to the traditional input box; but this user interface has been deemed ugly and confusing to the user. The many logos have been compared to the many ads on a race car, hence the term NASCAR problem that is used to refer to the OpenID user interface challenge.

To solve the challenge we propose to let the browser keep track of the identity provider(s) that the user has signed up with. The list of identity providers will be maintained by the browser as a user preference.

An identity provider will be added to the list by explicit declaration. As the user is visiting the identity provider’s site, the provider will offer its identity service to the user. The user will accept the offer by clicking on a button or link. In the HTTP response to the browser that follows the HTTP request triggered by this action the identity provider will include an ad-hoc HTTP header containing identity provider data including the OP Endpoint URL. The browser will ask the user for permission to add the identity provider to the list and store the identity provider data.

A relying party will use a login form containing a single button, with a label such as Login with OpenID. There need not be any input box for entering an OpenID identifier, nor any buttons with logos of particular identity providers. The form will contain a new ad-hoc non-visual element <idp>. When the form is submitted, the browser will choose one identity provider from the list and send its data to the relying party as the value of the <idp> element.

Which identity provider is chosen is up to the browser. It could be the default, or an identity provider that has previously been used for the relying party, as recorded by the browser, or an identity provider explicitly chosen by the user from a menu presented by the browser. The browser could choose to permanently display a menu showing the user’s list of identity providers as part of the browser chrome.

We arrived at this solution while thinking about the NSTIC pilot that we plan to propose. In the planned proposal the identity provider issues a certificate to the browser, which the browser imports automatically. A natural extension is to let the identity provider download to the browser other data besides the certificate, such as the OP Endpoint URL. Also, a browser user interface for selecting an identity provider is akin to the user interface for selecting a client certificate that browsers already have. We realize that existing user interfaces for certificate selection are less than optimal, but we believe that this is due to lack of attention by browser manufacturers to a rarely used feature, and that better interfaces can be designed.

OpenID Providers Invited to Join in an NSTIC Pilot Proposal

NSTIC has announced funding for pilot projects. Preliminary proposals are due by March 7 and full proposals by April 23. There will be a proposer’s conference on February 15, which will be webcast live.

We are planning to submit a proposal and are inviting OpenID identity providers to join us. The proposed pilot will demonstrate a completely password-free method of user authentication where the relying party is an ordinary OpenID relying party. The identity provider will issue a public key certificate to the user, and later use it to authenticate the user upon redirection from the relying party. The relying party will not see the certificate. Since the certificate will be verified by the same party that issued it, there will be no need for certificate revocation lists. Certificate issuance will be automatic, using an extension of the HTML5 keygen mechanism that Pomcor will implement on an extension of the open source Firefox browser.

There will be two privacy features:

  1. The identity provider will supply different identifiers to different relying parties, as in the ICAM OpenID 2.0 Profile.
  2. Before authenticating the user, the identity provider will inform the user of the value of the DNT (Do Not Track) header sent by the browser, and will not track the user if the value of the header is 1.

The identity provider will:

  1. Implement a facility for issuing certificates to users, taking advantage of the keygen element of HTML5. The identity provider will obtain a public key from keygen, create a certificate that binds the public key to the user’s local identity, and download the certificate in an ad-hoc HTTP header. Pomcor will supply a Firefox extension that will import the certificate automatically.
  2. Use the certificate to authenticate the user upon redirection from the relying party. The browser will submit the certificate as a TLS client certificate. The mod_ssl module of Apache supports the use of a client certificate and makes data from the certificate available to high-level server-side programming environments such as PHP via environment variables.

For additional information you may write to us using the contact page of this site.

After CardSpace, Microsoft Calls for Research on Passwords

In February 2011 Microsoft discontinued CardSpace, a Windows application for federated login that was the deployment vehicle for the U-Prove privacy-enhancing Web authentication technology, which itself is said to have inspired the NSTIC initiative. Cormac Herley, a Microsoft researcher, and Paul van Oorshot, a professor at Carleton University, have written a paper entitled A Research Agenda Acknowledging the Persistence of Passwords that mentions the CardSpace failure and calls for research on traditional password authentication.

The paper makes two points:

  1. It blames the failure of attempts at replacing passwords on a lack of research on identifying and prioritizing the requirements to be met by alternative authentication methods.
  2. It argues that passwords have many virtues, will persist for some time, and may be the best fit in many scenarios; and it calls for research on how to better support them.

I disagree with the first point but agree with the second.

The problem with the first point is that it does not take into account the non-technical obstacles faced by alternative authentication methods. Microsoft Passport was the first attempt at Web single sign-on. It was launched when Microsoft was in the process of annihilating the Netscape browser and acquiring a monopoly in Web browsing; it originally had an outrageous privacy policy, which was later modified; and if successful it would have made Microsoft a middleman for all Web commerce. No wonder it failed.

Other single sign-on initiatives had obvious non-technical obstacles. OpenID required people to use a URL as their identity, something that could only appeal to the tiny fraction of users who understand or care about the technical underpinnings of the Web. CardSpace was a Microsoft product; that by itself must have provided motivation for all Microsoft competitors to oppose it; furthermore it only ran on Windows; and in order to support CardSpace relying party developers had to install and learn to use a complex toolkit. Again, no wonder CardSpace failed.

The non-technical obstacles faced by Passport, OpenID and CardSpace were due to lack of maturity of the Web industry. Such obstacles will slowly go away as the industry matures. Signs of maturity are appearing: there are now five major browsers that seem to understand the need for common standards; the World Wide Web consortium (W3C) has shown that it can bring them together to develop standards such as HTML5 and has already engaged them in identity work through the Identity in the Browser workshop and the identity mailing list that was set up after the workshop; and OpenID 2.0 no longer insists on users using URLs as their identities. Industries can take decades to mature, so it’s not surprising that progress is slow.

As for passwords, I agree that they have virtues, will persist, and deserve research. There is actually research on passwords going on.

Password managers are an active area of research and development by browser providers and others.

There was a session on passwords at the last Internet Identity Workshop (IIW), called by Jay Unger, where Alan Karp described his site password tool, which can be viewed as an alternative to a password manager, where passwords for different sites are computed rather than retrieved from storage. The tool computes a high entropy password for a Web site from a master password and an easy-to-remember name for the site.

I have myself been recently granted two patents on password security, which were also discussed at the IIW session on passwords:

  • One of them describes a countermeasure against online password guessing that places a hard limit on the total number of guesses that an attacker can make against a password. Besides the traditional counter of consecutive bad guesses the countermeasure uses an additional counter of total bad guesses, not necessarily consecutive. The user is asked to change her password if and when this second counter reaches a threshold, rather than at arbitrary intervals.
  • The other describes a technique for password distribution, that allows an administrator to send a temporary password to a user, e.g. after a password reset, over an unprotected channel such as ordinary email. The administrator puts a hold on the user’s account that allows no further access beyond changing the temporary password into a password chosen by the user. The administrator removes the hold only after being notified by the legitimate user that she has successfully changed the password, e.g. over the phone. In abstract terms, instead of relying on a confidential channel to send the password, the administrator relies on a channel with data-origin authentication to receive the user’s notification.

Microsoft or anybody else who wants to increase password security can license either of these patents. You may use the contact form of this site to inquire about licensing.

Credential Sharing: A Pitfall of Anonymous Credentials

There is an inherent problem with anonymous credentials such as those provided by Idemix or U-Prove: if it is not possible to tell who is presenting a credential, the legitimate owner of a credential may be willing to lend it to somebody else who is not entitled to it. For example, somebody could sell a proof-of-drinking-age credential to a minor, as noted by Jaap-Henk Hoepman in a recent blog post [1].

This problem is known in cryptography as the credential sharing or credential transferability problem, and various countermeasures have been proposed. In this post I will briefly discuss some of these countermeasures, then I will describe a new method of sharing credentials that is resistant to most of them.

A traditional countermeasure proposed by cryptographers, mentioned for example in [2], is to deter the sharing of an anonymous credential by linking it to one or more additional credentials that the user would not want to share, such as a credential that gives access to a bank account, in such a way that the sharing of the anonymous credential would imply the sharing of the additional credential(s). I shall refer to this countermeasure as the “credential linking countermeasure”. I find this countermeasure unrealistic, because few people would escrow their bank account for the privilege of using an anonymous credential.

In her presentation [3] at the recent NIST Meeting on Privacy-Enhancing Cryptography [4], Anna Lysyanskaya said that it is a misconception to think that “if all transactions are private, you can’t detect and prevent identity fraud”. But the countermeasure that she proposes for preventing identity fraud is to limit how many times a credential is used and to disclose the user’s identity if the limit is exceeded. However this can only be done in cases where a credential only allows the legitimate user to access a resource a limited number of times, and I can think of few such cases in the realm of Web authentication. Lysyanskaya gives as an example a subscription to an online newspaper, but such subscriptions typically provide unlimited access for a monthly fee. I shall refer to this countermeasure as the “limited use countermeasure”.

Lysyanskaya’s presentation also mentions identity escrow as useful for conducting an investigation if “something goes very, very wrong”.

At the panel on Privacy in the Identification Domain at the same meeting Lysyanskaya also proposed binding an anonymous credential to a biometric. The relying party would check the biometric and then forget it to keep the presentation anonymous. But if the relying party can be trusted to forget the biometric, it may as well be trusted to forget the entire credential presentation, in which case an anonymous credential is not necessary.

An interesting approach to binding a biometric to a credential while keeping the user anonymous can be found in [5]. The biometric is checked by a tamper-proof smartcard trusted by the relying party, but a so-called warden trusted by the user is placed between the smartcard and the relying party, and mediates the presentation protocol to ensure that no information that could be used to identify or track the user is communicated by the smart card to the relying party.

However, if what we are looking for is an authentication solution that will replace passwords on the Web at large, biometric-based countermeasures are not good candidates because of their cost.

Update. In a response to this post on the Identity Commons mailing list Terry Boult has pointed out that cameras and microphones are pretty ubiquitous and said that, in volume, fingerprint sensors are cheaper than smartcard readers.

In his blog post [1], Hoepman suggested that, to prevent the sharing of an anonymous credential, the credential could be stored in the owner’s identity card, presumably referring to the national identity card that citizens carry in the Netherlands and other European countries. This is a good idea because lending the card would put the owner at risk of impersonation by the borrower. I shall refer to this as the “identity card countermeasure”.

Rather than storing a proof of age credential as an additional credential in a national identity card, anonymous proof of age could be accomplished by proving in zero knowledge that a birthdate attribute of a national identity credential (or, in the United States, of a driver’s license credential) lies in an open interval ending 21 years before the present time; Idemix implements such proofs. The identity credential could be stored in a smartcard or perhaps in a tamper-proof module within a smart phone or a personal computer. I’ll refer to this countermeasure as the “selective disclosure countermeasure”. As in the simpler identity card countermeasure, the legitimate user of the credential would be deterred from sharing the credential with another person because of the risk of impersonation.

But this countermeasure, like most of the above ones, does not help with the following method of sharing credentials.

A Countermeasure-Resistant Method of Sharing Credentials

An owner of a credential can make the credential available for use by another person without giving a copy of the credential to that other person. Instead, the owner can allow that other person to act as a proxy, or man-in-the-middle, between the owner and a relying party in a credential presentation. (Note that this is not a man-in-the-middle attack because the man in the middle cooperates with the owner.)

For example, somebody of drinking age could install his or her national identity credential or driver’s license credential on a Web server, either by copying the credential to the server or, if the credential is contained in a tamper-proof device, by connecting the device to the server. The credential owner could then allow minors to buy liquor by proxying a proof of drinking age based on the birthdate attribute in the credential. (Minors would need a special user agent to do the proxying, but the owner could make such user agent available for download from the same server where the credential is installed.) The owner could find a surreptitious way of charging a fee for the service.

This method of sharing a credential, which could be called proxy-based sharing, defeats most of the countermeasures mentioned above. Biometric-based countermeasures don’t work because the owner of the credential can input the biometric. Credential linking countermeasures don’t work because the secret of the credential is not shared. The identity card countermeasure and the selective disclosure countermeasure don’t work because the owner is in control of what proofs are proxied and can refuse to proxy proofs that could allow impersonation. The limited use countermeasure could work but, as I said above, I can think of few Web authentication cases where it would be applicable.

Are there any other countermeasures that would prevent or inhibit this kind of sharing? If a minor were trying to buy liquor using an identity credential and a payment credential, the merchant could require the minor to prove in zero-knowledge that the secret keys underlying both credentials are the same. That would defeat the sharing scheme by making the owner of the identity credential for pay for the purchase. However there are proof-of-age cases that do not require a purchase. For example, an adult site may be required to ask for proof of age without or before asking for payment.

The only generally applicable countermeasure that I can think of to defeat proxy-based sharing is the identity escrow scheme that Lysyanskaya referred to in her talk [3]. Using provable encryption, as available in Idemix, a liquor merchant could ask the user agent to provide the identity of the owner of the credential as an encrypted attribute that could be decrypted, say, by a judge. (The encrypted attribute would be randomized for unlinkability.) The user agent would include the encrypted attribute in the presentation proof after asking the user for permission to do so.

Unfortunately this requires the user to trust the government. This may not be a problem for most people in many countries. But it undermines one of the motivations for using privacy-enhancing technologies that I discussed in a previous blog [6].

References

[1] Jaap-Henk Hoepman. On using identity cards to store anonymous credentials. November 16, 2011. Blog post, at http://blog.xot.nl/2011/11/16/on-using-identity-cards-to-store-anonymous-credentials/.
 
[2] Jan Camenisch and Anna Lysyanskaya. An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology (EUROCRYPT 01). 2001. Research report available from http://www.zurich.ibm.com/security/privacy/.
 
[3] Anna Lysyanskaya. Conditional And Revocable Anonymity. Presentation at the NIST Meeting on Privacy-Enhancing Cryptography. December 8-9, 2011. Slides available at http://csrc.nist.gov/groups/ST/PEC2011/presentations2011/lysyanskaya.pdf.
 
[4] NIST Meeting on Privacy-Enhancing Cryptography. December 8-9, 2011. At NIST Meeting on Privacy-Enhancing Cryptography.
 
[5] Russell Impagliazzo and Sara Miner More. Anonymous Credentials with Biometrically-Enforced Non-Transferability. In Proceedings of the 2003 ACM workshop on Privacy in the electronic society (WPES 03).
 
[6] Francisco Corella. Are Privacy-Enhancing Technologies Really Needed for NSTIC? October 13, 2011. Blog post, at http://pomcor.com/2011/10/13/are-privacy-enhancing-technologies-really-needed-for-nstic/.
 

Trip Report: Meeting on Privacy-Enhancing Cryptography at NIST

Last week I participated in the Meeting on Privacy-Enhancing Cryptography at NIST. The meeting was organized by Rene Peralta, who brought together a diverse international group of cryptographers and privacy stakeholders. The agenda is online with links to the workshop presentations.

The presentations covered many applications of privacy-enhancing cryptography, including auctions with encrypted bids, database search and data stream filtering with hidden queries, smart metering, encryption-based access control to medical records, format-preserving encryption of credit card data, and of course authentication. There was a talk on U-Prove by Christian Paquin, and a talk on Idemix by Gregory Neven. There were also talks on several techniques besides anonymous credentials that could be used to implement privacy-friendly authentication: group signatures, direct anonymous attestation, and EPID (Enhanced Privacy ID). Kazue Sako’s talk described several possible applications of group signatures, including a method of paying anonymously with a credit card.

A striking demonstration of the practical benefits of privacy-enhancing cryptography was the presentation on the Danish auctions of sugar beets contracts by Thomas Toft. A contract gives a farmer the right to grow a certain quantity of beets for delivery to Danisco, the only Danish sugar producer. A yearly auction allows farmers to sell and buy contracts. Each farmer submits a binding bid, consisting of a supply curve or a demand curve. The curves are aggregated into a market supply curve and a market demand curve, whose intersection determines the market clearing price at which transactions take place. What’s remarkable is that farmers submit encrypted bids, and bids are never decrypted. The market clearing price is obtained by computations on encrypted data, using secure multiparty computation techniques. Auctions have been successfully held every year since 2008.

I was asked to participate in the panel on Privacy in the Identification Domain and to start the discussion by presenting a few slides summarizing my series of blog posts on privacy-enhancing technologies and NSTIC. In response to my slides, Gregory Neven of IBM reported that a credential presentation takes less than one second on his laptop, and Brian La Macchia of Microsoft pointed out that deployment is difficult for public key certificates as well as for privacy-friendly credentials. There were discussions with Gregory Neven on revocation and with Anna Lysyanskaya on how to avoid the sharing of anonymous credentials; these are big topics that deserve their own blog posts, which I plan to write soon, so I won’t say any more here. Jeremy Grant brought the audience up to date about NSTIC, which has received funding and is getting ready to launch pilots. Then there was a wide ranging discussion.

Do-Not-Track and Third-Party Login

Recently the World Wide Web Consortium (W3C) launched a Tracking Protection Working Group, following several recent proposals for Do-Not-Track mechanisms, and more specifically in response to a W3C-member submission by Microsoft. A useful list of links to proposals and discussions related to Do-Not-Track can be found in the working group’s home page.

The Microsoft submission was concerned with tracking by third-party content embedded in a Web page via cookies and other means of providing information to the third party. It proposed a Do-Not-Track setting in the browser, to be sent to Web sites in an HTTP header and made available to Javascript code as a DOM property. It also proposed a mechanism allowing the user to specify a white list of third party content that the browser would allow in a Web page and/or a black list of third party content that the browser would block. The browser would filter the requests made by a Web page for downloading third-party content, allowing some and rejecting others.

(The specific filtering mechanism proposed by Microsoft would allow third-party content that is neither in the white list nor in the black list. This would be ineffective, since the third party could periodically change the domain name it uses to avoid being blacklisted. I trust that the W3C working group will come up with a more effective filtering mechanism.)

A Do-Not-Track setting and a filtering mechanism are good ideas, but they only deal with the traditional way of tracking a user. Today there is another way of tracking a user, which can be used whenever the user logs in to a Web site with authentication provided by a third party, such as Facebook, Google or Yahoo.

Third-party login uses a double-redirection protocol. When the user wants to log in to a Web site, the user’s browser is redirected to a third party, which plays the role of “identity provider.” The identity provider authenticates the user and redirect the browser back to the Web site, which plays the role of “relying party.” The identity provider is told who each relying party is, and can therefore can track the user without any need for cookies. The identity provider can link the user’s logins to relying parties to the information in the user’s account at the identity provider, which in the case of Facebook includes the user’s real name and much other real identity information.

Privacy-enhancing technologies, which I discussed in a recent series of blog posts (starting with the one on U-Prove), may eventually make it possible to log in with a third party credential without the identity provider being able to track the user; but in the meantime, means must be found of providing protection against tracking via third-party login. The W3C Tracking Protection working group could provide such protection by broadening the scope of the Do-Not-Track setting so that it would apply to both the traditional method of tracking via embedded content and the new method of tracking via third-party login. An identity provider who receives a Do-Not-Track header while participating in a double-redirection protocol would be required to forget the transaction after authenticating the user.

The scope of the filtering mechanism could also be broadened so that it would apply to redirection requests in addition to third-party content embedding. This could mitigate a security weakness that affects third-party login protocols such as OpenID and OAuth. Such protocols are highly vulnerable to a phishing attack that captures the user’s password for an identity provider: the attacker sets up a malicious relying party that redirects the browser to a site masquerading as the identity provider. A filtering mechanism that would block redirection by default could prevent the attack based on the fact that the site masquerading as the identity provider would not be whitelisted (while the legitimate identity provider would be).

Benefits of TLS for Issuing and Presenting Cryptographic Credentials

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

[1] Christian Paquin. U-Prove Cryptographic Specification V1.1 Draft Revision 1, February 2011. Downloadable from http://www.microsoft.com/u-prove.
 
[2] M. Blum, P. Feldman and S. Micali. Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC 1988).
 
[3] Jan Camenisch et al. Specification of the Identity Mixer Cryptographic Library, Version 2.3.1. December 2010. Available at http://www.zurich.ibm.com/~pbi/identityMixer_gettingStarted/ProtocolSpecification_2-3-2.pdf.
 
[4] A. Fiat and A. Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Proceedings on Advances in Cryptology (CRYPTO 86), Springer-Verlag.
 
[5] J. Groth and A. Sahai. Efficient Non-Interactive Proof Systems for Bilinear Groups. In Theory and Applications of Cryptographic Techniques (EUROCRYPT 08), Springer-Verlag.
 
[6] R. Canetti, O. Goldreich and S. Halevi. The Random Oracle Methodology, Revisited. Journal of the ACM, vol. 51, no. 4, 2004.