[curves] PAKE questions

[Michael Hamburg]

Hi Brian,

Cool stuff.  I’ve got some comments inline, and I’m also planning on going to
BaySec in a week and a half if you want to discuss there.  (Or is there also a
drinking cryptographers thing at some point?)

One thing worth considering is “SPAKE2 Elligator Edition”.  This is SPAKE2,
except that you replace M^password, N^password with

cofactor * MapToCurve(H(“M to the password”, password)),
cofactor * MapToCurve(H(“N to the password”, password)).

The disadvantage of this is that you need to implement Elligator or some other
map to the curve, but the advantage is that the parties’ IDs can be more than
just “client” or “server”.  Eg you could use IP address and port (except NAT)
or even just a random number.  The map doesn’t need to be uniform or onto,
it just has to be invertible (or inverse-samplable) and within a small factor of
uniform.  So Elligator and SWU work, and hunt-and-peck works except that
it’s not constant time.

For the field, you can set MapToCurve to just be a full-domain hash function.

Also, this gets rid of the static DH assumption (i.e. that an attacker can MITM
the protocol if they know the discrete logs of M and N), but if you choose your
points in a sleeveless way that doesn’t matter much.

More comments inline...

> On Feb 6, 2015, at 7:27 PM, Brian Warner <warner at lothar.com> wrote:
> 
> 
> 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.

Are you using pow(x,e,p)?  It ought to be faster than that.

> 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?).

If you’re going to drop a coordinate, then send a sign bit in its place.  You
even have an extra (256th) bit to use without breaking alignment.  You can’t
(easily) use the Montgomery ladder anyway.

> 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.

I believe Watson and I determined that clearing the cofactor makes SPAKE2
safe, and because the identity point is actually allowed in SPAKE2 (I think?)
you don’t even have to reject points in small subgroups.  It’s probably a good
idea to make sure that the secret scalar has 252 random bits, though (~ the
group order).

> 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?

Yeah, that.  Or just *y*cofactor, since multiplication distributes and commutes.

*Shameless plug*:
If you’d like, I can get Decaf up and running on TwistEd25519 in Python.
Decaf divides the cofactor by 4, and also conveniently implements a hash to
the curve.

> 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.

I’m pretty sure PAKE2+ is fine.  But I might have been the one who pointed
it out to you.  It’s not in Pointcheval-Abdalla.

> (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?).

Yeah, it’s mostly a proof artifact.  The main difference is that it lets you use the CDH
problem (in the ROM) instead of CDH-squaring.  As a corollary, M=N is fine if you
watch out for reflection.

I don’t think reflection lets the attacker find Alice's password, but she will accept the
connection and probably shouldn’t.

> 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?

It should be fine, as Michael Scott said.

See also above: you can just have each party choose a random name for itself
and run SPAKE2 EE.

> 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 is probably fine, but watch out for the reflection attack!  If an attacker
reflects Alice’s messages and she accepts them, then she will xor the session
key with itself and get 0.  Bob will too.  Bad times.

Better to sort the two keys and then hash them, or something similar, but I
agree that this is annoying.  If you’re going to combine the keys commutatively,
maybe add them?

> 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.

Yes, this works.  Though I like Michael Scott’s idea of using 2 and 3 mod
a safe prime, if you aren’t using EC.

> 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?

Yeah.  Don’t use the password, but instead use scrypt(password).  And you
should use salt, either the username at domain or a random salt which the
server sends in its first flow.

> 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.

I’m pretty sure that this is (provably) safe if you’re careful of the message
order. The party who reveals second has to mask.

> thoughts?
> -Brian

Cheers,
— Mike