• Posts
  • RSS
  • ◂◂RSS
  • Contact

  • Nomic Game 2: Another Conclusion

    February 5th, 2019
    nomic  [html]
    This morning Chelsea won our second game of Nomic with a timing attack:

    Our game was set to use random numbers to figure out if someone had won. Effectively, each point you earn should give you an additional 1/100000th chance of winning. The source of randomness was python's random.random(), which was fine.

    I had written a PR (#98) to move us to using something derived from the hash of the most recent merge commit on master. I was intending for this to be a timing attack: the merge commit should be predictable entirely from its contents and the current time.

    The idea is, I can test for each upcoming timestamp whether there's hash that would end on me winning. A very hacky way to get git to think it's in the future is just to set your local clock fast:

    CURTIME=$(date +%s) ;
      sudo date -s '@1549031338' &&
        git merge tmp-branch
          -m "$MESSAGE" &&
      sudo date -s '@'$CURTIME

    Unfortunately, when I tested trying to exploit this I found that GitHub signs the merge commits it makes. For example:

    $ git cat-file commit 182b57a9b53fc31febd9166fc03f3d91e368b64e
    tree 04d5ff9335c297c203f4ee4cb5a14006bfa6abb9
    parent 0c08b506c96d42d4ad8fab5c2c1701d557aa3a97
    parent 6fc74cf39d7d79e8500ef4c4162decd64b82e8be
    author Todd Nelling  1549324096 -0500
    committer GitHub  1549324096 -0500
    gpgsig -----BEGIN PGP SIGNATURE-----
     -----END PGP SIGNATURE-----
    Merge pull request #99 from pavellishin/more_verbose_rule_names
    Be more vocal about which rule is being run

    This meant there was some information in the hash that I couldn't control, and this wasn't going to work.

    At this point the smart thing to do would have been to delete the PR: if I know it's dodgy but I can't exploit it then I shouldn't let anyone else take that opportunity! But instead I figured "I guess it's safe, then -- nice to have reproducible random numbers" and went to bed.

    The next morning I saw that Chelsea had won, and was suprised by the winning commit:

    $ git cat-file commit 0003490f8179527499e1b0739fec6d1ac22662f3
    tree cc61bc798249f7dbf4d12d139f9c9e3134efa87a
    parent 182b57a9b53fc31febd9166fc03f3d91e368b64e
    parent 1d6c32eea2556acd67c0b4e193bb4e2639bb487b
    author Chelsea Voss  1549380160 -0800
    committer Chelsea Voss  1549380160 -0800
    Merge pull request #98 from jeffkaufman/consistent-random
    start using reproducible random numbers

    No signature! Chelsea had noticed that GitHub allows making a local merge and then pushing that up. You can generate a local merge commit for an PR with an appropriate hash by tweaking the timestamp git reads (or waiting for exactly the right time) and then push the merge commit up when you're ready (her summary).

    So Chelsea prepared a vulnerable local commit, approved the PR with a cheeky message, and pushed it up. GitHub accepted the merge, Travis calculated a random number of 0.00005 which was in Chelsea's win-range, and we had a winner!

    It turns out, however, that a merge commit pushed from the command line isn't checked very thoroughly, and this on its own would have been enough to win. For example, I created a PR (#103) that docked myself a point, which is allowed to be merged without additional approval as a points transfer. Then, once Travis passed it, I merged it from the command line with:

    $ git checkout master
    $ git merge --no-ff testing-more-local-merges
    $ echo 100000 > players/jeffkaufman/bonuses/tons-of-points
    $ git add players/jeffkaufman/bonuses/tons-of-points
    $ git commit -a --amend
    $ git show ae3c5a0
    commit ae3c5a01195c351f13d1ae9415e3c7412b92cddb
    Merge: 5494d8e 1f73044
    Author: Jeff Kaufman 
    Date:   Tue Feb 5 17:20:42 2019 +0000
        Merge branch 'testing-more-local-merges'
    diff --cc players/jeffkaufman/bonuses/tons-of-points
    index 0000000,0000000..f7393e8
    new file mode 100644
    --- /dev/null
    +++ b/players/jeffkaufman/bonuses/tons-of-points
    @@@ -1,0 -1,0 +1,1 @@@
    You can see that this let me include extra changes in my merge commit that gave me 100,000 points. Even though the extra change wasn't in the PR that github ran tests on, I could still push the merge commit up:

    $ git push
    Counting objects: 6, done.
    Delta compression using up to 2 threads.
    Compressing objects: 100% (4/4), done.
    Writing objects: 100% (6/6), 497 bytes | 0 bytes/s, done.
    Total 6 (delta 3), reused 0 (delta 0)
    remote: Resolving deltas: 100% (3/3), completed with 3 local objects.
    To git@github.com:jeffkaufman/nomic.git
       5494d8e..ae3c5a0  master -> master

    Which made Travis call me a winner, though I'm not since Chelsea had already won:

    Possibly this is a bug in how protected branches are handled?

    (One prerequisite for this PR was that my previous PR (#97) switched us to only calling random() once and gave players "win ranges". That one was also sneaky and initially would always make player #2, me, win. Pavel noticed this, though, and I needed to update it (96d8ba).)

    Comment via: facebook, lesswrong

    Recent posts on blogs I like:

    Governance in Rich Liberal American Cities

    Matt Yglesias has a blog post called Make Blue America Great Again, about governance in rich liberal states like New York and California. He talks about various good government issues, and he pays a lot of attention specifically to TransitMatters and our …

    via Pedestrian Observations November 19, 2020

    Collections: Why Military History?

    This week, I want to talk about the discipline of military history: what it is, why it is important and how I see my own place within it. This is going to be a bit of an unusual collections post as it is less about the past itself and more about how we st…

    via A Collection of Unmitigated Pedantry November 13, 2020

    Misalignment and misuse: whose values are manifest?

    Crossposted from world spirit sock puppet. AI related disasters are often categorized as involving misaligned AI, or misuse, or accident. Where: misuse means the bad outcomes were wanted by the people involved, misalignment means the bad outcomes were wan…

    via Meteuphoric November 13, 2020

    more     (via openring)

  • Posts
  • RSS
  • ◂◂RSS
  • Contact