Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What is going on with NIST’s SHA-3?

cdt.org

Post reply on HN
Print view View original

21–30 of 50 posts

Re: What is going on with NIST’s SHA-3?

#21

Post by rainsford »

marshray wrote: post #2

Basically, NIST seems to be reasoning that because Keccack's sponge construction has no internal resistance to meet-in-the-middle attacks, the collision and preimage resistances are the same. An upper bound on the security of Keccack is set by the expression c + r = 1600. 'c' represents the internal bandwidth of the hash that is not directly controllable by an attacker. 'r' is the rate (bits per expensive f() functio…

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.

Re: What is going on with NIST’s SHA-3?

#22

Post by marshray »

marshray wrote: post #2

Basically, NIST seems to be reasoning that because Keccack's sponge construction has no internal resistance to meet-in-the-middle attacks, the collision and preimage resistances are the same. An upper bound on the security of Keccack is set by the expression c + r = 1600. 'c' represents the internal bandwidth of the hash that is not directly controllable by an attacker. 'r' is the rate (bits per expensive f() functio…

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

Re: What is going on with NIST’s SHA-3?

#24

Post by marshray »

rainsford wrote: post #21
marshray wrote: post #2

Basically, NIST seems to be reasoning that because Keccack's sponge construction has no internal resistance to meet-in-the-middle attacks, the collision and preimage resistances are the same. An upper bound on the security of Keccack is set by the expression c + r = 1600. 'c' represents the internal bandwidth of the hash that is not directly controllable by an attacker. 'r' is the rate (bits per expensive f() functio…

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 secu…

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.

Re: What is going on with NIST’s SHA-3?

#27

Post by msandford »

ballard wrote: post #23

As a backup, ECHO (nist round 2) has the nice properties of being expensive in both hw and sw execution speed, in addition to being based on existing crypto. Go impl here, from yours truly: https://github.com/steakknife/echo

Yeah I can't understand why everyone wants "fast" so badly. Something which deliberately can't be made fast is the way to ensure security. I don't really care if my SSL negotiation takes an extra 1ms or if my purchases on Amazon cost an extra $0.001 each because of the expense of the hash functions. I'd like security, thanks. When the price is so trivial, who really cares if it's 10x as expensive?

Re: What is going on with NIST’s SHA-3?

#28

Post by rainsford »

marshray wrote: post #24
rainsford wrote: post #21

Earlier quoted context omitted.

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 secu…

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 SH…

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.

Re: What is going on with NIST’s SHA-3?

#29

Post by ballard »

msandford wrote: post #27
ballard wrote: post #23

As a backup, ECHO (nist round 2) has the nice properties of being expensive in both hw and sw execution speed, in addition to being based on existing crypto. Go impl here, from yours truly: https://github.com/steakknife/echo

Yeah I can't understand why everyone wants "fast" so badly. Something which deliberately can't be made fast is the way to ensure security. I don't really care if my SSL negotiation takes an extra 1ms or if my purchases on Amazon cost an extra $0.001 each because of the expense of the hash functions. I'd like security, thanks. When the price is so trivial, who really cares if it's 10x as expensive?

Yeah, reminds me of the CPU clock speed wars. [0] Shouldn't crypto security margin be $-oriented [1] related to the secrets / lives / etc. being protected? In backup / availability formally use something called a BIA to justify investments based on risk to operations. (A document used by IT people &| consultants to get business people to spend $ on backing up critical shit) [2]

Refs:

[0] http://c2.com/cgi/wiki?PrematureOptimization

[1] https://www.tarsnap.com/scrypt/scrypt.pdf p. 14

[2] http://www.ready.gov/business-impact-analysis

Re: What is going on with NIST’s SHA-3?

#30

Post by NelsonMinar »

dsl wrote: post #15

Can someone fix the title? SHA3 is not an encryption standard.

I've long since given up trying to give meaningful titles to Hacker News posts since the anonymous silent moderators rewrite them.

The blog post I linked is titled "What the heck is going on with NIST’s cryptographic standard, SHA-3?" and that's the title I went with, saving the trouble of someone rewriting it without notification. But they rewrote it anyway. The title I would have chosen is "NIST's ability to do crypto work compromised by NSA", fwiw.

Post reply on HN