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 _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves