In contrast to the threat quantum computing poses to current public-key algorithms, most current symmetric cryptographic algorithms and hash functions are considered to be relatively secure against attacks by quantum computers.[2][11] While the quantum Grover’s algorithm does speed up attacks against symmetric ciphers, doubling the key size can effectively block these attacks.[12] Thus post-quantum symmetric cryptography does not need to differ significantly from current symmetric cryptography.
The citation there is from a 2010 paper, which is old and is just saying that this is believed to be the case.
This page, a year old, says that it is believed that the weakening from use of Grover’s algorithm is not sufficient to make AES-128 practically breakable, and that at some point in recent years it was determined that the doubling was not necessary.
Keeping in mind that I am about twenty years behind the current situation and am just skimming this, it sounds like the situation is that one cannot use an attack that previously had been believed to be a route to break some shorter key length AES using quantum computing, so as things stand today, we don’t know of a practical route to defeat current-keylength AES using any known quantum computing algorithm, even as quantum computers grow in capability.
Oh so both hashes and synmetric cryptography are secure entirely by doubling up the key size.
That’s not my understanding, which is that it’s more-secure than that and doesn’t require the doubling. Assuming the pages I linked are correct and that the understanding of them from my skim is correct, both of which may not be true:
About a decade-and-a-half ago, it was believed that AES of existing key lengths could be attacked via a known quantum algorithm – Grover’s algorithm – using future quantum computers. However, the weakness induced was not sufficient to render AES of all key lengths practically vulnerable. it would be viable to simply increase key lengths, not redesign AES, sufficient to make it not attackable via any kind of near-future quantum computers.
At some point subsequent to that, it was determined that this attack would not be practical, even with the advance of quantum computers. So as things stand, we should be able to continue using AES with current keylengths without any kind of near-future quantum computer posing a practical risk.
Take all that with a huge grain of salt, as I’m certainly not well-versed in the state of quantum cryptography, and I’m just summarizing a few webpages which themselves may be wrong. But if it’s correct, you were right originally that there aren’t going to be near-term practical attacks on AES from the advance of quantum computing, not from any presently-known algorithm, at least.
So, I haven’t read up on this quantum attack stuff, and I don’t know what Kairos is referring to, but setting aside quantum computing for the moment, breaking a cryptographic hash would simply require being able to find a hash collision, finding another input to a hash function that generates the same hash. It wouldn’t require being able to reconstitute the original input that produced the hash. That collision-finding can be done – given infinite conventional computational capacity, at any rate – simply from the hash; you don’t need additional information.
Nobody is wanting to make a magical algorithm that gets the input to the hash.
I mean, there’s provably at least one person who does, but there are infinite inputs that lead to the same hash.
Breaking a hash is being able to easily create new input data that leads to the same hash (with or without the constraint of needing the original input data)
Because hashes are deterministic one way functions - they’re generally one way only
Let’s say I hash a picture. It could go from 14MB to 128 digits of base 64 - there’s orders of magnitude less information in the hash than in the source data
Now - with that hash can you rebuild the picture? You’ve lost a great deal of information, you don’t necessarily even know the size or the format of the input.
Let’s set up an equation - x is the input (the photo), so hash_func(x) = hashx
There are multiple, maybe infinite (depending on the hashing function) values of x that will solve our equation. In the case of the photo, most of it will be random combinations of pixels that mean nothing to a human. There could also randomly be things that appear meaningful, but without knowing more about the original you could never be sure if you have the correct answer
Now, passwords might actually be shorter than the resulting hash, but we salt them so each password hash function works differently, and can still destroy information from the original password. Part of the password and the salt are then used as basically the seed for a deterministic random function to generate this extra information
Again, you have the dual problem of a huge problem space as well as an inability to be sure you have the original input or just another solution
Ultimately, everything is defeatable, and if you can narrow down the problem space (say, by knowing the length of a password, having enough known before and after data, or finding a bias in the algorithm), you can reduce the needed computations by orders of magnitude and make it feasible. Quantum computers also grow exponentially with chained qbits, so I expect someone clever will figure it out sooner or later
Then why are hashes secure?
I’m not sure I follow. Could you expand on that?
EDIT: Wikipedia says this:
https://en.wikipedia.org/wiki/Post-quantum_cryptography
The citation there is from a 2010 paper, which is old and is just saying that this is believed to be the case.
This page, a year old, says that it is believed that the weakening from use of Grover’s algorithm is not sufficient to make AES-128 practically breakable, and that at some point in recent years it was determined that the doubling was not necessary.
https://crypto.stackexchange.com/questions/102671/is-aes-128-quantum-safe
Keeping in mind that I am about twenty years behind the current situation and am just skimming this, it sounds like the situation is that one cannot use an attack that previously had been believed to be a route to break some shorter key length AES using quantum computing, so as things stand today, we don’t know of a practical route to defeat current-keylength AES using any known quantum computing algorithm, even as quantum computers grow in capability.
Oh so both hashes and synmetric cryptography are secure entirely by doubling up the key size. Interesting.
You know way more than I do.
That’s not my understanding, which is that it’s more-secure than that and doesn’t require the doubling. Assuming the pages I linked are correct and that the understanding of them from my skim is correct, both of which may not be true:
About a decade-and-a-half ago, it was believed that AES of existing key lengths could be attacked via a known quantum algorithm – Grover’s algorithm – using future quantum computers. However, the weakness induced was not sufficient to render AES of all key lengths practically vulnerable. it would be viable to simply increase key lengths, not redesign AES, sufficient to make it not attackable via any kind of near-future quantum computers.
At some point subsequent to that, it was determined that this attack would not be practical, even with the advance of quantum computers. So as things stand, we should be able to continue using AES with current keylengths without any kind of near-future quantum computer posing a practical risk.
Take all that with a huge grain of salt, as I’m certainly not well-versed in the state of quantum cryptography, and I’m just summarizing a few webpages which themselves may be wrong. But if it’s correct, you were right originally that there aren’t going to be near-term practical attacks on AES from the advance of quantum computing, not from any presently-known algorithm, at least.
Hahses don’t use encryption
Because you cannot reverse a hash. Information is lost from the result.
So, I haven’t read up on this quantum attack stuff, and I don’t know what Kairos is referring to, but setting aside quantum computing for the moment, breaking a cryptographic hash would simply require being able to find a hash collision, finding another input to a hash function that generates the same hash. It wouldn’t require being able to reconstitute the original input that produced the hash. That collision-finding can be done – given infinite conventional computational capacity, at any rate – simply from the hash; you don’t need additional information.
Nobody is wanting to make a magical algorithm that gets the input to the hash.
I mean, there’s provably at least one person who does, but there are infinite inputs that lead to the same hash.
Breaking a hash is being able to easily create new input data that leads to the same hash (with or without the constraint of needing the original input data)
Because hashes are deterministic one way functions - they’re generally one way only
Let’s say I hash a picture. It could go from 14MB to 128 digits of base 64 - there’s orders of magnitude less information in the hash than in the source data
Now - with that hash can you rebuild the picture? You’ve lost a great deal of information, you don’t necessarily even know the size or the format of the input.
Let’s set up an equation - x is the input (the photo), so hash_func(x) = hashx
There are multiple, maybe infinite (depending on the hashing function) values of x that will solve our equation. In the case of the photo, most of it will be random combinations of pixels that mean nothing to a human. There could also randomly be things that appear meaningful, but without knowing more about the original you could never be sure if you have the correct answer
Now, passwords might actually be shorter than the resulting hash, but we salt them so each password hash function works differently, and can still destroy information from the original password. Part of the password and the salt are then used as basically the seed for a deterministic random function to generate this extra information
Again, you have the dual problem of a huge problem space as well as an inability to be sure you have the original input or just another solution
Ultimately, everything is defeatable, and if you can narrow down the problem space (say, by knowing the length of a password, having enough known before and after data, or finding a bias in the algorithm), you can reduce the needed computations by orders of magnitude and make it feasible. Quantum computers also grow exponentially with chained qbits, so I expect someone clever will figure it out sooner or later