Sharon Goldberg's research group at Boston University has a web site on VRFs with research references and applications, including key transparency in CONIKS, authenticated enumeration-resistant denial of existence in DNSSEC with NSEC5, and the Byzantine agreement protocol Algorand.
Here's a quick history of how negative answers work in DNS and DNSSEC. The things to watch out for are:
- Forgery of A records, so a MITM can direct legitimate users to evil hosts.
- Forgery of negative answers, so a MITM can cheaply deny service to legitimate users without getting out the wirecutters and digging a trench by their house.
- Consequences of breaking into a live nameserver but not an operator's airgapped laptop.
- Zone enumeration: what is the computational and network cost of enumerating all names in a zone?
The DNS can be used for many purposes, and you might want to prevent someone from enumerating all hosts on your network, or all users' if each user gets a unique hostname for their mailbox, or what-have-you. (Debating the merits of zone enumeration or its prevention is left as an exercise for a pyromaniac on an IETF mailing list.)
Unauthenticated version (NXDOMAIN):
Client: Can you give me the A record for stackexchange.com?
MITM: stackexchange.com does not exist.
Client: Thanks!
Server: stackexchange.com is at 1.2.3.4.
Client: What? I already had an answer which I acted on. Go away!
There's no way for the client to distinguish an answer by the legitimate nameserver from an answer by a malicious MITM—positive or negative.
This fails to thwart forgery of positive (1) and negative (2) answers, and if an attacker breaks into a live nameserver (3) then the legitimate operator can't recover until the longest TTL period after they regain control of the live nameserver or delegation. But zone enumeration (4) costs one network query per guess.
Hypothetical online signed version:
Client: Can you give me the A record for example.com?
MITM: example.com is CNAME for malicious.badguys which is at 4.3.2.1.
Client: What? That doesn't have a valid signature. Go away!
Server: example.com does not exist. Signed, --Server.
Client: Thanks. Can you give me the A record for example1.com?
Server: example1.com does not exist. Signed, --Server
...
Client: Thanks. Can you give me the A record for example11237.com?
Server: I'm tired and I'm out of CPU to answer legitimate queries because signing takes too much effort.
Attacker: I broke into the live server because it was running an unpatched version of BIND 8 and now I can forge records with wild abandon! Haha!
Operator: Damnit! I knew we should have chosen a protocol with an offline signing key.
The computational cost of signing every negative query seemed prohibitive at the time DNSSEC design began. The world has since changed, so that doesn't matter as much now.
This thwarts forgery of positive (1) and negative (2) answers, though if an attacker breaks into a live nameserver (3), which necessarily has a signing key, then it's much the same as the unauthenticated story. Zone enumeration (4) still costs one network query per guess.
Can we do signing offline instead?
Offline signed version (NSEC):
Client: Can you give me the A record for example.com?
Server: There are no domains between exampla.com and examplo.com. Signed, --Server
Client: Can you give me the A record for examplo1.com?
Server: There are no domains between examplo.com and exemption.com. Signed, --Server
Client: Can you give me the A record for exemption1.com?
Server: There are no domains between exemption.com and exuberate.com. --Signed, Server
...
Client: Aha! I have enumerated all the domains in the com zone!
This still thwarts forgery of positive (1) and negative (2) answers (as will all subsequent methods), and the signing key can be offline so the worst an attacker can do by breaking into the live nameserver (3) is deny service. But now zone enumeration (4) is amazingly cheap: it costs one network query per name in the zone, and negligible computation.
With the original NXDOMAIN system, the client must test each guess with a query to the server. With NSEC, the client can quickly skip large ranges of the space of names because the server says which ranges to skip.
Offline hashed signed version (NSEC3):
Here $H$ is a public hash function, such as SHA-256 iterated 1000 times.
Client: Can you give me the A record for example.com?
Server: There are no domains with hashes between H(foo.com) and H(bar.com). --Signed, Server
Client (after some work to find bar.com from H(bar.com)): Can you give me the A record for ejemplo.com?
Server: There are no domains with hashes between H(fnord.com) and H(fjord.com). --Signed, Server
...
Client: Aha! I have enumerated all the domains in the com zone!
Live nameservers still need not have signing keys. Zone enumeration costs more computation per guess now, but it still costs only one network query per name in the zone. Since the space of domain name labels is relatively sparse, it is not hard to guess them; there's even a prepackaged tool to automate the process called nsec3walker.
This is the point at which standard DNSSEC as of today stopped. CloudFlare took a middle ground between online signing and NSEC3 called ‘NSEC3 white lies’, eating the server's computational cost of signing each negative answer afresh and the cost of live nameserver compromise by storing the signing key online and answering ‘there are no domains with hashes between SHA256(query.com) and SHA256(query.com) + 1’. (NSEC3 white lies is what motivated CloudFlare to push for the deployment of elliptic-curve cryptography in DNSSEC, since its signing performance beats the pants off RSA's at the same security level.)
But there's another option with VRFs:
Offline VRF'd signed version (NSEC5):
Here H is a secret hash function, namely a VRF, with a corresponding public key that can verify proofs of the output of H.
Client: Can you give me the A record for example.com?
Server: There are no domains with hashes between H(bar.com) and H(foo.com), and here's a proof that H(bar.com) and H(foo.com) are evaluations of my secret hash function H at their respective inputs. --Signed, Server (NSEC5)
Server: P.S. ‘H(example.com)’ is H(example.com), and here's a proof of the fact. (NSEC5PROOF)
Client: Blast! I'm thwarted.
Forgery is prevented as usual. The cost of zone enumeration is back to one network query per guess, because the client cannot evaluate H(guess.com) to try a guess. And if an attacker compromises a live nameserver, although there is secret key material for evaluating H(query.com) when a client asks for a nonexistent query.com, that's useful only for evaluating the NSEC5PROOF postscript. The signing key for the NSEC5 record denying the existence of any domains between H(bar.com) and H(foo.com) can remain offline.
