MD5/SHA collisions

Today has been a somewhat unusual day in the crypto world. Some people have found collisions in some of the major hash algorithms used today. In itself, it’s interesting but not earthshaking – after all, by their very nature, hash functions contain collisions. But a method for finding collisions in some restricted case could well lead to more general methods, which would get exciting.

Being a cynic, I tried to verify the results in the paper using the funky MD5 in 8 lines of perl, but I couldn’t recreate their results. That was a bit unnerving. However, this page explains the discrepencies. Once the paper has been presented, presumably all will become clear.

Double-press instead of shift

Here’s a keyboard idea, which I’m writing up here on the off-chance that MS hasn’t already patented it. I was trying to figure out a better way of entering left-parenethesis and right-parenthesis on my keyboard (since I used them all the time when I’m writing code (and also when writing blog entries)). Currently, I have to do the shift-9 combination which is poor because I have to move my fingers off their home keys, and also involves a nasty stretch. However, there doesn’t look like many better alternatives since I use all of the non-shifted keys regularly – I’d find it inconvienient if they got remapped to ‘(‘ and ‘)’. So if there’s no unshifted keys left then it looks like I’m always going to have to use some kind of shift key?

No, we can take inspiration from the mouse. I suggest using double-clicks on the keyboard as a way of entering indicating alternative inputs. So, two presses on the ‘9’ key in rapid succession would mean left-parenthesis and two presses in rapid succession on the ‘0’ key would mean right-parenthesis. Obviously this impacts on my ability to type “99” and “00” quickly, but in an average day I typed hundred of parentheses and hardly ever need to type “99” or “00”. On the rare occasion that I need to type them, I can simply leave a little pause (sufficient to exceed the double-click timeout) just like you do when you’re sending txts on a mobile phone without predictive texting.

Alternatively, you could use the length of time which the key was held down for to indicate an alternative input mode. Currently, almost all the keys will just auto-repeat when held down. How often is auto-repeat useful? For delete and the cursor keys it is often useful, but for the other hundred or so keys, it is less useful. So why not hijack that behaviour for more useful purposes?

Finally, we can use “chords” to indicate a whole different set of behaviour. Currently, if you hold down, say, “f” and “j” at the same time the computer will act as if you pressed “f” followed by “j” (or vice versa). It doesn’t notice that you deliberately pressed them both at the same time. If we make the computer respond differently to multiple simultaneous keypresses, we open up yet another set of possibilities for keyboard input without removing our fingers from the home keys. Effectively, we’re using the keys “a” to “z” as shift keys themselves. Clearly, you’d want to minimize the chances of triggering them accidentally whilst typing normal text so you may want to choose unlikely combinations (such as f+j) which are unlikely to occur in your normal typing (unless you write about fjords lots).

This gets rid of the need to move my hands off the home keys, and also gets rid of the awkward stretches caused by shift/ctrl combinations (although putting ctrl in the place where caps lock usually lives helps a lot too). Once I have figured out a way to get X11 to handle these cases, I’ll post it up. I also think it’s likely that keyboards from older computers used these tricks and more, but have been forgotten in the passage of time. Certainly the Spectrum used to minimize keystrokes whilst programming by automatically switching between modes as you typed, which was confusing to the uninitiated but quite efficient once mastered.

Hacking on USB

I like all-in-one chips. The BCM2040 is an all-in-one bluetooth keyboard/mouse solution. Connect it to a plain ‘ol keyboard matrix and hey-presto you have a bluetooth keyboard. I’m thinking about attempting to mod my twiddler chord keyboard into a bluetooth device using one of these, if I can get my hands on them.

Whilst on the subject of hardware, I notice that the Microchip PIC range now includes a couple of devices with USB support. This is cool because it means that it’ll be relatively easy to make my soon-to-be-built keyboard foot pedals into a USB device.

Refactoring Keyboards

After Thomas cunningly found a cheap way to get a smaller keyboard, I’ve been thinking about keyboards. I try to make myself conscious of how I do things and think about whether there’s a better way. I might not spend a lot of time thinking about keyboards, but I spend thousands of hours each year using one, and several of my friends have had crippling injuries related to keyboard use, so really it does merits some thought.

There’s at least two things to think about. Firstly, what physical input device is most useful for you. I spend a lot of time writing code and navigating code. I’m certainly not typing english text all day long. So it is likely that a keyboard design invented for people typing out memos is optimal for me? Unlikely, I think.

That’s a common problem with design of popular objects – economics causes a worse-is-better situation. Regardless of whether or not qwerty is Best, it’s unlikely to go away quickly because People have learned to use them and have little interest in learning something different. So, they’ll buy qwerty keyboards. And economies of scale makes qwerty keyboards cheap. People don’t choose a keyboard because it is Better, they choose it because it is cheap and familiar and requires no new learning. So that means that if you want to set away from the mainstream you’re going to have to spend more money because economies of scale are no longer shining their light in your direction. (Unless you are cunning like Thomas was)

Secondly, there’s the question of how you set up your software to make the most of your input hardware. I’m a big (x)emacs fan, mainly because it is easily mouldable into a tool which is useful for the work that I do. It becomes a tool for me, customized to allow me to easily do the things which I do every day. I watched myself for a week, noticing which tasks I did most often. Then I automated these tasks, and set up key bindings so that my common tasks were easily reachable with single keystrokes. Now when I want to push source code from my windows machine to the linux box on my desk and compile it, a single keypress launches unison to sync the files, then runs make/scons over ssh. That’s a task which I was doing several times a day. Now it’s a single keypress. I like “do what I mean” keypresses too. For example, I have a key-press that gets me to a shell prompt. I don’t care whether or not I was already running a shell – the computer will start one if needed, or switch to an existing one if possible. I don’t want to be hitting alt-tab, looking at the screen and figuring out how many times I need to keep hitting alt-tab to get to the right application or thinking about where the start menu icon for that program is. Do what I want, computer. But software is malleable and exists in a virtual world. We are physical beings and we communicate with the computer by hitting buttons and sliding around lumps of plastic.

So, back to the physical design question, unfortunately you have to weigh up the fact that you want a device which allows you to efficiently control your computer, but also one which won’t cause you discomfort and injury. Computers can be nasty things because they occupy your brain with interesting things, and you end up ignoring your physical body. In the past, I’ve been so involved in coding that my body has got really really cold. I only noticed when my fingers started getting less responsive from the cold and I started making typing mistakes! I’m really bad at noticing this gradual decrease in body temperature – I ended up putting a digital thermometer next to the computer. Anyway, here’s a quick experiment to get you thinking about physical design – try switching off your monitor and sit in your “at the computer” pose for five minutes. Without the internet to distract your mind, you’ll notice that sitting with your arms out on front of your isn’t a terribly natural or comfortable pose for humans. Now think about how many hours of your life you spend on front of a computer.

I’ve tried a few alternatives to the usual keyboard. I find the Microsoft “ergonomic” split keyboard to be pretty good, and I use one at work. I also have a twiddler chord keyboard, which I can use well enough to type english text at an acceptable rate, but it’d take a reasonable amount of customization to make it useful for programming. Tonight I found the Keybowl which is a kind of gesture keyboard. And there’s always the choice of where to put your keyboard – for example, on the arms of your chair. I also think that foot pedals could be interesting, not least because it’d be easy for me to knock some up and see how useful they are. If you could do shift/ctrl/meta/hyper keys on footswitches, then your fingers could get back to only ever hitting one key at a time. I find that scrollbars are one of the most annoying bits of gui which I have to deal with several times an hour. You have to zero in on a tiny bit of screenspace and carefully drag this wee thing around. A tilting footswitch would be ideal for this. I’d love to play with an eye-tracking system – I wonder if you can build one yourself without accidently burning your retina with a laser .. maybe you’d have to be careful to avoid repetitive looking injuries though. 😉

Webcams

I got a Creative Labs NX Pro webcam, but unfortunately there aren’t linux drivers for it yet. I did find a project which is developing a driver for zc030x-based webcams. They’ve managed to grab a still image from a webcam, so that’s hopeful. However, the driver only builds under linux 2.4 at the moment and I’m using 2.6.

First of all, I did a bit of reading about the kernel usb support.

  • There’s a skeleton usb driver (in drivers/usb/usb-skeleton.c). Under Documentation/DocBook there’s an article about the USB system.
  • drivers/usb/media/dabusb.c is quite a clean looking driver
  • USB programmers guide
  • Loads of great articles about porting drivers to the 2.6 kernel

I read through the existing code for the zc030x driver, and used Freemind to organise my notes about it.

Since then, I’ve crashed my computer more times that I can remember. Writing kernel code is very unforgiving. If you make a mistake, the whole computer will probably hang. I’ve ended up adopting a very different, even-more-paranoid-than-usual coding style, and have aliased insmod/rmmod to automatically run sync beforehand! But I’ve been making progress – the driver compiles, loads, creates the /dev file correctly, and responds to incoming data .. but I don’t think the webcam is being initialised properly yet. I need to do more snooping of the datastream under Windows to understand what needs to be sent when.

USB itself has been really nicely designed. The designers have obviously considered real use-cases and designed for these. For example, there are four different modes of data transfer, including isochronous (regular time interval, eg. for a webcam running at 15fps) and bulk transfer (eg. for a usb disk, which wants to use as much bandwidth as is available). When there are multiple devices plugged in to your PC, the USB system itself is responsible for arbitrating who is allowed to use how much bandwidth. The usb system knows that it’s better to drop a webcam frame entirely than to deliver it really late. On the other hand, it knows that it should stop files being copied to my usb storage stick if the webcam wants to send a frame. All of this happens behind the scenes, as far as a programmer is concerned. USB is not just an end-to-end pipe, like rs232 was. There’s a whole bandwidth/device management layer on top of that.

Oh, finally .. learning a new code always takes a bit of effort, but it can be made easier by using decent tools. Xref is a refactoring/navigation tool for C. If you’re working on a C program with emacs, and you’re not using this already then you must enjoy pain. Note that you don’t want to be browsing the kernel headers in /usr/include – you need to use the ones under /lib/modules/version/build. Here’s the options for xref to set this up.

[webcam]
  //  input files and directories (processed recursively)
  ~/Projects/zc0302/
  -D__KERNEL__
  -resetIncludeDirs
  -I /lib/modules/2.6.5-gentoo/build/include/linux
  -I /lib/modules/2.6.5-gentoo/build/include
  -I /lib/modules/2.6.5-gentoo/build/
  //  directory where tag files are stored
  -refs ~/Xrefs/webcam
  //  number of tag files
  -refnum=10