Sentences only have semantic meaning because you have experiences that they map to. The LLM isn't training on the experiences, just the characters. At least, that seems about right to me.
Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?
Grover's algorithm is provably optimal [0]. No quantum algorithm will ever find an n-bit key by queries to any reasonable sort of oracle faster than Grover's algorithm, and Grover's algorithm is way too slow to be a serious problem.
But symmetric ciphers are not black boxes. They're mostly built on some variant of a Feistel network, which is a very nice construction for turning a messy function into an invertible function that, in a potentially very strong sense, acts like a cryptographically secure permutation.
When I was in grad school, one project I contemplated but never spent any real time on was trying to either generate a real security proof for quantum attacks on Feistel networks or to come up with interesting quantum attacks. And there is indeed an interesting quantum attack against 3-round Feistel networks [1].
This is interesting, because, depending on what sort of security is needed, three or four rounds of Feistel network are sufficient against classical attack [2].
Now ciphers like AES have many more than 3 rounds, so hopefully they're fine. But maybe they're not. My intuition is that there is probably a reasonably small n1 and a reasonably small n2 >= n1 (probably constants, maybe logarithmic in numbers of bits) for which there is no quantum algorithm that can break symmetric crypto given classical query access even to the round functions (n1) or quantum query access to the round functions (n2) [3], but I'm not aware of any proof of anything of the sort. And my intuition definitely should be be trusted fully! (Maybe, even if I'm wrong, there is still a number of rounds that is sufficient for security against query access to the entire cipher.)
[3] It would be extremely cool if someone built quantum computers and networks and storage such that two parties that don't trust each other could actually communicate and exchange (interesting [5]) qubits. I've written some fun papers on the possible implications of this. If we ever get the technology, then it might actually be meaningful to consider things like chosen-quantum-ciphertext attacks against a classical symmetric cipher. But that's many, many years away, and, in any case, an attacker will only ever get to do a quantum query attack against a cryptosystem if a victim lets them. [4] Otherwise all queries will be classical.
[4] Or in very complex settings where there is an obfuscated black box, for example. This may be relevant for zk-snarks or similar constructions.
[5] I don’t consider the optical qubits exchanged in commercial devices that supposedly implement quantum key distribution to be interesting. To the vendors of such devices, sorry.
This is correct, but for substitution-permutation networks there are similar theoretical results about the minimum number of rounds under various assumptions, like for Feistel networks.
The arguments of OP are also applicable to this kind of ciphers.
Besides the fact that there might be some ways in which quantum computers might be able to accelerate attacks against iterated block ciphers with a number of rounds inferior to some thresholds, there exists also a risk that is specific to AES, not to other ciphers.
Recovering the secret key of any cipher when you have a little amount of known plaintext is equivalent with solving a huge system of equations, much too big to be solved by any known methods.
In order to ensure that this system of equations is very big, most ciphers that are built by composing simple operations take care to mix operations from distinct algebraic groups, typically from 3 or more algebraic groups. The reason is that the operations that appear simple in a group appear very complex in other groups. So if you mix simple operations from 3 groups, when you write the corresponding system of equations in any of those groups, the system of equations is very complex. This technique of mixing simple operations from at least 3 algebraic groups has been introduced by the block cipher IDEA, as a more software-friendly alternative to using non-linear functions implemented with look-up tables, like in DES.
An example of such algebraic groups are the 3 algebraic groups used in the so-called ARX ciphers (add-rotate-xor, like ChaCha20), where the 3 groups correspond to the arithmetic operations modulo 2^N, modulo (2^N-1) and modulo 2.
Unlike such ciphers, AES uses algebraic operations in the same finite field, GF(8), but instead of using only simple operations it also uses a rather complex non-linear operation, which is inversion in GF(8), and it relies on it to ensure that the system of equations for key recovery becomes big enough if sufficient rounds are performed.
Because of this rather simple algebraic structure of AES, it has been speculated that perhaps someone might discover a method to solve systems of equations of this kind. For now, it seems very unlikely that someone will succeed to do this.
Even if solving this system of equations seems unfeasible by classical means, perhaps one might discover a quantum algorithm accelerating the solution of this particular kind of systems of equations.
I have mentioned this risk for completeness, but I believe that this risk is negligible.
AES could be modified in a trivial way, which requires no hardware changes in most CPUs, but only software changes, in order to make that system of equations much more complex, so that it would defeat any possible quantum improvement. An example of such a change would be to replace some XOR operations in AES with additions modulo 64 or modulo 32. The only problem would be that there may be devices whose firmware cannot be updated and old encrypted data that has been recorded in the past will not benefit from future upgrades.
However, like I have said, I believe that this risk for AES to be affected by some equation-solving algorithm discovered in the future remains negligible.
The only caveat is that AES is not necessarily a black box. It's possible there may be hidden structure to take advantage of, but if there is there's no reason to suspect it's one that's amenable to a quantum speedup.
As far as the Grover speedup goes, it's already optimal. Requiring O(sqrt(N)) queries is the proven lower bound for unstructured search.
If you like this kind of thing: there's a deterministic algorithm for finding minimum spanning trees in a graph that's proven optimal, but no one knows its exact runtime.
Basically, the best they've proven is something like O(n * inverse_ackermann(n)), but it seems likely the algorithm actually runs in O(n). We also already have a randomised algorithm for this problem that runs in O(n) expected time on worst case input. The expectation is over the random choices.
It's very typical to have a retainer / insurance to bring in "emergency" incident responders beyond your existing team. Not saying that's the case here but it wouldn't be surprising.
> The author of iTerm2 initially didn’t consider it severe enough to warrant an immediate release, but they now seem to have reconsidered.
It's funny that we still have the same conversation about disclosure timelines. 18 days is plenty of time, the commit log is out there, etc.
The whole "responsible disclosure" thing is in response to people just publishing 0days, which itself was a response to vendors threatening researchers when vulns were directly reported.
Would it be possible to do somethign like editions for proc macros, or have crates establish "this is a v2 proc macro" or something? There are a lot of things I'd love to see change in a v2 but it'd all be breaking.
I think that they arguably do when they publish to a registry. I think that crosses a bridge from "I'm just writing software" and "I'm publishing software for consumption". Arguably, to be clear, I don't have very strong feelings, but I think there is a distinction between "I've placed code online" and "I've explicitly published it for use".
Sorry I'm just gonna copy some of this directly from tweets about sandboxing that I'd written.
I think it is a mistake to say "cargo build does not need to be sandboxed because cargo test is not". A very tricky part of sandboxing is sandboxing code you don't own. I own what code runs in tests, I do not own what code runs in cargo/ build scripts.
I can take responsibility for isolation in test/ci/prod. Those are tractable problems because I can design my tests/prod code to be friendly to sandboxing. I can not do that with build scripts or proc macros, I can't actually do much at all.
The solution for "sandbox cargo" ends up being "sandbox the entire dev environment", which is a very difficult problem to solve - you lose tons of performance, UX, and the security is lacking due to how much gets placed into the sandbox.
I strongly feel that cargo is in a much better position to help me out here. I can't even know if an update to a crate happened that suddenly added a build script without additional tooling.
As for typosquatting,
> If you think you can remember the URLs for each package you use, you’re probably wrong.
Most people aren't using urls so I don't get this. The issue is typing `cargo add reqwest`. Typosquatting algorithms solve this.
I did some math.
If crates.io had adopted a policy of "no crates within edit distance of one", 15% of crates would have been blocked across all time.
+Exception for same author: 14%
+Exclude <=4: 9%
+Swap from edit distance to actual typo detection algorithm: 5%
5% of crates would have needed a name change across all time. That number will likely decrease drastically as existing names are taken.
Yes, Rust needs radically more funding in these areas. Companies need to step up. Sandboxing, typo squatting, better auditing tools (ie: I need to know when `cargo udpate` adds a dep with a new build script, etc), TUF, etc, all need to be priorities.
Appreciate it! cloudformation isn't in scope today but the perf approach (tree-sitter + parallel file walk + rule pre-filtering) transfers, so happy to check it out.
reply