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

141–150 of 188 posts

Re: Maybe Skip SHA-3

#141

Post by baby »

RcouF1uZ4gsC wrote: post #115
tptacek wrote: post #84

Earlier quoted context omitted.

The advantage to 224 or 512/256 is that they don't expose the full register state of the hash at output and thus, like Blake2 and SHA-3, aren't vulnerable to length-extension attacks: you can (though it would be idiosyncratic to do so) use a simple prefix MAC with them, rather than HMAC.

With SHA 224, there is only 32 bits worth of information that are lost. Isn't a LEA "feasible" by generating the ~ 4 billion messages and finding the 1 that validates. With 512/256 this is infeasible. Is this a real concern with 224 in practice?

It sounds like you're right.

Re: Maybe Skip SHA-3

#142

Post by dchest »

baby wrote: post #73
snakeanus wrote: post #55

Earlier quoted context omitted.

> It allows you to build all the symmetric cryptographic primitives from one basic element! This means: hashes, PRNGs, MACs, encryption, AEAD, etc Isn't this true for most cryptographic hash functions? MAC with HMAC or H(key || m), encryption with a CTR-like mode on top of the MAC, etc.

I think a block cipher allows you to build a lot. Cmac for mac, a block cipher is at the center of sha1/2, aes-ctr for prngs, ... But it's rather that it's used as the center piece of some algorithm whereas doing anything with keccak is just natural.

More than that, a block cipher is a keyed permutation — that is, many permutations selected by the key, soooo by fixing the key we can have an unkeyed permutation and use it for sponges!

Or... BLAKE2 uses ChaCha permutation, but includes additions of key words to turn it into a block cipher, and then uses this block cipher in a MD-like construction. Metamorphosis...

Of course, if you take some block cipher, fix the key, and make a sponge from it, nobody guarantees that it will be secure. Just like trying to build a block cipher from some permutation will not result in anything good. So it's not on the same level as building higher-level secure things (such as PRNG) from a primitive.

I think what I'm trying to say is: in crypto you can indeed build many things from other things.

Re: Maybe Skip SHA-3

#143

Post by dfox »

niftich wrote: post #128
tptacek wrote: post #87

Earlier quoted context omitted.

We had plenty of good ciphers available in TLS when this happened, but because the BEAST bug was in joinery and not in the cipher itself, it didn't help. Cipher agility didn't help, and in fact probably hurt us.

Which "good" ciphersuites [1] were usable in TLS 1.0 when BEAST was made public in June 2011; with BEAST affecting only TLS 1.0? TLS 1.0 per RFC 2246 defined DES40_CBC, DES_CBC, 3DES_EDE_CBC, RC4_40, RC4_128, and IDEA_CBC. RFC 4132 added CAMELLIA_128_CBC and CAMELLIA_256_CBC in 2005, RFC 4162 proposed SEED_CBC in 2005, and RFC 6209 in April 2011 informationally specified ARIA_128_CBC, ARIA_256_CBC, ARIA_128_GCM, and…

I feel that tptacek's point is that excessive cipher agility in TLS precluded adoption of AEAD (and "unconventional" modes in general), because it was built on assumption that the interchangeable primitive is the block cipher itself (ie. keyed primitive that transforms n bit input to n bit output) and not the combination of cipher+mode (which transform arbitrary length input into some, preferrably longer, output). You cannot plug AEAD into framework that expects block cipher and MAC.

(Due to how all this is really implemented, this in fact was not technical problem, but problem of "design culture" or something like that)

Re: Maybe Skip SHA-3

#144

Post by dchest »

jasode wrote: post #136
dchest wrote: post #129

Earlier quoted context omitted.

If I recompile blake2sp with "/O2" optimization, it improves to 171MB/sec. Too slow! You're doing something wrong or measuring some slow implementation :) It should be more than 500 MB/s. Therefore, every hash had no optimizations to keep the comparisons apples to apples. That's not apples to apples at all. Most performant code is written specifically to be optimized by compiler. Use /O3 for benchmarking. Also, you j…

>Too slow! You're doing something wrong I do now notice that my ASUS motherboard monitor software is reporting that my CPU is at 1.2GHz instead of 3.3GHz. There's probably something wrong there. However, even if I get it up to 3.3GHz, the relative speeds between different benchmarks won't change. I got the same relative numbers on the Macbook. >measuring a hand-optimized assembly version and then compared it to a C v…

If I recompile Wei Dai's code with optimization, it will make Crypto++ perform better and make blake2sp look slower.

Just do it. If it's slower, you're doing something wrong. Which implementation of blake2sp are you measuring? It should be at least 1.5x as fast.

Why? If you study the source code, you'll see a loop inside the hash update() function. Why does a loop outside that update() mean "less noise"? Why does adding more function calls of BUFSIZETOTAL divided by BLOCK PROCESSING SIZE equal less noise?

Because you'll be measuring a lot of memory copying time apart from hashing time. Dealing with memory outside of CPU cache introduces a lot of variance.

I suggest that instead of our discussion you should try to reproduce the results of https://bench.cr.yp.to (which is a highly trusted source, e.g. it was used during SHA-3 competition by NIST and participants): if something doesn't approximately match it means you did something wrong. In the process, you'll learn how to properly benchmark hash functions and make some sciency science by reproducing results! :-)

