Wednesday, September 29, 2010

Yes, open source is a win-win

Open source is a win-win.

I am very pleased to let the MaraDNS community know that I have successfully gotten a job offer which I just accepted this week. This is a job offer which I would not have gotten if I had not kept my skills current while living in Mexico by continuing to develop MaraDNS, culminating with a three-year-long complete rewrite of the recursive code.

The timing for getting this offer is perfect. As I planned to do a year ago, now that MaraDNS 2.0 is out the door, I will put MaraDNS on the back burner. This will give me more time to be a productive worker at my new job and refine my programming knowledge to master new technologies, keeping my skills current in the 2010s.

I am going to continue to support MaraDNS, of course. I will fix important bugs brought up on the mailing list, and will naturally fix any critical security bug that may be found in MaraDNS. I will also answer emails on the mailing list when and if I have time to do so. But, I do not have any plans to add new features to MaraDNS at this time.

I would like to thank all MaraDNS users for all of your comments, feedback, bug reports, and feature requests. I have devoted a lot of the last decade to MaraDNS, and it has been an honor to freely give to the world something which I hope people find useful.

Open source development truly pays off. It’s a win for users, since they have good code which they can change any way they see fit; it’s a win for developers, because it allows them to showcase their work and demonstrate their programming discipline to prospective employers. I encourage people who are looking to improve their programming skills to become part of an open-source project. It can be frustrating at times; but it is also rewarding.

Tuesday, September 28, 2010

MaraDNS 2.0.01 released

I have released MaraDNS 2.0.01. This is simply MaraDNS 1.4 with the deprecated MaraDNS 1.x recursive DNS server removed, and with the documentation updated to reflect the fact that Deadwood 3 is now used for MaraDNS’ recursion. People, of course, are free to use MaraDNS 1.4 for as long as they want, but its recursive code is now deprecated and only supported for critical security updates.

I encourage users of MaraDNS to use Deadwood for all recursion with MaraDNS.

Friday, September 24, 2010

Deadwood 3.0.01 released

I have released Deadwood 3.0.01 today. With this release made, no new features will be added to the Deadwood recursive resolver for the foreseeable future. However, bug fixes and other routine maintenance will still be applied to this software package.

Deadwood is now a stable recursive resolver suitable for embedded systems, desktop PCs, or on internet servers. Deadwood is fully 64-bit compatible, has optional support for IPv6, and does not require threads to resolve records.

Deadwood 3.0.01 will be the recursive resolver for MaraDNS 2.0, which I will release shortly, as well as being an optional recursive DNS server to use in MaraDNS 1.4.

It has been a pleasure developing Deadwood and MaraDNS for nearly a decade. I will continue to support MaraDNS and Deadwood but have no plans to add new features once MaraDNS 2.0 is released.

In addition, I no longer need to accept donations for MaraDNS. All Deadwood and MaraDNS support needs to be done via the MaraDNS mailing list.

The 3.0.01 release of Deadwood is available here:

http://maradns.org/deadwood/stable/

Wednesday, September 22, 2010

New Deadwood snapshot: Parser bugs fixed

I have been uploading new Deadwood snapshots to fix some bugs in the dwood3rc parser; the parser now has the += (append) operator work correctly with dictionary variables, as well as having more stringent controls for dictionary indexes (dictionary variables must be initialized; a dictionary index can not be appended to without first being set; etc.) so that dwood3rc files must be working Python 2 scripts to correctly parse.

In addition, I have refined the documentation a little.

They can be looked at here:

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

Monday, September 20, 2010

New Deadwood snapshot: Two questions and answers added to FAQ

I have uploaded a Deadwood snapshot today that adds two questions and answers to the FAQ. One is about blacklisting domains with Deadwood, and the other is a brief note about how, as much as I would like Deadwood to have DNSSEC support, I am not in a place in my life where I have the time to implement DNSSEC “for fun and for free”.

The updated FAQ can be looked at here:

http://maradns.org/deadwood/doc/FAQ.txt

Thursday, September 16, 2010

Jobfox.com is a scam

For people looking for work, beware of Jobfox.com. I got hit by their scam when I was looking for work last week. Based on the various reviews about this company out there about this company, I can safely say that they are a scam.

The scam works like this: Jobfox.com has a number of job postings on their web site; once you sign up with them, they quickly send you an email that they have looked at your resume. They then tell you that your resume sucks, and that you should pay them $400 to improve your resume to have a chance in the job market.

They give this form letter to everyone who signs up for one of their postings on their site, giving out a letter like this: “Your resume does not pass the 30-second test, and the content is not up to the standards one would expect from a candidate like you. Countless studies have proven that resume quality is the key determinant as to whether a candidate is selected to be interviewed. Your resume needs a boost from a visual, content, and overall writing standpoint to engage the reader. It needs to make them want to learn more about you. I didn’t find it to be exciting, and it didn’t make me want to run to the phone to call you. In short, your resume is effectively sabotaging your job search.”

It does not matter how well-written one’s resume is. It does not matter if one has the best resume that was ever made. After Jobfox.com has their spambot scan your resume, they give you the above scathing criticism. Indeed, according to one anonymous poster, resumes written by Jobfox.com’s own resume writers get the above very negative review.

Googling the exact above phrase gives multiple results. Why am I not surprised?

Sunday, September 12, 2010

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.

Friday, September 10, 2010

New Deadwood snapshot: Improved documentation

I just uploaded a Deadwood snapshot; this snapshot has updated and improved the Deadwood manpage (typos corrected; Windows Reference.txt version of manpage updated). In addition, I have added install.bat and uninstall.bat batch files to the Windows port of Deadwood, and revised README.txt for Windows accordingly, so Windows XP users can now install (or remove) Deadwood with just one click.

It can be looked at here:

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

Update: I just tested this in Windows 7, and Deadwood is not a one-click nor two-click install, since right-clicking on a .bat file and choosing “run as administrator” changes the current working directory to \WINDOWS\system32. To install on Windows 7:
  • Go to the start menu and search for “cmd”
  • When found, rick click on it and run “cmd” as an administrator
  • At the cmd prompt, use the “cd” command to find and enter the directory where Deadwood is unpacked
  • Invoke the “install.bat” script from this directory
I will have to update Vista.txt and README.txt to point out how to install Deadwood in Windows 7 (and, presumably, Windows Vista) in the next couple of days.

An eulogy for DNScurve

OpenDNS is probably the strongest DNScurve proponent out there. So, when they start making moves to look for a DNSSEC engineer (as an aside, the position is no longer open; they finally convinced one of their own engineers to implement DNSSEC, probably while holding their nose), you know that DNSSEC has won.

DNScurve, with all due respect, never had a chance. It didn’t have a chance when I last talked about it a year ago. It’s downright moribund today.

Sure, on a technical level it has some really cool technology—in particular, I really like the (2^(255)) - 19 curve it uses for cryptography; a “stock” DNS packet can only fit 512 bytes of information (we can make the packet about 1280 bytes in size if we use EDNS), so a public key cryptographic primitive that offers strong security without needing to push around 3072-bit RSA signatures (the approximate size needed with RSA to get the same level of security as DJB’s “25519” curve) is very appealing.

But, unfortunately, standards are not judged solely on their technical merits. They are also judged on how well the people who work on the standards get along and are willing to make compromises.

DJB, as far as I can tell, was never willing to work with other people on DNScurve. He wanted it to be an end-to-end DJB-exclusive invention: His own “25519” curve for public key cryptography, his own Salsa20 stream cipher for encryption (a nice enough cipher, but it uses 32-bit words everywhere and doesn’t have a mode using 64-bit words), and his own “Poly1305”.

To top it off, DJB didn’t even implement a reference implementation of DNScurve. He wasn’t even willing to walk far enough outside of his ivory tower to make an implementation, make said implementation public, and allow people to see how it ran in the real world.

And, indeed, no one else implemented DNScurve either. The most notable implementation of DNScurve was GbDNS, but that was replaced by something called “QRP” a year ago. OpenDNS was the only other place that implemented DNScurve, but they’re now looking to implement DNSSEC.

