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.

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

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.

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.

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)

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

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.