[curves] SPEKE using Curve25519 - elligator2 required or recommended?

[Arasch Honarbacht]

Hi all,



I'm working on a proposal for key agreement in zigbee networks. The idea is
to use SPEKE and Curve25519. My understanding is that Curve25519 accepts all
32-byte strings as valid public keys. Now, instead of the default base point
9, the base point is generated using a hash of the password. For argument's
sake, assume the base point would be a random number. I've implemented a
test bench and tested this approach and it works well (for the small set of
experiments I made, i.e. a couple of thousand executions).



The approach as it stands:



Alice generates a secret a, Bob generates a secret b.

Alice computes P = aG and sends it to Bob. Bob computes Q = bG and sends it
to Alice.

Alice computes k = aQ = abG. Bob computes k = bP = baG.



When the base point G is chosen as one of the 12 points listed under the
"contributory" behavior on Bernstein's site (https://cr.yp.to/ecdh.html) the
scalar products P and Q and the shared secret become zero - so these points
need to be avoided.



Now, I saw in literature that reverse elligator2 mapping is used to map a
random string to a Montgomery x coordinate u, e.g. instead of G simply being
the hash, G = elligator2(hash), c.f. Figure 1 in this paper:
https://eprint.iacr.org/2017/562.pdf, or section 2.6 here:
https://signal.org/docs/specifications/xeddsa/.



My question is: Would a elligator2 mapping be required for the SPEKE use
case outlined above, or is any point, except for the 12 points mentioned
above suitable as a generator?



Thanks, Arasch

[Björn Haase]

_______________________________________________
Curves mailing list
***@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves

[Arasch Honarbacht]

Hi Björn,



Thank you for your prompt reply. Actually your paper is one of the sources I’ve been reading the past days. We’ll certainly consider the suggestions you have made. In fact, the hash could incorporate a random session ID (as I understood there is an attack against SPEKE where you create multiple concurrent sessions), but those are separate concerns – and therefore I was referring to a random base point.



Your note about an ephemeral generator is apparently also orthogonal, right?



So to better understand your point, if for example the hash of the password has n bits of effective security, say 128, then we would leak one bit of the hash (not the password itself), correct? Put differently, how could this information practically be exploited? Is it a realistic attack today or e.g. a potential weakness that could be attacked using a quantum computer and a nuclear power plant in e.g. 20 years from now?



The question is, whether or not added code space, execution time and battery drain for eliigator2 are worth it, for our particular use case. Or would you consider the additional complexity negligible compared to X25519. For example on a Cortex-M4 (ATSAM4S8B) the scalar product requires 4kB flash and roughly 1.8M cycles using Wouter de Groot’s implementation. What would elligator2 add to this, assuming an implementation of similar quality – or even reusing the field primitives already present (as far as possible)?



Thanks again



Arasch



Von: Curves [mailto:curves-***@moderncrypto.org] Im Auftrag von "Björn Haase"
Gesendet: Dienstag, 24. Oktober 2017 17:17
An: ***@moderncrypto.org
Betreff: [curves] Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?



Hi,



first of all, I agree that using a PAKE scheme for password-based authentication on zigbee networks is a good idea. Also, SPEKE-based protocols are IMHO the fastest choice available. Since SPEKE patents have expired, there is no need to avoid that the password itself enters the calculation of the generator, which was (IIUC) the main reason for the patent circumvention approach for that PACE has been developped.



Regarding the base point selection, I'd strongly recommend to use Elligator2 and not just the hash of the password. The reason is, that depending on your construction, you will at least leak one bit of the password. If you just use the hash, you will either be having a point on the curve or on it's twist and this information could be exploited.

IMO there are a couple of things to consider when suggesting standardization: I'd recommend to combine the construction with use of a sound password hash, such as scrypt or argon2, mainly because it's likely that you will never enter the password on the small node. At least one should use PBKDF2 with a strong parameter set.

The second thing is consideration of side-channel stuff. I'd advocate on using an ephemeral generator. This costs essentially one additional communication round, but this might be worth the effort, since you anyway might be having a communication telegram exchange before the actual PAKE scheme.

