Post-Quantum public keys might be too large for DNS over UDP.

[named-dodo]

RSA is eventually going to deprecate due to quantum computers being able to break it.
It will be replaced with Quantum resistant public cryptography algorithms.
However, the public key size for these algorithms might be too large for DNS over UDP.
(Packet fragmentation over UDP isn't fun or high performance.)

That leads to looking at other protocols and how they are supported on different platforms.
We need solutions, alternatives, etc.

From original post by @jsklein in https://github.com/hackerfactor/VIDA/discussions/4#discussioncomment-10010847

[hackerfactor]

Personally, I'm very hesitant to develop a solution until we know more about the problem.

This same problem is going to bite DKIM. Does VIDA want to be based on DKIM or do we want to try to make DKIM follow VIDA? Or, when the post-RSA solution develops, do we want to diverge from DKIM? Because DKIM is a widely accepted standard (including for use in a court of law), I don't like the "diverge" option.

When quantum comes out, RSA will be deprecated. However, we don't know if that is within a year or a decade. It's very possible that the underlying DNS problem may be resolved before RSA becomes deprecated, making it a non-issue. (DNSSEC, DNS over TCP, DNS over QUIC, large-packet UDP, etc.)

This is one of those scenarios where I don't want to panic into a solution before we know more about the problem and other options.

[named-dodo]

There's no need to panic, but it also shouldn't be ignored.
Can we figure out or ask whoever is working on DKIM if they have a solution or are working on one?

The DNS limits being resolved before Post-Quantum hits would be nice.
What do we do if it doesn't though?

What is the maximum size we can put inside TXT records?
And whatever public keys the current PQ cryptography uses, does it inside that?

[hackerfactor]

I've sent an email to the IETF mailing list. Let's see if they have someone working on the problem.

[hackerfactor]

Cross linking to the IETF posting:
https://mailarchive.ietf.org/arch/msg/ietf/yGIYTmr4CGXQK4yf6P8j1kHGkvQ/

I've had two responses so far. One had zero content (because the person sent something that was filtered out by the mailing list). The other only responded to me and not to the list. (Because it was a direct email, I'm not including names.)

>I'm currently looking at DKIM (for email; RFC 6376).
>DKIM uses RSA for signing emails.

It also uses ED25519.  See RFC 8463.  Once the world decides what PQ signing algorithms to use, we'll update it again.

>The problems:
>
>  - Quantum keys are expected to be much larger than RSA keys.

These issues are well known.  [redacted] wrote a comment to NIST (sent from the ICANN SSAC and from M3AAWG) pointing out the size limits on DNS packets so they're aware of them too.

My personal guess is that we'll end up using a scheme that has tractable keys and enormous signatures, and use hashes of the signatures, keeping in mind that hashing is not amenable to quantum speedup.

>  - Hope that DNS-over-TCP or DNS-over-QUIC (or anything else "not UDP") catches on before quantum becomes a standard.

DNS-over-TCP caught on at least a decade ago.  It's hard to retrieve DNSSEC key sets that have multiple keys and signatures without it.

> Is anyone working on this problem?

Perhaps you should ask the pquip working group.

https://datatracker.ietf.org/wg/pquip/about/

Keep in mind that nobody expects quantum computers to work at least for another decade, and neither DNSSEC nor DKIM depend on long lived secrets.

[hackerfactor]

Great response from Phillip Hallam-Baker (https://mailarchive.ietf.org/arch/msg/ietf/jocMOBSRFS9RQp7V8e75H2AEMUk/)

1. Quantum is not a done deal. It may be "never".
2. There's a simple solution if the key gets too large: store the public key in the DKIM header (or in this case, the VIDA record) and store a hash of the public key (sha256, whatever) in DNS. This still links the public key to the domain.

I actually like that 2nd option a lot. It means that you can validate a signature even if you are offline. (When offline, it can be validated but not linked back to the domain. Linking to the domain requires being online.) Maybe we need pub= as an option?

[named-dodo]

I think the pub= would be a decent solution, but i would then start to worry about VIDA record size if those public keys are really as large as they expect them to be. I'd like to avoid ./well-known/, but it might very well be the most stable fall-back mechanism we know of.

Alternatively, i think the DNS system should evolve to support larger record sizes to accommodate for PQ public keys.
(But i bet they are already working on that. At least, i hope they are.)