We are proud to introduce the first guest post on our blog! A team of researchers (listed below) has chosen PowerDNS as the basis for an implementation of post-quantum DNSSEC signing with the FALCON-512 algorithm. Below, you will find their experiences, including links to runnable code.

Authors: Matthieu Grillere, Peter Thomassen, Nils Wisiol (nils@desec.io)

Introduction

Just like public-key cryptography in virtually all applications today, digital signatures used in DNSSEC are subject to key recovery attacks using Shor’s algorithm. In contrast to classical algorithms, Shor’s algorithm cannot be executed on a regular computer. To run it, a quantum computer of sufficient size is required. As of today, it is unclear if and when such a computer can be built. Researchers are working on building large quantum computers, but also on providing alternatives to both RSA and Elliptic Curves (EC), today’s commonly used public-key cryptography schemes, so they are ready before quantum computers arrive.

Many of these efforts are motivated by the fact that encrypted data, once recorded somewhere along its way through the Internet, can be stored to be decrypted later, as soon as suitable computers are available. In addition, digital signature schemes are also threatened by Shor’s algorithm (and possibly other cryptanalytic applications of quantum computers).

The United States National Institute of Standards and Technology (NIST) has moved to standardize quantum-secure replacements for today’s RSA- and EC-based cryptographic schemes, both for key exchange mechanisms (as used in TLS) and for digital signatures. In case of the advent of large quantum computers, DNSSEC will need such a quantum-secure digital signature scheme to authenticate DNS data.

In the proceedings of NIST, several digital signature schemes have been proposed and evaluated with respect to their security, public and private key sizes, signature size, and implementation performance. So far, none of the proposed schemes could provide the security and characteristics similar to what we know from RSA and Elliptic Curve schemes. Instead, the schemes suffer from large keys, large signatures, and/or poor performance.

In a detailed analysis, Moritz Müller et al. have evaluated different schemes with respect to their aptness for usage in DNSSEC and found that FALCON-512, while not optimally suited, shows the best characteristics. This choice has been mostly based on public key size and validation performance.

To see how well DNSSEC based on FALCON-512 really integrates in the existing global DNS infrastructure of the Internet, we have extended PowerDNS to sign and verify DNS data using FALCON-512. Using our fork, we maintain a test zone with FALCON-512 signatures at falcon.example.pq-dnssec.dedyn.io which can be queried using your favorite resolver using, e.g., dig TXT falcon.example.pq-dnssec.dedyn.io @9.9.9.9 +dnssec. We also provide a public test resolver that can validate the signatures and can be queried using dig TXT falcon.example.pq-dnssec.dedyn.io @ns.example.pq-dnssec.dedyn.io -p 5302 (observe the AD flag).

Implementation

PowerDNS can be compiled to use OpenSSL for cryptographic functions such as key generation, signing, and signature verification. As there is already an OpenSSL fork maintained by the Open Quantum Safe project (OQS) that includes an implementation of FALCON-512, the combination of OpenSSL and PowerDNS is very handy to create our experimental setup.

The code additions to PowerDNS are quite straightforward. However, PowerDNS uses the EVP interface of OpenSSL, which did not yet support all needed functionality in the OQS fork. We added support for raw key management  to the EVP interface used by OQS keys, but skipped support for hybrid keys, as they are not required by PowerDNS. Another difference to the existing algorithm implementations in PowerDNS is that for FALCON-512, we need to store both the public and private key. For FALCON-512, recovery of the public key from the private key is not supported by design.

A more detailed list of our changes to PowerDNS can be found on GitHub. Our complete experimental setup, including our forks of OQS OpenSSL and PowerDNS, can also be found on GitHub.

Evaluation

We evaluated DNSSEC with FALCON-512 with respect to several metrics. In designing those metrics, we took into consideration all parties involved when maintaining or querying DNS information.

First, for signing the zone, keys need to be generated and stored, and several signatures need to be generated. Operators of authoritative DNS servers are thus interested in small key sizes and fast key generation and signing algorithms.

Second, the public key and relevant signatures need to be conveyed to the DNS resolver when it is queried by a user. As not all resolvers support DNS over TCP, and maximum UDP payload varies for each network, there is a risk of DNS information becoming unavailable if DNS responses by the authoritative DNS server become too large. There is also concern that large DNS responses to small UDP queries will be abused in amplification attacks. Hence, DNS operators are also interested in small response packets.

Third, DNS resolvers may need to validate many signatures in a short period of time. Operators of DNS resolvers are thus interested in fast validation times.

We hence evaluate our implementation of DNSSEC with FALCON-512 with respect to required storage for cryptographic keys, run time of key generation, signing, and validation algorithms, and packet sizes resulting from typical requests.

Database Storage

Like for other algorithms in PowerDNS, keys are stored in a SQL database in base64 format. This increases the storage space required for the public key from 897 bytes (raw format) to 1196 bytes and for the private key from 1281 raw bytes to 1708 bytes in storage. Together with 72 bytes formatting overhead, the grand total for a single key pair in PowerDNS storage is 2976 bytes.

For comparison, this is less than double what is required for a 2048-bit RSA key pair, but an order of magnitude more than what is required for key pairs for DNSSEC algorithms based on Elliptic Curves (ECDSA and ED variants).

Internal Benchmark

To assess performance of its crypto operations, PowerDNS ships an integrated benchmark that can be called using pdnsutil test-algorithms. It returns the average run time for keypair generation, signature generation, and validation for each combination of algorithm and used library, based on 100 samples. To obtain a good average, we ran this benchmark 100 times, resulting in a total of 10,000 samples for each combination of algorithm and library. In this assessment, we only consider implementations of OpenSSL as comparison.