When combining some ephemeral (and publicly known) random with the password hash for generating an ephemeral generator with Elligator2, you will be ending up with something very similar to our PACE paper at chess ( <https://eprint.iacr.org/2017/562.pdf> https://eprint.iacr.org/2017/562.pdf).

Note that the fact that you are using an ephemeral generator comes virtually at no added cost. I'd suggest to use a permutation or a hash for combining random values from both sides, and the password hash and feed the result into elligator2 to get an ephemeral generator. The patent circumvention step in our PACE paper (that forced us to use a symmetric cipher, in our case Salsa20, on top) is now no longer necessary.

Yours,

Björn

Gesendet: Dienstag, 24. Oktober 2017 um 14:03 Uhr
Von: "Arasch Honarbacht" < <mailto:***@ubisys.de> ***@ubisys.de>
An: <mailto:***@moderncrypto.org> ***@moderncrypto.org
Betreff: [curves] SPEKE using Curve25519 - elligator2 required or recommended?

Hi all,



I’m working on a proposal for key agreement in zigbee networks. The idea is to use SPEKE and Curve25519. My understanding is that Curve25519 accepts all 32-byte strings as valid public keys. Now, instead of the default base point 9, the base point is generated using a hash of the password. For argument’s sake, assume the base point would be a random number. I’ve implemented a test bench and tested this approach and it works well (for the small set of experiments I made, i.e. a couple of thousand executions).



The approach as it stands:



Alice generates a secret a, Bob generates a secret b.

Alice computes P = aG and sends it to Bob. Bob computes Q = bG and sends it to Alice.

Alice computes k = aQ = abG. Bob computes k = bP = baG.



When the base point G is chosen as one of the 12 points listed under the “contributory” behavior on Bernstein’s site ( <https://cr.yp.to/ecdh.html> https://cr.yp.to/ecdh.html) the scalar products P and Q and the shared secret become zero – so these points need to be avoided.



Now, I saw in literature that reverse elligator2 mapping is used to map a random string to a Montgomery x coordinate u, e.g. instead of G simply being the hash, G = elligator2(hash), c.f. Figure 1 in this paper: <https://eprint.iacr.org/2017/562.pdf> https://eprint.iacr.org/2017/562.pdf, or section 2.6 here: <https://signal.org/docs/specifications/xeddsa/> https://signal.org/docs/specifications/xeddsa/.



My question is: Would a elligator2 mapping be required for the SPEKE use case outlined above, or is any point, except for the 12 points mentioned above suitable as a generator?



Thanks, Arasch

_______________________________________________ Curves mailing list <mailto:***@moderncrypto.org> ***@moderncrypto.org <https://moderncrypto.org/mailman/listinfo/curves> https://moderncrypto.org/mailman/listinfo/curves

[Mike Hamburg]

Hi Arasch,

If the password is salted, then the issue is probably exploitable. This is because you will give away one bit of the password per salt. Whether the exploit is against the user or the device depend on protocol flow and on who choses the salt.

If the password is not salted, then you give away one bit of the password total. This might not be exploitable, but it’s definitely not ideal. Also, lack of salt isn’t ideal either.

If properly implemented (i.e. using one inverse square root), Elligator 2 adds about 10% to the curve25519 operation, which is to say 5% to each party’s runtime (since they do 2 curve25519 operations). It probably adds a few hundred bytes to the code size as well. It can reuse all the existing field operations, except that you need to extend your inverse operation to inverse square root.

On a related note, if you haven an M4 and are truly strapped for code size, you might want to consider STROBE. It supports Curve25519 key exchange, signing and verification, as well as (totally non-standard) hashing, AEAD encryption, pseudorandom generation, PBKDF2-quality password strengthening, and a lightweight protocol framework in as little as 3kB of code (probably more like 4k since you’d have to talk with Rambus to get the M4 asm version). So implementing SPEKE would just require the addition of Elligator. It’s probably not as fast as Wouter’s Curve25519 implementation though.

— Mike

Post by Arasch Honarbacht
Hi Björn,
Thank you for your prompt reply. Actually your paper is one of the sources I’ve been reading the past days. We’ll certainly consider the suggestions you have made. In fact, the hash could incorporate a random session ID (as I understood there is an attack against SPEKE where you create multiple concurrent sessions), but those are separate concerns – and therefore I was referring to a random base point.
Your note about an ephemeral generator is apparently also orthogonal, right?
So to better understand your point, if for example the hash of the password has n bits of effective security, say 128, then we would leak one bit of the hash (not the password itself), correct? Put differently, how could this information practically be exploited? Is it a realistic attack today or e.g. a potential weakness that could be attacked using a quantum computer and a nuclear power plant in e.g. 20 years from now?
The question is, whether or not added code space, execution time and battery drain for eliigator2 are worth it, for our particular use case. Or would you consider the additional complexity negligible compared to X25519. For example on a Cortex-M4 (ATSAM4S8B) the scalar product requires 4kB flash and roughly 1.8M cycles using Wouter de Groot’s implementation. What would elligator2 add to this, assuming an implementation of similar quality – or even reusing the field primitives already present (as far as possible)?
Thanks again
Arasch
Gesendet: Dienstag, 24. Oktober 2017 17:17
Betreff: [curves] Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?
Hi,
first of all, I agree that using a PAKE scheme for password-based authentication on zigbee networks is a good idea. Also, SPEKE-based protocols are IMHO the fastest choice available. Since SPEKE patents have expired, there is no need to avoid that the password itself enters the calculation of the generator, which was (IIUC) the main reason for the patent circumvention approach for that PACE has been developped.
Regarding the base point selection, I'd strongly recommend to use Elligator2 and not just the hash of the password. The reason is, that depending on your construction, you will at least leak one bit of the password. If you just use the hash, you will either be having a point on the curve or on it's twist and this information could be exploited.
IMO there are a couple of things to consider when suggesting standardization: I'd recommend to combine the construction with use of a sound password hash, such as scrypt or argon2, mainly because it's likely that you will never enter the password on the small node. At least one should use PBKDF2 with a strong parameter set.
The second thing is consideration of side-channel stuff. I'd advocate on using an ephemeral generator. This costs essentially one additional communication round, but this might be worth the effort, since you anyway might be having a communication telegram exchange before the actual PAKE scheme.
When combining some ephemeral (and publicly known) random with the password hash for generating an ephemeral generator with Elligator2, you will be ending up with something very similar to our PACE paper at chess (https://eprint.iacr.org/2017/562.pdf <https://eprint.iacr.org/2017/562.pdf>).
Note that the fact that you are using an ephemeral generator comes virtually at no added cost. I'd suggest to use a permutation or a hash for combining random values from both sides, and the password hash and feed the result into elligator2 to get an ephemeral generator. The patent circumvention step in our PACE paper (that forced us to use a symmetric cipher, in our case Salsa20, on top) is now no longer necessary.
Yours,
Björn
Gesendet: Dienstag, 24. Oktober 2017 um 14:03 Uhr
Betreff: [curves] SPEKE using Curve25519 - elligator2 required or recommended?
Hi all,
I’m working on a proposal for key agreement in zigbee networks. The idea is to use SPEKE and Curve25519. My understanding is that Curve25519 accepts all 32-byte strings as valid public keys. Now, instead of the default base point 9, the base point is generated using a hash of the password. For argument’s sake, assume the base point would be a random number. I’ve implemented a test bench and tested this approach and it works well (for the small set of experiments I made, i.e. a couple of thousand executions).
Alice generates a secret a, Bob generates a secret b.
Alice computes P = aG and sends it to Bob. Bob computes Q = bG and sends it to Alice.
Alice computes k = aQ = abG. Bob computes k = bP = baG.
When the base point G is chosen as one of the 12 points listed under the “contributory” behavior on Bernstein’s site (https://cr.yp.to/ecdh.html <https://cr.yp.to/ecdh.html>) the scalar products P and Q and the shared secret become zero – so these points need to be avoided.
Now, I saw in literature that reverse elligator2 mapping is used to map a random string to a Montgomery x coordinate u, e.g. instead of G simply being the hash, G = elligator2(hash), c.f. Figure 1 in this paper: https://eprint.iacr.org/2017/562.pdf <https://eprint.iacr.org/2017/562.pdf>, or section 2.6 here: https://signal.org/docs/specifications/xeddsa/ <https://signal.org/docs/specifications/xeddsa/>.
My question is: Would a elligator2 mapping be required for the SPEKE use case outlined above, or is any point, except for the 12 points mentioned above suitable as a generator?
Thanks, Arasch
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

[Arasch Honarbacht]

Hi Mike,



Thank you very much, this gives me a feeling for striking the right balance and indeed spending the additional resources seems to be worthwhile.



Arasch



Von: Mike Hamburg [mailto:***@shiftleft.org]
Gesendet: Dienstag, 24. Oktober 2017 22:44
An: Arasch Honarbacht <***@ubisys.de>
Cc: Björn Haase <***@web.de>; ***@moderncrypto.org
Betreff: Re: [curves] Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?



Hi Arasch,



If the password is salted, then the issue is probably exploitable. This is because you will give away one bit of the password per salt. Whether the exploit is against the user or the device depend on protocol flow and on who choses the salt.



If the password is not salted, then you give away one bit of the password total. This might not be exploitable, but it’s definitely not ideal. Also, lack of salt isn’t ideal either.



If properly implemented (i.e. using one inverse square root), Elligator 2 adds about 10% to the curve25519 operation, which is to say 5% to each party’s runtime (since they do 2 curve25519 operations). It probably adds a few hundred bytes to the code size as well. It can reuse all the existing field operations, except that you need to extend your inverse operation to inverse square root.



On a related note, if you haven an M4 and are truly strapped for code size, you might want to consider STROBE. It supports Curve25519 key exchange, signing and verification, as well as (totally non-standard) hashing, AEAD encryption, pseudorandom generation, PBKDF2-quality password strengthening, and a lightweight protocol framework in as little as 3kB of code (probably more like 4k since you’d have to talk with Rambus to get the M4 asm version). So implementing SPEKE would just require the addition of Elligator. It’s probably not as fast as Wouter’s Curve25519 implementation though.



— Mike





On Oct 24, 2017, at 1:14 PM, Arasch Honarbacht <***@ubisys.de <mailto:***@ubisys.de> > wrote:



Hi Björn,



Thank you for your prompt reply. Actually your paper is one of the sources I’ve been reading the past days. We’ll certainly consider the suggestions you have made. In fact, the hash could incorporate a random session ID (as I understood there is an attack against SPEKE where you create multiple concurrent sessions), but those are separate concerns – and therefore I was referring to a random base point.



Your note about an ephemeral generator is apparently also orthogonal, right?



So to better understand your point, if for example the hash of the password has n bits of effective security, say 128, then we would leak one bit of the hash (not the password itself), correct? Put differently, how could this information practically be exploited? Is it a realistic attack today or e.g. a potential weakness that could be attacked using a quantum computer and a nuclear power plant in e.g. 20 years from now?



The question is, whether or not added code space, execution time and battery drain for eliigator2 are worth it, for our particular use case. Or would you consider the additional complexity negligible compared to X25519. For example on a Cortex-M4 (ATSAM4S8B) the scalar product requires 4kB flash and roughly 1.8M cycles using Wouter de Groot’s implementation. What would elligator2 add to this, assuming an implementation of similar quality – or even reusing the field primitives already present (as far as possible)?



Thanks again



Arasch



Von: Curves [mailto:curves-***@moderncrypto.org] Im Auftrag von "Björn Haase"
Gesendet: Dienstag, 24. Oktober 2017 17:17
An: ***@moderncrypto.org <mailto:***@moderncrypto.org>
Betreff: [curves] Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?



Hi,



first of all, I agree that using a PAKE scheme for password-based authentication on zigbee networks is a good idea. Also, SPEKE-based protocols are IMHO the fastest choice available. Since SPEKE patents have expired, there is no need to avoid that the password itself enters the calculation of the generator, which was (IIUC) the main reason for the patent circumvention approach for that PACE has been developped.



Regarding the base point selection, I'd strongly recommend to use Elligator2 and not just the hash of the password. The reason is, that depending on your construction, you will at least leak one bit of the password. If you just use the hash, you will either be having a point on the curve or on it's twist and this information could be exploited.

IMO there are a couple of things to consider when suggesting standardization: I'd recommend to combine the construction with use of a sound password hash, such as scrypt or argon2, mainly because it's likely that you will never enter the password on the small node. At least one should use PBKDF2 with a strong parameter set.

The second thing is consideration of side-channel stuff. I'd advocate on using an ephemeral generator. This costs essentially one additional communication round, but this might be worth the effort, since you anyway might be having a communication telegram exchange before the actual PAKE scheme.

When combining some ephemeral (and publicly known) random with the password hash for generating an ephemeral generator with Elligator2, you will be ending up with something very similar to our PACE paper at chess ( <https://eprint.iacr.org/2017/562.pdf> https://eprint.iacr.org/2017/562.pdf).

Note that the fact that you are using an ephemeral generator comes virtually at no added cost. I'd suggest to use a permutation or a hash for combining random values from both sides, and the password hash and feed the result into elligator2 to get an ephemeral generator. The patent circumvention step in our PACE paper (that forced us to use a symmetric cipher, in our case Salsa20, on top) is now no longer necessary.

Yours,

Björn

Gesendet: Dienstag, 24. Oktober 2017 um 14:03 Uhr
Von: "Arasch Honarbacht" < <mailto:***@ubisys.de> ***@ubisys.de>
An: <mailto:***@moderncrypto.org> ***@moderncrypto.org
Betreff: [curves] SPEKE using Curve25519 - elligator2 required or recommended?

Hi all,



I’m working on a proposal for key agreement in zigbee networks. The idea is to use SPEKE and Curve25519. My understanding is that Curve25519 accepts all 32-byte strings as valid public keys. Now, instead of the default base point 9, the base point is generated using a hash of the password. For argument’s sake, assume the base point would be a random number. I’ve implemented a test bench and tested this approach and it works well (for the small set of experiments I made, i.e. a couple of thousand executions).



The approach as it stands:



Alice generates a secret a, Bob generates a secret b.

Alice computes P = aG and sends it to Bob. Bob computes Q = bG and sends it to Alice.

Alice computes k = aQ = abG. Bob computes k = bP = baG.



When the base point G is chosen as one of the 12 points listed under the “contributory” behavior on Bernstein’s site ( <https://cr.yp.to/ecdh.html> https://cr.yp.to/ecdh.html) the scalar products P and Q and the shared secret become zero – so these points need to be avoided.



Now, I saw in literature that reverse elligator2 mapping is used to map a random string to a Montgomery x coordinate u, e.g. instead of G simply being the hash, G = elligator2(hash), c.f. Figure 1 in this paper: <https://eprint.iacr.org/2017/562.pdf> https://eprint.iacr.org/2017/562.pdf, or section 2.6 here: <https://signal.org/docs/specifications/xeddsa/> https://signal.org/docs/specifications/xeddsa/.



My question is: Would a elligator2 mapping be required for the SPEKE use case outlined above, or is any point, except for the 12 points mentioned above suitable as a generator?



Thanks, Arasch

_______________________________________________ Curves mailing list <mailto:***@moderncrypto.org> ***@moderncrypto.org <https://moderncrypto.org/mailman/listinfo/curves> https://moderncrypto.org/mailman/listinfo/curves

[Björn Haase]

Hi Arasch,

In fact, the hash could incorporate a random session ID (as I understood there is an attack against SPEKE

where you create multiple >concurrent sessions), but those are separate
concerns – and therefore I was referring to a random base point.

Your note about an ephemeral generator is apparently also orthogonal, right?

Yes.

Actually I fully agree to Mike's response. What I would recommend you to
do is the following:

1.) make *both* sides contribute a random number. R_alice and R_bob

2.) use a salted hash for hashing the password with the salt s and the
password pw, such that the password-derived key is pdk = PBKDF(s, pw)
with the PBDKF function of your choice and the computational effort that
you could realistically spend.

derive a session-specific generator point by using

3.) G = Elligator2 (HASH (R_alice || R_bob || paddingZeros || pdk))

. I'd recommend you to add some padding zeros behind the random values
in case that you are using SHA2 or SHA512 as hash such that one block is
filled only with the hash. E.g. in case of SHA512 fill up the data up to
128 bytes. This is useful as defense against chosen-plaintext
power-analysis attacks against the hash. Padding costs nothing with
regarding to code size and also nothing in comparison to the PBKDF and
the X25519 protocol calculations.

The construction sketched above is very similar to what I have recently
been discussing with the guys from the BSI.

So to better understand your point, if for example the hash of the password has n

bits of effective security, say 128, then we would >leak one bit of the
hash (not the password itself), correct? Put differently, how could this
information practically be exploited? Is it a >realistic attack today or
e.g. a potential weakness that could be attacked using a quantum
computer and a nuclear power plant in >e.g. 20 years from now?

As Mike has pointed out, the attack is completely realistic if you are
either incorporating a session-specific random value or a salt. You will
be leaking one bit per sniffed login. After listening to 5-20 logins the
attacker will be able to mount an offline attack.

HTH, Yours,

Björn

[Andy Isaacson]

Post by Björn Haase

So to better understand your point, if for example the hash of the
password has n bits of effective security, say 128, then we would
leak one bit of the hash (not the password itself), correct? Put
differently, how could this information practically be exploited? Is
it a realistic attack today or e.g. a potential weakness that could be
attacked using a quantum computer and a nuclear power plant in e.g. 20
years from now?

As Mike has pointed out, the attack is completely realistic if you
are either incorporating a session-specific random value or a salt.
You will be leaking one bit per sniffed login. After listening to
5-20 logins the attacker will be able to mount an offline attack.

I'd like to understand this attack better (the description above is
pretty surprising to me), is there a canonical treatment or a phrase I
should look up in the literature?

-andy

[Gregory Maxwell]

Post by Andy Isaacson
I'd like to understand this attack better (the description above is
pretty surprising to me), is there a canonical treatment or a phrase I
should look up in the literature?

I don't know if there is a standard term for it, but it isn't that complicated.

When you coerce a random hash into a point you'll randomly end up with
a point on the curve or the twist. It will stay on its respective
group through things like blinding operations. So by observing the
protocol you can tell which one each interaction used (e.g. by
multiplying to check the order).

Assuming your hash value used a session ID visible to the attacker
like H(session_id||H(password)), then the attacker can-- offline--
pick a candidate password and check it with the session IDs they
observed to see if it matches the pattern of curve vs twist. If it
does, it's the right password with probability 1-1/2^observations.

While I'm posting in this thread, most PAKE schemes I looked at in the
past had a bad property of losing their authentication strength if an
attacker can break the underlying cryptosystem (e.g. solve EC DLP).
It seemed to me that they could easily be upgraded by again hashing
the KDFed password into the returned shared secret once the protocol
completes. Such an alteration would reduce the ZK property to
computational for an attacker that can solve ECEL, but this seems to
me to be a good tradeoff vs someone with an unknown attack on the
curve you're using being able to falsely authenticate to everything.
Do any well analyzed PAKE schemes bake this in?

[Björn Haase]

While I'm posting in this thread, most PAKE schemes I looked at in the

Post by Gregory Maxwell
past had a bad property of losing their authentication strength if an
attacker can break the underlying cryptosystem (e.g. solve EC DLP).
It seemed to me that they could easily be upgraded by again hashing
the KDFed password into the returned shared secret once the protocol
completes. Such an alteration would reduce the ZK property to
computational for an attacker that can solve ECEL, but this seems to
me to be a good tradeoff vs someone with an unknown attack on the
curve you're using being able to falsely authenticate to everything.
Do any well analyzed PAKE schemes bake this in?

The original SPEKE paper does so, but I'm not at all convinced that
hashing the password into the resulting key is actually beneficial. I'd
rather advocate for *not* doing it by purpose.

I identify two main aspects.

1.) So as I understand in the security proof of Philip MacKenzie from
2001 for SPEKE (https://eprint.iacr.org/2001/057) it's the exact fact
that the password is hashed into the result key at the very end is the
main reason why the security proof comes to the result that the attacker
might be able to test two passwords at the same time for one single
online login attempt. I consider this result to be rather some kind of
technical defect of the proof strategy and don't believe that there will
ever be a realistic attack. However the use of the password at the end
might complicate the security proof. This might be the reasons why I did
not see this method in protocols that were developped at the same time
with their respective security proof strategy.

2.) The real reason, why I'd avocate on not using the password twice is
side-channel resistance. In many systems the password should be
considered to form the crown jewels to protect with security. The fact
that you have to use the password twice might expose the password to a
higher risk of exposure. See, e.g. the recent Nijmegen paper on
side-channel attacks on SHA512. https://eprint.iacr.org/2017/985

