SPAKE2 "random" elements

SPAKE2 requires two special "arbitrary" constants M and N. What properties do these constants really need? What attacks are possible if these requirements are not met?

SPAKE2, like all PAKE ("Password-Authenticated Key Exchange") protocols, allows two people start with a weak password and then agree upon a strong shared key, despite active attackers getting in the way. There are a variety of protocols in this family: SRP is probably the most well-known (but has the weakest security proofs), and J-PAKE is the one we used in the original Firefox Sync. But SPAKE2 is my current favorite: it's simpler, faster, and has a better security reduction.

How SPAKE2 works

Assume the following notation: we have some group with generator (base element) B, we use additive notation (so B*x instead of g^x), lower-case letters are scalars, upper-case letters are elements, and * represents scalar multiplication.

Now the basic exchange looks like this:

one-time setup:

• choose M and N as random group elements

the protocol:

• Alice knows pw1, Bob knows pw2, hopefully they are the same
• Alice chooses random secret scalar x, sends X = B*x + M*pw1
• Bob chooses random secret scalar y, sends Y = B*y + N*pw2
• Alice computes Z1 = (Y-N*pw1)*x, then K1 = hash(X,Y,Z1,pw1)
• Bob computes Z2 = (X-M*pw2)*y, then K2 = hash(X,Y,Z2,pw2)

The promise of PAKE is that K1 and K2 will be the same if and only if the pw1/pw2 passwords were the same. If they were different, then the keys are completely unrelated. For SPAKE2, this property stems from Z1 and Z2. That N*pw1 is a "blinding factor": it obscures the Diffie-Hellman B*y element in transit. Alice unblinds the element before using it to compute Z1.

This means a passive attacker has no hope of figuring out the shared key: from their point of view, all keys are equally likely, as are all passwords.

An active attacker only gets one guess (or maybe two, depending upon how you count). They make this guess by pretending to be Bob and running the protocol as normal. If their pw2 guess was right, they'll get the same key as Alice, and they win: they know the password and the key. Then they turn around and pretend to be Alice, using the successfully-guessed password in a protocol run with Bob, which should succeed (with a different key). Now that they know both session keys, they can MitM the Alice-Bob connection like they would with traditional unauthenticated Diffie-Hellman.

If their guess was wrong, the session keys are independent and unrelated, and they won't be able to talk with Alice (or Bob) at all. For each time that Alice or Bob is willing to run the protocol, they get another guess.

(incidentally, both sides usually include some sort of identity string in their transcript hashes, so an attacker can't splice together unrelated sessions: Alice runs this protocol with a specific intent to construct a session key for server "foo.com", and can't be confused by a response that was replayed from an earlier session with "bar.com". K1 = hash(idA,idB,X,Y,Z1,pw1))

Where do M and N come from?

The original paper describes M simply as "an element in G associated with user A". A different paper (Boneh) describes M and N as "randomly chosen elements of G". While it's probably obvious to an experienced student of cryptography (which I am not), it turns out that what really matters is that nobody knows the discrete log of M and N. That is to say, nobody knows a scalar m for which M = B*m, and likewise for N.

If you don't realize this, and you're struggling to figure out how groups work anyway, you'd probably make the same mistake that I did, and construct M by choosing an arbitrary scalar (just a large number, modulo the group order |G|), and scalar-multiply it by the base point. My first implementation used 11*B and 12*B, which seemed sufficiently arbitrary to me :-). When I showed it to Mike Hamburg, he kindly pointed out the necessary properties of M and N, and I eventually figured things out. You can't start with a scalar and multiply your way to an element: you must somehow start with an element.

The traditional way to prove that nobody knows the scalar is to hash some simple string (with limited wiggle room) and somehow convert the hashed output into an element. Popular strings include pi, e, sin/cos functions, and the names of the parameters themselves. The nominal argument is that you'd have to tamper with the fundamental constants of the universe to have enough control over the output to steer it towards an element for which you already knew the discrete log.

It turns out to be much easier to choose an arbitrary element in an integer group, like Zp*: you treat the hash output as a random member of 0..p-1, then just raise it to (p-1)/q (since q is the order of the subgroup, (p-1)/q is the "cofactor"). The result will be in the right group and will be just as uniformly distributed as the hash output itself. There's an example here.

