Hacker News Reader

Comment by hannob | Hacker News Reader

You're proposing to add extra complexity for some hypothetical scenario that is unlikely to happen. That's a bad tradeoff.

View on HN

There's nothing unlikely with such scenario. See MD5, SHA1 and so on.

See current research on SHA256

https://en.wikipedia.org/wiki/SHA-2#Cryptanalysis_and_valida...

https://dusted.codes/sha-256-is-not-a-secure-password-hashin...

https://security.stackexchange.com/questions/34256/sha256-se...

The Wikipedia link is very reassuring regarding the security of SHA256. All attacks are very far away from going anywhere close to attacking full SHA256 and no major progress has been made lately.

The password hashing remark is correct, but irrelevant. SHA256 is not a good password hash, because it's not made to be a password hash. Don't use it for passwords.

The weaknesses that broke MD5/SHA1 were known since 1994. No similar weakness is known for SHA256.

If you want to be reassured then sure. My take from reading that is in 2016 there was practical collision attacks demonstrated, which would be amplified with specialized hardware (compare to bitcoin mining).

Btw cheers! I recall you from correspondence years ago regarding fuzz testing linux packages.

> My take from reading that is in 2016 there was practical collision attacks demonstrated

No such thing happened.

You're likely referring to this paper quoted in Wikipedia: https://eprint.iacr.org/2016/374.pdf

This is 1. not about SHA256, but about the truncated sha2 algorithms and, more important, 2. it's an attack on reduced-round versions of these algorithms. That's a common thing in cryptoanalysis to do. You're basically saying "we have no way of attacking the full algorithm, so let's build a version which is much less secure and try to attack that". That's a valid thing to do for research purposes, but it needs to be interpreted correctly. "I can break this massively weaker version of the algorithm" is very different from "I have shown a practical attack on the real algorithm".

Absolutely, you are correct - the papers does not describe SHA256 as broken, but it is one step of many on the path for SHA256 to become broken in the future - which is in reply to your earlier comment:

> You're proposing to add extra complexity for some hypothetical scenario that is unlikely to happen

I do not believe that the practical demonstration of a sha1 collision by google contributed at all to any potential future break of sha256.

> but it is one step of many on the path for SHA256 to become broken in the future

I disagree. It's evidence that the given path is not fruitful for breaking SHA256 in the future. When numerous researchers worldwide have attacked a function, and only broken X out of N rounds, for X << N, and future research hasn't been able to improve X for years, that's pretty good evidence that the technique used isn't going to continue to apply for more rounds. The existence of a multi-billion dollar bug bounty for breaking SHA256 (Bitcoin) that's gone unclaimed for years is further evidence that it's quite strong.

I’m not a cryptographer. Why isn’t SHA256 good as a password hash? Can you explain? And what’s a better alternative, and why?

> Why isn’t SHA256 good as a password hash?

Because it wasn't designed for it. For password hashing you want a hash that has a salt (so that the same password on two accounts doesn't have the same hash on the database) and is as slow as possible (that is, fast enough to validate on logins) to increase brute-force time.

Historically Bcrypt was a good option, but I think Argon2[0] is the current best option.

[0] https://en.wikipedia.org/wiki/Argon2

I thought adding a salt to a password before hashing it was standard practice, regardless of the hashing function. At least that's how UNIX derivatives have done it for the past 25+ years.

Point taken about hash calculation speed, though.

Because SHA256 is fast to compute. This means that an attacker can quickly try many passwords, either from a dictionary of common passwords or simply brute forcing a short password.

Also, if you use SHA256 bare without salt you are vulnerable to precomputed dictionaries. There is a fascinating way to make these dictionaries shorter called Rainbow Tables.

Better key derivation functions take a lot of time and memory to make it costly for the attacker to a lot of guesses at the password and they have built in salt. Examples would be SCrypt or Argon2.

To add to what others have already said:

A password hash is a function with 3 inputs: the password, the difficulty factor, and a customization structure (most often just a salt, sometimes more). A cryptographic hash is a function with 1 input: the message.

Password hashing functions have variable performance in time and usually memory and cache use, controlled by the difficulty factor. Cryptographic hashes have fixed performance.

Password hashing functions take a salt and possibly other customization data (a secret "pepper", a fixed domain-separation string if it's also a key derivation function, etc).

It's possible to build password hashes from cryptographic hashes. One must be very careful about encoding the multiple inputs into a single "message" for the cryptographic hash, to avoid cannonicalization attacks.

Argon2id is a good password hashing function.

unlikely ? all methods are broken eventualy when compute becomes faster

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.

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.

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.

Reply on news.ycombinator.com