Note also, that for the time being "only" forward secrecy might be
compromised by an quantum computing adversary in the far future. We
don't talk about false authentication at the moment.

In order to provide some level of protection against quantum computers
(QC), I'd rather suggest to use a scheme that hashes the password
together with ephemeral random numbers to a random point and again
hashes the result group element for key derivation at the end. Any PACE
variant will do so, as does the protocol I have suggested earlier in
this thread (which removes the unnecessary SPEKE-Patent-Workarounds from
PACE). As a result, you have two hashes at the beginning and the end
which most likely will never be broken by a QC algorithm.
The adversary might have additional capabilities, but most likely will
be forced to mount a "quantum computing dictionary attack" which
actually might exceed her budget and capabilities.

Yours

Björn

[Arasch Honarbacht]

All, thanks for the lively discussion.

I believe there is some confusion as to how we might want to utilize SPEKE. Let me sketch the current proposal:

Suppose you have a wireless zigbee mesh network. In a centralized zigbee network, there is a single device, the trust center (TC), which admits new devices to the network. The TC has a user interface of some sort (app, web page, touch screen, QR code, NFC reader etc.), which allows out-of-band entry of a password, which is tied to a the 64-bit globally unique MAC hardware address of a device (IEEE EUI-64, you could regard it as a "user ID" in a typical PAKE scenario).

1. The network is typically closed for new devices. The addition of a new devices requires explicit user action on the TC to allow onboarding of new devices. This time window is typically 3 minutes. While the network is open for joining, the device can associate.
2. A joining device has a low-entropy, fixed password, e.g. four hex digits = 16 bit printed on an adhesive label
3. The user enters EUI-64 + password into the TC, e.g. 00:1f:ee:00:12:34:56:78 as the EUI-64 and "A1B2" as the password
4. Both use a hash of A1B2 to determine a common base point on Curve25519 - no salt included in this hash, i.e. G = hash(password). Without Elligator2 we lose one bit of entropy, i.e. instead of 16 bit, we have 15 bit. This is because if we had n possible passwords, the number of passwords is reduced to n/2, as it can be determined whether the base point is on the curve or on its twist.
5. Both the joiner and the TC select a random number ("private key") and obtain a corresponding point on Curve25519 ("public key") by scalar multiplication.

From here it is standard ECDH(E) - with essentially the same security properties.

6. Joiner determines shared secret k by multiplying TC's public point with its own (joiner's) private key
7. TC determines shared secret k by multiplying joiner's public point with its own (TC's) private key

8. Both derive an encryption key for a symmetric key cipher (AES-CCM* in this case) using a KDF.
9. Before using this key, they verify that both have arrived at same encryption key. This is done by the joiner sending a hash of this key to the trust center, and the trust center confirming this (using a message encrypted with the agreed-upon key).

