13 ms·

SHA-3 Buffer Overflow

416 points by cbzbc 4y ago

computerfriend 4y ago
LibreSSL-based implementations seem unaffected. I can calculate that hash using hashlib without a segfault.
deleted 4y ago
[deleted]
ajsfoux234 4y ago
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.
    - 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.
cipherboy 4y ago
Does this impact most distros? I'd imagine Python and PHP's native crypto bindings would be replaced with OpenSSL which should have assembly variants of SHA-3.
- ok_dad 4y ago
  I use pyenv and whatever it installed for 3.10.4 months ago seems to be fine with the example code snippet run in the console. It took a few seconds, but didn't crash.
metadat 4y ago
If you're familiar with SHA-256 and this is your first encounter with SHA-3: The main differences between the older SHA-256 of the SHA-2 family of FIPS 180, and the newer SHA3-256 of the SHA-3 family of FIPS 202, are: * Resistance to length extension attacks. * Performance. The SHA-2 functions—particularly SHA-512, SHA-512/224, and SHA-512/256—generally have higher performance than the SHA-3 functions. Partly this was out of paranoia and political reasons in the SHA-3 design process. Further reading: https://crypto.stackexchange.com/questions/68307/what-is-the-difference-between-sha-3-and-sha-256 https://crypto.stackexchange.com/questions/68307/what-is-the...
- moonchild 4y ago
  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?
  - Vecr 4y ago
    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.
    - wahern 4y ago
      AArch64 supports accelerated SHA-3, available on production systems since 2019 with the Apple A13, judging by https://github.com/llvm/llvm-project/blob/c35ed40f4f1bd8afd709c5342b36f33c7c5b0fbd/llvm/lib/Target/AArch64/AArch64.td#L708 https://github.com/llvm/llvm-project/blob/c35ed40f4f1bd8afd7... Power10 also supports accelerated SHA-3: https://www.redbooks.ibm.com/redpapers/pdfs/redp5649.pdf 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.
      - adrian_b 4y ago
        Most Android smartphones support SHA3 starting with the 2018 models (i.e. Cortex-A55, Cortex-A75 or newer).
arisAlexis 4y ago
Can someone ELI5 the severity of this over the whole internet? What breaks/what not
- flatiron 4y ago
  If you don’t use that library then nothing. If you do and you hash my crafted binary I probably could crash it.
- Ayesh 4y ago
  SHA3 is relatively infrequent compared to sha1/2 and md5. SHA3 also has a few variants, and I don't know for sure if this vulnerability is present in all variants. The vulnerability is only present in the reference implementation. So it's unlikely that other implementations (rush as Rust or Go) are vulnerable. I tested with the latest released and master branches of PHP, both of which segfaulted for the code samples mentioned in the article. The article says Python is also vulnerable.this is because both of the languages apparently use the reference implementation. Ethereum uses SHA3 quite extensively, but I doubt it's vulnerable post migration from PoW, let alone it's unlikely that they use the vulnerable implementation/variant.
- capableweb 4y ago
  Most people limit the amount of input that gets passed to whatever is doing the hashing (SHA-3 in this case) to some amount of bytes that are way less than this issue requires. Most web servers default to a 50MB limit or something like that, I think, not many things accept by default the size required for this exploit. Most cases would involve services that accept large untrusted files from users.
- csande17 4y ago
  The full advisory is linked at https://github.com/XKCP/XKCP/security/advisories/GHSA-6w4m-2xhg-2658 https://github.com/XKCP/XKCP/security/advisories/GHSA-6w4m-2.... In order for an application to be vulnerable, it must: 1. Break the file into multiple chunks and pass them to SHA-3 individually. 2. Make one of those chunks larger than 4 GB in size. (This requires using 4 GB of memory.) This is kind of an unlikely thing for an application to do. If you're breaking the file into chunks, usually you'd use smaller chunks. (And if your server is limited to less than 4 GB of RAM, you might not be able to allocate enough memory to trigger the vulnerability in any case.) But it could be exploitable in some really weird or poorly written application somewhere.
