Posts Tagged ‘OpenBSD’

Newer Entries »

BitTorrent encryption, MSE basics

Sunday, July 29th, 2007

I have been working quite a bit recently on my BitTorrent implementation. My project is faring reasonably well so far - it can successfully download large real-world torrents at decent speed. In the course of development, I have been focusing solely on the core specification, as documented here. Having gotten support for peer connections - outgoing and incoming - working, I started to notice something. Some peers would send ostensibly random data to my client. Investigation of this led me to conclude these were peers using the Message Stream Encryption protocol.

I am not hugely interested in avoiding traffic shaping, but the encryption protocol looks like fun to implement and I’d like my software to be able to communicate with these funky peers (instead of just killing them, as it does now). I know very little about cryptography, but I know a little more now that I have begun implementing MSE. MSE really has two components - a Diffie-Hellman (D-H) key exchange to negotiate a secret, and RC4 stream cipher to encrypt the data. Both these functions are used in Secure Sockets Layer. However it should be pointed out that MSE is more about obfuscating the data to confuse traffic shapers than hiding its contents from prying eyes.

Fortunately for me, the OpenSSL library contains nice implementations of both D-H key exchange and RC4 . Before I can get to the nitty gritty of actually negotiating obfuscated streams, I had to make considerable changes to my software’s peer handling logic. I had written the peer response handler with quite hard assumptions about the nature of the incoming peer handshakes - for example, assuming the first byte would be the length of the protocol string. Furthermore I needed to add some timekeeping logic for each peer, because MSE handshake depends on timing for synchronisation. The initial peer handshake message is variably padded and so time must be considered to know when the message is complete. For example a MSE handshake from peer A may be considered invalid by peer B a) if A sent less than 96 Bytes within 30 seconds or b) if A sent more than 608 bytes.

My first step has been to re-work my peer handshake handling so that MSE handshakes can be distinguished and separately handled by the software, while traditional handshakes continue to work. Code to do this has been committed. The next step is to actually support crypto peers. For anyone curious about where the source code for my software is, I am not yet ready to release it. I have distributed it to a small group of testers to help iron out some of the bugs, but I don’t feel its ready for public release. I am being somewhat selfish and sitting on my personal project until I have polished it to where I want it to be. If you are really interested though, shoot me an email (niallo (*) niallo dot net).

Tags: , , ,
Posted in BitTorrent, Technical | No Comments »

BitTorrent basics - protocol etc

Tuesday, July 10th, 2007

I started working on a BitTorrent implementation in 2006. The protocol is kind of fun and there is a need for a lightweight UNIX implementation in my opinion. rTorrent is quite usable, but absolutely huge - something like over 40,000 lines of C++ last time I looked. My implementation is ~3,500 lines at present and has most of the needed functionality - although admittedly it will not support downloading of multiple torrents at a time, nor the fancy UI of rTorrent. Even assuming it doubles in size by the time its finished, that is still quite lightweight in comparison. It is written in C, Yacc and uses libevent - and its under the BSD license. I develop it completely under OpenBSD, although across multiple platforms (to weed out the endianness and pointer-size bugs). It should be easily portable to other systems with some glue (much like OpenSSH or OpenNTPd). Anyway, it has shaped up rather well and in fact I have been able to actually download some ‘real-world’ torrents with it. However, I still need to overhaul the network scheduler. Once I am satisfied with this part, I will publish the source code. The network scheduler is a complicated component - with numerous research papers on the subject! - and I plan to cover it in future postings.

For now, I want to post a quick summary of how BitTorrent works. I’m going to describe ‘vanilla’ BitTorrent - without distributed, trackerless operation and unofficial encrypted streams. The best complete “specification” I have found is this wiki page - the official specification being rather useless. Unfortunately, the official Python implementation sources are a neceesary reference at times also.

