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

Maybe Skip SHA-3

imperialviolet.org

Post reply on HN
Print view View original

101–110 of 188 posts

Re: Maybe Skip SHA-3

#101

Post by ktta »

sdrapkin wrote: post #97
ktta wrote: post #79

My suggestion after looking around for the best hash function is SHA-256. Not SHA-512, not SHA-512/256. Not even SHA-224 because it offers no performance benefits. BLAKE2 is a good candidate right now considering speed. But SHA-256 instructions will only get more prevalent which will take care of the speed issue. There have been speed comparisons between SHA-256 and BLAKE2 without SHA instructions[1]. BLAKE2 seems li…

The best (ie. fastest and safest) SHA2-family function is SHA-384. http://securitydriven.net/inferno/#Implementation%20Details

*fastest in software on 64 bit platforms without hardware instructions.

Note that it doesn't have the hardware instructions that are going to be common place for SHA-256 and SHA-224. Also if you have a 32-bit ARM phone (which is most phones in existence), it will take a hit on performance. That's because SHA-512 has 64-bit word size while SHA-256 has 32-bit word size.

I thought I had the winner with SHA-256, but looks like I blanked on the fact that SHA-256 is susceptible to length extension attacks while the truncated versions of SHA2 are not.

So I'll say SHA-224 is the optimal choice because even if you are running on 64 bit platforms, the hardware instructions will make it faster than SHA-512. Also insisting on higher security than SHA-256 is not a very smart move. SHA-256 offers more than enough security margin.

Re: Maybe Skip SHA-3

#102

Post by JackC »

matt_wulfeck wrote: post #64

Why don't we use hash functions that combine the output of two discrete hashing functions and combine the results? It seems to me it's easy to break sha or md5, but what about breaking two fundemantally different algorithms at the same time ? Implementation seems as easy as concatenating the two hex outputs into a single string and comparing the results. I'm curious to what others think of this idea.

A couple of criticisms I've seen for this idea, as best I understand them as an amateur:

(1) It's hard to use a multihash construct correctly. For example, do you want "hash1(message) + hash2(message)" or "hash1(message + hash2(message))" or "hash1(hash2(message))"? The answer is that it depends which features of a hash function matter for your application, and if you pick the wrong one you will have the worst of all worlds instead of the best of all worlds. (Simple example: "md5(password)+scrypt(password)" is a broken way to store passwords, while "sha3(md5(document))" is a broken way to authenticate documents; vice versa would probably be OK.)

(2) If you're paranoid, bytes and CPU cycles are (arguably) better spent on extending your best option instead of tacking on less good ones. Breaks tend to come in the form of "it is now feasible to crack a key with length X" or "find collisions with a hash with Y rounds" or whatever, where X and Y were originally picked to strike a balance of security and performance. So if you were going to spend performance on something nonstandard to guard against mathematical breakthroughs, experts might recommend doubling X and Y instead of throwing in a second less-secure cypher. (Although really they'd tell you just to use the standard thing.)

Re: Maybe Skip SHA-3

#103

Post by optimiz3 »

jasode wrote: post #58
JoshTriplett wrote: post #2

SHA-3 does seem to have relatively little to offer by way of incentives to switch. "Just as good" isn't motivation, and any notions of higher cryptographic strength haven't been extensively discussed. "Easier to implement in hardware" will be more compelling when such hardware exists. I'm curious about the statement that SHA-3 is slow; it links to https://www.imperialviolet.org/2016/05/16/agility.html , which doesn't…

>I'm curious about the statement that SHA-3 is slow; [...] I wonder how much relative attention the SHA-3 winner (Keccak) gets compared to other alternatives, like BLAKE? Coincidentally, I ran a bunch of hash performance benchmarks last week. These were my findings: test: hash a 500MB block of memory. hardware: Intel Core i7-5820K Haswell-E 6-Core 3.3GHz compiler: MSVC2017 (19.10.25019), 32-bit exe: blake2sp - offici…

I'll just say this - there are private implementations of Keccak that blow the pants off of those numbers.

Keccak is one of the primary functions in Ethash (Ethereum mining). It is heavily researched and completely destroys SHA2 performance-wise if you have the right implementation.

Also, Keccak doesn't require the construction of a key-schedule, and can be implemented much more elegantly in parallel (SIMD software) and in hardware than SHA2.

Re: Maybe Skip SHA-3

#104

Post by koenigdavidmj »

baby wrote: post #100
__manuels__ wrote: post #93

Earlier quoted context omitted.

Another advantage is that SHA-3 just uses AND, XOR, ROT, NOT, but not SHR (logical shift right) which allows for much easier formal analysis of the algorithm!

That's not true: https://github.com/gvanas/KeccakCodePackage/blob/master/Stan...

Which is ROT(ate), one of the listed options, even though you have to express it with shifts when writing C.

Re: Maybe Skip SHA-3

#105

Post by mikeash »

hdhzy wrote: post #80
oconnor663 wrote: post #46

Earlier quoted context omitted.

Part of the rule might be an incentive for developers to keep size under control.

I wonder if that rather incentivises them to download assets as a separate HTTP request after the app is started. If not how do AAA games work on the iPhone?

Big games just ignore the size limit entirely and require you to download over WiFi.

Re: Maybe Skip SHA-3

#106

Post by stouset »

baby wrote: post #67
agl wrote: post #60

Earlier quoted context omitted.

