[HN Gopher] Advancing Our Bet on Asymmetric Cryptography
___________________________________________________________________
Advancing Our Bet on Asymmetric Cryptography
Author : HieronymusBosch
Score : 135 points
Date : 2024-05-23 17:29 UTC (1 days ago)
(HTM) web link (blog.chromium.org)
(TXT) w3m dump (blog.chromium.org)
| quaunaut wrote:
| To tl;dr for people:
|
| - As we've known for years, cryptographically-relevant quantum
| computers(CRQC) likely could wreck digital security pretty
| massively
|
| - For HTTPS, 2 out of its 3 uses of cryptography are vulnerable
| to CRQC
|
| - The currently accepted algorithms that fix these
| vulnerabilities transmit 30+ times the data of current solutions,
| which for more unreliable network conditions(like mobile) can
| introduce latency by as much as 40%
|
| - Because attackers could store data now and decrypt it later
| with a CRQC, some applications need to deploy a solution now, so
| Chromium has enabled Kyber(aka ML-KEM) for those willing to
| accept that cost
|
| - However, other algorithms are being worked on to reduce that
| data size, but server operators for your applications at the
| moment can generally only use one certificate, which older
| clients like smart TVs, kiosks, etc are unlikely to support
|
| - So they're advocating for "trust anchor negotiation" by letting
| clients and servers negotiate on what certificate to use,
| allowing for servers to allow multiple at the same time
|
| Honestly really impressively written article. I've understood the
| risk that a cryptographically-relevant quantum computer would
| pose for years, but I didn't really know/understand what was
| being done about it, or the current state of things.
| k__ wrote:
| As far as I understood it, the tech is already there (Lattice-
| based algorithms, etc.) but nobody has bothered to deploy it yet.
|
| Probably a similar issue as IPv6.
| mcpherrinm wrote:
| The tech is only being developed and standardized now. Some of
| the post-quantum algorithms (like SIKE) have fallen. NIST
| standardization is ongoing. "nobody has bothered" ignores the
| fact that this is probably the biggest thing going on in
| cryptography right now. We're in the comments on a post about
| how Google is working towards adding support!
|
| And it's not really ready yet, unfortunately: The current post-
| quantum signature algorithms are too big for our current
| TLS/TCP/MTU packet sizes, and are going to be a big performance
| hit.
|
| One of the above post's authors has previously written about
| the size problem on his own blog:
| https://dadrian.io/blog/posts/pqc-signatures-2024/ - with
| comments at https://news.ycombinator.com/item?id=39796349
| ysofunny wrote:
| so any post-quantum crypto requires packets bigger than TCP
| can handle in a single message?
|
| I just super cynically see google pushing for quic and their
| other post-tcp visions for an internet even more theirs than
| it already is
| vlovich123 wrote:
| No that would be silly - TCP handles "infinite" length
| streams. The problem is that there's so much extra data for
| the cryptographic handshake that latency of establishing
| the connection is meaningfully higher by a lot and
| performance degrades by a meaningful amount. That's all.
|
| I don't know why OP brought in MTU and packet sizes since
| that doesn't really apply here. The most you could say is
| that the size exceeds the TCP window requiring an explicit
| ack but that's unlikely (windows are quite big) and
| everything I've read only talked about the latency of the
| handshake being caused by the much larger data exchange
| needed (ie if TLS handshake requires 32 bytes each way,
| Kyber and friends need to send 1kib each way [1])
|
| [1] https://blog.cloudflare.com/post-quantum-for-all/
| ysofunny wrote:
| regardless of all that, I must now think about the
| correlation between cryptographic strengths and amount of
| information necessarily transmitted
|
| is there such a correlation? why? how does it work? i
| don't even....
| vlovich123 wrote:
| I'm not enough of an expert to cut through your
| confusion. if I recall correctly the cryptographic
| signature size has always been tied with the size of the
| key which determines the strength. The larger the key,
| the larger the signature and "more cryptographic
| strength". What's new here aside from the signatures
| being an order of magnitude larger than before and having
| different growth factors with increasing key size?
| ysofunny wrote:
| the involvement of quantum computing devices?
|
| which is something else I must admit I cannot really fit
| together with what I imagine I understand about
| "classical" computing
|
| but in information theoretic terms does it matter whether
| you use quantum or typical computers??? I would think
| that it does not matter but I may be wrong and I couldn't
| really explain why
| vlovich123 wrote:
| The involvement of the quantum computer is only that it's
| an adversary that can break asymmetric encryption with
| different complexity constraints than a classical
| computer. For example, take two random prime numbers as a
| secret and publish the result of multiplying them. It
| turns out that if you want to find the two random prime
| numbers by knowing only the result of multiplication is a
| hard problem known as integer factorization. If you
| double the size of the prime numbers, discovering them
| takes exponentially longer. The theoretical quantum
| computer model though says that it can accomplish it in
| sub-exponential time. Now doubling the size of the number
| only increases your compute requirements by ~2x to
| recover the prime factors (specifically it's actually a
| logarithm so it's < 2x more compute is needed). The
| algorithm for doing this is known as Shor's algorithm [0]
| and because of how complexity works in computer science,
| it turns out that this algorithm can be applied to many
| many problems mechanically and these problems are the
| underpinnings of RSA, DSA, ECDH key exchanges.
|
| These quantum-resistant algorithms are based on
| mathematical problems believed to be exponentially
| difficult even for a theoretical quantum computer - when
| you double the size of the problem, it again takes
| exponentially more time even for a theoretical quantum
| computer. These are of course unproven beliefs but that's
| true of classical algorithms too. So no, it doesn't
| matter where you run the cryptographic algorithm; it
| remains computationally difficult to solve the problem
| without knowing the secret. The quantum computer is
| critically important though for your ability to crack
| classical problems though - without it, all of this post-
| quantum cryptography is unnecessary.
|
| [0] https://en.wikipedia.org/wiki/Shor%27s_algorithm
|
| [1] https://arxiv.org/pdf/2212.12372
| btdmaster wrote:
| Interesting tidbit from the paper, they suggest to
| "ignore" O(log(n)^3/2) and take it as equivalent to
| O(log(n)), even though strictly speaking this is not
| correct, in one of their time complexity proofs.
| dadrian wrote:
| > I don't know why OP brought in MTU and packet sizes
| since that doesn't really apply here.
|
| It does apply. TCP exposes streams as the API, but the
| underlying data is still sliced into packets of size up
| to the MTU.
| thadt wrote:
| Interesting. It does seem that being more agile in PKI deployment
| is going to be a requirement in the next few years as we grapple
| with rolling out a potentially interesting variety of PQ
| signatures and hybrids.
|
| Especially considering exploding PQ signature and key sizes, this
| looks increasingly like a data synchronization problem between
| the server and clients. I wonder if we could kill two birds with
| one stone by using trust expressions consisting of a set of
| certificate indexes against a trust store database, instead of
| trust store versions and exclusion labels. In that model, a trust
| store is just a centrally managed list where each certificate is
| assigned a unique 64-bit index.
|
| For example, a client says "I use trust store database XYZ with
| certificate indexes: <ordered, integer compressed 64-bit index
| list, maybe a couple hundred bytes>". The server constructs (or
| pulls a cached copy of) a trust chain from one of the listed
| roots and sends it to the client. Intermediate certificates may
| _also_ be stored in the trust store database - and cached on the
| client. In subsequent requests, the client may include those
| intermediate indexes in their request, allowing the server to
| respond with a shorter chain. Clients with an old, long trust
| chain might have a long first exchange, but after caching
| intermediates can have a much faster /shorter negotiation. As
| certificates expire, they are removed from both the trust store
| database, as well as the client's cache - naturally moving the
| 'working window' of certificates forward over time.
|
| This shifts a bit of work on the server, but dramatically reduce
| complexity on the client. The client just states which
| certificates it has and what algorithms it supports, and the onus
| is placed on the server to return the "shortest" chain that the
| client can use as a proof.
| chrisdinn wrote:
| Is "advancing our amazing bet" a nod to the Google Fiber
| turndown?
| nekoashide wrote:
| This has been causing a number of issues with proxys, we use
| nginx and we have started to see problems with chrome users and
| handshakes not working properly.
| upofadown wrote:
| If this lowers performance, can we just turn it off and forget
| about it?
| er4hn wrote:
| One perpetual source of concern that I have is how will this work
| in practice? NIST has not standardized algorithms as of yet. NSA
| has come out in opposition of hybrid schemes (note that NSA is
| also a big fan of CsfC, which uses entirely seperate dual layers
| of crypto, which could be how they would have a hybrid scheme -
| one layer classical, one layer pqc. Will they? I ahve no clue).
| But this protocol is still a draft.
|
| OpenSSH has chosen their own algorithm that afaik was on the NIST
| shortlist for PQC but not a final candidate and incorporated it
| in OpenSSH. That's not standardized either.
|
| Given that Govt (which mandates encryption requirements via blunt
| tools like saying they will only purchase things that meet their
| requirements) and Industry are going two ways, and industry is
| doing whatever they think best without waiting for
| standardization, it feels like this is going to be a source of
| headaches to support properly in the future due to the diversity
| of schemes.
|
| I am actually in favor of what Google / OpenSSH are doing,
| enabling new things shouldn't be breaking stuff, and should just
| be a net positive in their own bubbles, but the govt opposition
| and foot dragging makes this harder.
| tptacek wrote:
| Everybody is going to use hybrid schemes for the foreseeable
| future.
| dadrian wrote:
| Unlikely that signatures will ever be hybrid.
|
| Fairly likely we move off of hybrid for key exchange once
| NIST finishes standardization.
| thadt wrote:
| Geez, turbolaser X-Wing before it even gets in the air. Can
| y'all just give us a SCW death-match debate on this?
|
| Jokes aside, it would be interesting to have your
| optimistic take on the current PQ security trajectory. Do
| you think that it has proven comparably secure to ECC? Or
| just that by the time PQ primitives are ready to be rolled
| out they'll be load bearing enough that it is better to use
| them solo rather than the added overhead/complexity of a
| hybrid?
| tedunangst wrote:
| Doubling down on my bet nobody reading this will live to see a
| quantum computer that breaks year 2000 era crypto.
| sebzim4500 wrote:
| Is there a way to put money on this? I'd be willing to put down
| a fair amount against your prediction.
| wcoenen wrote:
| If they win the bet against you, you'll both be dead by
| definition of the bet. Therefore the bet doesn't make sense
| and shouldn't be taken seriously.
| im_anon_on_hn wrote:
| It could go to the estate.
| janalsncm wrote:
| Encrypt a file with "2000s era cryptography" (not too sure
| what that would be). The file contains instructions on how to
| unlock a sum of money.
| sebzim4500 wrote:
| Ok, but how do I make money from that?
| xhkkffbf wrote:
| You could bet in Bitcoin. If the quantum computer doesn't
| exist, one person gets it. If the quantum computer appears
| that can break the Bitcoin digital signatures, well, then the
| Bitcoin is worthless.
| tedunangst wrote:
| For some reason, this reminds me of the ding dong who bet
| bitcoin would hit a million dollars, immediately lost, then
| claimed he was the real winner because it proved people
| were interested in bitcoin.
| sebzim4500 wrote:
| That bet was the least interesting thing about John
| McAfee.
| sebzim4500 wrote:
| I'm sure someone smarter than me can come up with a way of
| making bitcoin quantum-safe with a soft fork.
|
| Of course, the addresses created right now would still be
| at risk.
| tedunangst wrote:
| Problem with long term bets is time value eats away at
| escrow. But sure, come back in 20 years and we'll settle up
| at whatever a week's worth of US median salary is. (For
| specifics, 2000 era crypto is 1024 bit RSA. I'm not betting
| against a conventional supercomputer factoring such coprimes
| though.)
| arglebargle123 wrote:
| One of the University of Iowa B schools runs a futures market
| that'll let you bet on predicted event outcomes
|
| https://iem.uiowa.edu/
|
| https://en.m.wikipedia.org/wiki/Iowa_Electronic_Markets
| juped wrote:
| This ends up being a bet mostly about medical life extension,
| since drastically longer human lifespans are more likely than
| quantum computers going anywhere soon.
| shaftway wrote:
| Inside Google "Advancing our bet" is a euphemism for shutting
| down (hat tip to Fiber). I'm deeply surprised that an article
| came out with that title that is actually true, given how
| negatively that phrase is seen.
| Nition wrote:
| I remember there was a great 'translation' of that fibre post
| on Hacker News at the time:
| https://news.ycombinator.com/item?id=12793033
| dadrian wrote:
| It's a joke, because it's about migrating off of pre-quantum
| asymmetric cryptography.
| wiktor-k wrote:
| Hmm... this is about PQ cryptography while I was expecting a
| status update of Ed25519 in WebCrypto which, sadly, is still
| available only via experimental platform flag:
| https://caniuse.com/mdn-api_subtlecrypto_verify_ed25519
| xvector wrote:
| This is a really well written article.
___________________________________________________________________
(page generated 2024-05-24 23:01 UTC)