J-PAKE: From Dining Cryptographers to Jugglers

Academic papers, Cryptology

Password Authenticated Key Exchange (PAKE) is one of the central topics in cryptography. It aims to address a practical security problem: how to establish secure communication between two parties solely based on their shared password without requiring a Public Key Infrastructure (PKI).

The solution to the above problem is very useful in practice — in fact, so useful that it spawns a lot “fights” over patents. Many techniques were patented, including the well-known Encrypted Key Exchange (EKE) and Simple Password Exponential Key Exchange (SPEKE). A secondary problem is technical; both the EKE and SPEKE protocols have subtle but worrying technical limitations (see the paper for details).

At the 16th Workshop on Security Protocols held in April 2008, Cambridge, UK, I presented a new solution (joint work with Peter Ryan) called Password Authenticated Key Exchange by Juggling (or J-PAKE). The essence of the protocol design inherits from the earlier work on solving the Dining Cryptographers problem; we adapted the same juggling technique to the two-party case to solve the PAKE problem. To our best knowledge, this design is significantly different from all past PAKE solutions.

Intuitively, the J-PAKE protocol works like a juggling game between two people — if we regard a public key as a “ball”. In round one, each person throws two ephemeral public keys (“balls”) to each other. In round 2, each person combines the available public keys and the password to form a new public key, and throws the new “ball” to each other.

After round 2, the two parties can securely compute a common session key, if they supplied the same passwords. Otherwise, the protocol leaks nothing more than: “the supplied passwords at two sides are not the same”. In other words, one can prove his knowledge of the password without revealing it. A Java implementation of the protocol on a MacBook Pro laptop shows that the total computation time at each side is merely 75 ms.

We hope this protocol is of usefulness to security engineers. For example, compared with SSL/TLS, J-PAKE is potentially much more resistant against phishing attacks, not to mention that it is PKI-free. Since this protocol is the result of an academic research project, we didn’t — and have no intention to — patent it. As explained in the paper, J-PAKE even has technical advantages over the patented EKE and SPEKE in terms of security, with comparable efficiency. It has been submitted as a follow-up to the possible future extension of IEEE P1363.2.

We believe the PAKE research is important and has strong practical relevance. This post is to facilitate discussions on this subject. The paper can be viewed here. Any comments or questions are welcome.

Update

  • 2008-06-28: a crude J-PAKE demo source code (.java) by me. (link broken)
  • 2008-11-04: a more refined J-PAKE in C and OpenSSL by Ben Laurie.
  • 2008-11-11: possible applications of J-PAKE in VPN and browser by James.
  • 2009-02-08: public group parameters for 112-bit and 128-bit security can be found in the comments.
  • 2009-03-15: fixed the broken link to the old Java file. Here is the link to the Java demo code.
  • 2010-04-17: a journal version of the paper available on IACR. No technical change to the protocol.
  • 2010-10-25: the journal version of the paper is accepted to publish on the TCS journal – Springer Transactions on Computational Science, the special issue on “Security in Computing”, 2011.
  • 2010-11-25: Sebastien Martini reported an implementation issue of J-PAKE in OpenSSL and OpenSSH. The issue is not applicable to the Java demo code that I wrote. As stated in the last paragraph of p. 11 in the paper, one shall check the element lies within the specified group. Stefan Arentz implemented a fix in OpenSSL. Official OpenSSL and OpenSSH patches can be found here and here.
  • 2011-01-11: Mozilla built J-PAKE into the base product of Firefox 4 ( beta 8 and later). More details here.
  • 2012-01-18: Today, Mohsen Toorani uploadeda paper on IACR eprint to claim several attacks on J-PAKE. My response can be found here.
  • 2012-07-21: Phil Clay contributed a Java implementation of J-PAKE to bouncycastle.
  • 2013-02-24: J-PAKE included into bouncycastle 1.48.
  • 2013-03-28: a code example to show how to use J-PAKE in bouncycastle
  • 2013-05-21: Submitted two Internet Drafts to IETF (one on J-PAKE and the other one on Schnorr NIZK Proof)
  • 2013-12-30: a code example to show how to implement J-PAKE using Elliptic Curve (or ECDSA-like group setting)
  • 2014-04-17: J-PAKE included into VMware NSS Cryptographic Module
  • 2014-10-27: J-PAKE adopted by the ISO/IEC standard (11770-4) following the ISO/IEC SC27 meeting held in Mexico City, October 20-24, 2014
  • 2014-12-26: My response to Mohsen Toorani’s IEEE ISCC’14 paper “Security Analysis of J-PAKE”.
  • 2015-04-29: J-PAKE included into Python
  • 2015-05-08: Standardization of J-PAKE in ISO/IEC 11770-4 in process. The first working draft (WD1) passed reviews by ISO/IEC SC27 at Kuching Malaysia, May 5-8, 2015.
  • 2015-05-19: Here is an independent formal analysis of J-PAKE by other researchers published at Oakland’2015. Their results are consistent with the original J-PAKE paper.
  • 2015-05-30: J-PAKE included in BarcoSilex BA414E Public Key crypto engine
  • 2015-05-31: Firefox is upgrading Sync 1.1 (using J-PAKE to transfer a full-entropy AES key between sync devices) to new Sync 1.5 (using user-defined passwords as encryption keys). But Pale moon decides to stay with Sync 1.1.
  • 2015-07-28: the Thread Technical white paper is public. It describes a technique that securely enrols a new device to the network based on J-PAKE. The technique is used in Google Nest thermostat products.
  • 2017-10-06: J-PAKE published in ISO/IEC 11770-4 as an international standard and also published in RFC 8236. See here.

