Live data from Hacker News

A Vulnerability in Implementations of SHA-3, Shake, EdDSA

eprint.iacr.org

11–20 of 49 posts

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#11

Is this due to stupidity or malice? I just can’t get my head round the idea that software written and reviewed by experts and submitted to the “National Institute of Standards and Technology” with a budget of 1 billion dollars can fuck up this way. I’m no mathematician but I would have thought implementing pure number crunching code is not rocket science. Buffer overflow, overwrite memory, run arbitrary code, serious…

> Buffer overflow, overwrite memory, run arbitrary code, seriously? LOL, WTF.

Do you think everything (arguably anything) is released flawless?

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#12

Is this due to stupidity or malice? I just can’t get my head round the idea that software written and reviewed by experts and submitted to the “National Institute of Standards and Technology” with a budget of 1 billion dollars can fuck up this way. I’m no mathematician but I would have thought implementing pure number crunching code is not rocket science. Buffer overflow, overwrite memory, run arbitrary code, serious…

Nobody with any experience would laugh at mistakes like this. It's only easy in hindsight. Past 30+ years of collective experience in our industry shows that these classes of bugs are nearly impossible to completely stamp out in any language but especially in memory unsafe ones, even with dramatically better compile time and runtime tools that can spot many of these nowadays. During the early days of the internet and the buffer overflow attacks after Morris worm, buffer overflow bugs existed in practically all software. There were times when pretty much any servers connected to the internet could be had relatively easily.

Even with memory safe languages, there are dangers. Humanity just hasn't figured out how to produce completely bug-free code at the scale we need in general, let alone in a memory-unsafe language.

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#13
post #9

> partialBlock = (unsigned int)(dataByteLen - i); The paper makes no mention of compiler warnings… but shouldn’t this cast trigger a compiler warning?

There is a mode of UBSan that would catch it, but I don't think you could run it on SHA code because that uses unsigned overflow for the hash. Basically, this is why you shouldn't use unsigned types unless you explicitly want them to overflow.

This is rather sad that one must give up the range and add the signed range just to avoid overflow bugs. Is there no way to make overflow not the default and instead trap unless one uses `add_wrap()` or `add_no_wrap()` in case it's not default?

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#14
post #13
post #9

Earlier quoted context omitted.

There is a mode of UBSan that would catch it, but I don't think you could run it on SHA code because that uses unsigned overflow for the hash. Basically, this is why you shouldn't use unsigned types unless you explicitly want them to overflow.

This is rather sad that one must give up the range and add the signed range just to avoid overflow bugs. Is there no way to make overflow not the default and instead trap unless one uses `add_wrap()` or `add_no_wrap()` in case it's not default?

There is overflow-checking math in GCC/Clang and standardized in C23, but I'm not sure if there's anything opt-out. If there is, I don't know how to write it.

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#15
post #8

This is over 4 months old, and is already patched in Python. Was discussed on HN at the time: https://news.ycombinator.com/item?id=33281106

What about PHP?

Yes, fixed in all (at the time) supported versions in October last year [0].

[0]: https://github.com/php/php-src/commit/248f647

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#16

Is this due to stupidity or malice? I just can’t get my head round the idea that software written and reviewed by experts and submitted to the “National Institute of Standards and Technology” with a budget of 1 billion dollars can fuck up this way. I’m no mathematician but I would have thought implementing pure number crunching code is not rocket science. Buffer overflow, overwrite memory, run arbitrary code, serious…

Nobody with any experience would laugh at mistakes like this. It's only easy in hindsight. Past 30+ years of collective experience in our industry shows that these classes of bugs are nearly impossible to completely stamp out in any language but especially in memory unsafe ones, even with dramatically better compile time and runtime tools that can spot many of these nowadays. During the early days of the internet and…

This particular mistake is all the more infuriating because it comes from a precaution. Or trying to silence a compiler warning:

  partialBlock = (unsigned int)(dataByteLen - i);
Where both `dataByteLen` and `i` where actually `size_t`.

Assuming this is close enough to C, what happens is that we're converting a difference between `size_t` into a mere `unsigned`, and since they're not the same sizes on 64-bit platforms this can give `partialBlock` the wrong value, and the whole thing then snowballs into a catastrophic error that is not trivial to test because it only happens with huge buffer sizes.

The biggest mistake here is having written `(unsigned int)` instead of `(size_t)`. But the reason it happened in the first place is because they tried to do the right thing: writing the cast as a precaution, even though the following would have worked:

  partialBlock = dataByteLen - i;
I really can't fault them: because it was a difference it could theoretically yield a "negative" result, and therefore intuitively the type of a difference should be signed, so we should cast it back to unsigned to be crystal clear. I knew C was dangerous, but to be honest I didn't expect such a wicked mind game.

Now I'm going to have to take a look at my code.

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#17

Earlier quoted context omitted.

Nobody with any experience would laugh at mistakes like this. It's only easy in hindsight. Past 30+ years of collective experience in our industry shows that these classes of bugs are nearly impossible to completely stamp out in any language but especially in memory unsafe ones, even with dramatically better compile time and runtime tools that can spot many of these nowadays. During the early days of the internet and…

This particular mistake is all the more infuriating because it comes from a precaution . Or trying to silence a compiler warning: partialBlock = (unsigned int)(dataByteLen - i); Where both `dataByteLen` and `i` where actually `size_t`. Assuming this is close enough to C, what happens is that we're converting a difference between `size_t` into a mere `unsigned`, and since they're not the same sizes on 64-bit platforms…

umm... But how (uint - uint) can be negative? I thought it would warp around 0 into (UINT_MAX - leftovers).

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#18
post #17

Earlier quoted context omitted.

This particular mistake is all the more infuriating because it comes from a precaution . Or trying to silence a compiler warning: partialBlock = (unsigned int)(dataByteLen - i); Where both `dataByteLen` and `i` where actually `size_t`. Assuming this is close enough to C, what happens is that we're converting a difference between `size_t` into a mere `unsigned`, and since they're not the same sizes on 64-bit platforms…

umm... But how (uint - uint) can be negative? I thought it would warp around 0 into (UINT_MAX - leftovers).

You're right, it cannot, and does wrap around.

But some people might think that it could, so putting the cast could increase readability for them. A similar reasoning applies with operator precedence: even though it's very well defined, we tend to forget it, so instead we put additional parentheses. But in a couple specific cases it hurts more than it helps.

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#19
post #2

I didn't read the whole paper, but how can this even happen? Seems like the buffer overflow would be triggered for any file larger than 4 GiB, which I assume someone has tested in the 8 years since it was released.

You'd be surprised how many of those submitted and approved crypto standards are still not tested with industry best practices.

buffer overflows or integer UB's and overflows are very common. ubsan, asan, valgrind tests are missing. some do offer symbolic verification of the algo, but not the implementations.

See my https://github.com/rurban/smhasher#crypto paragraph, and "Finding Bugs in Cryptographic Hash Function Implementations", Nicky Mouha, Mohammad S Raunak, D. Richard Kuhn, and Raghu Kacker, 2017. https://eprint.iacr.org/2017/891.pdf

Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA

#20
I wonder if this could be avoided by writing the canonical implementations in Rust or better yet in some system with formal verification.

This is such a critical part of the software stack, that we need a more reliable way of validation than just a bunch of people staring at the code written in C.

Post reply on HN