Deadwood on OpenWRT; The case for 32-bit Skein

When I was designing Deadwood, I made sure to make the program work really nicely on 32-bit processors, while retaining compatibility on 64-bit processors. In the places where word size really matters, namely the hash compression function and the cryptographic random number generator, I went out of my way to use 32-bit algorithms (my own home-grown algorithm for the 32-bit hash compression function; RadioGatun[32] for the random number generator).

During Deadwood’s development cycle, I even gave a nod to systems that can work with both 16-bit and 32-bit numbers, by having it so “int” in the source code means “something that can fit in 16 bits”, and using int32_t for anything that would need more than 16 bits (near the end of the Deadwood development cycle, I went from “int32_t” to “int_fast32_t” for “integer that needs more than 16 bits”). This is untested—I don’t think there are any systems in use today capable of routing packets that have 16-bit wide registers—but allows it to be at least possible to port Deadwood to a 16-bit system.

The reason for all this attention to detail was because my target platform while developing Deadwood was to have it run nicely on the 32-bit router in the corner used to connect people to the internet. And, I have succeeded.

Sebastian Müller has already gotten Deadwood to recursively process queries on an embedded router and is working on porting Deadwood to a number of platforms. He was able to pull this off in a single afternoon because Deadwood is, from beginning to end, an architecture-independent recursive DNS server optimized for 32-bit platforms.

Of course, Deadwood also runs nicely on 64-bit platforms; one of my regressions I perform when building Deadwood is to make sure nothing breaks in 64-bit. The only issue is that some operations (the hash compression, the cryptographic random number generator) are less efficient because they were written to run on 32-bit systems. [1]

Now, while Deadwood does run nicely on various 32-bit embedded systems, I unfortunately can not readily support these configurations because I run Deadwood on x86_32 and can not solve problems for people running it on different systems. It works, but people want to do this are on their own and need to take responsibility for any problems they see.

---

This leads us to Skein, a proposed hash primitive for SHA-3. Skein is a very good hash with a lot of features, including having, in its core, Threefish, the only tweakable block cipher primitive that appears secure.

However, I can’t use Skein because there’s no native 32-bit version of it, even though such a thing is possible. When I pointed out this problem on Schneier’s blog, I was dismissed by another poster with “all 32-bit desktop processors (and even some ARM chips) have instructions that can do math on pairs of 64-bit numbers”.

That’s all well and good, but Deadwood isn’t just for the desktop. It’s also for the embedded 32-bit space and that means no MMX/SSE instructions that work on 64-bit numbers.

One of the reasons why I feel so frustrated is because I can’t just make a 32-bit Skein variant. Not without possibly making 10 different errors that could destroy its security.

I understand why Schneier, et. al. don’t feel comfortable coming out with some rotation constants to make a 32-bit Skein variant; if they did make such a Skein variant and some cryptographers found weaknesses in them, it would make them look bad. So, they are being very conservative about what they will declare to be the official “magic numbers” for Skein. Numbers I simply do not feel comfortable changing.

If I were to use one of the SHA-3 submissions for Deadwood’s PRNG, I would use Keccak. Like Skein, it can output a stream of infinite length from any input of any length. Unlike Skein, it is more 32-bit compatible; not only is there a 32-bit “reduced word length” variant officially blessed by the algorithm’s creators, but also 64-bit Keccak more easily scales down to 32-bits than Skein, since the only operations done are permutes, rotates, and exclusive ORs.

32-bits is still very much a reality today. While the transition to 64-bit desktops is well underway, it will be a few years before 64-bit desktops become more common than 32-bit desktops. The embedded space is very slowly letting go of 8-bit systems, replacing them with 32-bit systems. I wouldn’t be surprised if 32-bit is still around in 2038, when we will have to worry about systems with 32-bit time_t overflowing (Deadwood will run until 2143 on systems with a 32-bit time_t, uses 64-bit timestamps internally, and won’t overflow in 2143 if compiled on a system with a 64-bit time_t).

Yes, we are making the transition to 64-bit. But we can’t make the transition with solutions like Skein that pretend 32-bit no longer exists.

---

[1] In terms of making a full 64-bit port of Deadwood, I would have to:

• Make most, but not all, of the int32_t declarations int_fast32_t declarations (64-bit compilers should make int_fast32_t 64 bits wide)
• Use RadioGatun[64] instead of RadioGatun[32] (because of how I wrote the RadioGatun code, this is a fairly quick change)
• Replace the hash compression core with one using 64-bit instead of 32-bit operations. The most difficult part of this is making a 63-bit random prime number; we can quickly brute-force test the primality of a 31-bit number, but not for a 63-bit number.

No, I don’t have plans to do this before MaraDNS 2.0 is released.

New Deadwood snapshot: Queries nearly three times faster

There has been some discussion today about the fact Deadwood, while very good at resolving names in general, is a good deal slower than other DNS servers.

Looking at the code, I already found the #1 offender that was responsible for about two thirds of the slowdown, and have patched this bug in today’s Deadwood snapshot. Anyone who feels Deadwood is a bit sluggish is encouraged to download and use today’s snapshot.

In addition, one issue that I have been thinking about for a while is that the hash compression function is not quite random enough. So, I’ve revised the hash compression core to add a random 16-bit number for each iteration of the hash compression. The number is randomly generated with Deadwood’s secure PRNG (Read: RadioGatún[32]) and is different every time Deadwood is started.

Deadwood snapshots can be looked at here:

http://maradns.org/deadwood/snap/

RadioGatún[32] even smaller

While going through the source code for the tiny version of RadioGatún[32], I realized the code had some unneeded bloat which I was able to remove, in order to make the program more lean and not be wasting precious bytes. The current version of the program is as follows:

/*Placed in the public domain by Sam Trenholme*/
#include <stdint.h>
#include <stdio.h>
#define p uint32_t
#define f(a) for(c=0;c<a;c++)
#define n f(3){b[c*13]^=s[c];a[16+c]^=s[c];}k(a,b
k(p *a,p *b){p A[19],x,y,r,q[3],c,i;f(3)q[c]=b[c*
13+12];for(i=12;i;i--){f(3)b[c*13+i]=b[c*13+i-1];
}f(3)b[c*13]=q[c];f(12){i=c+1+((c%3)*13);b[i]^=a[
c+1];}f(19){y=(c*7)%19;r=((c*c+c)/2)%32;x=a[y]^(a
[(y+1)%19]|(~a[(y+2)%19]));A[c]=(x>>r)|(x<<(32-r)
);}f(19)a[c]=A[c]^A[(c+1)%19]^A[(c+4)%19];a[0]^=1
;f(3)a[c+13]^=q[c];}l(p *a,p *b,char *v){p s[3],q
,c,r,x,d=0;for(;;){f(3)s[c]=0;f(3){for(q=0;q<4;){
if(!(x=*v&255))d=x=1;v++;s[c]|=x<<(q++*8);if(d){n
);return;}}}n);}}main(int j,char **h){p a[39],b[3
*13],c,e,g;if(j==2){f(39){a[c]=b[c]=0;}l(a,b,h[1]
);f(16)k(a,b);f(4){k(a,b);for(j=1;j<3;++j){g=a[j]
;for(e=4;e;e--){printf("%02x",g&255);g>>=8;}}}}}

There may some more bloat that needs to be removed from this code, however, for the time being, it appears to be a fairly lean implementation of the 32-bit version of RadioGatún. Certainly more efficient that the rather bloated RadioGatún implementation included with Deadwood (which, horror beyond horrors, has comments and other completely unnecessary pieces of code).

Some cryptographic primitives I would like to see

There are some symmetric cryptographic primitives the currently don’t exist or are very rate that I would like to see more of:

