FALCON-512 in PowerDNS

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.

PowerDNS Recursor 4.6.2 and 4.5.9 Released

We are proud to announce the release of PowerDNS Recursor 4.6.2 and 4.5.9.

Both releases are maintenance releases correcting an issue where a reload of a Lua script could cause in-flight queries to fail and an improvement in the caching of negative results. The 4.6.2 release contains a feature to disable processing of root-hints and improvements to the refreshing of “almost expired” records and processing of native dns64.

Please refer to the change logs for the 4.6.2 and 4.5.9 releases for additional details.

Please send us all feedback and issues you might have via the mailing list, or in case of a bug, via GitHub.

The tarballs (4.6.2, 4.5.9) and signatures (4.6.2, 4.5.9) are available from our download server and packages for several distributions are available from our repository.

The 4.3.x releases are EOL and the 4.4.x and 4.5.x releases are in critical fixes only mode. Consult the EOL policy for more details.

We would also like to repeat that starting with the 4.5 release branch we will stop supporting systems using 32-bit time. This includes most 32-bit Linux platforms.

We are grateful to the PowerDNS community for the reporting of bugs, issues, feature requests, and especially to the submitters of fixes and implementations of features.

Security Advisory 2022-01 for PowerDNS Authoritative Server 4.4.2, 4.5.3, 4.6.0 and PowerDNS Recursor 4.4.7, 4.5.7, 4.6.0

Hello,

Today we have released PowerDNS Authoritative Server 4.4.3, 4.5.4 and 4.6.1, and PowerDNS Recursor 4.4.8, 4.5.8 and 4.6.1 due to a low severity issue found in both products.

  • In the Authoritative server this issue only applies to secondary zones for which IXFR transfers have been enabled and the network path to the primary server is not trusted. Note that IXFR transfers are not enabled by default.
  • In the Recursor it applies to setups retrieving one or more RPZ zones from a remote server if the network path to the server is not trusted.

Tarballs and signatures are available at https://downloads.powerdns.com/releases/, and patches are available at https://downloads.powerdns.com/patches/2022-01/. However, the releases contain no other changes, with the exception of our EL8 builds, which were switched from CentOS 8 to Oracle Linux 8.

Please find the full text of the advisory below.


PowerDNS Security Advisory 2022-01: incomplete validation of incoming IXFR transfer in Authoritative Server and Recursor.

  • CVE: CVE-2022-27227
  • Date: 25th of March 2022.
  • Affects: PowerDNS Authoritative version 4.4.2, 4.5.3, 4.6.0 and PowerDNS Recursor 4.4.7, 4.5.7 and 4.6.0
  • Not affected: PowerDNS Authoritative Server 4.4.3, 4.5.4, 4.6.1 and PowerDNS Recursor 4.4.8, 4.5.8 and 4.6.1
  • Severity: Low
  • Impact: Denial of service
  • Exploit: This problem can be triggered by an attacker controlling the network path for IXFR transfers
  • Risk of system compromise: None
  • Solution: Upgrade to patched version, do not use IXFR in Authoritative Server

In the Authoritative server this issue only applies to secondary zones for which IXFR transfers have been enabled and the network path to the primary server is not trusted. Note that IXFR transfers are not enabled by default.

In the Recursor it applies to setups retrieving one or more RPZ zones from a remote server if the network path to the server is not trusted.

IXFR usually exchanges only the modifications between two versions of a zone, but sometimes needs to fall back to a full transfer of the current version.

When IXFR falls back to a full zone transfer, an attacker in position of man-in-the-middle can cause the transfer to be prematurely interrupted. This interrupted transfer is mistakenly interpreted as a complete transfer, causing an incomplete zone to be processed.

For the Authoritative Server, IXFR transfers are not enabled by default.
The Recursor only uses IXFR for retrieving RPZ zones. An incomplete RPZ transfer results in missing policy entries, potentially causing some DNS names and IP addresses to not be properly intercepted.

We would like to thank Nicolas Dehaine and Dmitry Shabanov from ThreatSTOP for reporting and initial analysis of this issue.

First Alpha Release of PowerDNS Recursor 4.7.0

We are proud to announce the first alpha release of PowerDNS Recursor 4.7.0.