DNScurve also suffered from being a solution looking for a problem. The only real issue DNScurve solved was the problem of being able to sniff DNS traffic and spoofing replies based on the traffic seen. It didn’t solve the problem of an upstream DNS server sending spoofed traffic. Quite bluntly, this is a problem OpenDNS’ current business model doesn’t want to see solved (they make their money from NX redirects and from having google.com point to their own web page), so it’s no surprise they advocated DNScurve for as long as they did.

DNSSEC, on the other hand, is already seeing wide adoption. BIND has always supported it, of course, and Unbound supports it. GbDNS also now has gone from supporting DNScurve to support DNSSEC. PowerDNS is getting DNSSEC support.

If things in my life ever change and I got a six-month paid sabbatical, I would also implement DNSSEC and make it part of Deadwood; I regret the fact I don’t have time to make a compact pure-C implementation of DNSSEC.

If you want to make a standard real, work with standards committees. I know DJB can do this; his excellent Salsa20 cipher is part of the eSTREAM portfolio (but, again, I’d like to see a 64-bit Salsa20, or, even better, a 64-bit version of Cha-Cha I would call Merengue, or even Merequetengue). It’s a shame he didn’t do the same with DNScurve. Hopefully, the 25519 curve can become a public key algorithm used in future revisions to the DNSSEC standard.

- Sam

Thursday, September 9, 2010

Deadwood 2.9.07 released: Faster resolution, better security

I have released Deadwood 2.9.07 today. Compared to Deadwood 2.9.06, this release offers:
  • Faster resolution speeds. I have fixed two significant bugs which measurably slowed down Deadwood’s resolution performance; now Deadwood has, on my home internet connection, performance better than Unbound (it took Deadwood 2.9.07 159 seconds to resolve a list of names; Unbound 1.4.6 needed 169 seconds to resolve this list).
  • Better security. The underlying hash compression function uses a “secret” number in its core that is usually only changed whenever a new Deadwood release is made. I have updated this code to now have another “secret” number that is changed every time Deadwood is started.
  • Spam zombie protection. For over a year, there was a bug in Deadwood that broke MX records. Not only have I fixed this bug in Deadwood 2.9.07, I also have set up Deadwood to disable MX records by default, since they are generally only used by email hubs and “zombie” computers spewing spam.
This release can be downloaded here:

http://maradns.org/deadwood/testing

Wednesday, September 8, 2010

New Deadwood snapshot: Resolve speeds comparable to Unbound

It looks like I have solved the issues people have reported with Deadwood being sluggish. The two bugs I fixed were one where Deadwood would delay timeout_seconds (normally 2 seconds) if there was a problem getting an upstream IP from its cache, and another where Deadwood would delay timeout_seconds if there were upper case letters in the name of a DNS reply.

I just ran Juergen’s test with Deadwood and Unbound. Deadwood is able to resolve the list of domain names on my network in 2:42 (two minutes forty-two seconds) and 2:54 (the 2:42 figure was done starting Deadwood with no cache); Unbound needed 2:57 to resolve the same list. In addition, namebench shows Deadwood doing a lot better than Unbound (far fewer lost queries and better average response time to the queries Deadwood does resolve) on my machine.

Steve Gibson’s DNS benchmark tool is buggy and incorrectly reports that Deadwood drops most DNS packets; I have set up Deadwood to report every reply it sends as well as every incoming query, and have verified that Deadwood replies to most, if not all, of its incoming queries when Gibson’s DNS benchmark is run against it.

In addition, I have revised Deadwood’s internal hash algorithm to be more secure: The algorithm, in addition to using a multiplication constant that randomly changes every time Deadwood is compiled in CentOS Linux or a new Deadwood release is made (which Deadwood has always done), now uses an additive constant that is different every time Deadwood is started. Deadwood is hard-coded to use /dev/urandom (secret.txt in Windows systems) for entropy to generate this additive constant from (we also get a bit of entropy from the timestamp); if this file is not found, Deadwood will fallback to using a hard-coded additive constant for its core hash.

I would like to thank Juergen Daubert, Wayne, and Marlon for their bug reports, feedback, and suggestions getting programs to help debug Deadwood’s performance.

The snapshot can be downloaded here:

http://maradns.org/deadwood/snap/deadwood-H-20100908-3.tar.bz2

Windows users can use this snapshot that has the improved performance (but not the improvements to Deadwood’s internal hashing function):

http://maradns.org/deadwood/snap/Deadwood-H-20100908-win32.zip

Please report any bugs to the mailing list [1].

- Sam

[1] Crash reports are useless unless they are accompanied by a stack trace or a recipe for reproducing the crash; Valgrind errors are invalid unless Deadwood is compiled with -DVALGRIND_NOERRORS

Note: Yeah, I’m still looking for work. Send me an email if you have a job for me.

Update: Anyone who downloaded deadwood-H-20100908-3 should download deadwood-H-20100908-4; this update is a hotfix that fixes dictionary variables which I broke in deadwood-H-20100908-3. Note also that dictionary variables work with the most recent Windows binary; it was the improved hash compression security which temporarily broke dictionary variables.

Yes, I do perform regressions to catch things like this, but only for numbered release (e.g. I’ll do the regressions before releasing Deadwood 2.9.07) and not for snapshot releases.

Monday, September 6, 2010

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/

Sunday, September 5, 2010

New Deadwood snapshot: MX record lookups disabled by default

Over the years, people have reported issues using MaraDNS as part of a mail hub, processing MX queries. This is a manner of using MaraDNS which I plain simply do not perform, and therefore have not adequately tested. The fact that releases of Deadwood with broken MX lookup support have been out for over a year, with no one letting me know about this bug on the MaraDNS mailing list (or me becoming aware of it myself with my own “dogfood” testing; I only became aware of it when I decided to make a MX lookup with Deadwood on a lark) indicate that this is not something widely used, much less tested.

My general feeling is that, if an average client machine is making a MX query, most likely it has been taken over by a spambot sending out spam. I have been using Microsoft Outlook and other MUAs (mail user agents) with Deadwood for over a year while its MX processing was broken and never saw a problem; a MUA does not perform MX lookups to send mail, but instead connects to the SMTP server, which does the actual MX lookups.

That in mind, in today’s snapshot of Deadwood, I have explicitly disabled MX lookups; if an MX lookup is made, the query is rejected and the IP is logged as being a possible spam zombie. There is a parameter which I have documented that will enable MX lookups again.

The fact of the matter is this: Using Deadwood with a mail hub making a large number of MX requests is completely untested. If one wants to use Deadwood in this manner, please subscribe to the MaraDNS mailing list and express the intention to help beta-test Deadwood for this use case which I do not have.

In the meantime, by disabling and logging MX lookups in Deadwood, we can make networks a little more secure and resistant to spam zombies commandeering machines on our networks.

Saturday, September 4, 2010

New Deadwood snapshot: Non-A records now resolve

I guess not that many people are testing Deadwood.

Let me be honest about the type of testing I’m doing with Deadwood: I am testing Deadwood’s as a DNS server used for casual web surfing on today’s internet. That means that most of the queries done are A queries; I don’t do much testing with AAAA (IPv6) queries because, quite bluntly, my ISP doesn’t offer IPv6 service and I can think of only one site on the Internet with an AAAA record: ipv6.google.com.

Likewise, I haven’t done any testing with MX records. I haven’t touched MX records at all because I’m not using Deadwood with a mail hub. So, it came as an unpleasant shock to me when I discovered last night that Deadwood hasn’t been properly resolving MX records for over a year.

In Deadwood 2.4.05 (released August 9, 2009), I added the ability to rotate resource records. Unknown to me, this feature broke Deadwood with any variable-length record, such as a MX record pair where the hostnames are of different lengths.

The advantage of using Deadwood’s robust string library with almost all of Deadwood’s DNS processing is that this bug did not result in any memory corruption or cause any other problems; the only issue has been that Deadwood would not resolve MX or other variable length records.

The idea that some freetards advocate that open source software is magically tested and that all bugs become shallow is nothing more than so much—how should I say this—mental masturbation. The author of Mailman, John Viega, points out how wrong this is in his excellent essay “The Myth of Open Source Security”.

