Re: [Cfrg] Static-DH oracles, strong-DH security

Alex Davidson <alex.davidson92@gmail.com> Fri, 29 November 2019 15:38 UTC

Return-Path: <alex.davidson92@gmail.com>
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 4A31D1200E0 for <cfrg@ietfa.amsl.com>; Fri, 29 Nov 2019 07:38:39 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.748
X-Spam-Level:
X-Spam-Status: No, score=-1.748 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 WrHHCEx_1xVX for <cfrg@ietfa.amsl.com>; Fri, 29 Nov 2019 07:38:37 -0800 (PST)
Received: from mail-vk1-xa36.google.com (mail-vk1-xa36.google.com [IPv6:2607:f8b0:4864:20::a36]) (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 92E3E12004E for <cfrg@irtf.org>; Fri, 29 Nov 2019 07:38:37 -0800 (PST)
Received: by mail-vk1-xa36.google.com with SMTP id i18so2139082vkk.7 for <cfrg@irtf.org>; Fri, 29 Nov 2019 07:38:37 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=R6G5ulc7WTTBWg3M+i9k5p9BZnVi1L+/8YdE08+W52E=; b=p7U90qx/AdUhVKrq0CsmYQ6oifxjIANM0z0O6uUZOR1w5FSpQbux0e1iZtFXPc8OxM ec2y/InKJ5PuOpldEO2iAdJT5UCxV5sFikYGwLmnkhW5KVndmjPg8wUcT3Yd0I45+fRi QblvOK2dOAp9bwYtKtjzePsIwET2uZ44GIepuwBktLbgO6c/nDPwMgLgIisWfcajZWBG WXRtesZWbBgXEM2t5YpFPrVKuaK1hCv+ivkBc0NN95vxb6TVjIXf0EdoXIXfJn79E3qD VnEldGWD7j5z9IkW0nqjqIMVqHngxiZ/MZCFBEnG1gonzPwYegT0CagEZS24Ui+qMB69 38KQ==
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=R6G5ulc7WTTBWg3M+i9k5p9BZnVi1L+/8YdE08+W52E=; b=phixQx9AX3IqDHHuefTG1GLd+1GpSeVkZppFQCF51iG9haCZM9RyqyzdVLO6xGR+bt /eQdRxOJmjY0bYVlkzqYztaP6cMb5B7NFoowKLSnkr60gdOCQqeBHoG0Al+y/pVzpPsN Ghrb2ICNmkYvfGFTSX4zM1hs44slGurwsamk0lojZi1AMfAXgNLviZulQzzTP9yJiMXr mq2KZJABe7z9h4/3aotAsBS90u5afwZ87kyJ1MtTdzob5Xuta4cT+KeybbdiXm5YR6jN T/vx7MP1fMKgfMcO+qHVXsaa6wJSjLFg4Y8sPlhuNWEFVi64lt5ICPtn8RvgPI4kmbbY fvzw==
X-Gm-Message-State: APjAAAWEIwciyagjaQDqLopETEOv3fsDf7BLmYEKU1cmjBHepGbbKOUL SKCtirynOUiOw3f5DMeRIcCzHhgAXS/YSyhwM5hHwxaJ+A==
X-Google-Smtp-Source: APXvYqzUACZttRQa4uMC/Jzp2G3el56AeHIECfXCrcIxo1Mvi0oSK0pyIxjqGuhShpmWn28Pn9djAxzqyR0BMditrFw=
X-Received: by 2002:a05:6122:332:: with SMTP id d18mr8611718vko.89.1575041916336; Fri, 29 Nov 2019 07:38:36 -0800 (PST)
MIME-Version: 1.0
References: <20191122000156.10DF360A41@jupiter.mumble.net> <b64d2afb-1c0a-48d4-85bc-492fbe866571@www.fastmail.com>
In-Reply-To: <b64d2afb-1c0a-48d4-85bc-492fbe866571@www.fastmail.com>
From: Alex Davidson <alex.davidson92@gmail.com>
Date: Fri, 29 Nov 2019 15:38:25 +0000
Message-ID: <CAD5V+fM4M=tnvbPW1tbTobk_=0t-SW1pTXxxhMa+BtMOEfKong@mail.gmail.com>
To: Filippo Valsorda <filippo@ml.filippo.io>
Cc: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="000000000000edfe4405987e05a0"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/BkfJ-ZW_n-Ywa_Nn1sctqz-O3Fo>
Subject: Re: [Cfrg] Static-DH oracles, strong-DH security
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: Fri, 29 Nov 2019 15:38:39 -0000

> On Fri, Nov 22, 2019 at 6:58 AM Filippo Valsorda <filippo@ml.filippo.io>;
wrote:
> 2019-11-21 19:01 GMT-05:00 Taylor R Campbell <campbell+cfrg@mumble.net>;:
> > To be clear: I don't mean to suppose limiting adversaries to 2^64
> > queries overall; rather, I mean to suppose limiting them to 2^64
> > queries made _one after the other_ -- not in parallel.
> >
> > What matters is the _latency_ of a query, not the _bandwidth_ of the
> > global Cloudflare network.  And I think it is quite reasonable to
> > suppose limiting the latency of a query to at least a nanosecond:
>
> I think it's even reasonable to assume a latency of 10 nanoseconds,
> meaning 684245902131068969 queries would take two centuries, leaving
> the only realistic attack at 2^118.

Thanks for both of your inputs. I agree that in the Internet setting
assuming this kind of latency on sequential queries is very likely not
to constrain any plausible adversary.

However, my contention is that the current draft-irtf-cfrg-vorpf
document describes a protocol in the generic sense, and the notion of
latency is not factored into the security model. This mirrors the
security model that the original (V)OPRF design [JKK14] uses, and so we
can invoke the proof of security that they provide for making arguments
about the security of the protocol.

The reason for describing the protocol in this manner is that it ensures
that the (V)OPRF is agnostic to the setting that it is used in. In turn,
this ensures that the security of the protocol is evaluated against the
*strongest* possible adversary. This also makes it possible to easily
evaluate the expected lower bound of the security parameter for a
(V)OPRF ciphersuite in any setting. This includes settings that the
adversary, for whatever reason, may enjoy 0ms latency per query.

As you point out, perhaps instantiating such an adversary is impossible
in the real world. However, in my opinion it is imperative that we make
*no* assumptions about the adversarial setting that the generic (V)OPRF
protocol is being used in, for the reasons above.

[JKK14]: https://eprint.iacr.org/2014/650.pdf