• Ciphers which can change the fundamental word size used.
  
  There are a few of these: Keccak can work with 64-bit, 32-bit, or even 16-bit words (or smaller, but there isn’t any real security with going below 16 bits). RadioGatún, Keccak’s predecessor, also allowed any word length between one bit and 64 bits. RC5 and RC6 can work with either 32-bit or 64-bit words (but are, alas, patented until at least 2015). The stream cipher ISAAC exists in 32-bit and 64-bit variants.
  
  But, besides those, there really aren’t that many cryptographic primitives with word size flexibility, which is a disappointment right now, since 32-bit and 64-bit systems are currently very common.
  
  I’m not the only one hungering for this; observe halfskein.js, which is an unofficial Skein variant using 32-bit words (Skein normally uses 64-bit words). I should also point out that LUX has both a 32-bit and a 64-bit mode (unfortunately the original LUX specification was broken; hopefully the revised version will not be.)
  
  
• A block cipher with a 2048-bit or larger block size.
  
  The largest block size out there in an unbroken cipher is Threefish, which includes a version with a 1024-bit block size. There was Mercy, with a 4096-bit (512-byte) block size, but that was unfortunately broken. XXTEA, which also allowed really large blocks has also been broken; and the Hasty Pudding Cipher has also this ability, but I remember reading somewhere that HPC doesn’t pass standard randomness tests, and weaknesses with the key schedule have been found with this cipher (it was also criticized by Brian Gladman as being difficult to implement).
  
  Yes, it is possible to make, say, an AES variant using 128-bit sized words and a 2048-bit block size, but it hasn’t been officially proposed as a block cipher. It should also not be too difficult to make a Skein variant with 2048-bit blocks (or 1024-bit blocks when using 32-bit words), but again this has not been done.
  
  A 2048-bit cipher, for example, would be useful for making a Cryptographic sponge with a 1024-bit rate and 1024-bit capacity, which could be used for either a stream cipher or for a 512-bit cryptographic hash primitive.
  
  
• More tweakable block ciphers. There is only one unbroken block cipher primitive with a tweakable core out there: Threefish. The only other tweakable block cipher is the original: Hasty Pudding Cipher (as discussed above); unfortunately, HPC appears to be broken (or at least have weaknesses)
  
  
• A cipher using playing cards with no known weaknesses.
  
  The strongest cipher designed specifically to be implemented using a deck of cards is the Solitaire cipher; but it has some bias in its PRNG. There has been proposed Mirdek, which is broken, as well as John Savard’s playing card cipher, which also is broken.
  
  The most secure playing card cipher out there appears to be a RC4 variant using playing cards.

One of the frustrations of not having more cryptographic chops is that I can not comfortably design a cryptographic primitive with any of the above desired traits. As a mere programmer, all I can do is hope to someday have the time to learn about differential cryptanalysis and what not so I can design one of these primitives, or have someone else do the work for me.

So, hey, if you’re one of the very few people in the world with the intelligence and chops to make a strong cryptographic primitive, this is my wishlist! And, yes, I really appreciate that most cryptographic primitives out there are public domain. AES was perfect when I was making a secure random number generator for MaraDNS 1.x, and RadioGatún was perfect (tiny, able to easily compress entropy from various sources with variable amounts of entropy-per-bit, fast, 32-bit compatible and easily adapted to 64-bit environments, and derived from PANAMA with a proven record as a secure stream cipher) for my needs when I originally designed Deadwood back in 2007.

Wesnoth's RNG has statistical weaknesses

All of the people playing Battle for Wesnoth complaining about Wesnoth’s random number generator (RNG) having problems were right.

There is a test used called the “minimum distance” test which tests a random number generator by filling up a volume of space with points determined by the random number generator and determining the minimum distance between any two points. Or, in other words, we take a cube, fill it with points “randomly” by using the RNG we are testing, and make spheres of each point and the point closest to that point. The smallest such sphere is our minimum distance. We do this a number of times.

