From 2faba57c85ea9b0f38558b4f55777727f21c5964 Mon Sep 17 00:00:00 2001 From: Daniel Stenberg Date: Wed, 30 May 2007 21:11:10 +0000 Subject: Shmulik Regev brought cryptographically secure transaction IDs --- ares/CHANGES | 26 +++++++++++++++++ ares/ares_init.c | 83 +++++++++++++++++++++++++++++++++++++++++++++-------- ares/ares_private.h | 16 +++++++++++ ares/ares_query.c | 61 ++++++++++++++++++++++++++++++++++++++- 4 files changed, 173 insertions(+), 13 deletions(-) diff --git a/ares/CHANGES b/ares/CHANGES index 9f0a04422..e3b5367d9 100644 --- a/ares/CHANGES +++ b/ares/CHANGES @@ -2,6 +2,32 @@ * May 30 2007 +- Shmulik Regev brought cryptographically secure transaction IDs: + + The c-ares library implementation uses a DNS "Transaction ID" field that is + seeded with a pseudo random number (based on gettimeofday) which is + incremented (++) between consecutive calls and is therefore rather + predictable. In general, predictability of DNS Transaction ID is a well + known security problem (e.g. + http://bak.spc.org/dms/archive/dns_id_attack.txt) and makes a c-ares based + implementation vulnerable to DNS poisoning. Credit goes to Amit Klein + (Trusteer) for identifying this problem. + + The patch I wrote changes the implementation to use a more secure way of + generating unique IDs. It starts by obtaining a key with reasonable entropy + which is used with an RC4 stream to generate the cryptographically secure + transaction IDs. + + Note that the key generation code (in ares_init:randomize_key) has two + versions, the Windows specific one uses a cryptographically safe function + provided (but undocumented :) by the operating system (described at + http://blogs.msdn.com/michael_howard/archive/2005/01/14/353379.aspx). The + default implementation is a bit naive and uses the standard 'rand' + function. Surely a better way to generate random keys exists for other + platforms. + + The patch can be tested by using the adig utility and using the '-s' option. + - Brad House added ares_save_options() and ares_destroy_options() that can be used to keep options for later re-usal when ares_init_options() is used. diff --git a/ares/ares_init.c b/ares/ares_init.c index d384f9401..e86d80ca4 100644 --- a/ares/ares_init.c +++ b/ares/ares_init.c @@ -72,6 +72,8 @@ static int config_nameserver(struct server_state **servers, int *nservers, static int set_search(ares_channel channel, const char *str); static int set_options(ares_channel channel, const char *str); static const char *try_option(const char *p, const char *q, const char *opt); +static void init_id_key(rc4_key* key,int key_data_len); + #ifndef WIN32 static int sortlist_alloc(struct apattern **sortlist, int *nsort, struct apattern *pat); static int ip_addr(const char *s, int len, struct in_addr *addr); @@ -85,10 +87,10 @@ static char *try_config(char *s, const char *opt); #endif #define ARES_CONFIG_CHECK(x) (x->lookups && x->nsort > -1 && \ - x->nservers > -1 && \ + x->nservers > -1 && \ x->ndomains > -1 && \ - x->ndots > -1 && x->timeout > -1 && \ - x->tries > -1) + x->ndots > -1 && x->timeout > -1 && \ + x->tries > -1) int ares_init(ares_channel *channelptr) { @@ -102,7 +104,6 @@ int ares_init_options(ares_channel *channelptr, struct ares_options *options, int i; int status = ARES_SUCCESS; struct server_state *server; - struct timeval tv; #ifdef CURLDEBUG const char *env = getenv("CARES_MEMDEBUG"); @@ -203,15 +204,9 @@ int ares_init_options(ares_channel *channelptr, struct ares_options *options, server->qtail = NULL; } - /* Choose a somewhat random query ID. The main point is to avoid - * collisions with stale queries. An attacker trying to spoof a DNS - * answer also has to guess the query ID, but it's only a 16-bit - * field, so there's not much to be done about that. - */ - gettimeofday(&tv, NULL); - channel->next_id = (unsigned short) - ((tv.tv_sec ^ tv.tv_usec ^ getpid()) & 0xffff); + init_id_key(&channel->id_key, ARES_ID_KEY_LEN); + channel->next_id = ares__generate_new_id(&channel->id_key); channel->queries = NULL; *channelptr = channel; @@ -1271,3 +1266,67 @@ static void natural_mask(struct apattern *pat) pat->mask.addr.addr4.s_addr = htonl(IN_CLASSC_NET); } #endif +/* initialize an rc4 key. If possible a cryptographically secure random key + is generated using a suitable function (for example win32's RtlGenRandom as + described in + http://blogs.msdn.com/michael_howard/archive/2005/01/14/353379.aspx + otherwise the code defaults to cross-platform albeit less secure mechanism + using rand +*/ +static void randomize_key(unsigned char* key,int key_data_len) +{ + int randomized = 0; +#ifdef WIN32 + HMODULE lib=LoadLibrary("ADVAPI32.DLL"); + if (lib) { + BOOLEAN (APIENTRY *pfn)(void*, ULONG) = + (BOOLEAN (APIENTRY *)(void*,ULONG))GetProcAddress(lib,"SystemFunction036"); + if (pfn && pfn(key,key_data_len) ) + randomized = 1; + + FreeLibrary(lib); + } +#endif + + if ( !randomized ) { + int counter; + for (counter=0;counterstate,key_data_len); + state = &key->state[0]; + for(counter = 0; counter < 256; counter++) + state[counter] = counter; + key->x = 0; + key->y = 0; + index1 = 0; + index2 = 0; + for(counter = 0; counter < 256; counter++) + { + index2 = (key_data_ptr[index1] + state[counter] + + index2) % 256; + ARES_SWAP_BYTE(&state[counter], &state[index2]); + + index1 = (index1 + 1) % key_data_len; + } + free(key_data_ptr); + +} + +short ares__generate_new_id(rc4_key* key) +{ + short r; + ares__rc4(key, (unsigned char *)&r, sizeof(r)); + return r; +} diff --git a/ares/ares_private.h b/ares/ares_private.h index 7fa316fec..f0314515c 100644 --- a/ares/ares_private.h +++ b/ares/ares_private.h @@ -80,6 +80,8 @@ #endif +#define ARES_ID_KEY_LEN 31 + #include "ares_ipv6.h" struct send_request { @@ -156,6 +158,13 @@ struct apattern { unsigned short type; }; +typedef struct rc4_key +{ + unsigned char state[256]; + unsigned char x; + unsigned char y; +} rc4_key; + struct ares_channeldata { /* Configuration data */ int flags; @@ -176,6 +185,8 @@ struct ares_channeldata { /* ID to use for next query */ unsigned short next_id; + /* key to use when generating new ids */ + rc4_key id_key; /* Active queries */ struct query *queries; @@ -184,10 +195,15 @@ struct ares_channeldata { void *sock_state_cb_data; }; +void ares__rc4(rc4_key* key,unsigned char *buffer_ptr, int buffer_len); void ares__send_query(ares_channel channel, struct query *query, time_t now); void ares__close_sockets(ares_channel channel, struct server_state *server); int ares__get_hostent(FILE *fp, int family, struct hostent **host); int ares__read_line(FILE *fp, char **buf, int *bufsize); +short ares__generate_new_id(rc4_key* key); + +#define ARES_SWAP_BYTE(a,b) \ + { unsigned char swapByte = *(a); *(a) = *(b); *(b) = swapByte; } #define SOCK_STATE_CALLBACK(c, s, r, w) \ do { \ diff --git a/ares/ares_query.c b/ares/ares_query.c index 742e87310..4ca4cf978 100644 --- a/ares/ares_query.c +++ b/ares/ares_query.c @@ -39,6 +39,64 @@ struct qquery { static void qcallback(void *arg, int status, unsigned char *abuf, int alen); +void ares__rc4(rc4_key* key, unsigned char *buffer_ptr, int buffer_len) +{ + unsigned char x; + unsigned char y; + unsigned char* state; + unsigned char xorIndex; + short counter; + + x = key->x; + y = key->y; + + state = &key->state[0]; + for(counter = 0; counter < buffer_len; counter ++) + { + x = (x + 1) % 256; + y = (state[x] + y) % 256; + ARES_SWAP_BYTE(&state[x], &state[y]); + + xorIndex = (state[x] + state[y]) % 256; + + buffer_ptr[counter] ^= state[xorIndex]; + } + key->x = x; + key->y = y; +} + +static struct query* find_query_by_id(ares_channel channel, int id) +{ + int qid; + struct query* q; + DNS_HEADER_SET_QID(((unsigned char*)&qid), id); + + /* Find the query corresponding to this packet. */ + for (q = channel->queries; q; q = q->next) + { + if (q->qid == qid) + return q; + } + return NULL; +} + + +/* a unique query id is generated using an rc4 key. Since the id may already + be used by a running query (as infrequent as it may be), a lookup is + performed per id generation. In practice this search should happen only + once per newly generated id +*/ +static int generate_unique_id(ares_channel channel) +{ + int id; + + do { + id = ares__generate_new_id(&channel->id_key); + } while (find_query_by_id(channel,id)); + + return id; +} + void ares_query(ares_channel channel, const char *name, int dnsclass, int type, ares_callback callback, void *arg) { @@ -50,7 +108,8 @@ void ares_query(ares_channel channel, const char *name, int dnsclass, rd = !(channel->flags & ARES_FLAG_NORECURSE); status = ares_mkquery(name, dnsclass, type, channel->next_id, rd, &qbuf, &qlen); - channel->next_id++; + channel->next_id = generate_unique_id(channel); + if (status != ARES_SUCCESS) { callback(arg, status, NULL, 0); -- cgit v1.2.3