In my opinion, this is the weakest section of the document right now. (But it's not far
from being great!) I'll start off with some high level thoughts and follow with detailed
comments.
The bulk of the security considerations is dedicated to discussion of
computational assumptions used in security proofs. This is particularly
important for this document because the assumptions are stronger than usual
ones, e.g., DLOG, CDH, DDH, and the like. The main consequence is that, compared
to other protocols, adopters of this standard will have to be much more careful in
choosing the cryptographic parameters best suited for their application.
The reason for this is that the proposed protocols all inherently expose a
so-called "static-DH" oracle. As the spec correctly points out, access to such
an oracle leads to a key-recovery attack that, while not feasible for
sufficiently large gropus, significantly degrades the security level,
potentially making other attacks more likely. Yet the spec also points out that
the degreee to which security is degraded depends on the protocol, as well as
the application that is built upon it.
This is a murky state of affairs, and one I fear might lead to adopters making
the wrong choice. I think the document would benefit from providing clearer and
more conservative guidance. Some specific suggestions:
Ideally we would be able to derive "safety limits" for each
ciphersuite and protocol. In particular, the document would specify how many times a
secret key operation can be performed before the key needs to be rotated. It's not immediately clear to me how this would work or how useful it would be, since the limits would have to be derived from the best known attacks. This is perhaps more of a research question than anything else.
The document should provide stronger guidance on when using the smaller
groups (ristretto255 or P-256) is safe. My take (based on my read of the doc)
is that I would be comfortable just rate-limiting key operations for the
larger groups, but if I had to pick the smaller ones, I would really only
feel comfortable if there were some way of controlling the number of clients
that access oracle (by authenticating them, for instance). Of course, this may
end up being a question for the application.
The document would benefit from providing examples of applications for which
the static DH oracle is not likely a problem and applications for which the
static DH oracle may be a problem. What about OPAQUE? PrivacyPass?
Finally, because the computational assumptions are stronger, they are more
likely to be falsified one day than "standard" assumptions. If I were writing
this spec, I would probably NOT RECOMMEND that the smaller groups be used,
simply as a hedge against future advancements in cryptanalysis. I realize this
is probably a controversial position, so just take it as a suggestion. (As with all of
these comments, of course!)
6
This section is written as if it only applies to POPROF. Is this intentional?
If so, what are the security considerations for OPRF and VOPRF? I think it
would be better to be explicit about what considerations apply to which
protocol. For example, the definition of pseudorandomness applies to all
modes, as does the notion of oblivious (modulo the public input).
Perhaps the idea here is that OPRFs and VOPRFs can be viewed as special cases
of POPRFs. I think this makes sense, but it's not stated anywhere explicitly.
Quote:
This section discusses the cryptographic security of our protocol, ...
Instead of "our protocol", I think this should be "the POPRF protocol defined
in Section 3.3.3."
6.2
The title of this section is "Cryptographic Security" is a bit confusing. I
expect it to define a set of security goals, but these were already enumerated
in Section 6.1. I think a better tittle would be "Computational Assumptions",
or even "Cryptographic Assumptions", since these are what the section
describes.
Throughout this section, the term "cryptographic security" is used as a
stand-in for some security property defined in Section 6.2. I think it would
be better to be specific. For example:
Consequently, the cryptographic security of the OPRF and VOPRF variants is
based on the assumption that the One-More Gap DH is computationally
difficult to solve.
For which property is this assumption required: pseudorandomness,
obliviousness, or verifiabilty? All three perhaps?
6.2.1
nit: I would revise "the assumption that the One-More Gap DH is
computationally difficult to solve" to "the assumption that the One-More Gap
DH problem is computationally infeasible to solve for GG".
What's the value of stating OMDH problem in this document? My guess is that a
reader who is interested in this would just refer to the paper.
One reason to not include it is that, in order understand what's going on, the
definition will require more detail than what's presented. In particular:
What does the OPRF functionality do? Is it just an oracle that returns
Evaluate() on whatever input the attacker chooses?
What is a "DDH solver", and what does it mean for their to be multiple DDH
solvers?
How is k generated?
"Q is the number of allowed queries": Queries to what? The OPRF
functionality or the DDH solvers?
I think these issues can be avoided by just simply naming the assumption and
providing a citation.
Quote:
The original paper [JKK14] gives a security proof that the 2HashDH-NIZK
construction satisfies the security guarantees of a VOPRF protocol Section
6.1 under the OMDH assumption in the universal composability (UC) security
model.
It could be made more clear how this statement relates to the draft. What's
the relationship between 2HashDH-NIZK and the VOPRF in this draft? Is the
protocol Section 3.3.2 based on the protocol from the paper? Are there any
differences or are they the same protocol? Section 6.2.2 does this very well,
I think, so I weould just follow suit here.
nit: UC isn't a security model per say. I would instead say: "... under the
OMDH assumption. The goals of pseudorandomness, obliviousness, and
verifiablity are formulated in the Universal Composability (UC) framework."
I'd also add a reference to the UC paper.
6.2.1.1
This section is too dense and can use a bit more exposition. In particular the
stated problem is that the OPRF/VOPRF protocols allow "instantiation of a
oracle for construction Q-strong-DH (Q-sDH) samples". This is fairly jargony,
and the average reader is not going to know what this means.
This section needs to start out by saying what attack vector is being
exploited, and to what end. For example: "The OPRF and VOPRF protocols are
vulnerable to a class of key-recovery attacks in which a malicious client, by
issuing a carefully crafted sequence of messages to the server, can compute
bits of the server's secret."
Then, before getting into the details, I would pivot to what this means for
applications: "The efficacy of these attacks depends on how much computational
power the adversary has at its disposal and how many queries it is able to
make. For applications in which the latter is difficult to control, it will be
necessary to choose a larger group."
At the end of this section I foundd myself wondering if Ristretto255 or P-256
are going to cut it. I noticed that this gets discussed later in Section 6.2.4.
I would add a forward reference here.
Quote:
Recall that from a malicious client's perspective, the adversary wins if
they can distinguish the OPRF interaction from a protocol that computes the
ideal functionality provided by the PRF.
I'm not sure I understand this paragraph. It sounds like it's saying that the
the protocol is designed so that the client can't distinguish the output of
the POPRF/VOPRF/OPRF from a random function. What is "an ideal functionality
provided by the PRF"? This is the first time such an ideal functionality is
mentioned.
This seems like it's a vestage of something else that has been deleted.
Perhaps just remove the paragraph?
6.2.2
Quote:
The construction is identical to 3HashSDHI, except ...
Slightly simpler: "Our construction is identical, except ...".
Quote:
Given G1, G2, hG2, (h^2)G2, ..., (h^Q)*G2; for G1 and G2 generators of
GG. Output h where h is an element of GF(p)
There are grammar errors here that make this difficult to understand. How
about: "Given G1, G2, hG2, (h^2)G2, ..., (h^Q)*G2, where G1 and G2 are both
generators of the group GG, compute the scalar h."
6.2.2.1
Simnilar comments as for Section 6.2.1.1.
6.2.3
This observation is interesting, but I don't see how it's relevant to the
spec. Would an implementor want to exploit this equivalence some how?
Incidentally, why is this section in Security Considerations? (I.e., what is
its relevance for security?)
6.2.4
Quote:
Moreover, such attacks are only possible for those certain applications
where the adversary can query the POPRF directly. In applications where such
an oracle is not made available this security loss does not apply.
Given how important this is, I think it would be worthwhile to cite
applications for which this is (and is not) a problem. For example, does
Privacy Pass expose a static-DH oracle?
I think the draft should provide more guidance for how to assess this risk and
mitigate the static DH oracles. Some thoughts:
How do I know if my application is exposing this oracle?
In some applications it might be possbible to slow down the attacker by
rate-limiting queries to the server.
My understanding of the attacks involving static-DH oracles is that they
lead eventually to key recovery. Would one way to mitigate this be to
recommend frequent key rotation?
Quote:
... are RECOMMENDED to only implement ciphersuites 0x0002, 0x0004, and
0x0005.
Since future implementations might pick future ciphersuites, I think it makes
sense to sharpen the requirement here. How about: "... are RECOMMENDED to
choose groups that target a higher security level, such as decaf448 (used by
ciphersuite 0x0002), P-384 (used by 0x0004), or P-521 (used by 0x0005).
6.7
GenerateProof() is executed on sensitive data (namely skS), so I think it
too MUST run in constant-time.
In my opinion, this is the weakest section of the document right now. (But it's not far from being great!) I'll start off with some high level thoughts and follow with detailed comments.
The bulk of the security considerations is dedicated to discussion of computational assumptions used in security proofs. This is particularly important for this document because the assumptions are stronger than usual ones, e.g., DLOG, CDH, DDH, and the like. The main consequence is that, compared to other protocols, adopters of this standard will have to be much more careful in choosing the cryptographic parameters best suited for their application.
The reason for this is that the proposed protocols all inherently expose a so-called "static-DH" oracle. As the spec correctly points out, access to such an oracle leads to a key-recovery attack that, while not feasible for sufficiently large gropus, significantly degrades the security level, potentially making other attacks more likely. Yet the spec also points out that the degreee to which security is degraded depends on the protocol, as well as the application that is built upon it.
This is a murky state of affairs, and one I fear might lead to adopters making the wrong choice. I think the document would benefit from providing clearer and more conservative guidance. Some specific suggestions:
Ideally we would be able to derive "safety limits" for each ciphersuite and protocol. In particular, the document would specify how many times a secret key operation can be performed before the key needs to be rotated. It's not immediately clear to me how this would work or how useful it would be, since the limits would have to be derived from the best known attacks. This is perhaps more of a research question than anything else.
The document should provide stronger guidance on when using the smaller groups (ristretto255 or P-256) is safe. My take (based on my read of the doc) is that I would be comfortable just rate-limiting key operations for the larger groups, but if I had to pick the smaller ones, I would really only feel comfortable if there were some way of controlling the number of clients that access oracle (by authenticating them, for instance). Of course, this may end up being a question for the application.
The document would benefit from providing examples of applications for which the static DH oracle is not likely a problem and applications for which the static DH oracle may be a problem. What about OPAQUE? PrivacyPass?
Finally, because the computational assumptions are stronger, they are more likely to be falsified one day than "standard" assumptions. If I were writing this spec, I would probably NOT RECOMMEND that the smaller groups be used, simply as a hedge against future advancements in cryptanalysis. I realize this is probably a controversial position, so just take it as a suggestion. (As with all of these comments, of course!)
6
This section is written as if it only applies to POPROF. Is this intentional? If so, what are the security considerations for OPRF and VOPRF? I think it would be better to be explicit about what considerations apply to which protocol. For example, the definition of pseudorandomness applies to all modes, as does the notion of oblivious (modulo the public input).
Perhaps the idea here is that OPRFs and VOPRFs can be viewed as special cases of POPRFs. I think this makes sense, but it's not stated anywhere explicitly.
Quote:
Instead of "our protocol", I think this should be "the POPRF protocol defined in Section 3.3.3."
6.2
The title of this section is "Cryptographic Security" is a bit confusing. I expect it to define a set of security goals, but these were already enumerated in Section 6.1. I think a better tittle would be "Computational Assumptions", or even "Cryptographic Assumptions", since these are what the section describes.
Throughout this section, the term "cryptographic security" is used as a stand-in for some security property defined in Section 6.2. I think it would be better to be specific. For example:
For which property is this assumption required: pseudorandomness, obliviousness, or verifiabilty? All three perhaps?
6.2.1
nit: I would revise "the assumption that the One-More Gap DH is computationally difficult to solve" to "the assumption that the One-More Gap DH problem is computationally infeasible to solve for
GG".What's the value of stating OMDH problem in this document? My guess is that a reader who is interested in this would just refer to the paper.
One reason to not include it is that, in order understand what's going on, the definition will require more detail than what's presented. In particular:
Evaluate()on whatever input the attacker chooses?kgenerated?Qis the number of allowed queries": Queries to what? The OPRF functionality or the DDH solvers?I think these issues can be avoided by just simply naming the assumption and providing a citation.
Quote:
It could be made more clear how this statement relates to the draft. What's the relationship between 2HashDH-NIZK and the VOPRF in this draft? Is the protocol Section 3.3.2 based on the protocol from the paper? Are there any differences or are they the same protocol? Section 6.2.2 does this very well, I think, so I weould just follow suit here.
nit: UC isn't a security model per say. I would instead say: "... under the OMDH assumption. The goals of pseudorandomness, obliviousness, and verifiablity are formulated in the Universal Composability (UC) framework." I'd also add a reference to the UC paper.
6.2.1.1
This section is too dense and can use a bit more exposition. In particular the stated problem is that the OPRF/VOPRF protocols allow "instantiation of a oracle for construction Q-strong-DH (Q-sDH) samples". This is fairly jargony, and the average reader is not going to know what this means.
This section needs to start out by saying what attack vector is being exploited, and to what end. For example: "The OPRF and VOPRF protocols are vulnerable to a class of key-recovery attacks in which a malicious client, by issuing a carefully crafted sequence of messages to the server, can compute bits of the server's secret."
Then, before getting into the details, I would pivot to what this means for applications: "The efficacy of these attacks depends on how much computational power the adversary has at its disposal and how many queries it is able to make. For applications in which the latter is difficult to control, it will be necessary to choose a larger group."
At the end of this section I foundd myself wondering if Ristretto255 or P-256 are going to cut it. I noticed that this gets discussed later in Section 6.2.4. I would add a forward reference here.
Quote:
I'm not sure I understand this paragraph. It sounds like it's saying that the the protocol is designed so that the client can't distinguish the output of the POPRF/VOPRF/OPRF from a random function. What is "an ideal functionality provided by the PRF"? This is the first time such an ideal functionality is mentioned.
This seems like it's a vestage of something else that has been deleted. Perhaps just remove the paragraph?
6.2.2
Quote:
Slightly simpler: "Our construction is identical, except ...".
Quote:
There are grammar errors here that make this difficult to understand. How about: "Given G1, G2, hG2, (h^2)G2, ..., (h^Q)*G2, where G1 and G2 are both generators of the group GG, compute the scalar h."
6.2.2.1
Simnilar comments as for Section 6.2.1.1.
6.2.3
This observation is interesting, but I don't see how it's relevant to the spec. Would an implementor want to exploit this equivalence some how?
Incidentally, why is this section in Security Considerations? (I.e., what is its relevance for security?)
6.2.4
Quote:
Given how important this is, I think it would be worthwhile to cite applications for which this is (and is not) a problem. For example, does Privacy Pass expose a static-DH oracle?
I think the draft should provide more guidance for how to assess this risk and mitigate the static DH oracles. Some thoughts:
How do I know if my application is exposing this oracle?
In some applications it might be possbible to slow down the attacker by rate-limiting queries to the server.
My understanding of the attacks involving static-DH oracles is that they lead eventually to key recovery. Would one way to mitigate this be to recommend frequent key rotation?
Quote:
Since future implementations might pick future ciphersuites, I think it makes sense to sharpen the requirement here. How about: "... are RECOMMENDED to choose groups that target a higher security level, such as decaf448 (used by ciphersuite 0x0002), P-384 (used by 0x0004), or P-521 (used by 0x0005).
6.7
GenerateProof()is executed on sensitive data (namelyskS), so I think it too MUST run in constant-time.