Re: [Cfrg] Potential vulnerabilities with OPAQUE

[Hugo Krawczyk <[e-mail]>]

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 <[e-mail]> wrote:

> 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
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>