fcelda / nsec5-draft Goto Github PK

In section 5.4.1.1 of the vrf draft, OS2ECP will reject if Hash(alpha || pk || CTR) is not in the correct finite field. For prime fields, this means reject if Hash(alpha || pk || CTR)>= the prime over which the curve is defined (this prime has no name in the draft; it is not the same as the curve order q, but it is close to q; it is usually called p). Similarly, for fields of characteristic 2, OS2ECP will reject if Hash(alpha || pk || CTR) has a 1 in any position that extends beyond the field size. This rejection will happen because of http://www.secg.org/sec1-v2.pdf Section 2.3.6, invoked via Section 2.3.4 step 2.2.

The field size can differ from hash size by up to 7 bits in the draft, causing average number of trials to avoid this rejection to be as high as 128 (this is before we even get to the "is this point on the curve" part of OS2ECP, which itself has probability 1/2 of rejection). To avoid this, I propose to zero out the correct number of leading bits of Hash(alpha || pk || CTR), so that the average number of trials to get x smaller than the prime is at most 2. This proposal requires no changes in the most common case, when the prime and the hash function have the same bit length (e.g., 256, as in P256 or Curve25519).

EC_hash_to_curve1 is susceptible to timing attacks. I feel quite uncomfortable about proposing this even if this property is not relevant for some use cases. Do we know how to implement the _curve2 without significant drawbacks? If we do, I propose to use _curve2 as the only option in the draft.

I just added in aaa83e5 discussion of VRF security property that is used by some applications, but not for any of the applications that we (NSEC5) or the CONIKS folks are using.

This is a different type of pseudorandomness than that one we use. The pseudorandomness we use only holds if VRF keys are generated in correct way.

What this is, is pseudorandomness that must hold even if the VRF keys are generated adversarially, as long as the VRF input alpha is unpredictable.

Specifically, suppose the VRF keys are generated by an adversary. Then, a VRF hash output beta should look pseudorandom to the adversary as long as (1) its corresponding VRF hash alpha is chosen randomly and independently of the VRF key, (2) alpha is unknown to the adversary, (3) the corresponding proof pi is unknown to the adversary, and (4) the VRF public key chosen by the adversary is valid.

An additional TODO is to figure out what checks are needed to make sure the adversarially-chosen VRF public key is valid.

To deal with different ways of encoding compressed curve points for 25519 and p256, I introduced the function xC2xyC that converts (the octet representation) of an x-coordinate of an EC point to (the octet representation) of a compressed EC point. This function will be different for 25519, p256, and ed448.

The upside: This way we keep ECVRF_hash_to_curve1() modular and working for all 3 curves, and we just need to specify xC2xyC as part of the ciphersuite.

Downside: This is a funny looking function that I just made up. Is there a more standard way to deal with this?

All of these changes are in a44dcb4

There are some inconsistencies in naming the cipher suites.

ECVRF-EDWARDS25519-SHA512-ELL2 vs ECVRF-ED25519-SHA512-Elligator2 and a few others.

Because it is needed in the nsec5 draft.

VRF draft includes RSA and EC VRF and is in the file vrf.xml

We should explicitly state what happens in the event a hash matches an existing owner name.

We say that TTL and class for NSEC5PROOF must be the same as for the corresponding NSEC5. However the logical dependency between NSEC5PROOF and NSEC5 is opposite.

Logically:

• VRF proof for a name is provided in NSEC5PROOF.
• VRF hash is derived from the proof.
• NSEC5 is looked up, the record may match the name or just cover the name.

We have text "Cryptographic security of Hash is at least as high as the cryptographic security level of the RSA key" and "Cryptographic security of Hash is at least as high as the cryptographic security of G". This is not clear: what do we mean by "cryptographic security"? How do you evaluate it? And what if the RSA key or G hash slightly higher security -- is that now completely ruled out?

Not sure what we should do about this.

Verifying says to fail "If gamma is not a valid EC point in G" but doesn't specify how to check if gamma in G (ECVRF_decode_proof will only check if gamma is on the curve, which is a superset of G if cofactor > 1). The VRF is NOT secure without such a check (specifically, uniqueness can be violated if gamma is a valid EC point but not in G -- more than one gamma could be valid). I see two choices:

• We could specify that, if cofactor > 1, verifying should check if gamma^q = O (point at infinity). That will make sure that gamma is in G. However, it has a cost of a full EC operation.

• We could instead take the approach of https://whispersystems.org/docs/specifications/xeddsa/#vxeddsa , which does not verify if gamma is in G, but rather computes gamma^cofactor as the first step of ECVRF_proof2hash. We would need to add to our proof to show that gamma^cofactor is unique even if gamma is not in G.

Elliptic Curve VRF section enumerates used primitives and notation used in algorithms below (https://tools.ietf.org/html/draft-goldbe-vrf-01#section-5). Clarifying what operation is meant in the algorithm steps is disruptive.

In case of *, if we want to differentiate between integer multiplication and EC point addition, we can specify both as primitives. Used operation must be clear from the context because the input types are always clear.

We discuss the relationship of NSEC5 to these RFCs in our research paper but not the draft. Should add the discussion to the draft.

Sections 5, 6, and 7, defining the NSEC5KEY, NSEC5, and NSEC5PROOF RRs respectively, could be tightened up by not using subsections for wire format and presentation format. Of course, each record would still have its own section.

The subsections break up the flow and, while convenient for external references, are also not really long enough that someone following an external reference that intended to focus on, say, presentation format, would have trouble finding what they were looking for in each consolidated section.

Here is my proposal for adapting @trevp's "synthetic nonce" idea to our draft. This is based on @trevp's email here: https://moderncrypto.org/mail-archive/curves/2017/000925.html
I am simplifying the proposal of Trevor. Differences: I am omitting his s labelset idea (as I don't understand its value). I am adopting his hashing of g, g^x into the synthetic nonce even though I don't completely understand what it is doing. (See his argument labeled (2) below.)

Proposal

We replace this step in our VRF signing algorithm

choose a random integer nonce k from [0, q-1] https://github.com/fcelda/nsec5-draft/blob/master/vrf.xml#L654

let z be a random 32 byte nonce
let pad1, pad2: padding filled with zero bytes to align the next hash
input with a hash block (128-byte alignment for SHA-512).
let k = Hash(g, g^x, z, pad1, x, pad2, alpha) mod q

Rationale

Here is a rationale to quote Trevor. This is quoted directly from Trevor's email linked above but translated into our notation.

• The secret nonce k must be uniformly random to an attacker, and
  must take a different value whenever c does. For security redundancy,
  this is done in two ways: first, by hashing random data z; second,
  by hashing the same inputs that are hashed into ECVRF_hash_to_curve plus the
  secret key x. We'll discuss the value of this redundancy later.

• x is hashed in its own hash block (due to padding) to provide a
  "cascade" PRF as in HMAC or AMAC: If z is a random secret value, then
  the "synthetic nonce" k is the output of a PRF keyed by z. If z is
  public (e.g. a bad RNG) then the synthetic nonce k is the output of
  a PRF keyed by k.

Trevor also says (I have not managed to work through all his arguments yet but here are a few that sound reasonable to me (apart from (2) which I don't understand). )

Nonce randomization

Traditionally discrete-log signatures choose k from an RNG. (By
"discrete-log signatures" meaning both Schnorr signatures like EdDSA,
and DSA/ECDSA which calculate s differently).

"Deterministic" signatures have been popularized by Ed25519 for
Schnorr, and RFC 6979 for DSA/ECDSA. In a deterministic signature the
nonce is a hash or PRF of the message and some secret key which is
unique for each signer (e.g. "N" in Ed25519, or the signer's private
scalar (our "x") in RFC 6979).

Deterministic signatures are intended to be more robust, since they're
not vulnerable to RNG failures. Even a small RNG failure could be
catastrophic:
(a) If our nonce k becomes known to an attacker, the signer's private
scalar is solvable as x = (s+k)/c.
(b) If nonce k repeats with different c, the private scalar is solvable as
k = (s1-s2)/(c1-c2).
(c) If the attacker has a few bits of information about many nonces,
the private scalar might be solved with more advanced techniques. See https://eprint.iacr.org/2014/434.pdf and https://eprint.iacr.org/2013/346.pdf.

RNG failures happen, so making the nonce a function of the message and
a secret key is a good idea. However randomization also provides
benefits:

(1) Faulty computations could be caused by attackers glitching clock
or power lines, or other tampering. Without randomization, any fault
in the calculation of h^x, or c=ECVRF_hash_to_curve(...), while signing the same
message repeatedly, would give multiple signatures with the same k but
different c. This would leak the private scalar x as in (b), provided
the attacker can calculate or guess the faulty k. With
randomization, I believe fault attacks are less effective, for
example:

• Flipping one bit in the private scalar to leak the private scalar
  in hundreds of faulty signatures https://www.researchgate.net/publication/221291537_Breaking_Public_Key_Cryptosystems_on_Tamper_Resistant_Devices_in_the_Presence_of_Transient_Faults
• Randomizing one byte of the private scalar to leak the private
  scalar in thousands of faulty signatures [https://link.springer.com/chapter/10.1007/978-3-540-27800-9_41]
• Skipping scalarmult instructions to leak the private scalar in
  tens of faulty ECDSA signatures [https://dl.acm.org/citation.cfm?id=1731211]

[NOTE: I DON'T FOLLOW THIS ARGUMENT.]
(2) Without randomization, the algorithm is fragile to modifications
and misuse. In particular, modifying it to add an extra input to
c=... without also adding the input to h=... would leak the private
scalar if the same message is signed with a different extra input. So
would signing a message twice, once passing in an incorrect public key
g^x (though the synthetic-nonce algorithm fixes this separately by
hashing g^x into k).

(3) Without randomization, an attacker can trigger repeated
calculations using the same inputs. Consider a sidechannel attacker
recording traces of the signer's power consumption or EM radiation.
This attacker might request repeated signing of the same message in an
attempt to average out noise and get information about secret inputs
in the calculations of k or s.

Of course, there are other ways besides randomization to mitigate
fault and sidechannel risk. Verifying a new signature before
returning it, or performing the signature twice and comparing, would
help against faults, but makes the signing operation a few times
slower. The gamma = h^x calculation could be "blinded" in different ways
to reduce sidechannel risk, but this probably involves either a
larger, slower scalar or calculating
new blinding / unblinding factors frequently. So random nonces appear
to be a simple and efficient way to increase protection.

Given this, I'll argue that randomized vs. deterministic is a false
dichotomy here. For private-key protection it's not important that
nonces be deterministic based on the message; nonces just have to
differ for different "c" values. Mixing (key, message) into the nonce
can provide this when an RNG fails, and an RNG can provide this when
mixing (key, message) fails. Combining these approaches yields what
we could call a "synthetic nonce" (by analogy with "synthetic IV"
authenticated encryption).

Combining these approaches isn't novel. Adam Langley switched
OpenSSL's DSA/ECDSA to combined hashing of RNG output and private
scalar in 2013, and this remains in OpenSSL plus the BoringSSL and
LibreSSL forks.

Let's consider two counter-arguments:

• DJB has pointed out that a malicious RNG might inspect memory and
  choose RNG outputs to bias the nonce and leak the private key as in
  (c) above. I'd argue that's a far-fetched threat which is
  outweighed by the above risks.

• It could be argued that determinism is valuable apart from
  private-key protection, e.g. to help testing. The above signing
  functions specify exactly how the random input z is used, so are
  deterministic and testable.

Just a thought to do with as the group wants. At the start of another draft my co-author and I have:

[ Ed note: Text inside square brackets ([]) is additional background
information, answers to frequently asked questions, general musings,
etc. They will be removed before publication. This document is
being collaborated on in Github at: https://github.com/[...].
The most recent version of the document, open issues, etc should all
be available here. The authors (gratefully) accept pull requests ]

I think we should have something like that on this one too.

Do you feel like the Terminology needs to be extended?

I noticed that we often use VRF prover that holds VRF SK for instance. Maybe we could shorten this just into Prover in case we define this as a term.

Just an idea. I don't have strong opinion on that.

Instead of pointing to a far away draft, just say what to do, and then point to the draft only to tell people that what they will get is a valid point encoding.

Perhaps using XOR to be branchless.

It is jilting that 8.2 immediately jumps into a discussion of handling DS when the general case of no data responses was not discussed. It should focus on No Data responses for the normal case and then address any special handling for other RR types afterward.

There should be examples for the main cases of section 8, either in an appendix or, if short enough, in section 8 itself.

Section 12.2:

" This document does not define a format to store private NSEC5 keys.
Use of a standardized and adopted format is RECOMMENDED."

This feels awfully squishy to me. It should either just declare the whole issue out of scope and drop the second sentence, or recommend something more concrete. As an implementor reading it I simultaneously react with both "well yes of course, that makes obvious sense" and "which?".

We should go over this section again, especially with David and Shumon, to make sure it is clear enough and is using the correct DNS terminology, esp. wildcard terminology. Potentially also add some examples to each section to clarify what we are saying.

The curve may have more points than q, in which case G is not the whole curve, but only a subgroup of it. This is not the case for the NIST prime-field curves, but is for some other curves (e.g., 25519, NIST binary-field curves). ECVRF_hash_to_curve will not work in that case, because it will get a point on the curve, but not in the group G. Multiplying by the cofactor should solve the problem.

Proposed, change:

"The Domain Name System Security (DNSSEC) Extensions introduced the
NSEC resource record (RR) for authenticated denial of existence and
the NSEC3 RR for hashed authenticated denial of existence. This
document introduces NSEC5 as an alternative mechanism for DNSSEC
authenticated denial of existence. "

to:

"The Domain Name System Security (DNSSEC) Extensions introduced the
NSEC resource record (RR) for authenticated denial of existence and
the NSEC3 RR for hashed authenticated denial of existence. This
document introduces NSEC5 as an alternative mechanism for DNSSEC
denials. "

Having "denial of existence" repeated three times in two sentences feels prosaically cumbersome to me.

The draft says "this algorithm MUST NOT be used in applications where the VRF input alpha must be kept secret" because of possible timing attacks. However, timing attacks may be not possible in some settings, may be mitigated in others, and anyway, as the draft itself says, the leakage is very small (expected 1 bit). Does MUST NOT really belong there?

Things are in a sufficient state that we could go ahead and ask IANA for allocations for the RR Types we need under Expert Review per RFC 5395.

https://tools.ietf.org/html/rfc5395#section-3.1.1

Shall I?

Also section 4 of the nsec5 id should reference specific sections of the vrf id, make sure to fix that.

If we want to get rid of "trusted" in the "trusted uniqueness" for EC VRF, we can add some optional steps for the verifier, so that uniqueness can be assured even when key generation is not trusted.

There are three cases:

• Curve is well-established ahead of time, g is trusted, PK g^k is not trusted. This case is easiest: verify that PK is on curve, not point at infinity, and that PK^q is point at infinity.
• Curve is well-established ahead of time, g is not trusted, PK g^k is not trusted. Same as above, except for both g and g^k.
• Curve could have been picked adversarially. This is the hardest one to handle, because adversary could, in principle, first compute ECVRF_hash_points on some six "points" that aren't even on a well-defined curve and them try to find a curve that lets him violate uniqueness on these points. There is no known attack, but the proof doesn't go through, because the proof requires a well-defined notion of log that is fixed at the time ECVRF_hash_points is called (so that only one c can work). If we add a description of the curve to the hash input in ECVRF_hash_points, this problem goes away, but we have to be careful about what we mean by "description," to make sure the adversary really is committed to the curve. Here's an attack if we are not careful: the adversary decides a curve's name before the curve is even selected (e.g., SecureCurve256), uses it as a curve "description" during hashing, then finds an adversarial curve that allows him to cheat, then standardizes SecureCurve256 as the name for that adversarial curve by adding it to some future standard, and then finally cheats.

@goldbe ad your removed cref in pull #24.

I checked that the OS2ECP algorithm has a variant of a failed state:

• SEC 1 section 2.3.4 for NIST P256 outputs "invalid".
• RFC 8032 Secion 5.1.3 for Ed25519 says that "decoding fails" instead of explicitly giving "invalid" as an output.

Do you think it has to be clarified? RFC8032 uses less formal and more descriptive language.

"otherwise you get into weird issues with the RO proof of pseudorandomness not composing for multiple copies of the same VRF with different PKs, because you have to program the RO in different ways that may contradict each other. Generally, hashing PK is good hygiene -- like salting hashes. Aside from proof issues, it simply makes attacker's job harder because you have to attack per PK, and precompute some crazy table once and for all."