Friendly Robot Overlord

I read an article about a recent wave of card skimming attacks. The bit I found interesting was this bit:

NSW fraud squad head Detective Superintendent Colin Dyson:

"There is sometimes a lag between PINs being compromised and used," he said. "If someone whose details are skimmed changes their PIN quickly, the data can be useless to the criminal."

Now if my understanding of bank card security is correct, then changing your PIN will do absolutely nothing, and if your card has been skimmed, then you will want to speak to the bank. Of course, it is quite possible that I'm not quite with the times, and it is sound advice, so here goes with my explanation of how I think it works:

1. You put your card into the ATM
2. You type in your PIN
3. The ATM reads the magnetic stripe on the card and reads:
   • The card number
   • Expiration date
   • A random number (a nonce)
   • Your "PIN offset"
4. The ATM then takes most of the data it read (but not the PIN offset) and sends it to a special secure cryptoprocessor.
5. The cryptoprocessor encrypts the data using 3DES, and a very secret "master PIN", known only to the bank.
6. The encrypted data (longer than 4 digits) is converted into your card's "natural PIN" (4 digits), by a fairly straightforward process.
7. The resulting "natural PIN" is output from the secure cryptoprocessor to the less secure innards of the ATM.
8. The "PIN offset" is added to the "natural PIN" (without doing carries, so 2468 + 2468 = 4826)
9. This number is compared to the number you typed into the ATM, if it matches you are authenticated.

When you go to an ATM and change your PIN, you are just changing the PIN offset, your cards natural PIN doesn't change, and you could even do it at home if you had a magnet and a steady hand :-). If your current PIN is 1234, and you want to change it to 2222, then you read the PIN offset on your card (lets say it was 6789) and (without carry) subtract the new PIN (6789 - 2222 = 4567) and add the old PIN (4567 + 1234 = 5791). Write this number as the PIN offset and you are done.

So, in the scenario that you have your card skimmed, then the attacker knows what PIN you typed in, and what the PIN offset was. When they reproduce the card, it will have the PIN offset from before you changed your PIN, so they can just use your old PIN.

So it is possible that they have changed how it all works. Or maybe just a slight change (e.g. store the nonce at the bank also, change it when the PIN changes, and check that it matches when authenticating). However, this slight change actually changes a whole lot of the security model, because in my model all authentication is done inside the ATM. I can't imagine that making this change would be easy.

A quick pointer for anyone who is embedding python into a C application. I found that the useful looking example code didn't work as described. When I ran it I would get:

$ ./call multiply multiply 3 2
ImportError: No module named multiply
Failed to load "multiply"

Even though I could run:

$ python
>>> import multiply
>>> multiply.multiply(3, 2)
Will compute 3 times 2
Result of call: 6

The problem is that sys.path is different between the two environments. In the C code, it doesn't include the current directory. You can fix this easily:

Py_Initialize();
PyObject *psyspath = PySys_GetObject("path");
PyList_Insert(psyspath, 0, PyString_FromString(""));

Hoepfully this will be helpful to someone.

I haven't finished the application that is actually using this (I'll post it when done). But I'm not crazily impressed by the Python C-API. A few examples:

• The fact that I'm writing this post (maybe it is something different in the Ubuntu python distribution)
• Not enough consts: Both PyImport_ImportModuleLevel() and PyImport_ImportModuleEx() take "char *name" as a parameter. If they do modify the values pointed to, then it isn't documented how. If they don't, then they should be marked const.
• Inconsistent naming: PyImport_Cleanup() is documented as "For internal use only". Nearly every other internal function (like _PyImport_Init) has a name starting with an underscore.
• python-config: It would be much better to use pkg-config like every other library. It would also be nice not to add all sorts of flags which have nothing to do with compiling applications that use this library. For example, the --cflags option adds "-g -DNDEBUG -g -fwrapv -O2 -Wall -Wstrict-prototypes -fno-strict-aliasing" - none of which should be needed. Also, running "python-config --cflags --ldflags" silently ignores the "--ldflags" option.
• Bug reporting non-obvious. The number 1 hit on google for me for "python-config cflags" is the bug report for the previous point. Maybe I'm dumb, but I can't see any way of commenting on this page, to help out.

I'd like it if things got more pleasant from here, but I'm not holding my breath.

Google street view car taking a picture of itself:

I'm not a big user of street view, so maybe this is more common than I realise. On the other hand, it did make me realise how cool it is that it works so well everywhere else.

I got a new toy last week. Today I discovered that the colours on it match the ubuntu palette.

I thought my computer was being sluggish, and I didn't know why. It turned out that it was just my left mouse button dying, and hence the computer seemed unresponsive.

Now I have the left/right buttons switched, and for some reason, it is putting my mind into "whacky input mode", and I keep on thinking the keyboard is dvorak.

For the cube, it is pretty much the same as any other > 3x3 rubik's cube, except bigger and more awesome. With the larger cubes, if you solve them the way I do (and I think most other people do) you get parity issues, where you get really close to the end, and then realise that some pieces are out of place and if you just use the set of moves you have been using, then you won't be able to fix them. Up until a few days ago, my solution had been to scramble the cube and try again.

Wikipedia originally made me think that it wouldn't have parity issues:

Because the centers, middle edges and corners can be treated as equivalent to a 3x3x3 cube, the parity errors sometimes seen on the 4x4x4 and 6x6x6 cannot occur on the 7x7x7 unless the cube has been tampered with.

But it was just referring to the parity issue you get with the even sized cubes that you don't discover until the very end. With the 5x5 and 7x7, you realise there is a parity problem a bit sooner, but it is still there. My first solve I got lucky and had no parity problems, which confirmed my misreading of wikipedia. The second time around, I had a double parity problem, which made me think that I should get a method for deterministically fixing the parity problems (which I have now).

I have a square-1 puzzle which I've solved once. Unfortunately my algorithm wasn't general enough to work all the time, and I don't have a good sense for probabilities on those puzzles, so I don't know what the chances of it working are (my guess would be 1/8 or 1/16). I think my big problem with the square-1 is that it is difficult to remember the state of the puzzle before you do a move sequence, so you can work out what has changed. Even notating a move sequence is difficult. (though I don't understand the notation people use for rubik's cubes either).

I tend to accumulate lots of junk in my home directory. Today seems like a good day to get rid of it. Occasionally I find a quote funny enough to save in case I need it later, other times I need to run a quick program (or see if something compiles), basically there is lots of garbage, but hopefully some of it will be amusing enough. So presenting the slightly more interesting things which I've just deleted:

Quotes

"As old hands will be well aware, it's not a new C standard without an entirely new meaning for the static keyword." - Peter Seebach

"Too many errors on one line (make fewer)" - Apple MPW C compiler

"Open letter = Can't find your email address" (I'm not sure who wrote this)

Media

An old wallpaper I used to use.

Some drum patterns (these were done in rosegarden a while ago using a different drum patch, so they sound nothing like what they sounded like originally)

Various attempts at ripping just the audio track of a dvd. Why can't someone make this easy (bonus points if each chapter gets put into its own file).

This was taken from a log file I had of a Sony AIBO running around when I was at uni.

Other

Web site and executable served by a storm worm infested computer. Just out of curiosity.

Instructions for the automatic timer I use to turn my air conditioner off at night.

Rant about whitespace dependance in programming languages and why I don't like it.

One of the files I included in my vim configuration (which I shouldn't have deleted)

Programs

A program for finding square triangular numbers (like 36 = 6 * 6 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8)

This snippet (and testing code to make sure it works in the range I needed):

int v = i;
v--;
v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;
v++;

(probably from Bit Twiddling Hacks)

And finally:

cat /*dev/null; echo "Happy New Year"\!
cat <<c*/ /*dev/null | cat > /dev/null
c */ () {} /*
c */ main() { cat(); printf("Happy New Year!\n"); } /*
17      format('  Happy New Year!')
         write (6,17)
         stop
         end
c This program runs in four languages with the same effect.
c The languages are C, Fortran, C Shell and Bourne Shell.
c Written by Vadim Antonov, avg@hq.demos.su
c*/

One of the features in the latest version of ubuntu is a really simple idea for installing software. You just make a link, like this one and when the user clicks on it, they get a prompt offering to install the package, if they say yes then it gets their password and installs it without any fuss.

Because it is a new feature, and it is pretty simple to understand, some people have gone a bit crazy with it - which is cool. But, a usability problem comes up when you have no idea what it is you are actually installing:

It is difficult to answer this question meaninfully. My thought process would be that it uses qt (which is a GUI library), has a gui (well I already suspected that from the qt part), and does something with "pfs", which according to google is "Professional Freight Services". But since all the packages in Ubuntu have a description associated with them, we can just add an extra bit to the interface:

So we can find out what it is.

Adding such a feature is quite simple, and you'd hope that with my computer science degree and years of experience that it wouldn't be much of an issue. So, I downloaded the code for it, added the new bits and then generated a file which says what changes I made, so then someone can integrate it into the main codebase that everyone uses.

Unfortunately, I tend to get really stupid when it comes to the final step of getting things integrated. My understanding of things is that every patch has a 'bug' that goes with it. So for a patch to be accepted, it needs to be fixing something. So I went to the place that handles all the bugs and found this:

There are currently no open bugs.

Now I don't think for an instant that a newly added feature will have no open bugs, so I look around and find on the overview page that it "Doesn’t use Bugs". So obviously the bugs are tracked somewhere else. Because I get stupid here, I have no idea where to look.

This happened yesterday, so today I thought that I'd give it another shot. So I google for the bug page again, and find this:

1 - 15 of 15 results

On a page that looks otherwise very similar to the one yesterday (which is also similar to this one). There I found that someone had already had this idea, so I put my patch in with that bug, and I guess if it gets accepted then we'll see it in ubuntu later.

The reason all of this is interesting to me is that I think contributing needs to be really easy - even if I'm really dumb. I've been scared off reporting bugs for some software packages before because I'm faced with screens like this:

I don't mean to specifically bag out one group. But, I can't imagine many people being able to correctly answer the question about what subcomponent they are talking about.

But it is a bit of a balancing act. The developers want the bugs neatly categorised by the users, and the user just wants a textbox where they can rant about whatever. I don't think I've dealt with a system where you can report bugs without logging in, but I think that is important. If someone is reporting a bug, I think you need to make it as easy as possible for them, and then have slightly more knowledgable people come along and do the categorisation. The problem is that that is a sucky and boring job for most people, so it is a bit of a tough sell.

I think in the case of the form above, the improvements I would make would be:

• Remove the requirement for having an account
• Give every field an 'unsure' option
• By default, hide the fields other than the summary and the description
• Add an (optional) email address field for a non-registered user, so they can stay in the loop

I think it is a lot easier to categorise a vague bug description than to work out what a user was about to post, than to guess what the bug was that a user was going to post, but then didn't because they couldn't be bothered to figure out what hoops they need to jump through.

Out of curiousity, I turned on the setting in firefox that asks you about every single cookie that a website wants to set. My thinking was that it would be annoying for the first few weeks, and then become tolerable (as it learns my preferences for the sites that I visit). The weird thing that I did notice was that when searching for various things on google, I would get requests for cookies from the website that came up as the #1 result, without me even clicking on the link. This made me a little nervous, as it seems like a case of my browser doing something that I didn't ask for, which is typically a sign of a security issue.

The cause of all this isn't very hard to understand. The html code which triggered my browser to visit another site was a link tag with a "rel" attribute of "prefetch": <link rel="prefetch" href="http://www.example.com/">. This is a hint from the webpage that we are probably about to visit http://www.example.com/ and that we might want to download that webpage now, so when we click on the link, then the page is ready to be displayed already. If it guesses correctly, it should speed up your web browsing lots, because you typically read a page before clicking any of the links on it, so if those links are already loaded before you click on them, then that will be great.

So what types of things could a malicious user do? The thing which comes to my mind is faking clicks on an ad (to get money), faking clicking on links as the user (if the user is logged into a website, then an attacker may be able to do stuff without your permission on that website). Those are the two big things I can think of, but when you look at what an attacker has to do, I think the threat is quite small. The main problem is that once the attacker is in a position where they can get your browser to do the fetching of a link behind your back, there are heaps of other ways they could do the same thing (like an invisible iframe, or some javascript, or whatever) (actually they can do far worse things, since a prefetch doesn't mean that the html will be rendered, only downloaded). This is typically called a XSS attack, and it is a problem when someone can put whatever they want on your website. The comments form on this page has a very simple prevention of such attacks by stripping out almost everything.

Now, although I don't think this prefetch thing is a hugely big problem, there is a danger in having google doing prefetches (note that it doesn't do prefetches for every search, I think it is only for pages with a high enough pagerank - compare gmail vs friendly robot overlord). Suppose you are the person who gets the #1 result from google when people search for "bimijinklix" (which will probably be this site in a few weeks) and your page has a high enough page-rank to get prefetched. Once you have this, anyone who searches for "bimijinklix" will automatically download your page. Now all you have to do is change what they download, so instead of getting your page, maybe they get the page that they go to when they click on one of your banner ads (which earns you $400 per click). This is a bit more difficult, because at least at this stage, firefox doesn't follow redirects in prefetches. What you can do is modify your DNS records, so instead of going to the real server for your site, they go to the ad company's server. There are a whole lot of places where this can go wrong (and you only get to choose the IP address of the server, not the actual page requested, and any ad server worth its salt will always be handing out unique links every time an ad is requested, so it would just look like one ad being clicked on lots of times), and it is probably too complicated to be worth doing (especially since a user will probably click on the first link from google anyway).

The only other thing which I'm slightly nervous about is that the website you search for can get and set cookies without you visiting their site. So if you own the #1 spot on google for a particular query and you have high enough pagerank to get prefetches, you can automatically profile how many people are searching for a particular keyword, and you can track how many times an individual does such a search.

You can turn this off if you don't like all this stuff (go to about:config and search for "prefetch"). I'm not sure, but you might need to restart firefox to get it back on. I can't seem to get it to work now I've turned it off. I will be keeping it on, since the risks are so minor, and I'm blocking nearly every cookie now, so there isn't much of a privacy issue.

• I had an office space like moment yesterday. For those who know my working arrangements, I have it pretty good only working 4 days a week. For some reasons, the boss asked me to come in on Friday. 5 days is way too many days in a row to work, I am so tired now because of it. To anyone thinking of getting a job, ask for 4 days, you won't regret it. To anyone who has a job, next time they offer you a raise, ask for a cut in hours. Make 4 days a week the standard.

• I still haven't fully mastered the 4x4 rubik's cube, I can solve it all the time 50% of the time, so my algorithm is basically 'solve it as best you can, if this fails (50% chance), scramble and try again'. I'd like to make my algorithm a bit more deterministic, but the final parity error is very stable - all of the methods I've used to mess up the cube have just got me back to the same position. I know that shortish solutions exist, but I'd even be happy with a longish solution (provided I can remember it).

• I think most programmers don't like writing applications, they prefer solving problems. The part where you have to actually build an interface to the outside world is so boring compared to the actual solving of the problem. I can't decide what the solution is. It could be to turn everyone into programmers, so you don't need the normal-person-usable interface. It might be to make interface building fun (I'm not just talking about graphical interfaces here either). It might be to make some sort of automated interface builder. The programmer in me knows that this solution would be the most fun to implement, but I don't think it is very easy to do well (I'm picturing some system where you give it a description of the data you want, and it can turn that into an API, a command-line interface, a GUI, an argument-taking text based process, an ncurses thing or whatever). The problem is that it needs to actually understand the meaning of the data it is collecting, or else the interface won't make much sense.

