Is SHA-3 slow? | Hacker News Reader

Is SHA-3 slow?

keccak.noekeon.org

106 pointssnakeanus81 comments

My takeaway from this post kind of is that there are probably too many variants and derivatives of SHA-3. Then again, these days normal developers should probably use some recommended interface of mature crypto libraries anyway and shouldn't play around with cryptographic primitives directly, so maybe more choice for the library devs is good.

Yeah all these discussions are rather aimed at people who implement cryptography or have to make a well-thought hash choice at some point.

As a developer you should use something like libsodium that has a default "hash" API. Underneath, the developers made the choice of choosing Blake2, but this is transparent to the user of the library.

If you do not have access to high level libraries like that, and don't want to loose time/dig too much into the topic, following standards (SHA-3) is easy.

> some recommended interface of mature crypto libraries

Maybe for bubble code it'd be okay to just say "gimma a hash".

But most real code needs to interoperate with stuff. E.g. I need to send a SHA-256 from a JS client to a Python server. So there needs to be a consistent and portable "SHA-256" concept that everyone understands.

A cryptographic hash is not a complicated concept (even if developing one is).

I suppose you can think about whether you require collision resistance or merely second pre-image resistance, but the popular ones are all intended to be collision resistant anyway.

The interop situation with the CRC family of hash functions is terrible. Check this madness out:

https://bitbucket.org/martin_scharrer/crccheck/src/default/c...

Yes and no. After all, these are just modes using Keccak (think, say, AES-CBC, AES-GCM all use AES), so the choice depends more on the purpose than anything else. But indeed, the naming is confusing. Instead of SHA3-256, SHAKE256, KMAC256 and ParallelHash256, maybe they should have better named them SHA-3-hash256, SHA-3-xof256, SHA-3-mac256 and SHA-3-parallel256 (or so).

Is this "is SHA-3 slow?" or is this "Look our new Keccak-based variant!"?

Speaking of hashing quickly, I actually just posted an article about hardware-assisted SHA calculations and their support (or lack thereof) in mainstream processors, if anyone is interested.

https://neosmart.net/blog/2017/will-amds-ryzen-finally-bring...

This was really really interesting! I'm currently trying to get SIMD to work in Go, and my problem right now is that it's hard to understand which SIMD instruction I should support (MMX, SSE, SSE2, SSE3, SSE4, AVX, AVX2, ...?) and how I should test what my architecture supports. If you have any resources on that I'd take it.

AFAIK x86_64 requires that MMX and SSE1/2 are present, so that should be a pretty safe bet unless you have to support ancient x86_32 models.

[0] is a presentation on SIMD targeted at game developers. It has a lot of valuable information about instruction set support and how to make effective use of vector instructions. [1] is a HN comment that summarizes the content.

[0] https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afr...

[1] https://news.ycombinator.com/item?id=9312856

Interesting, thanks for posting this!

> If you have a 64-bit build, you WILL have SSE2 instructions

Go allows you to detect a few architecture when you build (amd64, arm, arm64, 386) but not really the CPU model. So using SSE2 for anything amd64/arm64 would probably be a good solution.

SHA1/2 through NEON on ARM is slower than BLAKE2. "openssl speed aes-128-cbc is approximately..." if performance is of any concern, don't use CBC.

> if performance is of any concern, don't use CBC.

The idea there is not the absolute performance but rather the relative speed of the operation with and without hardware acceleration.

(additionally, openssl does not expose aes-128-ctr or gcm as an `openssl speed` option.)

There are alternatives like BLAKE2. https://blake2.net/

Anyone who thinks that Hacker News comments are a great source of information should consider the number of top-level commenters on this thread who don't know the difference between fast collision-resistant hashes and password hashes, but who decided to post as if they knew what they were talking about.

(on the other hand people were pretty quick to downvote/re-establish the truth)

In fairness, this is because 1) password breaches are the lowest common denominator of hash function discussions in which developers participate, and 2) developers have it beat into their heads not to use e.g. MD5 for password storage, but they don't typically receive the same lectures (with the same vehemence) for things like MACs.

I don't really think this is much of an excuse. Fast collision-resistant hashes and password hashes are very basic crypto concepts. If you don't know that difference, it would be hard to pass even the most introductory course on cryptography. If you've literally no education on crypto except what you heard someone at work say once, you shouldn't feel qualified to correct crypto articles on Hacker News.

Ignorance isn't the problem. The problem is ignorance combined with confidence.

I think crypto is a field where one needs an unfortunately low amount of confidence (relatively speaking) to come across this way, because it's complex enough that the default position is extreme ignorance. That's why I try to be a bit more charitable - I don't think people are trying to come across as authorities on the subject, they just haven't had enough exposure. It's an unknown unknown. Better crypto education would help.

I've been thinking for some time now about the state of cryptography education for non-experts, and what I've noticed over the years is we push a lot of digestible soundbites ("Don't use MD5, don't roll your own, use encrypt-then-mac", etc) without significant explanations. Sometimes there is an accessible explanation for these things that's appropriate for a message board comment, sometimes there isn't, and this advice is necessarily separated from a larger corpus of material due to the medium.

If telling developers what not to do over and over again in order to dissuade them from shooting themselves in the foot has made them more secure overall, this is a good thing. But I do think it comes at the cost of not encouraging real understanding of why not to do these things. You're right that they shouldn't take specific positions without that understanding, but I think it can be hard for them to know they don't have it due to the culture.

Since you guys appear to be familiar with crypto, can you recommend some book/article/blog that give a good intro, to the level of explaining the difference between the two concepts above? Many thanks in advance.

If you'd like to read a book, Cryptography Engineering is probably the best all around introduction.

If you're looking for an online resource, try Crypto101 (https://raw.githubusercontent.com/crypto101/crypto101.github...).

Here’s a good blog post explaining it:

https://blog.tjll.net/please-stop-hashing-passwords/

I wouldn't call myself an expert by any means, but I learned most of what little I do know from three sources:

1. Applied Cryptography by Bruce Schneier.

2. The Matasano Crypto Challenges: www.cryptopals.com

3. The Stanford cryptography courses taught by Dr. Boneh online (still waiting on the second one).

Summary of the post: SHA-3 is slow, but check out these other recently proposed parallelized variants of Keccak, they could be much faster.

I read it this way:

- On hardware, SHA3 is faster than every other contender in the competition.

- On software, K12 is so fast that the bottleneck will not be its computation.

There is an RFC being drafted on K12 here: https://tools.ietf.org/html/draft-viguier-kangarootwelve-00

Why would this matter? You can get an IETF RFC drafted on pretty much everything. Dan Harkins even got Dragonfly an RFC: https://tools.ietf.org/html/rfc7664.

I'm just pointing out this thing because it's relevant and was released two days ago :)

Genuinly curious: isn't the whole point of cryptographic hash functions that they are slow by design, so that they can't be made faster?

No, you're confusing them with password hashing functions (bcrypt, scrypt) and password-based key derivation functions (PBKDF1, PBKDF2). These _are_ cryptographic hash functions, but they are designed to iterate many many times (the exact number is customizable) in order to take a given amount of time.

"Generic" cryptographic hash functions like SHA-1/SHA-2/SHA-3 (or BLAKE, or MD5) don't iterate more times than is necessary for security, and are designed to be as fast as possible. This way, you can hash multi-gigabyte documents in a fraction of a second.

Thank you for the clarification!

No. Slow is primarily important for password hashes/key stretching, so specialized algorithms exist for those.

General cryptographic hash functions should not be slow, since in many scenarios they are used on a lot of data and slowness has no security benefits.

For passwords, yes. You want your hash function to be as slow as possible to reduce the impact of brute force attacks.

But for all other cryptographic purposes like message integrity checking, file verification, signing, or fingerprinting speed is extremely important.

In these cases, the input to the hash is generally public, so there is no reason to even try bruteforcing. And even if you did, these inputs are much longer than passwords.

No good hash functions are usually fast. You're talking about "password hashing function", and I can understand the confusion. Maybe if people decided to rename these "pash" it would be easier.

Anyway the state of the art here is Argon2 which won the latest password hashing competition: https://password-hashing.net/

Your "password hashing functions" have another name already - KDFs, or key derivation functions.

I think we're circling back, KDFs are definitely not suited for hashing passwords. For example, you wouldn't use SHA-3(password) as a password hashing function, but it makes a fine KDF.

If you're thinking of PBKDF2, it's a "password-based" KDF as its name hints. While both password-based KDFs and password hashing functions seem to have common properties, I think the term "password hash" has caught up more (specifically thanks to the password hashing competition).

Who's gonna be the first to launch KangarooCoin or KeccakCoin with a SHA-3 proof-of-work?

There are already a bunch of blockchain stuff using SHA-3 apparently. If people want to drop a list of products/companies/apps that use SHA-3 (or other Keccak construction) I'd be interested!

Ethereum uses SHA-3 to begin with.

To be precise it uses variant of Keccak as NIST changed parameters of SHA-3 when they were already using it.

They started using SHA-3 before it was standardized?

A bit off-topic, but I am currently trying to recover ~$70000 worth of ether[1] from my presale wallet and the encryption used is indeed SHA-3.

I'm currently trying 21970881 passwords against the hash using fairly basic python code (ETA: 2-3 days), and can definitely use tips for speeding up the work, as Id likely need to try an order of magnitude or 2 more generated password in order to crack it.