To prevent the attacks identified by Hao and Shahandashti (https://eprint.iacr.org/2014/585.pdf), the encryption key in step 8 is derived by feeding the public points of TC and joiner into the KDF. There is no need for concurrent sessions, so these would be disallowed right away. Alternatively, a session ID could be baked in as well (as suggested by the authors above and done in the 2017 edition of ISO/IEC 11770-4) - but multiple sessions are not required here at all.

We could gain one additional bit of entropy using Elligator2, but it does not seem necessary. If you feel that 15 bit's aren't enough, just add another hex digit to end up at 20 - 1 = 19 bits. All the password does is to provide mutual authentication, i.e. a malicious active attacker would have to impersonate as the white-listed EUI-64 and guess the password in the three minute joining window. Together with appropriate rate limiting (there is already some inherent rate limiting due to channel capacity and processing overhead), this is safe enough - it's guess of one out of M, where M = 2^("effective password entropy"), within the joining window. If higher security is required, a certificate-based scheme could be used (and such schemes already exist in zigbee e.g. ECMQV) - at the expense of having to entertain a PKI.

Is there any concern that Elligator2 could add structure, which could then be exploited?

Best Regards

Arasch

-----Ursprüngliche Nachricht-----
Von: Curves [mailto:curves-***@moderncrypto.org] Im Auftrag von Björn Haase
Gesendet: Sonntag, 5. November 2017 16:56
An: Gregory Maxwell <***@gmail.com>; Andy Isaacson <***@hexapodia.org>
Cc: ***@moderncrypto.org
Betreff: Re: [curves] Fwd: Re: Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?

While I'm posting in this thread, most PAKE schemes I looked at in the

Post by Gregory Maxwell
past had a bad property of losing their authentication strength if an
attacker can break the underlying cryptosystem (e.g. solve EC DLP).
It seemed to me that they could easily be upgraded by again hashing
the KDFed password into the returned shared secret once the protocol
completes. Such an alteration would reduce the ZK property to
computational for an attacker that can solve ECEL, but this seems to
me to be a good tradeoff vs someone with an unknown attack on the
curve you're using being able to falsely authenticate to everything.
Do any well analyzed PAKE schemes bake this in?

The original SPEKE paper does so, but I'm not at all convinced that hashing the password into the resulting key is actually beneficial. I'd rather advocate for *not* doing it by purpose.

I identify two main aspects.

1.) So as I understand in the security proof of Philip MacKenzie from
2001 for SPEKE (https://eprint.iacr.org/2001/057) it's the exact fact that the password is hashed into the result key at the very end is the main reason why the security proof comes to the result that the attacker might be able to test two passwords at the same time for one single online login attempt. I consider this result to be rather some kind of technical defect of the proof strategy and don't believe that there will ever be a realistic attack. However the use of the password at the end might complicate the security proof. This might be the reasons why I did not see this method in protocols that were developped at the same time with their respective security proof strategy.

2.) The real reason, why I'd avocate on not using the password twice is side-channel resistance. In many systems the password should be considered to form the crown jewels to protect with security. The fact that you have to use the password twice might expose the password to a higher risk of exposure. See, e.g. the recent Nijmegen paper on side-channel attacks on SHA512. https://eprint.iacr.org/2017/985

Note also, that for the time being "only" forward secrecy might be compromised by an quantum computing adversary in the far future. We don't talk about false authentication at the moment.

In order to provide some level of protection against quantum computers (QC), I'd rather suggest to use a scheme that hashes the password together with ephemeral random numbers to a random point and again hashes the result group element for key derivation at the end. Any PACE variant will do so, as does the protocol I have suggested earlier in this thread (which removes the unnecessary SPEKE-Patent-Workarounds from PACE). As a result, you have two hashes at the beginning and the end which most likely will never be broken by a QC algorithm.
The adversary might have additional capabilities, but most likely will be forced to mount a "quantum computing dictionary attack" which actually might exceed her budget and capabilities.

Yours

Björn
_______________________________________________
Curves mailing list
***@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves

[Mike Hamburg]

Post by Arasch Honarbacht
All, thanks for the lively discussion.
Suppose you have a wireless zigbee mesh network. In a centralized zigbee network, there is a single device, the trust center (TC), which admits new devices to the network. The TC has a user interface of some sort (app, web page, touch screen, QR code, NFC reader etc.), which allows out-of-band entry of a password, which is tied to a the 64-bit globally unique MAC hardware address of a device (IEEE EUI-64, you could regard it as a "user ID" in a typical PAKE scenario).
1. The network is typically closed for new devices. The addition of a new devices requires explicit user action on the TC to allow onboarding of new devices. This time window is typically 3 minutes. While the network is open for joining, the device can associate.
2. A joining device has a low-entropy, fixed password, e.g. four hex digits = 16 bit printed on an adhesive label
3. The user enters EUI-64 + password into the TC, e.g. 00:1f:ee:00:12:34:56:78 as the EUI-64 and "A1B2" as the password
4. Both use a hash of A1B2 to determine a common base point on Curve25519 - no salt included in this hash, i.e. G = hash(password). Without Elligator2 we lose one bit of entropy, i.e. instead of 16 bit, we have 15 bit. This is because if we had n possible passwords, the number of passwords is reduced to n/2, as it can be determined whether the base point is on the curve or on its twist.

You should probably include the MAC address in the hash, since that’s almost free and makes a precomputed dictionary attack much harder.

