All posts by Feng Hao

About Feng Hao

Feng Hao is currently a professor of security engineering in the Department of Computer Science, University of Warwick, UK. He graduated from the Computer Lab, University of Cambridge with a PhD in 2007 under the join supervision of Prof Ross Anderson and Prof John Daugman.

Owl, a new augmented password-authenticated key exchange protocol

Academic papers, Cryptology, Open-source security, Protocols

In 2008, I wrote a blog to introduce J-PAKE, a password-authenticated key exchange (PAKE) protocol (joint work with Peter Ryan). The goal of that blog was to invite public scrutiny of J-PAKE. Sixteen years later, I am pleased to say that no attacks on J-PAKE have been found and that the protocol has been used in many real-world applications, e.g., Google Nest, ARM Mbed, Amazon Fire stick, Palemoon sync and Thread products.  

J-PAKE is a balanced PAKE, meaning that both sides must hold the same secret for mutual authentication. In the example of the J-PAKE-based IoT commissioning process (part of the Thread standard), a random password is generated to authenticate the key exchange process and is discarded afterwards. However, in some cases, it is desirable to store the password. For example, in a client-server application, the user knows a password, while the server stores a one-way transformation of the password. 

PAKE protocols designed for the above client-server setting are called augmented (as opposed to the balanced in the peer-to-peer setting). So far the only augmented PAKE protocol that has enjoyed wide use is SRP-6a, e.g., used in Apple’s iCloud, 1Password and Proton mail. SRP-6a Is the latest version of the 1998 SRP-3 scheme due to Wu after several revisions to address attacks. Limitations of SRP-6a are well known, including heuristic security, a lack of efficiency (due to the mandated use of a safe prime as the modulus) and no support for elliptic curve implementation. 

In 2018, an augmented PAKE scheme called OPAQUE was proposed by Jarecki, Krawczyk and Xu. In 2020, IETF selected OPAQUE as a candidate for standardization. A theoretical advantage promoted in favour of OPAQUE is the so-called pre-computation security. When the server is compromised, an offline dictionary attack to uncover the plaintext password is possible for both OPAQUE and SRP-6a. For OPAQUE, its pre-computation security means that the attacker can’t use a pre-computed table, whilst for SRP-6a, the attacker may use a pre-computed table, but it must be a unique table for each user, which requires a large amount of computation and storage. Therefore, the practical advantage provided by pre-computation security is limited. 

Apart from pre-computation security, OPAQUE has a few open issues which leave it unclear whether it will replace SRP-6a in practice. First, the original OPAQUE protocol defined in the 2018 paper leaks password update information to passive attackers, whilst SRP-6a doesn’t have this leakage. Furthermore, OPAQUE relies on a constant-time hash-to-curve function available for all elliptic curves, but details about the instantiation of this function remain to be established. Finally, the 2018 paper didn’t give a full specification of OPAQUE. In 2020, when OPAQUE was selected by IETF, its specification remained incomplete. The task of completing the spec was left as a post-selection exercise; today, it is still not finished.  

Motivated by the recognised limitations of SRP-6a and OPAQUE, we propose a new augmented PAKE scheme called Owl (joint work with Samiran Bag, Liqun Chen and Paul van Oorschot). Owl is obtained by efficiently adapting J-PAKE to an augmented setting, providing the augmented security against server compromise with yet lower computation than J-PAKE. To the best of our knowledge, Owl is the first augmented PAKE solution that provides systematic advantages over SRP-6a in terms of security, computation, round efficiency, message sizes, and cryptographic agility. 

On 5 March 2024, I gave a presentation on Owl at Financial Cryptography and Data Security 2024 (FC’24) in Curacao. The purpose of this blog is to invite public scrunity of Owl. See the Owl paper and the FC slides for further details. An open-source Java program that shows how Owl works in an elliptic curve setting is freely available. We hope security researchers and developers will find Owl useful, especially in password-based client-server settings where a PKI is unavailable (hence TLS doesn’t apply). Same as J-PAKE, Owl is not patented and is free to use.

New attacks on HMQV

Academic papers, Cryptology, Protocols

Many people may still remember the debates a few years ago about the HMQV protocol, a modification of MQV with the primary aim of provable security. Various attacks were later discovered for the original HMQV. In the subsequent submission to the IEEE P1363 standards, the HMQV protocol has been revised to address the reported weaknesses.

However, the revised HMQV protocol is still vulnerable. In a paper that I presented at Financial Cryptography ’10, I described two new attacks. The first presents a counterexample to invalidate the basic authentication feature in the protocol. The second is generally applicable to other key exchange protocols, despite that many have formal security proofs.

The first attack is particularly concerning since the formal security proofs failed to detect this basic flaw. The HMQV protocol explicitly specifies that the Certificate Authority (CA) does not need to validate the public key except checking it is not zero. (This is one reason why HMQV claims to be more efficient than MQV). So, the protocol allows the CA to certify a small subgroup element as the user’s “public key”. Then, anyone who knows this “public key” can successfully pass authentication using HMQV (see the paper for details). Note, in this case, a private key doesn’t exit, but the authentication is successful. What is the “authentication” in HMQV based on?

