netdev - RFC: Established connections hash function

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 22 Mar 2007 08:39:04 -0700
From:	"Nikolaos D. Bougalis" <nikb@...master.com>
To:	<netdev@...r.kernel.org>
Subject: RFC: Established connections hash function

    Hello,

    I have noticed that the hash function that the kernel uses for
established TCP/IP connections is rather simplistic, specifically:

    h = (local address ^ local_port) ^ (remote_address ^ remote_port);
    h ^= h >> 16;
    h ^= h >> 8;

    Now, simple is great, but this has a number of issues, not the least of
which is that an attacker can very easily cause collisions and force
extremely long chain lengths, a situation that becomes worse the more
distinct IP addresses and listening ports a box has.

    Consider, for example, a box that has 20 ports open and 4 consecutive IP
addresses. An attacker that has an entire class C available can create
24,576 connections that hash to the same value, resulting in a ridiculously
overlong chain. With servers that do virtual hosting and have dozens of IPs,
the situation can become much worse very fast.

    This particular hash seems to be the odd-man out, since most other
network related hashes in the kernel seem to be Jenkins-based, and some use
tagged hashing to defeat algorithmic complexity attacks. For example, the
route hash uses this:

static unsigned int rt_hash_rnd;

static unsigned int rt_hash_code(u32 daddr, u32 saddr)
{
        return (jhash_2words(daddr, saddr, rt_hash_rnd)
                & rt_hash_mask);
}

    With this in mind, I propose the following replacement for inet_ehashfn,
which defeats algorithmic complexity attacks and achieves excellent
distribution:

unsigned int inet_ehashfn(const __be32 laddr, const __u16 lport,
                          const __be32 faddr, const __be16 fport)
{
    return jhash_3words((__force __u32)faddr, (__force __u32)laddr,
                        (((__force __u32)fport) << 16) + lport,
                        inet_ehash_rnd);
}

    where inet_ehash_rnd is initialized once in tcp_init to a random 32-bit
value.

    I will be more than happy to provide a patch for this, but I figured I
would solicit some input first.

    Nik B.


-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html