BitTorrent splits data into a number of units called pieces. Typically these pieces are 256K. Each piece has an associated 20 byte SHA-1 hash to verify integrity. The pieces are sub-divided further into what are called ‘blocks’ - typically 16K. Each peer has zero, some or all pieces. Metadata is distributed in .torrent files. Very likely you are familiar with downloading these files via HTTP and then feeding them to a BitTorrent implementation in some way. These files are encoded in a mixed binary/ASCII format called ‘bencode’ - which is a kind of mini-language supporting nested strings, integers, dictionaries and lists. Its actually quite a pain to parse in a language like C - it took me quite some time to write the Yacc parser. The metadata contains things like, number of pieces, piece sizes, hashes for each piece, tracker URL and filenames. Pieces are all zero-indexed. This gets a little complicated in multi-file torrents, where you must determine which file piece X falls within, and at what offset. My implementation uses mmap(), and has translation routines to nicely abstract these calculations away :-)

Each peer must initially ‘announce’ itself to the tracker, and is supposed to send further updates periodically. Communication with the tracker is done via HTTP GET, with the tracker returning a bencode’ed dictionary as its response. This response includes a list of other peers - whose addresses are in fixed-length (IPv4) binary format, making it a little difficult to use IPv6 for BitTorrent, at least without protocol changes. There are a variety of peer messages. Data is transferred in terms of pieces, offsets and lengths (block size). Peers tell each other which pieces they have by sending a bitmap - one bit per piece.

The basics of the protocol are fairly straight forward. Aside from some poor decisions in terms of the bencode format for encoding messages, it is not hard to code support. As I said above, things start to get tricky when it comes to peer communication strategies. One thing of note is that the most efficient algorithm for downloading pieces is believed to be ‘rarest first order’. To my knowledge, nobody is using a sequential download order - which is why partial BitTorrent downloads of audio or video data are notoriously unplayable.

Tags: , , ,
Posted in BitTorrent, Technical | 5 Comments »

Keyboard-only X, cwm hacks and Vimperator

Monday, July 9th, 2007

A few weeks ago, I wrote a short entry on some of the software I’d been looking at to reduce my reliance on the mouse. Specifically, I mentioned a window manager, cwm, and a FireFox extension, Conkeror.

Since I wrote that piece, I have refined my setup a little more. I found a Firefox extension called Vimperator which adds Vi-like keybindings. I prefer it to Conkeror mostly because it seems a little less buggy. Both Conkeror and Vimperator have a feature where you press a key and all links on a page get associated numbers (in the case of Conkeror) or letters (in the case of Vimperator). This feature enables you to very quickly visit links on a page. I found that Conkeror’s implementation of this feature would not work with certain focus-manipulating JavaScript used on websites, and also it would sometimes insert the HTML and CSS for these numbered links into HTML you were editing! In fact, because of Conkeror, I ended up with it’s numbered links embedded into an entry on this site - which was very odd and quite annoying. Conkeror also had a tendency to crash in some way which disabled all its keyboard shortcuts on windows, such that the only way to kill a window was via terminal - again, highly annoying. Vimperator is a little buggy still, but doesn’t seem quite so bad. Furthermore, Vimperator makes it easier to open links in a new tab and copy links via the keyboard. Finally, I feel more at home with Vi-like keybindings than with Emacs-like keybindings, and I think they are a little easier on the hands in any case (less chording).