Excuse me for the blunt wording, but I am a little frustrated right now: I have devoted a decade of my life to MaraDNS, and I haven’t even been able to get a job because of my hard work; while I have had a couple of interviews I would not have had because of MaraDNS, so far I have gotten no offers. Yes, those are interviews I would not had have if it weren’t for MaraDNS, and, yes, MaraDNS kept my skills from getting completely rusty during the ’00s when I was concentrating on learning Spanish and living in Mexico. But, looking back, I really wish I had spent more time learning C++ and object oriented programming and less time editing the Wikipedia or posting to /..

It looks like Deadwood isn’t getting much external testing; not one person saw Deadwood’s issue with MX records in the year Deadwood has had this bug. So, yeah, like everything else with MaraDNS, I’m responsible for just about all of the testing. This isn’t a complete loss; people have asked me in interviews about my testing methodology for MaraDNS.

I have just uploaded a snapshot which fixes the issue with rotating records like MX records:

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

As a side benefit, since I have fixed this issue, TTL aging and RR rotation now work with ANY records.

Next: Set up a test for this issue, as well as DNS compression tests for all of the resource record types MaraDNS supports. If I get time, I will also set up tests to make sure Deadwood correctly handles things like SRV records with compression pointers, and that Deadwood doesn’t compress SRV records.

Friday, September 3, 2010

Deadwood 2.9.06 released

I have just released Deadwood 2.9.06. This is Deadwood 2.9.05 with its handling of empty DNS packets tweaked to handle the corner case of a DNS server giving out an empty packet better. It’s been two weeks since the last Deadwood testing release and it looks like I’m getting down to the nitty-gritty corner cases that only affect a tiny percentage of DNS resolutions (properly configured DNS servers do not give out empty DNS packets).

My plan is to release Deadwood 3.0.01 in a little over two weeks.

Meanwhile, Deadwood can be downloaded here:

http://maradns.org/deadwood/testing/

Thursday, September 2, 2010

New Deadwood snapshot: Better heuristics for empty DNS packets

When a remote server sends us an empty DNS packet, what does that really mean? Well, it usually means that the hostname does not always exist. But, not always.

Let’s take the hostname ibnlive.in.com. It has three DNS servers: 123.108.40.31, 123.108.40.32, and 123.108.40.81. Two of the servers (123.108.40.32 and 123.108.40.81) do the right thing: They redirect the name to Akamai’s horrendous mess of DNS resolution. However, 123.108.40.31 is broken and gives us a blank DNS packet with a SERVER FAIL message.

The DNS administrators for in.com aren’t trying to tell us that ibnlive.in.com doesn’t resolve. No, they’re trying to tell us that their DNS administrator is asleep and misconfigured one of their three DNS servers.

So, I’ve tweaked the heuristics of Deadwood to treat a DNS packet with a “SERVER FAIL” RCODE as being one where the DNS server is asleep at the wheel, so instead of treating the packet like “this name does not exist” (like what we normally do with a blank DNS reply), we ignore the packet and bug the next DNS server on the list. The code isn’t perfect: We wait timeout_seconds before contacting the next server, but it’s good enough to have domains mismanaged like this correctly resolve.

I should note that the bugs I’m finding in Deadwood right now are not bugs caused by Deadwood not being RFC-compliant—the last bug I fixed like that was on August 9. No, at this point, I’m fine-tuning Deadwood to more or less do the right thing with mismanaged domains and broken DNS servers.

As always, the snapshot can be looked at here:

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

Wednesday, September 1, 2010

New Deadwood snapshot: Better handling of empty packets

I have uploaded a new snapshot of Deadwood which improves Deadwood’s handling of empty packets. A number of broken DNS configurations and servers out on the internet, such as the DNS servers answering the IPv6 (AAAA) query for wwwchase.gslb.bankone.com, send out an empty DNS packet instead of a correctly made SOA-in-NS-section DNS reply when a host name can not be found.

Another situation where a DNS server gives out a reply like this is when someone stops paying for their domain, so the ISP suspends their account by removing the zone for their domain. However, this information has not been changed upstream. As a result, when we contact the DNS servers for a given zone, the DNS servers give us a blank QUERY REFUSED reply.

Since these do happen, Deadwood now pretends that a blank DNS reply is a low-TTL “SOA-in-NS-section” reply. This should speed up some queries, especially on IPv6-capable computers that perform AAAA queries before doing A queries.

It can be looked at here:

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

I should point out that I wrote the code to do this in a way to minimize the amount of code added to Deadwood and to maximize code reuse by having the relevant code in DwRecurse.c call the already created make_synth_not_there_answer() function made a little-more general purpose.

Tuesday, August 31, 2010

MaraDNS progress report: Documentation updates

I am continuing to update MaraDNS 2.0’s up and-coming documentation to correctly reflect the fact that all recursion is now done by the separate daemon Deadwood. I have also updated Deadwood’s manpage to state that Deadwood is a fully recursive DNS server.

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

Monday, August 30, 2010

New MaraDNS 1.9 snapshot

I made some progress with updating the documentation for MaraDNS 2.0; I have updated the mararc man page to remove parameters that are used for MaraDNS 1’s recursion, as well as adding a section in the update document on updating from MaraDNS 1.4 to MaraDNS 2.0.

I plan on adding a couple of details from the Deadwood FAQ to MaraDNS’s upgrade document, as well as updating MaraDNS’ tutorials to discuss using Deadwood for all recursion.

I am considering MaraDNS 1.9.x releases “snapshot” releases since I am making them fairly quickly right now.

They can be looked at here:

http://maradns.org/download/1.9

Sunday, August 29, 2010

MaraDNS 1.9: Moving towards MaraDNS 2.0

I have made the changes to MaraDNS’ codebase to prepare her for the MaraDNS 2.0 release. The changes are (drum roll) pretty simple, actually: I have gone through all of the #ifdef AUTHONLY statements to either keep them as AUTHONLY statements, or to change them to #ifdef IPV6 for statements which enable IPv6 support (MaraDNS 1 has no recursive IPv6 support, so AUTHONLY is also used to enable IPv6).

The only other change I have done is to revise the build scripts to:
  • Always define AUTHONLY when compiling MaraDNS
  • Update the configure script and Makefiles to allow one to enable or disable IPv6
  • Not link MaraDNS to the pthreads library (MaraDNS 2.0 will be thread-free)
  • Compile Deadwood as MaraDNS 2.0’s recursive resolver
  • I removed makefiles for all operating systems besides Linux, Windows, and a generic *NIX “noflock” makefile
It can be looked at here:

http://maradns.org/download/1.9/

At this point, the code for both MaraDNS 2.0 and Deadwood 3.0 (the recursive resolver MaraDNS will have) are done: The only changes will be bug fixes. The thing I should do at this point is revise MaraDNS’ documentation to reflect the MaraDNS 2.0 changes, as well as removing any MaraDNS 1 SQA tests that test MaraDNS’ recursor.

One issue MaraDNS 2.0 will have is that the recursive resolver will require a separate IP, and that there isn’t an automated way to convert a MaraDNS 1 mararc file in to a MaraDNS 2 mararc file and Deadwood 3 dwood3rc file. This in mind, I have no plans to stop supporting MaraDNS 1.4 for critical security fixes and other important bugfixes and updates (such as updating the default list of root nameservers) for the foreseeable future, as well as supporting MaraDNS 2.0 for “this host does not resolve” bugs, as well as other bug fixes.

Saturday, August 28, 2010

ObHack 007.0 released

Fritz has made a release of ObHack 007.0, which I have uploaded to my web site:

samiam.org/slump

More information and support for this release is here:

http://www.doomworld.com/vb/doom-editing/52407-obhack-007-0-released-random-map-generator/

Friday, August 27, 2010

Deadwood update: No news is good news

No news is good news.

And, there’s no news for Deadwood this week. The only updates since 2.9.05 released a week ago today are documentation updates. I haven’t seen a single site not resolve in Deadwood that can resolve with other DNS servers.

I encourage users to continue testing Deadwood and reporting bugs on the MaraDNS mailing list.

Monday, August 23, 2010

Blog update: Comments disabled

I have had to disable comments because people were using the comment system for MaraDNS/Deadwood support concerns. Unfortunately, I do not have the time to use this blog to support MaraDNS and ask that people who have bug reports or whatever to take the time to join the MaraDNS mailing list and share with the list their concern. I have updated the FAQ for this blog to explain my thinking in more detail.

Friday, August 20, 2010

Deadwood 2.9.05 released

As long as I find bugs that stop sites from resolving, I will continue to make weekly releases of Deadwood.

I’ve added a workaround for one particular broken DNS server as well as fixing resolution of ANY queries that point to CNAME records.

It can be looked at here:

http://maradns.org/deadwood/testing/

There is also a change log available.

Monday, August 16, 2010

New Deadwood snapshot; allowing anonymous comments

I have just uploaded a new Deadwood snapshot; this release does not change the program, but it has updated the INSTALL.txt file to be current and all compile-time flags Deadwood has are now documented.

It can be looked at here:

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

This may be my last snapshot announcement for Deadwood snapshot updates when the actual Deadwood program has not been changed.



I have enabled anonymous comments in my blog again, since it looks like Google has enabled comment spam protection. As always, comments posted here are moderated and Deadwood/MaraDNS support requests will not be published, nor will flames, trolling, and spam.

Sunday, August 15, 2010

New Deadwood snapshot: mkSecretTxt added; doc/internals updated

In today’s snapshot of Deadwoood, I have added the mkSecretTxt program I made for the 1.4.04 release of MaraDNS. When adding it to Deadwood, I have added a test to make sure secret.txt does not exist before overwriting it. The thinking is that Windows shies away from potentially dangerous commands more than *NIX does; since overwriting secret.txt without prompting is an example of the old dangerous (and, IMO, obsolete) *NIX way, mkSecretTxt no longer does this.

In addition, I have gone through the doc/internals folder and updated the files there. In the case of a couple of files, I just added a note that the file in question is out of date.

It can be downloaded here:

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

OK, back to learning C++.

Saturday, August 14, 2010

Deadwood snapshot update: Working around aplus.net’s broken DNS server

Aplus.net’s DNS server is broken.

Let’s contact their DNS server for the A record for bookride.com:

$ dig @64.29.144.70 www.bookride.com

; <<>> DiG 9.3.6-P1-RedHat-9.3.6-4.P1.el5_4.2 <<>> @64.29.144.70 www.bookride.com
; (1 server found)
;; global options: printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 10397
;; flags: qr aa rd; QUERY: 1, ANSWER: 1, AUTHORITY: 1, ADDITIONAL: 0

;; QUESTION SECTION:
;www.bookride.com. IN A

;; ANSWER SECTION:
www.bookride.com. 3600 IN CNAME ghs.google.com.

;; AUTHORITY SECTION:
google.com. 86400 IN SOA ns1.aplus.net. hostmaster.aplus.net. 1007 86403 3600 3600000 86400

;; Query time: 304 msec
;; SERVER: 64.29.144.70#53(64.29.144.70)
;; WHEN: Sat Aug 14 01:18:15 2010
;; MSG SIZE rcvd: 119

This is an invalid packet: It is marked as a NXDOMAIN (complete with a SOA record in the NS/Authority section), but it is actually a CNAME.

I have updated Deadwood to treat these broken packets like ordinary CNAME packets. The snapshot can be downloaded here:

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

I am also in the process of trying to file a bug report with aplus.net.

Friday, August 13, 2010

Deadwood 2.9.04 released

I have released Deadwood today. This is the recursive resolver that I recommend all MaraDNS and Deadwood users use unless they have a compelling reason to use an older release of a recursive resolver; all other MaraDNS recursive code will now only be updated to address critical security problems. For example, if MaraDNS 1.0’s resolver stops being able to resolve www.google.com or www.microsoft.com tomorrow, I will not update it; I will tell people to update to Deadwood.

That said, this is still a beta-test release of Deadwood. The code has only been beta-tested for under a month and I want to get two full months of beta testing before declaring it stable. I really appreciate all of the bugs and issues Sebastian Müller has reported and hope other people also test this software and report issues.

It may seem unusual that I am not fixing bugs with the stable 1.0 recursive resolver while the Deadwood (MaraDNS 2.0) recursive resolver is only undergoing beta-testing. This isn’t entirely true; if someone reports a bug with MataDNS 1.0’s recursive resolver and wants it fixed, I will fix it. For a price. My business model with MaraDNS is to use the program as my resume (since I was having fun in Mexico during the first decade of the 2000s, it’s how I have been keeping my computer skills up to date), as well as accepting donations and selling service and support. [1]

Right now, the kinds of bugs I want people to look for and report in Deadwood are host names that do not resolve. If there is a host out there that correctly resolves in BIND or whatever, but doesn’t resolve in Deadwood, I want to know about it. I also want to know about any memory leaks people find in Deadwood. I welcome reports of crashes, but only if accompanied by a stack trace or recipe to reproduce the crash (ideally both). Valgrind errors are OK to report, but only if Deadwood is compiled with “VALGRIND_NOERRORS” defined (export FLAGS='-g -DVALGRIND_NOERRORS' ; make from the src/ directory of Deadwood). I would love people to test IPv6 compatibility with Deadwood; the SQA regressions tell me Deadwood works with IPv6, but I would love reports from users on IPv6 networks to see if they are any real-world problems with it (IPv6 needs to be explicitly enabled when compiling Deadwood: export FLAGS='-O3 -DIPV6' ; make ).

Deadwood 2.9.04 can be downloaded here:

http://maradns.org/deadwood/testing/

[1] I find it incredibly naive when people tell me I work on MaraDNS because I want to tweak things or what not. No, sorry freetards, the amount of work I do on MaraDNS is far greater than tweaking around and installing a new Linux distribution or compiling a program with different optimization flags. The reason I worked so hard on MaraDNS is because I wanted to make my mark on the world, have my Wikipedia page. I did that. And it was a nice way for me to pass the time during slower moments in Mexico when there weren’t girls around to flirt with. But, now I’m married and I need to think about the bottom line. Amazing how a wife changes my priorities.

Wednesday, August 11, 2010

Deadwood 2.3.06 released

I released Deadwood 2.3.06 today. This is a minor update to the older caching-only branch of Deadwood; most users of Deadwood will want to use the current 2.9 branch of Deadwood which has full recursion.

The update is one with possible (but not readily exploitable) security implications. There is a potential null pointer dereference in Deadwood’s underlying string library that the four-line patch assures never happens. As far as I know, there is no way to exploit this issue in Deadwood 2.3 (the bug only popped up when stressing the string library more in the recursive code in Deadwood 2.9), but it is prudent to update the older tiny branch of Deadwood.

Most of the work making this release was updating the tests to work with CentOS 5.5. CentOS 5.4 → 5.5 was supposed to be a bugfix-only update, but, not only did they update Valgrind to a newer version with different output, they also broke select(). The SQA tests have been updated to pass in CentOS 5.5.

The main advantage of the tiny branch of Deadwood is that its binary is only about 32 kilobytes in size, as opposed to Deadwood 2.9’s 64 kilobyte binary. There may be certain tiny embedded systems where this matters. Another advantage is that it can be optionally compiled without caching, making it act as a DNS load balancer. The main disadvantage is that it is a non-recursive cache; it needs another recursive server (like Deadwood 2.9) to do the “heavy lifting” of recursively solving DNS queries.

It can be looked at here:

http://maradns.org/deadwood/tiny

Since this is a maintenance update to an older branch of Deadwood, I have not made Windows binaries. Windows users: Please compile it yourself or, better yet, just use Deadwood 2.9 instead. Really, I can’t think of a machine out there that can run Windows XP (Deadwood won’t run on 95/98/Me because it is a service) where it matters whether the DNS server is 32 or 64 kilobytes in size. The 90s are, like, so over.

Tuesday, August 10, 2010

Where is the money?

This job market is scary

Sometimes, in the middle of the night, I just wake up and I can’t sleep anymore. I wonder if I am going to be able to re-enter the technology field or if I’m just going to end up teaching ESL for the rest of my life.

How MaraDNS came in to being

About a decade ago, everything was right. I had a well-paying promising contract with a major software company. I was making far more money than I knew what to do with. The work environment was fun and there was no limit with where I could take my career.

