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

Björn Haase bjoern.m.haase at web.de
Sun Nov 5 07:55:57 PST 2017

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.



More information about the Curves mailing list