Return to Answer

The first protocol for password authenticated key exchanged 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.

EDIT:

So, I discussed today with my PhD advisor, which 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.

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.

EDIT:

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.

The first protocol for password authenticated key exchanged 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.

The first protocol for password authenticated key exchanged 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.

EDIT:

So, I discussed today with my PhD advisor, which 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.

The first protocol for password authenticated key exchanged 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).

The first protocol for password authenticated key exchanged 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.