I was miserable.

It didn’t help that the girl I was dating at the time was not working out. When I finally let her go—she still owes me $312.98 for the record—I could not for love or money get a decent date. Having to commute for an hour followed by working eight hours followed by another hour coming back home five times a week doesn’t leave me much time to be part of the singles scene.

Something had to change.

The last job I had in technology before the dot-com bubble popped was for an internationalization firm. I met a lot of people from a lot of countries speaking a lot of languages. This revived my long-dormant interest in learning Spanish. Once that company died when the dot-com party ended, I went down to Mexico for a few months to learn Spanish.

It was a life-changing experience. I instantly went from being a guy who couldn’t get a decent date to save my life to someone who had this beautiful girl in my bed passionately making out with me. While things sadly didn’t work out with her, I discovered a world where I was no longer isolated and miserable. I had found home.

Of course, I wasn’t going to put my technical skills to waste. No, I wanted to make a name for myself and MaraDNS was already well underway when I was still working in the dot-com industry. It ignited my passion because here was something that wasn’t going to get forgotten when the company I worked for got bought out two times. It was my chance to make my mark on the world.

And, indeed, it has. You do a Google search of my name and MaraDNS is the third link that pops up. It has a Wikipedia entry. Indeed, MaraDNS is notable enough that the entry can not be easily deleted by the kinds of Wikipedia editors hell-bent on removing anything they can from the Wikipedia [1], because it has been used by a number of people and mentioned in books, in the title of a ZDnet article, as well as a number of scholarly papers.

After over a year of hard work, I released MaraDNS 1.0 on June 21, 2002. Then I went back to college and put MaraDNS on the back burner. Sure, I fixed bugs, but with all of my studies, and with adjusting to living in a far more conservative town than where I lived before (something I never fully adjusted to, quite frankly), I put MaraDNS on the back burner, sometimes going as long as half a year without updating it. Even back then, I wanted to rewrite MaraDNS’ recursive code, but just didn’t have time to do it.

As things were winding down with college and I was getting accustomed to life in that town, I was able to devote some time to improving the authoritative half of MaraDNS, including adding non-recursive IPv6 support to MaraDNS and improving its zone file format. This culminated with MaraDNS 1.2 being released in late 2005, a few months after I graduated from college. I then made some minor revisions to the zone file format to make it possible to write a Python script to convert BIND zone files in to MaraDNS zone files; that resulted in the 1.3 release a year after 1.2 was released.

It was between the 1.2 and 1.3 releases that I decided it was more important to go back to Mexico to improve my personal relationships than to try and get a job in the computer industry again. I had two notable rejections because I didn’t know more about C++ and objected-oriented programming, from both Google and a startup in southern California, and ended up briefly working as a cashier in Wal*Mart before throwing in the towel and going back to Mexico.

While dating girls down in Mexico, not only did I get a Python script to convert BIND zone files to MaraDNS zone files done, I finally started work on rewriting the recursive engine, something I had wanted to do for years. I started writing Deadwood in late 2007, with me planning to have a standalone recursive DNS daemon finished in mid-2008.

That didn’t happen. I had the fully non-recursive cache finished by late 2007, but then realized I had to concentrate more strongly on dating to have the right girl in my life in 2008.

It was while dating in 2008 that I started realizing the needs to put boundaries on MaraDNS support and start looking in to getting compensated for my hard work. Private email support was getting backlogged, so I finally had to let people know I would not support MaraDNS via private email without being paid for my time. People who appreciated MaraDNS started paying me a little in the tip jar I set up or by paying me a token sum for me to implement a feature they wanted in MaraDNS.

I had lost a lot of my free-software ideals at this point. I believed in 2000 that the year of the Linux desktop would happen. In 2004, I got off my high horse and started dual-booting in to Windows. In 2008, I got rid of my Linux partition altogether and started using Windows with Cygwin and a VMware virtual machine for the occasional Deadwood development I did that year. As I started developing Deadwood again, I tried putting Linux on my computer and liked it so little that I stabilized on the current setup I have for Deadwood development: Windows XP as my primary desktop OS, along with a CentOS 5 virtual machine which I use to develop Deadwood.

While this was going on, I found the girl who is today my wife in late 2008, and then had both a setup in place and some more free time to devote to working on Deadwood in 2009.

After getting most of the underlying support for having a fully recursive nameserver done (DNS compression support, integrated DNS-over-TCP support, full mararc dictionary variable and “execfile” support, “ip_blacklist” support, inflight merging, etc.), things with my girlfriend got serious and she became my fiancée. With marriage looming on the horizon, I grew up and realized it was time to make a roadmap to put closure on MaraDNS.

I was, when I made that decision, close enough to having Deadwood be fully recursive that I made Deadwood’s full recursion the point when I would declare MaraDNS done. I started work on Deadwood again in early 2010, and finally had full recursion finished in late July of 2010.

So, yeah, MaraDNS is finished. This doesn’t mean I am never going to make another release of MaraDNS. MaraDNS 2.0 is simply going to be MaraDNS 1.4 with the old recursive code thrown out, replaced by Deadwood being integrated in to the build script.

I will also update the documentation telling people how to update from MaraDNS to Deadwood. This will have to be done by hand; in order to ease the transition, I will support both MaraDNS 1.4 and 2.0 with security and other critical bug fixes for the foreseeable future. I also have no plans to stop fixing “this host does not resolve with Deadwood” bugs.

In addition, I am getting some minor sponsorship for MaraDNS, and will consider implementing features my sponsors want to implement. The only other thing I might do is add some more extensive SQA tests to test for bugs in fully recursive Deadwood (I currently only have one that tests one kind of recursive query).

Back to reality

So, yes, MaraDNS is finished. Time to get back to reality. I have been spending the last couple of weeks, along with fixing bugs in Deadwood, learning about a lot of new technologies. I have a mid-1990s book on Object Oriented programming I have almost finished (inheritance, both single and multiple, abstract classes, throwing and catching exceptions, a bit on C++ templates).

I had a phone screen for, of all things, a Javascript position yesterday. The position didn’t pan out: Even after spending all last weekend madly studying and learning Javascript, and explaining it is hardly the first scripting language I played with, my technical knowledge was not up to par with what they were looking for.

A good friend of mine told me last night I need to get more focused to get something in today’s job market. Since I have decades of C programming experience, and well over 60,000 lines of C code to show potential employers (MaraDNS), it makes the most sense to expand this with C++. There is the argument that it may make more sense for me to instead concentrate on Objective C, but the issue there is that I’m not a user of Apple’s products and don’t see too much money selling 99 cent iPhone toy applications.

I feel, if I improve my C++ programming, I will be able to get a good job, possibly with Google. Back during the dot-com days, I went to a lot of Linux User Group meetings where I met such people as Paul Vixie, Larry Wall, Linus Torvalds, RMS, as well as getting on a first-name basis with Chris DiBona. I think I will shoot Chris an email and see what ideas he has for me getting a stable corporate job.

I also have, bouncing around my head, a couple of ideas of how I can use the MaraDNS code to make a commercial product. I’m not sure how to develop the ideas and make a product from them, but I have already sent out a couple of emails to people who may have an idea how to start a business with them.

I’ve grown up. The 2000s were a good decade, since not only did I become fluent in the Spanish language and make my mark on the world with MaraDNS, an excellent high-security tiny embedded DNS server, I also found the woman who today is my wife.

There are some things I regret. I feel I spent too much time in the 2000s editing the Wikipedia, posting to Slashdot, making chess variants, or playing video games by myself; time I could have spent mastering C++ and being in a better position to get a job in the tech sector today. Indeed, I have a strict “no posts to Slashdot, no edits to the Wikipedia, and no chess variants” rule I made for myself so I can focus on the things I need to do to be a good husband for my wife.

So, yeah, even though everything seems scary right now and I wake up with these anxiety attacks when I bomb a phone screening like what happened yesterday, I know there is a good job out there for me for the 2010s that will support my wife and myself. I just have to keep trying, not give up, and not get upset every time I try and fail.

