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
So, I went looking for the code that does the randomizing. It’s at the bottom and looks like:
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.
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 @)
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.
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:
As expected, the pattern holds up if we add a “Dummy” to the end of the list:
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).
This is a Security Bloggers Network syndicated blog post authored by Patrick Thomas. Read the original post at: Coffee To Code