PED vulnerability paper receives "Most Practical Paper" award at Oakland

Academic papers, Awards, Banking security

In February, Steven Murdoch, Ross Anderson and I reported our findings on system-level failures of widely deployed PIN Entry Devices (PED) and the Chip and PIN scheme as a whole. Steven is in Oakland presenting the work described in our paper at the IEEE Symposium on Security and Privacy (slides).

We are very pleased that we are the recipients of the new “Most Practical Paper” award of the conference, given to “the paper most likely to immediately improve the security of current environments and systems”. Thanks to everyone who supported this work!

IEEE Security & Privacy Magazine Award

Twisty little passages, all alike

Legal issues, News coverage, Security engineering

Last month, on the 4th April, I published a document describing how the Phorm system worked and blogged about what I thought of the scheme. The document had been run past Phorm’s technical people to ensure it was correct, but — it turns out — there were still a handful of errors in it. A number of helpful people pointed out that I’d misdescribed third-party cookies (which didn’t matter much because Phorm specifically uses first-party cookies), and I’d managed to reference RFC2695 rather than RFC2965 !

In my original document, I’d waved my hands a little bit about how the system worked if people had blocked cookies for specific domains, and so I swapped some more email with Phorm to better understand, and then published a revised version on 23rd April — so that the correct information would be available to accompany FIPR’s press release and paper on the various laws that the Phorm system breaks. However, there was one final thing that wasn’t dealt with by press time, and that’s now been explained to me….

The Phorm system does some of its tracking magic by redirecting browser requests using HTTP 307 responses. When this was first explained to me at the meeting with Phorm there were two redirections (a scan of my notes is here), but having thought about this for a while, I asked for it to be explained to me again later on, and it turned out that I had previously been misled, and that there were in fact three redirections (here’s my notes of this part of the meeting).

It now turns out, following my further emails with Phorm, that there are in fact FOUR redirections occurring! This is not because my notes are rubbish — but because Phorm have managed to recall more of the detail of their own system!

For full details of how I understand the system works (at least until some more detail comes to light), see the latest version of my explanatory document, but to give you a flavour of it, consider an example visit to www.cnn.com:

  • The user wants to visit www.cnn.com, but their request does not contain a cookie (for www.cnn.com) with a Phorm unique identifier within it. They are redirected (ONE) by the Phorm system to www.webwise.net.
  • The user visits webwise.net by following the redirection. If they do not have a Phorm identifier cookie, then they will be issued with a new identifier and redirected (TWO) elsewhere on webwise.net.
  • The user visits webwise.net for the second time. If they still don’t have a Phorm identifier cookie then their IP address is marked as wishing to opt-out and they will be redirected to www.cnn.com and they won’t be redirected again for at least 30 minutes. If they do have a cookie (or if they had one at the previous stage) they are redirected (THREE) to a special URL within www.cnn.com.
  • The user visits the special URL, which the Phorm system redirects to a fake version of www.cnn.com that sets a www.cnn.com cookie with their Phorm identifier in it, and redirects (FOUR) them to the URL they wanted to visit all along.

For the moment, this appears to be the grand total; there can be up to four redirections, and it is deducible from this description what happens if you refuse (or delete) cookies in the webwise.net and www.cnn.com domains. It is also apparent that if you resolve webwise.net to 127.0.0.1 that you’ll never get past the first redirection; and you will need to rely on the Phorm system spotting these repeated failures and turning off redirection for your IP address.

direct adjective: Straightforward in manner or conduct; upright, honest.

indirect adjective: Mechanism by which Phorm fools your system into accepting tracking cookies from third-party websites, even when those websites promise never to track you!

Hardened stateless session cookies

Academic papers, Cryptology, Meta, Security engineering

The root cause behind the last-but-one WordPress cookie debacle was that the authors invented their own password hashing and cookie generation scheme. This is generally a bad idea, since it’s hard even for experts to get these right. Instead, whenever possible, a well-studied proposal should be chosen. It is for this reason that I suggested the phpass library for password hashing, and the Fu et al. stateless session cookie proposal.

These choices would be a substantial improvement on the previous custom design (had they been implemented correctly), but I still was not quite satisfied. The Fu et al. scheme has the property that an attacker who can read the cryptographic key stored in the database can create spoofed cookies. Given the history of WordPress security, it seems likely that there will eventually be a vulnerability discovered which allows the key, which authenticates cookies, to be leaked.

It’s good practice in security engineering to design systems with the widest possible range of attacker capabilities in mind. I therefore designed a cookie scheme which would do all that the Fu et al. design did, but also maintained some of its security properties if the attacker has read-access to the authentication database and knows the cookie authentication key. I published a paper on this topic — Hardened stateless session cookies — at the 2008 Security Protocols Workshop.

The trick behind my scheme is to store the hash of the user’s password in the cookie, and the hash of that in the authentication database. This means that it’s possible for the server to verify cookies, but the authentication database doesn’t contain enough information to create a fake cookie. Thus an attacker with read-access to the database still needs to know the user’s password to log in, and that isn’t stored. There are some additional subtleties to resist different attacks, and those are described in the paper.

I hope this proposal will trigger discussion over this important problem and lead to improved cookie authentication schemes.

Second edition

Banking security, Electronic voting, Internet censorship, Privacy technology, Security economics, Security engineering

The second edition of my book “Security Engineering” came out three weeks ago. Wiley have now got round to sending me the final electronic version of the book, plus permission to put half a dozen of the chapters online. They’re now available for download here.

The chapters I’ve put online cover security psychology, banking systems, physical protection, APIs, search, social networking, elections and terrorism. That’s just a sample of how our field has grown outwards in the seven years since the first edition.

Enjoy!

WordPress 2.5 cookie integrity protection vulnerability

Academic papers, Cryptology, Meta

Recently, I was preparing to give a talk on web authentication so was looking at the source code of WordPress, which I had just upgraded to version 2.5. Unfortunately, I found a rather nasty security hole, which has now been disclosed. If a WordPress installation is configured to permit account creation, the vulnerability allows an attacker to gain administrator access.

The problem is to do with how cookies are generated. The authentication code was substantially overhauled for WordPress 2.5, in part to deal with security problems in the password database. Now, the authentication cookies take the form of:

wordpress_.COOKIEHASH = USERNAME . | . EXPIRY_TIME . | . MAC

Where:
COOKIEHASH
MD5 hash of the site URL (to maintain cookie uniqueness)
USERNAME
The username for the authenticated user
EXPIRY_TIME
When cookie should expire, in seconds since start of epoch
MAC
HMAC-MD5(USERNAME . EXPIRY_TIME) under a key derived from a secret and USERNAME . EXPIRY_TIME.

This scheme is based on two papers: Dos and Don’ts of Client Authentication on the Web by Fu et al. and A Secure Cookie Protocol by Liu et al. However, there is a small difference and, as is common in cryptographic systems, small changes can have big impact.

The problem is that USERNAME and EXPIRY_TIME are not delimited when calculating the MAC. This means that a MAC for one cookie is valid for any other, provided that USERNAME . EXPIRY_TIME is unchanged. So an attacker can register a username starting with “admin”, log in as usual, then modify their cookie so it’s valid for the administrator account.

Fu et al. called this the “cryptographic splicing” attack in their paper (Section 3.3), and is one of the many ways they show how people can slip up when implementing web authentication. Unfortunately, dynamic website frameworks, especially PHP, offer little assistance to programmers trying to implement secure applications.

I will expand on this topic in a future post but in the mean time, if you run WordPress, you really should upgrade to 2.5.1. While WordPress 2.3.3 doesn’t have the problem described here, it is still not secure.

There is some more detail on the cookie vulnerability in my disclosure (CVE-2008-1930). WordPress have mentioned it in their release announcement and I’ve also just sent it to the usual mailing lists.

Stealing Phorm Cookies

Legal issues, News coverage, Privacy technology

Last week I gave a talk at the 80/20 Thinking organised “town hall meeting” about the Phorm targeted advertising system. You can see my slides here, and eventually there will be some video here.

One of the issues I talked about was the possibility of stealing Phorm’s cookies, which I elaborate upon in this post. I have written about Phorm’s system before, and you can read a detailed technical explanation, but for the present, what it is necessary to know is that through some sleight-of-hand, users whose ISPs deploy Phorm will end up with tracking cookies stored on their machine, one for every website they visit, but with each containing an identical copy of their unique Phorm tracking number.