As for cwm, the window manager, I in fact went ahead and made some improvements to it of my own. The cwm code is quite clean and elegant C code, and was a pleasure to hack on. Already, it featured a window-switching dialog which had auto-complete (a.k.a. type ahead find). This feature is very nice and makes switching windows via the keyboard very easy. However, cwm also had an execution dialog which lacked this feature. I felt it would be relatively easy to populate the execution dialog with the executable files in the default path to add such auto-completion. It was a little more involved than I originally anticipated, owing to the fact that the existing cwm API for these auto-completing dialogs was designed for selecting one item from many, not for entering input. With a little hacking, though, I made a working patch. I find this feature very useful, as it allows me to launch common applications like Firefox and Pidgin with a minimal number of keystrokes. The next feature I added was based on something that I saw in the Ion3 window manager - namely, an auto-completing `ssh-to’ dialog. Much like the window-switch dialog or the exec dialog, the `ssh-to’ dialog is populated with entries from your ~/.ssh/known_hosts file. OpenSSH has support for hashing these entries - the `ssh-to’ dialog simply skips hashed entries. For me at least, my work involves ssh’ing to a large number of different hosts, many of which have long names. The auto-completing dialog saves me considerable time. After committing these two hacks to the OpenBSD Xenocara tree, cwm was becoming very comfortable for me indeed. Only one major thing was bugging me - window movement. Cwm still required you to use the mouse to move windows around. Unlike a window manager such as Ion3, cwm does not (yet…) support tiling layout, and as such terminals and so on must be moved manually to maximise screen real estate. A simple solution to this is the ability to move windows around with the keyboard. After a productive conversation with OpenBSD developer Todd T. Fries I hacked up a simple patch which moved the active window with a Vi-style M-hjkl keybinding. Todd improved on this initial hack and committed it to the Xenocara tree. With these improvements, I find cwm quite comfortable and have little use for the mouse.

There are still a few niggling things in my setup. Mostly they revolve around X11’s copy/paste buffer management. A thing I do very frequently is to copy a link or text selection from Firefox into an xterm, and vice versa. X11 has effectively two copy buffers - the “PRIMARY selection” and the “CLIPBOARD”. If you select text with the mouse in an xterm, it goes into the “PRIMARY selection”. You can paste the contents into an xterm using the keybinding shift-insert. Additionally, links yanked with Vimperator, or text selected in Firefox with the mouse - this all ends up in the “PRIMARY selection” also. However, typing shift-insert in the “open” dialog (`o’) of Vimperator pastes the contents of the “CLIPBOARD”! Actually, not just the “open” dialog behaves like this, but every text input field in Firefox. Effectively this means I have to use the mouse to paste text into Firefox, which is quite irritating. I hope to find a utility which can keep the “CLIPBOARD” and “PRIMARY selection” synchronised. Personally, I do not find it helpful for these to be separate and it simply causes me annoyance. More information on X copy and paste can be found in this jwz article.

Tags: , ,
Posted in Health, Technical | No Comments »

UNIX, tell me if I can execute this file

Thursday, June 28th, 2007

A surprisingly complicated question on a UNIX system, in fact. UNIX files have three relevant execution bits. One for owner, group and other. To test if a file is executable at all, you can stat it, and simply test the mode bit-field - consider this short C program:

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
28
29

#include <sys/stat.h>
#include <sys/types.h>
 
#include <err.h>
#include <stdlib.h>
#include <stdio.h>
 
int
main(int argc, char **argv)
{
        struct stat sb;
 
        if (argc < 2)
                errx(1, "supply a filename");
 
        if (stat(argv[1], &sb) == -1)
                err(1, "stat %s", argv[1]);
 
        if (sb.st_mode 
            & (S_IXUSR|S_IXGRP|S_IXOTH))
                printf("%s is executable by "
                    "owner, group or other\n",
                     argv[1]);
        else
                printf("%s is not executable\n",
                    argv[1]);
 
        exit(0);
}

Now we run it against some very common UNIX files:


$ ./isexec $(which sh)
/bin/sh is executable by owner, group or other
$ ./isexec /etc/passwd
/etc/passwd is not executable

This still doesn’t tell us if the file is executable by our user. To find out, we must first find our relevant user ids and all our group memberships. We can do this quite nicely with the getresuid and getgroups functions. You may ask why I use getresuid() instead of the superficially simpler getuid() function. The answer is that the value getuid() returns can be ambiguous, getresuid() is much more explicit about what the real, effective and saved user IDs are. It makes code clearer and reduces the opportunity for subtle bugs. We add code like the following to the start of our program:

1
2
3
4
5
6
7
8

        gid_t mygroups[NGROUPS_MAX];
        uid_t r, e, s;
 
        if (getgroups(0, mygroups) == -1)
                err(1, "getgroups failure");
        if ((ngroups = getresuid(&r, &e, &s))
            == -1)
                err(1, "getresuid failure");

Now we have our uid and our group ids, we can test against the owner, group and mode bit-field of the file. If we are the owner, and the owner execute bit is not set, we may not execute it - even if the group or other execute bits are set in our favour. Same with group - if we are in the same group as the file, but group execute bit is not set, we may not execute it - unless we are the owner and the owner execute bit is set. This is may seem a little bit complicated to code at first. The important thing is to get the order right:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

        if (euid == sb.st_uid)
                if (sb.st_mode & S_IXUSR)
                        goto exec;
                else
                        goto noexec;
 
         for (j = 0; j < ngroups; j++)
                if (mygroups[j] == sb.st_gid)
                        if (sb.st_mode & S_IXGRP)
                                goto exec;
                        else
                                goto noexec;
         if (sb.st_mode & S_IXOTH)
                 goto exec;
         goto noexec;
exec:
         printf("file is executable by you\n");
         return (0);
noexec:
         printf("file is not executable by you\n");
         return (0);

The use of the goto keyword here in fact increases legibility, since it means you don’t have to have a whole bunch of ugly conditionals.

You may wonder why I bothered to write about this subject. Well, the answer is that I needed such an algorithm in order to add auto-completion to the cwm window manager. I committed the code to OpenBSD’s Xenocara tree a few days ago, so that now the exec dialog scans the default PATH, determines which files you may execute, and populates the execution menu with these values, such that you get auto-completion (aka type-ahead-find) when executing programs.

Tags: , ,
Posted in Technical | No Comments »

Typing, window managers and sore hands

Tuesday, June 19th, 2007

I am typically typing on a keyboard for many hours a day, and have been in this routine for many years. While I have never had soreness bad enough to prevent me from using a computer, unlike some unfortunate people, I definitely get some discomfort in my hands and wrists. This is pretty clearly a form of RSI brought on at least in part by my long hours using computers. It is also likely related to strains I sometimes get from boxing, which can be very hard on your wrists if you are not careful. Improperly throwing hooks on a heavy bag can leave you with a strained wrist for weeks. I will return to boxing-related injuries (which apply to many other sports too) in another post perhaps.

At work, I have a fairly ergonomic setup. Monitor is on a stand at a good level, I have a USB Microsoft Natural keyboard. I believe the keyboard does help my hands to some degree, although I can’t really say it makes a huge difference. My brother claims that he found it made typing more uncomfortable for him, so perhaps it varies from person to person. I find that chording - that is, pressing multiple keys with a single hand, for example left shift + f all with the left hand - would make my fingers feel uncomfortable. Not exactly pain, but a kind of strained feeling. I find the Emacs editor very uncomfortable to use if you have the habit of chording for example. Similarly, GNU Screen and OpenBSD’s KSH Emacs bindings - which I use all the time - are definite source of discomfort. I try now quite hard to avoid chording as much as possible. This seems to reduce considerably the strain on my hands. Additionally, using the Vi cursor movement keys in Mutt and nVi / Vim helps - in contrast to moving my hand over to use the arrow keys.

A second source of discomfort I identified was the mouse. I’m not entirely sure why, but it seems to me that shifting my right hand from its position on the keyboard over to the mouse, and also clicking the mouse, was quite stressful. I recall reading at JWZ’s site that he experienced something similar. The two biggest culprits of mouse usage for me were Firefox (obviously enough) and window management. I have gone through using many different window managers over the years. I am not hugely picky. I used fvwm for a while because it did everything I needed it to do, and came with OpenBSD. Then I switched to Ion for no particular reason. I liked Ion quite a bit but the author kept breaking the configuration format with every update. This infuriated me as I hate dicking around with funky configuration files (all Ion config was done through the Lua programming language, which I had no particular desire to learn in order to set a few trivial keyboard bindings). Eventually I switched to KDE from Ion. I figured KDE was unlikely to change their config format with every release and furthermore had a few nice features (task bar and the system tray thingy). Also I thought it would be good to at least try to fill up the 1G of RAM in my laptop. I learned a few key bindings in KDE, enough to switch between apps on the same virtual desktop. However, I am a very heavy user of terminals. I quite liked the tabbed Konsole (even if it is horrendously slow at scrolling text for some reason), yet I never really learned / set up the keyboard bindings properly, which mean I was using the mouse all the damn time.

This morning, since I had nothing really critical to do on my machine, I decided to update my system to the latest snapshot and move over to CWM at the same time. CWM is a little window manager written by people who have over the years been involved with OpenBSD development. Its BSD-licensed and as such was imported into the OpenBSD Xenocara tree. In other words, if you install X on an OpenBSD machine, you now get CWM as a window manager.

