8 ms·
Google's threat model for post-quantum cryptography
- rihegher 3y agoIn short all encrypted data transiting through internet will get uncrypted once quantum computing is there. As if we didn't already had enough threats to worry about...
- deleted 3y ago[deleted]
- Culonavirus 3y ago[flagged]
- ctz 3y ago[flagged]
- deleted 3y ago[deleted]
- tptacek 3y agoStateless tokens come with independent security concerns, and moving towards stateful tokens is prudent just to ensure more robust systems. [...] Our main recommendation is to use stateful tokens where possible, given their additional security benefits. This is smart. PQC schemes often add too much overhead for interoperable cookie sizes. Instead of trying to cram a PQC signature into a cookie, just stop using the stateless cookie designs that require asymmetric signatures. I'm not sure I buy the Global Risk Institute chart. I get that they need to motivate adoption, but practical cryptanalytic work with quantum computers seems unpromising right now.
- deleted 3y ago[deleted]
- dist-epoch 3y agoIs there any insight why there is no PQC signature with a short signature? Is it just us failing to find one, or something more fundamental prevents a quantum resistant short signature like?
- some_furry 3y agoThe kind of math problems that are hard for quantum computers to break tend to produce kilobyte+ outputs at our target security levels.
- adastra22 3y agoI’m confused because there are such things. What you want here is authentication, and there are hashing modes which provide that.
- some_furry 3y agoThey specifically asked about PQC signatures, not MACs.
- nmadden 3y agoWell, there are PQC (public key) signature schemes based on hash functions, but they all have large signatures (in the multi-kB range) and other drawbacks (eg being stateful). Moving to a MAC is also not a crazy idea in a lot of deployments. You can horizontally scale an internal MAC validation service. I believe Facebook use MAC-based tokens internally (CATs).
- adastra22 3y agoThere are hashing modes that achieve both integrity and authentication. It usually involves prefixing the data with a server-provided secret before hashing. Only someone who knows the secret can produce such a hash, thereby providing both authentication and data integrity. Cookies are signed by the server, not the client, and only the server needs to check the signature, so there really isn’t any reason to use much more expensive asymmetric cryptography. And post-quantum security is just a bonus. In the context of cookies, authenticated hashing IS a PQC signature.
- adtac 3y agoEven if the cookie size limit was 8192 bytes instead of 4096, I think it's insane to include a several KB signature on every request over the network (literally worth multiple packets). It's not a big deal if the payload is a large media file, but JWTs are most commonly used in the kind of API requests where the body is often empty or something tiny like {"success": true}. It'd be a shame to undo all the wins from things like smaller TLS handshakes using ECDSA (more of a pleasant side effect, but still).
- esprehn 3y agoThe header dictionary for http2 makes large headers like cookies less of an issue: https://blog.cloudflare.com/hpack-the-silent-killer-feature-of-http-2/ https://blog.cloudflare.com/hpack-the-silent-killer-feature-... Which means it's only sent once per connection.
- nine_k 3y agoThis is good for browsers which do a ton of requests to the same resource. It's less useful for service-oriented architecture where services would more often talk to other services through an LB, often contacting different nodes.
- nimih 3y agoAre you regularly using stateless, asymmetrically-encrypted tokens during service-to-service communication? That strikes me as a rather odd architecture decision, but maybe there's something I'm missing.
- _tk_ 3y agoThey mention they are working on their own QC. In corporate logic, using a third party projection to make a statement about where you are headed seems absolutely legit to me.
- NovemberWhiskey 3y ago>I'm not sure I buy the Global Risk Institute chart. I get that they need to motivate adoption, but practical cryptanalytic work with quantum computers seems unpromising right now. Yeah; that doesn't look right to me either. Perhaps "cryptographically relevant" has some unusual meaning (parity with conventional computing?). Otherwise, the consensus view is that there's, pessimistically, a 4% probability of a total break of all public key cryptography within 5 years. That's practically "abandon all hope right now" territory rather than "motivate adoption" territory.
- xhkkffbf 3y agoWho came to this consensus? I'm not aware that the quantum machines have been able to do much beyond, say, factoring 21.
- Rebelgecko 3y agoI think they were factoring 21 a decade or so ago. Now the record is at least 261,980,999,226,229. Although my understanding is that this # was somewhat cherry picked and the algorithm they used (not shor's) worked well on this 48 bit number but wouldn't scale as well as Schor's algo to sizes that are cryptographically meaningful
- hnaccount_rng 3y agoDo you have a reference for that achievement?
- hammock 3y agoAre there privacy concerns with stateful tokens?
- worksonmine 3y agoNo more than there would be with a stateless one, they're both used to authenticate a request after all.
- dvh 3y agoThis may be a naive question but why not go back to Vernam? Storage is cheap.
- Retr0id 3y agoOTP is deeply impractical. How do you distribute your pads? (hint: it's a chicken-and-egg problem, you need a secure channel) How do you ensure they're only ever used once? In its most obvious instantiation, you get no authentication. So now you have to build an authentication mechanism on top. There's simply no point, when we have better solutions already. And to top it all off, symmetric ciphers aren't threatened by quantum computing in the first place.
- GuB-42 3y agoIn addition to the usual argument about the impracticality of the one time pad. There is also that it is symmetric cryptography (the one time pad is a shared secret). Symmetric algorithms (AES-256 in particular) are generally considered to be quantum resistant. Here is what written about it in the article. > Symmetric cryptography, using a single secret key to encrypt and authenticate data: In our current understanding, symmetric cryptography is not impacted by quantum computers for all practical purposes. Grover's algorithm could be used as an attack here, but is currently considered infeasible for even medium-term quantum computers. (See "Reassessing Grover's Algorithm, 2017") The algorithms most affected by quantum cryptanalysis are public key (asymmetrical) algorithms, because we already have effective quantum algorithms against them (Shor's in particular). We are not even close to having the computer though.
- tapeloop 3y agoexcellent explanation.
- Analemma_ 3y agoOne-time pads just trade an encryption problem for a secure key distribution problem, the latter being much, much harder.
- IncRnd 3y ago
- xyst 3y agoBesides encrypting your user data at rest using these post-quantum cryptography algo. What can be done from a design point of view to make it as hard as possible to deter attackers? Would it make sense to segregate different types of data into other dbs rather than as a separate table? “Name DB” “Account DB” “Address DB” An attacker would need to have advanced knowledge of the app backend to know you have to snag both the account db and address db. Otherwise, the decrypted data is useless with only 1 db. Drawbacks of course include “performance degradation”, “increasingly complex app”. Ideally, if you did not need to store sensitive data or collect other user info such as address or zip code. Then not asking for it at all would be optimal. Maybe regulation is needed here.
- bawolff 3y agoThis doesn't make sense: - i think encryption at rest would probably just use symmeyric encryption which is unaffected by shor - how does the attacker get into your network in this scenario. Stuff encrypted at rest by definition is not flying around the network. - what sort of scenario would be involved where the attacker knows how to get one db but not the others? The hard part is figuring out the first db > Drawbacks of course include “performance degradation”, “increasingly complex app”. On the contrary, sharding is a super common performance technique.
- 4death4 3y agoMinor nit, symmetric encryption is “impacted” by QC, see Grover’s algorithm. The speed up isn’t as fast, though.
- bawolff 3y agoit is also trivial to work around by just doubling the key length. But even without that the speed up is slow enough that we will be well within the quantum age before this matters. The article talks about this a bit.
- arccy 3y agoTypically once you get access you just try to dump everything and figure it out later. Splitting into separate stores is just convoluting your day to day for minimal inconvenience to a possibly non-existent an adversary. The only real protection is encryption.
- JanisErdmanis 3y agoThe threat estimate for a quantum computer that breaks cryptography shall be based on currently available data and the understanding that only the Schor algorithm is known to provide exponential speedup for factorisation. Let’s give IBM credit for attempting to factor in the number 35 in 2022, although they failed there [1]. Before that, the successful factorisation happened for the number 21 in 2012 [2] and the first factorisation of 15 in 2001 [3]. Now we have three points. There is a trend that the factorised number grows by a number of 10 for every ten years. Thus, to get a quantum computer that facilitates RSA-2048, we shall wait for 2^2048 years. [1]: https://arxiv.org/pdf/2103.13855v1.pdf https://arxiv.org/pdf/2103.13855v1.pdf [2]: https://www.nature.com/articles/nphoton.2012.259 https://www.nature.com/articles/nphoton.2012.259 [3]: https://www.nature.com/articles/414883a https://www.nature.com/articles/414883a
- smburdick 3y agoFrom [1]: > We implemented the algorithm on IBM quantum processors using only 5 qubits Last December, a team based out of Harvard demonstrated the ability to scale up to 48 logical qubits: https://arxiv.org/abs/2312.03982 https://arxiv.org/abs/2312.03982 It has been shown that, to factor an integer with n bits, Shor's algorithm requires ~2n logical qubits: https://arxiv.org/pdf/quant-ph/0205095.pdf https://arxiv.org/pdf/quant-ph/0205095.pdf
- JanisErdmanis 3y agoIt is not enough to place qubits on a single chip or on a grid. We already know how to do that. The hard part is keeping them isolated while allowing arbitrary control of their interference. The core issue why Schor algorithm is hard is that it requires exponential supppression of error with number of qubits to produce meaningful results. Therefore we don’t actually see much results here as the error rates have not yet reached thresholds to do it with more qubits. The error correction would not be a panacea either because it would necessitate it’s repeated application to get necessary threshold to run Schor algorithm. This would require unreasonable amount of physical qubits.
- fsh 3y ago
- comex 3y ago> There are several alternatives to simply replacing classical signatures with quantum-safe signatures, which could address the performance issues when it comes to PKI. We are currently looking to experiment in this space to gather data for more solid recommendations, which we will share in a future blog post. Does anyone know what those alternatives might be? Some way to collapse a chain of signatures into one? Long-term symmetric session keys? Neither of those sound like good ideas but I'm grasping at straws.
- agl 3y agohttps://datatracker.ietf.org/doc/draft-davidben-tls-merkle-tree-certs/ https://datatracker.ietf.org/doc/draft-davidben-tls-merkle-t...
- deadbabe 3y agoHow close or far do people speculate we are from Q-Day?
- asystole 3y agoThere's a chart (referenced from [0]) in TFA. [0]: https://globalriskinstitute.org/publication/2023-quantum-threat-timeline-report/ https://globalriskinstitute.org/publication/2023-quantum-thr...
- Retr0id 3y agoJust from reading this it's a bit unclear to me why they recommend only SPHINCS+ for "Firmware Signatures", while for "Software Signatures" they recommend Dilithium3+hybrid or SPHINCS+. Is SPHINCS+ more lightweight?
- eyeofthenico 3y agoSPHINX+ is actually slower (which does not matter much as firmware signatures generation or verification are not time critical) but it is the most conservative choice available (avoids only relying on the security of lattices for signatures), which is very valuable for firmware that cannot be easily updated if a security issue arises with lattice-based signatures. It also offers the smallest public key size, which may help for devices with limited storage.
- thadt 3y agoA counter-point that perhaps everyone is taking PQ a bit too seriously [1]. Personally, it seems reasonable to at least spend some effort preparing for it, given the rather long lead time required to develop, study and stress the constructions needed. It might be a long time (if ever) before cryptographically relevant quantum computers show up, but if they do, we'll be glad we had a decade or two to get ready. The alternative of scrambling at the last minute while everything gets cracked seems unenviable. [1] https://www.cs.auckland.ac.nz/~pgut001/pubs/heffalump_crypto.pdf https://www.cs.auckland.ac.nz/~pgut001/pubs/heffalump_crypto...
- asah 3y agoThe risk is non-linear advances That's what everybody said about AI, then sudden advances ~2013 led to the situation today.
- upofadown 3y agoA non-linear advance probably wouldn't involve Shor's algorithm. As what happened with AI algorithms. What we call post quantum cryptography is really post Shor's cryptography.
- n4r9 3y agoThe difference is that we know Shor's algorithm will work once you solve certain engineering problems. As I understand it even the theoretical side of AI was always shooting in the dark.
- tsimionescu 3y agoI don't think it's really fair to call these engineering problems. Creating a working quantum computer is at the bleeding edge of experimental physics. Sure, the theoretical physics behind a working QC is somewhat understood, but there are no successful experiments in the area. Even the theory is somewhat debatable, as creating a working QC pushes close to the boundaries of the measurement problem.
- Alquds2024 3y agoYes, there is some truth to that
- deleted 3y ago[deleted]
- shireboy 3y agoI’ve wondered if the institutional buy up of BTC via ETFs and corporate and governmental balance sheets has adequately considered this risk. Could a bad actor steal BTC by cracking sha256 keys on a quantum computer? There could be a catch-22 - doing so would zero the value of btc, so if they didn’t immediately transfer to a quantum resistant asset, their heist would be worthless. Still, they could profit by shorting or it could be on agenda of other assets to just zero btc.