Security Review Summary of NIST SHA-3 Round 1 146
FormOfActionBanana writes "The security firm Fortify Software has undertaken an automated code review of the NIST SHA-3 round 1 contestants (previously Slashdotted) reference implementations. After a followup audit, the team is now reporting summary results. According to the blog entry, 'This just emphasizes what we already knew about C, even the most careful, security conscious developer messes up memory management.' Of particular interest, Professor Ron Rivest's (the "R" in RSA) MD6 team has already corrected a buffer overflow pointed out by the Fortify review. Bruce Schneier's Skein, also previously Slashdotted, came through defect-free."
ANSI C (Score:5, Insightful)
That is what they get for mandating the code be in ANSI C. How about allowing reference implementation in SPARK, ADA or something else using design-by-contract. After all, isn't something as critical as a international standard for a hash function the type of software d-b-c was meant for?
The reason is in the summary... (Score:5, Insightful)
Re:ANSI C (Score:1, Insightful)
Ummmm... because it wouldn't be a reference implementation if it wasn't actually implemented?
Re:ANSI C (Score:5, Insightful)
Presumably one of the things they want to evaluate is performance.
Re:ANSI C (Score:5, Insightful)
Because you can't compile a mathematical definition.
If we imagine that the hash function came only as a mathematical definition, how would your test your new implementation in LangOfTheWeek is correct?
Well, you have 2 options. One, you can prove that your program behaves, in every important way, the same as the definition. This is long, tedious work, and most programmers don't even have the necessary skills for this. Two, you can make a reference implemention in some other language, and compare the outputs.
Now, given, say, 100 programmers each working on their own functions, we should have 1 resulting behaviour. This will mean that everybody implemented the algorithm 100% correctly. However, the actual number will be between 1 and 100, depending on the skills of the programmers, and the care they've taken in implementing the functions.
Now, what's the result here? (no pun intended). It's likely to be chaos.
That's why it's very convenient to have a single reference source.
Re:ANSI C (Score:5, Insightful)
What did they get? You realize this is just an ad for Fortify, right? Out of 42 projects, they found 5 with memory management issues using their tool. Maybe instead of switching to SPARK, the 5 teams that fucked up could ask the 37 that didn't for some tips on how to write correct C.
Hardly "memory management" (Score:4, Insightful)
This doesn't follow from TFA. The blog points out two instances of buffer overflows. The first one you could argue they messed up "memory management" because they used the wrong bounds for their array in several places... but they don't sound very "careful" or "security conscious" since checking to make sure you understand the bounds of the array you're using is pretty basic.
But that's not what bothered me. The second example is a typo where TFA says someone entered a "3" instead of a "2". In what dimension is mis-typing something "messing up memory management"? That just doesn't follow.
Re:ANSI C (Score:3, Insightful)
An implementation in a programming language is the a way to define a function mathematically.
That is what a programming language is - a way to precisely define an algorithm.
But C is a low-level language, and therefore maybe a bad choice for function definitions. Instead, in my experience, implementing an algorithm in a high-level functional language like Haskell will often result in a beautiful and readable mathematical function definition.
Re:ANSI C (Score:5, Insightful)
That is what they get for mandating the code be in ANSI C.
Because most of the systems out there use C for the performance sensitive bits. (and when asm optimization is done, people generally use a C implementation as a reference since C and asm are similar in many ways).
When they start doing Linux and Windows and other popular systems primarily in Ada you can start going WTF over people posting ANSI C code. Until Java, Ruby and Python aren't dependent on C/C++ implementations for their functionality we'll just have to suffer with C.
In defense of C (Score:5, Insightful)
Buffer overflows are not hard to avoid, they are just something that must be tested. If you don't test, you are going to make a mistake, but they are easy to find with a careful test plan or an automated tool. Apparently those authors who had buffer overflows in their code didn't really check for them.
C is just a tool, like any other, and it has tradeoffs. The fact that you are going to have to check for buffer overflows is just something you have to add to the final estimate of how long your project will take. But C gives you other advantages that make up for it. Best tool for the job, etc.
C isn't the problem, it is really... (Score:4, Insightful)
I suspect the problem is related to the poor coding practices used in academia. I see college professors who write code that barely compiles in GCC without a bunch of warnings about anachronistic syntax. Some of the C code used constructs that are unrecognizable to someone who learned the language within the past 10 years, and is completely type unsafe.
I can't tell much from the code on the link, but I do see #define used for constants which is no longer appropriate (yet is EXTREMELY common to see). C99 had the const keyword in it, probably even before that.
Re:ANSI C (Score:3, Insightful)
That is what they get for mandating the code be in ANSI C. How about allowing reference implementation in SPARK, ADA or something else using design-by-contract. After all, isn't something as critical as a international standard for a hash function the type of software d-b-c was meant for?
C is the lowest common denominator. Once you have a library in C that's compiled to native code, you can link just about any other language to that library: Perl, Python, Ruby, Java, Lisp, etc., all have foreign function interfaces to C.
C also can compile to just about any processor out there: x86, SPARC, POWER, ARM, etc. Over the decades it's become very portable and optimized.
C is also know by a large subset of the programmers out there, so if people want to re-write the algorithm in another language, they can start with the C code directly, or with the formal specification and then use the C as a comparative reference.
Re:C isn't the problem, it is really... (Score:2, Insightful)
I suspect the problem is related to the poor coding practices used in academia. I see college professors who write code that barely compiles in GCC without a bunch of warnings about anachronistic syntax.
You know you'll learn a lot in a class when, after being told at the very least his c++ code is using deprecated includes, the professor tells you to just use '-Wno-deprecated'. I've basically come to the conclusion that I am just paying the school for a piece of paper, and I will learn little outside my personal study.
dandelion orchard (Score:3, Insightful)
I know nothing of the sort. How about asking some developers who have a history of getting both the security and the memory management correct which intellectual challenge they lose the most sleep over?
The OpenBSD team has a history of strength in both areas. I suspect most of these developers would laugh out loud at the intellectual challenge of the memory management required to implement a hash function. It's about a hundred thousand lines of code short of where the OpenBSD team gets grey hair over memory management problems in the C language.
I was just having an intense conversation about restrictive land covenants with my GF. If the economic cycle tips downward, the covenant holder (often a not-for-profit manila file folder which is legally distinct from the insolvent main entity) ceases to afford regular maintenance. Suddenly it turns into a dandelion orchard, and everyone in the community is dead certain that every dandelion on every lawn originated from this single source, whereupon some soon to be re-elected politico harpoons the legal infrastructure that permitted these things to flourish in the first place.
"What we know about C" and "what we know about dandelions" are surprisingly equivalent.
I wouldn't hire a programmer who can't get memory management right to take on any significant intellectual challenge. It's just a way to feel good about yourself without having the aptitude to cut your way out of a wet paper bag.
90% of software development projects are not aptitude driven. Let's stop fooling ourselves into thinking that the languages that work well in those contexts having anything to offer those of us dealing with the other 10%
Memory management is a subcase of resource management with a particularly harsh way of delivering the news: you suck. A memory managed language deprives the environment of so many golden opportunities to deliver this message, despite the fact that you still suck. By the time you don't suck, you've ceased to regard unmanaged memory as a core intellectual challenge, and trained yourself to work within an idiom where you hardly ever get it wrong anyway.
The C string functions that cause the worst of the grief were widely known to be a bad idea by the mid 1980s. They originated a point in history where linking sprintf() was sometimes considered a luxury you couldn't afford. In the microcontroller world, it's still common that an environment provides three different versions of printf/sprintf: basic, basic plus more of the format options and maybe long integers, and then the full version which also includes floating point. The middle option is the beer budget. The first option is for when you can't even afford beer. These micros are not so different that the mini-computers on which C and Unix were originally created.
Furthermore the efficiency of the string functions tends to ripple outward, as they tend to carry the torch for the platform's memory subsystem performance in most C code bases. What do the Z80, 6809, and 8086 all have in common? Instruction set tweaks to make zipping along a string of bytes a lot zippier.
These tricks are then rolled into vendor optimized string libraries and made available to the developer via the ratified ANSI C string functions.
It's unfortunate that all this industry of tweaking toward core performance was consolidated under a string API whose modern legacy is to have informed so many programmers that "you suck" that the general sentiment is to vote it off the island, as if such a thing is possible with a cockroach or a rat or dandelion dandruff.
Re:In defense of C (Score:4, Insightful)
Buffer overflows are not hard to avoid, they are just something that must be tested.
No, they're a huge pain in the ass 99% of the time, what's worst is that pointers work even when they absolutely shouldn't. I recently worked with some code that instead of making a copy of the data just kept a void pointer to it instead. Since that code was passed just a temporary variable that was gone right after being passed into it, it should error out on any sane system, but the problem is it worked - when it was called later, using the pointer to a temp that's alreday gone it would just read the value out of unallocated memory anyway, and since the temp hadn't been overwritten it worked! Only reason it came up was that when called twice it'd show the last data twice, since both would be pointing to the same unallocated memory location. It's so WTF that you can't believe it. Personally I prefer to work with some sort of system (Java, C#, C++/Qt, anything) that'll give you some head's up that will tell you're out of bounds or otherwise just pointing at nothing.
Re:uhh, lint... (Score:1, Insightful)
Lint isn't magic.
Re:ANSI C (Score:4, Insightful)
After all, isn't something as critical as a international standard for a hash function the type of software d-b-c was meant for?
No.
The key desirable characteristics of a good secure hash function are (in this order):
If the NIST AES contest is any example, what we'll find is that nearly all of the functions will be secure. That's not surprising since all of the creators are serious cryptographers well-versed in the known methods of attacking hash functions, so unless a new attack comes out during the contest, all of the functions will be resistant to all known attack methods.
With security out of the way, the most important criterion that will be used to choose the winner is performance. This means that every team putting forth a candidate will want to make it as fast as possible, but it still has to run on a few different kinds of machines. The closer you get to the machine, the faster you can make your code -- and this kind of code consists of lots of tight loops where every cycle counts. But assembler isn't an option because it needs to run on different machines.
That leaves C as the best choice. It's the portable assembler.
Re:dandelion orchard (Score:3, Insightful)
What I get out of this:
"We're going to give you more shit to think about by making you use C. if you can't deal with all the stupid shit C throws at you, you suck."
Which is a shit argument. Just use a better language that gives people less to worry about, and develop from there. Having to debug the shit out of a program for obscure memory management issues shouldn't be a test of your competence. You should be able to focus on the task at hand, nothing else.
Re:ANSI C (Score:3, Insightful)
C is a bad choice for mathematical function definitions, but it's a fantastic choice for integrating into virtually any stage of a software project. It can be used in an OS kernel, a standard portable crypto library (e.g. OpenSSL), embedded firmware, what have you. All of this with NO more library dependencies than the bare minimum memory management, and most crypto/hash functions don't need those because their state fits in a fixed-size structure. So you can have the mythical 100% standalone C code that fits in any context.
Implementing the algorithm in C from the start also makes it easy to port to C-like languages like Java and C#.
Re:this is why... (Score:4, Insightful)
If you're still writing unmanaged code, you get what you deserve. It's 2009, not 1989.
Try running managed code in the 4 MB RAM of a widely deployed handheld computer. Now try making that managed code time-competitive and space-competitive with an equivalent program in C++ compiled to a native binary.