[Cfrg] My review of OPAQUE

[Bill Cox <[e-mail]>]

Please let me know if this is the wrong way to post a PAKE review.  If I
understood an email from this morning, I am supposed to post it to the CFRG
list so it becomes part of the CFRG archive.  As always, my opinion is
worth what you paid for it.
Summary

Overall, I am very impressed with what the OPAQUE authors have accomplished
so far.  I suspect OPAQUE may have far wider impact than any pure PAKE
scheme. In a world that uses OPAQUE to its full potential, devices would
authenticate with their device-specific password-authenticated key pairs,
and password-derived bearer tokens would be a thing of the past.
Significant portions of our authentication flows could be rewritten to be
both simpler and more secure. Fewer user credential database leaks would
result in revealing passwords. In combination with two-factor
authentication such as Webauthn, users would be protected by both something
they have, and something they know, but servers would only store the user’s
password-and-OPRF-derived public keys.  Entering passwords would only be
required for the new-device problem, for occasional reauth, and to help the
use remember their passwords. Low entropy passwords would be good enough
for most use cases, and we could drop the cumbersome password rules.

Further, password-authenticated end-to-end encryption between devices would
be come a simple extension to OPAQUE.  It could also be used with a
vendor-independent scheme like the Mathematical Mesh, or a password manager
like SPHINX. In short, there is room for re-imagining authentication flows,
and they look a lot more promising in a world with OPAQUE.

All that said, OPAQUE provides a new primitive, rather than aPAKE or PAKE.
If the authors finish the specification to the level of quality seen so
far, I think the CFRG should recommend it, not as the “officially
recommended PAKE”, but as the “officially recommended OPRF-PAKE” scheme.
The CFRG should also recommend an OPRF scheme, an aPAKE scheme, and a
symmetric PAKE scheme: the world needs these primitives, too.  Preferably,
officially recommended OPAQUE schemes should rely on officially recommended
OPRF and aPAKE schemes, rather than different PAKE schemes as seems to be
the case currently.

Including OPAQUE in the PAKE selection is weird.  It is like considering
HMAC in a hash function competition.  Choosing OPAQUE as the official PAKE
winner would be like choosing HMAC-Skein as the winner for the officially
recommended hash function.

The CFRG can do the world a lot of good by recommending one or more
specific OPAQUE instantiations.  Any recommended instantiation should rely
on recommended primitives.
Advice for the authors

   1.

   Specify one or more recommended password hashing schemes, preferably
   including a memory-hard scheme like Argon2 rather than iterations of
   hashing.
   2.

   Leave less up to the implementer: This can be done by providing complete
   reference implementations for suggested modes of operation.
   3.

   Work with the CFRG to have OPAQUE use CFRG recommended OPRF and aPAKE
   solutions, rather than competing with them.
   4.

   Append the authentication URL to the password, as is done in SPHINX, to
   resist phishing attacks.
   5.

   Continue to aim higher: instead of aiming to be the officially
   recommended PAKE scheme, continue to try to change the world in ways a pure
   PAKE scheme cannot.


As a great example of 5), I see the OPAQUE authors also did excellent work
on SPHINX <https://eprint.iacr.org/2018/695.pdf>.
Comparisons

It is not clear to me what OPAQUE should be compared to, since it is a new
combined primitive rather than an OPRF or PAKE scheme.  I’ll attempt to
compare it to OPRFs, PAKEs, and schemes that simply do an OPRF followed by
authentication.
OPRF alone

The OPAQUE authors recommend an efficient OPRF scheme.  It is unclear to me
how it fits into the effort to recommend an OPRF, but this scheme is very
efficient.  On its own, I feel comfortable recommending OPAQUE’s OPRF
scheme.

Since OPAQUE has a different set of secrets per user, the secrets can be
split server-side in a Shamir sharing scheme which is compatible with their
OPRF function.  However, this requires splitting every user secret. Also,
since OPAQUE requires one or more secrets per user, these secrets will
likely be secured in a manner similar to the old password hash databases.
If an attacker can read the OPAQUE user credential database, it is fairly
likely that the attacker will also be able to read the user-OPRF-secret
database, enabling brute-force attacks against passwords. This is why good
password hashing remains critical in OPAQUE.

In reality, some secrets are better protected than other secrets.  Consider
TLS root signing keys vs cleartext passwords, for example.  It is more
likely a cloud provider can strongly protect a single OPRF secret than
protect a database of user-specific secrets.