1. https://etherchain.org/account/0x35f5860149e4bbc04b8ac5b272b...

It's pretty easy to speed up the process by using multi threaded gpu code.

Python? There's tools for this, like oclHashcat/cudaHashcat

You should definitively use hashcat[0]. It's the fastest hashing tool at the moment, and it supports both PBKDF2-HMAC-SHA256 and SCRYPT for Ethereum wallets since the last update.

It can test 588 passwords per second on my modest GPU. I guess that's a lot better than a basic Python script.

You should also have a look at probable wordlists[1], which contains a lot of passwords sorted by their popularity. It could significantly speedup the research, as long as your password has already leaked elsewhere.

[0] https://hashcat.net/hashcat/

[1] https://github.com/berzerk0/Probable-Wordlists

The password definitely hasn't leaked as it is a one time password I created based on a somewhat complex scheme, but switching to hashcat (as also pointed outby flipp3r) seems to be the best next step.

The encryption actually is KECCAK-256, not SHA-3. However, if you are using a library built for Ethereum it'll be called SHA-3.

When Ethereum was being developed, the spec for SHA-3 wasn't finished or something: https://ethereum.stackexchange.com/questions/550/which-crypt...

It sounds like you have it under control but I typically point people to Dave @ https://walletrecoveryservices.com/ for the less tech-savvy. He's pretty good. You can look at his site for what he can and can't crack. I know he's super super busy but it never hurts to give him a shout and ask him if he has any pro-tips or open-source code somewhere. A ping from someone who has a basic understanding of encryption might be refreshing.

Here are a random assortment of links I have saved regarding recovering presales:

https://www.reddit.com/r/ethereum/comments/46887p/tips_for_r...

https://forum.ethereum.org/discussion/3045/request-post-pass...

https://www.reddit.com/r/ethereum/comments/3g6aw0/i_lost_my_...

Slow security is good security.

It makes brute forcing more difficult, and promotes decentralization of infrastructure (slowness adds up only for large-scale deployments like Google and Facebook, and we want to depend less on centralized actors, not more).

If you need to choose between strength and performance, choose strength in nearly 100% of all cases. You make the job of NSA or GRU much harder, and promote offsetting security mechanisms to the edge, where they ought to be.

Once you've reached an appropriate security margin you shouldn't pour more resources into making it even slower. You don't typically need to choose between performance and security in a general sense, because you can achieve very good performance with very good security. Slowing down your password hashing function any further than is required is overkill, and won't improve your security.

Today's security margin is tomorrow's past news.

Usually, security margins are planned against brute force according to Moore's law. This is not enough. Novel cryptographic attacks do not suddenly render the entire algorithm useless (usually); rather, they dramatically reduce its strength. And novel cryptographic attacks appear all the time even in the public space -- who knows what stays behind closed doors and clearances?

If you have large enough security margin, you can escape unscathed while you upgrade your infrastructure. And if not, not.

Sure, but even assuming Moore's Law, algorithms like SHA-2 and SHA-3 are not likely to broken within our lifetimes, if ever. For the set of hashing algorithms that are quantum-safe, you literally gain nothing in practice by making them arbitrarily stronger - they're already so strong that any increase in security margin is a negligible improvement slighter than a rounding error in computational time. But these improvements can come with a performance cost. There's generally no upside and only a downside for choosing to increase the strength beyond what's required for the sake of future proofing.

> Slow security is good security.

This is simply not correct. There are a few cryptographic problems where slowness is the solution, but in most cases you want your cryptographic algorithms to be fast.

Could you please counter my arguments (brute force security against immeasurably larger computing power, resilience to novel unknown crypto attacks reducing the algorithm strength) with something more substantial than "this is simply not correct"?

I could, but doing so would likely involve teaching you a good chunk of crypto 101 while you try to tell me I'm actually wrong so you can be right, which would be enjoyable for neither of us. It would be more efficient for you to just take a introductory course on cryptography from someone more qualified than me. I'm not trying to be rude here, it's just clear that you've learned about password hashing and then assumed based on that one exceptional case that slowness is how all of crypto works. It's not, and you shouldn't make claims about all of crypto if the only thing you know about crypto is that password hashing works by being slow.

Slow security is bad for many reasons:

1) It means default-secure will not happen. If the NSA has to spend 10x as long to attack your security, but 1/10th as much communication is encrypted, it's a win for them (since now the simple fact that something is encrypted means someone put effort into it, which is a good signal that it will be useful).

2) Brute force attacks are typically embarrassingly parallel, and can be amenable to special purpose hardware (e.g. GPUs). An attacker with an 8 GPU system spend $10k and can attack PBKDF2 much faster than a $10k server will be authenticating people.