Re: Maybe Skip SHA-3

#145

Post by pshc »

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 recently came to believe (correct me if I'm wrong) that the recommended XOFs SHAKE128 and SHAKE256 are actually nice and fast, but often when people talk about SHA-3 they focus on the slower "drop-in replacements" like SHA3-256 which are quite conservative.

Re: Maybe Skip SHA-3

#146

Post by dchest »

kobeya wrote: post #47
remcob wrote: post #45

> SHA-3 did introduce something useful: extendable output functions Much more than that! Keccak (SHA-3) introduced the Sponge construction. This goes _way_ further than extendable output functions: It allows you to build all the symmetric cryptographic primitives from one basic element! This means: hashes, PRNGs, MACs, encryption, AEAD, etc. The only thing you need that looks like crypto code is a single permutation…

Replying here because you said most of the things I was going to say. This article just makes me sad -- Keccak was chosen for SHA-3 specifically because it turned out SHA-2 wasn't as broken as we feared, and although slow Keccak brings to the table cryptographic diversity and the slew of cool things that can be done with a sponge construction that are now possible using standard cryptographic primitives. NIST made cl…

NIST made clear that by the time of finalist selection, the point of SHA-3 was NOT to replace SHA-2. OP should know better.

That's exactly what this post is about. That we shouldn't replace SHA-2 with SHA-3, just what NIST ordered :)

Re: Maybe Skip SHA-3

#147

Post by yorwba »

baby wrote: post #132
oh_sigh wrote: post #124

Earlier quoted context omitted.

Why does invertibility matter? AND and OR are not invertible, but they are used?

Indeed, the whole permutation is invertible and I'm not sure why either.

Permutations are always invertible. Otherwise several different inputs will be mapped to the same output, which needlessly reduces your state space.

The inverse is also required for decryption: If you encrypt as ciphertext = permutation(plaintext + key), decryption is plaintext = inverse(ciphertext) - key.

Re: Maybe Skip SHA-3

#148

Post by jasode »

dchest wrote: post #144
jasode wrote: post #136

Earlier quoted context omitted.

>Too slow! You're doing something wrong I do now notice that my ASUS motherboard monitor software is reporting that my CPU is at 1.2GHz instead of 3.3GHz. There's probably something wrong there. However, even if I get it up to 3.3GHz, the relative speeds between different benchmarks won't change. I got the same relative numbers on the Macbook. >measuring a hand-optimized assembly version and then compared it to a C v…

If I recompile Wei Dai's code with optimization, it will make Crypto++ perform better and make blake2sp look slower. Just do it. If it's slower, you're doing something wrong. Which implementation of blake2sp are you measuring? It should be at least 1.5x as fast. Why? If you study the source code, you'll see a loop inside the hash update() function. Why does a loop outside that update() mean "less noise"? Why does add…

I think I found the issue. In terms of absolute (not relative) MB/sec performance, the main culprit is the slow cpu speed of 1.2GHz single threaded performance instead of 3.3GHz. The other investigations into "/O2 /O3" optimizations or 8k outer loop were red herrings.

However, for relative MB/sec performance comparison to SHA256, it seems to point back to the blake2 official reference code (non SSE) being very slow. Wei Dai Crypto++ also happens to have BLAKE2 algorithm and when I executed that, it ran at 525MB/sec which was faster than SHA256 and also faster than SHA1. No outer 8k chunk loop necessary for Crypto++ benchmark.

>Because you'll be measuring a lot of memory copying time apart from hashing time.

Yes, I notice the numerous memcpy() functions in the blake2s?-ref.c. For additional tests, I rewrote the loop to call update() on chunks and tried various sizes (8k, 16k, 32k, ... 256k, 512k, 1MB). At 256k chunks and below, I got 235MB/sec which was an improvement but still slower than SHA256. As stated above, the real key was to use an optimized BLAKE2 algorithm instead of the official reference code.

>you should try to reproduce the results of https://bench.cr.yp.to

I can't tell if the blake2 entries in https://bench.cr.yp.to are using official reference or optimized code so trying to replicate those results with official reference files may be a wild goose chase.

Re: Maybe Skip SHA-3

#149

Post by baby »

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…

Daemen talked about some figures for KangarooTwelve during RWC 2017:

* Intel Core i5-4570 (Haswell) 4.15 c/b for short input and 1.44 c/b for long input

* Intel Core i5-6500 (Skylake) 3.72 c/b for short input and 1.22 c/b for long input

* Intel Xeon Phi 7250 (Knights Landing) 4.56 c/b for short input and 0.74 c/b for long input

https://youtu.be/F_nAGS9L97c?t=2451

Re: Maybe Skip SHA-3

#150

Post by baby »

dchest wrote: post #107
jasode wrote: post #78

Earlier quoted context omitted.

>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 (war…

Daemen talked about some figures for KangarooTwelve during RWC 2017:

* Intel Core i5-4570 (Haswell) 4.15 c/b for short input and 1.44 c/b for long input

* Intel Core i5-6500 (Skylake) 3.72 c/b for short input and 1.22 c/b for long input

* Intel Xeon Phi 7250 (Knights Landing) 4.56 c/b for short input and 0.74 c/b for long input

https://youtu.be/F_nAGS9L97c?t=2451

Post reply on HN