[curves] PAKE questions

[Brian Warner]

I've been working on a (python) PAKE library, and as usually happens
with these things, there are a number of questions that don't really
surface until the bits meet the road. I talked to Trevor about it last
week, and we came up with a short list of things that we'd really like
to figure out or resolve.

I'm implementing SPAKE2, first with an integer group (prime-order
subgroup of a larger Zp* group), then I want to move to one of the 25519
groups. Portability matters more to me than speed, hence the
pure-python, but it'd be nice to not be painfully slow. I've got a
2048-bit integer group running in 16ms on a fast computer, 110ms on a
slower one, and it'd be nice to bring that down a little bit.

For reference, SPAKE2 (in additive notation, with scalars in lowercase
and group elements in caps) is:

 public elements: M and N (one per role), generator G
 private scalar: pw

 Alice:
   x = random_scalar()
   X = G*x
   MSG_X = X + M*pw , send MSG_X
 Bob:
   y = random_scalar()
   Y = G*y
   MSG_Y = Y + N*pw, send MSG_Y
   Z = (MSG_X - M*pw) * y
   key = H("Alice", "Bob", MSG_X, MSG_Y, Z)
 Alice:
   Z = (MSG_Y - N*pw) * x
   key = H("Alice", "Bob", MSG_X, MSG_Y, Z)


1: Dealing with the cofactor

I'm planning to grab the group-operation algorithms from the Ed25519
reference implementation, because SPAKE2 needs both point-addition and
scalar-multiplication (so Curve25519's DH-specific X-only code won't
help me). I think I need both X and Y coordinates, but I haven't studied
the algorithm enough to know if maybe I can get away with just the X
coord (maybe trying both sign bits and accepting one of two different
passwords?).

Both Curve25519 and Ed25519 reference implementations clamp the secret
scalars (clearing the low three bits, setting the high bit). My partial
understanding is that this clears the cofactor and makes it safe to not
do as much checking on the received public point (the DH public
parameter for Curve25519/DH, or the public verifying key for
Ed25519/Schnorr). If you don't check that the received point is part of
the right group (and that it has the correct large order), then you
might end up revealing the low-order bits of the private key, and so
fixing them to zero means you're not revealing anything.

So I think I either must spend the time to verify the incoming point for
subgroup membership, or find a way to clear the cofactor in SPAKE2. Any
idea how to do this correctly? We figured that, from Bob's point of
view, the concern is that MSG_X is not really a point on the right
subgroup, but MSG_X*cofactor would be. So maybe do something like:

  Z = (MSG_X*cofactor - N*pw*cofactor) * y

Are we on the right track?

2: Augmentation

Boneh/Shoup's "cryptobook" defines an additional algorithm, "PAKE2+",
which includes an augmentation step. I think this is beyond what Abdalla
and Pointcheval described in their 2005 RSA paper. Do people generally
agree that PAKE2+ is a good approach? I don't know how much review it's
had.

(also, are "Balanced" and "Augmented" the modern terms for these two
modes? or has this changed?)

3: Simultaneous Init (M==N)

I don't know what the best term is for this, but most of the PAKE
algorithms I've seen assign roles to the two parties, and bake those
into the messages. I'm sure this makes the proofs easier to build, and
might block some sort of reflection attack (what happens if the attacker
echoes Alice's message back to her.. could that help them learn the key
or the password?).

But it's a nuisance for certain peer-to-peer use cases, like the
Petmail/Panda introduction protocol, where there's no easy way to give a
consistent name to each side. In the scheme I'm building for Petmail,
the two humans can pick a string and type it into their agents at
roughly the same time; I then want PAKE to amplify that into strong key
exchange. There's no client-vs-server, or first-vs-second distinction.
I'd have to explain to users that, in addition to remembering a random
string, they also have to pick sides, and that'd be a drag.

So what happens if you take SPAKE2 and set M==N? Does it break horribly?

I had another idea, which I *think* is reasonable:

 Alice runs two instances in parallel, with the same password, one as A
 and one as B. She glues the A and B messages together and sends both to
 Bob.

 Bob does the same, but swaps Alice's A/B messages before feeding them
 into his A/B instances. Alice swaps Bob's A/B messages upon receipt.

 Alice then XORs the keys that come out of her two instances. Bob does
 the same.

This takes twice as much CPU and bandwidth, but:

 * combining the two keys before revealing any derivative means an
   active attacker still only gets one guess, not two
 * using XOR doesn't require deciding upon a canonical order for
   anything (like sorting them lexicographically, concatenating, then
   feeding into HKDF)
 * I think it preserves the validity of SPAKE2's security proof
 * it's pretty easy to implement


4: Choosing M and N (aka U/V in PAKE2)

SPAKE2 requires two "arbitrary public elements" to blind the passwords,
but what wasn't obvious to me when I first started was that it's
important that nobody knows the discrete log of either one (otherwise an
active attacker gets a dictionary attack, I think). Since the easiest
way to pick a random element is to start with a random scalar, it's a
subtle failure mode for implementors.

Picking an arbitrary member of a an elliptic curve subgroup usually
means picking a random X coordinate, finding the 0 or 2 points that
match (50/50 chance), choose one, then see if it's in the subgroup.
Small cofactors make this probable(?) enough that random hunt-and-peck
will yield a result quickly, and you can make it more rigid/"sleeveless"
by starting your random search at SHA256("") or something.

Doing this for a q=~160-bit prime-order subgroup of a p=~4kbit Zp* group
doesn't work, because the cofactor (r=(p-1)/q) is gigantic: you'll never
randomly discover a subgroup member this way. I learned/believe that the
right approach is to pick a uniform integer h in Zp, then compute h^r,
which will be a uniform member of the subgroup. My more-rigid algorithm
is to hash a seed into enough bits to Zp, turn it into an integer, then
take it modulo p (introducing some bias), before raising to the cofactor
r.

Is this right?

This is one of the things we'd need to nail down so implementors can
feel confident about it.

5: Hashing the password

The use cases that want Augmented PAKE really want something stronger
than a single scalar multiplication. PAKE appears to be at odds with
protecting server-side data against dictionary attacks, which is a pity
because it does a great job of protecting against network-side attacks.
Can we get both?

Trevor floated a crazy idea that involved only masking one side of the
exchange, and then being very careful about who reveals a derived key
first. We thought this might be useful for something, but tough to keep
it safe.


thoughts?
 -Brian