• Driving regularly seems to make you think about driving lots. I'm wondering what the roads would be like if everyone drove at the Nash equilibrium. I suspect that there would be larger gaps between cars, less lane changing, less braking, and faster taking off from a red light. Actually, my guess is that there is no equilibrium, and if everyone was driving in a way which minimised transport time for the whole group, then a greedier more aggressive driving style would be able to have shorter trips than the average driver.

• I discovered the problem I was having with my stealth distortion. It was just normal boring distortion, being added in a place I didn't expect. My volume control goes up to 11, and the setting I had it at (81%) was just over unity gain (which is at 80%), so it was just clipping any samples which were very close to clipping. Quite boring, but whoever thought it would be a good idea to have a volume control that goes past 100% at this stage in the signal chain should have second thoughts.

• I'm puzzled by why people have anti-virus software but no backups. The big problem with having a virus on your computer is that it will delete/corrupt/encrypt your data. Sending spams to people is bad, but it doesn't get in the way of doing your work. Slowing down your computer is bad, but it doesn't destroy your work. There is also the other problem of hard drive failure, or laptop theft, or whatever. It seems to me that the problem is the same here - you can get a new computer, but it won't come with all the stuff you were working on before - that is the stuff with value. Why not just have a good backup system, so the cost of a virus infection is low (you just restore your backup)? Having an antivirus and no backup does nothing to stop your hard drive from failing. As a word of warning, for me as soon as I bought an external hard drive to backup to, my main hard drive was corrupted. Then the other day at work a guy tried out some backup software, and then the next day his machine wouldn't boot. Sometimes I think that thinking about backup stuff means that your computer decides that it doesn't have to worry.

• I recently joined a private health insurance fund, and when I was signing the forms and stuff, I crossed out all the stuff about allowing them to send me spam. Well, they are sending me spam and I can't decide what to do about it. I don't find it particularly annoying (it is all identified as coming from them, it all goes to its own address, and it is all marked as spam by someone before it gets to me, and I'm sure I could just ask them to stop sending one more time and they would), but it is the principle of the matter which makes it so difficult - and asking them to stop the normal way would just be boring.

So one day at uni I was taught about a thing called a zero knowledge proof. We were told at the time - "You probably won't ever need this, but it is cool so you are going to learn it." or something along those lines. Ever since then I've been trying to find an excuse to use one, and I finally succeeded the other day at work.

Basically, I had two parts of a program, and they each wanted to make sure the other part was there, and not some evil imposter program. There are boring ways to do this (A sends B a random string, B signs the string and returns it then vice versa) but, because they are boring (and vulnerable to a man in the middle attack) I didn't use them.

Instead, I generated a large graph (as in dots joined by lines, not bar-graph) where I knew a way to start from dot, and by following the lines, I could get to every other dot exactly once and return to where I started (this is called a Hamiltonian cycle). I then put the description of this path(*) in one of my programs (which will be called the prover).

When the other program (provee) wanted to check that the prover was actually the prover, it would make sure the prover knew what the path was. But, the prover couldn't just say what the path was, because if the provee was actually some jerk program just pretending to be the provee, so then it later can pretend to be the prover then we would have given up our secret.

So, instead of directly telling what the path was, the prover woud send the provee a new graph, one which has the same structure as the original graph (so it still has a Hamiltonian cycle) but where all the labels are different, so it isn't obvious which dot corresponds to which dot in the original. The provee then asks the prover either - "how did you get from the original graph to this?" or "where is the Hamiltonian cycle in this new graph?". It is only allowed to ask one of these questions, and the prover will only answer one question. The prover can easily answer both questions, because it knows how it relabelled the graph itself, and if it just relabels the dots in the secret path, then it can answer the second question too. Then the prover sends a new graph, and they repeat the process as many times as they want (each time increases the certainty - at first it is 1/2, then 3/4, then 7/8 etc).

This relies on two things being hard:

1. Finding such a cycle.
2. Finding how you got from one graph to another (called finding an isomorphism).

If you can do either of them easily, then the security of this whole thing falls apart.

So the first thing is - why is it called a zero knowledge proof? This type of proof doesn't tell anyone except for the provee anything except for the fact that the prover knows the cycle. Anyone else who listens to them talk will not have a satisfactory proof (the prover and the provee might have conspired before, so the provee only asks questions the prover will know the answer to) and the provee can't find out what the cycle was, because they would have to find the relabelling in the graph (which is hard).

So next, how hard is it really? Obviously that depends on the size of the graph.

So to get some idea how hard this really is, I wrote a program which would try to find a hamiltonian path in a random graph. It is slightly smarter than just trying every possible path, but it is by no means the best (it is especially inefficient since it is written in ruby).

I was actually expecting my program to be much faster than it was. It is a randomised algorithm (it picks a random path until it reaches a node that it has reached before, then it reverses the direction of the nodes found in the loop it just found, and keeps trying. Every now and then it restarts the search.

So there is a chance that it will be lucky and find the solution straight off, or it could be very unlucky and never find the solution.

My very unscientific results:

A graph with 50 nodes and 50 edges takes 0.0 seconds (there aren't many choices)

A graph with 50 nodes and 60 edges takes 0.6 seconds

A graph with 50 nodes and 70 edges takes 3.7 seconds

A graph with 50 nodes and 80 edges takes 0.8 seconds (lots of different answers now)

A graph with 100 nodes and 120 edges takes 11.2 seconds.

A graph with 100 nodes and 150 edges takes more than a minute.

Now I'm going to bed. Don't rely on these results if you are designing a crypto system.

(*) Technically it is called a cycle (because it starts and finishes at the same spot). But path sounds more natural.

My 4x4 Rubik's cube died the other week, so in my sadness I decided to make a new typeface by using my 5x5 cube. I put some paper on my desk to give a mostly white background, and then spelt out every upper case letter on the 5x5 cube. I took 2 high resolution photos of each (with the camera on a tripod and the cube in a mostly consistent spot) and then selected one of the images, resized it, stitched it with all the other images, edited out the desk and increased the brightness and saturation to bring you this:

(note that I stuffed up when I did the resizing and accidentally saved the resulting images as jpegs, so there is some dodgy artifacts there which are then made even more obvious when I increased the brightness and saturation, then to save bandwidth I did another round of jpeg compression at the end just for a laugh. There is a png file with the same name as the jpeg if you want slightly better quality, email me if you want the higher-quality source images.)

In pleasant news, since it was recently my birthday, I now have a new 4x4 cube, which has inspired me to go back to my search for a method to fix the "parity error". For the non-Rubik's cube people, when you have a normal 3x3 Rubik's cube, there are actually multiple solutions since the centre square on each face can be rotated differently. This isn't very obvious, because they are just blocks of solid colour, so they don't seem to face a particular direction. But if you get one of those stupid sudokube's then it is much more obvious - you can get all the numbers in the right spots, but have some of the 5's upside down or whatever. But even though there are 6 faces where each could be facing 4 ways there aren't 24 different solutions, because a lot of these combinations are impossible. I don't know enough about group theory to be able to be certain about this, but I'm pretty sure that rotating a single face somewhere means that you will rotate one of the other faces (this is talking about the final solved state of the cube - you can easily rotate a face without moving others, but that will mess up the colours). So I'd guess that there are 12 different solutions (even though they all appear identical).

With a 4x4 cube, you can think of it as a 3x3 cube, but where the middle face is split up into 4 and the edge pieces are split up into 2. So to solve it, you will have to get the 4 parts to each face back together, and the 2 parts to each edge together as well. However there are multiple ways you can reconstruct each edge and each face - even though they look identical, it is possible that you are reconstructing it in a way that means you have one of the edge pieces flipped. So you can think you have solved it, and do your thing, but then you get to the very end, and you have 2 edge pieces (corresponding to a single edge in the 3x3 cube) which are flipped. This is the parity issue, and to fix it, you can either find a website which gives you a sequence of moves you can memorize (boring), scramble it up and try again (50% chance of success) or try to figure out how to fix it properly. In the past I've used the scramble method, but now I feel like working out a method for fixing it with 100% chance of success.

In other Rubik's cube news, I figured out my own algorithm for solving 3x3 cubes, and that was a few years ago, and while I don't play with a rubik's cube every day, I would say that I thought I had done it enough to have encountered every situation. But last night when playing with a 3x3, I got into a situation where there was a hole in my algorithm (i.e. a situation I'd never seen before). It was easy to fix, but it still surprised me a lot.