New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

@csvoss wins! #100

Closed
jeffkaufman opened this Issue Feb 5, 2019 · 37 comments

Comments

Projects
None yet
4 participants
@jeffkaufman
Copy link
Owner

jeffkaufman commented Feb 5, 2019

screenshot_20190205-103340

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

I wrote #98 as a timing attack, but then I found that github signs merge button commits:

$ git cat-file commit 182b57a9b53fc31febd9166fc03f3d91e368b64e
tree 04d5ff9335c297c203f4ee4cb5a14006bfa6abb9
parent 0c08b506c96d42d4ad8fab5c2c1701d557aa3a97
parent 6fc74cf39d7d79e8500ef4c4162decd64b82e8be
author Todd Nelling <tnelling@gmail.com> 1549324096 -0500
committer GitHub <noreply@github.com> 1549324096 -0500
gpgsig -----BEGIN PGP SIGNATURE-----

 wsBcBAABCAAQBQJcWM9ACRBK7hj4Ov3rIwAAdHIIAHJ8riEtIRdzPc8lrm6lVFaN
 WvgfntWG2SyokzgiTHmMT1GQvcN6imNMi6TOfo0dWp81OamRqlbg01DXLlVhjIdy
 U23aAtERdYo3UwLNcAss/slRPUFdhQlOd7A2WqapPfjSbVZD3g1SRzjBgDyH1Tfd
 FcuI2X9+nezBRxYd3Un5p//JwdEdu9bBFMIOT7UARMsgbsOmTiQlAUpKc0mrR3yc
 y/8jli7e4sIv29+v3k5w4+DKTwfjL3WHu1WLmEtpkQWz/0Aw/N/oX/CcUgH0foVl
 CDNON4aT+bih4F+saymjJJuM3cdxJAy9MD7BjtPGEDyqHvgpgF4rNyWFgRvF4Ms=
 =2G6+
 -----END PGP SIGNATURE-----


Merge pull request #99 from pavellishin/more_verbose_rule_names

Be more vocal about which rule is being run

Somehow @csvoss seems to have avoided this:

git cat-file commit 0003490f8179527499e1b0739fec6d1ac22662f3
tree cc61bc798249f7dbf4d12d139f9c9e3134efa87a
parent 182b57a9b53fc31febd9166fc03f3d91e368b64e
parent 1d6c32eea2556acd67c0b4e193bb4e2639bb487b
author Chelsea Voss <voss.chelsea@gmail.com> 1549380160 -0800
committer Chelsea Voss <voss.chelsea@gmail.com> 1549380160 -0800

Merge pull request #98 from jeffkaufman/consistent-random

start using reproducible random numbers
@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

Can you accomplish that by not merging though GitHub? I thought the repo was set to only allow merging through GitHub.

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

Right, this looks like a regular merge-locally-and-push? But if you can do that you can just push anything...

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

I know I can do that, because I'm a repo admin, but I thought no one else could? @tnelling do you want to try pushing an arbitrary commit onto master?

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

Well if you can do it that's problematic enough, I suppose.

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

Sure, but me doing it is out of bounds

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

Like, if I won because of something only I could do as a repo admin that would be cheating.

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

I don't know if that was specified earlier, but I'm glad you agree.

I cannot push directly to master with a commit, but maybe I could merge an approved PR into master?

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

Or @csvoss could enlighten us

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

It probably would have been wiser if after realizing I couldn't exploit this bug I'd revoked the PR. It was overconfident of me to think that just because I couldn't figure out how to keep GitHub from signing my merge commits no one else would!

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

I wonder if it's different if you merge something via the API?

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

Which you probably want to do anyway if you want to hit an exact timestamp.

@csvoss

This comment has been minimized.

Copy link
Contributor

csvoss commented Feb 5, 2019

Ah whoops, I missed this discussion and posted in #98. Moving my comment here.

@csvoss

This comment has been minimized.

Copy link
Contributor

csvoss commented Feb 5, 2019

Yeah! Some pieces:

  1. It turns out that git commit timestamps store to-the-second resolution instead of to-the-millisecond resolution. As @jeffkaufman mentions, this means that in theory, a person could precompute out what the hashes of different merge timestamps will be, and then hit the GitHub "Merge pull request" button at just the right second for it to have the right hash. This is especially possible if one has, say, been submitting many pull requests and perhaps measuring the latency from button-click to GitHub merge commit. When I started reading this PR I was concerned Jeff might well have data on that already.

  2. However! Git signs the commits. This does make predicting the hashes impossible.

  3. But! Pull requests can apparently be merged from the command line (apparently I never do this in real life?), and GitHub displays instructions for how to do so if you click into "view command line instructions":

screen shot 2019-02-05 at 12 33 18 am

This means that I can manufacture my own merge commit locally, with no need to sign it, and then push it up to GitHub once Travis CI has passed on this pull request. This is quite luxurious compared to hitting the button at the right time, too!

Given this, @zbenjamin and I paired on a script to calculate which timestamps in the next twelve hours or so would yield sufficiently low hash values for me, for some given merge commit (with fixed commit message). We used git cat-file and git hash-object to investigate what variables affect the values of merge commit hashes (similarly to what Jeff cites upthread). There were maybe 5 such timestamps available since last night.

One tangle: If you create a merge commit locally, you actually get a merge commit message that says (1) "Merged branch whatever into so-and-so" instead of (2) "Merged pull request #number from person/whatever" like we usually see. I figured it was more in the spirit of the rule against "Editing the text of a merge commit when merging the PR" for me to edit the locally-created merge commit message to match the usual GitHub-created merge commit message, given that we have some code that matches on (2) by regex. Up to you all whether this is a valid interpretation :) I could have successfully chosen an adversarial timestamp given either choice of commit message.