The main thing about CWM is that it is quite possible to use it purely via the keyboard. I’m not going to describe all the various ways you can use it, since I’ve only been using it for a few hours. Some really nice features are things like, labeling windows, hiding them with a key combo, then raising them again using a kind of type-ahead-find. I also like how window movement is implemented - you hold the meta key and can move the window by clicking anywhere on it. Sometimes it takes quite a bit of co-ordination to specifically click on the task bar to move a window around.

In any case, I am very happy with CWM so far. I don’t need a lot of frills in my window manager. CWM is very nice to use from the keyboard. It doesn’t require any configuration. One thing is that its not easily possible to change the command line options passed to Xterm when you execute it via C-M-Enter. To get around this and to set my Xterms to use white-on-black and be a login shell, I use the following in ~/.Xdefaults:

xterm*background: black
xterm*foreground: white
xterm*loginShell: true

I’m also now making considerable more use of Firefox’s type-ahead-find feature, and other keyboard shortcuts in that application. Unfortunately Firefox seems to have a number of glitches, at least on OpenBSD-current. Most annoying is that the ctrl+k shortcut, which is supposed to give focus to the search box, doesn’t work unless focus is on the browser component of the tab. This means that if you open a new tab with ctrl+t and then hit ctrl+k, nothing will happen. You have to first click the blank browser component. I’d also love a shortcut similar to tab, but which cycles through only the text input components on a page. This is required apparently because web authors are not setting a ‘tabindex’ property correctly, according to my brother. He suggests I could write a Greasemonkey script to rectify this if I was really bothered. Perhaps I should do that.

Update: After reading a bit on Firefox keybindings, I came across some suggestions that claimed Opera has very good support for keyboard shortcuts. I installed it from the www/opera port and am now running it. So far it does indeed seem very nice. I like the kind of mini-task-list it has for switching between tabs (ctrl+tab). Also it has nice support for cycling through text input fields, and just like Firefox has type-ahead-find. Finally, I was pointed to a Firefox extension called Conkeror which offers Emacs keybindings for Firefox. It also claims to offer Vi keybindings. While I use both Emacs and Vi keybindings in different settings, and I use both as editors, I believe I would prefer Vi keybindings for my web browser. I will have to try this out and see how it goes. The author claims he does not own a mouse which is very encouraging.

Tags: ,
Posted in Health, Technical | 2 Comments »

Blog is blog

Friday, June 15th, 2007

For a long time I’ve considered Word Press to be an awful pile of poo. Simply consider that its written in PHP, a bad, buggy language, and is futher full of security holes of its own making. I was thinking about writing my own implementation in Python (maybe TurboGears or Django or my own thing) or C. If I was doing it in C, I could use the BSD-licensed undeadly.org code and plug in Clearsilver templates or somesuch. It would be incredibly fast and perhaps a bit of fun. The problem is not so much the software side of it - its trivial to throw a simple schema together to represent posts in SQLObject - but more the display and interface. Writing good forms and UI and so forth is highly time-consuming and I just couldn’t be bothered. HTML and CSS and JavaScript are hard. Word Press also has a ton of extra features which I probably wouldn’t have time to implement, yet could potentially be nice for my site. I decided I would leverage the scalable nature of the Internet Word Press community, all those hundreds of people working on little plugins and tweaks etc. Even if the average quality is pretty low, in the end it should work “well enough”. Much as I like polish and perfection, sometimes its nice to be lazy and accept the warm sludge vomited up by the PHP-abusing masses. So yeah, I went with Word Press.

Well, at least its running in a chroot()-jailed Apache, with some pretty strict PF rules blocking outbound connections by the Apache user in case yet-another-PHP hole comes out before we can patch our server.

I also decided to try out the reCAPTCHA WordPress plugin to protect my posts from spam-comments. reCAPTCHA is a very clever idea - take a huge amount of old books, OCR them, and then use the words that the OCR software failed to recognise as a starting point. Next make captcha-solving help digitize these old books. I like that it encourages a kind of “arms race” between those cracking captchas (effectively the same thing as OCR) and those making better captchas which in the end, no matter what, will benefit the effort of creating digital copies of old books.

Tags: , , , , ,
Posted in Technical | No Comments »

Newer Entries »