J-PAKE published as an international standard

After attending ISO/IEC SC 27 WG2 for 4 years, I’m happy to say that J-PAKE is finally published in ISO/IEC 11770-4 (2017) as an international standard. In the mean time, J-PAKE is also published in RFC 8236 by IETF (together with an accompanying RFC 8235 on Schnorr non-interactive zero-knowledge proof). This is a milestone for J-PAKE. From the first presentation at Security Protocol Worksop ’08 in Cambridge to the publication in the international standard in 2017, J-PAKE has come a long way. The critical insight in the design of J-PAKE was based on understanding the importance of zero knowledge proof (ZKP), but this insight was not shared by other researchers in the field at the time. One main reason is that the use of ZKP was considered incompatible with the then-universally-adopted formal models in the PAKE field. However, in an independent study due to Abdalla, Benhamouda, MacKenzie and published in IEEE S&P 2015, the formal model for PAKE protocols was modified to make it compatible with ZKP, and the modified model was applied to prove J-PAKE was secure. The provable results are the same as in the original J-PAKE paper, but are constructed in a formal model, thus bridging the gap between theory and practice in the end.

Today, J-PAKE has already been used by many million users in commercial products, e.g., Palemoon Sync, Google Nest, ARM mbed OS, OpenSSL, Mozilla NSS, and Bouncycastle API. In particular, J-PAKE has been adopted by the Thread Group as a standard key exchange mechanism for the IoT commissioning process, i.e., adding new IoT devices to an existing network. The protocol has already been embedded into IoT products. The following video demonstrates how J-PAKE is used to securely enrol a new IoT device into the Thread network during the commissioning process (more details about Thread can be found at NXP, Thread Group, ARM, Silicon Labs and Google Nest’s Open Thread). It’s expected that in the near future, J-PAKE will be used by many billion Thread-compliant IoT devices for the initial bootstrapping of trust.

J-PAKE built into Google Nest thermostats

The J-PAKE key exchange protocol, designed by Prof Peter Ryan and myself in 2008, has been built into the Nest thermostat products (Nest was bought by Google in 2014 for US$3.2 billion). A technical white paper that describes the implementation has recently gone public (13 July, 2015).

Besides the Google Nest, J-PAKE has also been used in other commercial products. Since 2010, J-PAKE has been used by Mozilla Firefox to implement secure sync and deployed to over 400 million internet users. Recently, Mozilla Firefox starts to deploy a different mechanism (less secure but more usable than J-PAKE) for sync. However, the Palemoon browser, a popular fork of Firefox, retains the original J-PAKE based mechanism for preserving full security in protecting sync data (which contain sensitive user passwords). In the ISO/IEC SC 27 meeting held in Mexico City in October 2014, it was unanimously supported by national bodies in Work Group 2 to include J-PAKE into the ISO/IEC 11770-4 standard. The standardization of J-PAKE is currently in process and expects to finish in another two years.

The original J-PAKE paper was initially rejected by major conferences in the field, as the protocol design was based on a new method and didn’t follow any established approaches in the main stream at the time. The paper was eventually accepted and published by a small workshop (Security Protocols Workshop’08) held locally in Cambridge, UK in 2008. After 7 years of test by time, it is pleasing to see that the J-PAKE technique and its basic design ideas are being gradually accepted by the academic community and the industry.

Deleting secret data with public verifiability

In an upcoming paper (to be published by IEEE Transactions on Dependable and Secure Computing, 2015), we (with Dylan Clarke and Avelino Zorzo) investigate the secure data deletion problem. This problem concerns the guaranteed deletion of digital data using software means, which has been an active topic in recent years with quite a number of publications on major security conferences (Oakland, CCS, USENIX Security etc).

We observe that in all published solutions, the underlying data deletion system is (implicitly) assumed to be a trusted black-box. When the user instructs the system to delete data, she receives one bit in return: success or failure. The user has to trust the outcome, but cannot easily verify it. Demanding the deletion program to be open-source appears to be a solution, but it does not address the real problem since the actual code used in the run-time is opaque to the user. This is especially problematic when the software program is encapsulated within a tamper resistant hardware, and it’s impossible for users to access the internal code.

For those who work on electronic voting, the above problems should sound familiar. A black-box voting system works in exactly the same way. Take the standard Direct Electronic Voting (DRE) machine as an example. The DRE system records voters’ choices through a touch screen interface. At the end of the election day, the system announces the final tally, which voters have to trust but cannot easily verify. The source code is usually not publicly available as it may contain IPR. Even it were available, there is no guarantee that the software actually running in the DRE system is the same as the source code released in the public domain.

It’s exactly the above problems that promoted the thirty-year research on “verifiable e-voting”. Today, the importance of enabling public verifiability for an e-voting system has been widely accepted. Established solutions generally involve using cryptography to allow a voter to “trust-but-verify” a voting system rather than “completely-trust” it. The essence of those solutions is succinctly summarized by Ron Rivest as ”software independence”: namely, one should be able to verify the integrity of software by verifying the output of the software rather than its source code.

While the trust-but-verify principle has been universally adopted in the e-voting community, it has so far been almost entirely neglected in the field of secure data deletion. In this new paper, we initiated an investigation of applying the “trust-but-verify” principle to the data secure problem with a concrete solution, called Secure Storage and Erasure (SSE). The SSE protocol allows public verifiability on two important operations, namely encryption and deletion. More technical descriptions about the solution can be found in the paper (available in IACR ePrint).

