Subject: [Cfrg] Potential vulnerabilities with OPAQUE

From: Julia Len <[email-masked]>
Date: Wed, 18 Mar 2020 20:55:04 -0400

Dear CFRG,

I am a PhD student at Cornell studying applied cryptography; recently, I
have been analyzing the OPAQUE protocol along with my collaborators, Paul
Grubbs and Tom Ristenpart. We believe there are subtleties with the
protocol that should be given attention. In particular, it uses an
authenticated encryption (AE) scheme that needs to satisfy what the authors
call random-key robustness (RKR): intuitively, it should be hard to
construct an AE ciphertext that decrypts under multiple random keys.
However, the authors do not explain what attacks RKR prevents and are vague
in giving guidance about design choices for RKR AE.

If an RKR AE scheme is not used in OPAQUE, we have developed a theoretical
attack that results in an exponential speedup in online password guessing.
Though our attack is still theoretical (we are working on a
proof-of-concept now), we believe it is relevant to the ongoing aPAKE
standardization effort for two main reasons: first, because in the absence
of widespread library support for RKR secure schemes, practitioners are
likely to misunderstand or ignore the requirement (we have found several
implementations that do exactly this, see below). The second reason the
attack is relevant is that the guidance given in the current RFC, if
followed by practitioners in a natural way, will not necessarily prevent
the attack -- some of the recommended AE schemes have timing side channels
in decryption that enable the attack, even though they are RKR secure on
paper.

During client login, an attacker that impersonates the server can learn a
client’s password efficiently via an online guessing attack. More
specifically, the attacker can split the dictionary of passwords into two
sets of equal size and, using the fact that the AE scheme is not robust,
compute a ciphertext that can be decrypted by all the passwords in one set
but not the other. When the user attempts to log in, decryption of the AE
envelope will either succeed or fail depending on in which set the password
is, thereby allowing the attacker to narrow the set of potential passwords
by half. Continuing in this way, only log(n) impersonations are required to
learn a client’s password from a dictionary of size n.

There are already several implementations of OPAQUE, and a few do utilize
RKR AE, such as Encrypt-then-HMAC. However, many others do not. These
implementations use dedicated AEAD schemes implemented in popular libraries
such as libsodium. The schemes in these libraries are typically AES-GCM or
XSalsa20/Poly1305, neither of which is RKR-secure.

Currently, the RFC draft for OPAQUE does suggest a way to make GCM key
robust: append an all-zeros block to the end of the plaintext and check if
this block remains intact after decryption. However, the obvious way for
practitioners to implement this check results in a timing side channel that
allows detecting decryption failure, re-enabling the attack described
above. That is, the attacker could detect whether decryption failed because
decryption of the ciphertext itself failed or because decryption succeeded
but the zeros check failed. We believe this vulnerability is likely to
happen: practitioners will use libraries that already implement AES-GCM and
XSalsa20/Poly1305 and prevention requires modifying these libraries. Aside
from timing, other side channels, like application-level error messages (as
in the classical padding oracle attack) or cache-level access patterns,
could result in distinguishable decryption failures that enable the attack.

The attacks we outlined show that much of OPAQUE’s practical security
against online attacks hinges on RKR and, furthermore, RKR does not always
prevent these attacks. If OPAQUE is selected for standardization, then
there should be clear guidelines for practitioners about which AE schemes
are appropriate to use, as well as which are not, and an emphasis that
using these schemes is a necessity for secure deployment. While we are
still exploring the best ways to mitigate these attacks, we have some
suggestions. In particular, Encrypt-then-HMAC is RKR secure and should be
the only AE scheme recommended for use currently (the “fixed-string MAC”
transform described in the RFC does not guarantee RKR unless the MAC is
collision-resistant and, moreover, also suffers from side-channel attacks).
We are also working on a variant of GCM that we believe will be both RKR
and immune to the timing side channel attack we described above.

Sincerely,
Julia Len

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 19 Mar 2020 20:10:58 -0400

Julia's (and her co-authors) post requires some important clarifications to
avoid confusion about the security of OPAQUE.

The observations described in Julia's email point to some subtleties in the
implementation of RKR schemes which form one component of  OPAQUE. This is
good as it helps in choosing instantiations of this primitive, e.g., by
identifying  the care needed in one candidate scheme to avoid side channel
attacks. The bottom line, however, is that the simplest and main
instantiation offered in the OPAQUE paper and internet draft
(encrypt-then-HMAC) is secure and more robust to implementation attacks.

This being said, I feel that the subject line of this email and some of the
tone in its language may lead readers of this thread to believe that the
new work is unearthing some significant weaknesses in the protocol design
or even its analysis. I am sure this was not the authors' intention but I
do feel that it is worth setting the record straight particularly given the
current process of selecting a PAKE protocol.

