[CFRG] Security analysis for the VDAF draft

Christopher Patton <cpatton@cloudflare.com> Tue, 07 February 2023 21:15 UTC

Return-Path: <cpatton@cloudflare.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 772EBC14F747 for <cfrg@ietfa.amsl.com>; Tue, 7 Feb 2023 13:15:03 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Level:
X-Spam-Status: No, score=-2.097 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cloudflare.com
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 4qwAlvTv18rQ for <cfrg@ietfa.amsl.com>; Tue, 7 Feb 2023 13:14:59 -0800 (PST)
Received: from mail-lf1-x133.google.com (mail-lf1-x133.google.com [IPv6:2a00:1450:4864:20::133]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 15EA2C14E515 for <cfrg@irtf.org>; Tue, 7 Feb 2023 13:14:59 -0800 (PST)
Received: by mail-lf1-x133.google.com with SMTP id w11so24148917lfu.11 for <cfrg@irtf.org>; Tue, 07 Feb 2023 13:14:58 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=r41ZqrhiK4j19g/7RnxekPqvRZPPQMLcNIuG3RGu3dQ=; b=qQGTaS2VU+PSwJFnwManAXIz3HMfUzsnmCXwMKhx0A8JEiDtS19VdKzP1bus27iFp5 KmnvMepv/qcVI+e6eHddVoVjJ45hhQxkQ9g4zRvRFG4eq1yjVVeDIiteM27RqE5ViqaE HD+DxpuFLQD+Eauv+PC76kzx4ULvN3Vn4KMH0=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=r41ZqrhiK4j19g/7RnxekPqvRZPPQMLcNIuG3RGu3dQ=; b=Upjk4BxTFfEDd4lrumjP3NO0AGIyPgsE/GRIjoI4tUwzd5wUT9vXcpmX/pGNM/snJO uO17sVpra9VBzqn7CSd6xYYFpUB3AeIobt1L0QGfmM0WewJdJ8KfbPMcmlwgJd9GJI9o Z2a/mm0nipizjfA6cf1PNpcJ1oP/QXZiWqTMU3ciDilCGjW4frsrOuulmZRt2TibJ+GV lTEBgXjTDYL23TlX/fORCpsCp+loq154EmnTeGohGZiZRuXcDbiWMBA/FBKOJARiKjNh 4XuVretMbdPza2dSP9Ov8piojAhNT5TUogMJDjFvWZvCBPW3vK91xko3NEIqQ0k/7bRC BTJw==
X-Gm-Message-State: AO0yUKXlVT+13yiXCOKM5/FVF2Jp+vE+h1Axkbu1vHyUI1+IU3xjimyi K4daEUOOMmvRz/Fh2kgnsTVwlSrGJUq1mXnpoJ6LTHyDTVyQZ+at
X-Google-Smtp-Source: AK7set/DqH0Ht9svBpwW2G5b0JJxjv+Jom3S6dNpkPAS+Nh1vEBmpNRf0//BsAv0h3l6kazuGRmBUJ2koeRYegFaaPI=
X-Received: by 2002:ac2:51a7:0:b0:4cd:24e8:911c with SMTP id f7-20020ac251a7000000b004cd24e8911cmr755623lfk.209.1675804496064; Tue, 07 Feb 2023 13:14:56 -0800 (PST)
MIME-Version: 1.0
From: Christopher Patton <cpatton@cloudflare.com>
Date: Tue, 07 Feb 2023 13:14:45 -0800
Message-ID: <CAG2Zi22r=k_jZgEnCQM_QQwfE0=Um+wfBeu+eiy0a1joUKfgzA@mail.gmail.com>
To: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000b3f84505f422a3f1"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/-errBjFRvCqi7KuAxoZwH6iY4Vc>
Subject: [CFRG] Security analysis for the VDAF draft
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.39
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: Tue, 07 Feb 2023 21:15:03 -0000

Hello CFRG,

This message is to share with you all some recent security analysis of
draft-irtf-cfrg-vdaf-03 [1]. This is joint work with the draft editors
(Phillipp and myself), Hannah Davis (UCSD), and Mike Rosulek (OSU):
https://eprint.iacr.org/2023/130

The primary goal of this paper is to formulate a provable security
framework for studying candidate VDAFs. We give two definitions that
formalize "privacy" and, separately, "robustness", as described in [1,
Section 9]. We study two schemes in our paper: Prio3 [1, Section 7]; and a
variant of Poplar1 [1, Section 8] that improves round complexity. We call
this variant "Doplar". (More on this below.) Apart from some minor changes
to the draft, the most important takeaways are additional security
considerations for VDAF users, e.g., DAP [2], will need to attend to.

I'll start with a quick overview of the security model in (1). I'll then
describe how we think this model translates into security considerations in
(2). In (3) I will enumerate the changes to algorithms in the draft that we
are making in light of the results in this paper. I'll end in (4) with a
couple of random observations.

We (the authors of the paper) welcome and appreciate any feedback folks
might have on the paper. We're also happy to answer questions, here or in
GH issues :)


