Sort()ing out a Nerdsnipe

First, a disclaimer: this is really stupid stuff, and basically the opposite of work worth doing. But still, I got nerdsniped and the resulting rabbit hole went somewhere interesting, so I figured I’d write it up.

Update 10/2: Someone else got bit by the same bug. @swisshttp took a deeper dive, into the implementation details of different scripting engines. https://swisshttp.blogspot.ch/2016/10/latacora-riddle.html


The new security startup Latacora uses a small piece of javascript to randomize the names of the founders in the first paragraph. It seems like a reasonable & egalitarian thing to do, but after idly hitting F5 a few times (like you do…) I noticed that it’s not really random.

latacora_home

So, I went looking for the code that does the randomizing. It’s at the bottom and looks like:

original_javascript

Now, these are the same folks who put together the Matasano Crypto challenges and Starfighters.io, so something like that would not at all be out of the realm of possibility. And, whether intentional or not (hey, I said this whole rabbit hole was dumb), if test it (Gist)we find that the results are anything but random.

test-code

test-results

So, what gives? Is it in the call(s) to Math.random as the comment teases, or elsewhere? The code is really simple looking. Now, we hold as an article of faith that you cannot trust Javascript’s Math.random() (thanks @ropnop for the pointer), but there doesn’t seem to be any funny business with the seed or anything that might suggest actually messing with the generator. Plus, we’re not looking for a small bias, we’re looking for something really significant.

Could the issue be in the anonymous function passed to sort? Nope, not really. It correctly fulfills the contract expected by a custom sort function (return negative, 0, or positive number based on intended ordering of the compared values) , and the body of the function does what it says (implies) on the tin: returns each of those values close-enough-to-randomly, regardless of input.

Could it be something weird in the use of “ceil” to integerize the random number? That could create a small bias given the domain of Math.random, but again we’re looking for something that causes a huge bias.

Spoilers below – if you want to reason through this yourself, go ahead and do it, then come back.

No, the actual cause is both more subtle and more interesting. It’s actually in interaction of the implementation of Array.sort and the anonymous compare function. Several things are going on here:

  • the sort implementation (either quicksort or insertion sort in Chrome – I’m assuming insertion sort for an array this small and based on the observed behavior below ) assumes that the custom sort function passed into it does a sane comparison
  • the sort implementation moves left to right through the array
  • each comparison between two elements has 3 possible values (-1, 0, 1)
  • the sort operation is unstable (edit: this operation is stable. I misinterpreted the docs and how stability interacts with the random comparator. Thanks @fzzfzzfzzz)

So, there is no “correct” ordering of the array: the sorting algorithm isn’t checking to ensure that compares have a transitive property (nor should it). The result is not so much a true “sort” as a series of probabilistic changes of position.

I refactored the code a little bit to do a poor-man’s implementation of instrumenting the sort function (Gist). Here are three runs of it. Notice that that the only way Erin *doesn’t* get bumped is if she “loses” the first compare. A “win” (compare result of -1) does not result in a swap because of the intent of the sort function, and a “tie” (compare result of 0) is never rechecked because the sort implementation does not guarantee a stable result.

instrumented_sort

In effect: Someone starting in a given position has (1/3)^n chance of being bumped “n” positions in the array.

So, that explains why Erin gets to be first more often than expected, and why Thomas gets to be second. Here’s the breakdown of that math:

test-results

(1/3)^1 = .33333 ~= % of time Erin is bumped to position 1
(1/3)^2 = .11111 ~= % of time Erin is bumped to position 2

As expected, the pattern holds up if we add a “Dummy” to the end of the list:

test-results-with4

(1/3)^3 = .037 ~= % of time Erin is bumped to position 3

 


So… there you have it. It’s a (probably unintended) nerdsnipe that nonetheless took us into some interesting territory. Hope you had fun. Did I miss something or explain it wrong? Lemme know in the comments or on twitter (@coffeetocode).

2 Responses to “Sort()ing out a Nerdsnipe”

  1. Ed McCardell Says:

    Back in 2010, Microsoft had the same issue — using randomness in the sort comparator — with its Windows Browser Ballot for the EU. Ars Technica had a write-up:

    http://arstechnica.com/information-technology/2010/03/coding-error-leads-to-uneven-eu-browser-ballot-distribution/

  2. Sort()ing out a Nerdsnipe – sec.uno Says:

    […] Security Bloggers Network @ October 2, 2016 at […]

Leave a Reply