[1] A classic example of the internet dork rule. I find it rather fitting that the twit who tried to delete the MaraDNS article is not only completely anonymous (unlike my Wikipedia account which I haven’t used since March), but also is someone who has been blocked for rude Wikipedia behavior, something that hasn’t happen to me [2].

[2] Truth in reporting compels me to point out I once had a 24-hour block for violating something called the “three revert rule” back in 2005, when I thought it was worth wasting my time arguing with the kinds of people who like to pretend their kitchen is their own empire that they are the grand emperor for. Oh, how I wish I had spent the time I wasted arguing on the Wikipedia (and, yeah, /.) learning C++ or Java.

Monday, August 9, 2010

New Deadwood snapshot: neustar.biz fixed

While doing my own “dogfood” testing for Deadwood, I discovered that the host name “neustar.biz” did not resolve. The issue was that I never bothered to make DNS queries case-insensitive.

The solution is to convert all DNS queries in to their lower-case form before looking them up in the cache or sending another query out to resolve a glueless NS/incomplete CNAME (in the case of “neustar.biz”, the issue was that the CNAMEs were in upper case). In addition, since there may very well be some stub resolvers out there that won’t accept an answer unless it’s in the same case as the question, I now have Deadwood preserve the case in the original form of the query to give back to the stub resolver, using a variable called “orig_query”.

It can be downloaded here:

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

The patch can also be looked at.

I can see the program is getting some attention by the number of clueless emails I am getting asking for private Deadwood support. It would be nice if these people would pay me once I give them the usual form reply asking for money. That has not happened; people who do not have enough courtesy to heed multiple disclosures that email is only for paying customers are not courteous enough to decide to pay for support. It’s a form of the internet dork rule: The anonymity of the internet coupled with the ease of getting on a soapbox attracts all kinds of unpleasant people; the corollary to this rule is that any unmoderated forum is soon overrun by unpleasant people, since anyone who doesn’t want to waste time getting in to a flame war is soon chased away by the trolls and flamers.

Hopefully this attention will soon translate in to a job with a living wage. Things are tough in this economy, and looking for work is sometimes very frustrating. The only serious interest I have gotten is from people who know about MaraDNS or from connections. Simply putting my resume out there on Monster or Dice so far hasn’t resulted in anything.

Sunday, August 8, 2010

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).

Friday, August 6, 2010

Deadwood 2.9.03 released ; some thoughts on EDNS

I have released Deadwood 2.9.03 today. This is Deadwood 2.9.02 with a number of bug fixes added, as described in the Deadwood change log.

It can be downloaded here:

http://maradns.org/deadwood/testing/
One of the bugs I have fixed in Deadwood 2.9.03 is to change how EDNS (RFC2671) packets are handled. It used to be that Deadwood would just discard such packets, since Deadwood’s policy is to ignore anything that looks unusual.

RFC2671, in section 5.3, says that these packets should be handled by sending an error message back; I use the error message NOTIMPL (“not implemented”), which RFC2671 suggests as a possible error to give back when an EDNS request is sent. However, thinking about it some more, it may make more sense to what MaraDNS and DJB’s dnscache do: Treat a DNS packet with an EDNS section as if the packet were an ordinary DNS packet, ignoring the EDNS information.

The advantage with this approach is that poorly written non-RFC-compliant DNS servers which aren’t smart enough to try with a non-ENDS packet after getting a “not implemented” reply will still work with Deadwood. Considering that MaraDNS and dnscache have done this for years, it looks like this approach won’t result in any problems.

Update: I just uploaded a snapshot of Deadwood which by default ignores the EDNS part of a EDNS query. The old RFC-compliant behavior of sending a NOTIMPL can be enabled by defining STRICT_RFC2671_COMPLIANCE when compiling Deadwood. It can be downloaded in the usual place.

Thursday, August 5, 2010

NanoDNS updated

I’ve updated NanoDNS to work (in theory) on 64-bit machines, and to handle EDNS packets a little better:

/*Placed in the public domain by Sam Trenholme*/
#include <arpa/inet.h>
#include <string.h>
#include <stdint.h>
#define Z struct sockaddr
#define Y sizeof(d)
int main(int a,char **b){uint32_t i;char q[512]
,p[17]="\xc0\f\0\x01\0\x01\0\0\0\0\0\x04";if(a>
1){struct sockaddr_in d;socklen_t f=511;bzero(&
d,Y);a=socket(AF_INET,SOCK_DGRAM,0);*((uint32_t
*)(p+12))=inet_addr(b[1]);d.sin_family=AF_INET;
d.sin_port=htons(53);bind(a,(Z*)&d,Y);for(;;){i
=recvfrom(a,q,255,0,(Z*)&d,&f);if(i>9&&q[2]>=0)
{q[2]|=128;q[11]?q[3]|=4:1;q[7]++;memcpy(q+i,p,
16);sendto(a,q,i+16,0,(Z*)&d,Y);}}}return 0;}

This is a little bigger than the last version of NanoDNS I posted, but it’s still the world’s smallest useful DNS server. The above code handles a problem people frequently ask on serverfault: “How can I set up a DNS server to always return the same IP in reply to any query?” The program takes one argument: The IP we return. This program binds to all IP addresses a given machine has on the DNS port (port 53).

I’ve also updated MicroDNS (NanoDNS’s big sister, with fancy features like selectable IP to bind to) to better support EDNS packets:

http://samiam.org/software/microdns.html

Update: For people who wonder how NanoDNS does its magic, I now have a page that explains its source code line-by-line.

Tuesday, August 3, 2010

On the AES instruction set

I mentioned, in a recent blog entry, how much I like the Rijndael cryptographic primitive and why I was very happy when it became the official AES standard.

Once Rijndael was chosen for AES, it did not take long for VIA to add hardward support for it via their VIA padlock (which also included other cool things to have, such as fast SHA support, fast RSA support, and, nicely enough, a true hardware random number generator).

Unfortunately, VIA does not have a prominent enough position in the mindset of people who buy x86 processors to lead the way in terms of x86 extensions (for example, Lenovo for a while was selling a low-cost 12-inch netbook using a VIA instead of an Intel processor, but now all of Lenovo’s netbooks are 10-inch netbooks with the Intel Atom N455, a very nice little processor). So, when Intel decided to implement AES, they used their own instruction set called, simply, the “AES Instruction Set”.

What the AES instruction set does is perform an entire round of the AES encryption process on a 128-bit block. This can be used for AES encryption, of course, or for any related cipher that can use AES’ round function in its core. The SHAvite-3 hash function, for example, uses 128-bit AES for its code. It’s fairly easy to adapt the output to perform 256-bit Rijndael; as well as allowing Rijndael variants with different block sizes, a round transformation of the proposed hash/stream cipher LUX-224/256 uses [1] is Rijndeal-256.

The AES Instruction set is supported by the following CPUs by Intel:
  • Core i7-610E, i7-620M, i7-620LM, i7-620LE, i7-640LM, i7-620UM, i7-620UE, i7-640UM, i7-660UM, i7-970, i7-980X, i7-990X
  • Core i5-520M, i5-520E, i5-540M, i5-520UM, i5-540UM, i5-650, i5-655K, i5-660, i5-661, i5-670, i5-680
  • Xeon E5620, E5630, E5640, E5667, L5609, L5618, L5630, L5638, L5640, W3680, E5645, X5650, X5660, X5670, X5677, X5680
[1] I understand the original LUX was broken, but there is a revision to LUX that hasn’t been broken (yet)

Monday, August 2, 2010

Deadwood snapshot update

I have updated Deadwood to fix two bugs:
  • Large packets that needed DNS-over-TCP were not working when Deadwood was using full recursion. Fixed.
  • It is now possible to have a recursive_acl without the recursive_acl having a netmask (there is a mailing list posting with a description of the issue)
The updated snapshot can be downloaded here:

http://maradns.org/deadwood/snap/deadwood-H-20100802-2.tar.bz2

Sunday, August 1, 2010

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.

Saturday, July 31, 2010

MaraDNS 1.4.04 released

Now that Deadwood is feature-complete, I have released MaraDNS 1.4.04. This is the most current stable release of MaraDNS; if using an older MaraDNS, please update to this release (yes, I ran a bunch of SQA tests so anything that worked before should work in 1.4.04).