There is a range of minimum distances we should have. But, with Wesnoth’s random number generator, we don’t get that, especially in four dimensions (it also fails in three dimensions) [1]. A good randomness tester like Dieharder can readily distinguish Wesnoth’s RNG from a good RNG (such as RadioGatún).

The reason for this is because Wesnoth’ random number generator is as follows:

static int32_t state;
uint32_t mask;

state = (state * 1103515245) + 12345;
mask = (state >> 16) & 0x7fff;
return mask;

(The actual code uses division and modulo where I use a shifter and a logical and above).

This is a very simple Linear congruential generator, and is considered a rather poor RNG.

One of these years, I should submit a patch to replace Wesnoth’s junk RNG with RadioGatún. Although I have a feeling the developers will not accept it. It would, after all, be a pretty big blow to their pride to admit the RNG Wesnoth has been using for years has significant, measurable problems.

I should, before signing out, point out that Wesnoth is an excellent game and I appreciate all of the hard work done on it. I just wish the Wesnoth FAQ would stop pretending the random number generator is any good with nonsense like “programmers have examined the random number generator. No flaws have been found”. Because I found significant flaws in under an hour with Dieharder.

I should probably point out that Wesnoth’s RNG also flunks the “Diehard DNA test”.

[1] To properly test Wesnoth’s random number generator in three dimensions with Dieharder, I had to modify the random number generator to use a 32-bit unsigned integer and take the top 16 bits from the generator state (instead of using a 31-bit integer and taking 15 bits). The stream is identical if we remove the high bit from these 16-bit numbers to make them 15-bit numbers.

RadioGatún[32] passes all Dieharder tests

Dieharder is a series of tests to test the quality of random numbers. I have installed Dieharder 2.27.12 on my CentOS virtual machine (by virtue of the fact that this is the most recent version of Dieharder with handy precompiled 32-bit binaries) and then started running RadioGatún[32] as a stream cipher through this battery of tests.

The first time I tested RG32 (my shorthand for “RadioGatún[32]”), a couple of tests were marked as poor—which is not surprising, since the full battery is some 74 tests. When a tests is marked as being “poor”, that indicates that the stream of random numbers generated have a 1% or smaller chance of not being random. A good set of random numbers will occasionally fail a randomness test, since well-made random numbers sometimes do not quite look random.

I re-ran the tests that were “poor”, first with the same RG32 seed at a different point in its stream (which resulted in having a “possibly weak” result—a 5% chance the test was not random—for a different test, which is not surprising since there are 20 tests in this section of Dieharder), then with a couple of other RG32 seeds. With the third RG32 seed, none of the 20 tests were marked “poor” or “possibly weak”.

Conclusion: RG32 shows no biases when used as a pseudo-random number generator (PRNG). In practical terms: Deadwood is using a strong random number generator.

While I was testing the quality of RadioGatún’s random stream, I tried to run the tests at CAcert.at, but the server gave me an “Internal server error” instead of test results. I tried with two different sample sizes (one about 130 megs in size; the other about 18 megs in size).

I should note that RG32 is quite fast, even with the code-size-optimized implementation I made for Deadwood. Compiled with -03 in GCC, I got 20 megabytes of numbers in three or four seconds. cat /dev/null gives me 200 megabytes of zeros in the same amount of time.

Update: Using the rg32 seed (hash input) of “dieharder7&rdquo, Dieharder 2.27.12 passes all tests; again, random numbers should sometimes fail a randomness test, but they don’t with this particular seed and particular version of the full Dieharder test suite.

RadioGatún C++ class

I have been working on an off with a C++ class for the 32-bit version of the RadioGatún hash for a couple of weeks so I can become more familiar with C++ classes. I finally, after some trouble, got this class to correctly implement RadioGatún-32. It can be downloaded here:

