PQC in DNSSEC: padded or unpadded Falcon?
A format size analysis of Falcon signatures using .nl data
At SIDN Labs, we study post-quantum algorithms for DNSSEC within the PATAD research project together with University of Twente and SURF. Part of our work consists of evaluating the properties of post-quantum algorithms within the context of use in DNSSEC. Falcon is one such algorithm that is selected for standardisation by NIST, which is to be called FN-DSA when the final standard will be published. In this study, SIDN Labs and University of Twente collaborated to look at 2 Falcon signature formats in the context of DNSSEC: padded and compressed (or unpadded) signatures. We used real-world traffic from the .nl nameservers to evaluate the impact of using both those signature formats.
This blog post is based on a peer-reviewed article, which was published and presented at the ACM/IRTF Applied Networking Research Workshop 2025 (ANRW’25), co-located with IETF 123.
Falcon signature formats
In DNSSEC, we use cryptographic signatures to verify the integrity and authenticity of records. There is a potential threat that quantum computers will be able to break existing cryptography. Therefore, our focus is on post-quantum signature algorithms, such as Falcon. Between the Falcon-512 and Falcon-1024 variants, we chose the Falcon-512 variant because it provides sufficient security for use in DNSSEC. Falcon-512 is designed to meet NIST security level 1, which indicates that the algorithm’s security is comparable to that of AES-128 (128 bits).
Falcon-512 looks promising for use in DNSSEC, since the signatures are reasonably sized and its signing and validation performance is comparable to currently deployed DNSSEC algorithms. Since we already determined that Falcon-512’s signing and validation performance is comparable to the widely used non-PQC algorithms, we are now particularly interested in the effect of signature formats on DNS response sizes.
Falcon’s official implementation contains 3 signature formats:
Compressed signatures, the default, have the shortest average length. However, the length is variable. Falcon’s source code reports a test with 10,000 signatures, with an average length of 651 bytes (and a standard deviation of 2.55), but it includes a maximum of 752 bytes.
Padded signatures have a fixed length of 666 bytes. It’s the same as the compressed format, but signatures are padded to 666 bytes. If a computed signature is larger than 666 bytes, a new signature has to be computed.
CT signatures are longer (809 bytes) and have a fixed-size format. According to the source code, the CT signature format is useful for “uncommon situations in which the signed data is secret but of low entropy, and the public key is not actually public”. Since this situation does not apply to DNSSEC, we leave the CT format out of our evaluation.
For this study, we looked at the difference between compressed and padded signatures. We aimed to answer the question ‘Which Falcon signature format is most suitable for DNSSEC?’
Measuring the differences
To assess the effect of Falcon-512’s different signature formats, we created 2 signed versions of the .nl zone file: one signed with Falcon-512 in padded mode and the other with Falcon-512 in compressed (or unpadded) mode.
We first gathered all DNS queries sent to one of the authoritative name servers of the .nl zone over a 24-hour period. After that, we created 2 data sets based on the response codes that those queries received from our name servers: NOERROR (RCODE=0) and NXDOMAIN (RCODE=3). NOERROR indicates that the name server successfully returned a response to the query, and NXDOMAIN means the name server does not know the name that was queried. NXDOMAIN queries lead to a response from the name server with one or more signed NSEC3 records, which provide cryptographically verifiable proof that the domain name does not exist. The NOERROR dataset contains 59 million DNS queries and the NXDOMAIN dataset contains 113 million DNS queries.
We then sent all traffic from both data sets to 2 name servers that were configured for this study: one running the .nl zone file signed with Falcon-512 in padded mode, and one name server running .nl signed with Falcon-512 in compressed mode. We then replayed DNS queries from the 2 NOERROR and NXDOMAIN data sets onto both name servers, and measured and analysed the size distribution of the resulting replies.
We are specifically interested in 2 thresholds: 1,500 bytes (the default MTU for Ethernet) and 1,232 bytes (the recommended maximum DNS message size).
Padded or compressed?
The compressed Falcon-512 signatures for the .nl zone file exhibit a bell-shaped distribution with a median size of 655 bytes, as shown in Figure 1. The signatures are generally smaller than the fixed 666 bytes of padded Falcon-512. Although unpadded signatures can occasionally exceed 666 bytes, this is rare, and it occurred only once in a dataset of 9,912,711 signatures.
Figure 1: Size distribution of signatures for the .nl zone file signed with Falcon-512 using compressed signatures.
We then looked at the impact of the signature formats on real world DNS responses. The results for the NOERROR dataset are presented in Figure 2. We see that almost all responses that contain the requested data fit within the limit of 1,232 bytes. The right part of Figure 2 shows a series of responses between 1,532 and 1,622 bytes; each response contains one NSEC3 record. Each response is for a domain name that exists (hence the NOERROR reply), but the requested record type does not exist, leading to the extra NSEC3 record to cryptographically prove non-existence of the requested record type. The requests were almost exclusively for non-existing DS-records.
Figure 2: Histogram of the number of responses of a specific size (on a logarithmic scale) over a day for Falcon-512 DNSSEC responses for NOERROR responses. The vertical line is at 1,232 bytes (advised DNS maximum packet size).
We also analysed the NXDOMAIN dataset, the results of which are presented in Figure 3. All NXDOMAIN responses are larger than 1,232 bytes, and therefore can’t be sent in a single UDP DNS response packet that fits within the standard MTU of 1,500 bytes. In Figure 3, we can again distinguish 2 groups. On the left there are queries around 2,300 bytes, which each contain 2 NSEC3 records. The group on the right contain responses in the 3,000-3,200 bytes range, which each contain 3 NSEC3 records.
Figure 3: Histogram of number of responses of a specific size (on a logarithmic scale) over a day for Falcon-512 DNSSEC responses for NXDOMAIN responses.
Conclusions
Our findings indicate that the difference in DNS message size between padded and compressed signatures is minimal. While smaller signatures are theoretically advantageous, the use of the compressed signature format does not offer tangible real-world benefits. As our results demonstrate, compressed signatures do not result in a significant change in message size, nor do they allow more DNSSEC answers to fit within MTU limits.
These results provide valuable insights for the ongoing discussion on Falcon signature standardisation in DNSSEC. We conclude that standardising a fixed-size padded format may be preferable due to its predictability and the potential to prevent implementation errors.