(edited to tag @zbenjamin too)

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

If you can run the merge locally, what prevents you from editing the actual contents of the PR?

@csvoss

This comment has been minimized.

Copy link
Contributor

csvoss commented Feb 5, 2019

I am pretty curious whether this merge-on-command-line thing is something that GitHub has special handling for – on the one hand I'd seen previous pull requests be merged in by non-authors, but on the other hand I assumed we have blocked push access to master, and if so there must be some special permission handling that happens. I wasn't 100% sure whether this strategy was going to pan out for me until I actually got to the point where I ran git push and could see if it succeeded or not.

@csvoss

This comment has been minimized.

Copy link
Contributor

csvoss commented Feb 5, 2019

If you can run the merge locally, what prevents you from editing the actual contents of the PR?

Hopefully something! This seems worthy of more experimentation.

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

Any collaborator can push the merge button in the GitHub UI once a PR has approval. I don't know what differentiates that from any other kind of git push behind the scenes.

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

If you can run the merge locally, what prevents you from editing the actual contents of the PR?

Hopefully something! This seems worthy of more experimentation.

Hmm. If we wanted to play again I'd be okay with just ruling local merging out-of-bounds if we can't find a way to restrict it or a guarantee that it's locked down against such shenanigans. I can at least confirm that I can't just push commits into master, so I think to experiment we'd need to approve a dummy PR.

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

To experiment you can make a dummy PR that just docks yourself a point. That won't need review from anyone else.

@pavellishin

This comment has been minimized.

Copy link
Collaborator

pavellishin commented Feb 5, 2019

Awesome. I figured this would happen, but I figured @jeffkaufman would be the one to get a win from this :P

If we wanted to play again I'd be okay with just ruling local merging out-of-bounds if we can't find a way to restrict it or a guarantee that it's locked down against such shenanigans.

I would rather not add more "soft rules" about what is and isn't out of bounds; I'd rather solve it with code. (If there's a setting that we can toggle in Github to prevent this particular shenanigan, I'd be fine with that.)

But given that we've demonstrated that hashes aren't truly random, I'm not sure what a good solution would be.

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

I mean #98 isn't actually needed. My justification for it was pretty weak, and I just did it to set up the timing attack.

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

I actually think we do need something like #98, or at least we will once scores get bigger, particularly if one person has a big lead. The particulars of the implementation aren't important, but only having one score check per repository state has value.

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

Local merging does need to be out of bounds, though, if it turns out you can "resolve merge conflicts" locally to merge arbitrary things.

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

If we wanted to play again I'd be okay with just ruling local merging out-of-bounds if we can't find a way to restrict it or a guarantee that it's locked down against such shenanigans.

I would rather not add more "soft rules" about what is and isn't out of bounds; I'd rather solve it with code. (If there's a setting that we can toggle in Github to prevent this particular shenanigan, I'd be fine with that.)

But given that we've demonstrated that hashes aren't truly random, I'm not sure what a good solution would be.

Local merging does need to be out of bounds, though, if it turns out you can "resolve merge conflicts" locally to merge arbitrary things.

I agree with both of you, I just don't know if we have a reliable way to implement a solution in code or the repo settings.

@pavellishin

This comment has been minimized.

Copy link
Collaborator

pavellishin commented Feb 5, 2019

I also agree with the two previous commenters; any suggestions on another source of reproducible randomness? I was thinking of using the previous master commit, or some combination of the last two, but given that there are conditions that let people merge without approval, there's no reasonable way to do that :/

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

Turns out local merging is vulnerable: I checked the "Include administrators: Enforce all configured restrictions for administrators." box and verified that I couldn't push arbitrary commits anymore. Then I made #103 which gave me -1 point, and merged it as ae3c5a0 which gives me a ton of points.

I did:

$ 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 <jeff@jefftk.com>
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 @@@
++100000
$ 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

Bingo!

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

@csvoss once you thought of local merging you had everything you needed to win without #98 ;)

@pavellishin

This comment has been minimized.

Copy link
Collaborator

pavellishin commented Feb 5, 2019

Ok - so if we disallow local merges, we can continue using the master hash as the source of reproducible randomness, right?

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

@pavellishin I think so, unless there are other exploits we don't know about...

@tnelling commit signing isn't required, but also wouldn't help with either of these exploits. For the timing attack you could just keep generating merge commits until one had an acceptable hash, and for the merge commit attack signing doesn't prevent you from having resolved imaginary merge commits.

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

I was thinking that we could use signing to only allow merging through use of the GitHub UI.

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

@tnelling all that enforces is that commits need to be signed, but I can sign locally.

@tnelling

This comment has been minimized.

Copy link
Collaborator

tnelling commented Feb 5, 2019

I understand that you can sign locally, but I was hoping that we could combine signing with restrictions on commits to master in the GitHub settings to get the desired result. Perhaps there is no relevant configuration option, but if we could restrict the repo to only accept commits to master with GitHub's signature (the one that it attaches automatically to commits using the web interface per https://help.github.com/articles/about-commit-signature-verification/), then I think that would get us what we want.

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

I don't see an option to only allow github-signed commits

@jeffkaufman jeffkaufman referenced this issue Feb 5, 2019

Closed

Play again? #105

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

opened #105 for discussion about whether to play again

@jeffkaufman jeffkaufman closed this Feb 5, 2019

@jeffkaufman

This comment has been minimized.

Copy link
Owner Author

jeffkaufman commented Feb 5, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment