Hacker News Reader

Comment by ajsfoux234 | Hacker News Reader

The vulnerability impacts 'the "official" SHA-3 implementation'. How widely used is it for SHA-3 hashing compared to something like OpenSSL?

View on HN

SHA-3 is rarely used in general. Most applications still use SHA-2 hashes (such as SHA256).

Rare != bad && rare != unimportant.

The point of NIST standardizing on SHA-3 is to gradually replace SHA-2 due to the rise of computing power and the likelihood it will become as weak as SHA-1 is now in the near future. Unfortunately, like American credit cards vs. European chip & pin, it's going to take forever to adopt.

"near future"? I doubt that. Eventually, but likely not in my lifetime.

https://www.imperialviolet.org/2017/05/31/skipsha3.html

No. The "rise in computing power" doesn't jeopardize SHA2. There are important design differences between SHA1 and SHA2 (here's where in my younger days I'd pretend that I could rattle off the implications of nonlinear message expansion off the top of my head). SHA2 is secure; don't take my word for it through, you can find one of the Blake2 designers saying SHA2 is unlikely ever to be broken, or Marc Stevens on a Twitter thread talking briefly about why his attacks on SHA1 don't apply at all to SHA2.

I agree, SHA-2 is secure as far as we know. But since it's based on Merkle-Damgard, it permits length-extension attacks - i.e. given H(x), one can derive H(pad(x) || y) without knowing x.

So we need to be careful not to use it in setting where that would be problematic. Or we can use it with workarounds, like double hashing (SHA-256d) or truncating its output.

SHA-3 is sponge based, so its output is always truncated, preventing length-extension attacks. So I think SHA-3 is a better default, though it's fine to use SHA-2 if you know what you're doing.

Truncated SHA512 hashes, such as SHA512/256, defeat length extension attacks by omitting part of the hash state from the output. They're also significantly faster than classic SHA256 for large inputs.

Blake2/3 also doesn't suffer from length extension attacks, but SHA-256 is what everyone uses unfortunately.

We use Blake 3. So far so good…

I'm always leery when primitives mention their speed as a selling point because I'm thinking about the memory and CPU/GPU/ASIC costs required for adversary X years from now. Sure, one can hash or encrypt using N repeated rounds to up the cost but still: speed isn't everything.

Outside of password hashing applications, which message digests like the SHA and Blake families aren't ideal for anyway, hash functions don't really derive their strength from being slow. If a hash is seriously broken -- in the kind of way that MD4 is, for example -- attacks against it may require so few operations that the speed of the hash doesn't matter at all. But, so long as the hash function remains unbroken, any attack against it requires so many operations as to make it completely infeasible, regardless of how fast it is.

Like the sibling says, speed is not really related to hash security. Either the hash is good at any speed or it’s broken. Speed is important if you’re hashing often. Systems that hash often, in my experience, tend to have a stronger security posture than systems that use bearer tokens. So… fast strong hashing is good for applications because it enables good crypto to be applied more thoroughly. And that’s why we use Blake3, fast strong hash/kdf/xof that we can use anywhere (from powerful servers to wasm) without much of a second thought.

SMH. You're conflating "broken" by mathematical attack and having enough computing power to brute it (GPUs or quantum). Rise in computing power always jeopardizes the baseline brute cost of every algorithm, which is why standards shift over time, otherwise 3DES would still be recommended for new applications instead of AES.

An obvious issue is that many protocols do two-sided negotiations of crypto algorithms during a handshake - so one of "most applications" which uses SHA-2 hashes by default could be vulnerable to a network connection saying "I don't support SHA-2, let's use SHA-3 pls?" and then exploiting the buffer overflow.

In a similar manner, apps that verify signatures/certificates often let the certificate specify which algorithm is used, so again effectively an attacker may be able to force the app to use SHA3 as long as it uses a library that has some support for it.

> two-sided negotiations of crypto algorithms

This is a common problem, and massively increases attack surface, since if a vulnerability can be found in any algorithm, it can be exploited. Downgrade attacks are a varient of the same.

Let me present an alternative:

