Schnee (schnee) wrote,

2013 Underhanded C Contest

The 2013 Underhanded C Contest has wrapped up. Be sure to read up on the challenge before checking out the results so you know what it was about; alternatively here's an executive summary:

There were over 40 submissions this last year, which was a lot to judge (especially since some submitters do not provide any hints about their bugs!) It also resulted in a lot of really great hacks, too many to simply list as a few runners up. This summary is considerably longer than in previous years.

As you will remember (click the "THIS YEAR" tab if you don’t,) the object of the 2013 Underhanded C contest was to write a function to compute the DERPCON — Degrees of Edge-Reachable Personal CONnection — between two users in a social network. Essentially the programming task is to find the shortest distance between two users in a friendship graph.

The malicious goal is to write the code so that it mistakenly outputs a low DERPCON value from your account to others, granting you unwarranted access to people who have not "friended" you. Extra points were awarded for asymmetric bugs, meaning that DERPCON(you,me)==1 while DERPCON(me,you)>1; for bugs that can be triggered without insider access to the database; bugs that are relatively platform-independent; bugs that are spiteful or humorous; and of course bugs that are very well hidden, since the name of the game is creating an error that passes visual inspection of source.

It's all worth reading, especially if you're a C programmer (which I'm not). To me personally, this particular bit stood out, BTW:

[...] Mr Leurent’s submission also uses a bad hash that can output INT_MIN with the right username, but this is exploited differently. The hash is as follows:

#define HASHSIZE 151       // 151 is a prime number


// FNV hash:
int hash (user *x) {
  int h = x->user_ID;
  for (char *p = x->name; *p; p++) {
    h = 16777619 * (h^*p); // FNV prime

  // Reduce safely in [0..HASHSIZE-1]
  h = abs(h) % HASHSIZE;
  // Extra sanity check
  if (h < 0 || h >= HASHSIZE)
    h = 0;
  return h;

Note the use of a legit hash function, at first. But if h comes out as INT_MIN, then taking abs(h)%HASHSIZE results in -2. This is hidden rather well by the extra sanity check to double-ensure that the hash is in range. How does the -2 get past that final sanity check? Because the compiler removes that check as redundant, since h is already an absolute value modulo HASHSIZE. Ha!

This, in a nutshell, is why we'll never have programs without security holes as long as C is around: compiler programmers aren't just allowed to cheat by the spec, they're doing it on purpose, for the sake of performance, so long as they can claim that they stick to the letter of the law even while violating its spirit. And that's where the letter of the law isn't already "you may do whatever you want".

Worse yet, compiler programmers will take mutually incompatible positions at the same time, positions that, while each following the letter of the law when viewed in isolation, are nonetheless inconsistent with each other, thus inevitably leading to disastrous results in the real world.

The above is a great example. abs(INT_MIN) is undefined; apparently it's customary to have it be a negative number. (An absolute value, negative? Just let that sink in for a moment.) Modulo arithmetic preserves the sign, so h in the above code can in fact be negative. Yet in the next step the same compiler programmers that just said "we'll make h be negative, since the C standard allows us to do this" also say, in essence, "it's an absolute value, it cannot possibly be negative", and use that as a justification for removing the check that safeguards against their own shenanigans — all under the guise of "optimization".

And THAT is really why C cannot possibly be made secure. It's not just unspecified behavior; it's the fact that compiler programmers are actively working to make code insecure.

(Note: I'm saying "compiler programmers" rather than "compilers" on purpose, BTW, since I want to make it absolutely clear that these are all intentional choices made by human beings, rather than a program just so happening to act in a certain unfortunate way.)

EDIT, 2017-02-25: fixed links (contest moved to a new site).

Tags: c, programming languages, security
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded