From 8661b3ff05c7aa2bf195a8016b38b52fc2bdfa15 Mon Sep 17 00:00:00 2001 From: reyk Date: Wed, 9 Jul 2008 17:16:51 +0000 Subject: [PATCH] Use OpenBSD's knuth shuffle algorithm of random values from bind to produce the DNS request ids instead of a simple per-request arc4random(). This ensure randomness but also satisfies the non-repeating property we need. ok deraadt@ --- usr.sbin/relayd/Makefile | 4 +- usr.sbin/relayd/relay.c | 12 +++++- usr.sbin/relayd/relay_udp.c | 14 +++++-- usr.sbin/relayd/relayd.h | 14 ++++++- usr.sbin/relayd/shuffle.c | 75 +++++++++++++++++++++++++++++++++++++ 5 files changed, 111 insertions(+), 8 deletions(-) create mode 100644 usr.sbin/relayd/shuffle.c diff --git a/usr.sbin/relayd/Makefile b/usr.sbin/relayd/Makefile index 7bfb74a6bb7..3015ba6dc37 100644 --- a/usr.sbin/relayd/Makefile +++ b/usr.sbin/relayd/Makefile @@ -1,10 +1,10 @@ -# $OpenBSD: Makefile,v 1.17 2008/02/11 10:42:50 reyk Exp $ +# $OpenBSD: Makefile,v 1.18 2008/07/09 17:16:51 reyk Exp $ PROG= relayd SRCS= parse.y log.c control.c buffer.c imsg.c ssl.c ssl_privsep.c \ relayd.c pfe.c pfe_filter.c hce.c relay.c relay_udp.c \ carp.c check_icmp.c check_tcp.c check_script.c name2id.c \ - snmp.c + snmp.c shuffle.c MAN= relayd.8 relayd.conf.5 LDADD= -levent -lssl -lcrypto diff --git a/usr.sbin/relayd/relay.c b/usr.sbin/relayd/relay.c index 005ca6852c2..c9432815bb0 100644 --- a/usr.sbin/relayd/relay.c +++ b/usr.sbin/relayd/relay.c @@ -1,4 +1,4 @@ -/* $OpenBSD: relay.c,v 1.91 2008/07/09 14:57:01 reyk Exp $ */ +/* $OpenBSD: relay.c,v 1.92 2008/07/09 17:16:51 reyk Exp $ */ /* * Copyright (c) 2006, 2007, 2008 Reyk Floeter @@ -485,6 +485,16 @@ relay_init(void) rlay->rl_dstnhosts, rlay->rl_dsttable->conf.name, rlay->rl_dsttable->conf.check ? "" : " (no check)"); } + + switch (rlay->rl_proto->type) { + case RELAY_PROTO_DNS: + relay_udp_init(rlay); + break; + case RELAY_PROTO_TCP: + case RELAY_PROTO_HTTP: + /* Use defaults */ + break; + } } /* Schedule statistics timer */ diff --git a/usr.sbin/relayd/relay_udp.c b/usr.sbin/relayd/relay_udp.c index a2971a65f7a..71fc4b87b09 100644 --- a/usr.sbin/relayd/relay_udp.c +++ b/usr.sbin/relayd/relay_udp.c @@ -1,4 +1,4 @@ -/* $OpenBSD: relay_udp.c,v 1.13 2008/07/09 14:57:01 reyk Exp $ */ +/* $OpenBSD: relay_udp.c,v 1.14 2008/07/09 17:16:51 reyk Exp $ */ /* * Copyright (c) 2007, 2008 Reyk Floeter @@ -54,6 +54,7 @@ extern struct imsgbuf *ibuf_pfe; extern int debug; struct relayd *env = NULL; +struct shuffle relay_shuffle; int relay_udp_socket(struct sockaddr_storage *, in_port_t, struct protocol *); @@ -72,20 +73,25 @@ int relay_dns_cmp(struct session *, struct session *); void relay_udp_privinit(struct relayd *x_env, struct relay *rlay) { - struct protocol *proto = rlay->rl_proto; - if (env == NULL) env = x_env; if (rlay->rl_conf.flags & F_SSL) fatalx("ssl over udp is not supported"); rlay->rl_conf.flags |= F_UDP; +} + +void +relay_udp_init(struct relay *rlay) +{ + struct protocol *proto = rlay->rl_proto; switch (proto->type) { case RELAY_PROTO_DNS: proto->validate = relay_dns_validate; proto->request = relay_dns_request; proto->cmp = relay_dns_cmp; + shuffle_init(&relay_shuffle); break; default: fatalx("unsupported udp protocol"); @@ -401,7 +407,7 @@ relay_dns_validate(struct session *con, struct relay *rlay, priv = malloc(sizeof(struct relay_dns_priv)); if (priv == NULL) return (NULL); - priv->dp_inkey = arc4random() & 0xffff; + priv->dp_inkey = shuffle_generate16(&relay_shuffle); priv->dp_outkey = key; return ((void *)priv); } diff --git a/usr.sbin/relayd/relayd.h b/usr.sbin/relayd/relayd.h index b9b81a707ab..1979e4285fa 100644 --- a/usr.sbin/relayd/relayd.h +++ b/usr.sbin/relayd/relayd.h @@ -1,4 +1,4 @@ -/* $OpenBSD: relayd.h,v 1.105 2008/07/09 14:57:01 reyk Exp $ */ +/* $OpenBSD: relayd.h,v 1.106 2008/07/09 17:16:51 reyk Exp $ */ /* * Copyright (c) 2006, 2007 Pierre-Yves Ritschard @@ -64,6 +64,12 @@ #define DPRINTF(x...) do {} while(0) #endif +/* Used for DNS request ID randomization */ +struct shuffle { + u_int16_t id_shuffle[65536]; + int isindex; +}; + /* buffer */ struct buf { TAILQ_ENTRY(buf) entry; @@ -801,6 +807,7 @@ SPLAY_PROTOTYPE(session_tree, session, se_nodes, relay_session_cmp); /* relay_udp.c */ void relay_udp_privinit(struct relayd *, struct relay *); +void relay_udp_init(struct relay *); int relay_udp_bind(struct sockaddr_storage *, in_port_t, struct protocol *); void relay_udp_server(int, short, void *); @@ -871,3 +878,8 @@ void pn_ref(u_int16_t); void snmp_init(struct relayd *, struct imsgbuf *); int snmp_sendsock(struct imsgbuf *); void snmp_hosttrap(struct table *, struct host *); + +/* shuffle.c */ +void shuffle_init(struct shuffle *); +u_int16_t shuffle_generate16(struct shuffle *); + diff --git a/usr.sbin/relayd/shuffle.c b/usr.sbin/relayd/shuffle.c new file mode 100644 index 00000000000..a6ce822f9b2 --- /dev/null +++ b/usr.sbin/relayd/shuffle.c @@ -0,0 +1,75 @@ +/* $OpenBSD: shuffle.c,v 1.1 2008/07/09 17:16:51 reyk Exp $ */ + +/* + * Portions Copyright (C) 2008 Theo de Raadt + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM + * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL + * INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING + * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, + * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION + * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* based on: bind/lib/isc/shuffle.c,v 1.4 2008/07/09 17:07:32 reyk Exp $ */ + +#include +#include + +#include +#include + +#include +#include +#include +#include + +#include + +#include "relayd.h" + +#define VALID_SHUFFLE(x) (x != NULL) + +void +shuffle_init(struct shuffle *shuffle) +{ + int i, i2; + + assert(VALID_SHUFFLE(shuffle)); + + shuffle->isindex = 0; + /* Initialize using a Knuth shuffle */ + for (i = 0; i < 65536; ++i) { + i2 = arc4random_uniform(i + 1); + shuffle->id_shuffle[i] = shuffle->id_shuffle[i2]; + shuffle->id_shuffle[i2] = i; + } +} + +u_int16_t +shuffle_generate16(struct shuffle *shuffle) +{ + u_int32_t si; + u_int16_t r; + int i, i2; + + assert(VALID_SHUFFLE(shuffle)); + + do { + si = arc4random(); + i = shuffle->isindex & 0xFFFF; + i2 = (shuffle->isindex - (si & 0x7FFF)) & 0xFFFF; + r = shuffle->id_shuffle[i]; + shuffle->id_shuffle[i] = shuffle->id_shuffle[i2]; + shuffle->id_shuffle[i2] = r; + shuffle->isindex++; + } while (r == 0); + + return (r); +} -- 2.20.1