7 ms·
Post-quantum cryptography is too damn big
- asynchronous 3y agoThere’s quite a bit of research currently ongoing for this exact topic, especially in the domain of embedded devices and smaller compute forms. Valid concerns are being raised about performance degradation with some of these larger post-quantum models like Dilithium.
- Willingham 3y agoQuantum resistant cryptography seems like the ideal choice for cryptocurrencies, interesting that only a handful have implemented this.
- Retr0id 3y agoWhy cryptocurrencies specifically? Most cryptocurrencies value compact signatures, and so run into many of the same issues facing PKI.
- Thorrez 3y agoWithout it the accounts are sitting ducks. Big fat juicy ducks just waiting to be poached.
- Underpass9041 3y agoIn Bitcoin public keys are hashed when publicly exposed, in the optimal case the ECDSA public keys are visible for only a period of a few minutes between broadcast of a transaction, and it being confirmed. It is not an incompatible change to add new signature methods, a conservative implementation would have the public key commit to both an ecdsa key, and a quantum safe signature type, and use the committed ECDSA signature until such a time as it is no longer safe. This would result in no gain in signature size today, but allows for instant upgrades in place in the future with no additional transactions required.
- idontwantthis 3y agoBut couldn’t it be stolen just as easily from the thief?
- px43 3y agoI actually talked about this with Gavin (who was running the project back then) in 2013. It wasn't a priority, and it almost certainly never will be. Vitalik, on the other hand, has always made quantum resistance a priority, and the account abstraction model and pluggable signature schemes are just now starting to take off. Basically, you can deploy a smart contract to hold your assets, and part of the smart contract is that to move assets from the contract, you need to sign a message with something other than the typical ecdsa signatures. There are some wallets today that you can even send funds with passkey signatures, which will use the keys sitting in hardware on modern phones.
- jmprspret 3y agoAm I just supposed to know who fucking "Gavin" and "Vitalik" are?
- grayhatter 3y agoyou? probably no. I'm pretty confident that comment was only for the other crypto bros.
- Vecr 3y agoI can't remember Gavin's name, but Vitalik is Vitalik Buterin.
- ramchip 3y agoFor others like me wondering what "the project" is, I think it's Ethereum. > Vitaly Dmitrievich Buterin, better known as Vitalik Buterin is a Canadian computer programmer and co-founder of Ethereum. > Gavin James Wood is an English computer scientist, a co-founder of Ethereum and creator of Polkadot and Kusama.
- j16sdiz 3y agoIndeed. Every new technological threat is a opportunity for scams.
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- hughesjj 3y agoedit big dumb dumb here misread asymmetric as symmetric
- cedws 3y ago>This is false, and they even claim so just a few paragraphs down ? AES-GCM is a symmetric cipher. The claim was that existing asymmetric crypto is not quantum secure.
- hughesjj 3y agoI'm an idiot and was dyslexic
- palmfacehn 3y agoWe're all idiots and the mistake is relatable.
- hughesjj 3y agoThank you. I'm so ready for the weekend
- dsp 3y ago> This is false, and they even claim so just a few paragraphs down It’s not false. The first quote is about asymmetric, and the latter is about symmetric.
- adastra22 3y ago[flagged]
- tredre3 3y agoThere is no reason to believe one way or the other. Are there reasons to believe that the current post-quantum algorithms will actually be quantum resistant?
- adastra22 3y agoSome, yes. Lamport signatures are almost certainly quantum resistant. But the small, compact schemes that are getting attention and competing in the NIST selection? Probably not.
- defrost 3y agoThere are reasons to believe that some candidates aren't even non quantum desktop computer resistant: https://mathematical-research-institute.sydney.edu.au/news/quantum-encryption-algorithm-cracked-by-computer-running-magma/ https://mathematical-research-institute.sydney.edu.au/news/q... https://www.securityweek.com/nist-post-quantum-algorithm-finalist-cracked-using-classical-pc/ https://www.securityweek.com/nist-post-quantum-algorithm-fin... ( Disclaimer: I worked on pre 1991 Cayley, born again post 1991 as Magma )
- adastra22 3y agoThis is the reason for my sarcastic response above. Attempts at making compact PQC are being broken left and right. If anything the line of battle is moving towards larger, more costly schemes at the moment. Complaining about proof size or validation speed right now is like pissing into the wind. You’re lucky if your PQC finalist scheme is even secure against a 2010 Mac mini in a year or two. Complaining that its proofs don’t fit into a MTU packet? That’s rich.
- deleted 3y ago[deleted]
- thayne 3y agoOne possible tls change that isn't mentioned here: Initially just send a hash of the intermediate signature. The client would keep a cache of intermediate certificates, and if it didn't already have the cert in its cache, then request the full signed intermediate cert. The downside for that is that you have to maintain a cache, which would be difficult for some non-browser applications.
- FiloSottile 3y agoThat’s the first TLS change suggestion, under the “Intermediate elision” heading.
- 1letterunixname 3y agoI favor betting on proper orders of magnitude more rounds of reliable and proven constructions optimizing for a minimum mem/cpu/gpu/fpga- & asic-hard cost factors for a particular use-case than entirely new and unproven constructions (recall SIDH) and from untrustworthy intermediaries like NIST (recall P curves, Dual_EC_DRBG). PS: We'll sure be in relative trouble if we find faster &| cheaper ways to do prime factorization or invert matrixes.
- FiloSottile 3y agoWhat’s wrong with P curves?
- klabb3 3y agoHasn’t the path to quantum computing with that many qubits always been full of unknown unknowns? I’m happy that researchers are preparing but it seems like defending against a threat of unknown shape that doesn’t exist is kind of futile. First, do we even have high confidence that QC is the thing that will break current algorithms? Secondly, how much time from “the writing is on the wall” until bad actors can deploy them for financial gain? Unless it’s short, why not wait and migrate later? Because like the xkcd with the $5 hammer, crypto primitives has to be the weakest link in the chain to really be a threat so big it warrants throwing it on top of everything just in case. I mean our security for even critical infrastructure is so bad that ransomware groups are rampant without any need to ever care about primitives. Also assuming that if you’re high value target for state actors, you’re not gonna use default TLS anyway. Extra assumption: most harvest-now-decrypt-later seem completely worthless? Anyway, rambling aside: is this just naive skepticism from a mortal non-enlightened engineer with a short sighted YAGNI mindset? Or have the purist academics been selling parachutes to workers in skyscrapers - ie a solution to a problem that wont materialize anytime soon? Please, forgive my ignorance.
- juitpykyk 3y ago> First, do we even have high confidence that QC is the thing that will break current algorithms? If it doesn't it means our physics theories are fundamentally wrong.
- tromp 3y agoNot necessarily. It could be that ECDLP (Elliptic Curve Discrete Log Problem) is not as hard as we thought. It's not inconceivable that it's in P (Polynomial time). In fact, if we were to see current algorithms being broken right now, I think it's more likely to be due to a classical algorithm breakthrough than by quantum algorithms running on an actual large scale quantum computer with hundreds or thousands of logical (i.e. practically error-free) qubits.
- sesm 3y agoWe don’t have any mainstream physical theory that describes the process of quantum decoherence aka wave function collapse. We know it happens, but don’t know when exactly or how quickly. So if QCs fail, Quantum Mechanics won’t be proven wrong, but rather we’ll have more data on wave function collapse which has been an open question for more than a century. I personally like Penrose Objective Collapse theory, because it also connects gravity and QM in an unusual way.
- feverzsj 3y agoBut isn't quantum communication unbreakable? And it should be easier than building a quantum computer.
- etna_ramequin 3y agoQuantum Key Distribution (QKD) requires special (expensive) hardware, so it really doesn’t solve the problem of key size. Moreover, QKD still requires an authenticated channel, so we’ll still need a quantum-resistant authentication scheme. (All in all, QKD does not have a singular use case) See https://cyber.gouv.fr/en/publications/should-quantum-key-distribution-be-used-secure-communications https://cyber.gouv.fr/en/publications/should-quantum-key-dis...
- feverzsj 3y agoWhat about a highspeed quantum channel to transfer all the data?
- etna_ramequin 3y agoStill requires special hardware and authentication, AFAICT. Plus, you often have got length (hundreds of km) and connection constraints (e.g., only over fibre optic).
- deleted 3y ago[deleted]
- xgstation 3y agoWe will just need to use quantum to beat the quantum. QKD (quantum key distribution) is much more mature comparing with quantum computer which is still far away for cracking crypto algorithms from real practical application standpoint. Twin-field quantum key distribution over 830-km fibre https://www.nature.com/articles/s41566-021-00928-2 https://www.nature.com/articles/s41566-021-00928-2
- hnaccount_rng 3y agoWhat is the problem that QKD is solving? On the one hand you need a totally separate point-to-point network for the quantum connection. On the other hand you get relatively short symmetric keys on both ends. I’ve yet to see a proposal that wouldn’t be better served by transferring the key material via DVD/USB-stick/whatever and an armed guard. I’m certain I’m missing something rather obvious.. but I don’t see what
- krastanov 3y agoI do not think you are missing anything that would change your cost-benefit analysis, but here are two things that might be of interest: - A QKD link would be much lower latency than transmitting a physical token over an authenticated channel (same type of advantage as with asymmetric key encryption, but without the drawback of relying on assumptions about computational complexity) - It does not need to be point-to-point if you have a network of quantum memories/repeaters (which are probably much easier to build than quantum computers).
- hnaccount_rng 3y agoThanks for the reply. I’ll give you latency, but that’s almost never a problem in the first place. You need to (re)authenticate anyhow. I don’t think your second point holds though. Even if we assume memories/repeaters to exist (iiuc this should contradict the no-cloning-theorem) you’d need to trust them not to listen in so you’d be back to square one with electronic key distribution schemes? There might be an argument that one is unable to secure the two sets of key material (at least on one end and at least long term) and the destination is hard to reach (e.g. James Web or so). But at that point I’d also not trust that organization to implement their end of QKD correctly..
- Animats 3y agoWhat's the status of digital signature algorithms? There's much stuff that doesn't need to be encrypted because it's not secret - anybody can read the URL. It just needs to be protected against forgery. That's what subresource integrity is for. Only the parent page needs HTTPS. Most of the assets can use HTTP, locked to specific content by subresource integrity. That's more useful for security than encryption. If someone changes a third party Javascript file, it won't load. This would promote a more stable web.
- magicalhippo 3y ago> Most of the assets can use HTTP, locked to specific content by subresource integrity. That's more useful for security than encryption. This is OK if you're only concerned about getting scammed. It won't work if you're concerned about your privacy. And the problem is you can't change your mind on that after the fact.
- brabel 3y agoThe point OP is making is not everything requires privacy. We shouldn't pay the (higher and higher) price of keeping privacy for cases where it's just not needed.
- lukan 3y agoBut what URLs people visit are very much private information for example. Also one of the ideas in general is, to obfuscate the really private communication by burying them in a sea of also encrypted, but trivial data. If only the very sensitive informations get encrypted, then this is also a very good filter for an attacker to ignore everything else and just go for the high protected ones.
- wh0knows 3y agoGiven domains are not encrypted I’m not sure this holds true. Attackers can already target financial websites, messaging websites, etc…
- immibis 3y ago12 kilobytes is nothing when accessing a web page that's 2MB. One possible improvement: only negotiate one key per server. When opening a new connection to a server that was very recently accessed, just keep using the existing security channel. In other words, mandate HTTP 2.
- _trampeltier 3y agoYeah, with todays bloated websites, this few KBs don't really matter at all. Where do you even find a webpage today who is "just" 2MB.
- hinkley 3y agoNo it’s still a lot. The 2 MB can be streamed. In HTTP 3 it can be streamed in parallel. But none of those requests can start before the connection integrity is verified, otherwise you leak the intent of the request to a MITM agent. So you have head of line blocking on that 12k. And on mobile networking that comes with a lot of packet loss. If server certificates worked more like PGP you could probably avoid that, but that’s not how TLS works.
- remram 3y agoIf the web page is 2MB because it's loading ads, fonts, JavaScript libraries, images, cookie banners, trackers, etc each from a different domain or CDN... the problem is much bigger. This is 14k per connection...
- enva2712 3y agoThoughts on lattice-based crypto?
- jlokier 3y agoThe cryptosystems the article says are too big to use, Kyber and Dilithium, are both lattice-based. A solution to this problem may also be lattice-based: SQISign is mentioned, though that is too slow. Or it may be something else: Unbalanced Oil and Vineger, and Mayo, are not lattice-based.
- lphillips0825 3y ago“As a baseline reality check, we should not be sending over 1% of a 3.5" floppy disk purely in signatures and public keys.” Really? This is a ridiculous statement and sounds like we're worried about bandwidth consumption from the time when a US Robotics modem was a luxury.
- layer8 3y agoAs the article explains, it’s about latency, not bandwidth. Maybe they were alluding to floppy disk access times. ;)
- deleted 3y ago[deleted]
- vladak 3y agoIt is a strange comparison indeed, esp. with some generations of engineers might not even know what a floppy disk was, let alone imagine how the 1% of the capacity translates to network protocols.
- bjornsing 3y agoI expected this to include a discussion on forward secrecy [1], but it doesn’t seem to. (I searched the page for “forward” but got no hit.) A reasonable tradeoff at the current time may be to keep primary keys / certificates classical, and make session key exchange quantum resistant [2]. That would thwart any “harvest now, decrypt later” adversary. It wouldn’t protect against a man in the middle with a big quantum computer, but that’s not a very realistic threat for the foreseeable future. Don’t know how much it will bring down the handshake size though. 1. https://en.m.wikipedia.org/wiki/Forward_secrecy https://en.m.wikipedia.org/wiki/Forward_secrecy 2. https://en.m.wikipedia.org/wiki/Post-Quantum_Extended_Diffie-Hellman https://en.m.wikipedia.org/wiki/Post-Quantum_Extended_Diffie...
- deleted 3y ago[deleted]
- layer8 3y agoThe article explains what you are explaining. Search for “harvest now, decrypt later” on the page.
- twwwt 3y agoI'm no expert but somehow I think post-quantum cryptography will become what IP6 is to IP addressing: we all know very well what problem it solves but the problem doesn't hit us that hard in practice that we are actually forced to make the switch.
- layer8 3y agoIt’s not quite the same, because the problems solved by PQC depend on technological developments (practical quantum computers) that may or may not materialize, whereas the problems solved by IPv6 are independent from such developments. And we already are at the point were IPv6 is necessary, due to having run out of IPv4 addresses.
- Zamicol 3y agoHear, hear! Larger signatures, ES384 instead of ES256, are significantly harder to break.
- vitus 3y agoNot with quantum computers, which is the entire argument for moving to post-quantum crypto. If we can manage to solve the scaling problem and can have, say, 2000 qubits of useful computation to break ES256, then we "only" need to scale to 3000 qubits to break ES384. Which is a lot less daunting than it seems, since we'll all but certainly need breakthroughs in error correction or coherence times to reach that threshold of useful applications of Shor's algorithm.
- Zamicol 3y agoKlebb3: https://news.ycombinator.com/user?id=klabb3 https://news.ycombinator.com/user?id=klabb3 Quantum computers are like fusion in the 1940's, "it's only going to take 20 more years". Using arguments in line with klebb, if quantum is linearly difficult, and each qubit takes 1 year, with your thought experiment's numbers that's 1000 years between breaking 256 and 384, let alone 512. Early on, a decade ago, I was much more accepting of the quantum camp's arguments. But now in retrospect they've oversold, overpromised, and under delivered. These hypothetical breakthroughs may not come to fruition.
- vitus 3y agoI don't necessarily think that this is coming any time soon, but factoring a 5-bit integer is fundamentally different from factoring a 200-bit integer, which is why I said we probably need a breakthrough in quantum error correction or other methods such that we can actually entangle hundreds of qubits for long enough to perform meaningful computation. I'm not convinced that we've made meaningful progress on this front in the past 20+ years since IBM first used Shor's algorithm to factor 15 back in 2001. (In 2012, they factored 21. In 2019, they failed to factor 35 due to accumulation of errors.) If you're willing to accept the premise that quantum computers will exist that can break RSA-4096, then those same quantum computers can break elliptic curve crypto based on P256 or P384 or P521. If you're not willing to accept that premise, then what's the point of doubling your key length? Wasting CPU cycles?
- tiborsaas 3y agoMaybe it's worth start trading one time pads before quantum computers can break RSA. We also need to worry about retrospective decryption. https://en.wikipedia.org/wiki/Harvest_now,_decrypt_later https://en.wikipedia.org/wiki/Harvest_now,_decrypt_later
- ramchip 3y agoThis is covered in the article. It even links to the exact same page.
- pclmulqdq 3y agoOne-time pads need you to have a limited amount of data to encode and a good channel through which to send your one-time pad. However, assuming AES isn't broken by quantum computers (there is no evidence that it is), you could use a relatively small one-time pad to generate keys to encrypt a much bigger bulk of data. Not the craziest idea in the world, but you still need a very secure physical key distribution medium, which is hard.
- isotropy 3y agoQuantum key distribution solves the sharing problem and will arrive sooner, for a certain budget.
- pclmulqdq 3y agoI'm not so sure - QKD needs good SNR optical paths from source to destination, so over any real distance it's pretty hard. Physical medium security is just a matter of money today. There are ideas of satellites doing QKD, but that will fall firmly into the realm of nation-states, which already spend a shit load on physical security.
- narag 3y ago14k is too damn big? O_o Even this page (when I'm writing this) is 170k+ in a site that doesn't include images, bells and whistles.
- fireflash38 3y ago14k on every single connection is pretty huge. How many TLS connections for just this site? What about a site that uses 10+ cdns?
- grayhatter 3y agomaybe that site deserves to be slow and.... well I was gonna say unusable, but a site with over 10 different CDNs is probably already nearly unusable.
- narag 3y agoCorrect me if I'm wrong, but I believe that there's one TLS connection per site. Ten CDNs are still 140k, pretty tame by today's standards.
- blablabla123 3y agoIt's probably the stone-age of PQC right now. Apart from the humongous sizes the amount of scrutiny and standardization is low compared to RSA or even elliptic curve cryptography. So chances are that at least one popular algorithm needs to be swapped out in foreseeable time. On the other hand speaking about HTTP newer versions allow for more efficient connection reuse and multiplexing so the bulky handshakes aren't needed as often.
- the_panopticon 3y agoit has definitely been interesting trying to figure out how to accrete post quantum crypto into existing domains like firmware, too https://uefi.org/sites/default/files/resources/Post%20Quantum%20Webinar.pdf https://uefi.org/sites/default/files/resources/Post%20Quantu...
- ur-whale 3y ago> Large-scale quantum computers are capable of breaking all of the common forms of asymmetric cryptography used on the Internet today. Is that actually true? I was under the impression that there exists quite a large class of trapdoor functions (functions that are one-to-one maps, cheap to compute but whose reciprocal is crazy expensive to compute without some sort of oracle-like information) that could not be attacked by quantum computers? Are there no asymmetric algorithm that are impervious to QC in use today on the internet? Or are they specifically talking about the fact that RSA-style algos are vulnerable?
- uv-depression 3y agoSymmetric algorithms are largely safe-ish; the best known attack is Grover's algorithm, which reduces the effective bits by half (runs in O(sqrt(N)) evaluations). Shor's algorithm is a polynomial-time solution to the discrete logarithm problem, which has traditionally been the basis for asymmetric cryptography.
- ur-whale 3y ago> Shor's algorithm is a polynomial-time solution to the discrete logarithm problem Yes, exactly, and the discrete logarithm problem is but a narrow sliver of a much larger class of trapdoor functions, most of which don't have the equivalent of Shor's algorithm to be attacked with. That's precisely the point I was trying to make.
- jlokier 3y agoA trapdoor function isn't the same as asymmetric cryptography. Trapdoor functions can be used to build asymmetric cryptography, i.e. public-key encryption and signing. In general, hash-based asymmetric cryptography can do it with any hash you consider strong enough, such as SHA-256. Unfortunately the keys and signatures tend to be large, which is the problem the article is talking about. That's why they are not in common use. For example, although SHA-256 is 256 bits, which is considered small, the keys and signatures of asymmetric cryptography built with SHA-256 are very much larger. Making the keys and signatures smaller, yet secure and fast enough, is currently state of the art research.
- DennisP 3y agoSo it's a bit more than a 10X size increase. But 20 years ago we were using cryptography without it being an undue burden on the network. How much more bandwidth do we have now? How much more storage? Even on phones without wifi available, we're in pretty good shape. Measuring cryptographic overhead as a percentage of available bandwidth and storage, it'd be interesting to figure how many years we'd regress if we went post-quantum. I'd bet it wouldn't be dramatic.
- grayhatter 3y agodid you not read, or not agree with the authors comments about what about reasonable or appropriate?
- d-z-m 3y ago> TLS handshake would contain 52420 + 21312 = 14,724 bytes of signatures and public keys, an over 10x increase. > Barring a large-scale quantum computer staring us in the face, this is not a tenable amount of data to send simply to open a connection. Do we not run the risk of it simply being the case that Dilithium is the best TLS compatible algorithm for signatures we're going to get for a while? Then the question becomes: does a rodent of unusual size cough large, fault tolerant quantum computer...actually exist? I think the answer is probably no, but if I understand attacks against the current Web PKI, it's not like an attacker would sit on the wire running Shor's algorithm in real time. The work to make a MITM attack possible would be done ahead of time, (e.g. running Shor's algorithm against a Ed25519 public key to find the private scalar) then the attack proceeds as normal. Which is to say, if they[0] can make it work at all, they can start cracking keys and MITM attacks on connections become a reality. Does that mean that we should implement Dilithium? I don't know, but I also don't know if we should sit on our hands until something better comes along. [0]: whoever ends up building one of these things
- KILUA 3y ago[flagged]
- zachbee 3y agoThere are meaningful size and performance challenges to implementing post quantum crypto, but I don't think "oh no, HTTPS handshakes are 20% slower!" is something we should actually worry about. The real worry is all of the small, secure, embedded devices that literally don't have enough memory or compute to run these algorithms at all. Even the state-of-the-art hardware-accelerated implementations of PQC use a ton of memory and a ton of silicon area, to the point where they're untenable for lower end devices.
- klabb3 3y ago> but I don't think "oh no, HTTPS handshakes are 20% slower!" is something we should actually worry about. Why not? TLS handshakes are real. That said, we have pretty restrictive TCP windows from 20+y ago that might need a bump-up at som point. But importantly, we should not be making too many assumption on use-cases, as if stateful connections like TLS is the holy grail. Small and fast crypto enables new use-cases - engineering standards should always take perf & overhead into account, and not focus only on existing use. > The real worry is all of the small, secure, embedded devices that literally don't have enough memory or compute to run these algorithms at all. Indeed! And more overhead increases surface area for DOS attacks on “high-end devices” as well. So there are already clear examples of how these would break important things. The reason I’m skeptical is precisely that QR today has known, significant setbacks, but unknown benefits.