How I Hacked Hacker News (with arc security advisory) | Hacker News

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.
The 'rand' function is an arc primitive, bound directly to mzscheme's 'random':
This is the C function which implements mzscheme's 'random' function:
Where does the RNG seed come from? Ah ha:
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:
A couple months ago, PG left this comment after news.yc recovered from some downtime:
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:
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:
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.
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:
Like Pandora, he is so curious, he has to check this out.
Like a rat in a maze, he keeps going looking for the clear path.
Like Sherlock Holmes, he applies logic to determine the next step.
Like General Sherman, he keeps marching, building tools along the way as he needs them.
Like William Randolph Hearst, he defines the landscape. ("You provide the pictures, I'll provide the war.") "so I decided on a more proactive approach: crash it!" (hilarious)
And like any parent, he didn't quit until his baby walked.
Thank you, Daniel. I sure hope you've found a way to channel that talent in your day job.
I knew from previous discussions with you that you did work at this level, but this is the first time I had actually seen for myself. It read almost like a mystery and I found myself guessing what you'd do next. So I thought I'd pay a quick tribute with what came into my mind first.
AFAIC, you don't need a proposal or resume any more. Just email any prospect or prospective employer this link. If they don't see what you can do from this, you probably don't want to work for them anyway.
Slight error, Pandora was a female in greek mythology (well, the first female to be more precise)
Pandora was the wife of Prometheus (the Titan of Knowledge) who made all the animals and humanity (last of all and out of the only material he had left - clay). In order to give them life, he stole fire from the gods and gave it to his creations, for which he was bitterly punised. In one telling he was tied to a mountain and his heart/liver was eaten by an eagle/vulture and grew back every day. HOWEVER, in another telling, his punishment was PANDORA and her famous box.... I just always found that interesting, vivisection every day for eternity, or a curious wife... fine lines =P
EDIT - just looked it up, it was incorrectly translated by Erasmus of Rotterdam when he first translated Hesiod's tale into Latin from Greek.
That hack was damned impressive for breadth and depth of knowledge, pretty rare in my experience.
This should be ex