The difficult quest for quantum computer-secure cryptography

Whoever controls the Domain Name System (DNS) determines what destination a browser actually heads to after resolving the server name. This means that if attackers give Internet users false IP addresses, they can lure them into traps in order to steal access data for online services.

Therefore, at least the starting point of the DNS (root zone) and most top-level domains such as .de or .com are protected using DNS Security Extensions (DNSSEC). The DNS information transmitted in plain text is signed cryptographically (eg IP addresses). In this way, recipients can use signature verification to ensure that the data has not been tampered with and that it comes from an authorized source. Encryption such as DNS-over-HTTPS can also be used to protect the data from manipulation, but the methods are only designed for part of the way and they are not suitable for authenticating the sender, which is why DNSSEC is indispensable.

Feigned Authority

But the signatures are based on conventional algorithms such as RSA and ECDSA, which are unlikely to withstand attacks with future quantum computers. The crux of the matter is the verification of trustworthiness: Anyone who breaks the signatures used for this can foist wrong but technically correct signed DNS responses and thus redirect browsers to specially prepared servers.

New, quantum computer-secure algorithms should help against such attacks (post-quantum cryptography, PQC). The US National Institute of Standards and Technology (NIST) coordinates the ongoing search for candidates. For example, NIST considers the TLS protocol to be particularly important because many Internet applications are based on it. If attackers record complete dialogs between client and server, they could crack the current TLS ciphers with powerful quantum computers in a few years. On the other hand, some selected by NIST new encryption algorithms help.

Initially, it remained unclear how well these algorithms were suitable for DNSSEC. To investigate this, Nils Wisiol, Matthieu Grillere and Peter Thomassen developed the toolset PQ-DNSSEC and published it on GitHub. The EU Commission is funding the project via the Dutch NGI Assure Fund.

Field test in sight

The toolset includes authoritative DNS servers and resolvers that generate and verify signatures of new algorithms. It can also be used to check the compatibility of implementations with the public DNS infrastructure using sample data sets. To this end, Wisiol and Thomassen are planning a field study with various algorithms and are looking for other collaborators.

So far, they have studied the Falcon512 algorithm, which according to initial analyzes from 2020 should deliver high speed and good performance. In their blog post from April 2022, they presented key generation, signing and validation with Falcon512. The bottom line was: Falcon512 generates key pairs and signatures slightly faster than the long-established RSA with 2048 bits and only slightly slower than ECDSA. When it comes to validation, Falcon512 is only beaten by RSA.

Problem child package sizes

But the DNS packets signed with Falcon512 are likely to be too large. The packet size is important for two reasons: Operators of authoritative DNS servers must provide enough storage space for the signed data. The longer the keys and the more signed DNS zones an authoritative server contains, the larger the space requirement. Operators of large DNS servers are therefore skeptical about long signatures.

The second reason is more serious: the fast User Datagram Protocol (UDP) is predominantly used for DNS communication. But in many old-fashioned home routers and some firewalls, DNS packets transmitted via UDP must not be larger than 1232 bytes. If they are, then they have to be fragmented, but the outdated systems discard UDP fragments for supposed security reasons. Now, DNS servers could switch to Transmission Control Protocol (TCP) as a substitute, but some aren’t designed to do that. Therefore, oversized DNS responses can be sent, causing the connection to fail.

A remedy is in sight: Two researchers recently proposed a mechanism, which allows a resolver to retrieve oversized DNS messages piece by piece from the DNS server. This would avoid fragmentation, which is unannounced from the recipient’s point of view. But it can take years for such a method to be standardized.

Therefore, the interim results of Wisiol and colleagues can currently be seen as a yellow traffic light for Falcon512: They found that only part of the Falcon512-signed DNS responses remained below the desirable UDP limit and advise looking for other alternatives for DNSSEC. Wisiol sees the Bimodal Lattice Signature Schemes (BLISS) algorithms, which were already described in 2013, as a good source of inspiration. BLISS is the first commercially used quantum computer-secure signature method. But in NIST analyses, BLISS performs poorly because the variants tested do not achieve the required safety level 5. Among other things, NIST requires that candidates be at least as difficult to crack as AES 256 (exhaustive key search). It doesn’t help much that BLISS generates smaller signatures than Falcon.

Hash trees as a last resort

Burt Kaliski, VeriSign’s Chief Technology Officer, suggests signatures based on Merkle Trees in a blog post. If Kaliski has his way, one could get shorter signatures from such a hash tree of DNS entries.

Meanwhile, in December 2022, NIST ushered in the next round of algorithm discovery at its fourth conference. The institute accepts proposals until June 1, 2023. Mainly one is interested in additional signature methods for “general purposes”. But special methods “are also possible, for example those that generate very short signatures”. That sounds like another door for new DNSSEC algorithms. In any case, the NIST does not intend to start the exact standardization of the first PQC methods until 2024.

(dz)