From mboxrd@z Thu Jan 1 00:00:00 1970 From: Evgeniy Polyakov Subject: Re: RFC: Established connections hash function Date: Fri, 23 Mar 2007 11:33:32 +0300 Message-ID: <20070323083331.GB7193@2ka.mipt.ru> References: <391F64D0A7C5463CA2D70362E4B3E7EC@XEON> <20070322182156.GB17793@2ka.mipt.ru> <1199CE22A40740D28833A585014BE559@XEON> <20070322.135834.74723088.davem@davemloft.net> <20070323080715.GB29991@2ka.mipt.ru> <46038D0F.1060507@cosmosbay.com> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="qDbXVdCdHGoSgWSk" Cc: David Miller , nikb@webmaster.com, netdev@vger.kernel.org To: Eric Dumazet Return-path: Received: from relay.2ka.mipt.ru ([194.85.82.65]:60013 "EHLO 2ka.mipt.ru" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1422717AbXCWIf0 (ORCPT ); Fri, 23 Mar 2007 04:35:26 -0400 Content-Disposition: inline In-Reply-To: <46038D0F.1060507@cosmosbay.com> Sender: netdev-owner@vger.kernel.org List-Id: netdev.vger.kernel.org --qDbXVdCdHGoSgWSk Content-Type: text/plain; charset=koi8-r Content-Disposition: inline On Fri, Mar 23, 2007 at 09:17:19AM +0100, Eric Dumazet (dada1@cosmosbay.com) wrote: > You have a machine somewhere that allows 65536 concurrent connections > coming from the same IP address ? Attached png file of botnet scenario: 1000 addresses from the same network (class B for example), each one creates 1024 connections to the same static port. Eric, I agree, that XOR hash is not perfect, and it should be changed, but not blindly. I perfectly know that hash function is not bijective, but it must have good distribution. Function like this int hash(u32 saddr, u16 sport, u32 daddr, u16 dport, u32 rand) { return ((((rand ^ saddr ^ daddr)>>16)^(dport ^ sport)) >>8); } has even worse _distribution_, although you can not predict its end result due to random value, and attacker will not try to do it. -- Evgeniy Polyakov --qDbXVdCdHGoSgWSk Content-Type: image/png Content-Disposition: attachment; filename="jhash_botnet.png" Content-Transfer-Encoding: base64 iVBORw0KGgoAAAANSUhEUgAAAoAAAAHCEAIAAACgRzPNAAAACXBIWXMAAAsSAAALEgHS3X78 AAAVG0lEQVR42u3d7ZLaOAKGUTTV93/L2h+eqVWi2DH4A8nvOVUzNUtYQtsyzYOEXWqttdYX AAAAPNo/NgEAAAAJBDAAAAARhg7g0tm+p90JAADAmkEDeAna2ulDt72nDAYAAGDNZEug21N2 tenb/qkMBgAAoOc7wAAAAET4GfnJ9XO5V1y0yYwxAADAWUa+1O7QM8B7vgN8hPQFAAA418id NfQM8J1G/pSC8Q9s4wcjByMHIwcjB8afYpz4O8D9nHB/WiwAAABYDDoDvLbguY/b9p7SFwAA gDVDL4HeH7TSFwAAgG3Rs6a+2wAAAHCW8QvLdYABAACIIIABAACIIIABAOCB3r0gzWgXsBnh +Yx/UR/eJYABAIA/kH88jwAGAIBoo11S1CVOuY4ABgCABzoSkO3cb2n09+nvuXaftcd59/ls 3779d+35uc7ahoxJAAMAQKi1udb2ltroH2G5vX2cPilrZzto155Pn6/tPdtbtv+u/p4We+f4 sQkAACDNjMue+9j+7O/aDv5zf6bZxsXzZ7wFMAAQbnmTaqEjcC6vKiOyBBoAAIIcmUE98g3e 1trS5f3P3KJlPmMGGAAA+IM+Nbe/Cbz9OEeeSR/J/XLo7W8g25v8O5aSB8SegxkAeDpLoOHK o8sFjfL2+PLfY+53S6ABAACIIIABAIBLmPtlNAIYAACACAIYAACACAIYAACACAIYAACACAIY AACACAIYAACACAIYAIBXKaWUct39k5//aNvqup/xyE/62SOctW3XHidh36URwAAAB3mL/N9W GHU7yJjrtsnyOLXx2SO7YjD3EMAAALyhDZ5Zno+4upOtzch+bAIAAI5ESzvj1/53+5j97X24 rs0cnvXc1h5n+z79s/rsPvufz/bP0s+yvvt89uyvc+3fPu8+zmd/1/45ajH/PAIYAIBd1uZa 14K219+z/3+t5cr+29f+xj0/0bvPZ/9z23PLZ3vh3eezf3/teSb9f+/5Gd/927cfZ//ftedx eDYBDADAX8y47HmPPY+wnUZr87FrHxMc/9nH2QtnhfQVY2OMZ7L8M5Nal3+eTAADAMAf7J8t PD6vy1lG+oDg+TE5IyfBAgBg1ZGc+2wurnTGycv+J1qL4RmX1D51GbDlzbTMAAMAcII9J2fa vn3Pn+5x7gLptdN3rd1y1k9x1nNeez7799c9z2f727x7PlbY83fN+/EEZ4lennHPWe8AgLEt 7weOvBM4/gj8tx3PCNfR5o33P+e1P73/mY/2fJjrKB55nJgBBgDgUe6Z27ziOXs+cDUBDADA EM6NLgkH9JwECwAAgAgCGAAAgAgCGAAAgAgCGAAAgAgCGAAAgAgCGAAAgAgCGAAAgAgCGAAA gAgCGAAAgAgCGAAAgAgCGAAAgAgCGAAAgAgCGAAAgAgCGAAAgAgCGADg9XqVUoqtAPBsAhgA AIAIAhgAAIAIAhgAAIAIAhgAAIAIAhgAAIAIAhgAAIAIAhgAAIAIAhgAAIAIAhgAAIAIAhgA iFVKKa9XrbXaFgAJfsZ8WqUsv5D+rNbff1Et9+9vBwAAgMWgAbzYE7Rt+spgAAAA1ky8BLrP 3TaD7VoAAABaEwRwadhhAMBIvD8BmMnQS6D7Od7rFjmvBbYF1QAAAL0ZJykHDWDZCQAAwLmG ngG+k+QGAADYb+3qPCM/50G/A7xnw/WnvHIWaAAAANYMvQS6z+A+bl0ACQAAgD2mvw7wu/cE AAAg08TXAQYAGMPyQbxLIgGMTgADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQ QQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQ QQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQ QQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQ QQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQ QQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQ QQADAAAQQQADAAAQQQADAAAQQQADALxer1prfb1KKcW2AHgqAQwAAECEaQK4lK1PZLf/FAAA AKafAV7St9Zaa5XBAAAArJkggNeytk3f5RYZDAAAwJqhA7hPXAAAAPjMj02wWJs3lt8AAAC9 GdfeDjoDbO4XAACAcw09A9x/onBdGIttAACA/fqGGn9OeNAZ4NrpN3F/yivzxgAAAKyZ/jJI bQZLXwAAANZME8DbcSt9AQAA2Db9DDAAAADsIYABAACIIIABAD4w39UvARDAAAAfcxYSgJkI YAAAACIIYAAAACIIYAAAACIIYAAAACIIYAAAACIIYAAAACIIYAAAACIIYAAAACIIYAAAACII YAAAACIIYAAAACIIYAAAACIIYAAgUCmlvF611mpbAOQQwAAAAEQQwAAAAEQQwAAAAEQQwAAA AEQQwAAAAEQQwAAAAEQQwAAAAEQQwAAAp1iuKrxcYRiAEQlgAAAAIghgAAAAIghgAAAAIghg AAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghg AAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghg AAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghgAAAAIghg AAAAIghgAAAAIghgAAAAIvyM+bRKKaWUtT+ttdZa+/v3twMAAMBi0ABeS9k+jNv0lcEAAACs mWYJdB+3/S1tBtu1AAAAtCYIYPO6AAAAHDfoEuhFO5d7dQavzRsLbwAAgN6Ma2+HDmAnuwIA vmF5S+f9BsDTDB3AdxLVAMB/0et8IgB/tzZhOfJzHvQ7wHs2XH/KK/PDAAAArBn6Mkh9Bvdx 6wJIAAAA7DHZd4CP3xMAAIBM01wHGAAAAI4QwAAAAEQQwAAAAEQQwAAAAEQQwAAAAEQQwAAA AEQQwAAAAEQQwAAAAEQQwAAAAEQQwAAAAEQQwAAAAEQQwAAAbymllNer1lptC4C5CGAAAAAi CGAAAAAiCGAAAAAiCGAAAAAiCGAAAAAiCGAAAAAiCGAAAAAiCGAAAAAiCGAAAAAiCGAAAAAi CGAA4GFKKcVWAKAngAEAAIgggAEAAIgggAEAAIgggAEAAIgggAEAAIgggAEAAIgggAEAAIgg gAEAAIgggAEAAIgggAEAAIgggAEAAIgggAEAAIgggIEopZRy9j0BAJiDAAYAACCCAAYAACCC AAYAACCCAAYC+X4vAEAiAQwAAEAEAQwAAEAEAQwAAEAEAQwAPNLat/2X22ut1TYCSCOAAQAA iCCAAQAAiCCAgUDL0kcXQwIAyCKAAQAAiCCAAQBOZI0JwLgEMMAGb2EBAJ5DAAMAABBBAAMA ABBBAAOxfE8PACCLAAYAACCCAAYAACCCAAYAACCCAAYAAC5RyvIPjGLoAC6d7XvanQAAAKwZ NICXoK2dPnTbe8pgAAAA1ky8BLpN3+UWGQy8z8WQAABSDBrAbdYCAADAcT+zPNF+vveKx+9v l+IAAAC9GdfeTrAE+ur0BQCATM7STJqhZ4DvTF+BDQDzW+YifLcf4A59Q40/JzzBWaC3N3e7 ic0VAwAAsGaCGeD+9rUzP0tfAAAA1gwawO+mrPQFAABg28TXAQYAAID9BDAAAAARBDAAAPA2 l1BiRgIYAACACAIYAOA3riQM8EwCGAAAgAgCGAAAgAgCGAAAgAgCGAAAgAgCGGCDE+EAkMuF jngeAQwAAEAEAQwAAEAEAQwAAEAEAQwAAEAEAQwAAEAEAQwAAEAEAQwAPNIVlzFbHm15ZJjV uxc3cjEknkQAAwAAEEEAAwAAEEEAAwAAEEEAAwAAEEEAAwAAEEEAAwDAYzmHM7QEMAAAABEE MAAAABEEMAAAABEEMMDr9aq11terFN+SAgB4LgEMAABABAEMAABABAEMAABABAEMAACczPWH GZMABgAAIIIABgAAIIIABgCACJYlgwAGAAAgggAGAAAgwo9NAAAAyZal0bW+XrVuL5Pu/7S/ ZXkcW5UxmQEGAAAgggAGAAAgggAGAAAgggAGAABO42JLjEwAAwAAEEEAAwAAEEEAAyFKKeX1 qvXvF2bYf08AGNe7FzQ68mgwCwEMAABABAEMAABABAEM8FfLcuhlaTQAzGfPAmaLnEkggAEA AIgggAEAAIgggG9g2SQAAHf4bBlzrcs/W7ds3w6zEMAAABDNt3/JIYABAACIIIABAACIIIAB AACIIIABAACIIIABAACIIIABAGAy95y3ub3okQsg8QwCGAB4sFprfb1KcYkXOGY7ueUxs5gg gEv5+y+tPfcBAAAg2dABvD99a621VhkMAADAmkEDuM3a/feRwQAAcAWLnHmGQQN4O33nJMsB APgmEQs/NsFibd74iSkOAABw1Ixrb50FGgAAprTnYkhmfaFlBvhfZnoBAEiwJPGRKwkffwSe MpZ+b6jx54QnngHuT3m159RZAAAAZBp0Brj/5KC9Ze3Mz9IXAACANYMG8LspK30BAGCxLE7e /+1fS5rJ4SRYAAAARBDAAAAARBDAAECI5XwivjbFLOP19wXJ20uUr1vAvLaUerm9/dP+ni7C xGhcBgkAADiN6GVkZoABAE63zIuNfj1MgDQCGAAAgAgCGAAAHsLyY9gmgAEAAIgggAEAAIgg gKfm1BoY/44CuOdYG/+RXeKIZx+HV13iCNK4DBIwhf6NsjOsAsBevhsMCwEMDGgtdwEA4HMC +AEs+uIZY7hlPMOYx2nasdmuNPG6BPAEAhi4mdwFgBEty6R935hnE8DApe7JXfMzcM/xe93f 4vgF4A4C+FL9Wwe/5kkb81ePdqfCgqs5yuCb7p+Pdbosnk0A36ANAG8geBKLmYEcPsJm5NH5 eSTLXdII4Adwig7uIXcBAJibAAb+SO4C/SuAD1sBmJsABl5y99ef2lcV4GqOMgC+QwBDILkL jMBHTgDcTQDD48ldAAB4vV6vf2yC9435WbXP0WnHZ/vvZWy0/waYkd9xPHt83325I8hkBhim ZnYXAPiECyCRyQzwW9r5NJ9D860RaHZ3e/sA1x1N1/0GdPwCcAczwDAss7v7+VgKrjuyHL8A PIcAhq/bnmlhHK6DCt/Sr8ByDPLsEe/7wHAVAfww3hyMT+4CAMB3COCd+qSUmuwfOT1jBgAA 7uYkWJPyXamR90v774VTVQHPM9dvIq+9jHkUfbLUefl/bZ/D2RmeYY0Z4Kn5df5dZneBTE5b BcCsBPBfWeRMOxJ6xgYAAMxBAB805jeBfT/5OLkLANzN+Z/hagIYXq64CzAqJ6Ek1/I9XkkM 5xLABJK7CfvXPoUjR5DjF4BnEsAb/Bp+0n5s2adP5cQ8cO7RtP+IO/666vgF4A4C+BSWY41D 7rJnVIz5N747Vr3msD0eckZIZjZ7BXjSvtxa5NwuhO4XRb+/TNo7JdIJ4AdLyHIv4ox/DH42 kuEsMsn+JXls9PqPySCLAL6ZueIj5C6zjNJ3R+a7rwztPb2eQJr+FcDrgPHQ7nvjAbYIYIYl dwGOG+2Dkv0zTt7Ev7t/SdDm7q/HyP/HgKMGtvxjE/zJ8TkcPtvm/SfZ7b/hs3E1C68hHBnn e8bPOKPLq/oV29Orx1OP7nbP9pcEW/7r1zlgIwfWmQHmK8zu8tRRffVIdk1UPnPd21wj8E7b 29m+mGs//rfX/n58/f//Z9vBcQL48Ub4dSh3AUYgkHLYy+PshfZ/L/uj/Qhz6wzP7x/hn80D QxYBzOnkLqOZa4mXROG4hPHTHymWcfZbxivJnUfc2r74/b7rj7I3g4UuHCGAT5f2a1juMsvI BBZrH7KMc9Q4fs/dy1w9Jr3zgZkIYN4idxnf/W/7vvXt37Wf2lHJkXH13fEj2z57BdizPb0y 7N/O29sTmJsA/o1fEv3WaNkyzGXeEettK3tsnxRt/xhz/D6b15O1Y2esUfe9hc1GCFkEcIg9 L21yFyDNWRnsDfQs0vbRiKELfJcAvsj4n6zLXTjrOLru2Hk3KkQIPM9ZR/Szl5cLXWAvAfxF 3/ol5M0xzHv8PukZMo5z08jYG3mbPDWDv/+upj1v87kXN2of07EEJxytteaGUCn//wWQvB0A ADhiTwD3MSxreeKxMHph/WMnAQDAZ47P7gJ3EsAAAABEEMAAAPC2dmFzf7vtA2MSwAAAAEQQ wAAA8Ia1uV9gfC6DBABAtLMWLffneV57ZPEM3yKAAQCIdjxH20fYfjTpC9/1kCXQ7fWm4M5R Z+xh5GDkYORg5MAspg/g5bBcLrLsEAUAAGDNxAHcpu9yiwwGAABgjbNAAwAAEMFJsP5l3hjj ByMHIwcjB4wcns0MMAAAABGiZ4Db7w8DAADwbBPPAPenvOpPiwUAAACLh+Si9AUAAGCbaAQA ACCCk2ABAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQADAAAQQQD/opRSSrEd 6EdF68j4McaSR5GRw/7R4jUHI4erR8s49+EZI2eWVyEB/MsmrrXWWh2o9KOi1Y+QPePHGOOz UWHkZI4HrzkYOVw3WvaPqCPjxFjKGTlzvQoJ4F828XKLA5Vzx48xZoQYORzRjgEjh88YOfT7 97pxYiyljZy5XoUEMKw6fqiT7KxfGABwnN9HXDdy5hpdP3Yq7CdpgKv1n3N7zWHb2gyJkQN8 y8jvmQUwTH8YY7TwJP3IMaLYtjZCjBzgfuO/8lgCDdMfxow8cvpvttgyAMDzzPKeWQDv+vo1 DuMj48cYy3xVabW3GzkcH11GDkYOI48TYynNXO+ZDcS3dx5p42H7MH53/BhjyWNpbb8bOfT7 ur3FyMHI4YoRsj1azhonxlLCyJnrPbPhCAAAQARLoAEAAIgggAEAAIgggAEAAIgggAEAAIgg gAEAAIgggAEAAIgggAEAAIgggAEAAIgggAEAAIgggAEAAIgggAEAAIgggAEAAIgggAEAAIgg gAEAAIjwPyCgxDyBQftoAAAAAElFTkSuQmCC --qDbXVdCdHGoSgWSk--