It’s worth mentioning that we have implemented a fully functional prototype of the SSE on a resource-constrained Java Card. The source code is publicly available here. This implementation proved to be a non-trivial challenge as there was no precedent to follow. We were severely constrained by the (very limited) set of the APIs available to a Java card, and sometimes had to implement some primitive functions (such as modular multiplication) from scratch in pure software (without any support from the hardware co-processor). Kudos to Avelino Zorzo, who did the bulk of the implementation work during his sabbatical with us at the School of Computing Science in 2013, and also Dylan Clarke, who continued and completed the development work after Avelino left.

Password Authenticated Key Exchange in a Group

Today, we release a new paper entitled “The Fairy-Ring Dance: Password Authenticated Key Exchange in a Group“. This is joint work with Xun Yi (RMIT University), Liqun Chen (HP Labs) and Siamak Shahandashti (Newcastle University). The initial work started when Xun visited us at the School of Computing Science, Newcastle University in Feb, 2014. This is one of the collaborative research outcomes, which stem from that visit.

The subject of two-party Password Authenticated Key Exchange (PAKE) has been well studied for nearly three decades, however the topic of multi-party Group PAKE (GPAKE) has so far received little attention. Partly, this is because a Group PAKE is significantly more complex to design than a two-party PAKE due to more interactions between participants, hence exposing more potential attack vectors for an adversary to exploit.

We decided to investigate this subject as we believed Group PAKE protocols would become increasingly more important in the next 10 years – especially in the era of Internet of Things (IoT). Using a Group PAKE protocol can help set up a group of out-of-box IoT devices that have no pre-installed secrets or certificates; one just needs to enter a common (low-entropy) passcode into each of the devices. The protocol can then take over to ensure secure group communication among these IoT devices despite that all data is transmitted through an insecure Internet.

One major technical challenge here is to make the protocol as round efficient as possible. With Moore’s law, the computational efficiency can rapidly improve over time, but the round efficiency will stay more or less the same. Intuitively, when a group of entities engage in multiple rounds of interactions over a distributed network, the bottleneck of the overall latency will likely be determined by the slowest responder in each round. Hence, our strategy is to trade off computation for optimal round efficiency, with the aim to minimize the number of rounds as much as possible.

The paper (a free copy available at IACR ePrint) gives more technical details about how the above strategy is realized. I’ll present the paper at the ASIACCS Workshop on IoT Privacy, Trust, and Security (IoTPTS), in April 2015. It will be interesting to hear feedback from academic and industrial researchers working on IoT.

Before reading the paper, I would suggest the reader to watch the following “Fairy Ring Dance” from YouTube first, since the structural design of our solution shares some similarity to that dance.

Fairy Ring Dance (YouTube)


J-PAKE adopted by ISO/IEC standard

J-PAKE is a password-based authenticated key exchange protocol, developed by Peter Ryan and myself in 2008. Over the past six years, the protocol has withstood all sorts of attacks and has started to see some real-world use in providing end-to-end secure communication for Internet users. The full records of discussions on J-PAKE can be found in the previous lightbluetouchpaper blog.

About six months ago, in the ISO/IEC SC 27 meeting held at Hong Kong in April 2014, I gave a presentation on the rationale of including J-PAKE into the ISO/IEC 11770-4 standard. The presentation slides are available here. An accompanying document was officially circulated among the national bodies under ISO before the meeting. It was agreed in that meeting to start a six-month study period on Revision of ISO/IEC 11770-4 and invite all national bodies to comment my proposal.

This week, in its meeting held in Mexico City, October 20-24, 2014, ISO/IEC SC 27 Working Group 2 considered the contributions received under the study period. After some discussion, SC 27/WG 2 unanimously agreed that this standard should be revised to include J-PAKE.

In the same meeting, two security weaknesses of the existing SPEKE protocol in ISO/IEC 11770-4 were discussed based on the findings reported in our SSR’14 paper. (A copy of the paper is publicly available at IACR ePrint and the paper is discussed in a previous blog post.) After some discussion, it was agreed that the SPEKE specification in ISO/IEC 11770-4 should be revised to address the attacks reported in our SSR’14 paper. The revision work on ISO/IEC 11770-4 starts immediately with myself being one of the editors. We expect to provide the first working draft for comment by 15 Dec, 2014.

On a more lightweight subject, while in Mexico, I try to do as Mexicans do: i.e., drink a glass of cactus (mixed with celery, parsley, pineapple and orange) during the breakfast. It was such a horrible taste that I was unable to finish it the first time. However, the more I try it, the more I like it. Now I can’t have a breakfast without it. The way our body treats a new taste of drink reminds me of the way how our mind treats a new idea. A “new” idea usually has a bitter taste in it as it challenges our mind into accepting something different. The natural reaction is to reject it and remain satisfied where we are and what we already know. However, to appreciate the “sweetness” out of the initial “bitterness” of any new idea, it takes time and patience – and in fact, lots of patience. When I return to the UK, I am sure this will be the drink I miss most from Mexico. So, cheers one more time before my flight home tomorrow!

Cactus drink