I am looking into PAKEs (password-authenticated key exchanges), and it seems like SRP (Secure Remote Password) is essentially the de-facto standard.

However, implementing SRP actually requires doing modular arithmetic, and is similar to, say, implementing Diffie-Hellman. That is, you'd have to have constant-time exponentiation algorithms, a fast bignum library, and getting one of any of these subtly wrong and you might have a terrible side-channel attack.

And unlike algorithms like AES or Curve25519, there aren't many crypto libraries that contain a primitive for SRP, so "rolling your own" is often unavoidable anyway.

Are there any PAKEs that instead of using "custom" mathematics like SRP, simply is implemented in terms of more standard primitives, such as "any secure cryptographic hash", "any secure Diffie-Hellman-like exchange", "any secure signature scheme"? It would be a lot more obvious that it's secure - SRP isn't obviously secure at first glance unless you actually follow the reduction to the discrete log problem - and a lot easier to securely implement providing you have secure implementations of the primitives.

For example, I could think of a weak PAKE, where you simply do a Diffie-Hellman key exchange, but both parties attach a MAC to the ephemeral public keys derived from the password. This is obviously secure if the password is strong, but unlike SRP an attacker gains enough information for an offline brute-force attack, and the server has to store the password in plaintext.

I'm looking for whether there are PAKEs similar to SRP in strength that are as easy as the above weak scheme to intuitively understand and implement in terms of other primitives.

  • $\begingroup$ Hmm, asking for a list is kind-of off topic, but this question clearly requires objective reasons (using established primitives). Furthermore, I wonder if we would go over 1 or even 0 items on the list and the question is pretty interesting. Let's leave it open! $\endgroup$
    – Maarten Bodewes
    Mar 3 '17 at 9:42
  • $\begingroup$ It appears that both SESPAKE and J-PAKE are unsuitable for you :( $\endgroup$
    – SEJPM
    Mar 5 '17 at 10:51
  • $\begingroup$ The closest I've been able to find is the Salted Challenge Response Authentication Mechanism (SCRAM), but it is not a PAKE. It uses the "standard" SHA-1/SHA-256, PBKDF2, and HMAC cryptographic primitives. $\endgroup$ Mar 30 '18 at 2:23

The first protocol for password authenticated key exchange that appeared in the crypto community was the Bellovin-Merritt scheme (see also this survey page 4). This protocol is very simple, and might actually suit your need: is is exactly a Diffie-Hellman key exchange, in which the flows are encrypted with a block cipher (using the common password as the key of the cipher), and where the secret key the players agree on is derived by hashing the Diffie-Hellman tuple. The security of this protocol was analyzed several times, in various models (ideal cipher model or random oracle model, in indistinguishability-based framework or simulation-based framework...). Although it does not enjoy a proof of security in the plain model, you might be satisfied with a protocol proven secure in the random oracle model.

In this case, this scheme seems to exactly fit your requirements: you need "any Diffie-Hellman key exchanged", together with "any (good) hash function" and "any block cipher" that allows you to encrypt the flow with the password. Variations of the Bellovin-Merritt scheme that might make it even simpler are presented in this article (they essentially replace the block cipher by a simple one-time pad, and have two variants, one non-concurrently secure and one concurrently secure).

EDIT: so, after discussing with Ricky Demer, this does not quite work yet. A necessary condition for this to work is that the messages generated by the DHKE - which are group elements - should be indistinguishable from random bit-strings. For DHKE over $\mathbb{Z}^*_p$ for some large prime $p,$ group elements can be naturally mapped to a distribution statistically indistinguishable from bit-strings, and existing implementations might already encode these messages as random-looking bit strings (but this would have to be checked). For more sparse groups such as elliptic curves, I believe such a mapping can be done, but it would be more cumbersome from an implementation point of view. I thank Ricky Demer for pointing this out.

The variants presented in this article do not use a block cipher, which gives rise to dictionary attacks when the encoded element does not look random, but using a kind of multiplicative one-time pad: Alice masks her flow $g^x$ by multiplying it with $M^{\mathsf{pw}}$, where $M$ is a group element and $\mathsf{pw}$ is the password (and Bob plays similarly). Here, you do not have to care about how group elements are represented; however, you must perform an exponentiation (with a small exponent) and a multiplication, hence it does not makes a black-box use of the DHKE key exchange.


So, I discussed today with my PhD advisor, who happens to be the author of quite a number of papers in the PAKE area (in particular this paper which I had mentioned). It confirmed what I had started to think: it does not seem feasible to build a PAKE with a black box access to a DH key exchange and symmetric primitives. Somehow, you have to be at least able to multiply two group elements (hence you must know their structure). I cannot prove that it is infeasible, of course, but that is currently unknown in the scientific community, and not believed to be feasible.

  • 1
    $\begingroup$ "any Diffie-Hellman key exchanged" is not enough ​ - ​ One also needs oblivious sampling of group elements, or something very close to that. ​ ​ ​ ​ $\endgroup$
    – user991
    Mar 5 '17 at 13:54
  • $\begingroup$ Well, depends if you see the protocol as a complete black box that only provides a common key, or as some pre-existing code that will generate the message of Alice for Alice, the message of Bob for Bob, and will then give the corresponding key. Here, you can simply take the message generated for the DH key exchange, and encrypt it to get your message of the PAKE. $\endgroup$ Mar 5 '17 at 14:26
  • $\begingroup$ That does not necessarily work ​ ​ ​ - ​ ​ ​ Suppose the group elements all start with ​ security parameter ​ zeros. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user991
    Mar 5 '17 at 14:30
  • $\begingroup$ I'm not sure I'm following you, can we discuss that in a chat, if you have a few minutes? $\endgroup$ Mar 5 '17 at 14:37
  • $\begingroup$ I have time, but don't know how to create a chatroom here. ​ ​ $\endgroup$
    – user991
    Mar 5 '17 at 14:49

Building upon Geoffroy Couteau's answer, there are possible fixes to the issues addressed there.

The Bellovin-Merrit (from section 3: EKE using exponential key exchange) scheme is roughly like this: - Alice and Bob agree on a safe prime modulus and a generator of the group (which has a problem of leaking its Legendre symbol) - Alice and Bob do a normal DH key exchange first; this is encrypted with a symmetric encryption scheme using the password as key - Afterwards a challenge-response is done to counter replay attacks, encrypted with the exchanged key.

The issue is: If you use another KE protocol, encoding those elements might have certain structure and we can't assume they are indistinguishable from random values. And if you encrypt a non-random value with a low-entropy key, that could turn into an off-line or dictionary attack.

With a generic key exchange protocol and ECB mode of operation for the symmetric encryption, I don't think this is possible: If you give the attacker in addition to the original message an encryption of all $0$ (which could be part of the representation of group elements), the attacker can try and check guesses for the password.

If you use a password-based KDF this increases the effort for brute-forcing the password, but does not solve the problem entirely.

Using other modes of operation don't solve the problem either: With known IV and low entropy password, this can also be utilized in an attack.

The only way to solve this would to make sure that in the first $k$ bits of the binary representation of the group elements have at least $k-x$ bits of entropy (or even are hardcore bits) and then use some mode of operation with chaining.

Another idea would be to use SPEKE, which was developed shortly after the other protocol:

  • Agreement on public parameters with a safe prime $2p+1$
  • The password is hashed, matched to a group element and then squared. This is the generator of the subgroup with prime order $p$.
  • Alice and Bob just do a key exchange with this generator, which only they should know.

Regarding the scheme, the upside is there is no way an attacker can test a guess for the password, because the key exchange happens in the subgroup of quadratic residues and the group has prime order. It is noted that you can use the protocol with elliptic curves, but you do need a way to match a password to a group element. The wiki article notes IOP or Integer-to-Point function in IEEE P1363.2 for that.

However, in 2014 the paper The SPEKE Protocol Revisited (Hao,Shahandashti) showed attacks on SPEKE, and the paper also discusses necessary changes to the protocol.

One possibility of this is tho, that once you fix the problems for those attacks, you actually end up with something very similar to SRP.

  • $\begingroup$ See, all of these solutions require "manually" doing mathematics with big numbers. The point of my question was precisely, whether there are protocols that don't require me to do so. I shouldn't need to care that Diffie-Hellman even uses numbers: it's just a black box with two functions: "generate keypair" and "derive shared secret from my private key and their public key". $\endgroup$
    – ithisa
    Mar 6 '17 at 19:05
  • $\begingroup$ SPEKE alone is a hash function, squaring one element and a key exchange. That's as much out-of-the-box as you can get. However, if you assume a "gen keypair" algorithm, that's something entirely different than password based key exchange. Just use authenticated Diffie-Hellmann instead. $\endgroup$
    – tylo
    Mar 7 '17 at 10:23
  • $\begingroup$ As I said, authenticated Diffie-Hellman, authenticated with a MAC derived from the password, is less secure than SRP because a passive attacker gains enough information to brute-force the password if it's weak. SRP 1. does not need the server to store a password equivalent 2. does not allow passive attackers to gain information for an offline brute-force. Authenticated DH satisfies none of these requirements. $\endgroup$
    – ithisa
    Mar 7 '17 at 14:30
  • $\begingroup$ @user54609 Then I don't understand what you meant with your previous comment. The term "generate keypair" doesn't fit in password based key exchange at all. I did not mean authenticated DHKE with a password-derived key - I meant authenaticated DHKE with a proper PKI - where you store the certificate locally, and possibly unlock it with a passphrase. $\endgroup$
    – tylo
    Mar 7 '17 at 15:37
  • $\begingroup$ @tylo : ​ However, that term does fit non-interactive key agreement, as well as $\hspace{1.4 in}$ setup-based versions of that, such as Diffie-Hellman. ​ ​ ​ ​ $\endgroup$
    – user991
    Mar 8 '17 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.