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

SHA-3 Buffer Overflow

mouha.be

Post reply on HN
Print view View original

41–50 of 186 posts

Re: SHA-3 Buffer Overflow

#41

Post by tptacek »

tptacek wrote: post #39
retrocat wrote: post #36

Earlier quoted context omitted.

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

Re: SHA-3 Buffer Overflow

#42

Post by tinglymintyfrsh »

tinglymintyfrsh wrote: post #22

Oh shit. I better check my native Ruby extension that I believe uses the reference C code.

Phew. It works.

     gem specific_install https://github.com/steakknife/digest-sha3-ruby 
    git version 2.31.1
    http installing from https://github.com/steakknife/digest-sha3-ruby
    Cloning into '/var/folders/x6/87j2gpl54x79m0nvns2lsrpc0000gn/T/d20221020-79527-r1vite'...
    remote: Enumerating objects: 191, done.
    remote: Counting objects: 100% (3/3), done.
    remote: Compressing objects: 100% (3/3), done.
    remote: Total 191 (delta 0), reused 0 (delta 0), pack-reused 188
    Receiving objects: 100% (191/191), 6.10 MiB | 11.79 MiB/s, done.
    Resolving deltas: 100% (65/65), done.
      Successfully built RubyGem
      Name: digest-sha3
      Version: 2.0.0
      File: digest-sha3-2.0.0.gem
    Building native extensions. This could take a while...
    Successfully installed
     pry -rdigest/sha3
    [1] pry(main)> h = Digest::SHA3.new(224)
    => #
    [2] pry(main)> h.update("\x00")
    => #
    [3] pry(main)> h.update("\x00"*4294967295)
    => #
    [4] pry(main)> h.hexdigest
    => "c5bcc3bc73b5ef45e91d2d7c70b64f196fac08eee4e4acf6e6571ebe"
    [5] pry(main)>

Re: SHA-3 Buffer Overflow

#43

Post by tptacek »

halffullbrain wrote: post #40
derefr wrote: post #35

Earlier quoted context omitted.

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

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:/…

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?

Re: SHA-3 Buffer Overflow

#44

Post by tialaramex »

flatiron wrote: post #11

So if we ported this library to rust sha3 seems peachy? No doubt an interesting port but it now seems inevitable.

There are various crates with pure Rust implementations of SHA3 or of the Keccak functions, I would expect that they just don't have the bug, although it's possible they instead panic under the circumstances invoked in this exploit.

(safe) Rust writes actual bounds checks, so if you accidentally overflow a buffer in some case you never tested that compiles, it would just panic if the case you got wrong occurs in real life.

A more specialised language like WUFFS doesn't write bounds checks, it just constrains all the buffer access variables, so when you write code that could overflow that doesn't compile, preventing this problem.

There is a price for this, you can have code which you know, intellectually, never hits the case where say k = 5, but maybe the proof would be sixty pages of difficult maths, WUFFS just won't compile that code until you add handling for k = 5, too bad, safe Rust insists on behaving as though k might be 5 (e.g. inserting runtime checks), unsafe Rust would allow you to YOLO, with a lot of hoop jumping, C++ doesn't care. Of course if your sixty page proof is wrong then these outcomes feel very different...

Re: SHA-3 Buffer Overflow

#45

Post by tinglymintyfrsh »

flatiron wrote: post #11

So if we ported this library to rust sha3 seems peachy? No doubt an interesting port but it now seems inevitable.

Not the same, but there are multiple implementations. Here's the top one with 13 M downloads. https://crates.io/crates/sha3

If someone used ffi, linked to it, or attempted to reproduce the behavior verbatim in unsafe code, obviously it would have the same problems as the native code.

Re: SHA-3 Buffer Overflow

#47

Post by wahern »

Vecr wrote: post #13
moonchild wrote: post #10

Earlier quoted context omitted.

My understanding was that sha-3 should be faster than sha-2, in a general sense, but sha-2 has hardware acceleration. Is that incorrect?

I think SHA-3 is almost always slower in software, in theory SHA-3 could be hardware accelerated of course, but on both current AMD and Intel systems it's not, where SHA-2-256 is.

AArch64 supports accelerated SHA-3, available on production systems since 2019 with the Apple A13, judging by https://github.com/llvm/llvm-project/blob/c35ed40f4f1bd8afd7...

Power10 also supports accelerated SHA-3: https://www.redbooks.ibm.com/redpapers/pdfs/redp5649.pdf (p150)

Accelerated SHA-3 on x86_64 is probably an inevitability; the question is more when than if.

Re: SHA-3 Buffer Overflow

#48

Post by halffullbrain »

tptacek wrote: post #43
halffullbrain wrote: post #40

Earlier quoted context omitted.

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:/…

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.

Re: SHA-3 Buffer Overflow

#49

Post by tinglymintyfrsh »

tptacek wrote: post #23
derefr wrote: post #17

Earlier quoted context omitted.

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.

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

Re: SHA-3 Buffer Overflow

#50

Post by tptacek »

tinglymintyfrsh wrote: post #49
tptacek wrote: post #23

Earlier quoted context omitted.

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.

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?
Post reply on HN