Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A cryptography engineer's perspective on quantum computing timelines

words.filippo.io

Post reply on HN
Print view View original

21–30 of 260 posts

Re: A cryptography engineer's perspective on quantum computing timelines

#21

Post by adrian_b »

FiloSottile wrote: post #18
adrian_b wrote: post #15

It should be noted that if indeed there has not remained much time until a usable quantum computer will become available, the priority is the deployment of FIPS 203 (ML-KEM) for the establishment of the secret session keys that are used in protocols like TLS or SSH. ML-KEM is intended to replace the traditional and the elliptic-curve variant of the Diffie-Hellman algorithm for creating a shared secret value. When FIP…

That was my position until last year, and pretty much a consensus in the industry. What changed is that the new timeline might be so tight that (accounting for specification, rollout, and rotation time) the time to switch authentication has also come. ML-KEM deployment is tangentially touched on in the article because it's both uncontroversial and underway, but: > This is not the article I wanted to write. I’ve had a…

I agree with you that one must prepare for the transition to post-quantum signatures, so that when it becomes necessary the transition can be done immediately.

However that does not mean that the switch should really be done as soon as it is possible, because it would add unnecessary overhead.

This could be done by distributing a set of post-quantum certificates, while continuing to allow the use of the existing certificates. When necessary, the classic certificates could be revoked immediately.

Re: A cryptography engineer's perspective on quantum computing timelines

#22

Post by amluto »

I was in this field a while back, and I always found it baffling that anyone ever believed in the earlier large estimates for the size of a quantum computer needed to run Shor's algorithm. For a working quantum computer, Shor's algorithm is about as difficult as modular exponentiation or elliptic curve scalar multiplication: if it can compute or verify signatures or encrypt or decrypt, then it can compute discrete logs. To break keys of a few hundred bits, you need a few hundred qubits plus not all that much overhead. And the error correction keeps improving all the time.

Also...

> Trusted Execution Environments (TEEs) like Intel SGX and AMD SEV-SNP and in general hardware attestation are just f**d. All their keys and roots are not PQ and I heard of no progress in rolling out PQ ones, which at hardware speeds means we are forced to accept they might not make it, and can’t be relied upon.

This part is embarrassing. We’ve had hash-based signatures that are plenty good for this for years and inspire more confidence for long-term security than the lattice schemes. Sure, the private keys are bigger. So what?

We will also need some clean way to upgrade WebAuthn keys, and WebAuthn key management currently massively sucks.

Re: A cryptography engineer's perspective on quantum computing timelines

#23

Post by palata »

What is the consequence on e.g. Yubikeys (or say the Android Keystore)? Do I understand correctly that those count as "signature algorithms" and are a little less at risk than "full TEEs" because there is no "store now, decrypt later" for authentication?

E.g. can I use my Yubikey with FIDO2 for SSH together with a PQ encryption, such that I am safe from "store now, decrypt later", but can still use my Yubikey (or Android Keystore, for that matter)?

Re: A cryptography engineer's perspective on quantum computing timelines

#24

Post by ekr____ »

OhMeadhbh wrote: post #19
OsrsNeedsf2P wrote: post #8

Why do we "need to ship"? 1,000 qubit quantum computers are still decades away at this point