While the old recursive code is still in place to allow people to slowly make the transition to using Deadwood as their recursive DNS server, Deadwood 2.9.02 is included. The Windows version of MaraDNS has had its documentation updated to encourage people to use Deadwood for recursion instead of MaraDNS; I will also start nudging *NIX users along.

I have also, as blogged about yesterday, made a tool for getting entropy from the OS and putting it in a file. This is currently a very simple tool; it makes a random 64-byte file called secret.txt which MaraDNS and Deadwood can use. It acts like a UNIX command: There is no user interface; when it is run, it just silently creates the 64-byte random secret.txt file, overwriting any already existing secret.txt, and only outputting something if something goes wrong.

It’s a lot better than the old “just type in some random text to make secret.txt” directions I have given. I plan on making it a little more friendly (failing if secret.txt already exists, and stating the secret.txt file has been created, and always pausing and having the user hit a key so they know what the program is doing if called from the GUI.)

In addition, I fixed the bug with delegation NS records and ANY queries, as well as incorporating a NAPTR bugfix I made a few months ago in to the code. There is a full changelog.

It can be looked at here:

http://maradns.org/download.html

Or here:

http://sourceforge.net/projects/maradns

Friday, July 30, 2010

Deadwood and MaraDNS now have a Windows tool for making secret.txt

Deadwood and MaraDNS now both have a tool for getting entropy (random numbers) so that the file secret.txt is automatically generated. I call the tool "mkSecretTxt", and its source code can be looked at here:

http://samiam.org/software/mkSecretTxt.txt

Or downloaded as a C source file here:

http://samiam.org/software/mkSecretTxt.c

The file is a Windows port of the following *NIX command:

dd if=/dev/urandom of=secret.txt bs=64 count=1

In English: My program creates a 512-bit (64-byte) file called “secret.txt” using CryptGenRandom() to acquire the entropy from the Windows operating system.

This tool will make it easier for people to install and use MaraDNS and Deadwood in Windows, since they only have to run this program once to get some entropy for the servers’ random number generators.

Thursday, July 29, 2010

Deadwood 2.9.02 released ; keep on testing guys

