Crypto hash boffins trip on buffer overflow

@Vendicar Decarian

"This is hardly surprising. C is one of the worst computer languages ever created. Conceived by morons, implemented by incompetents and loved by sicophants."

::snort::

This is a really bad attempt at trolling, an/or the author is absolutely clueless.

Hang on, the name rings a bell ... ::hits metacrawler:: ... Oh. It's you.

Hi, Scott! Bye, Scott. :-)

buffer overflows - why?

I'm not sure whether these guys were working under time pressure (we can all make mistakes when pushed for time). We should, however, remember that their primary expertise is mathematical and logical analysis. Programming is probably secondary to what they really do. It would be unfair to accuse an architect for slightly wonky bricklaying. However I do believe we no longer have much real control over the code of our programs. Ultimately, a program is a set of machine code instructions that the machine follows blindly in some sequence, but we have largely lost this connection with the machine.

When I started microsystems development we used raw machine code, assembler and possibly C, multi-threading was an arcane concept and the machine instruction execution sequence was almost entirely under the control of the programmer. Now we mostly link together often massively complex black box library modules written by vendors, run hugely parallel (even if merely time sliced) multi-thread processes and execute on CPUs capable of predictive out-of-order machine instruction execution. The result is almost no control over the exact run-time process.

Buffer overflows can be written in by inattentive programmers even when coding at low level. They can also occur due to [a] calling a proprietary library module that contains a potential buffer overflow the programmer does not know about; [b] race conditions between threads or even possibly triggered by CPU execution order decisions. So testing becomes more important, but the very complexity of code bloated by massively redundant "do everything" library methods makes exhaustive testing impossible, so we're back to square one. And worse, as programmers are now almost exclusively trained to use solely highly abstracted languages, it's likely that buffer overflows and their causes will become less and less well understood. Expect buffer overflows (and integer overflows, and divide by zeros, and typing mismatches and null pointers, ...). They may be 35 years old, but they're still hale and hearty.

@Vendicar Decarian

C was conceived by very brilliant people, implementation quality is generally very high (when was the last time *you* wrote a compiler?) and it is loved by anybody who has the need (and ability) to write fast, accurate code.

It is 40 years old and the earliest implementations were macro passes in assemblers. Back then you may have had only 2 choices, C or assembler. Many programs were written in a mixture of both. C is not designed to be used by children, the careless or the hard of thinking.

Do people make mistakes? Of course they do. That’s why a sensible manager insists on doing Design/Code Reviews. That’s what Fortify have done and they've caught a couple of mistakes. Well done them.

Actually, I dunno what is worse ...

What is worse? Me responding to a known troll, or so-called "security" researchers not asking for help when programming in a low-level language they aren't genetically familiar with?

Mea culpa :-)

"current hash standards such as MD4, MD5, and SHA-0"

MD4 and MD5 haven't been "current" for some time (though MD5 keeps popping up like a bad penny) and SHA-0 was replaced by SHA-1 in 1995.

mathematical soundness != implementation flaws...

.. and C is fine if properly tested / debugged.

Re: C = Worst programming language...bla bla

C is beautiful. You just don't understand it.

You probably use something like Java or (heaven forbid) Perl - you know - runs like a dog, is massively bloated, needs huge gobs of memory to run, etc etc.

If it wasn't for C, you wouldn't have most of the electronic stuff you take for granted - from your washing machine and heating timer up to the PC you sent your post from. You have NO idea just how important C is.

Another vote for the maligned Corvair

Biggest problem with the Corvair was the driver/owner. No one was used to checking oil levels in air cooled engines, and no one paid attention to fan belts. You could get away with this in a 1964 Buick, but a 1964 Corvair needed more attention.

Driven by anyone with any automotive sense at all, the Corvair was actually a pretty nice car for the time. Economical, easy to steer, decent ride, surprisingly good handling. Corvair even had some good results in racing - look up "Yenko Stinger" on Google.

What killed the car was a combination of a certain ambitious liberal lawyer (who boasted that he didn't even have a driver's license!) and GM's arrogance and poor damage control after said lawyer made his name by attacking one of the very few almost-decent GM cars of the day.

I have personally met Ralph Nader - he's an asshole of the first order and a total publicity whore. We ought to wrap him up (duct tape would be good) and give him to North Korea or Iran as a Christmas present, even out of season if necessary. Drop him from 40,000 feet - he won't even need a parachute!

@Ed: Digital signature collisions

Try the interweb, say <http://en.wikipedia.org/wiki/Digital_signature>. Look for 'collision'.

Unless you're trolling too.

C Does Suck

The problem is C generally requires you to reinvent the wheel for all sorts of basic plumbing. Memory management, for one. It's like "to create a shower, first dig up some copper ore..."

I programmed in C for years, and I tolerated it for what it is, a high level assembler.

C gives you a lot of power, yes. It's compact, yes. But it has virtually no checking, no basic services, and most programmers disable the few things like boundry-checks C compilers do have in the name of the gods Speed and Compactness.

When nearly every variable assignment you do has the potential to overflow a buffer, when every memory allocation has the potential to create a memory leak, when every pointer has the ability to point *anywhere*, then you have a mess.

C requires a great deal of care to get the mind-numbingly simple things right. Over and over and over. It isn't that C itself is bad, it's that C does nothing for the programmer, the programmer has to do *everything*. The slightest flaw and you have a compromised system. This is a good thing?

C is still necessary in limited areas where the power truly is needed. Low level OS functions, for example. Stuff that A) isn't very large, B) needs to be absolutely as fast as possible.

C is not suited for large complex projects precisely because of the exponential chance of making a basic mistake. (And I know lots of large programs are in C--which is why buffer overflows are so damned common).

How about using a language that does memory management, with an interpreter or compiler that knows how to optimize to the bare metal? It's a lot easier for a specialist to create a solution everyone can use, right? That's the whole *point* of code reuse...

(no title)

It's true that it's mathematically impossible to have a hash function that can map a string m to a hash value n where m can be longer than n. Naturally, for the same reason a hashing algorithm cannot compress every possible file. If the algorithm can compress an arbitrary, it is possible to construct a file that would be made bigger by such compression.

"However, the point still remains that for any given signature there are a number of possible inputs that will produce it. I refer to my earlier mathematical proof. Of course, for a good crytographic algorithm, it will be hard to work out the corresponding inputs for any given output. That is the reason they are also known as one-way functions. Nonetheless, those multiple input values do exist, and no algorithm that can be devised can change this fact."

Nothing you said is false. But I can just as easily say that for any given AES key, it's possible for someone to randomly guess the value and decrypt your encrypted files. The statement holds just as much meaning. The idea is to make decryption (or in the case of SHA-3, being able to spoof a message with a valid hash for the message being replaced) computationally infeasible. The weakest SHA-3 variant, assuming there are no design/implementation weaknesses (I know, I know, but bear with me) should have a collision attack complexity of 2^128 (that being accomplished through a birthday attack, which does very little in actually helping you spoof a given document). The others would should have complexities of 2^256 and 2^512.

tl;dr the concept of a collision-free general purpose hash is flawed to begin with, but that's no different than the concept of a "secret" key.

@Steven Usher - C language

I would suggest to you that you might not have done that much programming in a variety of languages.

I've been programming since 1982. The C language is particularly dangerous and certainly more dangerous than most other programming languages out there.

It's use of pointers is the problem.

Bounds checking of arrays is not carried out. And when it comes to using pointers to access a block of memory, then there can't be any checking done.

Most other languages bounds check arrays.

In fact, take a look at the number of books on the market that talk about "Safer C programming" and show me another language where there such a similar book market exists.

It's even possible to go on training courses to learn how to defensively program in C to avoid the blunders.

QED.

@AC Hash Algorithms

"It's true that it's mathematically impossible to have a hash function that can map a string m to a hash value n where m can be longer than n. "

I'm not sure if that is really what you intended but it is wrong. It's the other way around.

If the input to the hash function is m and the output is n, then the output n must be equal to or less than the size of m ( in length of characters).

The whole point of the hash function is to create a 'signature' value which is much smaller in size than the input.

Digital Signature collisions

"Over the past few years, a growing body of research has revealed those algorithms can be vulnerable to so-called "collisions," in which two separate data files generate the same digital signature."

What is this, a joke? I was writing software for my A' level computer science project that was making use of hash functions ( but they weren't even called that in those days) back in 1987 that used hash functions and we were aware even then of the issues of multiple input values mapping to a single output value, and there were techniques back in those days that had been devised to deal with it.

It's something that's been known about for more than 20 years.

@Wolf

Now this guy Wolf is absolutely right. It's quite evident he has programmed in C for a good number of years ( as have I). In my case, military applications running on micro-controllers with 1536 bytes of RAM and 32B of ROM space (among other apps).

@Wolf

> How about using a language that does memory management, with an interpreter or compiler that knows how to optimize to the bare metal? It's a lot easier for a specialist to create a solution everyone can use, right? That's the whole *point* of code reuse..

We've been using the same home grown C utility libraries for more than 10 years. They are thoroughly debugged, run in every O/S and hardware combination we've tried them on (even Windows) with little on no modification and are very *very* fast. Certainly faster than those in the standard libraries. [At least with C (and C++) you can override the built-ins and use your own.]

That *is* the point of code reuse. If you aren't still using code you wrote 10 years ago then you need better code and better local procedures.

Ed - Hash Algoritms

"The algorithm in use is irrelevant to whether collisions can occur, it is simply a case of the number of permutations possible in the data size used to represent a signature."

Of course the particular hash algorithm is important, otherwise what would be the point of devising so many different ones, other than for intellectual curiousity.

It's to do with the distribution of those numbers in the output set. If the size of your output space is 2048 numbers, you don't want bunching up of the numbers, you don't want 80% of the collisions from the input numbers to be mapped to 10% of the output space.

'Mathematical Proof'

" I refer to my earlier mathematical proof."

Can we please ditch the use of this phrase, which was used by AC and subsequently by others. There was no mathematical proof provided, what there was a simple expression, which was actually incorrect anyway.

@@rota

> I did state that it's mathematically impossible to map a set onto a smaller set without collisions

Depends entirely on the entropy of the larger set.

But then we all know what we're talking about, not really disagreeing on anything but quibbling over trivia then taking it personally. We wouldn't converse like this if we were face-to-face in a pub, so why here? (assuming any of us would talk tech in a pub - I really hope not)

Hashes in general collide. We all know it and the consequences/resolution. End of story.

eh?

"Depends entirely on the entropy of the larger set."

Let's try a fun experiment. Grab 4 balls. Get 3 boxes. Now place every ball in a box, without putting more than 1 ball in any given box.

Now explain how the generic set of m items mapped onto a set of n items is any different.

But you're right, this is really just quibbling and not germane to the article (any fule kno cryptographic hashes collide, the game is more complicated than that). It's just irritating being told you're wrong by someone who is actually wrong, with them not even bothering to try and justify their statement.