Stripe CTF v3 Writeup

Written by AbiusX on . Posted in Computer, Development

Stripe is a financial firm, which runs CTF competitions of highest quality. This year, around today (22 Jan) they launched their third CTF, which is based on distributed computing (the top topic of the era!). The CTF is available at https://stripe-ctf.com

On their previous web hacking CTF, unfortunately my uncle had passed away, and I had very little time with being responsible for the funeral and all, and finished it in a day, the writeup of which is available here; and won the Stripe T-Shirt (sent to Iran, where I resided back then).

I started this one in the middle of Nicholas Christin‘s presentation today. He was at UVa today, presenting some of his illicit supply chain management tracking research to us, which was absolutely lovely. It’s also worth mentioning that he was my CMU advisor. On this CTF so far, I’ve been on the top 20 leaderboard list, but unfortunately I have to quit competing to get to the rest of my life (research), but I loved this CTF as much as their previous ones!

* * *

Level 0

There’s a piece of ruby code, that is apparently too slow, and you need to understand it and make it perform better. The code is:

#!/usr/bin/env ruby

# Our test cases will always use the same dictionary file (with SHA1
# 6b898d7c48630be05b72b3ae07c5be6617f90d8e). Running `test/harness`
# will automatically download this dictionary for you if you don't
# have it already.

path = ARGV.length > 0 ? ARGV[0] : '/usr/share/dict/words'
entries = File.read(path).split("\n")

contents = $stdin.read
output = contents.gsub(/[^ \n]+/) do |word|
  if entries.include?(word.downcase)
    word
  else
    "<#{word}>"
  end
end
print output

 

What it does is essentially reading the dictionary file (available on UNIX systems, having a list of all English words each on a separate line) and storing it in an array. Then it reads a text from STDIN, and for each word (word boundaries are space and enter, as defined in the gsub regex) if its found in the words (entries) array, outputing the word intact, otherwise inside <> marks.

The bottleneck here is that for each word in the text, the whole dictionary array is scanned. The best approach would be to construct a dictionary (hashmap, dictionary tree or any other compatible data structure) from the entries and then search inside that, changing O(n) code to O(1).

The resulting code would be:

path = ARGV.length > 0 ? ARGV[0] : '/usr/share/dict/words'
entries = File.read(path).split("\n")
t= Hash.new
entries.each{ |entry| t[entry]=1}
contents = $stdin.read
output = contents.gsub(/[^ \n]+/) do |word|
  # if entries.include?(word.downcase)
  if (t[word.downcase]==1)
    word
  else
    "<#{word}>"
  end
end
print output

There’s room for further optimization on this code, the furthest dealing with storing the memory image of the hashmap, and reading it instantly on launch, making the code run instantly (O(1)).

SPOILER ALERT: Stripe CTF is a lot of fun, and there are very few CTFs of this quality. If you wanna enjoy it, stop reading and start trying to solve the questions on your own.

Welcome

I'm Abbas Naderi Afooshteh, also known as Abius and AbiusX. A software engineer and a renowned security expert, I'm currently OWASP chapter leader of Iran, owner of many OWASP projects, a member of ISSECO and CIO of Etebaran Informatics. For more details of what I do and what I can do, check my resume.