I have released Deadwood 2.9.02 today. This is Deadwood 2.9.01 with bugfixes and documentation improvements. In more detail, here are the changes since 2.9.01:
  • Script to apply patches against one version of Deadwood to make the next Deadwood release made (based on similar MaraDNS script; this is something I have implemented now that the code is feature-complete and ready for general testing)
  • INSTALL.txt updated to not mention DwMain (Deadwood's older name; issue reported on mailing list)
  • DW_MAXIPS increased to 128 (issue reported on mailing list)
  • Spurious debug message removed
  • Documentation updates (root_servers more fully described in man page; more questions and answers added to FAQ; fixes things I saw myself and reported on mailing list)
  • Bug reporting policy update (you better have a stack trace or be able to reproduce a crash; otherwise I can’t use the bug report. No current issue; but I have had stuff like this with MaraDNS. Any joker can pretend Deadwood is crashing, but I won’t believe you without proof)
  • Issue getting “SERVER FAIL” when AAAA query points to non-existent AAAA fixed. (Reported on mailing list)
  • Issue when we get a “a.kabah.foo CNAME b.kabah.foo ; c.kabah.foo A 10.2.3.4” packet (where “b.kabah.foo” is a CNAME for “c.kabah.foo”) fixed. (Found this one during my own “dogfood” testing of Deadwood)
  • Deadwood for Windows now built using MinGW 3.4.2 instead of MinGW 3.1.0 (issue found by myself and discussed on mailing list)
It can be downloaded here:

http://maradns.org/deadwood/testing/

As an aside, now that I’m visibly actively working with users again so we can find and fix bugs together, I have been getting a lot more private email asking for MaraDNS support. I don’t mind this email (I’ve come to accept it’s a natural consequence of MaraDNS becoming popular), but you’re going to get the “pay me or take it to the list” form reply (I’ve come to accept people will occasionally get all worked up I don’t provide free support; I forward such lusers [1] on to the list, like I warn people I may do in my form reply, for our collective amusement).

I hope some of the people sending me this kind of email pay me for MaraDNS support; I can use the money. Or better yet, get me a real job with a living wage. Now that MaraDNS 2.0’s recursive resolver is feature-complete, I hope to have time to master OOP, Java, and whatever other buzzwords I need on my resume to get the job to support my beautiful wife.

[1] Someone who doesn’t read the “no free private email support” disclaimer at the bottom of the MaraDNS web page, as well as on the webpage with my email address, not to mention at the bottom most postings I make to the mailing list, and then flames me in response to my form reply asking for money [2] gets a LART in the form of me going public with their email. Especially since the form reply says, very clearly at the top, that I may forward their email to the MaraDNS mailing list.

[2] It doesn’t just ask for money. It also lets them know they can get free support by posting it to the MaraDNS list.

Wednesday, July 28, 2010

Deadwood snapshot update

Since Deadwood is in beta-testing, the changes at this point will by and large be bug fixes. That in mind, I am going to start announcing Deadwood snapshot updates on my blog again, since they are more interesting for end users than “I’ve started work on converting the code to handle NS referrals”, “I’m making more progress on converting the code to handle NS referrals”, “I’m making more progress on converting the code to handle NS referrals. No, it doesn’t work yet, but, really, I’m making progress”, “Yet more progress on converting the code to handle NS referrals”, etc.

Today’s snapshop fixes the bug reported in a mailing list posting. [1]

I have fixed the bug, but I’m not 100% happy with the way I’m fixing it, as described in this mailing list posting.

Anyway, people can look at both the patch (in the “update” directory) and the patched Deadwood here:

http://maradns.org/deadwood/snap/deadwood-H-20100728-1.tar.bz2

Update: I have updated this with a better patch that, instead of deciding all SOA records are always “in bailiwick”, has it so bailiwick tests are only done if the record is determined to be a NS referral. See here:

http://maradns.org/deadwood/snap/deadwood-H-20100728-2.tar.bz2

- Sam

[1] The guys at Marc.info need to fix things to recognize a name on the From: line is UTF-8 encoded when it says it’s UTF-8 encoded. “From: =?UTF-8?B?U2ViYXN0aWFuIE3DvGxsZXI=?=” is “Sebastian Müller”, not “Sebastian Müller”.

Friday, July 23, 2010

Upstream replies to Debian bugs

Since a number of MaraDNS users use the Debian bug tracking system to report MaraDNS bugs, I have just gone through a number of old Debian bugs. The ones with distribution-specific issues I have ignored, but here are my replies to issues I, as upstream, are responsible for:

Bug 477787: MaraDNS 2.0 will have full IPv6 support. I have just made a beta-test release of the relevant code (MaraDNS 2.0's up-and-coming recursor, Deadwood) and encourage people to test it and report bugs on the MaraDNS mailing list.

Bug 484466: If MaraDNS is run using the duende daemonizer, sending MaraDNS a HUP signal will stop and restart MaraDNS, reloading all configuration and zone files.

Bug 486497: It's a really bad idea to bind MaraDNS to 0.0.0.0, but if you insist on doing it, it can be done if csv2_synthip_list is set.

Bug 507591: This issue was never present in MaraDNS 1.2, and has been fixed in MaraDNS 1.3.07.10 and MaraDNS 1.4.03. If Debian versions of MaraDNS still have this bug, they need to incorporate my fix, or, better yet, upgrade to 1.3.07.10 or 1.4.03.

Bug 525188: Just this last day, I have released Deadwood 2.9.01, which is the daemon that will become MaraDNS 2.0's recursive resolver. This daemon fixes a number of long-standing issues MaraDNS 1.0's recursive resolver has, including CNAMEs pointing to AAAA records.

This particular issue is one that I will not fix in MaraDNS 1.x (IPv6 does not have wide adoption yet, and MaraDNS 2.0 should be out there by the time it does), but it has already been fixed for MaraDNS 2.0.

Bug 573970: There are no plans to add this to the authoritative MaraDNS code, but the up-and-coming MaraDNS 2.0 release will use a separate daemon for recursion called Deadwood (I just released the first beta-test version of this daemon this last day), which does support "includes" via Python-compatible execfile("filename") syntax.

All other bugs appear to be Debian-specific OS issues. The next time I look at Debian bugs will probably be in a year or two.

Thursday, July 22, 2010

Deadwood 2.9.01 released: Full recursion

I have just released Deadwood 2.9.01. This is the first release of the fully recursive Deadwood; Deadwood no longer needs an upstream server performing the “heavy lifting” of recursive DNS.

I have done a lot of “web surfing” testing with Deadwood; I have fixed enough bugs that Deadwood can be used for casual web surfing. Indeed, I am using Deadwood to post this blog right now and the issues I saw before (tagged.com, etc.) are no longer a problem.

This is a testing release. That now has a different meaning than my previous definition of a testing release. All of the features Deadwood 3.0 (MaraDNS 2.0) will have are already implemented. At this point, the program needs testing (expansion of the SQA regressions to handle recursion, etc.) and documentation (root_servers hasn’t been documented yet) updates.

It has been a long road to get here. I have wanted to rewrite MaraDNS’ recursive resolver since 2002; I started writing Deadwood in 2007 and it’s finally feature-complete here in 2010.

Deadwood 2.9.01 can be downloaded as source code and Windows binaries here:

maradns.org/deadwood/testing/

I encourage people to test Deadwood and make bug reports. Some things to keep in mind:
  • Valgrind-reported memory leaks can always be reported. Valgrind-reported errors are only valid if Deadwood is compiled with -DVALGRIND_NOERRORS
  • The only officially supported OSes are Windows XP and CentOS 5. OS-specific issues such as startup, daemonizing, sysloggin, and /etc/resolv.conf setup are only supported on these two OSes.
  • Bugs need to be reported to the MaraDNS list, not to my email account nor as blog comments. I hope to have time to set up a web forum for MaraDNS/Deadwood support for people not comfortable with mailing lists, but no promises.

Firefox does pretty agressive DNS pre-fetching

As I am performing some real-world testing with the (hopefully) soon-to-be-released Deadwood 2.9.01, I discovered something interesting that Firefox does.

The copy of Firefox 3.6.4 I have [1] in CentOS 5 looks at all of the links on a given page I am reading, and uses DNS to look up the hostnames of all of the links. This way, if I click on a given link, I don’t have to wait for the DNS lookup to be performed. I can see why Firefox implemented this.

Anyway, I usually don‘t announce snapshots here, but I am very pleased that Deadwood is finally, after nearly three years, a fully recursive DNS server. Snapshots are here:

http://www.maradns.org/deadwood/

Look in the snap directory for the latest snapshot.

Todo before releasing Deadwood 2.9.01:
  • Make a quick Deadwood FAQ
  • The usual Deadwood SQA regressions I do before any release
(Footnote follows)

[1] Yes, I know, the current version is Firefox 3.6.7, but I’m using CentOS 5, whose most current version of Firefox is 3.6.4. Out-of-date versions of programs is a very common problem in Linux, since the distributor of a given program has to approve and then send a program downstream before the users of the distribution get the update. It’s worse with CentOS, where a given update has to get approved by RedHat, then, in turn, processed by CentOS before it gets here.

One issue I have had a lot with MaraDNS is that people sometimes email me or post to the mailing list bug reports for issues I have already fixed, but the user in question is using the version of MaraDNS that comes with Debian or whatever, which hasn’t been updated.

Monday, July 19, 2010

Some thoughts on Rijndael

When I heard that the Rijndael block cipher was selected as the algorithm for the Advanced encryption standard, I was so excited I sent one of the creators of Rijndael a very excited email.

OK, I should probably explain this in more layman’s terms. AES—the advanced encryption standard—is the standard cipher people use when people get a clue and realize they need to use strong cryptography and not ad-hoc schemes to protect data. WEP used RC4 instead of AES, and was soon broken; this has been replaced by WPA2, which does use AES. Indeed, the wireless packets being sent to publish this blog are encrypted with AES. The blu ray discs sitting on the player in the other room are encrypted with AES (this is another form of cluelessness, since cryptography only makes it inconvenient, not computationally infeasible, for the intended user of a piece of media to copy said media. The way you stop piracy is by teaching freetards integrity and morals, not with cryptographic ideas that will never work). AES is the most secure way to make web sites encrypted with https.

I liked Rijndael more than the other contestants because it was a good deal more flexible. Rijndael was designed with something called the wide trail strategy that allows components to be readily replaced or modified. For example, it is possible to change its block size; all other AES candidates (with the exception of HPC and possibly RC6) had a fixed block size of 128 bits; Rijndael can have a block size of 128, 160, 192, 224, or 256 bits. Or, if desired, it is relatively straightforward to make an unofficial Rijndael variant with a 32, 64, or 96 bit block size.

It is also possible to change its S-box if one feels Rijndael is somehow too algebraic.

Another thing that is possible to do is to make a Rijndael variant using 64-bit instead of 32-bit integers. If this is done, the variant’s “natural” block size is 512 bits; this can be adapted to have a block size of any multiple of 64 bits from 64 to 1024 bits (64, 128, 192, 256, 320, 384, 448, 512, 576, 640, 704, 768, 832, 896, 960, or 1024 bits). The dirty work of coming up with magic constants for a 64-bit Rijndael variant has already been done with the Whirlpool hash; the only constants we need to pull out of the air are the “shift row” constants.

The Rijndael/Whirlpool variant with a 1024-bit block size has a large enough block to be used in a “sponge function” mode of operation. A cryptographic sponge allows any significantly large random-looking permutation to be used as the code of a hash function or stream cipher (it’s a hash function with an arbitrarily long output). We can use a 1024-bit block size cipher as a sponge to generate a 256-bit hash, or by having things be twice as slow, a 384-bit hash (For people familiar with sponge constructions: The 256-bit hash is done with a “capacity” and “rate” of 512 bits; the 384-bit hash is done with a “capacity” of 768 bits and a “rate” of 256 bits).

Another idea that has been implemented is both 64-bit and 128-bit Rijndael variants where the encryption and decryption operations are identical—useful for minimizing code size in implementations where encryption and decryption are both supported. We give up block size flexibility when we do this (the 32-bit version needs a block size of 128 bits, but the 64-bit version can have a block size of either 64 bits or 512 bits). This has been implemented with Anubis (32-bit words, 128-bit block size) and Khazad (64-bit words, 64-bit block size; can be modified to be a 512-bit block). In addition, there is a proposed 128-bit word size primitive (PDF file) that could be used to make either a 128-bit or 2048-bit Rijndael variant using the same operations for encryption and decryption.

Rijndael has a couple of issues. One is that the key schedule is not as strong as it could be; this has resulted in their being an academic weakness called a “related key attack”. This does not result in any practical security problems; a related key attack is one of the hardest to utilize in the real world (cipher keys are usually hashed using cryptographic hashes). Indeed, the website describing this attack on Rijndael uses, of all things, Rijndael to encrypt traffic.

The other issue is that in an optimized implementation, Rijndael uses a lot of table lookups, which make it vulnerable to an attack called a “cache timing attack”. A cache timing attack could be used by an adversary with limited access to a system running Rijndael encryptions to determine a Rijndael key used elsewhere on the system. The attack is right now a purely academic attack; no one has seen it used by a real-world adversary, and some processors (such as the ARM) series can thwart it with cache lock-down. With the AES instruction set now a reality, these attacks will soon be a non-issue.

So, yes, Rijndael is a very nice, very flexible cryptographic primitive.

Saturday, July 17, 2010

Deadwood 2.6.05 released: Feature complete

Deadwood is now feature complete.

However, it does not pass the “browsing” test. In other words, when I start to surf the net with Deadwood, my web surfing experience is hindered because of issues in the code. I have found the following issues to resolve:
  • CNAMEs pointing to nothing broken (e.g. AAAA for mail.google.com).
  • Poor handling of unresponsive name servers (samiam.org, kintera.com)
  • Use CryptGenRandom() as entropy source in Windows.
I hope to get these issues resolved. In the meantime, I have released Deadwood 2.6.05 today, which is a working recursive nameserver. It is in the testing/ directory here:

maradns.org/deadwood

Friday, July 16, 2010

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.