Subject: [Cfrg] My review of the four PAKEs

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 25 Feb 2020 20:45:47 +0000

Summary of my vote: Balanced PAKE: CPace; Augmented PAKE: OPAQUE
CPace vs SPAKE2 reasoning:
My opinion is essentially unchanged from my initial review.  The difference comes down to the superior Quantum Annoyance of CPace vs the implementation simplicity and potential side channel resistance of SPAKE2 (CPace absolutely needs a side channel free hash-to-curve routine; even if SPAKE2 is used with a hash-to-curve algorithm, it needn't be side channel resistant).  Even though SPAKE2 has potentially improved its Quantum Annoyance ("potentially" because it's now an option, and so the protocol might not decide to use it), it's still not to the level that CPace gives.  I am of the opinion that factor outweighs the implementation issues.
Opaque vs AuCPace reasoning:
I did not review Opaque for the previous round; when I reviewed it for this round, I was impressed.  It uses fewer messages than AuCPace (even with AuCPace reducing the round trips it requires for this round); this makes it easier to insert into existing protocols.  In addition, Opaque uses potentially less computation and to be, in general, a cleaner design.  In addition, after the first pass, both sides have the other's public signature key; this may mean that a protocol using it might have the option of using Opaque as a certificate replacement (and processing the signatures using its own logic rather than using Sigma).  I do see two downsides; for one, both the client and the server have long-term public signature keys, and I don't see a clean way (apart from re-registration) to update those public keys.  In addition, Opaque is not Quantum Annoying (a single DLog by a passive attacker would allow a dictionary search) - the submitters tried to argue that wasn't important, see below why I disagree with that assessment.  Despite those two points, I believe that, in this case, the practical issues outweigh this lack of Quantum Annoyance and the rekeying difficulties.
More detailed review (and random thoughts):
SPAKE2:
In response to question 1, they did add an option that would allow M and N to be different for every single pair of peers; they also added an option that allows M=N.  I would further note that, because the Hash2Curve operation is on public data, including that operation does not add potential side channel vulnerabilities.  While this mitigates the vulnerability of solving one DLog problem breaks the system globally, it still cannot be considered fully "quantum annoying" (although it is better) - solving one discrete log problem (as an active attacker) or two discrete log problems (as a passive attacker) would still allow a dictionary attack (and in the passive case, also recover the shared secret on the session under attack).  One issue I have is that the draft gives no guidance to the protocol designer as to when the various options (fixed vs dynamic N, M; distinct N, M vs identical) should be used (and it can be assumed that if we don't give such guidance, the protocol designers will select the cryptographically worse option).
CPace and AuCPace:
In response to question 5, they suggested that a postquantum version of (Au)CPace might be able to be done using Isogenies.  I am personally skeptical about that - the chief issue is that the protocol receives a Ya/Yb value from the peer, and uses it to compute the shared secret.  An active attacker would be able to submit a malicious Ya/Yb value; if he selects a value that (after transformation by the honest peer) maps to a comparatively small set of values, then the attacker could guess the shared secret (and log in, even though he did not know the password).  Sanity checking these received values would be mandatory, and with isogenies there is no obvious way to do so.
One advantage of accepting both CPace and AUCPace would be so that a protocol that needs both would be able to take advantage of the commonality.  I personally don't expect protocols to use both a balanced and an augmented PAKE; I believe most protocols are either strictly peer-to-peer or strictly client-server (and hence this need not be a major consideration).
OPAQUE:
The Opaque paper emphasizes that, with Opaque, an attacker who managed to recover the client database would not be able to use precomputation to help recover the passwords; he would need to perform all the computations involved with the dictionary search after he has recovered the password file.  I don't believe that's that important (at least, with comparison to AuCPace).  With AuCPace, an attacker could use precomputation, however any such precomputation would be usable only against a single user on a single server.  So, the difference is that, in both cases, the attacker uses X time to recover a single password; it's just that in the AuCPace case, the attacker may choose to perform that computation beforehand; however that computation result cannot be reused to recover any other session (either on the same server, or the same user logging into a different one).  Given that the attacker doesn't get any time savings for attacking multiple logins, I don't see when the attacker performs the computation as that critical (hence I did not mention it above).
The submitters tried to argue that our current understanding of Quantum Annoyance isn't what's important, and that they are the only submission that can be made Quantum Resistant to store-and-decrypt-latter Quantum Attacks.  I disagree on both points.  For one, any protocol that we endorse will likely to continue to be used 20 years from now, and so Quantum Attacks that recover the password are a nontrivial concern (even though, as my review above states, perhaps not the overriding concern).  In addition, any PAKE can be made resistant to store-and-decrypt-latter attacks (by simply performing an additional Quantum Safe KEM at the end, authenticated by the PAKE shared secret).  I note that, for AuCPace (OPAQUE's sole competitor), this can be done in parallel with the Explicit Mutual Authentication step, and so might not cost you an addition pass.
I would be nice if they had a Quantum-Safe OPRF (which would allow the entire structure to be Quantum Safe); however, I am unaware of any such construction.
Also, my opinion of Question 5: although none of the candidates are currently directly translatable to postquantum primitives, I don't know if that's actually a big deal.  When the CFRG feels the need to propose a postquantum PAKE, I would suggest we would have another contest specifically for that purpose; at the very least, there exists https://eprint.iacr.org/2014/589.pdf as a balanced postquantum PAKE candidate.

---

From: Björn Haase <[email-masked]>
Date: Wed, 26 Feb 2020 10:21:28 +0000

Dear Scott,

thank you for your careful review. I agree with all of your assessments. 

Specifically I agree that for the use-case of a direct integration of an augmented PAKE 
into TLS 1.3, OPAQUE is better. The feature that OPAQUE requires one round-trip less 
than AuCPace might outweight the single practical disadvantage that I see (the *large* 
size of password verifiers) in many scenarios.

Still from a system-level architecture point of view, I believe that there could be 
applications, where too neatly integrating the human-user related mechanisms into 
a transport-layer level component such as TLS might generate headaches.

I still would like to suggest to consider/discuss the following points.

- The augmented PAKE use-case is in my opinion directly linked to human 
  end-user authentication. This is different from the case for balanced 
  PAKE, where I also see the application of machine-machine interfaces.
  
- This means that a TLS subsystem using OPAQUE might have to maintain a
  quite close and possibly intricate link to software components that a)
  maintain the user credential database and b) the applications that
  use the TLS channel.
  For instance, TLS would have to provide interfaces to the application
  on the server side for retrieving the information which user has 
  successfully logged in.
  
- For many applications, I also see the need of a lot of flexibility.
  Sometimes users might not want to enter passwords but use
  Security tokens alone.
  Others would like to use username/passwords, and possibly
  TLS with OPAQUE.
  Other might require supporting two-factor  authentication 
  (TFA, username/password + security hardware).
  Managing all of these 3 settings while maintaining the same software-level
  structure might require not only require TLS cipher suites for OPAQUE but also
  TLS OPAQUE+Security-Token and TLS-Security-Token.
  Possibly for TLS this could result in a complexity that is no
  longer practical.
  
- I also see some unsolved issues for applications that need to migrate an 
  existing user-credential database to OPAQUE.

My personal assessment is that too closely integrating human user-interface
related complexity into a component such as TLS might generate trouble ?.

Here I see advantages for a more modular approach, as I had also tried to 
sketch in:

https://github.com/BjoernMHaase/fe25519/blob/master/Concept_For_Modularized_PAKE_integration_into_TLS_20190726.pdf

Basically the idea is to try to keep the intricate complexity of human 
user-related API interfaces away from the transport-layer components such 
as TLS. Instead TLS would be focusing on the transport-layer aspects and
the intricate human-user interfaces would be integrated into software modules
external to TLS, e.g. in the style of PAM on Linux.

Of course there is the risk of integrating insecure options (e.g. the EAP approach
might be overly flexible). On the other hand if we are too restrictive/monolithic,
we might not be serving important use-cases.

In my opinion the considerations regarding internal software APIs and
the respective scope/responsibilities of software components such as 
TLS / QUIC / PAM would benefit from discussions with people also from 
outside the typical CFRG team.

I believe that at the end of the discussion involving the system architects
for components such as PAM, there might be applications that are actually 
better served by the a more modular approach such as AuCPace.?

I have already tried to enter a discussion with the PAM people, but did not yet
receive any feedback. Maybe some other people on the CFRG list have such
contacts or suggestions regarding this topic.

Maybe somebody else on this list might have an idea on how to get into
discussion with people that have the "system-level" and "os architecture level" 
hat on.

Yours,

Björn.

Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware
Endress+Hauser Liquid Analysis

Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: +49 7156 209 377 | Fax: +49 7156 209 221
[email-masked] |  www.conducta.endress.com 

Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.

Von: Cfrg <[email-masked]> Im Auftrag von Scott Fluhrer (sfluhrer)
Gesendet: Dienstag, 25. Februar 2020 21:46
An: [email-masked]
Betreff: [Cfrg] My review of the four PAKEs

Summary of my vote: Balanced PAKE: CPace; Augmented PAKE: OPAQUE ...