aliqot 4y ago
Interesting they both say "Official Sha3" and "by its designers", which as I remember it isn't that accurate. Keccak was chosen and then NIST added what is affectionately known as the 'mystery padding' before certification. What we know as official is not the way the designers submitted the proposal. This isn't an attempt at a scary accusation, but as a pedant, this got me. For those wondering, here is an explanation by a commenter: The padding change is the only difference, this allows future tree hashing modes as well as the current SHAKE outputs to generate different digests given the same security parameters and message inputs. Up to 4 additional bits are added, which keeps the full padding inside a byte boundary, making implementations with octet only input able to switch to SHA-3 from Keccak with change to only a single line of code. https://crypto.stackexchange.com/questions/10645/are-nists-changes-to-keccak-sha-3-problematic https://crypto.stackexchange.com/questions/10645/are-nists-c... https://cdt.org/insights/what-the-heck-is-going-on-with-nist%E2%80%99s-cryptographic-standard-sha-3/ https://cdt.org/insights/what-the-heck-is-going-on-with-nist... ketccak team's response: https://keccak.team/2013/yes_this_is_keccak.html https://keccak.team/2013/yes_this_is_keccak.html
- encryptluks2 4y ago
  - tptacek 4y ago
    You're responding to a post that links to the Keccak designers saying that the padding change isn't nefarious. You have to be able to do better than "NIST bad" in comments on threads like these.
    - aliqot 4y ago
      From Daniel J. Bernstein: 2022.08.05: NSA, NIST, and post-quantum cryptography: Announcing my second lawsuit against the U.S. government. : https://blog.cr.yp.to/20220805-nsa.html https://blog.cr.yp.to/20220805-nsa.html https://twitter.com/hashbreaker/status/1555625577989541888 https://twitter.com/hashbreaker/status/1555625577989541888
flatiron 4y ago
So if we ported this library to rust sha3 seems peachy? No doubt an interesting port but it now seems inevitable.
- tialaramex 4y ago
  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...
  - green_on_black 4y ago
    It seems that some memory safety bug in C/C++ makes HN frontpage every other day.
- tinglymintyfrsh 4y ago
  Not the same, but there are multiple implementations. Here's the top one with 13 M downloads. https://crates.io/crates/sha3 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.
- drexlspivey 4y ago
  what do you mean? the sha3 crate is 8 years old
brundolf 4y ago
> The vulnerable code was released in January 2011, so it took well over a decade for this vulnerability to be found Ouch
- galangalalgol 4y ago
  Between this and "beacown" I came to a realization. I work on codebases worth way less than these amd we do lots of different static analyzers two compilers, lots of unit tests with coverage checks and asan/ubsan. The linux kernel and sha are worth tons of money. Thus, someone wrote all the pipelines and unit tests for that software too. The problem is, the people who paid for all that work aren't the people that rely on thos software's security. It's paid for by people that rely on it's insecurity. So we don't know about this stuff until they or the people they sold it too use these exploits. Edit: in case the solution I propose isn't obvious, organizations like red hatand google need to pay for these pipelines and unit tests. Getting good unit test coverage is expensive and ubsan and asan don't work without that coverage. So since no one has mentioned it yet, you could rewrite this stuff in rust as a poor man's substitute. It will catch some of the aame things, but ultimately there is no substitute for test coverage with sanitizers. Well, maybe formal analysis?
  - lmm 4y ago
    > So since no one has mentioned it yet, you could rewrite this stuff in rust as a poor man's substitute. It will catch some of the aame things, but ultimately there is no substitute for test coverage with sanitizers. That's backwards. You'll catch more cases with a Rust-style type system that naturally checks everything, than with sanitisers that can only check the paths that get executed in tests.
    - galangalalgol 4y ago
      Rust isn't perfect. UB is a bug in rust, but it occasionally has bugs. Ideally you'd do rust and asan with good unit tests. And yes, if you only picked one, it should be rust, but don't just pick one. And just because you are using rust is no excuse to skip static analysis like prusti, coverage with gcov, llvm, or tarpaulin, and certainly not unit tests.
bobkazamakis 4y ago
https://www.xilinx.com/products/intellectual-property/1-1mjenql.html https://www.xilinx.com/products/intellectual-property/1-1mje... https://documentation-service.arm.com/static/62bb3e4bb334256d9ea8d26f https://documentation-service.arm.com/static/62bb3e4bb334256...
tinglymintyfrsh 4y ago
Oh shit. I better check my native Ruby extension that I believe uses the reference C code.
- tinglymintyfrsh 4y ago
  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) => #<Digest::SHA3: 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7> [2] pry(main)> h.update("\x00") => #<Digest::SHA3: bdd5167212d2dc69665f5a8875ab87f23d5ce7849132f56371a19096> [3] pry(main)> h.update("\x00"*4294967295) => #<Digest::SHA3: c5bcc3bc73b5ef45e91d2d7c70b64f196fac08eee4e4acf6e6571ebe> [4] pry(main)> h.hexdigest => "c5bcc3bc73b5ef45e91d2d7c70b64f196fac08eee4e4acf6e6571ebe" [5] pry(main)>
ouid 4y ago
What dows generating preimages mean here? The preimage is the set of all messages that hash to some set of hashes. Is the author saying the the hash function is reversible in reasonable time?
- SAI_Peregrinus 4y ago
  It's a buffer overflow. They can get a vulnerable implementation to execute arbitrary code, so they can get it to return any value they want. The actual SHA-3 algorithm wouldn't return the same value as the vulnerable implementation, of course.
  - enedil 4y ago
    I didn't see anybody mention arbitrary code execution
    - NicolaiS 4y ago
      It's in the post: a specially constructed file can result in arbitrary code execution
bvrmn 4y ago
It looks pretty difficult to exploit. Untrusted 4GB input with non-chunked update.
- nequo 4y ago
  The purpose of running SHA is to determine whether the input can be trusted though. But it is true that relatively few files circulate at or above that size.
  - thayne 4y ago
    And even if they are, you probably aren't going to do a digest on the whole thing all at once.
    - kevincox 4y ago
      IDK, I see a lot of "non-production" code that likes to read whole files into a in-memory buffer rather than bothering with streaming. With modern memory sizes it is completely possible that you could read a 4GiB file into memory without having issues.
      - Too 4y ago
        Thinking about it, it's strange that hashlib doesn't have a function that accepts a file-object as input, to make the efficient method default pit of success. Naive implementations like hash(f.read()) are all too common to see. Such an api would also allow the entirety of the tight loop to be done outside of slow interpreted code. Guessing the rationale is that if you read a file, you also want to use the content for something else, not only compute its hash.
- mike_d 4y ago
  4+ GB inputs are often fed to hashing functions. Verifying the integrity of file downloads before running them for example.
  - 4y ago
Ptchd 4y ago
Does Tor use SHA-3?
jbaczuk 4y ago
no bounty and still politely reports it. Good guys need more praise.
- baby 4y ago
  it's a public standard, who would pay such a bounty?
  - mhh__ 4y ago
    Someone who values security with real money
  - morepork 4y ago
    I'm sorry, we lost millions of dollars due to an exploit. Don't you have bug bounties to find and fix these things? But this was in a public standard that we were using, we don't cover those. Do I look like I care?
    - baby 4y ago
      Are you telling me this? Or are you going to pay a bounty?
  - amenghra 4y ago
    A couple companies sponsor “the internet bug bounty”: https://www.hackerone.com/internet-bug-bounty https://www.hackerone.com/internet-bug-bounty IMHO, sha3 should be part of that bounty.
- deleted 4y ago
  [deleted]
throwaway81523 4y ago
Didn't they find a vulnerability like this in the official MD5 implementation when they tried to port it to SPARK/Ada and the proofs didn't work? I wasn't able to just find it with web search, but here's a release about something similar happening with another one of the SHA3 candidates (Skein), before Keccak was chosen: https://www.adacore.com/press/spark-skein https://www.adacore.com/press/spark-skein See also: https://www.adacore.com/papers/sparkskein https://www.adacore.com/papers/sparkskein
- deleted 4y ago
  [deleted]
all_these_years 4y ago
SHA-3 in Ruby: $ gem install sha3 $ irb > require 'sha3' > s = SHA3::Digest::SHA224.new > s.update("\x00") > s.update("\x00" * 4294967295) [ Segmentation fault... ] Tested with Ruby 3.1.2 Gem's code (including C native extension): https://github.com/johanns/sha3 https://github.com/johanns/sha3
- abraham 4y ago
  Just over half a million total downloads. So some use but not particularly popular.
- deleted 4y ago
  [deleted]
- johannsg 4y ago
  Released a fix earlier today (Oct 23rd) (v1.0.5)
Donckele 4y ago
“I’ve also shown how a specially constructed file can result in arbitrary code execution, ” Ouch, thats not looking good for a reference implementation for a piece of software deployed on billions and billions of machines that was written by experts and reviewed (and modified) by even bigger egg heads.
- hot_gril 4y ago
  At least it's not SHA-2, which is probably more widely used. Or am I mixing them up?
  - turminal 4y ago
    You are correct, SHA-2 is much more prevalent.
- manholio 4y ago
  Just another nail in the long overdue C/C++ coffin. If not even these experts can get it right, under the best development conditions, public review and highest stakes, on a relatively small component with the most strict specifications, then no one can.
  - adev_ 4y ago
    > Just another nail in the long overdue C/C++ coffin C, f**ing C. By the sake of god. Not C++. Stop to put both in the same basket, it just show you do not know what you are talking about. https://github.com/XKCP/XKCP/commit/fdc6fef075f4e81d6b1bc38364248975e08e340a https://github.com/XKCP/XKCP/commit/fdc6fef075f4e81d6b1bc383... Something like that in modern C++ would have been done using std::span<> and that prevents this kind of out-of-bound access and the party-time that comes with it.
    - saagarjha 4y ago
      C++ offers safer constructs but they have their own sharp edges and you have to actually use them to get their benefits. In security critical software these can still be enough to cause significant problems.
yieldcrv 4y ago
Bro what? This is a big deal right? Like NSO Group hacking everyone for the next 5 years deal?
- raydiatian 4y ago
  > The vulnerable code was released in January 2011, so it took well over a decade for this vulnerability to be found. It would have already been a big deal for the past five years, if anything. Furthermore you have to induce a bufferoverflow first. I’m no security researcher, but to my mind that means you’re either (a) trusting idiots to write sensitive code without a IT Sec team reviewing it, or (b) you’ve got a malicious actor on the inside, who can slip it past review. I’m sure there are plenty of other scenarios, but I’m saying it doesn’t feel likely by gut.
  - UncleMeat 4y ago
    Absolutely not. Buffer overruns aren’t something that only idiots introduce.
hasa 4y ago
It may be dumb question, but is there any realistic use case to use this vulnerability to reveal SHA-3 hashed secrets? Or is it just that attacker can crash systems with suitable input?
- 6LLvveMx2koXfwn 4y ago
  From the article: I’ve shown how this vulnerability in XKCP can be used to violate the cryptographic properties of the hash function to create preimages, second preimages, and collisions. Moreover, I’ve also shown how a specially constructed file can result in arbitrary code execution, and the vulnerability can also impact signature verification algorithms such as Ed448 that require the use of SHA-3. The details of these attacks will be made public at a later date.
deleted 4y ago
[deleted]
adunsulag 4y ago
FYI in the healthcare space to meet ONC Cures Update regulations for bulk patient export, its a requirement to use SHA384 (RS384 or ES384). I would think most implementations will be safe due to the 4GB payload criteria, but if anyone is doing anything funky they'll need to look at this closely.
- jakobdabo 4y ago
  SHA-384 is a hash function from the SHA-2 family, and it has no relation to SHA-3.

416 points by cbzbc 4y ago

computerfriend 4y ago

LibreSSL-based implementations seem unaffected. I can calculate that hash using hashlib without a segfault.

deleted 4y ago

[deleted]

ajsfoux234 4y ago

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

cipherboy 4y ago

Does this impact most distros? I'd imagine Python and PHP's native crypto bindings would be replaced with OpenSSL which should have assembly variants of SHA-3.

ok_dad 4y ago
I use pyenv and whatever it installed for 3.10.4 months ago seems to be fine with the example code snippet run in the console. It took a few seconds, but didn't crash.

metadat 4y ago

If you're familiar with SHA-256 and this is your first encounter with SHA-3: The main differences between the older SHA-256 of the SHA-2 family of FIPS 180, and the newer SHA3-256 of the SHA-3 family of FIPS 202, are: * Resistance to length extension attacks. * Performance. The SHA-2 functions—particularly SHA-512, SHA-512/224, and SHA-512/256—generally have higher performance than the SHA-3 functions. Partly this was out of paranoia and political reasons in the SHA-3 design process. Further reading: https://crypto.stackexchange.com/questions/68307/what-is-the-difference-between-sha-3-and-sha-256 https://crypto.stackexchange.com/questions/68307/what-is-the...

moonchild 4y ago
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?
- Vecr 4y ago
  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.
  - wahern 4y ago
    AArch64 supports accelerated SHA-3, available on production systems since 2019 with the Apple A13, judging by https://github.com/llvm/llvm-project/blob/c35ed40f4f1bd8afd709c5342b36f33c7c5b0fbd/llvm/lib/Target/AArch64/AArch64.td#L708 https://github.com/llvm/llvm-project/blob/c35ed40f4f1bd8afd7... Power10 also supports accelerated SHA-3: https://www.redbooks.ibm.com/redpapers/pdfs/redp5649.pdf 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.
    - adrian_b 4y ago
      Most Android smartphones support SHA3 starting with the 2018 models (i.e. Cortex-A55, Cortex-A75 or newer).

arisAlexis 4y ago

Can someone ELI5 the severity of this over the whole internet? What breaks/what not

flatiron 4y ago
If you don’t use that library then nothing. If you do and you hash my crafted binary I probably could crash it.
Ayesh 4y ago
SHA3 is relatively infrequent compared to sha1/2 and md5. SHA3 also has a few variants, and I don't know for sure if this vulnerability is present in all variants. The vulnerability is only present in the reference implementation. So it's unlikely that other implementations (rush as Rust or Go) are vulnerable. I tested with the latest released and master branches of PHP, both of which segfaulted for the code samples mentioned in the article. The article says Python is also vulnerable.this is because both of the languages apparently use the reference implementation. Ethereum uses SHA3 quite extensively, but I doubt it's vulnerable post migration from PoW, let alone it's unlikely that they use the vulnerable implementation/variant.
capableweb 4y ago
Most people limit the amount of input that gets passed to whatever is doing the hashing (SHA-3 in this case) to some amount of bytes that are way less than this issue requires. Most web servers default to a 50MB limit or something like that, I think, not many things accept by default the size required for this exploit. Most cases would involve services that accept large untrusted files from users.
csande17 4y ago
The full advisory is linked at https://github.com/XKCP/XKCP/security/advisories/GHSA-6w4m-2xhg-2658 https://github.com/XKCP/XKCP/security/advisories/GHSA-6w4m-2.... In order for an application to be vulnerable, it must: 1. Break the file into multiple chunks and pass them to SHA-3 individually. 2. Make one of those chunks larger than 4 GB in size. (This requires using 4 GB of memory.) This is kind of an unlikely thing for an application to do. If you're breaking the file into chunks, usually you'd use smaller chunks. (And if your server is limited to less than 4 GB of RAM, you might not be able to allocate enough memory to trigger the vulnerability in any case.) But it could be exploitable in some really weird or poorly written application somewhere.

aliqot 4y ago

Interesting they both say "Official Sha3" and "by its designers", which as I remember it isn't that accurate. Keccak was chosen and then NIST added what is affectionately known as the 'mystery padding' before certification. What we know as official is not the way the designers submitted the proposal. This isn't an attempt at a scary accusation, but as a pedant, this got me. For those wondering, here is an explanation by a commenter: The padding change is the only difference, this allows future tree hashing modes as well as the current SHAKE outputs to generate different digests given the same security parameters and message inputs. Up to 4 additional bits are added, which keeps the full padding inside a byte boundary, making implementations with octet only input able to switch to SHA-3 from Keccak with change to only a single line of code. https://crypto.stackexchange.com/questions/10645/are-nists-changes-to-keccak-sha-3-problematic https://crypto.stackexchange.com/questions/10645/are-nists-c... https://cdt.org/insights/what-the-heck-is-going-on-with-nist%E2%80%99s-cryptographic-standard-sha-3/ https://cdt.org/insights/what-the-heck-is-going-on-with-nist... ketccak team's response: https://keccak.team/2013/yes_this_is_keccak.html https://keccak.team/2013/yes_this_is_keccak.html

encryptluks2 4y ago
- tptacek 4y ago
  You're responding to a post that links to the Keccak designers saying that the padding change isn't nefarious. You have to be able to do better than "NIST bad" in comments on threads like these.
  - aliqot 4y ago
    From Daniel J. Bernstein: 2022.08.05: NSA, NIST, and post-quantum cryptography: Announcing my second lawsuit against the U.S. government. : https://blog.cr.yp.to/20220805-nsa.html https://blog.cr.yp.to/20220805-nsa.html https://twitter.com/hashbreaker/status/1555625577989541888 https://twitter.com/hashbreaker/status/1555625577989541888

flatiron 4y ago

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

tialaramex 4y ago
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...
- green_on_black 4y ago
  It seems that some memory safety bug in C/C++ makes HN frontpage every other day.
tinglymintyfrsh 4y ago
Not the same, but there are multiple implementations. Here's the top one with 13 M downloads. https://crates.io/crates/sha3 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.
drexlspivey 4y ago
what do you mean? the sha3 crate is 8 years old

brundolf 4y ago

> The vulnerable code was released in January 2011, so it took well over a decade for this vulnerability to be found Ouch

galangalalgol 4y ago
Between this and "beacown" I came to a realization. I work on codebases worth way less than these amd we do lots of different static analyzers two compilers, lots of unit tests with coverage checks and asan/ubsan. The linux kernel and sha are worth tons of money. Thus, someone wrote all the pipelines and unit tests for that software too. The problem is, the people who paid for all that work aren't the people that rely on thos software's security. It's paid for by people that rely on it's insecurity. So we don't know about this stuff until they or the people they sold it too use these exploits. Edit: in case the solution I propose isn't obvious, organizations like red hatand google need to pay for these pipelines and unit tests. Getting good unit test coverage is expensive and ubsan and asan don't work without that coverage. So since no one has mentioned it yet, you could rewrite this stuff in rust as a poor man's substitute. It will catch some of the aame things, but ultimately there is no substitute for test coverage with sanitizers. Well, maybe formal analysis?
- lmm 4y ago
  > So since no one has mentioned it yet, you could rewrite this stuff in rust as a poor man's substitute. It will catch some of the aame things, but ultimately there is no substitute for test coverage with sanitizers. That's backwards. You'll catch more cases with a Rust-style type system that naturally checks everything, than with sanitisers that can only check the paths that get executed in tests.
  - galangalalgol 4y ago
    Rust isn't perfect. UB is a bug in rust, but it occasionally has bugs. Ideally you'd do rust and asan with good unit tests. And yes, if you only picked one, it should be rust, but don't just pick one. And just because you are using rust is no excuse to skip static analysis like prusti, coverage with gcov, llvm, or tarpaulin, and certainly not unit tests.

bobkazamakis 4y ago

https://www.xilinx.com/products/intellectual-property/1-1mjenql.html https://www.xilinx.com/products/intellectual-property/1-1mje... https://documentation-service.arm.com/static/62bb3e4bb334256d9ea8d26f https://documentation-service.arm.com/static/62bb3e4bb334256...

tinglymintyfrsh 4y ago

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

tinglymintyfrsh 4y ago
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) => #<Digest::SHA3: 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7> [2] pry(main)> h.update("\x00") => #<Digest::SHA3: bdd5167212d2dc69665f5a8875ab87f23d5ce7849132f56371a19096> [3] pry(main)> h.update("\x00"*4294967295) => #<Digest::SHA3: c5bcc3bc73b5ef45e91d2d7c70b64f196fac08eee4e4acf6e6571ebe> [4] pry(main)> h.hexdigest => "c5bcc3bc73b5ef45e91d2d7c70b64f196fac08eee4e4acf6e6571ebe" [5] pry(main)>

ouid 4y ago

What dows generating preimages mean here? The preimage is the set of all messages that hash to some set of hashes. Is the author saying the the hash function is reversible in reasonable time?

SAI_Peregrinus 4y ago
It's a buffer overflow. They can get a vulnerable implementation to execute arbitrary code, so they can get it to return any value they want. The actual SHA-3 algorithm wouldn't return the same value as the vulnerable implementation, of course.
- enedil 4y ago
  I didn't see anybody mention arbitrary code execution
  - NicolaiS 4y ago
    It's in the post: a specially constructed file can result in arbitrary code execution

bvrmn 4y ago

It looks pretty difficult to exploit. Untrusted 4GB input with non-chunked update.

nequo 4y ago
The purpose of running SHA is to determine whether the input can be trusted though. But it is true that relatively few files circulate at or above that size.
- thayne 4y ago
  And even if they are, you probably aren't going to do a digest on the whole thing all at once.
  - kevincox 4y ago
    IDK, I see a lot of "non-production" code that likes to read whole files into a in-memory buffer rather than bothering with streaming. With modern memory sizes it is completely possible that you could read a 4GiB file into memory without having issues.
    - Too 4y ago
      Thinking about it, it's strange that hashlib doesn't have a function that accepts a file-object as input, to make the efficient method default pit of success. Naive implementations like hash(f.read()) are all too common to see. Such an api would also allow the entirety of the tight loop to be done outside of slow interpreted code. Guessing the rationale is that if you read a file, you also want to use the content for something else, not only compute its hash.
mike_d 4y ago
4+ GB inputs are often fed to hashing functions. Verifying the integrity of file downloads before running them for example.
- 4y ago

Ptchd 4y ago

Does Tor use SHA-3?

jbaczuk 4y ago

no bounty and still politely reports it. Good guys need more praise.

baby 4y ago
it's a public standard, who would pay such a bounty?
- mhh__ 4y ago
  Someone who values security with real money
- morepork 4y ago
  I'm sorry, we lost millions of dollars due to an exploit. Don't you have bug bounties to find and fix these things? But this was in a public standard that we were using, we don't cover those. Do I look like I care?
  - baby 4y ago
    Are you telling me this? Or are you going to pay a bounty?
- amenghra 4y ago
  A couple companies sponsor “the internet bug bounty”: https://www.hackerone.com/internet-bug-bounty https://www.hackerone.com/internet-bug-bounty IMHO, sha3 should be part of that bounty.
deleted 4y ago
[deleted]

throwaway81523 4y ago

Didn't they find a vulnerability like this in the official MD5 implementation when they tried to port it to SPARK/Ada and the proofs didn't work? I wasn't able to just find it with web search, but here's a release about something similar happening with another one of the SHA3 candidates (Skein), before Keccak was chosen: https://www.adacore.com/press/spark-skein https://www.adacore.com/press/spark-skein See also: https://www.adacore.com/papers/sparkskein https://www.adacore.com/papers/sparkskein

deleted 4y ago
[deleted]

all_these_years 4y ago

SHA-3 in Ruby: $ gem install sha3 $ irb > require 'sha3' > s = SHA3::Digest::SHA224.new > s.update("\x00") > s.update("\x00" * 4294967295) [ Segmentation fault... ] Tested with Ruby 3.1.2 Gem's code (including C native extension): https://github.com/johanns/sha3 https://github.com/johanns/sha3

abraham 4y ago
Just over half a million total downloads. So some use but not particularly popular.
deleted 4y ago
[deleted]
johannsg 4y ago
Released a fix earlier today (Oct 23rd) (v1.0.5)

Donckele 4y ago

“I’ve also shown how a specially constructed file can result in arbitrary code execution, ” Ouch, thats not looking good for a reference implementation for a piece of software deployed on billions and billions of machines that was written by experts and reviewed (and modified) by even bigger egg heads.

hot_gril 4y ago
At least it's not SHA-2, which is probably more widely used. Or am I mixing them up?
- turminal 4y ago
  You are correct, SHA-2 is much more prevalent.
manholio 4y ago
Just another nail in the long overdue C/C++ coffin. If not even these experts can get it right, under the best development conditions, public review and highest stakes, on a relatively small component with the most strict specifications, then no one can.
- adev_ 4y ago
  > Just another nail in the long overdue C/C++ coffin C, f**ing C. By the sake of god. Not C++. Stop to put both in the same basket, it just show you do not know what you are talking about. https://github.com/XKCP/XKCP/commit/fdc6fef075f4e81d6b1bc38364248975e08e340a https://github.com/XKCP/XKCP/commit/fdc6fef075f4e81d6b1bc383... Something like that in modern C++ would have been done using std::span<> and that prevents this kind of out-of-bound access and the party-time that comes with it.
  - saagarjha 4y ago
    C++ offers safer constructs but they have their own sharp edges and you have to actually use them to get their benefits. In security critical software these can still be enough to cause significant problems.

yieldcrv 4y ago

Bro what? This is a big deal right? Like NSO Group hacking everyone for the next 5 years deal?

raydiatian 4y ago
> The vulnerable code was released in January 2011, so it took well over a decade for this vulnerability to be found. It would have already been a big deal for the past five years, if anything. Furthermore you have to induce a bufferoverflow first. I’m no security researcher, but to my mind that means you’re either (a) trusting idiots to write sensitive code without a IT Sec team reviewing it, or (b) you’ve got a malicious actor on the inside, who can slip it past review. I’m sure there are plenty of other scenarios, but I’m saying it doesn’t feel likely by gut.
- UncleMeat 4y ago
  Absolutely not. Buffer overruns aren’t something that only idiots introduce.

hasa 4y ago

It may be dumb question, but is there any realistic use case to use this vulnerability to reveal SHA-3 hashed secrets? Or is it just that attacker can crash systems with suitable input?

6LLvveMx2koXfwn 4y ago
From the article: I’ve shown how this vulnerability in XKCP can be used to violate the cryptographic properties of the hash function to create preimages, second preimages, and collisions. Moreover, I’ve also shown how a specially constructed file can result in arbitrary code execution, and the vulnerability can also impact signature verification algorithms such as Ed448 that require the use of SHA-3. The details of these attacks will be made public at a later date.

deleted 4y ago

[deleted]

adunsulag 4y ago

FYI in the healthcare space to meet ONC Cures Update regulations for bulk patient export, its a requirement to use SHA384 (RS384 or ES384). I would think most implementations will be safe due to the 4GB payload criteria, but if anyone is doing anything funky they'll need to look at this closely.

jakobdabo 4y ago
SHA-384 is a hash function from the SHA-2 family, and it has no relation to SHA-3.