From e0a883e3d70d6c9dc5e2d4a984bd75b1d9390be3 Mon Sep 17 00:00:00 2001 From: Ian Jackson Date: Thu, 21 Jul 2011 19:41:29 +0100 Subject: [PATCH] WIP dns packet en/decoding --- dns-transp-common.c | 193 ++++++++++++++++++++++++++++++++++++++++++++ dns-transp-common.h | 31 +++++++ dns-transp-server.c | 17 +++- 3 files changed, 237 insertions(+), 4 deletions(-) create mode 100644 dns-transp-common.c create mode 100644 dns-transp-common.h diff --git a/dns-transp-common.c b/dns-transp-common.c new file mode 100644 index 0000000..59f739a --- /dev/null +++ b/dns-transp-common.c @@ -0,0 +1,193 @@ + +static const char out_table[32]="0123456789abcdefghijklmnopqrstuv"; + +static inline int enoughinput(struct dnsbitenc *be) { + return be->npending >= 5; +} +static inline void startlabel(struct dnsbitenc *be) { + be->labremain=63; +} +static inline void outputchar(struct dnsbitenc *be) { + /* there must be enough input and enough space */ + if (!be->labremain) { + *--(be->out) = 63; + startlabel(be); + } + *--(be->out) = out_table[be->pending & 0x1f]; + be->pending >>= 5; + be->npending -= 5; +} + +void dnsbitenc_start(struct dnsbitenc *be, uint8_t *buf, int buflen) { + assert(buflen>0); + be->pending=0; + be->npending=0; + be->bufstop=buf+1; + be->out=buf+buflen; + startlabel(be); +} + +void dnsbitenc_addbits(struct dnsbitenc *be, uint32_t val, int nbits) { + assert(nbits<=28); /* otherwise pending might overflow */ + assert(!(val & ~(((uint32_t)1 << nbits)-1))); + be->pending |= val << be->npending; + be->npending += nbits; + while (enoughinput(be)) { + assert(be->out > be->bufstop); + outputchar(be); + } +} + +void dnsbitenc_addu32(struct dnsbitenc *be, uint32_t val) { + dnsbitenc_addbits(be, val & 0xffff, 16); + dnsbitenc_addbits(be, val >> 16, 16); +} + +int dnsbitenc_restbytes(struct dnsbitenc *be, uint8_t *bytes, int qty) { + for (;;) { + if (buf==bufstop) { + return qty + ((be->npending + 7) / 8); + } + if (be->npending<5) { + if (qty) { + be->pending |= (*bytes++) << be->npending; + be->npending += 8; + } else if (be->npending <= 0) { + return 0; + } + } + outputchar(be); + } +} + +uint8_t *dnsbitenc_getresult(struct dnsbitenc *be) { + *--(be->out) = 63 - be->labremain; /* finish the last label */ + return be->out; +} + + + + +#define MAX_DATA_LABELS + +struct labelinpacket { + const uint8_t *bytes; + int len; +}; + +struct dnsbitdec { + /* private for dnsbitdec_... functions; do not access direcctly */ + const databuf[MAX_DOMAIN_BYTES]; + const uint8_t *in; +}; + +static void setafter(const uint8_t *domain, const uint8_t **domain_end_r) { + if (domain_end_r && !*domain_end_r) + *domain_end_r=domain; +} + +int dnsdomaindec_start(struct dnsbitdec *bd, const uint8_t *packet, + const uint8_t *endpacket, const uint8_t *domain, + int mydompathlen, const char *mydompath[], + const uint8_t **domain_end_r) { + int maxlabels=mydompath+MAX_DATA_LABELS; + const strut labelinpacket labels[maxlabels]; + int nlabels=0, totallen=0; + + *domain_end_r=0; + for (;;) { + if (domain==endpacket) + return FORMERR; + unsigned b=*domain++; + if (!b) { + totallen++; + setafter(domain,domain_end_r); + break; + } + if ((b & 0xc0) == 0xc0) { + if (domain==endpacket) + return FORMERR; + unsigned b2=*domain++; + setafter(domain,domain_end_r); + unsigned off= ((b & 0x3f)<<8) | b2; + if (off >= endpacket - packet) + return False; + domain=packet+off; + b=*domain++; + if (!b) return FORMERR + /* now fall through to code expecting a literal */ + } + if ((b & 0xc0) != 0x00) + return FORMERR; + if (nlabels>=maxlabels) + return NOTAUTH; + totallen+=b+1; + if (totallen >= MAX_DOMAIN_BYTES) /* we still need a nul label */ + return FORMERR; + labels[nlabels].bytes=domain; + labels[nlabels].len=b; + nlabels++; + domain += b; + } + if (nlabels <= mydompathlen) + return NOTAUTH; + for (i=0; ilen != l || memcmp(got->bytes,mydompath[i])) + return NOTAUTH; + } + /* OK, it's our domain and it has some data and a good + * number of labels. Wow. */ + uint8_t *copyto=&bd->databuf; + for (i=0; idatabuf+sizeof(bd->databuf)); + bd->in=copyto; + return 0; +} + +static uint8_t in_table[256]; + +static void dnsdomaindec_globalinit(void) { + memset(in_table,0xff,sizeof(in_table)); + for (i=0; i<32; i++) { + in_table[out_table[i]]=i; + in_table[toupper((unsigned char)out_table[i])]=i; + } +} + +static void inputchar(struct dnsbitdec *bd) { + /* must be enough input and enough space in pending */ + int ch=*--(bd->in); + bd->pending <<= 8; + bd->pending |= ch; /* already decoded */ +} +uint32_t dnsdomaindec_getbits(struct dnsbitdec *bd, int nbits) +{ + /* must be enough */ + assert(nbits<=28); + while (bd->pending < nbits) + inputchar(); + int newnpending = bd->pending - nbits; + uint32_t rv = bd->pending >> newnpending; + bd->pending &= ((uint32_t)1 << newnpending)-1; + bd->npending = newnpending; +} +uint32_t dnsdomaindec_getu32(struct dnsbitdec *bd) +{ + uint32_t lsw=dnsdomaindec_getbits(bd,16); + uint32_t msw=dnsdomaindec_getbits(bd,16); + return (msw << 16) | lsw; +} +int dnsbitdec_restbytes(struct dnsbitdec *bd, uint8_t outbuf[MAX_DOMAIN_BYTES]) +{ + for (;;) { + diff --git a/dns-transp-common.h b/dns-transp-common.h new file mode 100644 index 0000000..a715427 --- /dev/null +++ b/dns-transp-common.h @@ -0,0 +1,31 @@ + +struct dnsbitenc { + /* private for dnsbitenc_... functions; do not access direcctly */ + uint32_t pending; + int npending; /* never more than 4 unless we're in the middle */ + uint8_t *out, *bufstop; /* counts backwards */ + int labremain; +}; + +/* + * The only legal calling sequence is this: + * start + * (addbits | addu32)* + * restbytes + * getresult + */ + +void dnsbitenc_start(struct dnsbitenc *be, uint8_t *buf, int buflen); + +void dnsbitenc_addbits(struct dnsbitenc *be, uint32_t val, int nbits); + /* adds the bottom nbits bits of val; must be enough space; nbits<=28 */ +void dnsbitenc_addu32(struct dnsbitenc *be, uint32_t val); + /* must be enough space */ + +int dnsbitenc_restbytes(struct dnsbitenc *be, uint8_t *bytes, int qty); + /* returns number of bytes which did not fit */ + +uint8_t *dnsbitenc_getresult(struct dnsbitenc *be); + /* returns pointer into caller-supplied buffer; we have used + * bytes from the result to the end (so the caller needs to remember + * the buffer len to know what the encoded length is */ diff --git a/dns-transp-server.c b/dns-transp-server.c index 154c907..fd52b8a 100644 --- a/dns-transp-server.c +++ b/dns-transp-server.c @@ -10,25 +10,25 @@ /* * Query format: create assoc: - * 1 bit set this a create assoc query * 32 bits clientnonce + * 1 bit set this is a create assoc query * 10 bits offset of this data fragment in packet * 1 bit is this the last fragment ? * remainder data packet fragment * data packet sequence number is always implicitly zero * * Query format: submit: - * 1 bit clear this is not a create assoc query * 32 bits associd + * 1 bit clear this is not a create assoc query * 16 bits data packet sequence number * 10 bits offset of this data fragment in packet * 1 bit is this the last fragment * remainder data packet fragment * * Query format: fetch: - * 1 bit clear this is not a create assoc query * 32 bits associd - * 16 bits client query distinguishper (for defeating dns cache) + * 1 bit clear this is not a create assoc query + * 16 bits client query distinguisher (for defeating dns cache) * * Response format: * [ 32 bits associd - only for responses to create assoc ] @@ -42,6 +42,15 @@ * Query bitstring, from above, is encoded as follows: * 1. * . append our server's domain + * Max DNS domain is 255 bytes. + * Max UDP packet is 512 bytes. + * If our domain is .s.chiark.net. (12 bytes) + * then we have 241 bytes of payload left. + * We need at least 4 subdomains to avoid blowing the 63-byte limit + * So that means we need 3 more dots, so 238 chars. + * At 5 bits per char that's 1190 bits. Minus our submit + * header (1+32+16+10+1 = 60 bits) that's 1130 bits or 141.25 bytes. + */ struct expires { struct expires *next; -- 2.30.2