5 ms·

This is not true. Modern cryptography is not breakable via brute force any more, nor will it ever be. You can prove that the amount of energy required assuming

This is not true. Modern cryptography is not breakable via brute force any more, nor will it ever be. You can prove that the amount of energy required assuming a thermodynamically ideal computer is more than will ever be available in our galaxy, with classical computing. Breaks of symmetric crypto or hashes that are practical require an actual cryptographic weakness, whose existence is not a given. Then there's quantum computing, but that also doesn't break symmetric crypto outright, it just makes it weaker. I'm not sure if anyone has run the math, but we'd probably still be talking galaxy sized quantum computers to get anywhere.

elcomet 5y ago
thanks, that's interesting, I didn't know this !
samstave 5y ago
This is why they create laws to require you unlock your phone when crossing borders. I have been constantly surprised that there isnt a phone/company that specifically markets to "buy this temp phone to cross a border" -- Also, WRT Quantum computing, what are your thoughts on the talk by D-Wave CEO where he said "we can reach into different dimensions" -- and soon after, D-Wave went super silent? What is the state of quantum currently - did they discover something super secret?
- antris 5y ago
  They? Who, where? Which law?
xoa 5y ago
>Modern cryptography is not breakable via brute force any more Specifically, modern symmetric crypto (and hashing which is a related but different thing) is fine. It's public-key crypto that has always been the worry thanks to Shor's Algorithm, and all modern widely used crypto there is indeed vulnerable if an actual scalable general quantum computer could be constructed. There are a variety of post-quantum cryptographic algorithms under development including some ones that would be ugly slow but likely effective bandaids if required, but that's still a not totally unreasonable concern for certain threat profiles. But yes GP was totally wrong about "all methods are broken when compute becomes faster". >I'm not sure if anyone has run the math "The math" here is just Grover's Algorithm, that lowers the cost of generic brute forcing to O(sqrt(n)). So a 128-bit symmetric key could be cracked on average like 2^64 or a 256-bit key like 2^128. Obviously this is utterly trivially countered by doubling the exponent. Even 2^128 is still ridiculous, and going to a 512-bit key brings us right back to 2^256 which is impossible. 128-bit keys should indeed be phased out entirely (and that seems to be well on the way anyway), and perhaps 256-bit too at some point (even if it's only the very paranoid or very long termers, it's also not big stretch on modern hardware at all, so eh), but fundamentally yes symmetric crypto is fine.
- marcan_42 5y ago
  I know about Grover's Algorithm, but the reason I didn't want to make any hard claims is that with hashes you also have to worry about collision attacks. Those give you an O(sqrt(n)) time advantage themselves in classical computing, at the expense of space for storing existing hashes (birthday attack), and you can play with the balance as a space-time tradeoff. I can't claim to have any idea how those interact with quantum crypto, plus once you introduce storage at a large scale I imagine you start running into speed of light and communication energy cost issues.
  - im3w1l 5y ago
    So one thing im thinking could work is to do a sort of probabilistic birhtday attack. Like you could do a binary search, where in every step you narrow down on the bucket with more data. So like lets say a year had 256 days and you want to find colliding birthdays. First you would check how many birthdays in 0-127 vs 128-255. This takes just two counters - very little storage. Then lets say the former has more. You'd try 0-63 vs 64-127. Etc. But yeah this will of course miss collisions. But I think if you have enough children (where enough is still pretty close to sqrt(n)) it should have a good chance of finding a collision. And subdividing into many buckets at a time will miss less collisions, but require more storage - a tradeoff can be used.
dooglius 5y ago
Do you have a cite for this for SHA256? It surprises me a bit as our galaxy is big and we are far from physically ideal computers.
- marcan_42 5y ago
  I did the math myself at one point, but I lost the link. However, here's a reference for the same kind of thing: https://pthree.org/2016/06/19/the-physics-of-brute-force/ https://pthree.org/2016/06/19/the-physics-of-brute-force/ The total energy output of a supernova is enough to count up to 2^220, making a lot of generous (invalid) assumptions. You'd need 2^36 supernovas to just count up to 2^256, never mind actually running SHA256. At minimum. There are circa 2^38 stars in the Milky Way, and they're not going to all go supernova. Add in the actual cost of compute and it just isn't happening, not in this galaxy. For 128-bit crypto we can look at a more earthly calculation. Using the same math as that article, but at room temperature, and taking the total solar irradiance on the Earth as an energy source, it would take this long to count up to 128 bits (calculated using Google): ((2^128) * (1.38064852 * ((10^(−16)) (ergs / K))) * (298 K)) / ((1361 (W / (m^2))) * (pi * (radius of Earth^2))) = 8.04911615 seconds Definitely more on the plausible side, but we're already moving away from 128-bit crypto and there's a staggering number of generous assumptions being made here; we aren't going to be getting thermodynamically ideal computers using a significant fraction of the total solar irradiance on the Earth any time soon. Just to give you an idea of how far away we are from that, looking at actual SHA256 calculations: https://www.iea.org/data-and-statistics/charts/efficiency-of-bitcoin-mining-hardware https://www.iea.org/data-and-statistics/charts/efficiency-of... 22222 MH/J is the highest, or 4.5 × 10^-12 joules per hash. That's a factor of 2^30 worse, so if we used the total solar irradiance of the Earth to power Bitcoin miner style ASICs, it would take about 272 years to go through 128 bits' worth of brute forcing something of similar complexity to SHA-256. The factor is more like 2^36 relative to the first "temperature of outer space" calculation. That happens to be about the number of galaxies in the observable universe, so using current technology, it would take somewhere on the order of all the stars in the observable universe going supernova to power through a single SHA-256 brute force.
  - GoblinSlayer 5y ago
guimplen 5y ago
AFAIK, this is more of a belief than a fact. I would be very curious if you would show me a rigorous proof that e.g. SHA256 requires like on the order of 2^256 of operations to find a preimage of a random 256-bit string.
- Dylan16807 5y ago
  If you have something more clever than 2^256 operations, then that's not brute force.
aumerle 5y ago
That is not true. There is nothing provable about hash functions. The best that you can say is that there is no known algorithm that can calculate a pre-image for any given hash function in less than some super linear time. You certainly cannot prove that no such algorithm exists. If you can prove it please publish a paper you will be revolutionize mathematics.
- marcan_42 5y ago
  > The best that you can say is that there is no known algorithm that can calculate a pre-image for any given hash function in less than some super linear time. If your algorithm is not linear in the size of the key/hash space, it's not a brute force algorithm. It's a cryptographic break. There is no proof that such algorithm does not exist, nor is there any proof that it does. Therefore you can't claim it definitely does. That's my point.

elcomet 5y ago

thanks, that's interesting, I didn't know this !

samstave 5y ago

This is why they create laws to require you unlock your phone when crossing borders. I have been constantly surprised that there isnt a phone/company that specifically markets to "buy this temp phone to cross a border" -- Also, WRT Quantum computing, what are your thoughts on the talk by D-Wave CEO where he said "we can reach into different dimensions" -- and soon after, D-Wave went super silent? What is the state of quantum currently - did they discover something super secret?

antris 5y ago
They? Who, where? Which law?

xoa 5y ago

>Modern cryptography is not breakable via brute force any more Specifically, modern symmetric crypto (and hashing which is a related but different thing) is fine. It's public-key crypto that has always been the worry thanks to Shor's Algorithm, and all modern widely used crypto there is indeed vulnerable if an actual scalable general quantum computer could be constructed. There are a variety of post-quantum cryptographic algorithms under development including some ones that would be ugly slow but likely effective bandaids if required, but that's still a not totally unreasonable concern for certain threat profiles. But yes GP was totally wrong about "all methods are broken when compute becomes faster". >I'm not sure if anyone has run the math "The math" here is just Grover's Algorithm, that lowers the cost of generic brute forcing to O(sqrt(n)). So a 128-bit symmetric key could be cracked on average like 2^64 or a 256-bit key like 2^128. Obviously this is utterly trivially countered by doubling the exponent. Even 2^128 is still ridiculous, and going to a 512-bit key brings us right back to 2^256 which is impossible. 128-bit keys should indeed be phased out entirely (and that seems to be well on the way anyway), and perhaps 256-bit too at some point (even if it's only the very paranoid or very long termers, it's also not big stretch on modern hardware at all, so eh), but fundamentally yes symmetric crypto is fine.

