How I Hacked Hacker News (with arc security advisory)

928 points

17 years ago

[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-local and be initialized when the thread is spawned. However, instrumenting sch_int_rand() with some debug output showed that in arc, the same state vector gets used everywhere, and is initialized when the mzscheme runtime starts up.

The millisecond at which news.yc last started is not an immediately simple thing to determine, though it was at least easy to verify the sanity of the system clock, thanks to an open NTP serevr:

  dfranke@feanor:~$ sudo ntpdate -q news.ycombinator.com
  server 174.132.225.106, stratum 2, offset 0.370866, delay 0.08228
  17 May 01:45:13 ntpdate[27901]: adjust time server 174.132.225.106 offset 0.370866 sec

So for a start, I thought, perhaps I could determine the server's start time to within a few seconds or minutes. A boring way to go about this would be simply to monitor the server for downtime, and record when it became accessible again. But impatience is one of the three great programmer's virtues, and the best way to predict the future is to create it, and so forth, so I decided on a more proactive approach: crash it!

A couple months ago, PG left this comment after news.yc recovered from some downtime:

  HN was down today for around 2 hours. Sorry about that.

  The News server currently crashes a couple times a day when it runs
  out of memory. All the comments and stories no longer fit in the 2 GB
  we can get on a 32 bit machine. We'd been planning to upgrade to a new
  64 bit server. In the meantime it was arguably a rather slow form of
  GC.

  Unfortunately the process somehow got wedged in the middle of
  segfaulting. We're not sure why and will probably never know. But that
  meant the process that usually notices when News is wedged and
  restarts it was unable to kill it.

(The server had since been upgraded, so these crashes are/were no longer happening.)

I figured that the watchdog works by requesting a page and checking to make sure it gets a response, and that if it doesn't get one, then it assumes the server is wedged and restarts it.

Here's arc2's top-level request handler:

  (= srvthreads* nil threadlimit* 50 threadlife* 30)

  ; Could auto-throttle ips, e.g. if one has more than x% of recent requests.
  (= requests* 0 requests/ip* (table) throttle-ips* (table) throttle-time* 30)

  (def handle-request (s (o life threadlife*))
    (if (len< (pull dead srvthreads*) threadlimit*)
        (let (i o ip) (socket-accept s)
          (++ requests*)
          (= (requests/ip* ip) (+ 1 (or (requests/ip* ip) 0)))
          (let th (thread 
                    (if (throttle-ips* ip) (sleep (rand throttle-time*)))
                    (handle-request-thread i o ip))
            (push th srvthreads*)
            (thread (sleep life)
                    (unless (dead th) (prn "srv thread took too long"))
                    (break-thread th)
                    (close i o))))
        (sleep .2)))

So, there's a limit of 50 concurrent threads, and threads are killed after 30 seconds if they haven't already terminated. So if I were to hold open 50 concurrent connections, and the watchdog were to run during the following 30 seconds, then the server ought to restart.

The watchdog code has not been released, so rather than soil my hat color by DoSing the production server, I decided to continue hacking on my local install on the assumption that I had the ability to determine the server's start time to within one minute.

So, a one-minute interval is 60,000 possible PRNG seeds. If I kept polling to see when the server came back up after the watchdog killed it, then let's very conservatively assume that I could be among the first 50 people to issue an HTTP request. Each page that comes back from the server typically contains 2-3 fnids, so the reply I got would contain some from among first few hundred to be generated, and thus from among the first few thousand iterations of of the PRNG.

This leaves determination of the PRNG seed comfortably within the reach of brute force: run the PRNG for 10,000 iterations for each of the 60,000 possible seeds, and see which one produces the fnids I saw in response to my request. I wrote a program that does just this:

  http://dfranke.us/hacknews.c

So now I was able to determine PRNG seeds, but I couldn't conclude my adventure quite yet. Since logging into news.yc is an uncommon operation compared to simply browsing around, only a tiny fraction of rand-strings that the server generates correspond to login cookies. Furthermore, since fnids and login cookies have different lengths, and since the PRNG gets called for a few other purposes at unpredictable times, every individual PRNG iteration begins a candidate login cookie. That's 40 or more false candidates produced for every page view.

Nonetheless, online brute force would still be manageable. If each page view produces an average of 50 candidates, and one in every thousand page views is a login (this might be slightly optimistic), that's 50,000 attempts necessary in order to find a working login. HN gets about 500,000 hits on a busy day, so this could be done in a day or two while likely staying under the radar.

A marginally more efficient approach would be a bit of social engineering:

1. Request a page. Find a generated fnid from the page source and look it up in our candidate list. Call this A.

2. ERC> /join #startups <dfranke> Hey guys, I haven't been able to log in to news.yc since the server restarted a little while ago. Anyone else having problems? <jrandomsucker> dfranke: Works for me. <dfranke> Hmm, weird. I'll just try again later I guess.

3. Request another page, note the fnid, find it in the candidate list. Call this B.

Step 4: Test the cookies that fall between A and B.

If this conversation takes one minute, then this reduces the search to about 17,500 attempts -- less than a day's worth at a modest rate of querying -- and possibly picks up multiple accounts in the process.

Epilogue:

I sent PG a draft of this post. RTM and I wrote a better implementation of rand-string which reads from /dev/urandom and obeys a proper uniform distribution. This new version appears in arc3:

  (def rand-string (n)
    (let c "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
      (with (nc 62 s (newstring n) i 0)
        (w/infile str "/dev/urandom"
          (while (< i n)
            (let x (readb str)
               (unless (> x 247)
                 (= (s i) (c (mod x nc)))
                 (++ i)))))
        s)))

PG removed the 50-thread concurrency limit and replaced it with a per-IP rate limiter, so the DoS attack described here should no longer work.

78 comments

(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)))

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; }

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; }

dfranke@feanor:~$ sudo ntpdate -q news.ycombinator.com server 174.132.225.106, stratum 2, offset 0.370866, delay 0.08228 17 May 01:45:13 ntpdate[27901]: adjust time server 174.132.225.106 offset 0.370866 sec

HN was down today for around 2 hours. Sorry about that. The News server currently crashes a couple times a day when it runs out of memory. All the comments and stories no longer fit in the 2 GB we can get on a 32 bit machine. We'd been planning to upgrade to a new 64 bit server. In the meantime it was arguably a rather slow form of GC. Unfortunately the process somehow got wedged in the middle of segfaulting. We're not sure why and will probably never know. But that meant the process that usually notices when News is wedged and restarts it was unable to kill it.

(= srvthreads* nil threadlimit* 50 threadlife* 30) ; Could auto-throttle ips, e.g. if one has more than x% of recent requests. (= requests* 0 requests/ip* (table) throttle-ips* (table) throttle-time* 30) (def handle-request (s (o life threadlife*)) (if (len< (pull dead srvthreads*) threadlimit*) (let (i o ip) (socket-accept s) (++ requests*) (= (requests/ip* ip) (+ 1 (or (requests/ip* ip) 0))) (let th (thread (if (throttle-ips* ip) (sleep (rand throttle-time*))) (handle-request-thread i o ip)) (push th srvthreads*) (thread (sleep life) (unless (dead th) (prn "srv thread took too long")) (break-thread th) (close i o)))) (sleep .2)))

(def rand-string (n) (let c "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" (with (nc 62 s (newstring n) i 0) (w/infile str "/dev/urandom" (while (< i n) (let x (readb str) (unless (> x 247) (= (s i) (c (mod x nc))) (++ i))))) s)))