The analysis and proof of OPAQUE fully recognizes the necessity of RKR
schemes, proving it as a necessary and sufficient property of encryption -
in addition to other standard requirements of course. The OPAQUE paper, in
addition to its proof, is careful about highlighting this requirement with
a short section dedicated to it and explaining its necessity via a
not-so-vague attack. The paper also has encrypt-then-HMAC as the preferred
instantiation making  explicit the need for a collision resistant MAC,
hence HMAC (which coincides with the preferred RKR implementation advised
in this email). The OPAQUE authors were fully aware of attacks at the basis
of this new work, and the authors of this new reported work have personal
evidence for that. The internet draft contains secure schemes as potential
instantiations of RKR encryption including encrypt-then-MAC as the most
robust. The work in this email does identify potential side channel risks
on one of them which is important to know.

There is a claim in the email about many OPAQUE implementations not using
the correct RKR schemes. First, I am glad to hear there are many. I only
knew about two or three experimental implementations. The OPAQUE paper is
not a source to build secure implementations and the OPAQUE i-d, while more
explicit about schemes, is also very explicit (even in the abstract) about:

This draft presents a high-level description of OPAQUE highlighting
   its components and modular design.  A detailed unambiguous
   specification for standardization will be presented in future
   revisions of this document, or separately.

The most important consequence of this discussion is that I fully agree
with the authors in their conclusion:

>  Encrypt-then-HMAC is RKR secure and should be the only AE scheme
recommended for use currently

Lastly, the whole subject of RKR encryption can be bypassed as the OPAQUE
i-d specifies (end of section 3.1.1) in its authentication-only envelope
variant.

And to more important stuff: My best wishes to everyone, be careful, stay
home if you can, and be well!

Hugo

On Thu, Mar 19, 2020 at 10:17 AM Julia Len <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Julia Len <[email-masked]>
Date: Sat, 21 Mar 2020 12:55:00 -0400

We agree with Hugo in that if an RKR scheme is properly implemented,
without the side channel weakness we previously mentioned, then OPAQUE is
secure. Our email was not meant to discourage choosing OPAQUE for
standardization but rather to inform the community about potential
implementation vulnerabilities that we might be able to preemptively avoid
with more precise guidance.

We recognize that the OPAQUE i-d is meant only as a high-level description.
However, the guidance currently presented in the OPAQUE i-d, even if only
meant to be high-level, is likely to encourage vulnerabilities: there are 3
suggestions for implementing a key-robust AuthEnc scheme in section 3.1.1,
and 2 out of those 3 suggestions could lead to side-channel attacks if
implemented in the natural way.

Indeed, the guidance about using an RKR AE scheme is already being ignored
in prototype implementations. GCM and XSalsa20/Poly1305 are two of the most
widely used AEAD schemes today, with widespread library support and
standardization. Furthermore, to our knowledge, there is no standard or
official documentation about implementing Encrypt-then-HMAC. Given this, we
think it is likely that practitioners would choose to utilize standardized
schemes such as GCM instead of Encrypt-then-HMAC, misunderstanding that
they are not RKR-secure. Explicit warnings in future documentation against
using these AEAD schemes could remedy this.

There is a specification in 3.1.1 for an authentication-only envelope
variant, but much of our discussion still applies. This scheme requires the
use of a key-robust MAC, and if something like Poly1305 were to be used,
the attack would still be viable. The i-d does recommend the use of HMAC,
but the i-d might be strengthened to explicitly recommend against
non-key-robust MACs.

Now is an important time to surface these issues, before any
standardization decisions are made and, if OPAQUE is chosen, before any
documentation is written, so that we can provide practitioners with the
most concrete guidelines that will ensure secure deployment. Our hope is
that exploring these subtleties now will lead to discussions about how to
best move forward with providing such guidelines.

Sincerely,
Julia

On Thu, Mar 19, 2020 at 8:11 PM Hugo Krawczyk <[email-masked]>
wrote:

> Julia's (and her co-authors) post requires some important clarifications
> to avoid confusion about the security of OPAQUE.
>
> The observations described in Julia's email point to some subtleties in
> the implementation of RKR schemes which form one component of  OPAQUE. This
> is good as it helps in choosing instantiations of this primitive, e.g., by
> This being said, I feel that the subject line of this email and some of
> the tone in its language may lead readers of this thread to believe that
> the new work is unearthing some significant weaknesses in the protocol
> design or even its analysis. I am sure this was not the authors' intention
> but I do feel that it is worth setting the record straight particularly
> given the current process of selecting a PAKE protocol.
>
>> If an RKR AE scheme is not used in OPAQUE, we have developed a
>> theoretical attack that results in an exponential speedup in online
>> password guessing. Though our attack is still theoretical (we are working
>> on a proof-of-concept now), we believe it is relevant to the ongoing aPAKE