How I Hacked Hacker News (with arc security advisory)

[Condensed version of this narrative: the news.yc code, prior to the the release of arc3, contains a remotely-exploitable vulnerability permitting account theft. Anyone running a news installation who has not yet upgraded to arc3 should do so.]

Hacker News login cookies are random eight-character strings, stored server-side in a hash table mapping them to user names. I discovered a few weeks ago that these strings were rather less random than they were meant to be, and, through a delightful combination of exploits, could be predicted, enabling an attacker to steal accounts.

Here's the rand-string function from arc.arc, version 2. It gets called with n=8 to generate login cookies, and n=10 for the "fnids" that get used all over the site as hash keys identifying closures.

  (def rand-string (n)
    (with (cap (fn () (+ 65 (rand 26)))
           sm  (fn () (+ 97 (rand 26)))
           dig (fn () (+ 48 (rand 10))))
      (coerce (map [coerce _ 'char]
                   (cons (rand-choice (cap) (sm))
                         (n-of (- n 1) (rand-choice (cap) (sm) (dig)))))
              'string)))

The first thing you might notice about this function is that not all characters are equally probable. Each digit has a 1/30 chance of occuring, while each letter has a 1/78 chance. This alone is no big deal: this distribution means that each character carries 5.826 bits of entropy, versus the 5.954 that a uniform distribution would provide. So for an eight-character string, this bug reduces the effective keyspace by just over a factor of two -- not enough to have any practical implications.

The 'rand' function is an arc primitive, bound directly to mzscheme's 'random':

  ; need to use a better seed
  (xdef 'rand random)

The comment seen here is prescient, as we'll see.

This is the C function which implements mzscheme's 'random' function:

  static long sch_int_rand(long n, Scheme_Random_State *rs)
  {
    double  x, q, qn, xq;

    /* generate result in {0..n-1} using the rejection method */
    q  = (double)( (unsigned long)(m1 / (double)n) );
    qn = q * n;
    do {
      x = mrg32k3a(rs);
    } while (x >= qn);
    xq = x / q;

    /* return result */
    return (long)xq;
  }

Where mrg32k3a() is:

  static double mrg32k3a(Scheme_Random_State *s) { /*(double), in {0..m1-1}*/
    double x10, x20, y;
    long   k10, k20;

    /* component 1 */
    x10  = a12*(s->x11) - a13n*(s->x12);
    k10  = (long)(x10 / m1);
    x10 -= k10 * m1;
    if (x10 < 0.0)
      x10 += m1;
    s->x12 = s->x11;
    s->x11 = s->x10;
    s->x10 = x10;

    /* component 2 */
    x20  = a21*(s->x20) - a23n*(s->x22);
    k20  = (long)(x20 / m2);
    x20 -= k20 * m2;
    if (x20 < 0.0)
      x20 += m2;
    s->x22 = s->x21;
    s->x21 = s->x20;
    s->x20 = x20;

    /* combination of component */
    y = x10 - x20;
    if (y < 0.0)
      y += m1;
    return y;
  }

This, obviously, is not a cryptographically strong PRNG. Is it possible that we could break it, computing its internal state by seeing a few consecutively-generated rand-strings? Probably: it looks as though it could be represented as the solution to a manageable system of diophantine equations. That, though, was more math than I felt like doing, so I went looking for an easier approach.

Where does the RNG seed come from? Ah ha:

  rs = scheme_make_random_state(scheme_get_milliseconds());

Where scheme_get_milliseconds is defined, after eliding some preprocessor cruft, as:

  long scheme_get_milliseconds(void)
  {
    struct timeb now;
    ftime(&now);
    return now.time * 1000 + now.millitm;
  }

In other words, the random seed is merely the number of milliseconds since epoch at the time the seed function was called.

The part of mzscheme that calls the seed function is a bit daunting: it appears that in some cases, the PRNG state can be thread-loca...