Each protocol has one specific encryption algorithm and set of parameters. However, that set isn't fixed, but defined based on the current date and time.

For example, HTTPS could be defined as "SHA1 from 1996 till 2006", "SHA256 from 2005 till 2018", "SHA3 from 2017 till 2032", etc.

The dates can be written 10+ years into the future, so that software deployed today is still usable that many years into the future. As soon as the last date period expires, the software is not usable until it has been upgraded (unless both ends of the communication link choose to fake the date).

There is precedent for software 'expiring' - that happens whenever the root certificate of a trust store reaches an expiry date.

The downside is sometimes an algorithm might be broken before its date comes, and other times an algorithm may still be secure at that date. But that still seems better than our current mess of downgrade attacks.

As you say, it could be that an algorithm gets broken before its "expiry date" or remains secure well past that (look e.g. at AES). There is a similar but better alternative, usually called "opnionated cryptography". A protocol specifies a single cryptographic primitive for each type needed (hash function, block cipher etc) so no negotiation is needed. If one of the primitives gets broken, a new version of the protocol is released that uses a different primitive.

It seems to me that it may be better in many cases to support exactly two configurations (or some other small fixed number). This way there is no need to wait until a new version is released and dropping the vulnerable one won't cause any downtime. Ideally both codepaths would be regularly exercised (maybe clients should pick randomly when both choices are available). Then as soon as a vulnerability is discovered (maybe even before it is publicly revealed) all clients and servers could immediately drop support for the one that was discovered vulnerable.

Then the release of a new configuration can be done slowly with reasonable caution to get back to the desired redundancy level.

And then you still have a roll-out period during which those two protocols are available, so the two parties still need to negotiate which version they want. It's not clear to me what the advantage over the current situation is?

>the two parties still need to negotiate which version they want

Not necessarily. If the client contacts the server using version X, the server will reply with version X.

That's sounds a lot like protocol negotiation, just implicit vs explicit and limited to 2 algos.

What if the server doesn't support version X? Then the client will try again with version X-1. This is a negotiation, it is just an inefficient one (client might have to try X-1, X-2, X-3 in turn if more versions are still co-existing; and contrarily, if client doesn't support any version the server does, you will not get a detailed error about the version mismatch, because they are entirely different protocols).

>Then the client will try again with version X-1

Who says that? Either it is specified in the protocol, and then you're right that this is still a negotiation, or it is not specified in the protocol, so if the client does that is implementing some out of spec behavior. Which is true that already happened on the Internet for compatibility's sake, but keep in mind that there is still an advantage, as an adversary can't easily mess in the connection setup phase in a way that protocol version X looks like protocol version Y.

If you don't have this downgrade, then clients can't talk with servers that haven't been upgraded yet! This means either that:

* you expect all servers to upgrade immediately, or at least faster than clients, or

* you delay upgrading clients you know to be insecure until servers had time to upgrade, or

* you are ok with breaking a significant portion of the network for every protocol update.

Either way, your proposal makes no sense for the internet.

Additionally, this is already possible with the current negotiation scheme. You can have clients refuse old algorithms (and they do). Your proposal doesn't improve anything there or anywhere else.

Negotiation makes the protocol more complicated, so more room for bugs. Additionally, sometimes (or maybe all times?) you need to explicitly configure a client or server to not accept broken algorithms during the negotiation, so you would need to keep track for yourself for which algorithms are safe to use and which are not. Anyway it would be interesting to look at how the Wireguard folks would handle this, as Wireguard is a protocol with opinionated crypto.

I've mostly seen SHA-3 used in more modern applications, it's used a lot in cryptocurrencies (with BLAKE2)

I’d love to use SHA-3, but I’m waiting until I see SHA-3 in standard libraries for my most-used languages.

The version in the Golang stdlib defaults to a pure-go implementation... unless you're compiling for amd64, in which case you get an assembler variant apparently directly derived from the XKCP package (https://github.com/golang/crypto/blob/master/sha3/keccakf_am...).

Slightly concerning news for the (mostly-Golang-based) Ethereum ecosystem, which relies on SHA3-256 for pretty much everything...

