Poor port numbers distribution for udp

[Vitaly Mayatskikh <v.mayatskih@gmail.com>]

UDP port randomizator doesn't always use port number, provided by
net_random(), even when port is free. It tries to search empty or
shortest chain and use the first available port in it. In practice this
weakens the quality of distribution: there are ports in partially
filled chains, which will never be allocated, but their entropy will
go to the port from next empty or shorter chain. 

This simple test outputs entropy for random ports allocation (output
may be used then in Octave):

#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>

#define PORTS 65536

int main()
{
	int s, err, i, j;
	char buf[256];
	struct sockaddr_in sa = { 0 }, sa1;
	int optval = 1, port;
	unsigned int p[PORTS] = { 0 };

	sa.sin_addr.s_addr = htonl(INADDR_ANY);
	sa.sin_family = AF_INET;
	sa.sin_port = 0;

	for (i = 0; i < PORTS * 100; ++i) {
		s = socket(PF_INET, SOCK_DGRAM, IPPROTO_UDP);
		err = bind(s, (const struct sockaddr*)&sa, sizeof(sa));
		getsockname(s, (struct sockaddr*)&sa1, &j);
		port = ntohs(sa1.sin_port);
		p[port]++;
		close(s);
	}
	printf("x = 32767:1:65535;\ny = [");
	for (i = 32767; i < PORTS; i++)
		printf("%d%s", p[i], (i + 1 < PORTS ? "; " : ""));
	printf("];\nplot(x,y,'.');pause;");
}

It outputs ... 221 237 0 437 242 264 ... in period. Distances between
zero time allocated ports also repeat in period: ... 42, 84, 42, 84,
...  or ... 5, 4, 0, 1, 3, 0, 15, 5, 9, 16, 7, 13, 0, 35, 0
... (depends on kernel version). It's possible to utilize this
weakness for compromising systems (like dns servers).

The simplest way to fix this issue is to use port number, provided by
net_random() (if it's not in use).

Signed-off-by: Vitaly Mayatskikh <v.mayatskih@gmail.com>

diff --git a/net/ipv4/udp.c b/net/ipv4/udp.c
index 57e26fa..e9c8dea 100644
--- a/net/ipv4/udp.c
+++ b/net/ipv4/udp.c
@@ -167,6 +167,9 @@ int udp_lib_get_port(struct sock *sk, unsigned short snum,
 		best_size_so_far = UINT_MAX;
 		best = rover = net_random() % remaining + low;
 
+		if (! __udp_lib_lport_inuse(net, rover, udptable))
+			goto gotit;
+
 		/* 1st pass: look for empty (or shortest) hash chain */
 		for (i = 0; i < UDP_HTABLE_SIZE; i++) {
 			int size = 0;

--
wbr, Vitaly