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

11–20 of 50 posts

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

#11

Post by nly »

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

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

#12

Post by floody-berry »

> 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's CubeHash was widely panned during the competition for having the exact same "weakened preimage in exchange for performance" tradeoff that is now being made for Keccak.

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

#13

Post by duaneb »

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.

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

#14

Post by nullc »

DJB posted to the NIST SHA3 mailing list a couple days ago suggesting fixing R at 1024, giving the hash a capacity of 576 and a security against preimage attacks of >= 256 bits in all configurations.

This sounds pretty prudent. It avoids any security gotchas, and will also make life easier for implementers because the hash will consume a nice round 1024 bits of data at a time for all hash sizes.

This config would have slightly greater anticipated security at 256 bits than the submission, somewhat worse at 512 bit output— but in both cases be better than NIST's proposed parameters... and the performance impact would be relatively modest.

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

#16

Post by nullc »

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

The weird thing for me is that I predicted skein would not be selected on the basis of it being the only finalist without the full 2x output capacity (which was a NIST requirement that DJB had bucked, and was part of the reasons cubehash had bee removed), I was so confidence in this that I bet money on it and won. :P

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

#17

Post by pbsd »

Dylan16807 wrote: post #9
pbarreto wrote: post #3

Also, this setting does not address the security of MAC constructions based on SHA-3. For instance, HMAC over SHA-2-256 or SHA-2-512/256 with a 256-bit key is expected to attain 256-bit security (i.e. the MAC size equals the security level). Yet SHA-3-256 would not reach anything above 128-bit security, even though the MAC is 256 bits long; to attain 256-bit security one would have to scale the MAC size up to 512 bit…

I think you would be safe using SHA-3-512 and truncating to 256 bits but that is a rather ridiculous way to set up a cryptographic primitive.

Well, not so much now that SHA-3 is length-extension resistant, eschewing the need for HMAC. A standard MAC mode has to be defined anyway, and truncating the output might as well be part of it.

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

#18

Post by kzrdude »

The author doesn't seem to have all the facts. The Keccak team suggested these changes (Go back to Fosdem, Feb 2013 and one of them has a talk). The whole point was that Keccak won the competition by meeting the spec NIST formulated. Then they proceeded to present how they thought a menu of hash strengths and security guarantees would be structured in a smarter way.

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

#19

Post by marshray »

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…

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

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

#20

Post by marshray »

kzrdude wrote: post #18

The author doesn't seem to have all the facts. The Keccak team suggested these changes (Go back to Fosdem, Feb 2013 and one of them has a talk). The whole point was that Keccak won the competition by meeting the spec NIST formulated. Then they proceeded to present how they thought a menu of hash strengths and security guarantees would be structured in a smarter way.

Keccak with a very specific set of parameters is what was submitted to each round of the competition. That was also what was cryptanalyzed by all those folks contributing their time.

I know I wasn't the only one who was a little bit surprised when NIST said "Keccak is SHA-3, now let's see how to standardize a hash function and other applications out of it".

Post reply on HN