The HMQV author acknowledges this attack, but states it has no bad effects. Although I disagree, this will be up to the reader to decide.

Updates:

  • 2010-03-11: Full version of the paper available here
  • 2010-04-04: My comments on Tang’s paper.

How to vote anonymously under ubiquitous surveillance

Academic papers, Cryptology, Electronic voting, Privacy technology, Security engineering

In 2006, the Chancellor proposed to invade an enemy planet, but his motion was anonymously vetoed. Three years on, he still cannot find out who did it.

This time, the Chancellor is seeking re-election in the Galactic Senate. Some delegates don’t want to vote for him, but worry about his revenge. How to arrange an election such that the voter’s privacy will be best protected?

The environment is extremely adverse. Surveillance is everywhere. Anything you say will be recorded and traceable to you. All communication is essentially public. In addition, you have no one to trust but yourself.

It may seem mind-boggling that this problem is solvable in the first place. With cryptography, anything is possible. In a forthcoming paper to be published by IET Information Security, we (joint work with Peter Ryan and Piotr Zielinski) described a decentralized voting protocol called “Open Vote Network”.

In the Open Vote Network protocol, all communication data is open, and publicly verifiable. The protocol provides the maximum protection of the voter’s privacy; only a full collusion can break the privacy. In addition, the protocol is exceptionally efficient. It compares favorably to past solutions in terms of the round efficiency, computation load and bandwidth usage, and has been close to the best possible in each of these aspects.

With the same security properties, it seems unlikely to have a decentralized voting scheme that is significantly more efficient than ours. However, in cryptography, nothing is ever optimal, so we keep this question open.

A preprint of the paper is available here, and the slides here.

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.

Kish's "totally secure" system is insecure

Hardware & signals

Recently, Kish proposed a “totally secure communication system” that uses only resistors, wires and Johnson noise. His paper—“Totally Secure Classical Communication Utilizing Johnson (-like) Noise and Kirchoff’s Law”—was published on Physics Letters (March 2006).

The above paper had been featured in Science magazine (Vol. 309), reported in News articles (Wired news, Physorg.com) and discussed in several weblogs (Schneier on security, Slashdot). The initial sensation created was that Quantum communication could now be replaced by a much cheaper means. But not quite so …

This paper—to appear in IEE Information Security—shows that the design of Kish’s system is fundamentally flawed. The theoretical model, which underpins Kish’s system, implicitly assumes thermal equilibrium throughout the communication channel. This assumption, however, is invalid in real communication systems.

Kish used a single symbol ‘T’ to denote the channel temperature throughout his analysis. This, however, disregards the fact that any real communication system has to span a distance and endure different conditions. A slight temperature difference between the two communicating ends will lead to security failure—allowing an eavesdropper to uncover the secret bits easily (more details are in the paper).

As a countermeasure, it might be possible to adjust the temperature difference at two ends to be as small as possible—for example, by using external thermal noise generators. However, this gives no security guarantee. Instead of requiring a fast computer, an eavesdropper now merely needs a voltage meter that is more accurate than the equipments used by Alice and Bob.

In addition, the transmission line must maintain the same temperature (and noise bandwidth) as the two ends to ensure “thermal equilibrium”, which is clearly impossible. Kish avoids this problem by assuming zero resistance on the transmission line in his paper. Since the problem with the finite resistance on the transmission line had been reported before, I will not discuss it further here.

To sum up, the mistake in Kish’s paper is that the author wrongly grafted assumptions from one subject into another. In circuit analysis, it is common practice to assume the same room temperate and ignore wire resistance in order to simplify the calculation; the resultant discrepancy is usually well within the tolerable range. However, the design of a secure communication is very different, as a tiny discrepancy could severely compromise the system security. Basing security upon invalid assumptions is a fundamental flaw in the design of Kish’s system.

AV-net – a new solution to the Dining Cryptographers Problem

Privacy technology

Last week in the 14th International Workshop on Security Protocols, I presented a talk on the paper: A 2-round Anonymous Veto Protocol (joint work with Piotr Zieliński), which interested some people. The talk was about solving the following crypto puzzle.

In a room where all discussions are public, the Galactic Security Council must decide whether to invade an enemy planet. One delegate wishes to veto the measure, but worries about sanctions from the pro-war faction. This presents a dilemma: how can one anonymously veto the decision?

This veto problem is essentially the same as the Dining Cryptographers Problem first proposed by Chaum in 1988 — how to compute the Boolean-OR securely. However, Chaum’s classic solution, DC-net, assumes unconditionally secure private channels among participants, which don’t exist in our problem setting. Our protocol, Anonymous Veto Network (or AV-net), not only overcomes all the major limitations in DC-net, but also is very efficient in many aspects (probably optimal).