|
On Thu, Jun 05, 2003 at 07:17:29AM -0400, Joseph Mack wrote:
> Here's a posting in ./ to an article about DoS attacks on hash functions.
>
> http://slashdot.org/article.pl?sid=03/05/31/2157254&mode=thread&tid=126&tid=172
>
> is LVS susceptible to this sort of attack on the connection hash table?
>
> I would imagine that the client only has a small number of variables (the
> port they are sending from?), the others being fixed (CIP, VIP:port).
> and probably can't mount much of an attack even if they can choose the
> ports at the clients end.
Here is my take on this:
LVS uses the following hash
(proto^addr^(addr>>IP_VS_CONN_TAB_BITS)^port) & IP_VS_CONN_TAB_MASK
^ is Bitwise XOR
proto is the protocol number 6 for TCP and 17 for UDP
addr is the source IP address in host byte order
port is the source portin host byte order
IP_VS_CONN_TAB_BITS defaults to 8
IP_VS_CONN_TAB_MASK is (1 << IP_VS_CONN_TAB_BITS) - 1
thus the default is 0xff
>From here on ^ will mean power
The only inputs and end user can effect are addr and port.
I would say that it is quite easy for someone to set things
up so that they consistently hit the same bucket.
For instance by connecting from the same ip address
with different ports from the set (port % IP_VS_CONN_TAB_MASK) = n
Though we ovserve that each end-user only has
2^(16-IP_VS_CONN_TAB_BITS) = 256 such ports.
So they would need to use multiple source IP addresses.
What is the effect of this on LVS?
The effect is that instead of n connections going into
2^IP_VS_CONN_TAB_BITS different buckets they will
go into one bucket. Thus LVS will have to do on average n/2 traversals
instead of n/2^(IP_VS_CONN_TAB_BITS+1) traversals.
So the real effect is to amplify traversal times
by 2^IP_VS_CONN_TAB_BITS. Though it is worth remembering
that the larger IP_VS_CONN_TAB_BITS is then lower
2^(16-IP_VS_CONN_TAB_BITS) becomes, and thus
the greater the number of source IP addresses required becomes.
Though if it was a UDP bassed attack this might not be
an issue as the source IP could be spoofed.
This could become a problem if n became very large.
But how large? Traversal is actually pretty fast.
So I think that n would need to be quite large indeed
to have a noticable effect on LVS and larger still
to seriously degrade performance. Though I could be wrong.
As for soulitions, it is a bit tricky AFIK.
Perhaps using some component of the skb which
is static for a connection, but not directly
influenced by end users. But that may well
open up a whole new can of worms.
--
Horms
|