Compared to the previous major (4.6) release of PowerDNS Recursor, this release contains the following major changes:

  • ZONEMD validation of the zones retrieved by the Zone to Cache feature.
  • A configurable way of adding Additional records to answers sent to the client.
  • The step sizes for Query Minimization are now computed following to guidelines in RFC 9156.
  • A Lua FFI hook for post-resolve interception: postresolve_ffi, to be documented before the final release.

There are also improvements in root-hints handling and resolving of IPv6 address of nameservers not learned by glue records. The latter has the consequence that, if applicable, nameservers will be contacted over IPv6 more often.

As always, there are also many smaller bug fixes and improvements, please refer to the changelog for additional details. When upgrading do not forget to check the upgrade guide.

Please send us all feedback and issues you might have via the mailing list, or in case of a bug, via GitHub.

The tarball (signature) is available from our download server and packages for several distributions are available from our repository.

With the final 4.7 release, the 4.4.x releases will be EOL and the 4.5.x and 4.6.x releases will go into critical fixes only mode. Consult the EOL policy for more details.

We would also like to mention that with the 4.5 release we stopped supporting systems using 32-bit time. This includes 32-bit Linux platforms like arm6, arm7, and i386.

We also like to announce the upcoming removal of XPF support. If you are using this feature, plan switching to the proxy protocol.

We are grateful to the PowerDNS community for the reporting of bugs, issues, feature requests, and especially to the submitters of fixes and implementations of features.

Authoritative Server 4.7.0-alpha1

Hello!

this is the first Alpha release for Authoritative Server 4.7.0. It brings a couple of new features into the hands of our users early.

New features:

  • lmdbbackend databases now get a UUID assigned, making it easy for external software to spot if a database was completely replaced
  • lmdbbackend databases now optionally use random IDs for objects
  • a new LUA function called ifurlextup

A full list of changes can be found in the changelog.

Please make sure to read the Upgrade Notes before upgrading.

The tarball (signature) is available at downloads.powerdns.com. Packages for various distributions are available from repo.powerdns.com.

Please send us all feedback and issues you might have via the mailing list, or in case of a bug, via GitHub.

Moving CentOS 8 builds to Oracle Linux 8

As you might be aware, CentOS 8 has reached End of Life on December 31st 2021. Furthermore, yesterday, CentOS 8 actually disappeared from the distribution mirrors. While we had made plans for this, we failed to execute those plans until now. This means we will need to switch build environments on some of our supported branches (Recursor and Authoritative 4.4/4.5/4.6, and dnsdist 1.5/1.6/1.7) mid release cycle. We are making those changes this week.

In mid-2021, we did extensive testing of building and running on the various CentOS alternatives, and came to one very clear conclusion – while the resulting binaries were not always bit for bit identical, the differences were uninteresting. Because of this, we believe users will not notice this change in our build environment at all and can continue to run our packages on their RHEL-derivative of choice.

However, just in case incompatible changes pop up, we are not switching the 7 build environment at this time.

Authoritative Server 4.6.0

Hello!

after a very useful beta/RC period in which we received some excellent bug reports, we released Authoritative Server version 4.6.0 today.

Version 4.6.0 mostly brings small improvements and fixes, but there are three notable new features:

  • support for incoming PROXY headers
  • support for EDNS cookies
  • autoprimary management via pdnsutil and the API

Support for PROXY headers allows you to put a load balancer (such as dnsdist) in front of the Authoritative Server, while still having the Auth see the actual IPs of clients talking to it.

EDNS Cookies allow resolvers that support it to have an extra layer of authentication on their communication with the Authoritative Server.

Compared to 4.6.0-alpha1, the major user visible change is the new NSEC3PARAM settings – check the upgrade docs below for more information. Besides that, various bugs have been fixed.

A full list of changes can be found in the changelog.

Please make sure to read the Upgrade Notes before upgrading.

The tarball (signature) is available at downloads.powerdns.com. Packages for various distributions are available from repo.powerdns.com.

Please send us all feedback and issues you might have via the mailing list, or in case of a bug, via GitHub.

PowerDNS Authoritative Server 4.5.3

Hello!

