insufficient TCP source port randomness
Subsystems (3)
v3 cover insufficient TCP source port randomness
Hi,
In a not-yet published paper, Moshe Kol, Amit Klein, and Yossi Gilad report being able to accurately identify a client by forcing it to emit only 40 times more connections than the number of entries in the table_perturb[] table, which is indexed by hashing the connection tuple. The current 2^8 setting allows them to perform that attack with only 10k connections, which is not hard to achieve in a few seconds.
Eric, Amit and I have been working on this for a few weeks now imagining, testing and eliminating a number of approaches that Amit and his team were still able to break or that were found to be too risky or too expensive, and ended up with the simple improvements in this series that resists to the attack, doesn't degrade the performance, and preserves a reliable port selection algorithm to avoid connection failures, including the odd/even port selection preference that allows bind() to always find a port quickly even under strong connect() stress.
The approach relies on several factors:
- resalting the hash secret that's used to choose the table_perturb[] entry every 10 seconds to eliminate slow attacks and force the attacker to forget everything that was learned after this delay. This already eliminates most of the problem because if a client stays silent for more than 10 seconds there's no link between the previous and the next patterns, and 10s isn't yet frequent enough to cause too frequent repetition of a same port that may induce a connection failure ;
- adding small random increments to the source port. Previously, a random 0 or 1 was added every 16 ports. Now a random 0 to 7 is added after each port. This means that with the default 32768-60999 range, a worst case rollover happens after 1764 connections, and an average of 3137. This doesn't stop statistical attacks but requires significantly more iterations of the same attack to confirm a guess.
- increasing the table_perturb[] size from 2^8 to 2^16, which Amit says will require 2.6 million connections to be attacked with the changes above, making it pointless to get a fingerprint that will only last 10 seconds. Due to the size, the table was made dynamic.
- a few minor improvements on the bits used from the hash, to eliminate some unfortunate correlations that may possibly have been exploited to design future attack models.
These changes were tested under the most extreme conditions, up to 1.1 million connections per second to one and a few targets, showing no performance regression, and only 2 connection failures within 13 billion, which is less than 2^-32 and perfectly within usual values.
The series is split into small reviewable changes and was already reviewed by Amit and Eric.
Regards,
Willy
---
v3:
- fix field ordering in secure_ipv6_port_ephemeral() so that the timeseed is really part of the hashed array. Spotted by Jason.
v2:
- fixed build issue reported by [email protected] on 32-bit archs due to the 64-by-32 divide; it's now correctly 32-by-32 as suggested by Eric
- addressed the IPv6 hash size as well that was overlooked, as reported by Jason
---
Eric Dumazet (1):
tcp: resalt the secret every 10 seconds
Willy Tarreau (6):
secure_seq: use the 64 bits of the siphash for port offset calculation
tcp: use different parts of the port_offset for index and offset
tcp: add small random increments to the source port
tcp: dynamically allocate the perturb table used by source ports
tcp: increase source port perturb table to 2^16
tcp: drop the hash_32() part from the index calculation
include/net/inet_hashtables.h | 2 +- include/net/secure_seq.h | 4 ++-- net/core/secure_seq.c | 16 ++++++++----- net/ipv4/inet_hashtables.c | 42 ++++++++++++++++++++++------------- net/ipv6/inet6_hashtables.c | 4 ++-- 5 files changed, 43 insertions(+), 25 deletions(-)
Signature · 1 line
2.17.5
PATCH v3 1/7 secure_seq: use the 64 bits of the siphash for port offset calculation
SipHash replaced MD5 in secure_ipv{4,6}_port_ephemeral() via commit 7cd23e5300c1 ("secure_seq: use SipHash in place of MD5"), but the output remained truncated to 32-bit only. In order to exploit more bits from the hash, let's make the functions return the full 64-bit of siphash_3u32(). We also make sure the port offset calculation in __inet_hash_connect() remains done on 32-bit to avoid the need for div_u64_rem() and an extra cost on 32-bit systems.
--- include/net/inet_hashtables.h | 2 +- include/net/secure_seq.h | 4 ++-- net/core/secure_seq.c | 4 ++-- net/ipv4/inet_hashtables.c | 10 ++++++---- net/ipv6/inet6_hashtables.c | 4 ++-- 5 files changed, 13 insertions(+), 11 deletions(-)
include/net/inet_hashtables.h +1 -1
@@ -425,7 +425,7 @@ static inline void sk_rcv_saddr_set(struct sock *sk, __be32 addr) }int __inet_hash_connect (struct inet_timewait_death_row *death_row, -struct sock *sk,u32 port_offset, +struct sock *sk,u64 port_offset,int (*check_established)(struct inet_timewait_death_row *,struct sock *,__u16 ,struct inet_timewait_sock **));
include/net/secure_seq.h +2 -2
@@ -4,8 +4,8 @@#include <linux/types.h> -u32 secure_ipv4_port_ephemeral (__be32 saddr,__be32 daddr,__be16 dport); -u32 secure_ipv6_port_ephemeral (const __be32 *saddr,const __be32 *daddr, +u64 secure_ipv4_port_ephemeral (__be32 saddr,__be32 daddr,__be16 dport); +u64 secure_ipv6_port_ephemeral (const __be32 *saddr,const __be32 *daddr,__be16 dport);u32 secure_tcp_seq (__be32 saddr,__be32 daddr,__be16 sport,__be16 dport);
net/core/secure_seq.c +2 -2
@@ -94,7 +94,7 @@ u32 secure_tcpv6_seq(const __be32 *saddr, const __be32 *daddr, }EXPORT_SYMBOL (secure_tcpv6_seq); -u32 secure_ipv6_port_ephemeral (const __be32 *saddr,const __be32 *daddr, +u64 secure_ipv6_port_ephemeral (const __be32 *saddr,const __be32 *daddr,__be16 dport) { const struct {
@@ -142,7 +142,7 @@ u32 secure_tcp_seq(__be32 saddr, __be32 daddr, }EXPORT_SYMBOL_GPL (secure_tcp_seq); -u32 secure_ipv4_port_ephemeral (__be32 saddr,__be32 daddr,__be16 dport) +u64 secure_ipv4_port_ephemeral (__be32 saddr,__be32 daddr,__be16 dport) {net_secret_init (); return siphash_3u32((__force u32)saddr, (__force u32)daddr,
net/ipv4/inet_hashtables.c +6 -4
@@ -504,7 +504,7 @@ static int __inet_check_established(struct inet_timewait_death_row *death_row,return -EADDRNOTAVAIL ; } -static u32 inet_sk_port_offset (const struct sock *sk) +static u64 inet_sk_port_offset (const struct sock *sk) {const struct inet_sock *inet =inet_sk (sk);
@@ -734,7 +734,7 @@ EXPORT_SYMBOL_GPL(inet_unhash);static u32 table_perturb[1 <<INET_TABLE_PERTURB_SHIFT ];int __inet_hash_connect (struct inet_timewait_death_row *death_row, -struct sock *sk,u32 port_offset, +struct sock *sk,u64 port_offset,int (*check_established)(struct inet_timewait_death_row *,struct sock *,__u16 ,struct inet_timewait_sock **)) {
@@ -777,7 +777,9 @@ int __inet_hash_connect(struct inet_timewait_death_row *death_row,net_get_random_once (table_perturb,sizeof (table_perturb)); index =hash_32 (port_offset,INET_TABLE_PERTURB_SHIFT ); - offset = (READ_ONCE (table_perturb[index]) + port_offset) % remaining; + offset =READ_ONCE (table_perturb[index]) + port_offset; + offset %= remaining; +/* In first pass we try ports of @low parity. * inet_csk_get_port() does the opposite choice. */
@@ -859,7 +861,7 @@ int __inet_hash_connect(struct inet_timewait_death_row *death_row,int inet_hash_connect (struct inet_timewait_death_row *death_row,struct sock *sk) { -u32 port_offset =0 ; +u64 port_offset =0 ;if (!inet_sk (sk)->inet_num) port_offset =inet_sk_port_offset (sk);
net/ipv6/inet6_hashtables.c +2 -2
@@ -308,7 +308,7 @@ static int __inet6_check_established(struct inet_timewait_death_row *death_row,return -EADDRNOTAVAIL ; } -static u32 inet6_sk_port_offset (const struct sock *sk) +static u64 inet6_sk_port_offset (const struct sock *sk) {const struct inet_sock *inet =inet_sk (sk);
@@ -320,7 +320,7 @@ static u32 inet6_sk_port_offset(const struct sock *sk)int inet6_hash_connect (struct inet_timewait_death_row *death_row,struct sock *sk) { -u32 port_offset =0 ; +u64 port_offset =0 ;if (!inet_sk (sk)->inet_num) port_offset =inet6_sk_port_offset (sk);
Signature · 1 line
2.17.5
PATCH v3 2/7 tcp: use different parts of the port_offset for index and offset
In reply to Willy TarreauAmit Klein suggests that we use different parts of port_offset for the table's index and the port offset so that there is no direct relation between them.
--- net/ipv4/inet_hashtables.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
net/ipv4/inet_hashtables.c +1 -1
@@ -777,7 +777,7 @@ int __inet_hash_connect(struct inet_timewait_death_row *death_row,net_get_random_once (table_perturb,sizeof (table_perturb)); index =hash_32 (port_offset,INET_TABLE_PERTURB_SHIFT ); - offset =READ_ONCE (table_perturb[index]) + port_offset; + offset =READ_ONCE (table_perturb[index]) + (port_offset >>32 ); offset %= remaining;/* In first pass we try ports of @low parity.
Signature · 1 line
2.17.5
PATCH v3 3/7 tcp: resalt the secret every 10 seconds
In reply to Willy TarreauFrom: Eric Dumazet <[email protected]>
In order to limit the ability for an observer to recognize the source ports sequence used to contact a set of destinations, we should periodically shuffle the secret. 10 seconds looks effective enough without causing particular issues.
--- net/core/secure_seq.c | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-)
net/core/secure_seq.c +9 -3
@@ -22,6 +22,8 @@static siphash_aligned_key_t net_secret;static siphash_aligned_key_t ts_secret; +#define EPHEMERAL_PORT_SHUFFLE_PERIOD (10 * HZ) + static __always_inline void net_secret_init(void) {net_get_random_once (&net_secret,sizeof (net_secret));
@@ -100,11 +102,13 @@ u64 secure_ipv6_port_ephemeral(const __be32 *saddr, const __be32 *daddr,const struct {struct in6_addr saddr;struct in6_addr daddr; +unsigned int timeseed;__be16 dport; }__aligned(SIPHASH_ALIGNMENT) combined = { .saddr = *(struct in6_addr *)saddr, .daddr = *(struct in6_addr *)daddr, - .dport = dport + .timeseed = jiffies /EPHEMERAL_PORT_SHUFFLE_PERIOD , + .dport = dport, };net_secret_init (); return siphash(&combined, offsetofend(typeof(combined), dport),
@@ -145,8 +149,10 @@ EXPORT_SYMBOL_GPL(secure_tcp_seq);u64 secure_ipv4_port_ephemeral (__be32 saddr,__be32 daddr,__be16 dport) {net_secret_init (); -return siphash_3u32 ((__force u32 )saddr, (__force u32 )daddr, - (__force u16 )dport, &net_secret); +return siphash_4u32 ((__force u32 )saddr, (__force u32 )daddr, + (__force u16 )dport, + jiffies /EPHEMERAL_PORT_SHUFFLE_PERIOD , + &net_secret); }EXPORT_SYMBOL_GPL (secure_ipv4_port_ephemeral);#endif
Signature · 1 line
2.17.5
PATCH v3 4/7 tcp: add small random increments to the source port
In reply to Willy TarreauHere we're randomly adding between 0 and 7 random increments to the selected source port in order to add some noise in the source port selection that will make the next port less predictable.
With the default port range of 32768-60999 this means a worst case reuse scenario of 14116/8=1764 connections between two consecutive uses of the same port, with an average of 14116/4.5=3137. This code was stressed at more than 800000 connections per second to a fixed target with all connections closed by the client using RSTs (worst condition) and only 2 connections failed among 13 billion, despite the hash being reseeded every 10 seconds, indicating a perfectly safe situation.
--- net/ipv4/inet_hashtables.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-)
net/ipv4/inet_hashtables.c +5 -4
@@ -833,11 +833,12 @@ int __inet_hash_connect(struct inet_timewait_death_row *death_row,return -EADDRNOTAVAIL ; ok: -/* If our first attempt found a candidate, skip next candidate -* in 1/16 of cases to add some noise. +/* Here we want to add a little bit of randomness to the next source +* port that will be chosen. We use a max() with a random here so that +* on low contention the randomness is maximal and on high contention +* it may be inexistent. */ -if (!i && !(prandom_u32 () %16 )) - i =2 ; + i =max_t (int, i, (prandom_u32 () &7 ) *2 );WRITE_ONCE (table_perturb[index],READ_ONCE (table_perturb[index]) + i +2 );/* Head lock still held and bh's disabled */
Signature · 1 line
2.17.5
PATCH v3 5/7 tcp: dynamically allocate the perturb table used by source ports
In reply to Willy TarreauWe'll need to further increase the size of this table and it's likely that at some point its size will not be suitable anymore for a static table. Let's allocate it on boot from inet_hashinfo2_init(), which is called from tcp_init().
--- net/ipv4/inet_hashtables.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-)
net/ipv4/inet_hashtables.c +10 -2
@@ -731,7 +731,8 @@ EXPORT_SYMBOL_GPL(inet_unhash);* privacy, this only consumes 1 KB of kernel memory. */ #define INET_TABLE_PERTURB_SHIFT 8 -static u32 table_perturb[1 <<INET_TABLE_PERTURB_SHIFT ]; +#define INET_TABLE_PERTURB_SIZE (1 << INET_TABLE_PERTURB_SHIFT) +static u32 *table_perturb; int __inet_hash_connect(struct inet_timewait_death_row *death_row, struct sock *sk, u64 port_offset,
@@ -774,7 +775,8 @@ int __inet_hash_connect(struct inet_timewait_death_row *death_row,if (likely (remaining >1 )) remaining &= ~1U ; -net_get_random_once (table_perturb,sizeof (table_perturb)); +net_get_random_once (table_perturb, +INET_TABLE_PERTURB_SIZE *sizeof (*table_perturb)); index =hash_32 (port_offset,INET_TABLE_PERTURB_SHIFT ); offset =READ_ONCE (table_perturb[index]) + (port_offset >>32 );
@@ -912,6 +914,12 @@ void __init inet_hashinfo2_init(struct inet_hashinfo *h, const char *name, low_limit, high_limit);init_hashinfo_lhash2 (h); + +/* this one is used for source ports of outgoing connections */ + table_perturb =kmalloc_array (INET_TABLE_PERTURB_SIZE , +sizeof (*table_perturb),GFP_KERNEL ); +if (!table_perturb) +panic ("TCP: failed to alloc table_perturb" ); }int inet_hashinfo2_init_mod (struct inet_hashinfo *h)
Signature · 1 line
2.17.5
PATCH v3 6/7 tcp: increase source port perturb table to 2^16
In reply to Willy TarreauMoshe Kol, Amit Klein, and Yossi Gilad reported being able to accurately identify a client by forcing it to emit only 40 times more connections than there are entries in the table_perturb[] table. The previous two improvements consisting in resalting the secret every 10s and adding randomness to each port selection only slightly improved the situation, and the current value of 2^8 was too small as it's not very difficult to make a client emit 10k connections in less than 10 seconds.
Thus we're increasing the perturb table from 2^8 to 2^16 so that the the same precision now requires 2.6M connections, which is more difficult in this time frame and harder to hide as a background activity. The impact is that the table now uses 256 kB instead of 1 kB, which could mostly affect devices making frequent outgoing connections. However such components usually target a small set of destinations (load balancers, database clients, perf assessment tools), and in practice only a few entries will be visited, like before.
A live test at 1 million connections per second showed no performance difference from the previous value.
--- net/ipv4/inet_hashtables.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-)
net/ipv4/inet_hashtables.c +5 -4
@@ -726,11 +726,12 @@ EXPORT_SYMBOL_GPL(inet_unhash);* Note that we use 32bit integers (vs RFC 'short integers') * because 2^16 is not a multiple of num_ephemeral and this * property might be used by clever attacker. -* RFC claims using TABLE_LENGTH=10 buckets gives an improvement, -* we use 256 instead to really give more isolation and -* privacy, this only consumes 1 KB of kernel memory. +* RFC claims using TABLE_LENGTH=10 buckets gives an improvement, though +* attacks were since demonstrated, thus we use 65536 instead to really +* give more isolation and privacy, at the expense of 256kB of kernel +* memory. */ -#define INET_TABLE_PERTURB_SHIFT 8 +#define INET_TABLE_PERTURB_SHIFT 16#define INET_TABLE_PERTURB_SIZE (1 << INET_TABLE_PERTURB_SHIFT)static u32 *table_perturb;
Signature · 1 line
2.17.5
PATCH v3 7/7 tcp: drop the hash_32() part from the index calculation
In reply to Willy TarreauIn commit 190cc82489f4 ("tcp: change source port randomizarion at connect() time"), the table_perturb[] array was introduced and an index was taken from the port_offset via hash_32(). But it turns out that hash_32() performs a multiplication while the input here comes from the output of SipHash in secure_seq, that is well distributed enough to avoid the need for yet another hash.
--- net/ipv4/inet_hashtables.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
net/ipv4/inet_hashtables.c +1 -1
@@ -778,7 +778,7 @@ int __inet_hash_connect(struct inet_timewait_death_row *death_row,net_get_random_once (table_perturb,INET_TABLE_PERTURB_SIZE *sizeof (*table_perturb)); - index =hash_32 (port_offset,INET_TABLE_PERTURB_SHIFT ); + index = port_offset & (INET_TABLE_PERTURB_SIZE -1 ); offset =READ_ONCE (table_perturb[index]) + (port_offset >>32 ); offset %= remaining;
Signature · 1 line
2.17.5
This series was applied to netdev/net.git (master) by Jakub Kicinski <[email protected]>:
Hello:
This series was applied to netdev/net.git (master) by Jakub Kicinski <[email protected]>:
Quoted 10 lines · On Mon, 2 May 2022 10:46:07 +0200 you wrote:
Hi,
In a not-yet published paper, Moshe Kol, Amit Klein, and Yossi Gilad report being able to accurately identify a client by forcing it to emit only 40 times more connections than the number of entries in the table_perturb[] table, which is indexed by hashing the connection tuple. The current 2^8 setting allows them to perform that attack with only 10k connections, which is not hard to achieve in a few seconds.
[...]
Here is the summary with links:
- [v3,net,1/7] secure_seq: use the 64 bits of the siphash for port offset calculation
https://git.kernel.org/netdev/net/c/b2d057560b81 - [v3,net,2/7] tcp: use different parts of the port_offset for index and offset https://git.kernel.org/netdev/net/c/9e9b70ae923b - [v3,net,3/7] tcp: resalt the secret every 10 seconds https://git.kernel.org/netdev/net/c/4dfa9b438ee3 - [v3,net,4/7] tcp: add small random increments to the source port https://git.kernel.org/netdev/net/c/ca7af0402550 - [v3,net,5/7] tcp: dynamically allocate the perturb table used by source ports https://git.kernel.org/netdev/net/c/e9261476184b - [v3,net,6/7] tcp: increase source port perturb table to 2^16 https://git.kernel.org/netdev/net/c/4c2c8f03a5ab - [v3,net,7/7] tcp: drop the hash_32() part from the index calculation https://git.kernel.org/netdev/net/c/e8161345ddbb
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html