On behalf of the authors: Thanks for reading!
Chris P.


(1) Security model

In the following, we refer to the set of input shares generated by a Client
(via the `Vdaf.measurement_to_input_shares()` algorithm) as the Client's
"report". In our security definitions, each report has an associated
"nonce" generated by the Client as well.

(1.1)  Privacy

The main goal for VDAFs is to ensure that, as long as some fraction of
Aggregators is honest, the attacker learns nothing about the Clients'
measurements beyond the aggregate result. Our privacy game (Figure 4 in the
paper) gives the attacker complete control over VDAF execution, except for
transmission of the input shares from honest Clients to honest Aggregators.
The game models a kind of "chosen-batch attack" (analogous to a
"chosen-plaintext attack" for encryption) where the attacker provides each
Client with a pair of measurements, and the game picks which one is
processed based on a coin toss at the start of the game. The adversary wins
if, at the end of the game, it guesses correctly which batch of
measurements was processed. We say the VDAF is private if no reasonable
adversary wins with probability better than 1/2 (Definition 3).

There are a couple features of our security game that are worth calling out.

(1.1.1)
First, the attacker gets to pick the VDAF verification key used for
processing the reports. This models settings in which the key is generated
by one (possibly malicious) Aggregator and distributed to the others. (For
instance, in DAP we would like it if we could have the Leader pick this
value unilaterally: See issue
https://github.com/ietf-wg-ppm/draft-ietf-ppm-dap/issues/161.)

This turns out to be fine, but we need to be somewhat careful here. The
current privacy proof for Prio3 (Theorem 2) assumes the underlying FLP
system ("Fully Linear Proof"; see [1, Section 7.1]) is "honest-verifier"
zero-knowledge. An honest verifier picks its challenge at random, so in
order to push through the reduction to VDAF privacy, we would need to
emulate this random challenge in Prio3.

The challenge (called the "query randomness" in the spec) is derived from
the verification key and the nonce picked by the Client. When modeling the
function used to derive the challenge as a random oracle, it is sufficient
to ensure that (i) the VDAF verification is fixed prior to the report being
generated and (ii) the nonce is chosen at random by the Client.

Remark: Other restrictions on the model are possible. For instance, it may
be sufficient to ensure, somehow, that the verification key is chosen
randomly via some secure coin flipping protocol. (See discussion in
https://github.com/ietf-wg-ppm/draft-ietf-ppm-dap/issues/161.) However,
this would shift more complexity to DAP. Requiring (i) and (ii) seemed to
be the minimally invasive change.

(1.1.2)
Our model involves a notion of "allowed initial states''. The "initial
state" basically means "aggregation parameter", e.g., a set of candidate
prefixes for Poplar1. In our analysis of Doplar (Theorem 4) we found it
necessary to restrict the attacker to aggregating a given report at most
one time per level of the IDPF tree. Otherwise, there are subtle attacks
that arise when the validity proof for a given level is allowed to be
reused.

Remark: Although we did not study Poplar1 in detail, we believe there are
similar attacks if the "authenticator value" for a given level of the IDPF
tree is reused. Thus we have to restrict the initial states in the same way.

(1.2) Robustness

Our secondary goal for VDAFs is that, if all Aggregators execute the
protocol correctly, then the Collector correctly computes the aggregate
result of reports uploaded by honest Clients. (Reports generated by
malicious Clients are filtered out during preparation.) Here we consider
the attacker to be a cohort of malicious Clients who can eavesdrop on the
preparation phase (i.e., it gets to see the messages exchanged by the
Aggregators). The attacker's goal is to cause an Aggregator to accept a
share of an invalid report. (Validity is defined by the VDAF itself; see
"refinement consistency" in Section 3.1.) The game requires the VDAF
verification key is unknown to the attacker. It also requires that nonces
are non-repeating. We say that the VDAF is robust if the probability of the
attacker winning this is small.

Remark: There are important differences between the threat model for
privacy and robustness. (One allows the attacker to control aggregators,
while the other does not; one allows the attacker to control the network,
while the other does not; one allows the verification key to be picked by
the attacker, while the other requires the key to be random; one requires
the nonce to be random, while the nonce to be simply non-repeating.) It's
worthwhile asking whether both properties can be achieved under the same
threat model. However, it is not possible for the current crop of VDAFs.

(2) Security considerations

Based on the security model and analysis of Prio3 and Doplar (which is
related to Poplar1; see below), we have the following recommendations for
additional security considerations.

(2.1) Verification key requirements

Some care is required in choosing the VDAF verification key. The
Aggregators may use any strategy they wish to exchange this key, but the
application MUST ensure that the key that is picked independently of the
reports. For DAP in particular, this means it is safe for the Leader to
pick the key and distribute it, but the Aggregators need to "commit" to the
verification key used for a given task and use the same key for the
duration of the task. (Rotation requires rolling the task configuration.)

Unfortunately, this contradicts a current recommendation. From [1, Section
9]:

"It is also possible to consider a stronger form of robustness, where the
attacker also controls a subset of Aggregators (see [BBCGGI19], Section
6.3). To satisfy this stronger notion of robustness, it is necessary to
prevent the attacker from sharing the verification key with the Clients. It
is therefore RECOMMENDED that the Aggregators generate verify_key only
after a set of Client inputs has been collected for verification, and
re-generate them for each such set of inputs."

Note that preventing leakage of the verification key to the clients is
necessary for robustness in this stronger threat model, but not sufficient.
Thus this recommendation boils down to defense-in-depth for robustness. In
our opinion, privacy takes precedence here.

(2.1) Nonce requirements

Clients MUST choose the report nonce at random. This ensures the nonce is
unpredictable to a privacy attacker; and it reduces the chance of
collisions, which is required for robustness.

(2.2) Requirements for report processing

Poplar1: Applications MUST ensure that reports are aggregated at most once
per-level. Repeated usage of the authenticator at a given level may lead to
subtle attacks on privacy. In particular, the current
"max_batch_query_count" mechanism of DAP [2, Section 4.5.6] is not
sufficient.

Prio3: Applications SHOULD ensure that each report is processed at most
once. It's probably safe to allow re-processing, but (1) this is not
captured in our model; (2) this gets hairy in terms of differential privacy
(see issue https://github.com/cfrg/draft-irtf-cfrg-vdaf/issues/94); and (3)
there doesn't seem to be a good reason to allow this. (It is explicitly
disallowed in DAP.)

(2.3) Security requirements for the PRG

The `Prg` object defined in [1, Section 6.2] is used to map a seed to a
pseudorandom value of a suitable type, e.g., another seed, or a vector of
field elements. Our security analysis models each such mapping as an
independent, random oracle. As such, `Prg` MUST be instantiated with a
primitive that is well-suited for this purpose, like SHA-3.

Relatedly, inputs to random oracles need to be "decodable". Essentially
this is because the current proofs use an RO extractor for proving
robustness.

(3) Changes to Prio3 and Poplar1

To prove Prio3 secure in our model, we needed to make some minor
adjustments to the scheme. We also have some suggestions for Poplar1 based
on our analysis of Doplar, which is quite similar. We summarize our
suggestions below. (Note that some of these changes have already been
merged.)

(3.1) Prio3: Improve domain separation of calls to `Prg`. (Similarly for
Poplar1.) PR: https://github.com/cfrg/draft-irtf-cfrg-vdaf/pull/121

(3.2) Prio3: Add nonce to transcript for joint randomness derivation. This
leads to an improved robustness bound. Issue:
https://github.com/cfrg/draft-irtf-cfrg-vdaf/issues/118. Closed by PR:
https://github.com/cfrg/draft-irtf-cfrg-vdaf/pull/117

(3.3) Replace `PrgAes128` with something that is more suitable for
instantiating a random oracle, like SHA-3. Issue:
https://github.com/cfrg/draft-irtf-cfrg-vdaf/issues/106. Candidate PR (uses
cSHAKE128): https://github.com/cfrg/draft-irtf-cfrg-vdaf/pull/136

(3.4) Specify the nonce length. Right now the nonce is allowed to be
variable length, but since privacy requires this to be randomly generated,
and not all nonce lengths are safe, it makes sense to be more prescriptive
here. This is also useful for making it easier to decode RO queries (see
(2.3)). Issue: https://github.com/cfrg/draft-irtf-cfrg-vdaf/issues/127

(4) Other things

(4.1) What is this "Doplar" thing and what should we do with it?

Doplar is like Poplar1 in that it solves the same use case (heavy hitters).
It is different in that, instead of two rounds of communication for the
preparation phase, only one round is required. The cost of this improvement
is an increase in overall communication overhead (i.e., there are fewer
messages, but they are larger in size). See Section 5.3 of the paper for a
comparison.

Before considering replacing Poplar1, it is worth investigating whether the
communication overhead can be reduced. We are optimistic that it can be. In
any case, the draft editors think that it would be best to keep Poplar1 in
the current draft; if we were to specify Doplar, it would go in a new
document.

(4.2) Consider specializing VDAF syntax to one round preparation

Given that heavy hitters is achievable with one-round preparation, we might
consider specializing the syntax in [1, Section 5.2] to one round instead
of many. This would make specs like DAP [2] vastly simpler. (DAP is
currently suffering from a degree of complexity resulting from generality.)

Acknowledgements

Thanks to Simon Friedberger and Tim Geoghegan for illuminating
conversations about security considerations.

References

[1] VDAF draft: https://datatracker.ietf.org/doc/draft-irtf-cfrg-vdaf/03/
[2] DAP draft: https://datatracker.ietf.org/doc/draft-ietf-ppm-dap/03/