Today we published release 4.5.3 of the Authoritative Server. It contains several robustness fixes for the LMDB backend, and for the zone cache.

Please find a full list in the changelog.

Please make sure to read the Upgrade Notes before upgrading.

The tarball (signature) is available at downloads.powerdns.com and packages for various Linux distributions are available from repo.powerdns.com.

Please send us all feedback and issues you might have via the mailing list, or in case of a bug, via GitHub.

dnsdist 1.7.0 released

Hello!

We are proud to announce the release of dnsdist 1.7.0. This release contains several new exciting features since 1.6.1, as well as improvements and bug fixes. It contains one single change from the first release candidate, a fix for DynBlockRatioRule::warningRatioExceeded provided by Doug Freed.

In our view, the most exciting new feature of 1.7.0 is the support of outgoing DNS over TLS and DNS over HTTPS, as well as the ability to do “cross-protocol” queries, meaning a query received over a given protocol (UDP, TCP, DoT, DoH, …) can be forwarded over a different one. Now that dnsdist is capable of contacting its backend over an encrypted channel, full end-to-end encryption is possible, offering improved confidentiality and integrity.

Among the new features is the ability to add a custom EDNS option to a query before forwarding it to a backend, via SetEDNSOptionAction. phonedph1 also contributed a new rule making it possible to route a query based on the number of outstanding queries in a pool, PoolOutstandingRule.

Pierre Grié from Nameshield contributed an XDP program to reply to blocked UDP queries with a truncated response directly from the kernel, in a similar way to what we were already doing using eBPF socket filters. This version adds support for eBPF pinned maps, allowing dnsdist to populate the maps using our dynamic blocking mechanism, and letting the external XDP program do the actual blocking or response.

The packet cache has been improved so that one can now configure which EDNS options should be ignored, raising the cache hit ratio behind customer-premises equipment. The incoming and outgoing protocols have been added to the output of the grepq command for a better understanding of the recently processed traffic.

Dimitrios Mavrommatis improved the handling of AXFR and IXFR queries, making it possible to reuse a TCP connection used for a zone transfer much more efficiently.

We added support for generating the still experimental SVCB and HTTPS records directly from dnsdist, offering potential benefits to both performance and privacy.

Our LMDB code has gained the ability to do range-based lookups, and is now more performant even for simple lookups.

Extending the per-thread custom load-balancing policies introduced in 1.6.0, it is now possible to write blazing-fast, lock-less per-thread custom actions using the Lua foreign function interface.

Holger Hoffstätte also improved the reporting of an unavailable backend, making sure the existing metrics are no longer reported to prevent any confusion.

This release also reduces the memory footprint of dnsdist in several places, which makes it easier to use in resource-constrained environments.

Please see the dnsdist website for the more complete changelog and the current documentation.

Please send us all feedback and issues you might have via the mailing list, or in case of a bug, via GitHub.

The release tarball and its signature are available on the downloads website, and packages for several distributions are available from our repository.

With this release, the 1.4.x releases become be EOL and the 1.5.x and 1.6.x releases go into critical security fixes only mode.

Finally, we would like to thank the PowerDNS community and all external contributors for their great work in this release!

First Release Candidate for Authoritative Server 4.6.0

Hello!

Today we released the first Release Candidate for Authoritative Server version 4.6.0.

Version 4.6.0 mostly brings small improvements and fixes, but there are three notable new features:

  • support for incoming PROXY headers
  • support for EDNS cookies
  • autoprimary management via pdnsutil and the API

Support for PROXY headers allows you to put a load balancer (such as dnsdist) in front of the Authoritative Server, while still having the Auth see the actual IPs of clients talking to it.

EDNS Cookies allow resolvers that support it to have an extra layer of authentication on their communication with the Authoritative Server.

Compared to 4.6.0-alpha1, the major user visible change is the new NSEC3PARAM settings – check the upgrade docs below for more information. Besides that, various bugs have been fixed.

A full list of changes can be found in the changelog.

Please make sure to read the Upgrade Notes before upgrading.

The tarball (signature) is available at downloads.powerdns.com. Packages for various distributions are available from repo.powerdns.com.

Please send us all feedback and issues you might have via the mailing list, or in case of a bug, via GitHub.