[curves] PAKE questions

[Michael Scott]

First off, its great to see interest in PAKE-like protocols. In my opinion
they are one of the gems of modern cryptography, but not widely known about
and not widely used.

The SPAKE2 idea with M=N, is basically the scheme described by Kobari and
Imai here http://eprint.iacr.org/2003/038, and they have a security proof
for it. So I think this is fine. The basic original idea also independently
occurred to me (and probably others) some time before that - see
*www.computing.dcu.ie/wpapers/2000/CA1300.ps
<http://www.computing.dcu.ie/wpapers/2000/CA1300.ps> *

It is vital that the discrete logarithm relationship between the generators
is not known, as if it is it represents exactly the same kind of back-door
that was used by the NSA with the late and unlamented Dual Elliptic Curve
Deterministic Random Bit Generator. The solution is to create the
generators using a hash function in some transparent way. (In my original
paper I suggested using as generators 2 and 3 with a safe prime, the
challenge for an attacker being to find x such that 2=3^x mod p. You can't
get more transparent than that!)

The cofactor issue can be simply solved by raising any received value to
the power of the cofactor, and checking that it is not the neutral element
of the group (read multiplying by the cofactor in the elliptic curve case).
In the EC case the cofactor is so small that this is not a problem. In Zp
the cofactor can be huge, so this is not practical. The solution here is to
choose a lim-lee prime (for example such that (p-1)/2q is prime), in which
case a sub-group confinement attack becomes pointless and the group order
check is no longer necessary (other than to wipe out the cofactor 2 which
can be done as for the EC group).

FYI my Python implementation of elliptic curves takes 17ms on a modem PC
for a general point multiplication. In Zp with a 2048-bit prime, you really
want to be using Karatsuba, which would give a substantial speed-up.


Mike



On Sat, Feb 7, 2015 at 3:27 AM, 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.
>
> 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 at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>



-- 
Michael Scott
Chief Cryptographer
CertiVox Ltd
Tel (353) 86 3888746
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150207/5e445b2d/attachment.html>