How do We Make Encryption More Accessible?

This post is about a program I wrote to publish public keys in gravatar images. You can try it (if you’ve got a gravatar account) here or look at the source here.

HELO
250 Hello, I am glad to meet you
MAIL FROM:˂professor.bob@staff.uni.edu˃

When I was at university, discovering that I could easily have a conversation with the computer that managed mail was great fun. There were rules for our conversation of course, but they all seemed very civilized; I had to start by saying HELO, and it would give me some equally polite response. After that though, it quickly became obvious that it was a little too trusting. If I said that I was giving it mail from the.president@theWhitehouse.gov, or some lecturer or even some cute girl that my friend liked and that the mail was for my friend, it would just say Ok, Bye and then go ahead and deliver it.

It doesn’t take a genius to see that there’s quite a lot of potential for mischief there. Things have moved on a little since then, but probably less than you think. Email for most people is still not much more advanced than passing crumpled notes around a classroom. It has many of the same features – anyone on the path from the originator to the recipient can read it, the originator can pretend they never sent it if it turns out that their affection is not reciprocated, or worse, it’s easy for someone to forge one and create all kinds of opportunity for comedy. I suppose the main difference is that instead of it being a classroom, we’re talking about the world, and instead of it being about whether Emma likes Richard or not (she did), it’s about every aspect of our lives, including money, job, family, etc.

PRISM logo

This has been in peoples minds recently with news that various governments are logging every word, not just of email, but of everything we do online. This of course opens up even more potential for mischief. Normal individuals have already used the no fly list as a way of punishing people they didn’t like, but given the NSA and others, a few well placed forged emails might be easier than the phone calls and less risky.

Anyway, I’ve got some great news. A bunch of guys have been working on this, and they’ve come up with a really clever system that makes it basically impossible for anyone you didn’t intend to look your messages to read them. I was telling my Dad about it recently, and he found it hard to believe, but it’s just a bunch of maths, not even as complicated as you might expect and it more or less completely solves this problem.

There is of course a catch. The catch is that this scheme was invented independently at least twice in the 1970s, predates the use of the word ‘internet’ yet for some reason normal people are still using systems that are much less deserving of trust than they appear.

One of the problems is that of ‘key management’. You usually use a pair of computer ‘keys’ to enable this kind of security and you need a way to make one as available as possible, and the other as secret as possible. This is not really within the realm of possibility for normal humans, who regularly lose their physical keys or ‘hide’ them in obvious places despite the fact that they secure a majority of their worldly possessions. That’s a simple metal token that can easily be carried everywhere with you and is always around when you need it, and can’t be copied quickly without you noticing (generally speaking). The computer keys are harder to change if stolen, and easier to lose. Basically I shouldn’t be trusted with anything as precious as my own private key.

The next problem is that so few people are currently using any better system that it becomes difficult to find people to communicate with. This is probably partially because of the third problem:

The third problem is probably just software. There is no software that doesn’t make sending and receiving encrypted messages a massive pain. On top of that it’s hard (but not impossible) to enable important features like search on encrypted data.

I came up with a few ideas of my own to try to make this more reasonable. I wanted to use images with public keys embedded into them, so that when you see the image of someone in your address book, you also have the means to send them private messages, and possibly little seal images that are your private key, so you drag them onto data to sign the data. I think a much more visual, drag and drop system stands a much better chance of getting people using it. I also wanted to build on top of services that people already know about. Bitcoin is an encryption based currency system that lots of people are interested in, and Gravatar provides a sort of directory of email addresses to images.

The perfect system that I imagine is something that is easy enough to use for people who aren’t very technical, builds on top of things like Bitcoin and Gravatar, and probably provides a mail service that can’t read your stored history of emails but allows you to search them quickly and automatically encrypts messages to people or alternatively sends them a link that enables them to retreive the message over https. I didn’t create that, but I have created a proof of concept to show that some of these ideas are pretty doable. It’s still very rough and ready, so it’s not something for the non technical yet, but I think it shows one approach we could try using to bring private communications to everyone. You can try it (if you’ve got a gravatar account) here or look at the source here.

SolarPosition

I’ve ported some C code designed to calculate the suns position into javascript. It’s all part of my plan to make a clock that shows the local sunrise and sunset times on its face.

Given a bewildering number of parameters (most of which you can just guess), it will tell you the time of sunrise, sunset and solar noon.

It also has a few methods for calculating time based on fractions of days, and the Julian Day (a commonly used system in astronomy).

You can try it out here.

SoleMirror

Particularly when I start a new web project, I often find myself wanting a javascript console that I can embed in a page. The consoles built into modern browsers are usually very good, but it’s also nice to have something useful for logging and visible on the screen as soon as the page is loaded.

As it happens, the excellent CodeMirror implements a lot of the functionality I needed and is easy to extend, so I added a few small pieces of javascript and ended up with SoleMirror, a CodeMirror javascript console.

You can use it at the SoleMirror console page or get the source at the github page. There’s even a bookmarklet that will install it into other pages.

This was just something that I put together over a couple of hours, so there are certainly inelegancies and I’ve not tested it in browsers that aren’t ‘fun’. Maybe you are just the person to improve it…

The Madness of the HTML5 FileSystem API

I’m quite excited about the possibilities that the FileSystem API opens up to web applications. At the moment it’s only implemented in Chrome, but the w3c has a spec and I hope to see it in other browsers soon. I’ve been working on a library to make it easier to use.

The FileSystem API is asynchronous, so you’ll notice quickly from the html5rocks guide that even simple tasks involve many many levels of nesting of callbacks to get them sequenced correctly. Take a look at this piece of code to create a file and then list all the files in the root folder:

window.webkitStorageInfo.requestQuota(PERSISTENT, 1024*1024, function(grantedBytes) {
  window.webkitRequestFileSystem(PERSISTENT, grantedBytes, onInitFs, errorHandler);
}, errorHandler);

function onInitFs(fs) {
  fs.root.getFile('log.txt', {create: true}, function(fileEntry) {
        fileEntry.createWriter(function(fileWriter) {

          fileWriter.onwriteend = function(e) {

                function listResults(entries) {
                    // finished!  Output the directory entries
                    console.log(entries);
                };

                var dirReader = fs.root.createReader();
                var entries = [];

                // Call the reader.readEntries() until no more results are returned.
              var readEntries = function() {
                 dirReader.readEntries (function(results) {
                  if (results.length < 1) {
                    listResults(entries.sort());
                  } else {
                    entries.push.apply(entries, results);
                    readEntries();
                  }
                }, errorHandler);
              };

              readEntries(); // Start reading dirs.
          };

          fileWriter.onerror = errorHandler;

          // Create a new Blob and write it to log.txt.
          var bb = new WebKitBlobBuilder();
          bb.append('Hello FileSystem API');
          fileWriter.write(bb.getBlob('text/plain'));

        }, errorHandler);
  }, errorHandler);
}

function errorHandler(err) {
    console.log("ERROR", err);
}

While this code can be tidied up a little, compare it with the bash commands to do the same thing:

echo Hello FileSystem API > log.txt
ls

There's quite a difference in length and complexity. You may not have noticed because some of it is split out, but by the time we get to the listResults function and the end of the task, we are 5 levels deep, mainly in closures.

Here's the equivalent code using this library:

var fs = FS.request(window.PERMANENT, 1024*1024);
fs.seq(
    FS.getFile("log.txt", true),
    FS.write("Hello FileSystem API"),
    fs,
    FS.list
).then(function(entries) {
    // we're done!
    console.log(entries);
}, function(err) {
    console.log("ERROR", err);
});

It's still not as simple as the bash code, but the nesting has been turned into sequential calls, and this gives us the power to compose and reuse pieces of functionality much more easily. It's actually an implementation of the Monad Design Pattern; Promises that gives us the ability to unwrap all of those nested calls.

Dancing-links: Understanding how the algorithm works

I’ve been writing a little recently about a program I wrote to solve sudoku and other problems using the dancing links algorithm.

This was how I explained it when someone asked for information about how it worked:


Firstly you have to understand Exact Cover. An exact cover problem is a problem where you’re given a bunch of choices, and a set of constraints and your challenge is to select a bunch of the choices that will fill every constraint exactly once.

For example, consider the case of someone creating their ice dance routine. They have a number of tricks that they need to show the judges, and don’t want to perform any trick more than once. They have a number of sequences which are groups of tricks that can be put together and they want to choose the ideal selection of sequences to cover all the tricks once. In this example, the constraints are that they must perform every trick. The choices are the possible sequences they could incorporate into their routine.

A nice way to represent problems of this sort is to draw out a table where the constraints are columns and the choices are rows, and you have a big X in cells where a particular choice fulfills that constraint.

As it turns out, given the right constraints and choices, sudoku can be described as an Exact Cover problem. It does involve 729 rows and 324 columns, which is perhaps why people tend not to use this technique when solving sudoku by hand.


Ok, assuming you’ve got that, now you need to understand Algorithm X. Knuth said of it “Algorithm X is simply a statement of the obvious trial-and-error approach. (Indeed, I can’t think of any other reasonable way to do the job, in general.)”. You can actually work through this by hand if you have pencil and eraser and the table drawn out in pen as I described in the previous section. Here’s my description of algorithm X:

  1. If your table has no columns, stop – you’ve solved it. If you’ve got a partial solution stored, then it’s actually a real solution, return it.
  2. Select a column (representing a constraint).
  3. Find a row with a cross in that column (representing a choice that fulfills that constraint). Add it to some kind of structure where you’re storing potential solutions. If you can’t find a row, give up – there are no solutions.
  4. Assume that the row you found in 3 is in the solution, so remove all columns that it have an X in that row. While removing all those columns, also remove all rows that have an X in the columns you’re removing (because you’ve already satisfied the constraint, so you’re barred from choosing something that would satisfy it again).
  5. Now recursively try to solve the reduced table. If you can’t, remove the row you tried from the potential solution structure, restore all the rows and columns you removed in steps 3 and 4 and try a different row. If you run out of rows, then give up – there are no solutions.

Now that you understand that, you can understand dancing links. Dancing Links is a way of implementing that algorithm efficiently. The key point of dancing links is that in a linked list, when you remove a node (which can be done efficently by modifying the pointers of its neighbours), the node that you’ve removed has all the information you need to add it back to the linked list (in the case that it turns out you were wrong when you guessed it was part of the solution). That plus the fact that if you make all your linked lists circular then suddenly you lose a lot of special cases is pretty much all dancing-links is.

Javascript Puzzlers

Here are a few javascript puzzlers. If you want to try them yourself, all of the statements below evaluate to true and you have to work out what values could make that happen…

Starting simply, name a value that is not === to itself:

    a !== a

And its dual – name two values that are different but do === each other. The second part of this puzzle is to provide a statement that can distinguish b and c. (clue – don’t look unless you’re stuck)

    b === c

What’s a value that seems to be the same as its complement (there are quite a few possibilities):

    !d == d

How about something that seems to give 42 more than you might expect (Can you find a second way of doing the same thing)?

    (e + 4 === 42) && ("4" + e.toString() === "42")

How did you do?

Dancing-links: The JS ecosystem

I recently created a sudoku and polyonimo solver using javascript, node.js, jasmine, jsdoc, git & github, cloud9 and heroku.

These programs and services are not perfect, but the fact that you can slot them together to provide a complete, production-ready, web-based development infrastructure for free is amazing.

Javascript

When you’re working on javascript code, there are a number of environments you might want to be able to deploy to. For Dancing-links, I wanted the code I wrote to work in the browser, in node.js and, to allow me to click ‘debug’ in eclipse, I wanted it to work in Rhino too.

As far as I’m concerned Javascript is the only real write-once-run-anywhere language.

Having said that there are also a number of ways in which it is deficient and perhaps the worst is in terms of loading code you depend on. Each of those three environments I mentioned requires a different solution. I approached this by creating a piece of library code that faked up the way that node.js does it on the browser and in Rhino, a sort of fake ‘require’ function. In node.js the order doesn’t matter, because everything is cached and if the required module isn’t already there, it goes away and gets it.

Unfortunately, the way most people write javascript, the order does matter in the browser, which means you can’t just concatenate files together without understanding what they mean. To reduce this complexity, and make it easier to use the result in more places, I’ve made a concerted effort to remove ordering requirements. This means never actually constructing anything during ‘definition time’. This means removing patterns that look like statics and singletons. Where you can’t help it, using lazy instantiation can get round some problems.

The other problem that crops up is inheritance. I allow myself the luxury of having a single ordering requirement: Utils.js will be included before anything else. In Utils.js I fake up require where it doesn’t exist and also provide an inheritance mechanism that sets up the inheritance prototype chain immediately or sets a trigger to set up the inheritance mechanism when the super class is included. This is a first cut at this, so I’m not completely happy with it yet, but I think something like this approach is the right one.

node.js

Node.js makes writing servers extremely easy. It has a large library of modules publicly available and easily accessed through the node package management tool.

It can be a bit of a shock for people used to the Java ecosystem though. Firstly in terms of cross platform, as things stand at the moment windows is definitely a second class citizen. Many important APIs don’t work correctly on windows – for example requesting the inode of a file will always return 0, which breaks code that uses that to check to make sure it doesn’t process files more than once. Jasmine used to fail on windows because of this, but they have graciously accepted my patch to use a library that doesn’t fall for this problem. Another nasty issue I hit was that the API for watching a filesystem for changes that is best specified and should be most compatible (because it uses a fallback behaviour where it is not available) is completely unsupported on windows – it just throws an exception telling you to use a much less specified API:

Providing filename argument in the callback is not supported on every platform (currently it’s only supported on Linux and Windows). Even on supported platforms filename is not always guaranteed to be provided. Therefore, don’t assume that filename argument is always provided in the callback, and have some fallback logic if it is null.

Like what? If you aren’t passed a filename how are you supposed to deal with a rename? The documentation is silent on this matter.

The fs.watch API is not 100% consistent across platforms, and is unavailable in some situations….. If the underlying functionality is not available for some reason, then fs.watch will not be able to function. You can still use fs.watchFile, which uses stat polling, but it is slower and less reliable.

…except of course you can’t, because on windows it just throws an error. Maybe if you were writing the code yourself this wouldn’t be quite so big an issue, but some of that large library of thirdparty modules I mentioned require this functionality to work.

My solution was to monkey patch it:

var os = require('os');

if (os.platform() == 'win32') {
	// change fs.watchFile so that it doesn't throw an error on windows.
	
	fs.watchFile = function(filepath, callbackfunc) {
		var old = fs.statSync(filepath);
		fs.watch(filepath, function() {
			fs.stat(filepath, function(err, newStat) {
				callbackfunc(old, newStat);
			});
		});
	};
}

which is of course far from ideal, but works well enough for my usecase. Another issue – the document talks about filenames and paths, but the code actually expects stat objects.

All this highlights another difference between the node community and other communities you may be familiar with. You will need to look at the source code of some of the modules you use. That’s just the way it is. Fortunately most of them are pretty reasonably coded. A common complaint of mine is that modules that expect you to use them from the command line tend not to provide a reasonable programmatic way of invoking them, and many tool-like modules don’t expect to be run more than once in the same VM and don’t provide the necessary API to clean up.

Node.js is amazing for writing servers very easily (and for integrating with some of the other tools I’m going to mention later), but I used it in dancing-links for two main reasons – the speed (much faster than rhino in eclipse) and as a build language.

When you are writing javascript you typically want to see it in a browser. You want the manual part of the build process to be at most control-s in the js file you’re editing and F5 in the browser you’re viewing your page in. However, you generally want a bunch of other stuff done in between the two, potentially like concatenation of separate js files, building the jsdoc, running the tests, obfuscation, perhaps building the .css files from some other format like less/sass/stylus. Then you need to serve all this to the browser. Setting up a node server to do all this is relatively easy (less than 70 lines) using mature libraries like express and connect-assetmanager.

For less webby builds, you might prefer to use travis.ci.

Node provides the node package manager, npm which makes it easy to declare and grab your dependencies as well as publish your own code to the public repository.

Jasmine

I’m not a great believer in making test code read like English. It seems that everyone is trying to do that these days with various contortions of the host language. I particularly hate fluent interfaces where the normal semantics of what functions and objects mean are broken. Code is code and should read like code. What I do like unequivocally though is test code that generates an English description of the code under test.

A CircularList,
  when newly created without any data,
    is empty.
    and a data item is pushed after it,
      toArray returns an array with only the new item.
      is not empty.
  when newly created with some data,
    has a next and a previous of itself.
    toArray returns an array with only itself.
    is not empty.
    and a data item is pushed after it,
      toArray returns an array with itself and the new item.
      returning a node that contains the data item
  when created with an (empty) header node and 5 data items,
    forEach calls its callback for all items (and their nodes) until false is returned.
    and the third node is hidden,
      toArray returns only the non hidden items.
      calls the onNodeHidden function once on the listener
      then restored,
        toArray returns all the data items.
        calls the onNodeRestored function on the listener
      and hidden is called a second time, it makes no difference;
        toArray returns only the non hidden items.
        calls the onNodeHidden function once on the listener
        then restored,
          toArray returns all the data items.
          calls the onNodeRestored function on the listener
    and a two item chain is spliced into it after the third node,
      inserts the new chain into the right place.

One place that jasmine is a bit of a pain is that really you would like everything at higher nesting levels to be recreated for every test (as Junit does for instance variables), however the lower nesting levels share things defined higher up. This means that to be safe, at most you declare the variables in the outer scope and all actual instantiations need to be done in a beforeEach().

What I’d like to do is generate HTML from the tests and serve the generated ‘spec’ with the documentation.

