New Deadwood snapshot

I have released a new snapshot of Deadwood today. This snapshot has two enhancements:

• I have added a copy of Duende (MaraDNS' daemonizer) modified to compile without MaraDNS proper, and the tools MaraDNS uses for creating documentation
• I have made a man page for DwMain, and included a man page for Duende updated with the FreeBSd fix and more geared towards Deadwood

These files can be downloaded here, and the man page for DwMain can be seen here.

samiam.org and blog comments update

I'm just letting people know I am doing a year-end cleanup of samiam.org, getting rid of a lot of outdated software and what not. As a general rule, I am removed links to versions of programs that are not the last release of a given program. With ObHack, I have made sure the last 002 and 003 releases are available, in addition the the final 004 release, so people can check out the subtly different maps each version of ObHack makes.

I have also deleted all of the Chess Variant-related stuff from the site. I have decided that Chess Variants are simply a waste of time; I have better things to do with my time. People who want to see my work in this area can download my Schoolbook file from the Zillions of Games website (look in "free games", then look for "schoolbook").

In terms of support, the only geek project I have done over the years I still use today is Deadwood (code that will someday be MaraDNS' next recursive resolver). Other projects are not supported and blog comments asking for support for, say, ObHack, will probably not be posted.

MaraDNS, of course, is still supported, but the only changes I will make in 2009 are critical and security bug fixes. I do not support non-security issues in MaraDNS anywhere except on the MaraDNS mailing list. Again, blog comments asking for MaraDNS support in 2009 will not be posted.

Deadwood is the only project I still find useful and support. People are welcome to download and use any other open-source code I have, but please don't ask me to solve your problems for you. Be smart. Learn to troubleshoot and figure out issues on your own. It'll make you a more mature, responsible person.

My 2009 plans for Deadwood

At this point I'm thinking of holding off on MaraDNS 2.0 for the time being. Instead, I think I will concentrate on getting the last bugs ironed out of Deadwood, and then seeing if I can make it part of BusyBox. Deadwood has some final wrinkles I would like to resolve:

• I need to solve the "Google problem"
• I need to make sure "resurrections" (getting expired elements from the cache when it is not possible to contact an upstream DNS server) work

Once I do that, I can send an email to the Busybox people and see what it would take to make Deadwood a Busybox module (probably merging as much of the UDP and TCP code as possible, having the option to strip out the parser, being able to remove the saving/loading of the cache from a file, etc). I think doing this will greatly benefit the kinds of embedded router makers who use Busybox a lot, and will give MaraDNS/Deadwood a lot more exposure, which is good for my future job prospects.

This allows Deadwood to fill a niche which other DNS servers don't really fill: The need for a tiny secure stub resolver so people get correct DNS replies when asking their router to resolve hosts.

The need for a somewhat bigger secure fully recursive DNS resolver is nicely filled by Unbound, Power DNS, or even MaraDNS (if you don't mind all of the threads being spawn). As an aside, don't use DJBDNS' "Dnscache"; even though the code is now public domain, it hasn't been updated for years and I don't see anyone stepping up to plate and making a supported updated version with security and other problems fixed.

The only way I can motivate myself to continue work on Deadwood making it a fully recursive resolver is by seeing a niche for it that hasn't already been filled. The "non-DNSSEC recursive resolver" niche is more nicely filled up than it was when I did the lion's share of work on Deadwood a year ago: I was not aware of Unbound when I started work on Deadwood. One niche that doesn't seem to be filled is the "small DNS recursive resolver with DNSSEC support" niche; this might be what I end up doing with Deadwood in the long run, which would result in an eventual MaraDNS 2.0 release.

However, I think I will wait until after the end of 2009 before adding recursion to Deadwood. MaraDNS will have no features added to it in the meantime, with the only changes being security and serious bugs being fixed.

As an aside, in my personal life, while my former neighbor is still a very close platonic friend, I now have another girl in my life today who is my girlfriend.

32-bit Skein is possible

Looking over the Skein paper, I saw this little gem:

5.4 The Word Size as a Tunable Parameter

All versions of Skein are specified with 64-bit words. The word size can be seen as a tunable parameter; we can define a Skein variant with 32-bit words. This variant would run much faster on 32-bit CPUs, but significantly slower on 64-bit CPUs.

At this point, we have not searched for rotation or permutation constants for a 32-bit variant, nor have we analyzed it to determine how many rounds would be required for security. However, given the knowledge obtained from the 64-bit variants, this would not be complicated.

So, yeah, it would be possible to make a 32-bit version of Skein, but it hasn't been done yet.

Why Deadwood will still use RadioGatun

I have spent the last day or so looking at all of the SHA-3 hash function candidates; my first step was to look at all of them and see which ones can also be used as stream functions. As I pointed out yesterday (go there for links to the hash primitives I will talk about), only four of the SHA-3 submissions can be used both as a hash and as a stream cipher.

One thing that is important for Deadwood is to use a cryptographic primitive that works well with 32-bit words. Deadwood's target is a 32-bit embedded platform, such as a router. Radio Gatun works nicely here because it has both a 32-bit and a 64-bit variant; Deadwood uses the 32-bit variant.

Of the four submissions I listed yesterday, the only one whose SHA-3 submission uses 32-bit words is LUX (for the 224-bit and 256-bit long hashes). The other three use 64-bit words in their SHA-3 submissions.

It would appear that there is already cryptanalysis of LUX when it uses 32-bit words that concludes that LUX does not work well as a stream cipher or as a PRNG. This, in spite of the fact LUX only came out two months ago.

While Skein has incredible 64-bit performance and respectable 32-bit performance, it uses 64-bit words and there isn't a variant that uses 32-bit words.

MeshHash is designed to use 64-bit words from start to finish. In addition, there is already some cryptanalysis which doesn't look good.

Keccak, developed by the same group who created Radio Gatun, can work with 32-bit words, and indeed, while not part of the SHA-3 submission, the authors specify two forms of Keccak that can be used on 32-bit systems, one optimized for speed and another optimized for security. The "fast" version appears to have a good deal less security than Radio Gatun appears to have.

While Keccak looks promising and perhaps Skein can work well on 32-bit systems, Radio Gatun has been out in the wild for two years with no cryptographic attacks against it yet. Radio Gatun is closely related to Panama, which has been around for over 10 years without any weaknesses found in its stream cipher operation (which is how I use Radio Gatun in Deadwood).

So, in conclusion, while Keccak and possibly Skein deserve further investigation at a later date, neither is as freely adaptable to 32-bit systems as Radio Gatun is. While both have not been attacked yet, they are very new primitives that I want to give more time to be analyzed before I feel comfortable using them in Deadwood.

The other two primitives have already been attacked. Consequently, I don't feel entirely comfortable using them in Deadwood.

So, in conclusion, Deadwood will continue to use Radio Gatun as the engine for generating secure pseudo-random numbers for the foreseeable future.

My first look at the SHA-3 candidates

I have just spent all afternoon looking over the SHA-3 candidates. What I am looking for is hash primitives that, like RadioGatun, are able to output hashes of arbitrary size (work as stream cipher). Of the many submissions, only four unbroken submissions appear to be able to do this:

• Keccak
• LUX
• MeshHash
• Skein

I hope one of these submissions win, because would be nice to have something that is standardized both as a hash function and as a stream cipher.

A couple of goodies

Over a year ago, I wrote a couple of programs that use the 32-bit version of the Radio Gatun cryptographic hash to calculate the cryptographic sums of files.

These programs are open-source, and are released to the public domain. The program is called "rg32hash" and is used like the md5sum program. Unlike the md5sum program, this program automatically recursively enters directories. Give it the file name or directory name you wish to hash, and it will output on the standard output the 256-bit Radio Gatun 32-bit hash of all of the files you list. If you want to perform a recursive hash from the current working directory, simply type in something like rg32hash . > RG32SUMS

I have both a Windows 32-bit binary and *nix source code of this program available.

The Nokia 5310 is not open-source friendly

OK, I have been posting some reviews and talking about my new Nokia 5310 phone. I am been generally positive about it; now I will point out some issues these phones have because they cater to corporate interests. Last night, after some aggravation, I was able to update the firmware in my Nokia phone.

The problem was this: My phone is a Red Telcel-branded Nokia 5310, with the Product Code "0558120". Well, the problem is that the latest firmware for this version of the phone is an old 5.xx firmware, which has problems with being compatible with >4gb memory cards and with random "white screens of death" while playing music.

The current firmware, 8.32 (as an aside, you can see which version of the firmware a Nokia phone is running by typing in "*#0000#" without the quotes), appears to have fixed the "white screen of death" problem and is compatible with up to 16gb microSDHC memory cards.

I had to change the phone's product code to be allowed to update my firmware. I don't suggest doing this, because if you're not careful you can brick your phone. There was an issue with the current version of the USB driver Nokia makes blocking the program I downloaded to change the product code, so I just uninstalled all of my Nokia Software and downloaded an older version of the USB driver without this lockout.

After trying a "EURO-C" (Europe section C, which seems to include Spain) product code which also hasn't updated the firmware, I found on a Spanish-language program the product code for the "AMER-L" (Latin America) version of the unbranded Nokia firmware, which version 8.32 is available for. The code is 0551710 for the red phone, 0551739 for the blue phone, and 0563632 for the pink phone. This firmware supports English, Spanish, Portuguese, Dutch (huh?), and French.

Once I did this, I was able to update the firmware to 8.32.

However, there was a problem. Since I changed my phone's product code, the games I legally purchased no longer worked, since they include DRM. The solution was easy: I just went on the 'net, did some Google searches, and got unlocked versions of all of the games I bought from various "file sharing" services. I also got a lot of games I have never bought, but my sense of morals makes it unethical for me to play and enjoy a game I haven't bought.

So far, I haven't gotten a white screen of death, and feel a lot more comfortable using the music player since I don't have to worry about it crashing any more. I can also, if I wanted to, get an 8gb or even a 16gb memory card for the phone, but will hold off for now. The problem is that the current batch of 16gb memory cards are what as known as "class 2" cards; they can only transfer 2 megabytes of data a second, which means it can take over an hour to fill up the memory card with files.

Toshiba has announced that they will start making "class 6" (6mb a second minimum transfer speed) 16gb microsdhc memory cards, but these cards are not going to to available until mid-2009 or so. So, I'll either get a "class 4" (4mb/second) 8gb card for $20, or just wait until next year.

Another issue is that the 5310 doesn't support Ogg Vorbis files. This was OK back in the days when corporate interests said "Oh, our CPUs don't have the horsepower to decode Vorbis streams", but since the 5310 does support AAC files, there's no reason for this phone to not support Vorbis, except it isn't a format as well-known by the suits. The advantage of Vorbis is the free auTuV encoder, which does a better job of encoding audio than FAAC, the only freely available AAC encoder (since this software is not as mature as the proprietary AAC encoders), and LAME, the best MP3 encoder (also freely available; not as good because of the limitations of the MP3 format).

Nokia "Pink Planet" theme completed

I actually finished up the "Pink Planet" theme a week ago or so, but neglected to mention it was done last week. So, without further ado, here's a link to the three versions of this theme, and a direct link to what should be the final version of this theme.

I might upload this to some of the sites that host Nokia 5310 themes.

- Sam

Capa opening setups

(Disclaimer: All of this material I have previously posted in a thread at chessvariants.org, but I am reposting it here so it's available in a more convenient form)

One popular branch of chess variants is Capablanca Chess. Originally proposed in the 1600s by Carrera, and proposed again in the 1800s by Bird, and propsed yet again in the 20th century by Capablanca, this is one of the more popular types of chess variants that people have proposed versions of.

There are some 126,000 possible Capablanca opening setups, where the bishops are on opposite colors, and where the queen is to the left of the queen. However, looking at all of the Capablanca opening setups which have actually been proposed, I have observed that:

• All of the opening setups have the king and a powerful (R+N,B+N, or Queen) piece in the center files
• All of the proposed opening setups are symmetrical with the rooks, knights, and bishops
• All of the proposed opening setups have the rooks either in the corners, or one file closer to the center than the corners.

As it turns out, there are only 72 possible Capablanca opening setups that follow all of the above rules. Of these 72 opening setups, I find that only 15 have been formally proposed as starting setups:

Here is a list of proposed Capa chess setups I know about:

RANBQKBNMR      Aberg
RMNBQKBNAR      Carrera
RNBMQKABNR      Bird
RNBAQKMBNR      Capa 1 (1.Mh3 mating threat)
RNABQKBMNR      Capa 2
RBQNKMNABR      Grotesque
RBNMQKANBR      Univers
RBQNKANMBR      Landorean
RNBQKMABNR      Embassy
RQNBAKBNMR      Schoolbook
NRMBQKBARN      Optimized  
RNBQCKABNR      Gothic
MRNBQKBNRA      Paulowich 1 link
ARNBQKBNRM      Paulowich 2 link
QRNBKABNRM      Paulowich
RNMBQKBANR      Nalls link
RNBQAKMBNR      Teutonic link (1. Mh3 mating threat)

Any without a link here are listed on on the Capablanca Chess Wiki page.

And some more proposed opening setups, since not nearly enough Capa opening setups have been proposed :)

RNBQKAMBNR      Consulate
RNQBKMBANR      Finesse
RQNBKABNMR      Notebook
QRNBAKBNRM      Closebook
RNQBMKBANR      Blackbook
NRABQKBMRN      Nightwink
RQNBKMBNAR      Narcotic

Setups which suffer from white being able to threaten mate on the first move:

RQNBMKBNAR Md3
QRNBMKBNRA Md3
RBNQKMANBR Mg3
BRNQKMANRB Mg3
QRNBKMBNRA Mg3
BRNAQKMNRB Mh3 (Capa 1)
RNBQAKMBNR Mh3 (Teutonic)
BRNQAKMNRB Mh3
RABNQKNBMR Mh3
RQBNAKNBMR Mh3

So, for aspiring Chess variant inventors, that leaves us with the following possible Capa opening setups:

QRBNAKNBRM RQBNMKNBAR NRBQAKMBRN RBNQAKMNBR NRBMQKABRN BRNMQKANRB RBNMQKANBR QRBNMKNBRA NRBQKMABRN RMBNQKNBAR ARBNQKNBRM RQBNKMNBAR BRQNMKNARB RBQNMKNABR NRQBMKBARN NRQBKABMRN RNQBKABMNR NRBAQKMBRN BRQNKANMRB BRANQKNMRB RBANQKNMBR BRNAQKMNRB RBNAQKMNBR MRBNQKNBRA QRBNKMNBRA RQBNKANBMR BRMNQKNARB RBMNQKNABR QRBNKANBRM NRBQKAMBRN NRQBAKBMRN BRNQKAMNRB RBNQKAMNBR RNQBAKBMNR BRQNAKNMRB RBQNAKNMBR NRBQMKABRN NRQBKMBARN BRQNKMNARB BRNQMKANRB RBNQMKANBR

OK, one of those dictionaries I downloaded wasn't free

The huge three-megabyte dictionary I mentioned in my last blog entry actually isn't freeware. It's demoware; the program asked for a registration key a few days after I started using it, so I just deleted the application.

The other two dictionaries I have, however, still haven't done anything like this.