At the same time, there needs to be a scheme for rotating OPRF secrets.
OPAQUE deals with this cleanly, enabling rotation whenever a user
authenticates by entering their password.

The trade-offs here are complex.  For example, it is desirable to
rate-limit password guessing.  The OPRF service, if using a shared secret s
for all users, will return s*P, when given an EC point P from a user.  The
user can pretend to login with a different userID over and over, defeating
rate-limiting by the OPRF server. OPAQUE defeats this with user-specific
secrets.

An alternative scheme is for the server-side secret to be hashed with the
userID to defeat such attacks, fixing rate-limiting.  However, if this is
done, the server-side secret is no longer compatible with Shamir secret
sharing. Single-secret OPRF schemes that have both support for rate
limiting and compatibility with Shamir secret sharing are more complex and
slower than OPAQUE’s scheme.

Given the complexity of such trade-offs, OPAQUE’s scheme is a reasonable
compromise.

Pros:

   -

   Very efficient
   -

   Simple
   -

   Takes secret rotation into account: can rotate during any password
   authentication
   -

   Compatible with rate-limiting by the OPRF server
   -

   Compatible with per-user Shamir secret sharing

Cons:

   -

   Server must maintain user-specific OPRF secrets
   -

   OPRF server must query the OPRF secret database for each query
   -

   Security of user-specific OPRF secrets is probably no better than
   today’s password hash databases.

aPAKE alone

OPAQUE can be used with many aPAKE schemes, and probably it should use one
of the eventual recommended aPAKE primitives.  It currently recommends HMQV
and SIGMA, both of which are interesting aPAKE schemes.

I read only SIGMA, being the simpler of the two.  SIGMA has properties I
find attractive. In particular, authentication becomes asymmetric key
based, and the server stores only the client’s public key.

The OPAQUE authors justify their choices in their RFC, and I see no obvious
flaws in their arguments.  My only advice here is for the OPAQUE authors to
provide an instantiation that uses the eventual CFRG recommended aPAKE
scheme.
OPRF + authentication

The OPAQUE authors likely would agree that there is room for additional
research into OPRF + authentication schemes, where any resulting shared key
is not used.  Evidence of this appears in their work on SPHINX
<https://eprint.iacr.org/2018/695.pdf>.  This section will compare OPAQUE
to SHINX for the use case of authentication.

Password authenticated key exchange schemes result in shared secrets that
can be used to secure a communication channel.  However, passwords are
typically sent over TLS encrypted channels today. There are good reasons to
continue authentication over TLS encrypted channels: eg the user ID is sent
to the OPRF server in the clear in OPAQUE, which might be sensitive
information, such as a user’s email address.  A good use case for OPAQUE
appears to be password-based user authentication over a TLS-secured
channel, where the resulting shared secret is most likely never used.

In such a scheme, the aPAKE is replaced with a traditional
proof-of-possession or zero-knowledge-proof of the OPRF-strengthened
password-derived private key, or the password-derived key is converted into
a strong site-specific password, as is done in SPHINX.  Compared to such a
scheme, OPAQUE has plusses and minuses:

Pros:

   -

   Provides forward-secret shared key, which may have some use cases.
   -

   No more messages than OPRF + generated strong password based auth
   (SPHINX)
   -

   Unlike strong-hash base schemes, OPAQUE sends no bearer tokens that can
   be used by an attacker to authenticate as the user.

Cons:

   -

   Requires auth server-side changes, unlike SPHINX.
   -

   Somewhat higher complexity.
   -

   Less compatibility with existing infrastructure than a scheme like
   SPHINX.
   -

   The OPRF is not easily provided by a different cloud provider than the
   auth server.
   -

   Auth server needs to communicate with OPRF server to compete key
   agreement.
   -

   In real implementations, the OPRF server will often be combined with the
   aPAKE server, increasing the odds that an attacker will learn both the OPRF
   secrets and aPAKE credentials, enabling the attacker to launch brute-force
   password guessing attacks.
   -

   Password hashing is entirely the responsibility of the client.  This
   likely makes dictionary attacks more cost effective when an attacker knows
   both the OPRF secrets and user credentials.


There appears to be some good reasons to use an OPRF+auth like
SPHINXinitially, and later switching to OPAQUE.  SPHINX
<https://eprint.iacr.org/2018/695.pdf> requires no server-side changes, and
is insantly compatible with a wide range of web sites.  However, SPHINX
continues the practice of sending bearer tokens over the wire, and as
history has shown, they are likely to be accidentally logged server-side.
An eventual migration to a scheme like OPAQUE may make sense.

Bill