If I may (hopefully accurately) summarise your argument: the sponge construction means that we could just implement a single permutation in hardware / optimised software and build everything from it, thus saving die area / code size, and complexity. But deciding to skip SHA-3 doesn't preclude any of that. SHA-3 is the hash standard itself, and even the Keccak team appear to be pushing K12 rather than SHA-3. It seems…

I agree with you. But at the same time I wouldn't toss SHA-3 which is the answer for many applications. If you're agile and you know what you're doing sure. But for people who don't know what they are doing, following the NIST standard is a safe decision. In 20 years maybe we'll get hardware support for keccak-f. In the mean time we can get excited at the idea of most of your crypto primitives (kdf, prng, aead, hash,…

SHA-3 is currently a reasonable choice for effectively zero real world use-cases. SHA-2 has many advantages over it, and I can't think of a single disadvantage.

SHA-3 has practical value as a moderately well-analyzed cipher in the event of rapid catastrophic cryptanalysis of SHA-2, but barring that kind of event its real value is in the general theoretical advancement of sponge constructions.

Re: Maybe Skip SHA-3

#107

Post by dchest »

jasode wrote: post #78
dchest wrote: post #74

Earlier quoted context omitted.

Hmm, something is wrong with your benchmark: the absolute values in MB/s are very low for i7, and relative too — blake2sp should be much faster than SHA256.

>blake2sp should be much faster than SHA256. blake2sp is indeed faster than Microsoft's builtin Crypto API for SHA256. However, it is not as fast as Wei Dai's Crypto++ library implementation of SHA256 that has lots of hand tuned assembly language code. The official C source code for blake2sp does not have assembly language primitives in it. It's very possible that if an assembly language expert wrote optimizations fo…

My pure JavaScript implementation of blake2s (which is approximately half the speed of parallelized sp variant) on 2.6 GHz Core i5 hashes at 170 MiB/s. JavaScript! Whatever you do with your benchmark, you're doing it wrong. Also, there is no reason to use such large buffer sizes, I suspect this only makes benchmarks more unreliable.

For real numbers on many platforms, see https://bench.cr.yp.to/results-hash.html (warning: very large page)

For long messages on 2015 Intel Core i5-6600; 4 x 3310MHz:

    blake2b: 3.33 cycles/byte
    blake2s (remember, half speed of sp): 4.87 cycles/byte
    sha512: 5.06 cycles/byte
    sha256: 7.63 cycles/byte
This means BLAKE2s is close to 700 MB/s, and BLAKE2sp will hash data at more than 1 GB/s.

Here are the SHA-256 implementations measured: https://bench.cr.yp.to/impl-hash/sha256.html

As you can see, the winner varies by platform, but in most cases OpenSSL wins, and Wei Dai's implementation is close.

Re: Maybe Skip SHA-3

#108

Post by baby »

stouset wrote: post #106
baby wrote: post #67

Earlier quoted context omitted.

I agree with you. But at the same time I wouldn't toss SHA-3 which is the answer for many applications. If you're agile and you know what you're doing sure. But for people who don't know what they are doing, following the NIST standard is a safe decision. In 20 years maybe we'll get hardware support for keccak-f. In the mean time we can get excited at the idea of most of your crypto primitives (kdf, prng, aead, hash,…

SHA-3 is currently a reasonable choice for effectively zero real world use-cases. SHA-2 has many advantages over it, and I can't think of a single disadvantage. SHA-3 has practical value as a moderately well-analyzed cipher in the event of rapid catastrophic cryptanalysis of SHA-2, but barring that kind of event its real value is in the general theoretical advancement of sponge constructions.

I think your mis using "world use case". It's a hash function and so it is usable as a hash function.

I'll repeat what was said elsewhere. SHA-2 of vulnerable to length extension attacks.

Re: Maybe Skip SHA-3

#109

Post by baby »

koenigdavidmj wrote: post #104
baby wrote: post #100

Earlier quoted context omitted.

That's not true: https://github.com/gvanas/KeccakCodePackage/blob/master/Stan...

Which is ROT(ate), one of the listed options, even though you have to express it with shifts when writing C.

I'm not sure I understand what you two mean.

1) How does not having SHR makes it easier to audit?

2) how are sha-3 implementations actually using SHR not making the parent's comment moot?

Re: Maybe Skip SHA-3

#110

Post by fpgaminer »

ngrilly wrote: post #91
tptacek wrote: post #9

Earlier quoted context omitted.

That's a good point, but the truncated SHA-2 variants (512/224 and 512/256) are also not susceptible to length extension, and are faster than SHA-3. BLAKE2 was a SHA-3 finalist, and thus by definition isn't vulnerable to length extension either.

> the truncated SHA-2 variants (512/224 and 512/256) are also not susceptible to length extension Any link to some reference document on this topic?

It's pretty straight forward.

SHA-2 works by, after padding the message and appending the message's length, breaking the message into chunks. It sets up an initial state, and then sequentially iterates over the chunks updating the state as it goes. At the end, your state is your hash.

In other words:

   state = INITIAL_STATE
   for chunk in chunks:
      state = SHA2 (state, chunk)
   
   hash = state
So it's easy to see that an attacker can take that hash and keep running iterations after the fact.

Truncated SHA-2 variants are immune because attackers aren't given state, they're given only a piece of state. They have no way of knowing the rest of state, so they can't continue iterating.

Post reply on HN