13 ms·

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

derefr 4y ago
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_amd64.s 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...
- tptacek 4y ago
  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.
  - derefr 4y ago
    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?
    - tptacek 4y ago
      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.
      - derefr 4y ago
        > 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.
        halffullbrain 4y ago
        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/642fcc37f5043eadb2509c84b2769e729e7d27ef/sha3/sha3.go#L138 https://github.com/golang/crypto/blob/642fcc37f5043eadb2509c... Possibly not as fast as C, but easier to reason about, I'd say.
        tptacek 4y ago
        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?
        4y ago
  - retrocat 4y ago
    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.
    - tptacek 4y ago
      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.
      - tptacek 4y ago
        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
  - tinglymintyfrsh 4y ago
    Off-by-one error. Didn't do the 1 byte update.
    - tptacek 4y ago
      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?
- bugfix-66 4y ago
  All the Go code is safe. No bugs.
  - deleted 4y ago
    [deleted]
- bugfix-66 4y ago
  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:sha3/sha3.go https://cs.opensource.google/go/x/crypto/+/refs/tags/v0.1.0:... There's obviously no problem.
duskwuff 4y ago
SHA-3 is rarely used in general. Most applications still use SHA-2 hashes (such as SHA256).
- tinglymintyfrsh 4y ago
  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.
  - tialaramex 4y ago
    "near future"? I doubt that. Eventually, but likely not in my lifetime. https://www.imperialviolet.org/2017/05/31/skipsha3.html https://www.imperialviolet.org/2017/05/31/skipsha3.html
  - tptacek 4y ago
    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.
    - dlubarov 4y ago
      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.

derefr 4y ago

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

tptacek 4y ago
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.
- derefr 4y ago
  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?
  - tptacek 4y ago
    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.
    - derefr 4y ago
      > 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.
      - halffullbrain 4y ago
        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/642fcc37f5043eadb2509c84b2769e729e7d27ef/sha3/sha3.go#L138 https://github.com/golang/crypto/blob/642fcc37f5043eadb2509c... Possibly not as fast as C, but easier to reason about, I'd say.
        tptacek 4y ago
        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?
        4y ago
- retrocat 4y ago
  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.
  - tptacek 4y ago
    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.
    - tptacek 4y ago
      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
- tinglymintyfrsh 4y ago
  Off-by-one error. Didn't do the 1 byte update.
  - tptacek 4y ago
    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?
bugfix-66 4y ago
All the Go code is safe. No bugs.
- deleted 4y ago
  [deleted]
bugfix-66 4y ago
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:sha3/sha3.go https://cs.opensource.google/go/x/crypto/+/refs/tags/v0.1.0:... There's obviously no problem.

duskwuff 4y ago

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

tinglymintyfrsh 4y ago
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.
- tialaramex 4y ago
  "near future"? I doubt that. Eventually, but likely not in my lifetime. https://www.imperialviolet.org/2017/05/31/skipsha3.html https://www.imperialviolet.org/2017/05/31/skipsha3.html
- tptacek 4y ago
  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.
  - dlubarov 4y ago
    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.