Post by Arasch Honarbacht
5. Both the joiner and the TC select a random number ("private key") and obtain a corresponding point on Curve25519 ("public key") by scalar multiplication.
From here it is standard ECDH(E) - with essentially the same security properties.
6. Joiner determines shared secret k by multiplying TC's public point with its own (joiner's) private key
7. TC determines shared secret k by multiplying joiner's public point with its own (TC's) private key
8. Both derive an encryption key for a symmetric key cipher (AES-CCM* in this case) using a KDF.
9. Before using this key, they verify that both have arrived at same encryption key. This is done by the joiner sending a hash of this key to the trust center, and the trust center confirming this (using a message encrypted with the agreed-upon key).
To prevent the attacks identified by Hao and Shahandashti (https://eprint.iacr.org/2014/585.pdf), the encryption key in step 8 is derived by feeding the public points of TC and joiner into the KDF. There is no need for concurrent sessions, so these would be disallowed right away. Alternatively, a session ID could be baked in as well (as suggested by the authors above and done in the 2017 edition of ISO/IEC 11770-4) - but multiple sessions are not required here at all.
We could gain one additional bit of entropy using Elligator2, but it does not seem necessary.

I agree. If you only do one authentication ever, or only authenticate with the same salt, then Elligator2 probably isn’t necessary.

Post by Arasch Honarbacht
If you feel that 15 bit's aren't enough, just add another hex digit to end up at 20 - 1 = 19 bits. All the password does is to provide mutual authentication, i.e. a malicious active attacker would have to impersonate as the white-listed EUI-64 and guess the password in the three minute joining window. Together with appropriate rate limiting (there is already some inherent rate limiting due to channel capacity and processing overhead), this is safe enough - it's guess of one out of M, where M = 2^("effective password entropy"), within the joining window. If higher security is required, a certificate-based scheme could be used (and such schemes already exist in zigbee e.g. ECMQV) - at the expense of having to entertain a PKI.
Is there any concern that Elligator2 could add structure, which could then be exploited?

For PAK it provably does not add exploitable structure. I’m not sure about SPEKE, but I would guess the same. You do have to eliminate the cofactor, but X25519’s scalar clamping does that automatically.

Post by Arasch Honarbacht
Best Regards
Arasch

Best,
— Mike

Post by Arasch Honarbacht
-----UrsprÃŒngliche Nachricht-----
Gesendet: Sonntag, 5. November 2017 16:56
Betreff: Re: [curves] Fwd: Re: Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?
While I'm posting in this thread, most PAKE schemes I looked at in the

Post by Gregory Maxwell
past had a bad property of losing their authentication strength if an
attacker can break the underlying cryptosystem (e.g. solve EC DLP).
It seemed to me that they could easily be upgraded by again hashing
the KDFed password into the returned shared secret once the protocol
completes. Such an alteration would reduce the ZK property to
computational for an attacker that can solve ECEL, but this seems to
me to be a good tradeoff vs someone with an unknown attack on the
curve you're using being able to falsely authenticate to everything.
Do any well analyzed PAKE schemes bake this in?

The original SPEKE paper does so, but I'm not at all convinced that hashing the password into the resulting key is actually beneficial. I'd rather advocate for *not* doing it by purpose.
I identify two main aspects.
1.) So as I understand in the security proof of Philip MacKenzie from
2001 for SPEKE (https://eprint.iacr.org/2001/057) it's the exact fact that the password is hashed into the result key at the very end is the main reason why the security proof comes to the result that the attacker might be able to test two passwords at the same time for one single online login attempt. I consider this result to be rather some kind of technical defect of the proof strategy and don't believe that there will ever be a realistic attack. However the use of the password at the end might complicate the security proof. This might be the reasons why I did not see this method in protocols that were developped at the same time with their respective security proof strategy.
2.) The real reason, why I'd avocate on not using the password twice is side-channel resistance. In many systems the password should be considered to form the crown jewels to protect with security. The fact that you have to use the password twice might expose the password to a higher risk of exposure. See, e.g. the recent Nijmegen paper on side-channel attacks on SHA512. https://eprint.iacr.org/2017/985
Note also, that for the time being "only" forward secrecy might be compromised by an quantum computing adversary in the far future. We don't talk about false authentication at the moment.
In order to provide some level of protection against quantum computers (QC), I'd rather suggest to use a scheme that hashes the password together with ephemeral random numbers to a random point and again hashes the result group element for key derivation at the end. Any PACE variant will do so, as does the protocol I have suggested earlier in this thread (which removes the unnecessary SPEKE-Patent-Workarounds from PACE). As a result, you have two hashes at the beginning and the end which most likely will never be broken by a QC algorithm.
The adversary might have additional capabilities, but most likely will be forced to mount a "quantum computing dictionary attack" which actually might exceed her budget and capabilities.
Yours
Björn
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

[Björn Haase]

Hello to all,

as a follow up of this rather old thread, I would like to draw your
attention to the paper project I have been mentioning in this thread. 
Benoit Labrique and me finally have written down our idea of a V-PAKE
solution tailored to IIoT applications. It's now online at the IACR eprints.

https://eprint.iacr.org/2018/286.pdf

It's essentially a SPEKE variant working with an ephemeral generator
that is constructed by use of Elligator2.

@Mike: Again thank's for your advice regarding avoiding one field
exponentiation for calculating Elligator2. We have now explicitly
written down the respective formulas.

Yours,

Björn

P.S.:

The paper also gives speed figures on Cortex M4. We, BTW, come to the
conclusion that FourQ is indeed faster than Curve25519, but however
unlike statements in the recent FourQ papers, the speed advantage might
rather be some 20 % to 30% on Cortex M4 and not an integer factor. Also
the speed advantage of FourQ comes, in our opinion at the cost of
significantly increased complexity and ram/flash size.

