I asked Dan Boneh about this, and we didn’t figure out an answer in our brief meeting but he said it’s a good problem.
Makwa with a public N, where nobody holds the trapdoor, is a good idea since you can outsource it. You can’t check the answer, though… which is OK, I guess? Another option, which is also way out there: Let H(password) = H1(discrete log(H2(password))), where the discrete log is computed over a weak elliptic curve which is unique per user but doesn’t depend on the password. Perhaps the curve has ~2^50 points on it, requiring ~2^25 work, which will take a couple seconds. The discrete log calculation can be offloaded to the server, by sending H2(password) * g^r, where r is random mod the order of the curve. Subtracting r at the end gives the answer, and the answer can be checked easily. The problem is, n discrete logs can be batched into O(sqrt(n)) times longer than a single one. So if the database has a million passwords, they can be checked in the time required for 1000 logins. So Makwa probably works better. Cheers, — Mike > On Oct 21, 2014, at 7:01 PM, Brian Warner <[email protected]> wrote: > > On 10/16/14 3:34 PM, Greg Zaverucha wrote: > >> Are there PAKE schemes where the augmented option adds a workfactor >> for the server role only? The goal being to make brute force attacks >> more expensive if the verification information is compromised. > > I haven't found one yet. I suspect it's impossible, but I have no idea > how you'd prove that. > > This was part of the reason that we switched Firefox Accounts from the > SRP-based protocol that I'd built to the simpler plain-old-scrypt > scheme. I liked the zero-knowledge aspects of SRP (or any PAKE system, > augmented or symmetric), but the lack of server-side key-stretching > meant that any protection against server compromise must come from the > client. In our SRP-based protocol, the client did about 1.0 seconds of > scrypt (N/r/p = 64k/8/1) before using the stretched result as the SRP > "password". This made life difficult for slow clients, such as ones > implemented in web-page javascript. > > One crazy idea: Thomas Pornin has a password-hashing.net submission > named "Makwa", based on repeated squaring modulo a composite Blum > integer, which enables a certain amount of delegation (safely letting > someone else do part of the key-stretching work for you). I've wondered > if this might be usable as a primitive in a PAKE protocol, using > "square-N-times" instead of "multiply-N-times" as the group operation. > > The upside/downside is that there's a secret key (the factors of the > Blum modulus) which lets you bypass the stretching and exponentiate > directly. For many login-like settings, this is fine (you keep the > factors offline, or throw them away after setup), and even useful (you > can batch-update the stretched verifiers without needing client > involvement). But for Pond/Petmail-like invitation schemes, with no > trusted server, the existence of this secret key is uncomfortable, as > the safety of your stretching depends upon the creator of your group > parameters honestly throwing it away. > > cheers, > -Brian > _______________________________________________ > Curves mailing list > [email protected] > https://moderncrypto.org/mailman/listinfo/curves _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
