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.

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

> I don't think anyone should presume ill intent here on the part of NIST.

We should assume a federal agency will keep the best interest of our privacy at heart, because they would never do anything to undermine our trust.

Sounds like a good idea.

I guess I don't really understand the objection to NIST's reasoning. While a larger capacity (c) would increase pre-image resistance, it wouldn't help generic collision resistance (which would always be limited by the output size). There are certainly contexts where a pre-image attack would be more damaging than a collision, but collisions can be a problem in other situations. Asking the user to figure out which security level applies to their application seems like a source of potential issues. Giving them a generic security level parameter to work with might make things easier.

On top of that, Keccak's software performance is nothing to write home about and SHA-256 and SHA-512 look a lot safer now than they did when the SHA3 competition was started. The reasonably large performance boost the capacity changes could bring about might help SHA-3's case a bit for software developers who have barely started moving away from SHA-1 (if they're not still hanging on to MD5).

While 512 vs 256 bits of pre-image security for SHA-3-512 (which the author seems to think is an unacceptable security downgrade) is interesting to discuss in an academic sense, it seems ludicrous to suggest the change would actually benefit someone trying to break SHA-3. Any adversary able to perform 2^256 operations is so far beyond modern cryptanalysis that everyone might as well just give up.

Designing a crypto primitive that generates N bits of output having only N/2 bits of primary preimage security is unprecedented. It's a radical design decision.

The competition Keccak proposals specified a healthy safety margin, NIST proposes to eliminate it entirely. Why? Is it worth being able to hash messages 24-89% faster if in return you have to make your MACs twice as large? For example, if you currently use SHA-1 and want to move to SHA-3 without losing any preimage security, instead of 20 bytes you'll need to send 48 bytes over the wire with every message.

Attacks only ever get better and c/2 is an upper bound. If weaknesses are found in other parts of the function, we may wish there had been at least some safety margin built in.

I agree that it's a new design decision, but I think there is reasonable support for making it. Hash function history has pretty well demonstrated that most implementers don't understand the difference between pre-image security, hash output length and collision resistance. And the security margin is far from eliminated entirely. Not only is there significant margin in the round function itself over the full number ofrounds, but the 256-bit security level provided by the proposed SHA-3-512 seems fairly substantial to me.

I don't quite understand your MAC output length math. As far as I can tell, at least HMAC-SHA1 security could be achieved with SHA-3-512 truncated to 20 bytes of output. From what I understand of sponge functions, pre-image security is based on capacity (more specifically, half the capacity) and that truncated output up to the desired security level is valid. The Keccak page parameter calculator claims 160-bit security can be achieved with a capacity of 320 bits and 160 bits of output.

But I will admit that changing the pre-image security level association with output length does seem like it could create some confusion among people who do understand the current hash security situation. To be honest, I would be OK with NIST making the capacity for both be 512 bits (or 576 as DJB suggested). SHA-3-512 performance doesn't suffer much, since it has the most to lose there, security levels are reasonable and implementation is simpler. I would still like a higher performing version of Keccak given that there is already little enough reason to switch to it, but the 512/576 universal capacity might be a reasonable compromise since it wouldn't make SHA-3-256 THAT much slower from NIST's proposed parameters.

> SHA-3-512 truncated to 20 bytes of output

At this point, your fellow software developers are pointing and laughing at you for "inventing your own cryptography". Your function doesn't come standard in any library. Every single 3rd party audit of your architecture raises a red flag about this and you have trouble finding any official documentation to back you up. (Ask me how I know about this :-)

I'm not trying to say you don't know what you're doing or that that wouldn't meet the security properties, I'm just saying that the whole point of NIST defining these standards is to save us from having to come up with this kind of thing on our own.

NIST actually does define truncated versions of SHA-2, e.g., SHA-2-512/256. But they specify a different IV so that the functions are distinct.

> some confusion among people who do understand the current hash security situation

Right. I totally agree that most of the time we should assume that collision resistance is the relevant figure, whether we can see the attack or not. But still, SHA-2-256 has has 256 bits of preimage resistance just like a 256 bit random oracle. But SHA-3-256 will have 128? Can we use SHA-3-256 to derive an AES-256 key?

Don't forget that NIST has mentioned they'll standardize variable-output-length SHA3: SHAKE512 with 20 byte output would be perfectly fine. They've also mentioned they might include MAC and AEAD standards, so I'm not convinced the situation is as bad as you make it.

OK so NIST-SHAKE512-[0 <= bit < 256] is basically what was proposed as round 3 Keccak-256.

But it's a) unwieldy to specify, and b) reveals the output of NIST-SHAKE512-[0 <= bit < 128] unlike other truncated hash standards.

Note: I am definitely not saying this is the end of the world.

I think you're on to something there with regards to the performance. Schneier was making some noise towards the end of the competition that none of the entries really improved on speed. ( https://www.schneier.com/blog/archives/2012/09/sha-3_will_be... ) Contrary to to article, hashing is used a lot, and there are a few areas where performance will be an issue for sometime (mobile space, and high-density virtualized environments) It may be that the key space was indeed deemed excessive, and of little added benefit compared to the rewards gained in greater speed.

As another mentioned further down, no one is simply going around busting up 256bit keys, and when it finally happens, it will be with a computational paradigm that will require a defense built to an entirely different set of requirements: out of the scope of this competition.

Minor correction: The final round submission specified c=512 and c=1024 bits for Keccak-256 and Keccak-512 respectively.

Thanks! This was much clearer than the blog post.