Post by Arasch Honarbacht
All, thanks for the lively discussion.
Suppose you have a wireless zigbee mesh network. In a centralized zigbee network, there is a single device, the trust center (TC), which admits new devices to the network. The TC has a user interface of some sort (app, web page, touch screen, QR code, NFC reader etc.), which allows out-of-band entry of a password, which is tied to a the 64-bit globally unique MAC hardware address of a device (IEEE EUI-64, you could regard it as a "user ID" in a typical PAKE scenario).
1. The network is typically closed for new devices. The addition of a new devices requires explicit user action on the TC to allow onboarding of new devices. This time window is typically 3 minutes. While the network is open for joining, the device can associate.
2. A joining device has a low-entropy, fixed password, e.g. four hex digits = 16 bit printed on an adhesive label
3. The user enters EUI-64 + password into the TC, e.g. 00:1f:ee:00:12:34:56:78 as the EUI-64 and "A1B2" as the password
4. Both use a hash of A1B2 to determine a common base point on Curve25519 - no salt included in this hash, i.e. G = hash(password). Without Elligator2 we lose one bit of entropy, i.e. instead of 16 bit, we have 15 bit. This is because if we had n possible passwords, the number of passwords is reduced to n/2, as it can be determined whether the base point is on the curve or on its twist.
5. Both the joiner and the TC select a random number ("private key") and obtain a corresponding point on Curve25519 ("public key") by scalar multiplication.

Post by Arasch Honarbacht
From here it is standard ECDH(E) - with essentially the same security properties.

6. Joiner determines shared secret k by multiplying TC's public point with its own (joiner's) private key
7. TC determines shared secret k by multiplying joiner's public point with its own (TC's) private key
8. Both derive an encryption key for a symmetric key cipher (AES-CCM* in this case) using a KDF.
9. Before using this key, they verify that both have arrived at same encryption key. This is done by the joiner sending a hash of this key to the trust center, and the trust center confirming this (using a message encrypted with the agreed-upon key).
To prevent the attacks identified by Hao and Shahandashti (https://eprint.iacr.org/2014/585.pdf), the encryption key in step 8 is derived by feeding the public points of TC and joiner into the KDF. There is no need for concurrent sessions, so these would be disallowed right away. Alternatively, a session ID could be baked in as well (as suggested by the authors above and done in the 2017 edition of ISO/IEC 11770-4) - but multiple sessions are not required here at all.
We could gain one additional bit of entropy using Elligator2, but it does not seem necessary. If you feel that 15 bit's aren't enough, just add another hex digit to end up at 20 - 1 = 19 bits. All the password does is to provide mutual authentication, i.e. a malicious active attacker would have to impersonate as the white-listed EUI-64 and guess the password in the three minute joining window. Together with appropriate rate limiting (there is already some inherent rate limiting due to channel capacity and processing overhead), this is safe enough - it's guess of one out of M, where M = 2^("effective password entropy"), within the joining window. If higher security is required, a certificate-based scheme could be used (and such schemes already exist in zigbee e.g. ECMQV) - at the expense of having to entertain a PKI.
Is there any concern that Elligator2 could add structure, which could then be exploited?
Best Regards
Arasch
-----Ursprüngliche Nachricht-----
Gesendet: Sonntag, 5. November 2017 16:56
Betreff: Re: [curves] Fwd: Re: Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?
While I'm posting in this thread, most PAKE schemes I looked at in the

Post by Arasch Honarbacht
past had a bad property of losing their authentication strength if an
attacker can break the underlying cryptosystem (e.g. solve EC DLP).
It seemed to me that they could easily be upgraded by again hashing
the KDFed password into the returned shared secret once the protocol
completes. Such an alteration would reduce the ZK property to
computational for an attacker that can solve ECEL, but this seems to
me to be a good tradeoff vs someone with an unknown attack on the
curve you're using being able to falsely authenticate to everything.
Do any well analyzed PAKE schemes bake this in?

The original SPEKE paper does so, but I'm not at all convinced that hashing the password into the resulting key is actually beneficial. I'd rather advocate for *not* doing it by purpose.
I identify two main aspects.
1.) So as I understand in the security proof of Philip MacKenzie from
2001 for SPEKE (https://eprint.iacr.org/2001/057) it's the exact fact that the password is hashed into the result key at the very end is the main reason why the security proof comes to the result that the attacker might be able to test two passwords at the same time for one single online login attempt. I consider this result to be rather some kind of technical defect of the proof strategy and don't believe that there will ever be a realistic attack. However the use of the password at the end might complicate the security proof. This might be the reasons why I did not see this method in protocols that were developped at the same time with their respective security proof strategy.
2.) The real reason, why I'd avocate on not using the password twice is side-channel resistance. In many systems the password should be considered to form the crown jewels to protect with security. The fact that you have to use the password twice might expose the password to a higher risk of exposure. See, e.g. the recent Nijmegen paper on side-channel attacks on SHA512. https://eprint.iacr.org/2017/985
Note also, that for the time being "only" forward secrecy might be compromised by an quantum computing adversary in the far future. We don't talk about false authentication at the moment.
In order to provide some level of protection against quantum computers (QC), I'd rather suggest to use a scheme that hashes the password together with ephemeral random numbers to a random point and again hashes the result group element for key derivation at the end. Any PACE variant will do so, as does the protocol I have suggested earlier in this thread (which removes the unnecessary SPEKE-Patent-Workarounds from PACE). As a result, you have two hashes at the beginning and the end which most likely will never be broken by a QC algorithm.
The adversary might have additional capabilities, but most likely will be forced to mount a "quantum computing dictionary attack" which actually might exceed her budget and capabilities.
Yours
Björn
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves