Tag Archives: ruby

Stripe CTF 3.0

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.

A Fractal Height Map Generator in Ruby

[I’m migrating my old articles to the blog in order to switch to it entirely]

Date: 25th March 2010

Introduction

This article describes the theory behind, and how to implement, a basic fractal height map generator. It is based upon the algorithm defined at http://gameprogrammer.com/fractal.html. Height maps are used in many things: positioning software, graphical rendering, and procedural map generation. Given the right conditions, height maps can be used to create visually stunning images, and are frequently used with an alpha channel to simulate clouds.

All source code used in this article shall be made freely available, under a Creative Commons GPL Licence

The implementation which will be defined here outputs an array of numbers, which on the surface seems fairly mundane. However, with a bit of tweaking with VT100 colour codes, or passing to an image generation program, the algorithm can produce outputs such as this:

The ASCII renderer assigns a colour code to a range of numbers and then depending on your ranges, you can create rainbow-like maps like the one above. The grey scale and transparent images had their number arrays passed to an image generation program called RMagick.

 

The Theory

I will go through the basic idea again as it was defined in the gameprogrammer link, to keep a consistency with terms used further in the article. So before we get on to the DiamondSquare algorithm, I shall implement the simpler 1 dimensional algorithm, which will describe the height of a line, similar to a horizon. The patterns created show some fractal behaviour, in that it is said to be self-similar. An object is said to be self-similar when magnified subsets of the object look like, or are identical to, the whole and to each other[1].

In context of this algorithm, it means that as we add more detail, the more rougher and major features will still hold true, but more detail will become apparent as we look closer. This makes the algorithm ideal for recursion or iterative methods. This implementation uses an iterative method.

Midpoint Displacement in One Dimension

For the creation of the 1 dimensional height map, similar to a horizon, a very simple algorithm is used:

    def generateLine(length)

      # Due to this algorithm being simple for
      # the articles sake, length should be 
      # constrained to the powers of 2. 
      #
      # As we need a midpoint, however, length
      # should be defined as (2^n)+1.

      # Create an array which describes a line.
      # Set the default values to 0American Standard Code for Information Interchange 
      line = Array.new(length, 0)

      # Define the range of the terrain values.
      # For this example we shall take the range
      # of values to be -63 to 63, with the midpoint
      # at 0, out default value. 
      # Range is then 128.
      range = 128;

      # Work out the number of line segments
      # levels there are in the line. As each line 
      # segment level is defined by deviding by two 
      # until length is 1, the number of segments
      # is the log_2 of the length.
      noSegments = Math.log(length-1, 2)

      #Iterate through the levels
      (1 .. noSegments).each{ |level|

        # Work out the line segment length so you
        # can properly address the offset.
        segLength = (length/2**level)

        # Work out the number of line segments
        # within this level
        noSegL = (2**level)-1

        # Iterate through the line segments and 
        # apply your random function.
        (1 .. noSegL).each{ |segOffset|

          # If value is not zero, skip over it, done on a previous
          # level
          if( line[segLength*segOffset] == 0 )

            # Make sure the current value of the line
            # is directly midway between its two parents.
            line[segLength*segOffset] = (line[segLength*(segOffset-1)] + line[segLength*(segOffset+1)])/2

            # Apply random function to value
            line[segLength*segOffset] = randomFunction(line[segLength*segOffset], level, range)

          end
        }
      } 

      return line
    end

Now as you can see the most important part of that algorithm is that which I have purposely missed, randomFunction. This is where you, quite obviously, define how you want your heights defined. A good way is to simply use a bounded random function, where the bounds are defined by the line segment level you are currently within. For example, a function like:

    def randomFunction(value, level, range)

      # Roughness constant 0 < h < 1
      # As h approachs 0, the level dependent
      # bounds grow and tend to 1 for all values
      # of level
      h = 0.8

      # Define bounds in terms of level and a roughness
      # function
      multiplier = 2 ** (-h * level-1)

      # Perform random function, bound it, and then apply 
      # multiplier
      value += (rand() * (range) - (range / 2)) * multiplier

      # Return
      return value
    end

Would offset the value of the line a random amount which is bounded by a function dependent on the line segment level and a roughness coefficient. As this function is the heart of this algorithm and the 2 dimensional algorithm, I will go into some detail on the use of the roughness coefficient. If the roughness coefficient is set to 1, then the multiplier acts the same as : 2^{(-l-1)}; 0 < l < infty ; l in mathbb{Z}^+[/latex]. Decreasing the value of h flattens out the function meaning the bounds are less constrictive and allowing for much rougher terrain. Here is a plot of the multiplier when h=0.8 and h=0.2, and a plot of the generated lines when those constraints are used. X axis is equal to line segment level.  [gallery columns="2" ids="434,433"]  As you can see, the roughness coefficient makes a massive difference to the outputted numbers. For those interested in recreating the plot, I piped the output of the above code into a text file, and then used <a href="http://www.gnuplot.info/">GNUPlot</a> to make the images.</p> </div> <div id="2d"> <h3>Extending into 2 dimensions - The diamond square algorithm</h3> <p>To extend this algorithm into the second dimension, we have to imagine the terrain data as a two dimensional array of numbers. Each number represents a height in this two dimensional field, and so each column and row can be treated similarly to above.</p> <p>To split up a two dimensional array in a self-similar way we must use squares, or diamonds, which are analogous to the line segments of the 1 dimensional algorithm. Then, rather than using the ends of a line segment to work out a base height the corners of the square, or diamond, are used. For example:</p> [gallery columns="2" ids="436,435"] <p>Like the line segment algorithm, the mathematical 'meat' is the same random function as before. The complexity comes in managing which indexes are part of a diamond or a square. So, for example, here is a code segment which works out indexes of a square, depending on level and location, and applies the random function:</p> <pre>    # Get the corners of an arbitrary square and perform operation     # on center.     #     # @param  array           Array to use     # @param  topleftIndexX   X index of top left of square     # @param  topleftIndexY   Y index of top left of square     # @param  length          Length of the square      # @param  level           Level into the calculation     def processSquare(array, topleftIndexX, topleftIndexY, length, level, range, h)        # Get coordinates of the corners of the square       toprightIndexX    = topleftIndexX       toprightIndexY    = topleftIndexY + length + ((level == 0) ? -1 : 0)        bottomleftIndexX  = topleftIndexX + length + ((level == 0) ? -1 : 0)       bottomleftIndexY  = topleftIndexY        bottomrightIndexX = topleftIndexX + length + ((level == 0) ? -1 : 0)       bottomrightIndexY = topleftIndexY + length + ((level == 0) ? -1 : 0)        middleX           = topleftIndexX + (length)/2       middleY           = topleftIndexY + (length)/2        # Get values       topleftValue      = array[topleftIndexX][topleftIndexY]       toprightValue     = array[toprightIndexX][toprightIndexY]       bottomleftValue   = array[bottomleftIndexX][bottomleftIndexY]       bottomrightValue  = array[bottomrightIndexX][bottomrightIndexY]        # Get average       average = (topleftValue + toprightValue + bottomleftValue + bottomrightValue)/4        # Set new value       array[middleX][middleY] = average + calculateOffset(level, range, h)     end</pre> <p>Where <em>calculateOffset</em> is the random function in this application. The diamond calculation algorithm is very similar and looks like this:</p> <pre>    # Get the edges of an arbitrary diamond and perform operation     # on center     #     # @param  array           Array to use     # @param  topIndexX       X index of top of diamond     # @param  topIndexY       Y index of top of diamond     # @param  length          Length of diamond     # @param  level           Level into the calculation     def processDiamond(array, topIndexX, topIndexY, arraylength, level, range, h)        # Adjust       arraylength -= 1       length = arraylength/(2 ** level)        #Get coordinates of the diamond       rightIndexX   = topIndexX + length/2       rightIndexY   = (topIndexY == length) ? length/2 : topIndexY + length/2         leftIndexX    = topIndexX + length/2       leftIndexY    = (topIndexY == 0) ? arraylength - length/2 : topIndexY - length/2        bottomIndexX  = (topIndexX + length/2 == arraylength) ? length/2 : topIndexX + length       bottomIndexY  = topIndexY        middleX       = topIndexX + length/2       middleY       = topIndexY        # Get values       topValue      = array[topIndexX][topIndexY]       rightValue    = array[rightIndexX][rightIndexY]       bottomValue   = array[bottomIndexX][bottomIndexY]       leftValue     = array[leftIndexX][leftIndexY]        # Get average       average = (topValue + rightValue + bottomValue + leftValue)/4        # Set new value       array[middleX][middleY] = average + calculateOffset(level, range, h)        # Wraps       if(middleX == arraylength)         array[0][middleY] = array[middleX][middleY]       end       if(middleY == 0)         array[middleX][arraylength] = array[middleX][middleY]       end     end</pre> <p>The only difference with the above snippet is the different indices it retrieves, and that it must handle wrap around for some of the edges.</p> <p>So currently, we can create arbitrary diamonds and squares within a 2-dimensional array and assign a fuzzy average of the edges according the <em>h</em> value. Now all we need is some code to manage traversing through the levels of iterations and through the diamonds and squares themselves. Here is my solution:</p> <pre>    # The main control loop for the algorithm.     #     # @param  lengthExp       Length exponent     # @param  range           Value range     # @param  h               Roughness constant     def generateTerrain(lengthExp, range, h)        length = (2 ** lengthExp) + 1        array = Array.new       array = createArray(array, length)        #Go through Levels (irerative recursion)       (0 .. lengthExp - 1).each{ |level|          # Iterator for the Square part of the algorithm         # Will go through the x-axis coords         (0 .. (2 ** level) -1 ).each { |sqx|            # Y axis coords           (0 .. (2 ** level) -1).each { |sqy|              gap = length/2 ** level             x = (0 + (gap*sqx))             y = (0 + (gap*sqy))              processSquare(array, x, y, gap, level, range, h)           }         }          # Iterator for the diamond part of the algorithm         (0 ... (2 ** (level+1))).each { |dix|            # Offset in the number of points on the y-axis. Dependant           # on if x iteration is even or odd.           offset = (dix.even?) ? 1 : 2           (0 ... (2 ** (level+1)/2)).each { |diy|              gap = (length/2 ** (level+1))             ygap = 2 * gap              x = (0 + (gap*dix))             if (dix.even?)                y = 0 + (ygap*diy)             else                y = gap + (ygap*diy)             end             processDiamond(array, x, y, length, level, range, h)           }         }       }       return array     end</pre> <p>And this gives us our array with its height map hidden inside. Using a library like <a href="http://rmagick.rubyforge.org/">RMagick</a> we can output images like the ones shown above. To create the gray scale image, the following code was used:</p> <pre>  image = Image.new(array.length, array.length)    (0 ... array.length).each { |x|     (0 ... array[x].length).each { |y|       val = array[x][y] * (2**9)       # Create greyscale image       image.pixel_color(x, y, Pixel.new(val, val, val, val))     }   }   image.display</pre> <p>Which just takes the value in the array, and multiplies it by 512 which gives the values a range of [latex]0 ge v ge 2^{15}, ; frac{v}{512} in mathbb{Z} . This gives us the gaseous image that has been generated above.

