Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/netbsd-3-0]: src/dist/bind Pull up following revision(s) (requested by a...
details: https://anonhg.NetBSD.org/src/rev/0d66b36c8ae8
branches: netbsd-3-0
changeset: 579435:0d66b36c8ae8
user: ghen <ghen%NetBSD.org@localhost>
date: Tue Aug 14 10:34:16 2007 +0000
description:
Pull up following revision(s) (requested by adrianp in ticket #1829):
dist/bind/bin/named/client.c: revision 1.1.1.6 via patch
dist/bind/lib/dns/dispatch.c: revision 1.1.1.7 via patch
dist/bind/lib/dns/include/dns/dispatch.h: revision 1.1.1.5 via patch
Fix for a security issue in BIND 9.3.x (CVE-2007-2926):
Query id generation was cryptographically weak.
diffstat:
dist/bind/bin/named/client.c | 10 +-
dist/bind/lib/dns/dispatch.c | 500 +++++++++++++++++++++++++++---
dist/bind/lib/dns/include/dns/dispatch.h | 9 +-
3 files changed, 466 insertions(+), 53 deletions(-)
diffs (truncated from 677 to 300 lines):
diff -r 11100f9c209b -r 0d66b36c8ae8 dist/bind/bin/named/client.c
--- a/dist/bind/bin/named/client.c Mon Aug 06 11:43:01 2007 +0000
+++ b/dist/bind/bin/named/client.c Tue Aug 14 10:34:16 2007 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: client.c,v 1.1.1.2.4.1 2007/02/10 19:20:36 tron Exp $ */
+/* $NetBSD: client.c,v 1.1.1.2.4.2 2007/08/14 10:34:16 ghen Exp $ */
/*
* Copyright (C) 2004, 2005 Internet Systems Consortium, Inc. ("ISC")
@@ -1274,6 +1274,14 @@
}
/*
+ * Hash the incoming request here as it is after
+ * dns_dispatch_importrecv().
+ */
+ dns_dispatch_hash(&client->now, sizeof(client->now));
+ dns_dispatch_hash(isc_buffer_base(buffer),
+ isc_buffer_usedlength(buffer));
+
+ /*
* It's a request. Parse it.
*/
result = dns_message_parse(client->message, buffer, 0);
diff -r 11100f9c209b -r 0d66b36c8ae8 dist/bind/lib/dns/dispatch.c
--- a/dist/bind/lib/dns/dispatch.c Mon Aug 06 11:43:01 2007 +0000
+++ b/dist/bind/lib/dns/dispatch.c Tue Aug 14 10:34:16 2007 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: dispatch.c,v 1.1.1.2.4.1 2007/02/10 19:20:53 tron Exp $ */
+/* $NetBSD: dispatch.c,v 1.1.1.2.4.2 2007/08/14 10:34:16 ghen Exp $ */
/*
* Copyright (C) 2004 Internet Systems Consortium, Inc. ("ISC")
@@ -22,14 +22,16 @@
#include <config.h>
#include <stdlib.h>
+#include <sys/types.h>
+#include <unistd.h>
#include <isc/entropy.h>
-#include <isc/lfsr.h>
#include <isc/mem.h>
#include <isc/mutex.h>
#include <isc/print.h>
#include <isc/string.h>
#include <isc/task.h>
+#include <isc/time.h>
#include <isc/util.h>
#include <dns/acl.h>
@@ -43,13 +45,22 @@
typedef ISC_LIST(dns_dispentry_t) dns_displist_t;
+typedef struct dns_nsid {
+ isc_uint16_t nsid_state;
+ isc_uint16_t *nsid_vtable;
+ isc_uint16_t *nsid_pool;
+ isc_uint16_t nsid_a1, nsid_a2, nsid_a3;
+ isc_uint16_t nsid_c1, nsid_c2, nsid_c3;
+ isc_uint16_t nsid_state2;
+ isc_boolean_t nsid_usepool;
+} dns_nsid_t;
+
typedef struct dns_qid {
unsigned int magic;
unsigned int qid_nbuckets; /* hash table size */
unsigned int qid_increment; /* id increment on collision */
isc_mutex_t lock;
- isc_lfsr_t qid_lfsr1; /* state generator info */
- isc_lfsr_t qid_lfsr2; /* state generator info */
+ dns_nsid_t nsid;
dns_displist_t *qid_table; /* the table itself */
} dns_qid_t;
@@ -158,7 +169,7 @@
static void udp_recv(isc_task_t *, isc_event_t *);
static void tcp_recv(isc_task_t *, isc_event_t *);
static void startrecv(dns_dispatch_t *);
-static dns_messageid_t dns_randomid(dns_qid_t *);
+static dns_messageid_t dns_randomid(dns_nsid_t *);
static isc_uint32_t dns_hash(dns_qid_t *, isc_sockaddr_t *, dns_messageid_t);
static void free_buffer(dns_dispatch_t *disp, void *buf, unsigned int len);
static void *allocate_udp_buffer(dns_dispatch_t *disp);
@@ -179,8 +190,12 @@
static isc_boolean_t destroy_mgr_ok(dns_dispatchmgr_t *mgr);
static void destroy_mgr(dns_dispatchmgr_t **mgrp);
static isc_result_t qid_allocate(dns_dispatchmgr_t *mgr, unsigned int buckets,
- unsigned int increment, dns_qid_t **qidp);
+ unsigned int increment, isc_boolean_t usepool,
+ dns_qid_t **qidp);
static void qid_destroy(isc_mem_t *mctx, dns_qid_t **qidp);
+static isc_uint16_t nsid_next(dns_nsid_t *nsid);
+static isc_result_t nsid_init(isc_mem_t *mctx, dns_nsid_t *nsid, isc_boolean_t usepool);
+static void nsid_destroy(isc_mem_t *mctx, dns_nsid_t *nsid);
#define LVL(x) ISC_LOG_DEBUG(x)
@@ -260,38 +275,16 @@
}
}
-static void
-reseed_lfsr(isc_lfsr_t *lfsr, void *arg)
-{
- dns_dispatchmgr_t *mgr = arg;
- isc_result_t result;
- isc_uint32_t val;
-
- REQUIRE(VALID_DISPATCHMGR(mgr));
-
- if (mgr->entropy != NULL) {
- result = isc_entropy_getdata(mgr->entropy, &val, sizeof(val),
- NULL, 0);
- INSIST(result == ISC_R_SUCCESS);
- lfsr->count = (val & 0x1f) + 32;
- lfsr->state = val;
- return;
- }
-
- lfsr->count = (random() & 0x1f) + 32; /* From 32 to 63 states */
- lfsr->state = random();
-}
-
/*
* Return an unpredictable message ID.
*/
static dns_messageid_t
-dns_randomid(dns_qid_t *qid) {
+dns_randomid(dns_nsid_t *nsid) {
isc_uint32_t id;
- id = isc_lfsr_generate32(&qid->qid_lfsr1, &qid->qid_lfsr2);
-
- return (dns_messageid_t)(id & 0xFFFF);
+ id = nsid_next(nsid);
+
+ return ((dns_messageid_t)id);
}
/*
@@ -631,6 +624,9 @@
goto restart;
}
+ dns_dispatch_hash(&ev->timestamp, sizeof(&ev->timestamp));
+ dns_dispatch_hash(ev->region.base, ev->region.length);
+
/* response */
bucket = dns_hash(qid, &ev->address, id);
LOCK(&qid->lock);
@@ -821,6 +817,8 @@
goto restart;
}
+ dns_dispatch_hash(tcpmsg->buffer.base, tcpmsg->buffer.length);
+
/*
* Response.
*/
@@ -1204,7 +1202,7 @@
isc_mempool_setmaxalloc(mgr->bpool, maxbuffers);
isc_mempool_associatelock(mgr->bpool, &mgr->pool_lock);
- result = qid_allocate(mgr, buckets, increment, &mgr->qid);
+ result = qid_allocate(mgr, buckets, increment, ISC_TRUE, &mgr->qid);
if (result != ISC_R_SUCCESS)
goto cleanup;
@@ -1350,7 +1348,7 @@
static isc_result_t
qid_allocate(dns_dispatchmgr_t *mgr, unsigned int buckets,
- unsigned int increment, dns_qid_t **qidp)
+ unsigned int increment, isc_boolean_t usepool, dns_qid_t **qidp)
{
dns_qid_t *qid;
unsigned int i;
@@ -1371,8 +1369,16 @@
return (ISC_R_NOMEMORY);
}
+ if (nsid_init(mgr->mctx, &qid->nsid, usepool) != ISC_R_SUCCESS) {
+ isc_mem_put(mgr->mctx, qid->qid_table,
+ buckets * sizeof(dns_displist_t));
+ isc_mem_put(mgr->mctx, qid, sizeof(*qid));
+ return (ISC_R_NOMEMORY);
+ }
+
if (isc_mutex_init(&qid->lock) != ISC_R_SUCCESS) {
UNEXPECTED_ERROR(__FILE__, __LINE__, "isc_mutex_init failed");
+ nsid_destroy(mgr->mctx, &qid->nsid);
isc_mem_put(mgr->mctx, qid->qid_table,
buckets * sizeof(dns_displist_t));
isc_mem_put(mgr->mctx, qid, sizeof(*qid));
@@ -1385,21 +1391,6 @@
qid->qid_nbuckets = buckets;
qid->qid_increment = increment;
qid->magic = QID_MAGIC;
-
- /*
- * Initialize to a 32-bit LFSR. Both of these are from Applied
- * Cryptography.
- *
- * lfsr1:
- * x^32 + x^7 + x^5 + x^3 + x^2 + x + 1
- *
- * lfsr2:
- * x^32 + x^7 + x^6 + x^2 + 1
- */
- isc_lfsr_init(&qid->qid_lfsr1, 0, 32, 0x80000057U,
- 0, reseed_lfsr, mgr);
- isc_lfsr_init(&qid->qid_lfsr2, 0, 32, 0x80000062U,
- 0, reseed_lfsr, mgr);
*qidp = qid;
return (ISC_R_SUCCESS);
}
@@ -1415,6 +1406,7 @@
*qidp = NULL;
qid->magic = 0;
+ nsid_destroy(mctx, &qid->nsid);
isc_mem_put(mctx, qid->qid_table,
qid->qid_nbuckets * sizeof(dns_displist_t));
DESTROYLOCK(&qid->lock);
@@ -1558,7 +1550,7 @@
return (result);
}
- result = qid_allocate(mgr, buckets, increment, &disp->qid);
+ result = qid_allocate(mgr, buckets, increment, ISC_FALSE, &disp->qid);
if (result != ISC_R_SUCCESS)
goto deallocate_dispatch;
@@ -1856,7 +1848,7 @@
*/
qid = DNS_QID(disp);
LOCK(&qid->lock);
- id = dns_randomid(qid);
+ id = dns_randomid(&qid->nsid);
bucket = dns_hash(qid, dest, id);
ok = ISC_FALSE;
for (i = 0; i < 64; i++) {
@@ -2199,3 +2191,409 @@
}
}
#endif
+
+/*
+ * Allow the user to pick one of two ID randomization algorithms.
+ *
+ * The first algorithm is an adaptation of the sequence shuffling
+ * algorithm discovered by Carter Bays and S. D. Durham [ACM Trans. Math.
+ * Software 2 (1976), 59-64], as documented as Algorithm B in Chapter
+ * 3.2.2 in Volume 2 of Knuth's "The Art of Computer Programming". We use
+ * a randomly selected linear congruential random number generator with a
+ * modulus of 2^16, whose increment is a randomly picked odd number, and
+ * whose multiplier is picked from a set which meets the following
+ * criteria:
+ * Is of the form 8*n+5, which ensures "high potency" according to
+ * principle iii in the summary chapter 3.6. This form also has a
+ * gcd(a-1,m) of 4 which is good according to principle iv.
+ *
+ * Is between 0.01 and 0.99 times the modulus as specified by
+ * principle iv.
+ *
+ * Passes the spectral test "with flying colors" (ut >= 1) in
+ * dimensions 2 through 6 as calculated by Algorithm S in Chapter
+ * 3.3.4 and the ratings calculated by formula 35 in section E.
+ *
+ * Of the multipliers that pass this test, pick the set that is
+ * best according to the theoretical bounds of the serial
+ * correlation test. This was calculated using a simplified
+ * version of Knuth's Theorem K in Chapter 3.3.3.
+ *
+ * These criteria may not be important for this use, but we might as well
+ * pick from the best generators since there are so many possible ones and
+ * we don't have that many random bits to do the picking.
+ *
+ * We use a modulus of 2^16 instead of something bigger so that we will
+ * tend to cycle through all the possible IDs before repeating any,
+ * however the shuffling will perturb this somewhat. Theoretically there
+ * is no minimimum interval between two uses of the same ID, but in
+ * practice it seems to be >64000.
+ *
+ * Our adaptatation of Algorithm B mixes the hash state which has
+ * captured various random events into the shuffler to perturb the
+ * sequence.
+ *
+ * One disadvantage of this algorithm is that if the generator parameters
+ * were to be guessed, it would be possible to mount a limited brute force
+ * attack on the ID space since the IDs are only shuffled within a limited
+ * range.
+ *
+ * The second algorithm uses the same random number generator to populate
+ * a pool of 65536 IDs. The hash state is used to pick an ID from a window
+ * of 4096 IDs in this pool, then the chosen ID is swapped with the ID
+ * at the beginning of the window and the window position is advanced.
+ * This means that the interval between uses of the ID will be no less
Home |
Main Index |
Thread Index |
Old Index