81–90 of 116 posts
One wonderful thing about Filippo is that when it is possible for him to give concrete advice, he gives it, and brings receipts.
Thanks Filippo!
On one hand I hear that quantum computers will crack factorisation and discrete logarithms, on the other that the max number factorised is 15 and that 21 might not even be feasible. What is going on?
Earlier quoted context omitted.
I'm not familiar with their stance, but bear in mind the costs of introducing new key type on the ecosystem, and on maintenance of SSH implementations.
Imagine if we would've had the same hesitant cost-first reasoning about Ed25519, and then again about ML-KEM and SNTRUP.
You suppose what happens if the OpenSSH maintainers considered the cost when implementing those algorithms? Perhaps they did, but decided the benefits were worth it.
On one hand I hear that quantum computers will crack factorisation and discrete logarithms, on the other that the max number factorised is 15 and that 21 might not even be feasible. What is going on?
As far as I know, the current state of AES-256 is something like "this attack breaks AES in 2**254 instead of 2**256 if we have something like 2**80 bits of ciphertext to work with in the first place". That's nice for getting papers in crypto conferences but not something to lose sleep over yet, but an AI trained on the entirety of LNCS and ePrint might be a different matter.
That and side-channels, but we've known about those for a while.
Whether AES or ChaCha holds up better in the face of AI is an interesting open question for which I can't offer anything better than a coin flip.
Earlier quoted context omitted.
Coherency To get useful results, a quantum computer needs all of its qbits to stay entangled with each other, until the entire group collapses into the result. With current technology, it is very difficult for a reasonable sized group of qbits to stay coherently entangled, so it can only solve problems that are also relatively easy to solve on classical computers. If someone today were to figure out how to keep large…
> instantly Shor's and Grover's still are algorithm that require a massive amount of steps...
Earlier quoted context omitted.
Fun fact: Grover's algorithm is a rare example of an algorithm that was proven optimal before it was invented.
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 inp…
Earlier quoted context omitted.
Yes and no. 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 in…
Nitpick: AES isn't a Feistel network, it's based on a substitution-permutation network.
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.
I wonder when the OpenSSH developers will change their stance on Ed448.
Earlier quoted context omitted.
I am not an expert, but while you are correct that a fast enough traditional computer (or a parallel enough computer) could brute force a 128 bit key, the amount of improvement required would dwarf what we have already experienced over the last 40 years, and is likely physically impossible without some major fundamental change in how computers work. Compute has seen in the ballpark of a 5-10 orders of magnitude incre…
> That isn’t happening with how we make computers today. Keep here in mind that computers today have features approaching the size of a single atom, switching frequencies where the time to cross a single chip from one end to the other is becoming multiple cycles, and power densities that require us to operate at the physical limits of heat transfer for matter that exists at ambient conditions. We can squeeze it quite…