Re: [Cfrg] Potential vulnerabilities with OPAQUE

Julia Len <jlen@cs.cornell.edu> Sat, 21 March 2020 16:55 UTC

Return-Path: <jl3836@cornell.edu>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8A3403A040F for <cfrg@ietfa.amsl.com>; Sat, 21 Mar 2020 09:55:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.361
X-Spam-Level:
X-Spam-Status: No, score=-3.361 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H2=-1.463, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id goz3qo-nSW9g for <cfrg@ietfa.amsl.com>; Sat, 21 Mar 2020 09:55:13 -0700 (PDT)
Received: from mail-il1-f174.google.com (mail-il1-f174.google.com [209.85.166.174]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3C0823A040E for <cfrg@irtf.org>; Sat, 21 Mar 2020 09:55:12 -0700 (PDT)
Received: by mail-il1-f174.google.com with SMTP id a6so8904281ilc.4 for <cfrg@irtf.org>; Sat, 21 Mar 2020 09:55:12 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=CA8PJ5GYLLohM9/VqoXEQPU0x3mg5ztsLXJGKRsMFzU=; b=t+BmclIEQSvtqV1C8UfCQAquBU2o5Vj9vNsN+yKaxvTARoRJB/OI78OKArU9Y5g/gc cNQZurfC4VhOr3+711WuIaO9gSRKoFNStqajMD9eV88VyA+GIxI0YwRsibCmFL/vq8iQ 0QpV2SJEo9zYXhCs4PMKHwrBVCPpFLSch7BXaNSKwK6eYcOD6dPF+OGr2G8LVP9c5Nxs AwUgWoNHDv/Gl6uKqKeXbopmkQJDQ6XOLfWemjPebrRSUCblY+lNnKTt3c3fGfm18ZaI btgVumsxFQQlzwixoPR4FpTCSRbFEGlr0lAGdZPB8djv4fc+tJCygFo1a9Luyby07z91 AjNw==
X-Gm-Message-State: ANhLgQ3Vmy1ig022jOUhXTFSP2zEnAEaUcCo+ox+8voObTr/yBsFuasD Oo7pS64IftLt5Ldxs/tw+5qhmWz4NdukMJ5qMXy0Xg==
X-Google-Smtp-Source: =?utf-8?q?ADFU+vtA9Y069WWSQVpjuogmtXqcwoLHzjOrjIgD39Bc?= =?utf-8?q?ju9qbIPPpj8r9i2T3RZZ8P54mVO19t++ijGL2duhpEiuGM4=3D?=
X-Received: by 2002:a92:1a53:: with SMTP id z19mr13963730ill.85.1584809711741; Sat, 21 Mar 2020 09:55:11 -0700 (PDT)
MIME-Version: 1.0
References: <CAK0e1Drh8khq7_v9jsYWHuAQ3XRnK2+2dNFOZQTyqVrbxk21MA@mail.gmail.com> <CADi0yUMsX9USNK_Eov+16oSEvKOTmSGg8VNVqFXob+xpVqFTBQ@mail.gmail.com>
In-Reply-To: <CADi0yUMsX9USNK_Eov+16oSEvKOTmSGg8VNVqFXob+xpVqFTBQ@mail.gmail.com>
From: Julia Len <jlen@cs.cornell.edu>
Date: Sat, 21 Mar 2020 12:55:00 -0400
Message-ID: <CAK0e1Dqr1-0t=Hg4vLQe4w2gB+2okYz8tyJn0mCNySEsaHCwqg@mail.gmail.com>
To: Hugo Krawczyk <hugo@ee.technion.ac.il>, cfrg@irtf.org
Cc: Thomas Ristenpart <ristenpart@cornell.edu>, Paul Grubbs <pag225@cornell.edu>
Content-Type: multipart/alternative; boundary="000000000000e7bee105a1604300"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/rJFpETS-p7UJME5MwY9I20MaDpM>
Subject: Re: [Cfrg] Potential vulnerabilities with OPAQUE
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 21 Mar 2020 16:55:18 -0000

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 <hugo@ee.technion.ac.il>
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
> 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 <jlen@cs.cornell.edu> 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
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>