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-boun...@moderncrypto.org] Im Auftrag von Björn Haase
Gesendet: Sonntag, 5. November 2017 16:56
An: Gregory Maxwell <gmaxw...@gmail.com>; Andy Isaacson <a...@hexapodia.org>
Cc: curves@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@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
Curves@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