http://www.samiam.org/rg32

Simple RadioGatun library

A while ago, I wrote a simple code-size optimized Radio Gatun library. A version of this code is used in new ObHack releases, and can be downloaded here or looked at here.

ObHack 005a released

One thing that has always annoyed me a bit about ObHack is the fact the library for the underlying random number generator only allows a 32-bit seed to be used.

I have fixed this. Instead of using the Mersenne twister as a random number generator, ObHack now uses the 32-bit version of RadioGatún as the RNG. This allows us to take advantage of the fact that RadioGatún allows an arbitrarily long input as its "seed" and can output a arbitrarily long stream.

Since RadioGatún is (as far as this academic cryptographic community knows) a secure stream cipher, its output is indistinguishable from random noise.

I have changed the relevant parts of the LUA scripts to seed the random number generator with a string instead of a number, and have changed the GUI dialog code to allow any string up to 16 characters long to be inputted as the RNG seed.

If a seed longer than 16 characters is desired, this can be done by invoking ObHack from the command line. To do this:

• Open up the ObHack gui from the directory containing ObHack
• Configure, in the GUI, the type of game you want ObHack to make (level size, number of monsters, game type, number of maps to make, etc.)
• Leave the GUI without making a level
• Now, invoke ObHack from the command line with the first command line argument the seed of the map you want to make that starts with a number. For example, to use the seed '12345-long-ObHack-seed.wad' invoke ObHack as ObHack 12345-long-ObHack-seed.wad. It will generate a .wad file with both the name and seed '12345-long-ObHack-seed.wad' (yes, the .wad extension will be part of the RNG seed).
• This can be done repeatedly from a script if you have a few DVD-R blanks you want to fill up or what not
• Did I make it clear that a map generated from the command line must start with a number?

Note that there is a minor bug in ObHack: When I wrote the code to implement the new RNG last night, I neglected to free the memory used by the old seed when re-seeding the RNG; this means the program leaks 240 bytes of memory for every level generated by ObHack in a megawad; when making a Heretic megawad (55 levels), this leaks 13200 bytes of memory. Since it's rare to generate more than one wad file each time one invokes ObHack (following the above steps to repeatably invoke ObHack with a script restarts ObHack every time we make a .wad), so we only leak up to 13200 bytes, this isn't a serious enough bug for me to make a new release of ObHack to fix.

ObHack 005a can be downloaded at samiam.org/slump. Here is the Doomworld thread I use to announce new releases of Obhack there.

NanoRG32: RadioGatun 32 in 877 bytes of C

RadioGatun 32 in only 877 bytes of c:

/*Placed in the public domain by Sam Trenholme*/
#include <stdint.h>
#include <stdio.h>
#define p uint32_t
#define f(a) for(c=0;c<a;c++)
#define n f(3){b[c*13]^=s[c];a[16+c]^=s[c];}k(a,b
k(p *a,p *b){p A[19],x,y,r,q[3],c,i;f(3){q[c]=b[c
*13+12];}for(i=12;i;i--){f(3){b[c*13+i]=b[c*13+i-
1];}}f(3){b[c*13]=q[c];}f(12){i=c+1+((c%3)*13);b[
i]^=a[c+1];}f(19){y=(c*7)%19;r=((c*c+c)/2)%32;x=a
[y]^(a[(y+1)%19]|(~a[(y+2)%19]));A[c]=(x>>r)|(x<<
(32-r));}f(19){a[c]=A[c]^A[(c+1)%19]^A[(c+4)%19];
}a[0]^=1;f(3){a[c+13]^=q[c];}}l(p *a,p *b,char *v
){p s[3],q,c,r,x,d=0;for(;;){f(3){s[c]=0;}for(r=0
;r<3;r++){for(q=0;q<4;q++){if(!(x=*v&255)){d=x=1;
}v++;s[r]|=x<<(q*8);if(d){n);return;}}}n);}}main(
int j,char **h){p a[39],b[39],c,e,g;if(j==2){f(39
){a[c]=b[c]=0;}l(a,b,h[1]);f(16){k(a,b);}f(4){k(a
,b);for(j=1;j<3;++j){g=a[j];for(e=4;e;e--){printf
("%02x",g&255);g>>=8;}}}printf("\n");}}