3) If your security relies on slowness, then people will pick less-secure defaults. If you can get an equivalent level of security per cpu-cycle, then people will pick a higher security margin (this is the non-binary version of #1).

3DES is way slower than most crypto primitives used today. I haven't seen it recommended much though.

I think it's crazy that we're considering "settling" for a 128-bit hash function that we won't even start to adopt until 5-10 years from now, when Google is already planning to announce its 49-qubit quantum computer by the end of this year. It's also very likely that quantum computers will scale at a "Moore's Law" of sorts rate (doubling the qubits every 2 years or so, if not even faster in the first few years). We've seen that with D-Wave already.

http://spectrum.ieee.org/computing/hardware/google-plans-to-...

I feel the same about all of those "faster" (read: weaker) IoT-optimized crypto algorithms that are being proposed right now for standardization.

What we should be talking about now is quantum-resistant algorithms that are likely to be even slower than SHA-3, but would at least protect communications against quantum computers. We need them soon, because they'll have to be deployed on 80%+ of the internet by 2030 or so, and we know how slow the internet ecosystem is at adopting a new protocol.

> I think it's crazy that we're considering "settling" for a 128-bit hash function

Actually the sponge capacity in the so called 128-bit keccak functions is 256, they only call them 128-bit because they provide 128bits of preimage and collision resistance (at 256 bits of output). In a quantum setting the difficulty for preimage and collision attacks for these functions is 2^(256/3), when assuming that the output is of at least 256 bits.

> What we should be talking about now is quantum-resistant algorithms that are likely to be even slower than SHA-3

SHA3-256 has c = 512 and output of 256 bits (128 bits of preimage resistance and ~85 bits of collision resistance on a quantum setting), while SHA3-512 has c = 1024 and output of 512 bits (256 bits of preimage resistance and ~170 bits of collision resistance on a quantum setting). I would say that both of the above sha3 versions are quantum resistant.

Most modern symmetric cryptography would safe in a post-quantum world, I would say that the only thing that is left is to adopt post-quantum asymmetric algorithms more widely.

> they only call them 128-bit because they provide 128bits of preimage and collision resistance (at 256 bits of output).

You're right, Appendix A.1 of http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf

Quantum computers are pretty unlikely to follow anything like Moore's law. They are fundamentally difficult to scale up due to decoherence and compounding of errors, a property that digital circuits have never shared. It's not "just" a matter of increasing density or clock rates.

I'm not sure if SHA-3 has a design goal of being fast. My understanding is that, if your using it for encryption, for example password storage, you want it to be slow. This helps with brute force attacks, particularly if someone gets ahold of your database full of password hashes and can unleash as many calculations as they want. Because the SHA family has typically been fast, they are considered bad candidates for passwords. My quick Google foo doesn't turn up the goals of the competition, but I'm guessing being fast might be a negative.

Remember, what you are talking about is only one application of hash functions. In the world of crypto, speed becomes very important in things like MACs and signatures. There are a ton of other uses for hash functions that are not crypto-related too!

Besides, even when using a "fast" hash function for password storage, you can always just increase the number of rounds to compensate.

SHA-3 is supposed to be fast.

Do not use SHA-3 for password storage!

Use a key-stretching password hash function e.g. bcrypt or scrypt.

(These take a fast hash or encryption function and apply it many many times, to make the total work be slow.)

You're technically wrong, but your concept is right. BCrypt and SCrypt are originally designed to be slow.

PBKDF2 is the function that takes a fast hash function and applies it many times to make it slow.

Or Argon2 as it fits the theme of the SHA-3 competition better (using chacha20 internally, similar to the BLAKE candidate).

From the SHA3 Round 1 results: "NIST expects SHA-3 to offer improved performance over the SHA-2 family of hash algorithms at a given security strength"

You want hashes to be fast, and KDFs to be slow.

KDF != PB-KDF / password hashes. There is no need that a KDF needs to be slow, e.g. you want fast handshakes for protocols (e.g. TLS), not slow handshakes.

Highly recommend using Argon2id/Argon2d/scrypt/bcrypt/PBKDF2 (in that order of preference) for password authentication/"storage." While SHA-3 might be slower than other fast hash functions, it's not at all designed for the same purpose. Functions suitable for password authentication are not merely CPU-intensive, but also memory-intensive.

Shameless plug: https://patrickmn.com/security/storing-passwords-securely/#n...

No, being fast is good in this case. Password hashing is a different beast, with a different competition: https://password-hashing.net

This is a really great discussion of the difference between hashing and secure password storage, would highly suggest reading: https://blog.tjll.net/please-stop-hashing-passwords/

Reply on news.ycombinator.com