[curves] Fwd: Re: Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?

[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.


Am 06.11.2017 um 12:37 schrieb 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-bounces at moderncrypto.org] Im Auftrag von Björn Haase
> Gesendet: Sonntag, 5. November 2017 16:56
> An: Gregory Maxwell <gmaxwell at gmail.com>; Andy Isaacson <adi at hexapodia.org>
> Cc: curves at 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
>> 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
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
>