[Donckele]

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, seriously? LOL, WTF.

[drivebycomment]

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.

[loup-vaillant]

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.

[junon]

> since they're not the same sizes on 64-bit platforms

Not guaranteed, but they certainly can be.

[IYasha]

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

[loup-vaillant]

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.

[nayuki]

So, (unsigned int) - (unsigned int) → (unsigned int) is guaranteed on every platform.

But relevant to the bad SHA-3 code, the resulting type of size_t - size_t can be surprising. First, size_t is not guaranteed to have any relation with unsigned int; it could be narrower, the same, or wider. For example, size_t could map to unsigned short, unsigned int, unsigned long, or unsigned long long.

If size_t is defined as unsigned short (note that size_t must be at least 16 bits), and short is 16 bits wide, and int is 32 bits wide, then the calculation of size_t - size_t will be promoted to (signed int) - (signed int), and thus the result will have the type signed int.

[jongjong]

Agreed, people wildly underestimate how difficult it is to produce correct code. I think if people adopted the mindset that it's impossible, we'd be closer to the truth. Some of these important projects should only hire genius-level developers who code at a max speed of 1 line per day. Every line of code should be added with an unfathomable degree of thoughtfulness and care. I wish I was joking, but I'm not.

Shipping a non-trivial program which has more than a few thousand lines of code borders on impossible.

[GoblinSlayer]

Buffer overflow in hash function is unprecedented, buffering simply doesn't work this way, it was figured out long ago and never changed. Smells like bullrun to me.

[red_admiral]

I'm going with "neither".

It's true that Snowden revealed the NSA had their fingers in NIST's cryptographic standards team, with Dual-EC a specific example that is considered suspicious since the revelations. So a suspicion of malice is not completely unfounded, but as far as I can tell, this code was written by the Keccak team not NIST itself, and for any claim of "they're NSA stooges", I would need evidence.

It also seems to me that the Keccak team are not stupid people. That leaves "honest mistake" as the most likely explanation.

There are lots of studies on human behaviour that show a competent and diligent human will mess up every Nth time they perform a routine task; some forms of probabilistic risk analysis take N = 10^3 as a lower bound for this.

There is a long history of railroad operation in the UK (who invented the steam train after all) where occasionally, a signaller would send an express onto a line where they'd forgotten that the local was standing, or two trains head-on down a single line in opposite directions. This led to the development of interlockings and token working systems as technological solutions to mitigate the risks of human error, and later on to today's computerised safety systems, because signallers are (almost always) neither stupid nor malicious, but still human. The same can be said for programmers.

(As I understand, the recent train disaster in Greece was on a line where there should have been interlocking in place, but it wasn't active.)

[bilekas]

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

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