Alice, Bob, and Mallory

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.

Keypads have obvious security problems and keypads accepting a stream of digits with no # or enter in between, while checking for the four digit long code, are even worse.

The important part is to not leak the digits in the code by wear or intentional markings because if they leak it's suddenly very far from 10000 combinations.

If the "lock picker" only knows that the code contains four digits there are 10000 combinations. Keypads accepting a stream of digits can then be opened in a maximum of 10003 keystrokes using the De Bruijn sequence. That is still quite a lot.

Below is a Ruby implementation of the De Bruijn sequence.

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

# De Bruijn sequence
# Original implementation by Frank Ruskey (1994)
# translated to C by Joe Sawada
# translated to Ruby by Jonas Elfström (2009)

@n=4
@k=10
@a=[0]
@sequence=[]

def debruijn(t, p)
  if t>@n
    if @n%p==0
      1.upto(p) {|j| @sequence<<@a[j]}
    end
  else
    @a[t]=@a[t-p]
    debruijn(t+1,p)
    (@a[t-p]+1).upto(@k-1) {|j|
      @a[t]=j
      debruijn(t+1,t)
    }
  end
end

debruijn(1,1)
print @sequence.join

It's not uncommon to find keypads with 4 of the 10 keys worn down and if you do you can be pretty sure that the code contains those four different digits. The number of possible combinations are 4! = 4x3x2x1 = 24. I got curious to see if there's a kind of De Bruijn sequence for this that brings down the 4*24=96 keystrokes. By scribbling in a text editor I quickly realized there's not a clean sequence. Not clean in the way that a sequence following the rules can be created. Also it's probably even quite daunting to present it as mathematically dense and beautiful as the De Bruijn but that could be my less than great combinatorics speaking.

I made a quick and dirty brute force hack to try to find a shorter sequence.

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

seq=[]
1.upto(4) {|a| 1.upto(4) {|b| 1.upto(4) {|c| 1.upto(4) {|d|
  seq << "%d%d%d%d" % [a,b,c,d] if !(a==b || a==c || a==d || b==c || b==d || c==d)
}}}}

s=seq[0]
seq.delete_at(0)
while (seq.length>0)
  next_code=(seq.select {|c| c[0..2]==s[-3..-1]})
  if next_code.empty?
    next_code=(seq.select {|c| c[0..1]==s[-2..-1]})
    if next_code.empty? 
      next_code=(seq.select {|c| c[0]==s[-1]})
      s+=next_code[0][1..3]
      seq.delete_at(seq.index(next_code[0]))
    else
      s+=next_code[0][2..3]
      seq.delete_at(seq.index(next_code[0]))
    end
  else
    next_code=(seq.select {|c| c[0..2]==s[-3..-1]})
    s+=next_code[0][3].chr
    seq.delete_at(seq.index(next_code[0]))
  end
end

The above code takes the first code "1234" of the 24 and then searches the rest of the array for a code beginning with "234". It finds "2341" and adds "1" to the end of s and continues to look for "341" and so on. Relatively soon there is no three digit match and then it tries two digits and eventually even that fails and then it gets the first one digit match. The resulting sequence is:

123412314231243121342132413214321

From 96 to 33 keystrokes. Not as effective as De Bruijn but still significant. Unlike De Bruijn I have absolutely no proof that this is the shortest one possible but it seems likely. Also notice that in the middle of the sequence we find "3121" and "1213". Those break the criteria of four different digits but they seem to be necessary to be able to enter the reversed mode. Try reading the sequence forward and backwards to see what I mean.

If the code only contains two digits it's gets even more trivial to try them all. There are 14 possible codes and by compressing those to one sequence you get down to 20 keystrokes.

Things get a little more interesting if only three buttons are worn. It turns out that the repeated digits can be placed in the code in six different ways.

0012,1002,1200,0102,0120,1020

That's 6x2x3=36 combinations and, maybe a little unintuitive, 12 more than if you are using four different digits. I compressed it down to 49 key strokes (16 more than with four different digits). Unlike the sequence for four different digits I can't find it with google and I know it's kind of security by obscurity but I still chose not to publish it here.

Be aware that if an attacker knows you are using a 0012-like code he gets a smaller space to search. 6x8x9x10=4320 instead of 10000. You have to weight the risk of button leaks against a code protocol leak.

Edit 2010-10-25
Uckelman noticed that the alike variable in the former version of the debruijn-script wasn't used so I removed it.

I made a couple of very bad mistakes in this article so I took it down. Hopefully I'm more on track in the sequel.

Check out Chris Eng's post on how he broke the code on the cover of the 2009 Verizon Data Breach Investigations Report. He makes it seem so simple and without making a big deal of it he also shows the tools and commands he used.