The Phorm system strips out these cookies when it can, but the website can access them anyway, either by using some straightforward JavaScript to read their value and POST it back, or by the simple expedient of embedding an https image ( <img = "https://.... ) within their page. The Phorm system will not be able to remove the cookie from an encrypted image request.

Once the website has obtained the Phorm cookie value, then in countries outside the European Union where such things are allowed (almost expected!), the unique tracking number can be combined with any other information the website holds about its visitor, and sold to the highest bidder, who can collate this data with anything else they know about the holder of the tracking number.

Of course, the website can do this already with any signup information that has been provided, but the only global tracking identifier it has is the visiting IP address, and most consumer ISPs give users new IP addresses every few hours or few days. In contrast, the Phorm tracking number will last until the user decides to delete all their cookies…

A twist on this was suggested by “Barrie” in one of the comments to my earlier post. If the remote website obtains an account at the visitor’s ISP (BT, Talk Talk or Virgin in the UK), then they can construct an advert request to the Phorm system, using the Phorm identifier of one of their visitors. By inspecting the advert they receive, they will learn what Phorm thinks will interest that visitor. They can then sell this information on, or serve up their own targeted advert. Essentially, they’re reverse engineering Phorm’s business model.

There are of course things that Phorm can do about these threats, by appropriate use of encryption and traffic analysis. Whether making an already complex system still more complex will assist in the transparency they say they are seeking is, in my view, problematic.

New Banking Code shifts more liability to customers

Banking security, Security economics

The latest edition of the Banking Code, the voluntary consumer-protection standard for UK banks, was released last week. The new code claims to “give customers the most up to date information on how to protect their accounts from fraud.” This sounds like a worthy cause, but closer inspection shows customers could be worse off than they were before.

Clause 12.11 of the code deals with liability for losses:

If you act fraudulently, you will be responsible for all losses on your account. If you act without reasonable care, and this causes losses, you may be responsible for them. (This may apply, for example, if you do not follow section 12.5 or 12.9 or you do not keep to your account’s terms and conditions.)

Clauses 12.5 and 12.9 include some debatable advice about anti-virus software and clicking on links in email (more on this in a later post). While malware and phishing emails are a serious fraud threat, it is unrealistic to suggest that home users’ computers can be adequately secured to defeat attacks.

Fraud-detection algorithms are more likely to be effective, since they can examine patterns of transactions over all customers. However, these can only be deployed by the banks themselves.

Existing phishing schemes would be defeated by two-factor authentication, but UK banks have been notoriously slow at rolling out these, despite being widespread in many other European countries. Although not perfect, these defences might cause fraudsters to move to easier targets. Two-channel and transaction authentication techniques additionally give protection against man in the middle attacks.

Until the banks are made liable for fraud, they have no incentive to make a proper assessment as to the effectiveness of these protection measures. The new banking code allows the banks to further dump the cost of their omission onto customers.

When the person responsible for securing a system is not liable for breaches, the system is likely to fail. This situation of misaligned incentives is common, and here we see a further example. There might be a short-term benefit to banks of shifting liability, as they can resist introducing further security mechanisms for a while. However, in the longer term, it could be that moves like this will degrade trust in the banking system, causing everyone to suffer.

The House of Lords Science and Technology committee recognized this problem of the banking industry and recommended a statutory change (8.17) whereby banks would be held liable for electronic fraud. The new Banking Code, by allowing banks to dump yet more costs on the customers, is a step in the wrong direction.

The Phorm “Webwise'' System

Legal issues, News coverage, Privacy technology

Last week I spent several hours at Phorm learning how their advertising system works — this is the system that is to be deployed by the UK’s largest ISPs to pick apart your web browsing activities to try and determine what interests you.

The idea is that advertisers can be more picky in who they serve adverts to… you’ll get travel ads if you’ve been looking to go to Pamplona for the running of the bulls, car adverts if you’ve been checking out the prices of Fords (the intent is that Phorm’s method of distilling down the ten most common words on the page will allow them to distinguish between a Fiesta and a Fiesta!)

I’ve now written up the extensive technical details that they provided (10 pages worth) which you can now download from my website.

Much of the information was already known, albeit perhaps not all minutiae. However, there were a number of new things that were disclosed.

Phorm explained the process by which an initial web request is redirected three times (using HTTP 307 responses) within their system so that they can inspect cookies to determine if the user has opted out of their system, so that they can set a unique identifier for the user (or collect it if it already exists), and finally to add a cookie that they forge to appear to come from someone else’s website. A number of very well-informed people on the UKCrypto mailing list have suggested that the last of these actions may be illegal under the Fraud Act 2006 and/or the Computer Misuse Act 1990.

Phorm also explained that they inspect a website’s “robots.txt” file to determine whether the website owner has specified that search engine “spiders” and other automated processing systems should not examine the site. This goes a little way towards obtaining the permission of the website owner for intercepting their traffic — however, in my view, failing to prohibit the GoogleBot from indexing your page is rather different from permitting your page contents to be snooped upon, so that Phorm can turn a profit from profiling your visitors.

Overall, I learnt nothing about the Phorm system that caused me to change my view that the system performs illegal interception as defined by s1 of the Regulation of Investigatory Powers Act 2000.

Phorm argue, with some justification, that their system does not permit them to identify individuals and that they meet and exceed all necessary Data Protection regulations — producing a system that is superior to other advertising platforms that profile Internet users.

Mayhap, but this is to mix up data protection and privacy.

The latter to me includes the important notion that other people, even people I’ll never meet and who will never meet me, don’t get to know what I do, they don’t get to learn what I’m interested in, and they don’t get to assume that targeting their advertisements will be welcomed.

If I spend my time checking out the details of a surprise visit to Spain, I don’t want the person I’m taking with me to glance at my laptop screen and see that its covered with travel adverts, mix up cause and effect, and think — even just for a moment — that it wasn’t my idea first!

Phorm says that of course I can opt out — and I will — but just because nothing bad happens to me doesn’t mean that the deploying the system is acceptable.

Phorm assumes that their system “anonymises” and therefore cannot possibly do anyone any harm; they assume that their processing is generic and so it cannot be interception; they assume that their business processes gives them the right to impersonate trusted websites and add tracking cookies under an assumed name; and they assume that if only people understood all the technical details they’d be happy.

Well now’s your chance to see all these technical details for yourself — I have, and I’m still not happy at all.

Update (2008-04-06):

Phorm have now quoted sections of this article on their own blog: http://blog.phorm.com/?p=12. Perhaps not surprisingly, they’ve quoted the paragraph that was favourable to their cause, and failed to mention all the paragraphs that followed that were sharply critical. They then fail, again how can one be surprised? to provide a link back to this article so that people can read it for themselves. Readers are left to draw their own conclusions.

Update (2008-04-07):

Phorm have now fixed a “tech glitch” (see comment #31) and now link to my technical report. The material they quote comes from this blog article, but they point out that they link to the ORG blog, and that links to this blog article. So that’s all right then!