Last Days of The Pirate Bay

I’ll be showing my BitTorrent video collage at Long Winter tonight.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
$ cat last-days.nfo
    __               __     ____                            ____
   / /   ____ ______/ /_   / __ \____ ___  _______   ____  / __/
  / /   / __ `/ ___/ __/  / / / / __ `/ / / / ___/  / __ \/ /_  
 / /___/ /_/ (__  ) /_   / /_/ / /_/ / /_/ (__  )  / /_/ / __/  
/_____/\__,_/____/\__/  /_____/\__,_/\__, /____/   \____/_/     
                                    /____/                      
  ________            ____  _            __          ____             
 /_  __/ /_  ___     / __ \(_)________ _/ /____     / __ )____ ___  __
  / / / __ \/ _ \   / /_/ / / ___/ __ `/ __/ _ \   / __  / __ `/ / / /
 / / / / / /  __/  / ____/ / /  / /_/ / /_/  __/  / /_/ / /_/ / /_/ / 
/_/ /_/ /_/\___/  /_/   /_/_/   \__,_/\__/\___/  /_____/\__,_/\__, /  
                                                             /____/   

Last Days of The Pirate Bay

On December 9th, Swedish police raided a datacenter in Stockholm and
seized the servers that run The Pirate Bay, shutting down the world's
most notorious and popular piracy site. Five days previously, on
December 4th, I had bought a server under an assumed name from a
European hosting company that doesn't ask too many questions, chose
the 100 most popular movie torrents from The Pirate Bay, and began
recording network traffic. I had no idea that I was recording the last
days of The Pirate Bay.

TPB was a BitTorrent tracker. BitTorrent is a way for many
people to share large files over the internet. To download a movie
over BitTorrent is to connect to other people downloading that movie
and request little pieces. The pieces are downloaded out of order from
your peers across the globe and then reassembled on your computer back
into the movie you want.

After I downloaded the 100 most popular movies, I started to seed
them for others to download. People from around the world are
downloading little pieces of different movies from me, and as they do, I
record the piece they ask for and the IP address they were coming
from.

You're watching a visualization of that traffic.

The Pirate Bay might come back, but it probably won't. It's not needed
anymore. About 20 million nodes are connected at any given time to a
global sharing network that doesn't need websites like TPB
to distribute information about which peer has which file. All the
movies I downloaded are still being actively shared without TPB.

TPB is gone, for now at least. Consider this my eulogy.

The Pirate Bay 2003-2014(?)

- Max Veytsman, December 2014

Greets: Hacker School where writing a BitTorrent client is a right of
passage, Nicolas Maigret who I shamelessly stole from, Long Winter for
letting me do this.

Last Days of The Pirate Bay

Solving the Expression Problem in Clojure

Last night, I was having a drink with a friend and he asked me what I liked about Clojure. Immutable data structures are coming in vogue outside Clojure, and they don’t need to be sold very hard. I don’t know a lot about virtual machine optimization, but I’ve always been swayed by the argument that with the amount of dollars and intellectual effort spent on JVM optimization in the past decades, it’s pretty fast. Honestly, I just find parentheses alluring.

Then I tried to say something about how protocols elegantly solve the expression problem, my friend had no idea what I was talking about.

I started writing an email about what I meant, and it morphed into this post.

The expression problem

To be honest, “a drink” is somewhat of an understatement, and I did a poor job of explaining what the expression problem actually is.

The best explanation of the expression problem comes from c2.com, and I include it almost in its entirety:

The “expression problem” is a phrase used to describe a dual problem that neither ObjectOrientedProgramming nor FunctionalProgramming fully addresses.

The basic problem can be expressed in terms of a simple example: Suppose you wish to describe shapes, including rectangles and circles, and you wish to compute the areas.

In FunctionalProgramming, you would describe a data type such as:

type Shape = Square of side
             | Circle of radius 

Then you would define a single area function:

define area = fun x -> case x of
    Square of side => (side * side)
    | Circle of radius => (3.14 *  radius * radius)

In ObjectOrientedProgramming, you would describe the data type such as:

class Shape <: Object
  virtual fun area : () -> double
   
class Square <: Shape
  side : double
  area() =  side * side
 
class Circle <: Shape
  radius : double
  area() = 3.14 * radius * radius

The ‘ExpressionProblem’ manifests when you wish to ‘extend’ the set of objects or functions.

  • If you want to add a ‘triangle’ shape:
    • the ObjectOrientedProgramming approach makes it easy (because you can simply create a new class)
    • but FunctionalProgramming makes it difficult (because you’ll need to edit every function that accepts a ‘Shape’ parameter, including ‘area’)
  • OTOH, if you want add a ‘perimeter’ function:
    • FunctionalProgramming makes it easy (simply add a new function ‘perimeter’)
    • while ObjectOrientedProgramming makes it difficult (because you’ll need to edit every class to add ‘perimeter()’ to the interface).

Defining some shapes

Clojure’s records serve the purpose of types and classes in the examples above.

1
2
3
4
5
6
7
8
9
10
11
;; We have circles with radii
(defrecord Circle [radius])

;; and squares with sides, oh my!
(defrecord Square [side])

;; Here's a circle
(def my-circle (Circle. 5))

;; And a square!
(def my-square (Square. 4))

Adding a new Shape

As the quote above says, in functional programming languages, defining a perimeter function is easy, but adding a new shape is hard. If our area function looks like this:

1
2
3
4
(defn area [shape]
  (cond 
   (instance? Circle shape) (* Math/PI (:radius shape) (:radius shape))
   (instance? Square shape) (* (:side shape) (:side shape))))

we can easily add a perimeter function in the same vein, but adding a new shape is harder.

We can define a new record:

1
(defrecord Triangle [a b c])

But now we’re stuck rewriting the area function to include Triangle in the switch statement. If we were using a shape library that didn’t have triangles, we would have a hard time extending it without forking their code.

We need a better way to do polymorphism then a switch statement!

One choice is multi-methods, but I’m going to focus on Protocols.

Protocols

Protocols are an abstract notion of interfaces from OO land. A protocol is simply a set of methods and their signatures. If a type participates in a protocol, there exists an implementation for that method for that type.

1
2
3
;; Things that are Areable have an area method
(defprotocol Areable
  (area [this]))

We use extend-protocol to define how Square and Circle implement the Areable protocol1.

1
2
3
4
5
6
;; Circles and Squares are Areable
(extend-protocol Areable
  Circle
  (area [{radius :radius}] (* Math/PI radius radius))
  Square
  (area [{side :side}] (* side side)))

Protocol methods behave just like functions, with dispatch determined by the type of the argument:

1
2
3
4
5
6
7
8
9
10
11
;; A circle with the radius 5
(def my-circle (Circle. 5))

(area my-circle)
; => 78.53981633974483

;; A square with the side 5
(def my-square (Square. 5))

(area my-square)
; => 25

With protocols we simple extend the Triangle type to support the Areable protocol:

1
2
3
(extend-type Triangle
  Areable
  (area [this] ...))

Adding a new function

The other part of the expression problem is defining a “perimeter” method. Types can implement multiple protocols, and this implementation can be written anywhere. You can define a new protocol, and then extend core Java classes to participate in it. If you come from the Ruby world, you might think that this is similar to monkey-patching, and it is.

Because we can extend the Circle and Square types to participate in a new protocol, adding a perimeter is also straightforward:

We define a new protocol

1
2
(defprotocol Perimeterable
  (perimeter [this]))

and extend it to support Circle and Square

1
2
3
4
5
(extend-protocol Perimeterable
  Circle
  (perimeter [{radius :radius}] (* 2 Math/PI radius))
  Square
  (perimeter [{side :side}] (* 4 side)))

On “monkey-patching”

If you come from the Ruby world, the above code might remind you of monkey-patching. Monkey-patching certainly deserves its infamy, but it’s problems are misunderstood. Being able to add functionality to core types is not a bad thing! The issue is namespacing.

What bothers many people about monkey-patching in Ruby is that you can load a library, and suddenly it injects all kinds of new methods into core classes you didn’t expect:

1
2
3
4
5
"string".methods.count
# => 170
require 'rails'
"string".methods.count
# => 225

Now your code has 55 new methods in the String class, and who knows how many of the existing String methods you know and love have been redefined!

In Clojure, you can extend core types to support whatever protocol you want, but participating in a protocol is just like defining some functions, and those functions are scoped to a namespace:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
(def foo bar)
(in-ns 'monkeypatching)
;; We're now in the monkeypatching namespace

(defprotocol Monkey
  (patch [this]))

;; Let's let nil and String participate in this protocol
(extend-protocol Monkey
  nil
  (patch [this] "Check out this cool nil!")
  String
  (patch [this] "I'm an awesome string!"))

(patch nil)
; => "Check out this cool nil!"
(patch "this is some string")
; => "I'm an awesome string!"

;; Now we switch back to another namespace to do some hard work
(in-ns 'workin-hard)

(patch nil)
; => CompilerException java.lang.RuntimeException: Unable to resolve symbol: patch in this context, compiling:(NO_SOURCE_PATH:1:1)

;; We can access the "monkeypatched" methods by using their namespace
(monkeypatching/patch "a string")
; => "I'm an awesome string!"

Brining it together

Let’s add a Triangle type that support both area and perimeter. We can even provide implementations for the protocols it participates in directly inside of defrecord:

1
2
3
4
5
6
7
8
9
(defrecord Triangle [a b c]
  Areable
  ;; The hardest part of solving the expression problem in Clojure is looking up highschool geometry
  ;; Heron's formula
  (area [{:keys [a b c]}]
    (let [s (/ (+ a b c) 2)]
       (Math/sqrt (* s (- s a) (- s b) (- s c)))))
  Perimeterable
  (perimeter [{:keys [a b c]}] (+ a b c)))

Footnotes

  1. The [{radius :radius}] bit may be confusing. It’s using map destructuring to bind the :radius field of the Circle record to the symbol radius. Without it, the function would look like this:

    (area [this]
      (let [radius (:radius this)]
        (* Math/PI radius radius)))
    

How to take over the computer of any Java (or Clojure or Scala) developer

Update: 07/31/2014

Sonatype has reacted to this post and will soon be turning on SSL access for all users. Their blog post announcing this is here. I’m very happy that they are making this change, and the Java ecosystem is going to be more secure for it!

That being said, if you’re reading this and are thinking of charging $10 to gauge the true demand for security features in your product, don’t. Imagine if car companies decided to charge $10 to gauge the true demand for air bags. Luckily, we live in a world where car companies can’t legally do that.

I’m happy that Sonatype made this change in their policy, and I hope they continue to decrease friction for security features in their products. It’s our responsibility as developers to make the most secure product we can for our users. How much friction they are willing to endure for a security feature shouldn’t factor into it.


The other day I started hacking on a Clojure project of mine, when I saw my firewall display this:

I’m downloading clojure.jar from http//repo.maven.apache.org over port 80! This means that I’m going to be downloading JARs over unencrypted http. I thought this was an issue with leiningen at first. As it turns out it’s not lein’s fault at all. Clojure.jar, and a whole lot of other JARs that are important in the Java/Clojure/Scala/etc world are officially hosted on Maven Central, which is a public service provided by Sonatype. Sonatype has a policy that they only allow SSL access to people who have authentication tokens. In order to get an authentication token and SSL access, you need to donate $10 to the Apache foundation. If you don’t believe me, the donate page is here, and the blog post announcing this policy is here. They even mention man-in-the-middle attacks on it.

Because authentication tokens are issued per user/organization, tools like maven and leiningen can’t bundle authentication tokens. If you’re pulling down some Java project and installing its dependencies, you’re not going over SSL. This policy was confirmed by a Sonatype employee when I got into a twitter tiff about this:

Unless you take very careful steps that involve paying someone $10, JARs you download can be man-in-the-middled, and code you execute on your system can be replaced by malware.

When can this happen? If you ever use a public wifi network in a coffee shop, or are on a wifi network that someone took over you can be man-in-the-middled. Your ISP can man-in-the-middle you at will, and some do so in order to serve you ads. Or, perhaps you are subject to a man-in-the-middle attack from a state actor.

Dilettante

To prove how easy this is to do, I wrote dilettante, a man-in-the-middle proxy that intercepts JARs from maven central and injects malicious code into them.

Proxying HTTP traffic through dilettante will backdoor any JARs downloaded from maven central. The backdoored version will retain their functionality, but display a nice message to the user when they use the library. You can see the video below:

Or a screenshot:

You can find the code here

The Technical Details

When JARs are downloaded from Maven Central, they go over HTTP, so a man in the middle proxy can replace them at will. It’s possible to sign jars, but in my experimentation with standard tools, these signatures aren’t checked. The only other verification is a SHA1 sum, which is also sent over HTTP. When dilettante sees a JAR coming from Maven Central it replaces the original JAR with a backdoored version that runs malicious code on the victim’s computer. Since the SHA1 hashes are sent over HTTP only, dilettante simply replaces any hashes it sees with the hash of the corresponding backdoored JAR.

I used the excellent mitmproxy library to build my tool. I started by writing an inline script for the proxy and then moved on to creating a standalone tool with libmproxy.

A JAR is just a zip file that contains Java Class files, resources and some metadata. To backdoor a JAR, I can insert my own class by adding it to the zip archive:

1
2
3
4
5
6
7
package dilettante;

public class Dilettante {
    public static void() {
        // do some evil stuff
    }
}

The trick is finding a way to call my malicious class. I know that my victim will be downloading some library, and I need to run my malicious code regardless of what classes in the library they actually use. I would also like to actual functionality of the library to not be affected.

Java has the concept of static class blocks, which are class level initializers — that is, they contain code that is run once when the class (not an instance!) is loaded into memory. After I insert a malicious class file into the jar, I can call it in a static block like this:

1
2
3
4
import dilettante.*;
static {
    Dilettante.backdoor();
}

In order to inject the above snippet, I need to inject it into Java classes directly, not source files. I use Krakatau, a Java disassembler/assembler library for Python. It let’s me add the snippet in Jasmin format:

1
2
3
4
5
6
7
.method static <clinit> : ()V
  ; method code size: 4 bytes
  .limit stack 0
  .limit locals 0
  invokestatic dilettante/Dilettante backdoor ()V
  return
.end method

Limitations

This is a proof of concept!, and so it still has some limitations

  1. Currently it’s not very fast. There are a couple of reasons for this

    • I have to run a disassemble and an assemble step. It would be more efficient to directly append the assembled shim to the .class file.
    • The way I am using Python’s zipfile library, I’m actually creating a second copy of every class in the zip. This is inefficient in terms of space and speed. Careful reading of the zip spec may lead to an efficient way of appending data to files inside a zip.
  2. If a user is downloading multiple JARs in one go, we will backdoor each one. The malicious payload is executed only once per JAR, but if multiple JARs are backdoored, we will execute it several times. This issue will disappear if we replace the cat picture with a high quality persistent backdoor that is smart enough to only infect a system once :).

Delimited Continuations in Ruby Part 2: Generators and Coroutines

Last time, I showed some basic things you can do with delimited continuations. If you’re still confused about them (as I am!) another good tutorial is here.

Let’s dive right in and build some more complicated control structures!

Generators

Let’s start by building what Python calls “Generators.” Ruby has Enumerators, which are pretty similar, but I’ll call it a generator in order to differentiate my implementation from the Ruby core.

Here’s the code I want to write <div class=’bogus-wrapper’>

<figcaption></figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 3 4 5 6 7 </pre></td><td class=’code’><pre>counter = Generator.new do |g| ctr = 0 while true g.yield(ctr) ctr += 1 end end </pre></td></tr></table></div>
</div> Then I use it like so

1
2
3
4
5
6
7
counter.next
# => 0
counter.next
# => 1
counter.next
# => 2
# ...

Using delimited continuations to build a generator is pretty straight-forward. Our constructor will get a block and surround it with a prompt to delimit a continuation. Yielding adds the yielded value into an internal queue, and uses control to capture a continuation. When we call that continuation, we will execute the code around the control, which is precisely like entering at where we called yield. Getting the next value of our generator pops a result off the queue and invokes the saved continuation.

The annotated code is below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Generator
  def initialize(&block)
    # @results will be used to save values yielded by our generator
    @results = []
    # Calling the block is wrapped in a prompt in order to enclose it in a continuation
    DelimR.prompt do
      # The block is passed self, so that it can call the yield method defined below
      block.call(self)
    end
  end

  def yield(result)
    # The yield method saves the result it receives, and saves the continuation in @next
    @results << result
    DelimR.control do |k|
      @next = k
    end
  end
  def next
    # @result is used as a FIFO queue of yielded values
    r = @results.shift

    # an empty @results means that no more values have been yielded
    if r.nil?
      raise "Iterator finished"
    end

    # This invokes the saved continuation, not passing it any values
    @next.call(nil)

    # return the saved @result that was shifted off the bottom of the queue
    r
  end
end

Coroutines

Coroutines, also known as Fibers in ruby-land, are subroutines that can suspend their execution, to be resumed at a later point. They are very useful as a lightweight thread-like construct. They are very similar to generators, and can actually be implemented in terms of them. Besides being useful for asynchronous tasks, “Co-routines are to state machines what recursion is to stacks”.

We can can modify our Generator class to be a coroutine by renaming next to send and allowing data to be passed into it, so foo = c.yield will alssign whatever is sent to the coroutine to foo when execution resumes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Coroutine
  # initialize and yield are the same as for Generator
  def send(value=nil)
    # @result is used as a FIFO queue of yielded values
    r = @results.shift

    # an empty @results means that no more values have been yielded
    if r.nil?
      raise "Iterator finished"
    end

    # This invokes the saved continuation, not passing it any values
    @next.call(value)

    # return the saved @result that was shifted off the bottom of the queue
    r
  end
end

Here’s an implementation of the parsing example from Eli Bendersky’s blog post using the Coroutine class defined above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
def hex_encode(str)
  str.split(//).map{ |x| x.ord.to_s(16) }.join
end

frame_receiver = Coroutine.new do |c|
  while true
    frame = (c.yield(true))
    puts 'Got frame:', hex_encode(frame)
  end
end

unwrap_protocol = Coroutine.new do |c|
  header = "\x61"
  footer = "\x62"
  dle = "\xAB"
  after_dle_func = lambda { |x| x }
  target = frame_receiver
  # Outer loop looking for a frame header
  #
  while true
    byte = (c.yield(true))
    frame = ''

    if byte == header
      # Capture the full frame
      #
      while true

        byte = (c.yield(true))

        if byte == footer

          target.send(frame)
          break
        elsif byte == dle
          byte = (c.yield(true))
          frame += after_dle_func.call(byte)
        else
          frame += byte
        end
      end
    end
  end
end



bytes = [0x70, 0x24,
         0x61, 0x99, 0xAF, 0xD1, 0x62,
         0x56, 0x62,
         0x61, 0xAB, 0xAB, 0x14, 0x62,
         0x7
        ].map(&:chr)


bytes.each do |byte|
  unwrap_protocol.send(byte)
end

# Got frame:
# 99afd1
# Got frame:
# ab14

Final thoughts

Once I had prompt/control, I found implementing generators and coroutines pretty straightforward. I think that prompt/control are easier to reason about then non-delimited continuations. One piece of evidence that I have for this is that Ruby’s implementation of generators using non-delimited continuations is harder (for me) to understand then the one above using delimited continuations.

Either way, having an abstraction that allows you to implement new control structures is really cool and empowering. For instance, this paper uses delimited continuations to implement Prolog-like backtracking!

There are still many things I don’t understand about continuations, a partial list is below

  1. There is a difference between prompt/control and reset/shift. I don’t know what it is.
  2. I don’t entirely understand what @@keep_delimiter_upon_effect does in https://github.com/mveytsman/DelimR/blob/master/lib/delimr.rb
  3. In the generator example, why doesn’t the line ctr=0 get executed on every iteration?
  4. I actually implemented semi-coroutines. For full coroutines I need to be able to transfer exeution between them. My instricnt is that I can do this by calling resume on the target coroutine, but seeing this in the Ruby Fiber documentation makes me think there is something non-trivial I don’t understand here: > You cannot resume a fiber that transferred control to another one. This will cause a double resume error. You need to transfer control back to this fiber before it can yield and resume.

Delimited Continuations in Ruby Part 1

For the past few days at Hacker School, I’ve been exploring continuations. Continuations are hard to describe. Basically, a continuation represents the execution state of a program at a point. Capturing the continuation and invoking it later allows you to come back to that point in the programs execution. Continuations can be used to implement complicated control flow constructs.

If that was complicated, here’s a sandwich metaphor from Luke Palmer:

Say you’re in the kitchen in front of the refrigerator, thinking about a sandwich. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwich, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwich. But fortunately, there’s a sandwich on the counter, and all the materials used to make it are gone. So you eat it. :-)

Another way to put it: a captured continuation is a label, and to invoke it is to GOTO.

The Basics

On that note, let’s start by building a simple GOTO.

In Ruby, you need to require 'continuation' to enable continuations. callcc takes a block, and passes it the current continuation as parameter. That continuation can be invoked later.

1
2
3
4
5
6
7
8
9
10
11
12
13
require 'continuation'
$labels = {}

def label(label_name)
  callcc { |continuation|   $labels[label_name] = continuation }
end

def goto(label_name)
  unless $labels.has_key? label_name
    raise "No label #{label_name}"
  end
  $labels[label_name].call
end

We can then build a for loop

1
2
3
4
5
6
7
8
9
10
i = 1
puts "entering loop"
label "loop"
if i < 10
  puts i
  i += 1
  goto "loop"
end
puts "loop done"
puts "i is #{i}"

We can even build a reverse GOTO (known as the COMEFROM, implementation courtesy of Wikipedia).

ruby
1
2
3
4
5
6
7
8
9
10
11
12
13
$come_from_labels = {}
 
def label(l)
    if $come_from_labels[l]
        $come_from_labels[l].call
    end
end
 
def come_from(l)
    callcc do |block|
        $come_from_labels[l] = block
    end
end

Problems Abound

You can implement pretty much any control flow you want with continuations, but it may be hairy.

To give an example of the kind of problems you face when working with traditional continuations, here’s a bug I ran into when writing the GOTO example above. My orginal code for label looked like this:

1
2
3
def label(label_name)
   $labels[label_name] = callcc { |continuation| continuation }
end

Running it, I got the following output:

1
2
3
4
5
entering loop
1
2
goto.rb:15:in `goto': undefined method `call' for nil:NilClass (NoMethodError)
	from goto.rb:27:in `<main>'

Can you guess the issue? When goto was called, it returned to the place where callcc was called. That means that whatever was passed to the continuation would now be assigned to $labels[label_name]. We didn’t pass anything to the continuation, and so $labels[label_name] becomes nil.

To further illustrate the point:

1
2
3
4
5
6
$continuation = callcc { |continuation| continuation }
puts "$continuation is #{$continuation}"
# "$continuation is #<Continuation:0x007fbbaa0193f8>"
$continuation.call("hello world")
puts "$continuation is #{$continuation}"
# "$continuation is hello world"

It seems like it would be convent to separate the concept of shifting control from the place we want to return to.

Enter delmited continuations

Delimited continuations are way of capturing a fixed slice of computation instead of the unlimited computation captured by a regular continuation.

I wrote a little library called DelimR that implemnts delimited continuations for ruby by using the native callcc construct. I made a direct port of Oleg Kiselyov’s scheme implementation. In an inversion of Knuth’s famous line, the code seems to work, but I don’t understand it.

Delimited continuations have two operations. prompt marks a continuation, when the continuation is invoked, it will return to where prompt was called. control allows us to capture the continuation.

It’s best to demonstrate this with some examples. prompt on it’s own is a no-op. <div class=’bogus-wrapper’>

<figcaption></figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 </pre></td><td class=’code’><pre>DelimR.prompt { 123 } # => 123 </pre></td></tr></table></div>
</div> Inside of prompt, you can call control, and pass it a block that receives a continuation as an argument <div class=’bogus-wrapper’>
<figcaption></figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 </pre></td><td class=’code’><pre>DelimR.prompt { 1 + DelimR.control { |k| k.call(2) }} # => 3 </pre></td></tr></table></div>
</div> k captures the computation that surrounds control inside of prompt. If we don’t call k, that computation is lost <div class=’bogus-wrapper’>
<figcaption></figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 </pre></td><td class=’code’><pre>DelimR.prompt { 1 + DelimR.control { |k| 2 }} # => 2 </pre></td></tr></table></div>
</div> And finally, the most exciting part, <div class=’bogus-wrapper’>
<figcaption></figcaption><div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 </pre></td><td class=’code’><pre>DelimR.prompt { 1 + DelimR.control { |k| k.class }} # => Proc </pre></td></tr></table></div>
</div> This is really cool! In delimited continuations, k is a Proc, which is Ruby-speak for a function. Delimited continuations are also called composable continuations, because you can compose k like any other function.

Here’s an example:

1
2
DelimR.prompt { 1 + DelimR.control { |k| k.call(k.call(k.call(2))) } + 7 }
# => 26

How did 26 get there? The way to think about this is to realize that k captures the execution around control. In this case it’s k = lambda { |x| 1 + x + 7}. So, in the above statement

1
k.call(k.call(k.call(2))) = 1 + (1 + (1 + (2) + 7) + 7) + 7 = 26

Delimited/composable continuations are really cool and powerful abstractions. Next time, I’m going to show you how to implement generators and co-routines with them!

Doorbot Overflow

Today was presentation day at Hacker School. I have a 10 minute talk about “building a better doorbot” which was secretly a talk about exploiting stack buffer overflows. People seemed to enjoy it.

The slides are available here, and the source code is here.

Hacker School: The First Three Weeks

For three weeks now, I’ve been at Hacker School. Hacker School is hard to describe, they call themselves a “writer’s retreat for programmers.” Personally I prefer “programmer summer camp,” mostly because I have no idea what writer’s retreats are like. Basically it’s a collection of people working in a self-directed way to improve their skills as programmers. They accept people of all skill levels, as long as you have programmed before. I’ve heard “but Max, you already know Ruby on Rails” from more then one person when telling them I’m going to Hacker School, so I think I should let you know that Hacker School doesn’t have a curriculum, isn’t a bootcamp, and I’m trying to write as little Ruby as I can get away while here.

I have a lot to say about what it feels like to go to a Montessori school for adults, but I’ll save that for another blog post. This is going to be a inventory of what I’ve been working and thinking about while here, and some of my goals. One of my goals coming in was to blog a lot. I haven’t done it, but I hope this will the first of n Hacker School blog posts (for sufficiently large n).

What I’m Doing

I’ve started a lot of projects while here, but they fall into two main categories. Courses and Projects.

Courses

  • I started Write Yourself a Scheme in 48 Hours with another Hacker Schooler here. I’m finding that I’m not getting a lot of out of it — I’m running into a lot of issues that would be solved with a more traditional Haskell resource, so to that end,
  • I started Yorgey’s Haskell course here
  • I started working through this exploitation course.
  • I signed up for Dan Boneh’s crypto course which starts tomorrow.

This above is very ambitious, and I fully expect to not finish most of these. I’m pretty sure I’m not going to come back to the Haskell Scheme interpreter course. I would like to finish the Haskell and exploitation class. I’ve started the crypto class many times before already, so there’s that.

Projects

  • To prove to myself just how much better I understand Ruby then Haskell, I wrote a very simple Scheme interpreter based on Norvig’s lispy
  • My main project so far is implementing an emulator for the MSP430 in clojure.

Emulator

The emulator project has been taking up most of my time here, and it’s worth talking about it more. The MSP430 is the chipset used in the MicroCorruption hacking game. Working on the emulator has helped me get better at reversing the MIPS assembly used by the processor, and I finally got to the last level after a 5 month hiatus.

I have two directions I want to take this emulator in. First of all, I have started reading papers about using SMT solvers in binary reverse engineering and exploitation. I would like to develop some heuristics for solving the microcorruption challenges automatically. Since I already have an emulator, the next step would be to emit SMT formulas based on execution traces. I don’t actually understand how to solve the problem deeper then the above sentence, so the real next step is to read more papers.

The other direction I have been thinking about is to port my emulator from Clojure into Clojurescript and build a web-based UI around it. The microcorruption game has a web based emulator, but the emulation actually happens on a sever and the browser provides only the UI. I have this vague idea of using colors to map display bytes in memory and show a buffer overflow as mixing colors. That’s about all I got though, but it’s a good excuse to learn Om.

Future posts

Next time I’ll explain how the biggest lesson I learned from writing a emulator in a functional programming style was about testing and talk about writing my first (!) clojure macros.

Thoughts On Bsidesto

** You can also find this post on my consultancy’s blog here **

Last month, I helped organize a security conference in Toronto called BsidesTO. I’ve attended and volunteered at my fair share of conferences, but this is the first time I’ve had an integral role in throwing and event of this scale.

One day, two floors, 14 speakers, and over 150 attendees. It was a blast. An exhausting blast.

Bsides. is a brand for security conferences around the world.

What is BSides? Each BSides is a community-driven framework for building events for and by information security community members. The goal is to expand the spectrum of conversation beyond the traditional confines of space and time. It creates opportunities for individuals to both present and participate in an intimate atmosphere that encourages collaboration. It is an intense event with discussions, demos, and interaction from participants. It is where conversations for the next-big-thing are happening.

The Toronto security community had long wanted a Bsides of its own to compliment the larger SecTor conference. 2013 was the first year that things came together and a successful Bsides in Toronto was launched.

If you build it they will come

Conferences without speakers are just parties. Which isn’t a bad thing, but we’re throwing a conference damnit! To be a conference, someone has to talk.

At first, getting enough speakers concerned me the most. Having spoken at conferences before, I know how harrowing it can be to put yourself out there in front of a crowd. Because we were starting a brand new event, I was constantly anxious that no one would want to speak, thus forcing me to spend 6 hours performing magic tricks to entertain the attendees.

This worry was entirely unfounded. I had no idea how many smart talented people are willing to show up to a hitherto unknown event with their research and perspectives.

We had an amazing group of speakers show up, and I’m proud of all of them for making the conference the success that it was.

The other kind of speakers matter too

No matter how much you plan ahead, something will go wrong.

We ran the conference on two floors of the Monarch Tavern. We piped audio and video from the talks to televisions upstairs, so people could have a lounge like atmosphere while they watched the talks.

I still think the model was solid. The “Hallway Track” is always a great experience at conferences. We wanted to create an atmosphere where you could converse with your friends while still paying attention to talks and not bothering other attendees.

There were some issues with the audio quality upstairs, and my main lesson learned for next year is to improve the A/V experience as much as possible.

Sleep

Sleep is important. BsidesTO happened to be on the night of Nuit Blanche. If you went out that night, I’m impressed. I for one went home and slept for 36 hours.

In conclusion

Organizing BSidesTO was one of the best experiences I’ve had in 2013, and I hope you had a good time at the conference as well. My eternal thanks to everyone else involved: Jamie, Dave, Ben, Phill, Laura, and the staff of The Monarch.

Hacking Letterpress

You can also find this post on my consultancy’s blog here

Letterpress is an iOS game that came out a few weeks ago and immediately became popular enough to take down Apple’s GameCenter. It’s a cross between Scrabble and Go. The game is played on a board made out of 25 letters and players take turns building words in order to capture the letters they use.

I was hopelessly addicted to Letterpress until I figured out how to win consistently.

winning

As it turns out, letterpress’s dictionary is stored on the device. By simply adding words to Letterpress’s dictionary, you can register any combination of letters as a valid word.

Inside your iPhone, the dictionary is spread across a series of text files located in /<Letterpress folder>/Letterpress.app/o/[ab-zz].txt. For instance, ab.txt contains all the words that begin with aa, and so on and so forth.

However, digging around a bunch of text files is no fun, and so I decided to write a tool to help me out.

By the way, the author of Letterpress does know about people cheating this way.

Automating Letterpress cheating

First of all, it’s a common misconception that you need to jailbreak a phone in order to access an individual app’s files. Tools like iExplorer allow you to, among other things, access an app’s directory and modify the files there on any iPhone. (It’s my understanding that they’re using undocumented calls in the library iTunes uses for syncing in order to pull this off.)

Since I didn’t want to rely on a commercial tool like iExplorer, I decided to use libimobiledevice. Libimobiledevice is an open-source library for talking to iDevices over USB. It’s capable of providing access to the filesystem, the iPhone internals, and much more. Libimobiledevice supports both OS X and Linux.

I wrote a ruby gem that acts as an adapter for libimobiledevice and exposes some of the API calls in an object-oriented way. It’s available on github as imobiledevice. So far, I have implemented only the small subset of libimobiledevice that I need, but I definitely welcome pull requests.

Once I had a ruby wrapper for for libimobiledevice, it was simple to write an app that adds arbitrary words to the Letterpress dictionary. I call it letterpress-lexicographer. Here’s how it works:

Is this a word?

Before

Shucks!

1
2
3
4
5
6
7
8
9
10
./letterpress-lexicographer.rb
 [*] Connecting to iDevice
 [*] Connected to iDevice. UDID:REDACTED
 [*] Accessing Letterpress app
 [*] Accessed Letterpress app
 [?] What word would you like to add? (/q to quit)
  -> szug
 [+] Reading word-list /Letterpress.app/o/sz.txt
 [+] Inserting word szug into word-list /Letterpress.app/o/sz.txt
 [+] Successfully added word szug.  You can play it now!

## Let’s try again After

You can find the app here. Please enjoy responsibly.