So... In 2013 I was working for Mozilla adding TLS 1.1 and 1.2 support into Firefox. It turns out that some of the extensions common in 1.1, in some instances caused PDUs to grow beyond 16k (or maybe it was 32k, can't remember.). This caused middle boxes to barf. Sure, they shouldn't barf, but they did. We discovered the problem (or rather one of our users discovered the problem) by increasing the key size on server…

A few points here: There is already very wide use of PQ algorithms in the Web context [0], which is the most problematic one because clients need to be able to connect to any site and there's no real coordination between sites and clients. So we're exercising the middleboxes already.

The incident you're thinking of doesn't sound familiar. None of the extensions in 1.1 really were that big, though of course certs can get that big if you work hard enough. Are you perhaps thinking instead of the 256-511 byte ClientHello issue addressed ion [1]

[0] https://blog.cloudflare.com/pq-2025/ [1] https://datatracker.ietf.org/doc/html/rfc7685

Re: A cryptography engineer's perspective on quantum computing timelines

#25

Post by FiloSottile »

adrian_b wrote: post #21
FiloSottile wrote: post #18

Earlier quoted context omitted.

That was my position until last year, and pretty much a consensus in the industry. What changed is that the new timeline might be so tight that (accounting for specification, rollout, and rotation time) the time to switch authentication has also come. ML-KEM deployment is tangentially touched on in the article because it's both uncontroversial and underway, but: > This is not the article I wanted to write. I’ve had a…

I agree with you that one must prepare for the transition to post-quantum signatures, so that when it becomes necessary the transition can be done immediately. However that does not mean that the switch should really be done as soon as it is possible, because it would add unnecessary overhead. This could be done by distributing a set of post-quantum certificates, while continuing to allow the use of the existing cert…

How do you do revocation or software updates securely if your current signature algorithm is compromised?

Re: A cryptography engineer's perspective on quantum computing timelines

#26

Post by amluto »

palata wrote: post #23

What is the consequence on e.g. Yubikeys (or say the Android Keystore)? Do I understand correctly that those count as "signature algorithms" and are a little less at risk than "full TEEs" because there is no "store now, decrypt later" for authentication? E.g. can I use my Yubikey with FIDO2 for SSH together with a PQ encryption, such that I am safe from "store now, decrypt later", but can still use my Yubikey (or And…

Your Yubikey itself is doomed.

If you are doing a post-quantum key exchange and only authenticating with the Yubikey, then you are safe from after-the-fact attacks. Well, as long as the PQ key exchange holds up, and I am personally not as optimistic about that as I’d like to be.

Re: A cryptography engineer's perspective on quantum computing timelines

#27

Post by FiloSottile »

palata wrote: post #23

What is the consequence on e.g. Yubikeys (or say the Android Keystore)? Do I understand correctly that those count as "signature algorithms" and are a little less at risk than "full TEEs" because there is no "store now, decrypt later" for authentication? E.g. can I use my Yubikey with FIDO2 for SSH together with a PQ encryption, such that I am safe from "store now, decrypt later", but can still use my Yubikey (or And…

This article is more aimed at those specifying and implementing WebAuthN and SSH, than at those using them.

They/we need to migrate those protocols to PQ now, so that you all can start migrating to PQ keys in time, including the long tail of users that will not rotate their keys and hardware the moment the new algorithms are supported.

For example, it might be too late to get anything into Debian for it to be in oldstable when the CRQCs come!

Re: A cryptography engineer's perspective on quantum computing timelines

#28

Post by bitexploder »

janalsncm wrote: post #16

Building out a supercomputer capable of breaking cryptography is exactly the kind of thing I expect governments to be working on now. It is referenced in the article, but the analogy to the Manhattan Project is clear. Prior to 1940 it was known that clumping enough fissile material together could produce an explosion. There were engineering questions around how to purify uranium and how to actually construct the weap…

The Manhattan project employed some significant % of all of America. A project of that scale will likely never happen again.

It was also about far more than the science. It was about industrializing the entire production process and creating industrial capability that simply did not exist before.

Re: A cryptography engineer's perspective on quantum computing timelines

#29

Post by tkhattra »

OhMeadhbh wrote: post #13
schmichael wrote: post #10

Earlier quoted context omitted.

That's not a rebuttal. The post references the paper and a rebuttal to it from an expert in the field.

Damn. It's like I insulted Vault. Also, I went over Filippo's post again and still can't see where it references the Gutmann / Neuhaus paper. Are we talking about the same post?

From Filippo's post: "Sure, papers about an abacus and a dog are funny and can make you look smart and contrarian on forums."

Re: A cryptography engineer's perspective on quantum computing timelines

#30

Post by ekr____ »

FiloSottile wrote: post #25
adrian_b wrote: post #21

Earlier quoted context omitted.

I agree with you that one must prepare for the transition to post-quantum signatures, so that when it becomes necessary the transition can be done immediately. However that does not mean that the switch should really be done as soon as it is possible, because it would add unnecessary overhead. This could be done by distributing a set of post-quantum certificates, while continuing to allow the use of the existing cert…

How do you do revocation or software updates securely if your current signature algorithm is compromised?

As a practical matter, revocation on the Web is handled mostly by centrally distributed revocation lists (CRLsets, CRLite, etc. [0]), so all you really need is:

(1) A PQ-secure way of getting the CRLs to the browser vendors. (2) a PQ-secure update channel.

Neither of these require broad scale deployment.

However, the more serious problem is that if you have a setting where most servers do not have PQ certificates, then disabling the non-PQ certificates means that lots of servers can't do secure connections at all. This obviously causes a lot of breakage and, depending on the actual vulnerability of the non-PQ algorithms, might not be good for security either, especially if people fall back to insecure HTTP.

See: https://educatedguesswork.org/posts/pq-emergency/ and https://www.chromium.org/Home/chromium-security/post-quantum...

[0] The situation is worse for Apple.

Post reply on HN