For elliptic curves, you must turn the hash output into an x (or y) coordinate, recover the other coordinate (giving you a point on the right curve, but not necessarily in the right group), then either check the group order or just multiply (known as "clearing the cofactor"). Here is the function which does this in my python-spake2 implementation.

Why must M and N be random?

A thing that puzzled me up until now was why, exactly, it was so important that nobody knows the discrete logs for these constants. I knew there was some sort of attack possible, but I couldn't figure out the details. Mike Hamburg pointed me in the right direction in his discussion of "SPAKE2 - Elligator Edition" on the moderncrypto.org curves mailing list. But I didn't work out the attack until just recently.

Here's the deal: if Mallory (our active attacker) can pretend to be Bob for the duration of the protocol, then later she can mount an offline dictionary attack against the password that Alice used. In particular, Mallory can construct a function that converts a potential password into a potential session key, and this function can be run without further interaction with Alice and Bob. As long as she has some way to check whether a potential session key is correct or not, she can feed a list of common passwords into the function and quickly identify which one (if any) was correct. This violates PAKE's promise of security: an active attacker is supposed to be limited to just one online guess.

Mallory almost certainly has a way to observe some use of the session key, which will give her a way to test her guesses. Maybe Alice immediately sends a key-confirmation message (a simple hash of the key) so Bob can tell whether the PAKE succeeded or not: then Mallory just hashes the potential key and sees if it matches the confirmation message. Or if Alice uses the key for authenticated encryption, and Mallory gets to see the ciphertext, then trial decryption of that message lets her test each guess. Because this test is offline, the attacker can test guesses of K1 as frequently as she likes.

The math looks like this. Suppose that the attacker knows that N = B*n (n being the discrete log of the no-longer-arbitrary point N).

Now, when our attacker Mallory pretends to be Bob, she picks a random y and sends Y = B*y, omitting the password and blinding factor N entirely. Mallory receives X = B*x + M*pw1 from Alice. Note that B*x = X - M*pw1.

Alice will then compute Z1 = (Y-N*pw1)*x, which is really (Y-B*n*pw1)*x, which is really (B*y-B*n*pw1)*x, which (since scalar multiplication is associative) is really (y-n*pw1)*B*x, which means Z1=(y-n*pw1)*(X-M*pw1).

Note that every term in that final equation is known to Mallory except the password pw1: she picked y herself, n is the discrete log of N, and X was given to her by Alice. Mallory has all the time in the world to try various values of pw1, compute a potential Z1, and test the resulting session key K1 until she finds the right password.

This only works if Mallory can factor out the B*something in Alice's Z1 computation, which is why she needs the discrete log of N to pull it off.

Of course, if N were chosen safely, but M's discrete log were known, then Mallory would pretend to be Alice instead of Bob. Hamburg pointed out that if you can constrain the order of the messages, and have Alice prove herself to Bob first, then it's safe to drop one of the blinding factors entirely (send B*x instead of B*x + N*pw). But if the protocol isn't constrained this way, you must have both.

Weaker things

M and N might not be completely independent, but still nobody knows the discrete log of them. For example, maybe:

• we know that N is some constant times M (hence n is some constant k plus m)
• we know that N == M (e.g. k=0)

I don't think these result in attacks, but I'm still looking for papers to prove it. I'm told that the 2003 Kobara/Imai paper proves this, and Mike told me that M==N yields a proof that reduces to the CDH-Squared problem instead of the usual CDH (Computational Diffie-Hellman) problem, but that they're basically the same thing.

I especially want M==N to work because that makes the message flows in magic-wormhole easier. If M and N are distinct, then the two sides need to agree (ahead of time) which role they're going to play. If M==N then the protocol is much more symmetric, and the humans constructing offline wormhole codes don't need to choose sides as well.

I use the M==N form in python-spake2's SPAKE2_Symmetric class, and in magic-wormhole itself.

Acknowledgments

Many thanks to Mike Hamburg for pointers and feedback on this post, and to Prof. Dan Boneh for telling me about SPAKE2 in the first place.