> On Feb 7, 2015, at 4:30 PM, Brian Warner <war...@lothar.com> wrote: > > On 2/7/15 2:21 PM, Michael Hamburg wrote: > >> 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”. > > How is this different than the static idA/idB that's usually hashed > (along with the transcript) into the final key? I imagine it's more > tightly bound somehow..
If the hash to the curve is based on idA / idB, then you don’t need to figure out which party uses M and which uses N, which is something you were concerned about. >> For the field, you can set MapToCurve to just be a full-domain hash >> function. > > That's a hash function with an output range of Zp*, right? Do people > typically implement that with hash-to-larger-and-modulo (accepting a > fraction of a bit of bias), or try-try-again (no bias but variable > runtime)? Or hash-to-necessary-bits and accept more bias? Hash larger and modulo. Security-level bits larger (128 or whatever) is good enough even for a prime that’s not close to a power of 2. Especially here because it doesn’t have to be uniform anyway. >>> 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. > > Yeah, pow(x,e,p) on python2.7 . It looks like a single pow() takes 4ms, > but there are several of them. Alice computes G*x and M*pw when building > the first message. She verifies the incoming point (MSG_Y*q) and > computes -N*pw and (MSG_Y-that)*x during receipt of the second mesage. > > That's 5 exponentiations, and when I added the point-verification check > (which I forgot the first time through, like always), it takes 20.5ms to > do the whole side, so that about accounts for it. > > The code is in https://github.com/warner/python-spake2 if you want to > take a look. Run "python setup.py speed" for the benchmarks. Ah, that makes more sense. >>> 1: Dealing with the cofactor > >> 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. > > Yeah, so I need to decompress the point before doing anything with it, > right? I can't use the Curve25519 trick of ignoring Y everywhere? Right. >>> 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. > > Is it safe to do that after the subtraction? I know the subgroup's "*" > is distributive, but I was concerned that we'd leave the subgroup with > the (nonmember-N*pw) and then all bets would be off. The whole group’s * is distributive. >> *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. > > That'd be fun :). OK, I’ll see what I can do. >>> 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. > > Sigh, once again my implementation didn't guard against trivial things > like that.. unit test now added :). There was a Stanford crypto problem set where you had to design a protocol for something. A lot of people had a very similar bug in their design. >>> 5: Hashing the password > > I'll think more about this one.. I seem to recall that simply stretching > it before the exponent didn't accomplish what I wanted, but I have to > nail down exactly why. > > thanks! > -Brian In the earlier thread, it was because you didn’t want to push the work to the client. Is that still a requirement? I don’t have a solution for it. Cheers, — Mike _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves