Sadly, level 3 would not run for me, even with Stripe’s patch, so I could not continue with the competition. It was fun while it lasted though – C
Wednesday saw the beginning of another Stripe CTF! This time I was in London when it started so I went to the launch meeting with some old uni friends.
The theme this time was distributed computation, so with a tiny netbook, I dove in to the levels.
Level 0
Level 0 was essentially an exercise in optimisation. A given text input was checked against a list of words. If an input word was in the preset dictionary, it had to be tagged. The preset dictionary was an ordered list, and as such was O(n) to search. By applying the following:
index 1558f2d..d07273f 100644
--- orig.rb
+++ mod.rb
@@ -1,4 +1,5 @@
#!/usr/bin/env ruby
+require 'set'
# Our test cases will always use the same dictionary file (with SHA1
# 6b898d7c48630be05b72b3ae07c5be6617f90d8e). Running `test/harness`
@@ -7,6 +8,7 @@
path = ARGV.length > 0 ? ARGV[0] : '/usr/share/dict/words'
entries = File.read(path).split("n")
+entries = Set.new(entries)
contents = $stdin.read
output = contents.gsub(/[^ n]+/) do |word|
The list is turned into a set with a O(1) lookup time. Significantly speeding up the operation.
Level 1
This level was about cryptocurrencies, and to pass this level you had to mine a … ‘GitCoin’. Essentially, you were given a repo with an initial catalog of transactions. You had to successfully submit a transaction with gave your given use a gitcoin.
Proof of work for a gitcoin was determined by ensuring that the git commit message had a SHA1 signature that was lexigraphically smaller than the difficulty. So add a nonce to your commit message and keep cycling though random numbers until the commit message had a valid signature.
Stripe provided a very slow bash reference implementation, which I still used to pass the level. Instead of increasing the nonce in bash though, I wrote a python script to find a correct hash for me faster.
import sys
from hashlib import sha1
import random
import string
import Queue as queue
import threading
def work(diff, tree, parent, timestamp, q):
diffl = len(diff)
diff = ''.join('0' for x in range(diffl))
body = "tree %snparent %snauthor CTF user <me@example.com> %s +0000ncommitter CTF user <me@example.com> %s +0000nnGive me a Gitcoinnnnonce: " % (tree, parent, timestamp, timestamp)
while True:
body_b = '%s%s' % (body, ''.join(random.choice(string.hexdigits) for x in range(8)))
s = sha1('commit ' + str(len(body_b)) + ' ' + body_b)
hex = s.hexdigest()[:diffl]
if hex.startswith(diff):
body = body_b
break
q.put(body)
def main():
diff, tree, parent, timestamp = sys.argv[1:]
q = queue.Queue()
threads = [threading.Thread(target=work, args=(diff, tree, parent, timestamp, q)) for i in range(1)]
for th in threads:
th.daemon = True
th.start()
body = bytes(q.get())
with open('/home/carl/level1/test.txt', 'w') as f:
f.write(body)
for th in threads:
th.join(0)
if __name__ == '__main__':
main()
There were some hurdles I came across while solving this, which show in the code. The git hashing command git hash-object -t commit didn’t just take the SHA1 hash of its input, it would first prepend commit len(data) before hashing. This was easy enough to find with a bit of searching, but a major issue I was having that I couldn’t replicate the SHA1 hash unless I first wrote the commit to a file, rather than streaming via stdout. So I just wrote to a file and modified the miner bash script to change:
@@ -56,12 +56,12 @@ $counter"
# See http://git-scm.com/book/en/Git-Internals-Git-Objects for
# details on Git objects.
- sha1=$(git hash-object -t commit --stdin <<< "$body")
+ sha1=$(git hash-object -t commit /home/carl/level1/test.txt)
if [ "$sha1" "<" "$difficulty" ]; then
echo
echo "Mined a Gitcoin with commit: $sha1"
- git hash-object -t commit --stdin -w <<< "$body" > /dev/null
+ git hash-object -t commit --stdin -w /home/carl/level1/test.txt > /dev/null
git reset --hard "$sha1" > /dev/null
break
fi
Which let me get the correct hashes and mine the coin.
Level 2
Level 2 was all about DDOS attacks. The idea was that there were a number of back end servers, a reverse proxy (which you modified), and a number of clients, some malicious and others not. You had to modify the reverse proxy (called shield) to not let malicious traffic through, and to attempt to minimise back end idleness. Scores were determined by a test harness and also on the git push hook.
Stripe provided the attack code for reference, which made the level really easy. Malicious attackers basically spawned more connections more often, and the numbers that they spawned was defined in the file, as:
simulationParameters = {
'clientLifetime': 2, // In rounds
'roundLength': 500, // In ms
'roundCount': 40,
'clientsPerRound': 5,
'pElephant': 0.4,
'mouseRequestsPerRound': 2,
'elephantRequestsPerRound': 50,
'backendCount': 2,
'backendInFlight': 2,
'backendProcessingTime': 75
};
So from this you can see that malicious clients send 50 requests per round, and normal clients send 2. So my first solution was just to limit the number of connections from each client with a simple counter. My implementation looks like:
diff --git a/shield b/shield
index c67bd68..8ba87f2 100755
--- a/shield
+++ b/shield
@@ -7,6 +7,7 @@ var httpProxy = require('./network_simulation/lib/proxy');
var checkServer = require('./network_simulation/lib/check_server');
var nopt = require('nopt');
var url = require('url');
+var rcount = {};
var RequestData = function (request, response, buffer) {
this.request = request;
@@ -14,6 +15,16 @@ var RequestData = function (request, response, buffer) {
this.buffer = buffer;
};
+
+function checkRequest(ip){
+ if (rcount[ip] === undefined) {
+ rcount[ip] = 1;
+ } else {
+ rcount[ip]++;
+ }
+ return rcount[ip] <= 4;
+}
+
function ipFromRequest(reqData) {
return reqData.request.headers['x-forwarded-for'];
}
@@ -29,10 +40,10 @@ var Queue = function (proxies, parameters) {
};
Queue.prototype.takeRequest = function (reqData) {
// Reject traffic as necessary:
- // if (currently_blacklisted(ipFromRequest(reqData))) {
- // rejectRequest(reqData);
- // return;
- // }
+ if (!checkRequest(ipFromRequest(reqData))) {
+ rejectRequest(reqData);
+ return;
+ }
// Otherwise proxy it through:
this.proxies[0].proxyRequest(reqData.request, reqData.response, reqData.buffer);
};
I committed and pushed, and surprisingly, this gave me a passing score!
Level 3
This is where the story gets sad. I checked out the code, and I could not get the ./test/harness to work correctly. The tak was a file indexing service, and it had to be optimised. It was written in Scala, which I have never used – so I could not work out how to debug it. Stripe released a fix, but it still did not fix my issues. At which point I had to move on to other things and could not complete the CTF.
Sad times.