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

31–40 of 50 posts

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

#31

Post by AnthonyMouse »

duaneb wrote: post #13
floody-berry wrote: post #12

> it should be based on completely different underlying mathematics Wasn't that shoe-horned in at the end? There were no requirements that it not be e.g. ARX based, or AES based, etc. It wasn't until the final round that any choices were made based on being as alien as possible, where BLAKE's equal security margin and B+/A+ hardware/software performance was tossed out for Keccak's A+/D-. Also of interest is that DJB'…

Well of course they want you to use hardware encryption, much easier to backdoor more or less invisibly.

Also provides a significant performance advantage to attackers with custom hardware.

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

#32

Post by rainsford »

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?

Because there are a lot of ways to make a fast thing slow in cases where "slow" improves security. And at the same thing you're not hurting performance in cases where a slow function doesn't significantly help security and performance might be important.

Making your hash function twice as slow means you've halved the number of hash operations you can perform with fixed computational power. On the other hand, in many situations the resultant doubling of your security margin makes absolutely no practical difference since the existing margin is many, many order of magnitude away from any attacker's capabilities. Making things twice as hard on an attacker sounds impressive, until you think of it like asking someone to travel 2 billion light years instead of only 1 billion. Both are ridiculously outside of our current capabilities, but anyone able to travel 1 billion light years is likely going to be able to travel 2 billion as well.

In more specific terms, making a function with 256 bit security 10x slower has a pretty dramatic impact on performance with a resulting security increase to about 259 bits of security. You have a fairly marginal security increase for making your function 10 times slower. Modern cryptography is fast, but it's not yet fast enough that running at 1/10th the speed won't be noticeable in many situations.

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

#33

Post by betterunix »

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?

If "fast" did not matter, we could use generic constructions of most cryptographic primitives and have very strong security claims e.g. "If you can find collisions for this hash function, you can solve the discrete logarithm problem on elliptic curves." There are a few downsides to such an approach but the primary one, the one that kills it in practice, is speed.

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

#34

Post by einhverfr »

ballard wrote: post #25
dsl wrote: post #15

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

Yea: s/encryption/hash function/ 'encryption' -> 'hash function' for those that dont grok sed

Right, but it is a cryptographic hash, so presumably it would be better to call it a "cryptographic standard."

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

#35

Post by realy »

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

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

#36

Post by harshreality »

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?

There are applications that need to hash data as fast as possible as long as there's a perception of a reasonable security margin. ZFS uses SHA(2)-256 for data checksumming. Some crypto protocols involve HMAC as well as encryption for transmitted data. If a hash can't keep up with line rate on SAS, FC, or many-GigE links, because you wanted maximum security, those users are going to find another, faster, less examined, hash function.

The criteria for SHA-3 is not "as secure as possible". An application that needs as secure a hash as possible should use a protocol that combines multiple hashes of different families.

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

#37

Post by marshray »

rainsford wrote: post #28
marshray wrote: post #24

Earlier quoted context omitted.

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

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

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

#38

Post by afhof »

nly wrote: post #11
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…

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

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.

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

#39

Post by nullc »

afhof wrote: post #38
nly wrote: post #11

Earlier quoted context omitted.

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

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…

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

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

#40

Post by emillon »

afhof wrote: post #38
nly wrote: post #11

Earlier quoted context omitted.

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

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…

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

Post reply on HN