[Cfrg] Potential vulnerabilities with OPAQUE

[Julia Len <[e-mail]>]

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