marcan_42 5y ago
I know about Grover's Algorithm, but the reason I didn't want to make any hard claims is that with hashes you also have to worry about collision attacks. Those give you an O(sqrt(n)) time advantage themselves in classical computing, at the expense of space for storing existing hashes (birthday attack), and you can play with the balance as a space-time tradeoff. I can't claim to have any idea how those interact with quantum crypto, plus once you introduce storage at a large scale I imagine you start running into speed of light and communication energy cost issues.
- im3w1l 5y ago
  So one thing im thinking could work is to do a sort of probabilistic birhtday attack. Like you could do a binary search, where in every step you narrow down on the bucket with more data. So like lets say a year had 256 days and you want to find colliding birthdays. First you would check how many birthdays in 0-127 vs 128-255. This takes just two counters - very little storage. Then lets say the former has more. You'd try 0-63 vs 64-127. Etc. But yeah this will of course miss collisions. But I think if you have enough children (where enough is still pretty close to sqrt(n)) it should have a good chance of finding a collision. And subdividing into many buckets at a time will miss less collisions, but require more storage - a tradeoff can be used.

dooglius 5y ago

Do you have a cite for this for SHA256? It surprises me a bit as our galaxy is big and we are far from physically ideal computers.

marcan_42 5y ago
I did the math myself at one point, but I lost the link. However, here's a reference for the same kind of thing: https://pthree.org/2016/06/19/the-physics-of-brute-force/ https://pthree.org/2016/06/19/the-physics-of-brute-force/ The total energy output of a supernova is enough to count up to 2^220, making a lot of generous (invalid) assumptions. You'd need 2^36 supernovas to just count up to 2^256, never mind actually running SHA256. At minimum. There are circa 2^38 stars in the Milky Way, and they're not going to all go supernova. Add in the actual cost of compute and it just isn't happening, not in this galaxy. For 128-bit crypto we can look at a more earthly calculation. Using the same math as that article, but at room temperature, and taking the total solar irradiance on the Earth as an energy source, it would take this long to count up to 128 bits (calculated using Google): ((2^128) * (1.38064852 * ((10^(−16)) (ergs / K))) * (298 K)) / ((1361 (W / (m^2))) * (pi * (radius of Earth^2))) = 8.04911615 seconds Definitely more on the plausible side, but we're already moving away from 128-bit crypto and there's a staggering number of generous assumptions being made here; we aren't going to be getting thermodynamically ideal computers using a significant fraction of the total solar irradiance on the Earth any time soon. Just to give you an idea of how far away we are from that, looking at actual SHA256 calculations: https://www.iea.org/data-and-statistics/charts/efficiency-of-bitcoin-mining-hardware https://www.iea.org/data-and-statistics/charts/efficiency-of... 22222 MH/J is the highest, or 4.5 × 10^-12 joules per hash. That's a factor of 2^30 worse, so if we used the total solar irradiance of the Earth to power Bitcoin miner style ASICs, it would take about 272 years to go through 128 bits' worth of brute forcing something of similar complexity to SHA-256. The factor is more like 2^36 relative to the first "temperature of outer space" calculation. That happens to be about the number of galaxies in the observable universe, so using current technology, it would take somewhere on the order of all the stars in the observable universe going supernova to power through a single SHA-256 brute force.
- GoblinSlayer 5y ago

guimplen 5y ago

AFAIK, this is more of a belief than a fact. I would be very curious if you would show me a rigorous proof that e.g. SHA256 requires like on the order of 2^256 of operations to find a preimage of a random 256-bit string.

Dylan16807 5y ago
If you have something more clever than 2^256 operations, then that's not brute force.

aumerle 5y ago

That is not true. There is nothing provable about hash functions. The best that you can say is that there is no known algorithm that can calculate a pre-image for any given hash function in less than some super linear time. You certainly cannot prove that no such algorithm exists. If you can prove it please publish a paper you will be revolutionize mathematics.

marcan_42 5y ago
> The best that you can say is that there is no known algorithm that can calculate a pre-image for any given hash function in less than some super linear time. If your algorithm is not linear in the size of the key/hash space, it's not a brute force algorithm. It's a cryptographic break. There is no proof that such algorithm does not exist, nor is there any proof that it does. Therefore you can't claim it definitely does. That's my point.