Post-quantum cryptography is too damn big
dadrian.io
dadrian.io
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.
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.
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.
E.g. if you are connecting to a cloudflare domain an attacker can not tell which one.
It never ceases to amaze me how complicated privacy is.
From cloudflares blog [1]
“ What about the IP address?
While both DNS queries and the TLS SNI extensions can now be protected by on-path attackers, it might still be possible to determine which websites users are visiting by simply looking at the destination IP addresses on the traffic originating from users’ devices. Some of our customers are protected by this to a certain degree thanks to the fact that many Cloudflare domains share the same sets of addresses, but this is not enough and more work is required to protect end users to a larger degree. Stay tuned for more updates from Cloudflare on the subject in the future”
Using unencrypted communication you can't put the cat back in the bag if circumstances change.
Once you have already opened a TLS connection for the parent page, you might as well keep using it. You've already paid for it, and that way you get confidentiality in addition to integrity.
P.S. because nobody actually answered. Hashes like what SRI uses are quantum safe.
Historically there is some performance benefit of using a separate CDN, as browsers would share the cache. However modern browsers do not do that. I suppose in theory the CDN might be geo-distributed to be very close to your user, however it seems like the latency of opening a second connection (esp. In http/2 world) would likely outweigh that unless your web server is really bad.
And if you use SRI you end up with a broken website every once in a while and you need to monitor it and ship a fix ASAP (but there's always downtime if you want to make sure the change wasn't malicious before updating the signatures on your website).
Nobody really cares about security, stakeholders just want a good looking enough security theater.
Using a TLS connection should give you all three. Without the TLS connection on assets, you’re missing the secrecy element. Now sure, the data is public, but an attacker could now be in possession of information about what you’re requesting, which may leak information about which pages you’re visiting etc.
That aside, digital signatures are implemented in terms of asymmetric encryption (with the roles of private and public key reversed), so the quantum safety of asymmetric encryption and of digital signatures, as well as their possible size issues, are really one and the same.
No, you're thinking of textbook RSA, which is a special case. Most signature algorithms don't work like that.
This is obviously not true, what leads you to claim the URI is never sensitive or protected information?
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.
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.
We also need to worry about retrospective decryption.
Not the craziest idea in the world, but you still need a very secure physical key distribution medium, which is hard.
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.
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.
Even this page (when I'm writing this) is 170k+ in a site that doesn't include images, bells and whistles.
> 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
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.
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.
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.
If it doesn't it means our physics theories are fundamentally wrong.
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.
I personally like Penrose Objective Collapse theory, because it also connects gravity and QM in an unusual way.
Wave collapse interpretation is an orthogonal topic.
It might as well require some unknown tech, or material or rather a real understanding of the domain.
QM says a quantum entangled state will remain like that until disturbed/measured. If there is some limit as you suggest, that means QM is at least partially broken.
Although that is true, QC isn't ruled in or out by other current observations, despite the extreme accuracy with which quantum physics theories match a very wide range of observations. If QCs can't work, QM will need to be amended but very subtly.
It's even possible that useful QC can't work for such a subtle reason that there's no way to be sure.
According to current physics and computability theories, it is thought you need a useful QC to calculate the behaviour of any physical system that has the properties required by a useful QC. Where "useful" means large enough to be out of reach of classical computers, and "calculate" means to sufficient accuracy to test if calculated behaviours match observation.
This means, the universe might deviate from the appealing math of quantum physics just enough to prevent a highly-entangled QC from ever working, at the same time as agreeing with everything we can calculate from what we have observed so far.
Examples of things we can measure but not calculate accurately: Chemical behaviours, material properties and phase transitions (at least some of them) depend on highly-entangled quantum effects, even higher than any QC is aiming for.
You might think, if we know the basic physics, and we can accurately measure temperature, energy, reaction rates and other properties, those measurements surely gives us a good idea if quantum physics theory matches the universe.
But where there is high entanglement, we can't do the calculations accurately enough to say for sure. They are limited by computational complexity on conventional computers. We have good approximations that are very useful, but they aren't precise enough to rule QC feasibility one way or the other.
But then we also have QFT. The difficult things you were talking about fall more on the QFT side of things.
In my view QM predicts QC will work just like math predicts Turing machines will work.
But the practical realization of an advanced Turing machine can indeed be a very complicated thing - in fact we need quantum physics to understand how modern transistors work.
So if practical useful QC don't work, wouldn't that be more of a QFT engineering problem?
I fully agree that we might not be able to build a working QC, just like we are struggling with fusion power for over 50 years now despite theory predicting it should work, and in theory it being a simpler problem than QCs.
Maybe I'm being pedantic with the distinction between QM/QFT...
Yes?
I mean nothing is certain, but it is the most viable known threat by a wide margin.
> 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?
Nobody knows, but its difficult to coordinate changes, and it is difficult to know which quantum algs actually work. It can take decades to have confidence a new crypto promitive actually works.
As far as actually changing things, look how long it took to change out md5. People started warning it was insecure in 1996, it was totally broken in 2005, and in 2012 the flame malware used it to hack computers.
2002: factorisation of 15 [1]
2012: factorisation of 21 [2]
2022: factorisation of 35 by IBM (although the article is about number 21, but let’s give them credit) [3]
In a plot, the tendency is somewhat linear, with the factorised number increasing by one every year.
A sceptic immediately replies to this thread, saying we already have 100-1000 qubit quantum computers and are on the path to getting a million qubits in the foreseeable future. That may as well be true. The issue is that the Schoor algorithm requires that the error rate of the qubit operations scale exponentially with the number of qubits. This is why IBM only uses five qubits in [3], although they already had a hundred qubit QCs at that time. It just produces meaningless results when used with more qubits.
This is also why the line for factorisation is about to be linear. If the error rate of the qubit operations decreases by 20% every year and we have exponential progress, the usefulness of the Schor algorithm taken on a log scale would be linear.
The error correction is not a panacea either. It does not reduce errors to zero for logical qubits but rather reduces them after the error threshold is reached. It would require repeated application to get the necessary error threshold to run the Schor algorithm for a desired number, which would require an unreasonable number of qubits.
[1]: https://www.nature.com/articles/414883a
So… traditional silicon computing scales exponentially in time, but QC computes in constant time(!) with the minor detail that it scales exponentially in error.
> If the error rate of the qubit operations decreases by 20% every year and we have exponential progress, the usefulness of the Schor algorithm taken on a log scale would be linear.
Right, which is exactly the type of leeway you need, no? 1-2 qubits per year will take many decades to break ECC or RSA. It’s the same Moores law-style assumptions baked into traditional computing getting faster.
> This is why IBM only uses five qubits in [3], although they already had a hundred qubit QCs at that time. It just produces meaningless results when used with more qubits.
So IBM has this really cool gf, but she’s at a different school so you won’t know her. Half joking, but putting error propagation in the footnotes seems very off to me as a complete layman. Like thinking we can accurately predict the weather 5 months out with a bit more compute.
The jury is still out on real self driving cars, but I’m less optimistic than I was five years ago.
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.
If server certificates worked more like PGP you could probably avoid that, but that’s not how TLS works.
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?
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.
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.
PS: We'll sure be in relative trouble if we find faster &| cheaper ways to do prime factorization or invert matrixes.
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.
? AES-GCM is a symmetric cipher. The claim was that existing asymmetric crypto is not quantum secure.
It’s not false. The first quote is about asymmetric, and the latter is about symmetric.
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
2. https://en.m.wikipedia.org/wiki/Post-Quantum_Extended_Diffie...
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.
Maybe they were alluding to floppy disk access times. ;)
(All in all, QKD does not have a singular use case)
See https://cyber.gouv.fr/en/publications/should-quantum-key-dis...
Plus, you often have got length (hundreds of km) and connection constraints (e.g., only over fibre optic).
Larger signatures, ES384 instead of ES256, are significantly harder to break.
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.
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.
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?
Most cryptocurrencies value compact signatures, and so run into many of the same issues facing PKI.
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.
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.
> 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.
Every new technological threat is a opportunity for scams.
Twin-field quantum key distribution over 830-km fibre https://www.nature.com/articles/s41566-021-00928-2
- 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).
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..
The whole point of having repeaters is that it's impossible for them to listen in. For the same reason why it's impossible to just "listen in" on a fiber transmitting the QKD quantum signals. Repeaters don't contradict non-cloning.
If quantum cryptography is the solution, it won't arrive immediately, or for free.