Hacker News Reader

Comment by elcomet | Hacker News Reader

unlikely ? all methods are broken eventualy when compute becomes faster

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.

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

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?

They? Who, where? Which law?

>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.

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.

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.

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.

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/

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...

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.

A supernova may be an inefficient source of energy, it's probably better to take that material and make dwarf stars from it.

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.

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

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.

> 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.

Computers can only become faster within the limits of what humans are able to build and what physics allows.

You're not gonna break SHA256 with faster computers.

I swear there was a pertinent article link that goes through how it's physically impossible to construct a computing device fast enough to break SHA-256, even at the most fundamental scale.

All current methods. Isn’t sha256 an order of magnitude more complex than sha1? It’s not like cryptographers can’t learn from their mistakes.

Reply on news.ycombinator.com