rebound case randomization

[Ted Unangst]

16 bit IDs don't offer much security. This is well known. A trick to encode
more bits into the query is to vary the case of the query name. It's case
insensitive, but all known servers echo it back exactly, case preserving. Thus
we can twiddle the query on the way out and verify we get exactly the right
reply.

In theory a dns packet can contain more than one query, but in practice it's
only one, so this also adds a few checks for that to avoid some more
complicated parsing.

Index: rebound.c
===================================================================
RCS file: /cvs/src/usr.sbin/rebound/rebound.c,v
retrieving revision 1.74
diff -u -p -r1.74 rebound.c
--- rebound.c 8 Oct 2016 06:33:59 -0000 1.74
+++ rebound.c 14 Oct 2016 02:40:15 -0000
@@ -32,6 +32,7 @@
#include <stdio.h>
#include <limits.h>
#include <string.h>
+#include <ctype.h>
#include <err.h>
#include <unistd.h>
#include <fcntl.h>
@@ -63,8 +64,10 @@ struct dnspacket {
uint16_t ancount;
uint16_t nscount;
uint16_t arcount;
+ char qname[];
/* ... */
};
+#define NAMELEN 256

/*
* requests will point to cache entries until a response is received.
@@ -102,6 +105,8 @@ struct request {
uint16_t clientid;
uint16_t reqid;
struct dnscache *cacheent;
+ char origname[NAMELEN];
+ char newname[NAMELEN];
};
static TAILQ_HEAD(, request) reqfifo;

@@ -157,12 +162,46 @@ cachecmp(struct dnscache *c1, struct dns
}
RB_GENERATE_STATIC(cachetree, dnscache, cachenode, cachecmp)

+static void
+lowercase(unsigned char *s)
+{
+ while (*s) {
+ *s = tolower(*s);
+ s++;
+ }
+}
+
+static void
+randomcase(unsigned char *s)
+{
+ unsigned char bits[NAMELEN / 8], *b;
+ u_int i = 0;
+
+ arc4random_buf(bits, strlen(s));
+ b = bits;
+ while (*s) {
+ *s = (*b & (1 << i)) ? toupper(*s) : tolower(*s);
+ s++;
+ b++;
+ i++;
+ if (i == 8)
+ i = 0;
+ }
+}
+
static struct dnscache *
cachelookup(struct dnspacket *dnsreq, size_t reqlen)
{
struct dnscache *hit, key;
+ unsigned char origname[NAMELEN];
uint16_t origid;

+ if (ntohs(dnsreq->qdcount) != 1)
+ return NULL;
+
+ strlcpy(origname, dnsreq->qname, sizeof(origname));
+ lowercase(dnsreq->qname);
+
origid = dnsreq->id;
dnsreq->id = 0;

@@ -172,6 +211,7 @@ cachelookup(struct dnspacket *dnsreq, si
if (hit)
cachehits += 1;

+ strlcpy(dnsreq->qname, origname, sizeof(origname));
dnsreq->id = origid;
return hit;
}
@@ -241,6 +281,7 @@ newrequest(int ud, struct sockaddr *remo
conntotal += 1;
if ((hit = cachelookup(dnsreq, r))) {
hit->resp->id = dnsreq->id;
+ strlcpy(hit->resp->qname, dnsreq->qname, strlen(hit->resp->qname) + 1);
sendto(ud, hit->resp, hit->resplen, 0, &from.a, fromlen);
return NULL;
}
@@ -260,21 +301,27 @@ newrequest(int ud, struct sockaddr *remo
req->clientid = dnsreq->id;
req->reqid = randomid();
dnsreq->id = req->reqid;
+ if (ntohs(dnsreq->qdcount) == 1) {
+ strlcpy(req->origname, dnsreq->qname, sizeof(req->origname));
+ randomcase(dnsreq->qname);
+ strlcpy(req->newname, dnsreq->qname, sizeof(req->newname));
+
+ hit = calloc(1, sizeof(*hit));
+ if (hit) {
+ hit->req = malloc(r);
+ if (hit->req) {
+ memcpy(hit->req, dnsreq, r);
+ hit->reqlen = r;
+ hit->req->id = 0;
+ lowercase(hit->req->qname);
+ } else {
+ free(hit);
+ hit = NULL;

- hit = calloc(1, sizeof(*hit));
- if (hit) {
- hit->req = malloc(r);
- if (hit->req) {
- memcpy(hit->req, dnsreq, r);
- hit->reqlen = r;
- hit->req->id = 0;
- } else {
- free(hit);
- hit = NULL;
-
+ }
}
+ req->cacheent = hit;
}
- req->cacheent = hit;

req->s = socket(remoteaddr->sa_family, SOCK_DGRAM, 0);
if (req->s == -1)
@@ -359,6 +406,11 @@ sendreply(int ud, struct request *req)
if (resp->id != req->reqid)
return;
resp->id = req->clientid;
+ if (ntohs(resp->qdcount) == 1) {
+ if (strcmp(resp->qname, req->newname) != 0)
+ return;
+ strlcpy(resp->qname, req->origname, strlen(resp->qname) + 1);
+ }
sendto(ud, buf, r, 0, &req->from.a, req->fromlen);
if ((ent = req->cacheent)) {
/*

[Ted Unangst]

Ted Unangst wrote:
> 16 bit IDs don't offer much security. This is well known. A trick to encode
> more bits into the query is to vary the case of the query name. It's case
> insensitive, but all known servers echo it back exactly, case preserving. Thus
> we can twiddle the query on the way out and verify we get exactly the right
> reply.
>
> In theory a dns packet can contain more than one query, but in practice it's
> only one, so this also adds a few checks for that to avoid some more
> complicated parsing.

Matthew Martin pointed out a bug in the randomizer. Only increment the byte
pointer when we've used up all the bits. Tried to be clever, and it bit me.
(hahahahaha). Math should be better now.

Index: rebound.c
===================================================================
RCS file: /cvs/src/usr.sbin/rebound/rebound.c,v
retrieving revision 1.74
diff -u -p -r1.74 rebound.c
--- rebound.c 8 Oct 2016 06:33:59 -0000 1.74

+++ rebound.c 14 Oct 2016 04:47:10 -0000

@@ -32,6 +32,7 @@
#include <stdio.h>
#include <limits.h>
#include <string.h>
+#include <ctype.h>
#include <err.h>
#include <unistd.h>
#include <fcntl.h>
@@ -63,8 +64,10 @@ struct dnspacket {
uint16_t ancount;
uint16_t nscount;
uint16_t arcount;
+ char qname[];
/* ... */
};
+#define NAMELEN 256

/*
* requests will point to cache entries until a response is received.
@@ -102,6 +105,8 @@ struct request {
uint16_t clientid;
uint16_t reqid;
struct dnscache *cacheent;
+ char origname[NAMELEN];
+ char newname[NAMELEN];
};
static TAILQ_HEAD(, request) reqfifo;

@@ -157,12 +162,47 @@ cachecmp(struct dnscache *c1, struct dns

}
RB_GENERATE_STATIC(cachetree, dnscache, cachenode, cachecmp)

+static void
+lowercase(unsigned char *s)
+{
+ while (*s) {
+ *s = tolower(*s);
+ s++;
+ }
+}
+
+static void
+randomcase(unsigned char *s)
+{
+ unsigned char bits[NAMELEN / 8], *b;
+ u_int i = 0;
+

+ arc4random_buf(bits, (strlen(s) + 7) / 8);

+ b = bits;
+ while (*s) {
+ *s = (*b & (1 << i)) ? toupper(*s) : tolower(*s);
+ s++;

+ i++;
+ if (i == 8) {

+ b++;

+ i = 0;
+ }
+ }
+}
+
static struct dnscache *
cachelookup(struct dnspacket *dnsreq, size_t reqlen)
{
struct dnscache *hit, key;
+ unsigned char origname[NAMELEN];
uint16_t origid;

+ if (ntohs(dnsreq->qdcount) != 1)
+ return NULL;
+
+ strlcpy(origname, dnsreq->qname, sizeof(origname));
+ lowercase(dnsreq->qname);
+
origid = dnsreq->id;
dnsreq->id = 0;

@@ -172,6 +212,7 @@ cachelookup(struct dnspacket *dnsreq, si

if (hit)
cachehits += 1;

+ strlcpy(dnsreq->qname, origname, sizeof(origname));
dnsreq->id = origid;
return hit;
}

@@ -241,6 +282,7 @@ newrequest(int ud, struct sockaddr *remo

conntotal += 1;
if ((hit = cachelookup(dnsreq, r))) {
hit->resp->id = dnsreq->id;
+ strlcpy(hit->resp->qname, dnsreq->qname, strlen(hit->resp->qname) + 1);
sendto(ud, hit->resp, hit->resplen, 0, &from.a, fromlen);
return NULL;
}

@@ -260,21 +302,27 @@ newrequest(int ud, struct sockaddr *remo

@@ -359,6 +407,11 @@ sendreply(int ud, struct request *req)

[Stuart Henderson]

On 2016/10/13 22:55, Ted Unangst wrote:
> 16 bit IDs don't offer much security. This is well known. A trick to encode
> more bits into the query is to vary the case of the query name. It's case
> insensitive, but all known servers echo it back exactly, case preserving.

Unfortunately not. Many do but there are some cases, especially with
things like global-loadbalancer DNS servers, and firewalls doing DNS
content inspection where there are problems (either for all records, or
some records especially in-addr.arpa).

Unbound had to add fallbacks for this (see the 'caps_fallback' bits in
iterator/iterator.c). Some strategies for this are discussed in
draft-vixie-dnsext-dns0x20-00.