Subject: [Cfrg] Review of PAKE protocols (for Magic-Wormhole)

From: Brian Warner <[email-masked]>
Date: Sun, 15 Sep 2019 22:58:54 -0700

I was asked to review the balanced PAKE proposals, with an eye towards
their suitability for my "Magic Wormhole" application. Here is my
report.

First, some background on my use case. Magic Wormhole
(http://magic-wormhole.io) is a PAKE-based provisioning library and
file-transfer application. As a library, it helps two humans introduce
their computers to each other securely, for example to exchange
long-term public keys for a private chat application (think Signal or
Wire), or to provision a mobile client for some service from an existing
desktop client. As an application, it provides a command-line tool for
sending a file, directory, or short message, by having the sender
dictate a random single-use "wormhole code" like "4-purple-sausages" to
the receiver. The sending human runs "wormhole send FILENAME" which
prints out the code, and the receiving human runs "wormhole receive" and
types in the code. The numeric part of the code is used to access a
"mailbox" on a shared central server, and the words are used as the PAKE
secret. The PAKE messages are pushed to the mailbox, where they can be
read by the other side to continue the protocol. My implementation uses
SPAKE2 over an Ed25519 group to derive a secret shared session key, and
then encrypts everything else under that key. Small messages are
encrypted and sent through the mailbox server. For large transfers, the
two sides use the mailbox channel to negotiate a direct TCP connection,
and derive a separate key to protect that connection.

This leverages an existing low-bandwidth short-term secure-enough
channel between the two humans, such as two people standing next to each
other, or talking on the phone. They might have a secure high-bandwidth
channel already, but one that is ill-suited for transferring files (I
constantly wormhole files from the other end of an ssh connection,
because it's easier than remembering and re-typing whatever directory
I'm using into a new "scp" command). Or they might have a channel that
isn't exactly secure (SMS, IRC, twitter direct messages) but the
attacker's temporal window is narrow.

Magic-Wormhole was inspired by my work at Mozilla on Firefox Sync in
2010, for which I was the proponent of using J-PAKE in a similar scheme
to transfer one browser's local-data encryption key to a new browser.
Sync encrypts all bookmarks, open tabs, history, and password manager
entries with this local key before uploading the ciphertext, so the
Mozilla servers cannot read this data, and we used a randomly-generated
transfer code to get this key from one machine to another when the user
attaches a new browser to their account. J-PAKE was the first PAKE I had
ever heard about. After we implemented the system, I had an opportunity
to speak with Dan Boneh, who recommended SPAKE2 (known as "PAKE2" in his
https://toc.cryptobook.us/) over J-PAKE, hence its use in
Magic-Wormhole.

In 2014, I built the protocol which replaced PAKE in Firefox Sync. I
presented our reasons for abandoning PAKE at Real World Cryptography
2014, with details at http://www.lothar.com/presentations/fxa-rwc2014/ ,
but in short we failed to provide an adequate user experience for a
purely transfer-based protection mechanism: users wanted to recover
their data with a password, even after their last browser key had been
lost, and our approach could not make that easy.

## Review Criteria

I'm not a cryptographer, and I'm not qualified to evaluate proofs of the
various candidate algorithms. My review criteria are related to how well
the protocols fit the needs of my application, and how well I think I
(or some other self-taught cryptographic engineer) could implement them
safely. In particular, my goals are:

* minimize round trips
* avoid "sidedness" which requires symmetry-breaking additions
* minimize complexity for the implementor
* maximize concreteness of the specification

All applications want to reduce roundtrips. For Magic-Wormhole, the
worst case is to be deployed as a secure-messaging introduction step
between a pair of laptops or mobile phones, that spend most of their
lives asleep. The clients will get network connectivity only briefly,
while the phone application is running, or when the laptop is open. The
two clients may never be online at the same time, so each time the app
is activated, it might only be able to fetch one message, and submit one
new message. The number of roundtrips the PAKE protocol requires tells
you the number of wake-up-the-laptop cycles it takes to compete the
introduction. For two users in different timezones who only open the app
during lunchtime, each roundtrip could take a full day.

Magic-Wormhole has an "offline codes" mode, in which the two humans meet
without their computers, and decide upon a secret code manually (perhaps
by rolling dice, or counting passing birds, or something). Then they
return to their computers, and each type in the shared code. We don't
know which person will type in their code first, and a symmetric
application protocol (like populating address books in a messaging
program) doesn't give us any automatic way to distinguish one side from
the other. So a PAKE protocol with "sides" (like SPAKE2, or any
augmented PAKE) is slightly awkward. We need some other mechanism to
break the symmetry: an exchange of random numbers (higher number plays
Alice, lower number plays Bob). This either costs an extra roundtrip, or
requires both parties run two copies of the protocol in parallel, and
throw one of them out after they learn which role they should play
(https://github.com/warner/magic-wormhole/issues/348, 3rd comment).

Lacking a well-specified off-the-shelf library in my preferred language,
I had to implement it myself. Minimal complexity helped. I could
tolerate a more complex protocol if someone else writes the
implementation (at Mozilla we had Brian Smith to write our J-PAKE code;
I would have been lost trying to write that myself, and even he missed
some important checks the first time through).

While writing the Python SPAKE2 implementation, I lacked a byte-level
specification to match. This was terrifying. There are plenty of options
that must be settled (choice of curve, point representation, transcript
representation, transcript hash). Most aren't significant for security,
but are vital for compatibility, and I did not know which of my casual
"works for me" choices would become difficult, annoying, or embarrassing
in an actual spec. There are now four somewhat-compatible
implementations (Python, Rust, Go, and Haskell), and each had to match
my perhaps-idiosyncratic choices. The string-to-(unknown-dlog)-point
function was the worst.

My non-goals are:

* augmentation or password-stretching
* identity binding
* timing-channel resistance
* message size, within reason, or super high performance
* well-defined key-confirmation messages

Unlike passwords, the "wormhole codes" we use are randomly-generated and
single-use. The distribution of possible codes is uniform. An attacker
who successfully managed to guess a single code early enough could
intercept the data transferred during that one operation (via an active
MitM attack), but that gives them no advantage over the next transfer.
The wormhole code is used as the PAKE password, but it is not stored
anywhere, and is discarded as soon as the session key is generated.
Consequently I have no need for an Augmented PAKE, and in fact the
additional setup step these require would make my protocol completely
unworkable. And since the code/password is not stored anywhere, I do not
need a mechanism to slow down online guessing attacks, or to protect
against "server" compromise by storing something other than the
password.

Magic-Wormhole has no notion of "identity": each instance of the
protocol is driven by two humans introducing their computers to each
other. The wormhole code is the only identifier: Computer A generates
it, the humans transcribe it, and Computer B accepts it. Computer A only
knows about the human that reads the codes it displays. Computer B only
knows about the human who controls the keyboard over which codes are
entered. So the protocol has no need for features which bind a server
name, or account name, into the generated key.

Constant time operation is always better, but I think Magic-Wormhole is
less threatened by timing attacks than other protocols which might use
long-lived passwords. Each client performs the PAKE computations just
once for any particular wormhole code, and many of those computations
take place before any messages are sent, limiting an attackers potential
observations. My current implementation uses a pure-python Ed25519
library, which is not constant-time at all.

Magic-Wormhole protocol messages are delivered over WebSockets to the
mailbox server, which enables more portability (to different languages,
operating systems, and potentially even web-browser -based clients). As
a result, we are not particularly sensitive to the size of the messages,
and they certainly don't need to fit in a single ethernet frame. I very
much prefer ECC groups over integer/MODP ones, but the protocol would
not suffer terrible inefficiencies even if the messages were several
kilobytes in length. The protocol assumes human interaction (and it
wouldn't make much sense to automate it: if you have two computers that
can securely exchange the wormhole code, then you already have a secure
channel for everything else). So the rate of execution is limited to
human conversation speeds.

Most of the CPU time spent in the PAKE operations is on the "long pole"
of user experience, so keeping it reasonable is helpful. However the
majority of the time is spent waiting for a human to transcribe a
wormhole code, and connections are initiated by humans, not machine, so
100ms or even 500ms might not be a problem. The PAKE operations are only
computed on the two client machines (the server relays the messages but
does not interpret or generate them), so there is no
multiplication/bottleneck factor to worry about.

Many PAKE use-cases are about proving control over an account to
authorize some action (i.e. establish a TLS connection, then run PAKE
inside it to demonstrate knowledge of a password, creating a login
protocol that's better than plaintext-password-inside-TLS but still
vulnerable to CA compromise). Magic-Wormhole starts with PAKE and
creates the connection from that. Consequently, "key verification" is
expressed by using the PAKE-derived session key as a transport
encryption key (AEAD or just AE) for the subsequent tunnel. The receipt
of the first message inside this tunnel is the indication that PAKE
succeeded, and the failure of a MAC on the AE cipher is indication that
it failed (or an attacker has injected a message into the transport
layer, which is another kind of failure).

So my protocol doesn't have much use for a specification of how
key-verification steps should work (i.e. "send H(H(key)) in one
direction, wait for it to arrive, then send H(key) back"). These steps
assume that the success of the PAKE exchange is interesting by itself,
whereas I believe the correct thing to care about is the session key
alone, and its binding to subsequent messages. Learning that PAKE
succeeded without actually using the session key is like learning the
user's plaintext password was correct without binding it to the channel.
An attacker who uses a fake/compromised CA certificate to fool the end
user into connecting to the attacker, rather than the real server, can
run an MitM attack (sitting in between the user's TLS connection to the
attacker, and a separate TLS connection from the attacker to the
server), forward the PAKE handshake until completion, then drop the
user's connection and impersonate them to the server. This is the same
problem as sending plaintext passwords over TLS, except the attacker
doesn't learn the password to make it easier to impersonate them again
in the future.

## Minimizing roundtrips

J-PAKE and CPace require two pairs of messages to be exchanged before a
shared key is available. In contrast, SPAKE2 and SPEKE need only one.

In the worst-case never-simultaneous execution scenario described
earlier, with SPAKE2 and SPEKE, Magic-Wormhole would require five
activations to get one secure message from A to B and from B to A with
acks of both (i.e. Alice runs, then Bob, then Alice, then Bob, then
Alice). For J-PAKE and CPace, this would require seven activations.

This depends upon what exactly is used as a UserID, how the symmetry is
broken (see below), and whether key confirmation is verified before
sending a payload. But in general, the extra commitments of J-PAKE and
the session ID agreement of CPace induce an extra pair of messages.
While this non-simultaneous scenario might not be the most common, I'd
still prefer a protocol that needs fewer roundtrips.

Good: SPAKE2, SPEKE
Bad: J-PAKE, CPace

## Avoiding asymmetry

SPAKE2 was the second PAKE function I ever learned about. I decided to
use a symmetric form of it, in which the two blinding factors are set
equal to each other, which I'm told is probably safe but would prefer to
replace with something proven. As described above, I know how to work
around this without incurring an extra roundtrip, but it'd be better if
I didn't have to.

J-PAKE includes a UserID in the NIZKs, and RFC8236 says the verifier
shall check that it differs from their own identity (presumably to
defend against reflection). To achieve my symmetry goals, I would want
these UserIDs to be constant for all users (removing that check), and I
don't know if this breaks the security properties.

SPEKE, as described in "SPEKE Protocol Revisited" paper, appears to
value symmetry in the way needed for Magic-Wormhole. However it is not
clear to me what exactly would be included in a specification based on
the recommendations therein. The "alternative solution" in section
5.3(2), namely s=H(pw+Min(idA,idB)+Min(idA,idB)), would be ideal, as my
protocol could simply leave idA/idB empty. I don't see anything that
suggests SPEKE implementations would have to explicitly check user IDs,
which sounds good for Magic-Wormhole.

The CPace "ssid agreement step" is defined as hashing 's' and 't' in a
particular order that implies an asymmetry, but I believe this could be
replaced by sorting the two contributions without affecting security. If
that is true, perhaps the spec could be updated to remove an unnecessary
asymmetry.

CPace is defined with UserIDs that are folded into the ephemeral
generator (figure 5, g' = H1(sid+Pi+Pj+pw). Again, these would need to
both be empty or the same constant value, to obtain the symmetry I'm
looking for. I don't see any protocol steps that require checking for
distinct identities.

Good: SPEKE, maybe CPace
Maybe Bad: J-PAKE
Bad: SPAKE2

## Minimzing Complexity, Maximizing Concreteness

To this amateur implementor, SPAKE2 is the simplest of the candidates
(assuming ECC rather than MODP). It took me a while to get code that
performs both scalar multiplication and point addition in the Ed25519
group (starting from djb's papers and the code in NaCl), but everything
else about SPAKE2 is straightforward (to me).

SPEKE is similar, assuming a well-defined hash-to-curve rule. I could
probably implement it. I know this is the nature of cryptographic papers
(as opposed to proper specifications), but it felt like the SPEKE papers
were more of a collection of good ideas, rather than instructions for
building a protocol. I have to imagine specification that might result
from following those recommendations, and hope that this hypothetical
complete spec might include things like ECC and hashing a full
transcript of the conversation. SPEKE was written a while ago, when
perhaps protocols were more casual about mixing scalars and group
elements (something that always bothered me about SRP), specifically in
the password-to-generator function. Having a clearer distinction between
scalars and elements in the SPAKE2 definitions made it easier for me to
understand.

CPace feels very much like what SPEKE would be in an ECC group, except
with the extra pass to agree on a session ID. Again, assuming
hash-to-curve being specified, I could imagine implementing it.

J-PAKE feels like the most complex of the candidates. Each message must
include zero-knowledge proofs along with the normal DH parameters. As an
amateur implementor, this is a level of complexity I would rather avoid.
I think I understand the basic group math involved in all the other
protocols (SPAKE2 is just DH with blinding applied to the ephemeral
keys, SPEKE is DH with a secret generator derived from the password, and
CPace is the same but with a roundtrip to salt the password with a fresh
session ID). But J-PAKE's multiple scalars don't map to my understanding
of DH, and the correctness of a ZKP construction is slightly beyond me,
so I'd feel far more comfortable implementing one of the others. That
said, if someone else is writing the code, I could tolerate more
complexity.

Most of these protocols (but not J-PAKE) require a function to convert a
string (the password, plus maybe other stuff) into a group element for
which nobody knows the discrete log. SPAKE2 uses it for the shared
blinding factors, CPace needs it each time to build the secret shared
generator, and SPEKE would need one if it were defined over a
non-integer group. This requires some extra specification, and
frequently gets left up to the implementor, resuting in
incompatibilities. I'm hopeful that the final specification will define
this function clearly so implementations will be compatible.

SPAKE2 only needs this function to be run once, during the specification
process. When I implemented SPAKE2 in python for magic-wormhole, I
picked an approach that seemed natural, but subsequent implementations
by other people (e.g. the SPAKE2 patch for SJCL) chose other approaches
that were not compatible. However if my approach was sound, those other
implementations could simply copy the value directly rather than
re-implementing the full function. The appearance of a large magic
number in a protocol implementation is not very satisfying, nor in a
protocol specification document, and both ask the reader to manually
verify that the number was generated in the claimed way.

Good (complexity): SPAKE2, SPEKE, CPace
Bad: J-PAKE

Good (string-to-point): J-PAKE
Somewhat Bad: SPAKE2
Bad: SPEKE (ECC), CPace

## Conclusions

It's a mixed bag. For Magic-Wormhole, I still prefer SPAKE2. I can
imagine an ECC-based SPEKE specification that could work. I'm reluctant
to take on the extra roundtrips of J-PAKE or CPace, or the NIZK
complexity of J-PAKE, but if someone convinced me that they were more
secure (and published test vectors for the ZK proofs), I could imagine
implementing them.

My ideal construction would probably be "SPAKE2 Elligator Edition", in
which the blinding factor is just the Elligator2 mapping of the
password. This would be symmetric, one-round-trip, and pretty simple (of
course by pushing the complexity into somebody else's Elligator
implementation). It's conceivable that one of the candidates, when
implemented over an Elligator-capable curve, could look like this.

I hope my use case helps the group with the selection process. My
apologies if I've misunderstood any of the candidates or was unfair in
my assessment. Please let me know if I've committed such errors and I'll
endeavor to update my review.

cheers,
 -Brian

---

From: "Hao, Feng" <[email-masked]>
Date: Mon, 16 Sep 2019 12:51:06 +0000

Hi Brian,

Thanks for your reviews and useful feedback on the practical requirements. I have two comments below.  

[FH] If you set the two blinding factors equal (M=N), that will effectively turn it into a different protocol, which is very similar to Kobara-Imai's Pretty-Simple Password-Authenticated Key Exchange at https://eprint.iacr.org/2003/038.

Both protocols rely on a trusted setup, but the main difference is below:
 * In SPAKE2: the protocol uses three generators, g, M, N. It's assumed that the discrete logarithm between any of these two must be unknow.
 * In Kobara-Imai, the protocol uses two generators, and it's assumed the DL between these two must be unknown.
   
I don't know if anyone has studied whether the proofs in SPAKE2 are still applicable when only two random generators are used. The use of 2 generators is certainly simpler than 3.

[FH] In J-PAKE, the identities are used as the basis for each communicating party to retrieve the shared password. Hence, a party can use an arbitrary identity as long as when the two parties engage in a PAKE session, they know which shared password to retrieve from their respective databases. This should be the same for all PAKEs. I don't think you can remove the check that the two identities in a session should be different (which is a natural thing to check, and necessary to prevent the ZKP being replayed back to the sender).

---

From: Brian Warner <[email-masked]>
Date: Tue, 17 Sep 2019 09:42:29 -0700

> [FH] If you set the two blinding factors equal (M=N), that will effectively turn it into a different protocol, which is very similar to Kobara-Imai's Pretty-Simple Password-Authenticated Key Exchan…

Thank you! I've been looking for literature about the M==N case without
success. I'll read that paper.

In my SPAKE2 variant, I include a check that the inbound message is not
the same as the outbound message, but I'm not sure how effective that is
at preventing the reflection attack (i.e. I compare bytes, but maybe the
attacker could transform the outbound message into a different
representation of the same point, which would pass the check but still
result in one side unknowingly talking to themselves).

> [FH] In J-PAKE, the identities are used as the basis for each communicating party to retrieve the shared password. Hence, a party can use an arbitrary identity as long as when the two parties engag…

Got it. So I think for J-PAKE (and several of the others), I *must* find
a way to agree upon (different) identities ahead of time. The identities
could be random and ephemeral, but they must be different.

I will take a another look at each candidate and see if the peer's
identity must be known before the first outgoing message is generated.
If not, Magic-Wormhole could just use random ones without incurring an
extra roundtrip.

For SPAKE2, I could even imagine setting M=hash_to_point(randomIdA) and
N=hash_to_point(randomIdB), using new values for each session, and just
including the ID in the first message. I think that would get me back to
the original protocol, without adding a roundtrip, at the cost of
requiring the hash_to_point() function at runtime.

thanks,
 -Brian