Hacker News Reader

Comment by nly | Hacker News Reader

> the collision and preimage resistances are the same.

> The idea of a hash function which outputs 256 bits having only 128 bits of preimage resistance is unprecedented.

But does the SHA-3 construction mean a collision attack will further enable a preimage attack? Most breaks in recent cryptographic hashes have been confined to collision attacks. Even MD5 (publicly) hasn't been shown to be vulnerable to a viable preimage attack.

It's worth remembering that just to count to 2^128 it'll take a 3 GHz core with a single cycle increment instruction, along with a billion of its friends, over 3 and a half trillion years.

Also, even if a 128 bit meet in the middle could be computed, it'd require an unfathomable amount of memory.

View on HN

> But does the SHA-3 construction mean a collision attack will further enable a preimage attack?

Yes! This is a well-known feature of the sponge construction. Sponges generally handle this challenge by having a huge internal bandwidth, 1600 bits in the case of Keccack. No one is going to collide that!

However, this internal bandwidth effectively narrows at the points where the message input gets mixed in. Which is why the choice of c (representing the minimum width in bits) is so security critical.

But remember c/2 just represents an upper bound! If algorithmic attacks against the 24 rounds of Keccack's f() function are discovered in the future, it seems very plausible that having a little bit of safety margin in the choice of c could make the difference between it being exploitable or not.

Its deeply troublesome when these kinds of comments come up for two reasons: first and lesser: its wrong; secondly: its inconspicuously wrong. Processor speeds double approximately every generation which we can estimate is once every two years.

What do we have to count to: 2^128 = 3.402823669209385e+38

How many times can we count in a year with a 3GHz core: 3e9 * 3600 * 24 * 365.24 = 9.4670208e+16

In two years, when processing speeds have doubled? 9.4670208e+16 * 2 = 1.89340416e+17

How many years until a core can complete count to 2^128 in a year? log(3.4028e+38 / 9.467e+16) / log(2) * 2 = 143.21

So, in 143 years a single computer will be able to count to 2^128 in a single year. That's still a long time, but its WAY WAY less than the trillions of years people quote. Add in as many extra cores/machines/datacenters/planets of extra processors and you aren't really indefinitely secure. You are secure for a limited number of years and that's it.

> Its deeply troublesome when

People just assume exponential growth goes on forever. You're giving a counter argument to moores law. Moore's law is not physical law, and physical law says otherwise here.

The amount of energy needed to update a counter 2^128 times on a non-reversible computer with the highest efficiency permitted by understood physics requires the energetic equivalent of something like 2 megatonns of TNT.

The additional state that brings security against brute force preimage attacks also tends to increase security against analytical attacks, as well as speculative QC attacks. So it's not worthless, at all— but your moore's law argument is not credible.

> Processor speeds double approximately every generation which we can estimate is once every two years.

Do you have any sources to back up this claim? Max processor speed has stalled to ~4GHz since 2005. If you're referring to Moore's law, it concerns the amount of transistors in ICs, and will eventually hit a limit (not before 10 years, but not after 140 years).

I think "speed" here is "flops", not "hertz".

The Landauer limit [1] is relevant here. Even if you could theoretically make a processor that does it, it would take about 30 gigawatts of power for 1 year [2] to just do 2^128 bit flips (this is obviously a lower bound since it disregards the additional energy required to actually do the calculation). This is more than 1/100th of the world's current energy production. So it's not something that is going to be a concern for most people, and certainly not in the near future!

If the world had access to that kind of energy, I'm sure it'd be used for far more interesting things than finding a single hash collision.

[1] http://en.wikipedia.org/wiki/Landauer_limit [2] http://en.wikipedia.org/wiki/Brute-force_attack#Theoretical_...

Edit: and while we're on the subject of inappropriately extrapolating Moore's law, if current performance-per-watt continues to double every 18 months I'd be interested in how long it'd take to even reach the Landauer limit. I can't seem to find out how much energy it takes to do a single bit flip in a modern processor online, so I can't do the calculation.

Reply on news.ycombinator.com