Code Listings

A library version of the ruby code found in this tutorial can be found at GitHub.

References

  1. Voss, Richard D., FRACTALS in NATURE: characterization, measurement, and simulation. SIGGRAPH 1987

Creative Commons License
Ruby Diamond Square Height Map Generator by Mr Carl Ellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.
Based on a work at gameprogrammer.com.

Code Golf

CSLU did code golf today. I did 1 and a half tasks, which were:

  1. Output the first 100 prime numbers
  2. Output e to 100 decimal places

Prime numbers

I’m quite proud of this, I managed to do this in 55 characters initially but then after some collaboration with the rest of the club shrunk it down to 49 characters

2.upto(541){|a|i=2;i+=1 while a%i>0;p a if i==a}

e

I never got his fully working as I ended up getting caught up in list comprehensions. Ended up with:

1 + sum [1 / (product [m | m<- [1..n] ]) | n <- [1..300] ]

 

Which is the same as e = sum_{n=0}^{infty } frac{1}{n!} and shows how pretty Haskell is.

Ruby gem – json_serialisable

I was working on a ruby project and stumbed upon my first valid application of metaprogramming. I was creating json serialisation methods and realised they were all practically identical. So I looked at how attr_accessor worked and then wrote my own class method called attr_serialisable. This method generated serialisation methods automatically.

Example

Given a class A

class A
  attr_accessor :a, :b, :c
  attr_serialisable :a, :b, :c

  def initialize(a, b, c)
    @a, @b, @c = a, b, c
  end
end

 

attr_serialisable would generate the following methods:

  def to_json(*a)
    {
      "json_class"  =>  self.class.name,
      "a"           =>  @a,
      "b"           =>  @b,
      "c"           =>  @c
    }.to_json(*a)
  end

  def json_create(o)
    new(*o["a"], *o["b"], *o["c"])
  end

 

Which will allow the class to easily be used by the ‘json’ library.

Links

Rubygems page
Source code

Programming languages course

So I ran a talk on learning programming languages last week. It was the second time I had done that particular talk, and in this case the hardware setup went smoothly – as it was done by Stephen Wattam the CSLU VP.

We had a pretty good turn out, mostly of year year undergraduate students who so far had only played with a little C. I took pictures of everyone hard at work doing their task … well, ok. They were mostly on tryruby.org which was even better.

It showed that they had an interest in a new language which is fairly good at prototyping and will allow them to try out their ideas fast. I may have semi pushed them on to it in my talk, so I’m glad they were listening. No one tried learning Haskell though, but then I’ll drop in on everyone next term and see how they are doing. The slides and some info for my talk can be found  at the CSLU site.

On a side note … My Instagram tshirt came! I’m not sure if I’ll ever wear it outside as it’s a bit long, but still!

Rain – Agent-based water

Well I’ve been wanting to do this for a while now, and on Sunday with a freshly installed (and therefore speedy) net book under my belt, I thought I’d have a crack at it.

Last year (maybe even 2 years now) ago, I made a weak plasmoid generator with the intention of using it for terrain generation. I’ve always wanted to use that library for some agent based programming, and a simple (rule wise) example of it would be water. You put some water agents on the map they move as low as they can go, then evaporate. This kind of does that, and definitely suffers from “proof of concept” syndrome. Water moves, but to do anything fancy will require redoing, which I’ll probably end up doing on my next free Sunday.

So,  using a library called Gosu to handle the drawing and the event loop, and a library called TexPlay which allowed me to modify pixels, I got a render up and running which displayed a map of tiles (1 pixel tile 😉 ), and the colour was defined with a lambda that was passed to all of them.

As I’m learning Haskell at the moment, I thought I’d give some lambdas a go, and it made it really easy actually.

There are two types of agents in this program,  Rain and Sources.

  • Rain just flows to a low point.
  • Sources make Rains.

Rains become sources if they hit a low point, which basically has the effect of stacking the Rains that have pooled there so they can make lakes. As Rains are destroyed when they stop, and Sources can only produce a finite amount of Rains based on how many are there when it is made, the system sort of stays constant. Initial sources are given enough Rains to cover the whole map 1 deep.

That is awkward to explain.

Most of the issues with this program was making the renderer fast enough to work on a net book, and as I’m not a graphics man, I made many rooky mistakes.

This is fairly mesmirizing to watch, and I’ll definitely improve it further, by:

  • Making the map colouring sample from colour->height table
  • Have water level as a tile attribute to make things cleaner
  • Fix evaporation
  • Make it so that tiles which have a constant flow of agents over them are distinguished from one-off “rain” paths
  • Fix Rain

It’s a project, feel free to fork from git hub here at https://github.com/carl-ellis/Rain

 

Old school screen capture.

Video here:  Rain – agent-based

 

Rails 3 and lighttpd

This was performed on Archlinux with lighttpd 1.4.28 and rails 3.0.3

Prerequisites

Required packages:

  • lighttpd,
  • fcgi,
  • ruby,
  • and their dependencies…

 

Ruby Setup

Required gems:

  • fcgi,
  • bundler

(if you are behind a proxy, the magic gem command is :

# gem install GEM -r -p "http://[PROXY_URL]:[PROXY_PORT]"

)

Once you have that you need to create a “dispatch.fcgi” script to do all the rails magic. I found an example one at http://stackoverflow.com/questions/3296206/rails-3-and-fcgi .

#!/usr/bin/ruby

require 'rubygems'require 'fcgi'

require_relative '../config/environment'

class Rack::PathInfoRewriter  

  def initialize(app)    
    @app = app  
  end

  def call(env)    
    env.delete('SCRIPT_NAME')    
    parts = env['REQUEST_URI'].split('?')    
    env['PATH_INFO'] = parts[0]    
    env['QUERY_STRING'] = parts[1].to_s    
    @app.call(env)  
  end
end

Rack::Handler::FastCGI.run  Rack::PathInfoRewriter.new(YOUR_APP_NAME::Application)

Running a “bundle install” from your app root will make sure all the necessary gems are available for local use. Follow these instructions and run “ruby public/dispatch.fcgi”, if you get no errors, voila!

Lighttpd Setup

Now, to set up lighttpd you need to merge this with your config:

server.modules   += ( "mod_fastcgi", "mod_rewrite" )

$HTTP["host"] == "localhost" {        

  server.document-root       =   "/path/to/your/app/public/"

  server.dir-listing         =   "disable"        
  server.error-handler-404   =   "/dispatch.fcgi"

  fastcgi.server             =   ( 
                                   ".fcgi" => ( 
                                     "localhost" => (
                                       "min-procs" => 1,
                                       "max-procs" => 1,
                                       "socket" => "/tmp/ruby-beholder.socket",                
                                       "bin-path" => "/path/to/your/app/public/dispatch.fcgi",                
                                       "bin-environment" => ( "RAILS_ENV" => "development" )        
                                       ) 
                                     ) 
                                   )
}

A quick “sudo /etc/rc.d/lighttpd restart” and a check of the error logs will tell you if it has worked