Alice, Bob, and Mallory

Recently N. asked a question on a list that made my geek-senses tingle. He had a test with 12 levels of questions. The testee should answer 10 questions. If a question was answered correctly the level would go up and if it was not correct it would go down. If a level 12 was answered correctly, another level 12 would be asked and vice versa. The first question would be a level 6. N. wanted to know how many questions of each level he needed.

Pretty soon he got a correct answer and several wrong. One of the incorrect answers was, and I don't like to admit this, provided by me. I took the recursive route (which I very seldom do) and then tried to present the result in ASCII. I failed. The result from the algorithm in itself was correct but the presentation was simplified so much it failed to deliver the correct answer. Here it is:

             06
            05 07
          04 06 08
         03 05 07 09
       02 04 06 08 10
      01 03 05 07 09 11
    01 02 04 06 08 10 12
   01 02 03 05 07 09 11 12
 01 02 03 04 06 08 10 11 12
01 02 03 04 05 07 09 10 11 12

The problem is that this result can be read as if the testee could get two level 2 questions in a row but the rules forbids that.

Then I remembered reading about Graphviz and especially Ruby-Graphviz. That's what I used to generate the graph to the right. The graph itself is nothing but a visualization of all the possible question sequences. To find the answer that N. was looking for you can follow a level from top to bottom and count the number of times it can occur. I have to admit that it's far from the most convenient way but it works.

The result
5 of level 1, 5, 6 & 7.
4 of level 3, 4, 8, 9 & 12.
3 of level 2, 10 & 11.

I had to jump a few hurdles to get there. First my old Ubuntu-install, for unknown reasons, had some ancient version of libfreetype in /usr/local/lib/ that I had to remove. In the end an rm /usr/local/lib/libfreetype* would have been good. I also did a sudo ldconfig but I'm not sure that was necessary. Let's just hope you're on a modern system where a sudo apt-get install graphviz followed by sudo gem install ruby-graphviz will be enough.

The recursive code I wrote produces every single path the testee can take. A graph of that would be quite big since it's 1023 nodes. I then found out about strict digraph in the Graphviz DOT language. It sounded like a perfect fit and it was! One problem though, Ruby-Graphviz didn't seem to know about it. The power of open source software let me patch ruby-graphviz-0.9.18/lib/graphviz/constants.rb so that GRAPHTYPE included it

1
2
3
4

## Const: graphs type
 GRAPHTYPE = [
   "digraph", "graph", "strict digraph"
 ]

Another awesome power of open source is Grégoire Lejeune because only hours after me contacting him he added it to the GitHub repository.

Here's the code that produced the Rooted Binary Directed Acyclic Graph (or is it Rooted Directed Binary Acyclic Graph?).

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

require 'rubygems'
require 'graphviz'

@min_level=1
@max_level=12
@max_depth=10
start_level=6

@g = GraphViz.new(:G, :type => "strict digraph" )

def add_node(level, depth, parent)
  if depth<@max_depth
    current=[level, depth].join(",")

    sub=level<=>@min_level
    add=@max_level<=>level
    add_node(level-sub, depth+1, current)
    add_node(level+add, depth+1, current)

    @g.add_node(current).label=level.to_s
    @g.add_edge(parent, current) unless parent=="00"
  end
end

add_node(start_level, 0, "00")

@g.output( :png => "graph.png" )

With the current parameters this problem might not be the most exciting but I believe that by just modifying them slightly we would, again, reach a wall of complexity.

In browsers that supports the HTML5 canvas it's possible to read the raw image data. I figured that this makes it possible to encrypt images on the client. Why would one ever want to encrypt images client-side? One use case could be to send images to a server that only those who know the password can decrypt (host-proof hosting).

I used Crypto-JS to encrypt with AES and Rabbit.

First I get the CanvasPixelArray from the ImageData object.

1
2
3
4

var ctx = document.getElementById('leif')
                  .getContext('2d');
var imgd = ctx.getImageData(0,0,width,height);
var pixelArray = imgd.data;

1
2
3
4
5
6
7
8
9
10

function canvasArrToString(a) {
  var s="";
  // Removes alpha to save space.
  for (var i=0; i<pix.length; i+=4) {
    s+=(String.fromCharCode(pix[i])
        + String.fromCharCode(pix[i+1])
        + String.fromCharCode(pix[i+2]));
  }
  return s;
}

var encrypted = Crypto.Rabbit.encrypt(imageString, password);

1
2
3
4
5
6
7
8
9
10

function canvasStringToArr(s) {
  var arr=[];
  for (var i=0; i<s.length; i+=3) {
    for (var j=0; j<3; j++) {
      arr.push(s.substring(i+j,i+j+1).charCodeAt());
    }
    arr.push(255); // Hardcodes alpha to 255.
  }
  return arr;
}

1
2
3
4

var arr=canvasStringToArr(
              Crypto.Rabbit.decrypt(encryptedString, password));
imgd.data=arr;
ctx.putImageData(imgd,0,0);

A demo can be found here.

EDIT 2010-10-17

Warning I've noticed that the encrypted strings aren't compatible between browsers. At least not in between Google Chrome and Firefox. I don't know why.

I also tried to add deflate/inflate and that compresses my test image to a third of the raw size and in Google Chrome it also halved the execution time. In Firefox Rabbit got about 50% slower and AES about 50% faster with deflate/inflate.

Here's a demo of this.

EDIT 2010-10-21

Added a preprocessing filter of the raw image data inspired by PNG type 1 sub filter. Presented my idea to Fredrik and he returned a formula. Thanks!
The result wasn't what I had hoped for, a measly 6% smaller. I also tried to save the image as real PNG and that one is 20480 bytes. 20480*1.37=28057 bytes (Base64 overhead) and my homemade format is 38336 bytes. Not a fantastic result but not that horrible either.

Here's a demo of this.

I was interviewed in a swedish documentary called Att hacka en stormakt (To hack a Superpower). It's mostly in swedish but Brian Koref (US AF) and Tom Talleur (NASA) are interviewed in english. It can be streamed from SVTPlay (at least if you live in Sweden) until 2010-11-09.

It covers the cracking frenzy of a couple Swedish youths back in 1996. They happened to break into a server I was responsible for and from that server they logged in to a machine with a .mil-address. That's how we got involved.

The event has been covered before in a radio documentary called Svenska hackers (Swedish hackers).

As you may have heard, we've had a very close election here in Sweden. Today the Swedish Election Authority published the hand written votes. While scanning through them I happened to notice

R;13;Hallands län;80;Halmstad;01;Halmstads västra valkrets;0904;Söndrum 4;pwn DROP TABLE VALJ;1

The second to last field¹ is the actual text on the ballot². Could it be that Little Bobby Tables is all grown up and has migrated to Sweden? Well, it's probably just a joke but even so it brings questions since an SQL-injection on election data would be very serious.

Someone even tried to get some JavaScript in there:

R;14;Västra Götalands län;80;Göteborg;03;Göteborg, Centrum;0722;Centrum, Övre Johanneberg;(Script src=http://hittepa.webs.com/x.txt);1

I'm pleased to see that they published the list as text and not HTML. This hacker/joker voter seems to think³ they "censored" his vote/script. I'm not so sure about that, a more reasonable explanation is that they couldn't enter brackets, quotation marks, and so on.

There are also a couple of URL:s to online retailers and three votes on a conspiracy friendly site. I chose not to link to any of those.

This time the pen and paper scripting attack failed. Let's hope it stays that way.

PS. Someone noticed that there are no votes from Stockholm in there right now (2010-09-24). I asked the Swedish Election Authority about this and it turns out that The County Administrative Board (Länsstyrelsen) gets two months to register all the handwritten votes. There's a good chance that those will bring more attempts like the ones above. DS.

EDIT 2010-09-24
Links:
Aftonbladet DN SvD Expressen SVT - all in Swedish.
Slashdot BBC Wired

¹The name of the party, not a name of a person.
²Almost all Swedish voters use the preprinted ballots but you are allowed to write your own by hand.
³The site disappeared after this post was published.

There's more than one way to skin a cat and the same is true for looping in Ruby. This is a silly post with a silly number of ways to

print the integers from 1 to 10.

If you're a BASIC-programmer and are getting your feet wet with Ruby, you might end up with something like this.

1
2
3
4

while i<=10 do
   puts i
   i+=1
end

That and the following for-loop is not the usual Ruby way of looping.

1
2
3

for i in 1..10
 puts i
end

Instead rubyists often iterates over ranges or arrays with each.

(1..10).each {|i| puts i }

But for simple integer loops like this, we also have upto

1.upto(10) {|i| puts i }

and times.

10.times {|i| puts i+1}

Here's where I should've stopped but I can't help myself, I just have to show off with some Symbol#to_proc "magic".

(0..10).inject(&:p)

The above works because p is an alias of puts and & converts the symbol :p to a proc that is called with the numbers in the range as parameters.

The alias p also gives us, what I think has to be, the shortest possible way.

p *1..10

You could argue that it's a bad thing that there are so many ways to do something as simple as this. But I see no big problem here, if any at all, even though these are hardly all possible ways to loop over integers in Ruby.