For key generation, where high performance is arguably not critical, we found that FALCON-512 is faster than generating an RSA key pair with 2048 bits by an order of magnitude, but also an order of magnitude slower than the available Elliptic Curve algorithms.

For signing, we found that FALCON-512 is on par with ED448, i.e. slightly faster than RSA (2048 bits), but an order of magnitude slower than ECDSA P-256 and ED25519.

For verification, arguably the most performance-critical aspect, FALCON-512 is slower than RSA (2048 bits), but faster than the Elliptic Curve algorithms. In the case of the currently less popular options of ECDSA P-384 and ED448, it is even faster by an order of magnitude.

We conclude that while FALCON-512 has performance degradation in some aspects, it also improves on others. 

We conclude that if you accept the performance of 2048-bit RSA and ECDSA P-256 at some point, it will be hard to argue against FALCON-512 for performance reasons.

End-To-End Benchmark

To practically confirm our most important performance assessment, the validation performance, and to rule out the possibility that any other part of PowerDNS may degrade performance when using FALCON-512, we created a complete test bench of an authoritative DNS server, a resolver, and a DNS client as a Docker application.

To avoid biases from optimizations not related to the choice of signing algorithm, the resolver in the test bench is configured to not use its packet cache, and aggressive NSEC caching has been disabled. For a zone with a wildcard record, this means that each query incurs a signature validation. Performance effects from additional round trips (common due to truncation of large responses) are erased by increasing the MTU between authoritative name server and resolver to an unrealistically high value. This enables communication between resolver and authoritative name server to exclusively happen over UDP. Communication between the client and the resolver happens exclusively in TCP. Overall, this setup enables us to use the query-response time as a measure for the validation performance of the resolver.

Qualitatively, our findings obtained with this setup match the PowerDNS benchmark well. While measured query-response times are orders of magnitudes higher than what is required just for validation, we can see confirmation that validation of FALCON-512 signatures is on par with RSA (2048 bit) and outperforms all Elliptic Curve schemes.

Packet Sizes

Lastly, we evaluated the packet sizes generated by typical responses when signed with FALCON-512. The community often treats 1232 as the maximum safe packet size for DNS messages that are sent over UDP; compatibility with some parts of the DNS infrastructure may be broken if larger packets are used. For our study, we tested the packet sizes for a number of different DNSSEC-enabled queries, including responses containing two A records with signature, one AAAA record with signature, one AAAA record with signatures as required by a wildcard record and NSEC, the same case but for NSEC3, and a response including one DNSKEY record carrying a FALCON-512 public key (with signature). All signatures use FALCON-512.

Our results show that while the cases of two A records and one AAAA record stay well below the 1232 byte bar, all others exceed it. This means that if a resolver is asking for DNSSEC at the authoritative server, but does not support large UDP responses and does not support TCP fallback, the data in the zone will become unavailable at this resolver. As far as we know there is no public data on how many resolvers are affected (if any).

In contrast, all tested scenarios stay well below the 1232 byte bar when using any of the other available DNSSEC algorithms. We also point out that for migration to FALCON-512, at least for a short while, signing the zone with two algorithms is required. (Let’s not consider going insecure for an algorithm upgrade an option.)

Public Test Bench

To facilitate tests, we operate a zone signed using FALCON-512 (with algorithm number 17) at falcon.example.pq-dnssec.dedyn.io, which can be queried using the resolver of your choice (query for TXT records). We also operate a public DNS resolver with validation support for FALCON-512 at pq-dnssec.dedyn.io on port 5302 (try dig TXT falcon.example.pq-dnssec.dedyn.io @pq-dnssec.dedyn.io -p 5302) For a quick look, check out our HTTP-based query interface at https://pq-dnssec.dedyn.io/.

Our complete test bench is available on GitHub and includes the fork of PowerDNS and OQS OpenSSL, as well as the test bench and any analysis and testing scripts that were used in our work.

The root KSK rollover is currently planned for 1600 UTC on the 11th of October 2018 – a few days from now. If you are using PowerDNS Recursor for DNSSEC validation, please keep reading!

During the KSK rollover, the root zone will stop using the old root Key Signing Key, known as KSK-2010 or 19036, and will start using the new Key Signing Key, known as KSK-2017 or 20326. Your Recursor needs to be aware of both keys to make sure validation keeps working after the rollover event.

If you are running Recursor 4.0.5 or up, both keys come preconfigured. If you are running an older 4.0.x version, it is possible your distribution has added the key for you.

In case of any doubt, verify you are ready:

# rec_control --socket-dir=. get-tas
Configured Trust Anchors:
.
19036 8 2 49aac11d7b6f6446702e54a1607371607a1a41855200fd2ce1cdde32f24e8fb5
20326 8 2 e06d44b80b8f1d39a95c0b0d7c65d08458e880409bbc683457104237c7f8ec8d

The output should have both the 19036 and 20326 lines. If 20326 is missing, please upgrade your Recursor. If for some reason upgrading is not feasible for you right now, please follow the PowerDNS Recursor instructions that ICANN published. Those instructions involve a restart; if you want to avoid a restart this week, please see Runtime Configuration of Trust Anchors in the PowerDNS documentation.

In case of panic (in the unlikely event ICANN botches the roll, or the roll finds a bug in our software), you can run rec_control add-nta . DNSSEC on root is broken to disable DNSSEC immediately without restarting your daemon.

Should you have any trouble: if you are a supported customer, please reach out through the usual channels. Otherwise, contact us via our community channels.