I did look at a number of other test frameworks, like Buster.js. My ideal requirements are

  • Can be run entirely in node.
  • Can be run entirely in the browser (but not capture mode) which means it can’t rely on node.js require behaviour.
  • Can be run by my webserver every time a file changes.
  • Creates a nice, readable spec document.
  • Works on windows as well as other platforms.

jsdoc

It’s lovely to have jsdoc automatically built from your code and served from the build web server. My experience is that if you aren’t doing something like this it’s very difficult for developers to take jsdoc seriously. Jsdoc implementations for node tend to be a bit fragmented, and none of them seem to have a nice programmatic API. I ended up copying a lot of code from the cli runner of one implementation and writing my own.

If you’ve already got a js project on github, you may already have a jsdoc site without realising it. Have a look at jsdoc.info.

git & github

I’ve mainly been using git for personal projects rather than for large distributed projects, so I haven’t had to get into it properly. I’m disappointed with the very flaky integration into eclipse and the apparent lack of decent visual merging tools. Hopefully these things will improve given time.

Github on the other hand is an amazing service, I’ve heard it called ‘facebook for nerds’. Providing public repositories for free, you can use it as a central point to share your code, easily clone and submit patches to other projects, serve the project website from it, use the wiki and issue tracker, view diffs, make smaller changes directly through the site…. The list goes on. Partly because it’s so useful, ecosystems have grown around it. The django guys said it best: Github is Rome.

I should mention too that bitbucket is also a good service, which might be worth checking out, particularly if you have a small group of friends working on a private project.

cloud9

Cloud9 is a web based IDE. What is most impressive is its excellent integration with node and git. I’d go so far as to say that for developing a project with node and git, you might well be better off developing it in your web browser on cloud9 than in eclipse on a windows machine. You can do all your normal git commands in it, and also run node servers and npm commands. You can edit the code then run the unit tests through the built in console. It also gives you a single click deployment (assuming you’ve got all the files set up correctly) to cloud production level servers like heroku.

heroku

If you have your files set up right, heroku will take your node server and run it on a single instance. You can scale up by configuring heroku to give you more processes, but that costs money. Still, you get a single node.js process for free, and that is plenty for even a moderate load. I don’t expect it to survive getting posted to reddit (although you could also easily set up cloudflare for free….), but for almost anything else it’s going to be fine.

the ecosystem

What amazes me is that you can develop the whole thing in cloud9, using github as your source repository, running your tests and dev server on cloud9 too, then deploy with a single click to a production grade server all for free and without installing a single piece of software on the machine you develop from (except possibly Chrome). You could run major projects from a netbook, or an internet cafe from anywhere in the world. The cost now for setting up and running experimental services is probably as near to free as it can be made, and I look forward to seeing what happens as people discover how empowering that is.

Playing on the CouchDB

Let’s say you’re playing with CouchDB and javascript. It’s great fun, but you’re in development mode, you want to be able to change a file and then reload in your browser without having to mess around uploading and deploying stuff.

The ‘proper’ way of doing this is probably to set up a reverse proxy so that your couchdb is visible through your development webserver, and all is good, but that sounds like a lot of configuration for a playing around kind of setup.

What you’d like to do is run a normal couchdb install on your machine, and use whatever you normally do for webserving (for just playing around, I tend to use a jetty jar I’ve created as it’s very light and easy, but you could equally use tomcat or whatever), and edit the javascript and html files in place. If you have this set up, you can’t usually load the javascript couchdb api from the couchdb server, since it uses an XHR to communicate with the couchdb server, and these are restricted to using exactly the host that the page is loaded from. The fact that the couchdb server is on a different port to your webserver stops it from working.

You can get around this by saving a simple html document as an attachment in your couchdb (any database). This html document is then loaded in an iframe, sets the document.domain to the hostname (removing the port), and then it passes the api object up to the parent window.

If you’ve attached that file to a document with id ‘document’ in a database called ‘webaccess’, you would then use it as below:

Tetravex

I’ve recently been playing a puzzle game called tetravex on Ubuntu, so I thought I’d write a version of it for HTML5. It’s designed to work on android phones and the iphone (only in vertical orientation at the moment), but if you’re using a modern browser you should see a working version of it below. The GUI still needs a lot of work, and I’m sure there are bugs, but pretty much all the functionality of the linux version is in there. On a phone, you can visit this direct link and then save it onto your homescreen to run it as an application. This should let it run offline too. It uses localStorage to store the high score table.

Update: Turns out it uses some features that Apple don’t support on iphone yet. I’ll try to make it more backwards compatible later. In the meantime, Chrome, Desktop Safari, Firefox and Android Browser should all work fine.