To run this program, compile it with the name NanoRG32; the program will output the Radio Gatun 32 hash of the first argument given to the program. For example, to get the Radio Gatun 32 hash of "123456789012345678901", run this program as NanoRG32 123456789012345678901 and you should get a hash starting with 381957046bec1dfc08eaa0

Radio Gatun cryptanalysis (NOT broken) ; Deadwood minor update

Over two years have passed since RadioGatún was published; there finally has been some cryptanalysis of RadioGatún. In the first attack (PDF file), Dmitry Khovratovich and Alex Biryukov were able to attack RadioGatún with a complexity of 2^576 for the 32-bit version of RadioGatún. This attack is clearly not practical, and is only slightly less complex than the claimed security for RadioGatún32, 2^608.

Thomas Fuhr and Thomas Peyrin have a more successful attack; they claim to be able to break RG32 with a complexity of 2^352 (and actually break the 2-bit version of Radio Gatún in their paper). Again, the attack is not practical, but is significantly less complex that RG32's security claim of 2^608. Even if this attack can be extended to the 32-bit version of RadioGatún, RG32 can still be used to make secure 512-bit hashes (a birthday attack on a 512-bit hash has a complexity of 2^256). I personally use it for 256-bit hashes and feel that there will not be any cryptanalysis that makes a collision attack for RG32 easier than 2^128 (and probably no attack easier than 2^256).

There has been no cryptanalysis against using RG32 as a stream cipher (like I do in Deadwood), and RadioGatún's close relative, Panama, has been around since the late 1990s and never has been broken when used as a stream cipher.

---

I am working on making Deadwood a bona fide Windows service. The first step of this work, porting MicroDNS to Windows (so I have a very simple server to make a service out of), has been done and can be downloaded as microdns-simple.c. Compile this program as gcc -DMINGW -o microdns-simple microdns-simple.c -lwsock32 on a Windows system with MinGW.

MaraDNS snapshot uploaded

I have uploaded a MaraDNS snapshot with the beginning of my work for XeroBank; I also have added Radio Gatun 32-bit support to the mqhash program.

It can be downloaded by following this link

MaraDNS snapshot update

I have done a number of updates this last day in preparing my snapshot update. One issue is that I have fixed the timestamps the VMware server creates; I will discuss the timestamp issue and possible workarounds in a future blog. The timestamp for the last snapshot was off by a day or so; the current snapshot has correct timestamps.

In addition, I took the rg32hash program (which recursively calculates Radio Gatun 32-bit sums, given a list of files and folders), removed all compile-time warnings, and am adding it to the next MaraDNS release. It's in tools/misc.

I have also added a "borked zone" test; this is a test that reproduces the bug mentioned in yesterday's blog entry. The results I get from this testcase is that MaraDNS initially reports a "server fail", but will correctly resolve a hostname when a second query is sent. This "server fail" message, if it causes problems, can be resolved by setting the mararc variable handle_noreply to have a value of 0.

This test is in the directory sqa/regressions/borked_zone.

OK, some MaraDNS todos:

• Update the list of other DNS servers to mention unbound and dnsmasq
• Update the FAQ to add a workaround for the borked zone issue
• Add a man page for rg32hash
• Add Radio Gatun support to mqhash

Since there is a reasonable workaround (set handle_noreply to 0), I see no reason to try and fix the borked zone issue; I don't like making changes to the recursive resolver.

The snapshot can be downloaded at http://www.maradns.org/download/1.3/snap/2009

Deadwood 2.03 released

Well, I spoke too soon about not updating Deadwood until I can get my CentOS Vmware image up and going again. I discovered a bug in Deadwood this morning. The bug is pretty minor: Should Deadwood not be able to bind to all IP addresses it tries to bind to, it would end with a deceptive error message.

I just changed the code to have Deadwood still run as long as it binds to at least one IP address. Yeah, I should add code to warn the user which IP addresses we did not bind to, but the whole messaging system needs an overhaul.

This version of Deadwood has otherwise worked for me without problem for over four months. I am declaring this stable and Deadwood 2.03.

It can be downloaded here:

maradns.org/deadwood

The md5 sum is 9490d474a4a25b01297ce58e019c5994.

The sha1 sum is cb1e4dffb3e110208ea03b42345fa1adb4c56654.

The Radio Gatun 32 sum is
9d16f8e2d2a33fd5fc37f787d770cfd7a21309e97734862098cadf7b18be4d1f.

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.

MaraDNS snapshot update

Well, I've implemented a secure random number generator for the new Deadwood code. Last time, with MaraDNS, I used AES, which became an AES variant in late 2001. The problem with AES is that it may have cache timing issues with some CPUs, since it uses table lookups to get indexes based on key information. I revised the code to work around this, at the expense of making the code about three times slower. Also, the code is fairly large and block ciphers are not the best building block for making random streams.

This time, I am using a new stream cipher/cryptographic hash algorithm called "Radio Gatun". Radio Gatun is a new and novel cryptographic primitive: It's a cryptographic hash that can take an input of any length, and generates, from that input, a hash of any desired length. It's also (if not officially) a stream cipher that can take a key of any desired length.

Radio Gatun is a derivative of a late 1990s stream cipher/hash construction called PANAMA. PANAMA's cryptographic hash creation was broken, but it's (as far as we know) still as secure stream cipher. Radio Gatun is not as fast as PANAMA, but appears (so far) to be both a secure cryptographic hash and a secure stream cipher primitive.

Radio Gatun, in theory, can use words of any length from one bit to 64 bits. In practice, test vectors only exist for the 32-bit and the 64-bit versions of Radio Gatun. The Deadwood code is using the 32-bit version of Radio Gatun, but this can be fairly easily changed to use the 64-bit (or, if one wants, the 16-bit or even 8-bit) version by changing two defines in DwRadioGatun.h, and rewriting the dwr_rng() function.

Radio Gatun is a good deal more compact than AES; the entire library fits in under 2k (2048 bytes) when compiled with -Os; compare this with the 12k or so the AES-derived library uses.

---

I have also created a basic SQA test, and fixed some bugs. There was a minor bug in the FSM definition that made it so dwood1rc parameters could not have numbers in them, making ipv4_bind_addresses not work; this has been fixed. Another bug is that I did not use the socket bound on port 53 to forward the remote reply back to the local user; this made Dig unhappy, since Dig checks the port number of the reply.

In addition, I have added "DwMain -f dwood1rc" style argument parsing.

Oh, oh, there's some under the hood changes. DwMain.c is now a very small file; DwSocket.c has all of the functions that use socket-specific code (and no functions that don't use socket code) and DwSys.c has the rest of the functions. This way, adding DNS-over-TCP, ipv6, and WinSock support only requires changing the DwSocket.c file.

The DwMain binary, when compiled in DeLi Linux 0.7.2 with the -Os flag and stripped, is currently 14,092 bytes in size.

MaraDNS 1.3.07.06 and 1.3.09 release

Today I release not one, but two versions of MaraDNS: MaraDNS 1.3.07.06 and MaraDNS 1.3.09. These are both beta-test versions of MaraDNS; the changelog is here. Downloads of these versions of MaraDNS are available here (Scroll down to see the 1.3 releases).

I also have made a tiny version of the Radio Gatún hash function available under the same license terms as MaraDNS (BSD w/o advertising clause), which is available here.

- Sam