Easy enough to test, right?

    func main() { 
      h := sha3.New224()
      buf := make([]byte, 4294967295)
      h.Write(buf)
      sum := h.Sum(nil)
      fmt.Printf("%x\n", sum)
    }

Doesn't crash on my amd64 dev machine.

Later

I could have just looked at the code, too: the assembly you've linked to is just the Keccak permutation, not the entire Go hash; the buffer management is done in Go, not in assembly.

This is one of those cases where I'm actually more concerned that it doesn't crash. It's like seeing clearly-syntactically-invalid code that somehow compiles anyway — you wonder what semantics the compiler could have possibly ascribed to it.

Presumably this isn't not-crashing just because the developers of the Golang stdlib somehow found+fixed this bug back in 2015 when this assembler file was baked. The error is in that assembler code, I'm sure. It's presumably getting masked by something. (Something that may be benign, or might be subtly corrupting the runtime.)

For a benign case: maybe the Golang runtime isn't allocating you precisely as many bytes as you're asking for, but rather a little bit more? Perhaps rounding up to a multiple of a page for more-than-page-sized allocations?

Not having access to an amd64 machine at the moment, I'll have to ask you: does increasing the size by one, as in the article, cause an infinite loop?

No, it causes the string

    c5bcc3bc73b5ef45e91d2d7c70b64f196fac08eee4e4acf6e6571ebe

No matter what Go is allocating under the hood, it has to be feeding exactly that many bytes to the SHA3 algorithm.

> it has to be feeding exactly that many bytes to the SHA3 algorithm

Well, yes, but this is supposed to be a buffer overflow — the algorithm itself is reading and/or writing past the end of the buffer it's been handed. My hypothesis was that Golang is allocating in such a way that reading/writing a single byte past the received slice bounds won't result in a protection fault in the way you'd expect if the allocation were exact.

The buffer overflow is in the C version of the algorithm (and likely related to loop condition checks idiomatic to C's for-loops). The Go version is a fresh implementation, not a wrapping of the C version. I'm no Go programmer, but if I'm not mistaken, the Go implementation just eats little slices of the input buffer until no more buffer is left, leaving all the overflow-danger to the Go array implementation:

https://github.com/golang/crypto/blob/642fcc37f5043eadb2509c...

Possibly not as fast as C, but easier to reason about, I'd say.

Just for what it's worth, we're talking about the amd64 assembly version of the SHA3 code in the x/crypto/sha3 library; I didn't look carefully at how it's called, so if it's used incrementally the way this Go code shows, then yeah, it's fine regardless.

A second later

Oh, wait, yeah, this is just the Keccak permutation in assembly, not the entire hash. That was dumb of me. Yeah, this code looks ok?

Indeed, the two assembly variants are just of the 1600 byte block bit fiddling (keccakF1600).

The outer loop of the Write method (function?) is the same for all architectures.

Are you sure this is the same code that triggers the vulnerability? Is the double `update` in the post itself unimportant (i.e., first updating with a 1-byte string, then the 4,294,967,295-byte string)? As I don't think this does that.

Let's try! Gimme a sec. And: to be clear: I make no representation that this code proves anything, and people should of course take a hard look at the SHA3 amd64 assembly code. I'm just having a message board discussion.

One sec and I'll get you an answer to your thing about the extra write.

With the extra write:

    c5bcc3bc73b5ef45e91d2d7c70b64f196fac08eee4e4acf6e6571ebe

With the extra write and an extra byte on the big write (to try to trigger the loop condition):

    ec66be1ebccf055f839fccf2d12e641dcbbda4f5c71a3bdee6509495

Off-by-one error. Didn't do the 1 byte update.

See downthread, but I don't think it matters. I didn't look at the code before writing the test case; the code here is just the SHA3 transform, not the buffer management code around it, which AFAIK is just Go code. I don't see an opportunity for the overflow here?

All the Go code is safe. No bugs.

I read the code carefully, both yesterday and today, and it's correct.

Read it yourself here:

https://cs.opensource.google/go/x/crypto/+/refs/tags/v0.1.0:...

There's obviously no problem.

Reply on news.ycombinator.com