blog/assets/js/15966941.58ddb6d9.js

"use strict";(self.webpackChunkfi=self.webpackChunkfi||[]).push([[8326],{16721:(e,t,n)=>{n.r(t),n.d(t,{assets:()=>r,contentTitle:()=>o,default:()=>d,frontMatter:()=>a,metadata:()=>h,toc:()=>l});var s=n(85893),i=n(11151);const a={id:"mitigations",slug:"/hash-tables/breaking/mitigations",title:"Possible Mitigations",description:"Talking about the ways how to prevent the attacks on the hash table.\n",tags:["cpp","python","hash-tables"],last_update:{date:new Date("2023-11-28T00:00:00.000Z")}},o=void 0,h={id:"hash-tables/2023-11-28-breaking/mitigations",title:"Possible Mitigations",description:"Talking about the ways how to prevent the attacks on the hash table.\n",source:"@site/algorithms/12-hash-tables/2023-11-28-breaking/02-mitigations.md",sourceDirName:"12-hash-tables/2023-11-28-breaking",slug:"/hash-tables/breaking/mitigations",permalink:"/algorithms/hash-tables/breaking/mitigations",draft:!1,unlisted:!1,editUrl:"https://github.com/mfocko/blog/tree/main/algorithms/12-hash-tables/2023-11-28-breaking/02-mitigations.md",tags:[{label:"cpp",permalink:"/algorithms/tags/cpp"},{label:"python",permalink:"/algorithms/tags/python"},{label:"hash-tables",permalink:"/algorithms/tags/hash-tables"}],version:"current",lastUpdatedAt:1701129600,formattedLastUpdatedAt:"Nov 28, 2023",sidebarPosition:2,frontMatter:{id:"mitigations",slug:"/hash-tables/breaking/mitigations",title:"Possible Mitigations",description:"Talking about the ways how to prevent the attacks on the hash table.\n",tags:["cpp","python","hash-tables"],last_update:{date:"2023-11-28T00:00:00.000Z"}},sidebar:"autogeneratedBar",previous:{title:"Breaking Python",permalink:"/algorithms/hash-tables/breaking/python"}},r={},l=[{value:"Random seed",id:"random-seed",level:2},{value:"Better random seed",id:"better-random-seed",level:2},{value:"Adjusting the hash function",id:"adjusting-the-hash-function",level:2},{value:"Combining both",id:"combining-both",level:2},{value:"Fallback for extreme cases",id:"fallback-for-extreme-cases",level:2},{value:"References",id:"references",level:2}];function c(e){const t={a:"a",admonition:"admonition",code:"code",em:"em",h2:"h2",hr:"hr",li:"li",ol:"ol",p:"p",pre:"pre",strong:"strong",...(0,i.a)(),...e.components};return(0,s.jsxs)(s.Fragment,{children:[(0,s.jsx)(t.p,{children:"There are multiple ways the issues created above can be mitigated. Still we can\nonly make it better, we cannot guarantee the ideal time complexity\u2026"}),"\n",(0,s.jsxs)(t.p,{children:["For the sake of simplicity (and referencing an article by ",(0,s.jsx)(t.em,{children:"Neal Wu"})," on the same\ntopic; in references below) I will use the C++ to describe the mitigations."]}),"\n",(0,s.jsx)(t.h2,{id:"random-seed",children:"Random seed"}),"\n",(0,s.jsxs)(t.p,{children:["One of the options how to avoid this kind of an attack is to introduce a random\nseed to the hash. That way it is not that easy to choose the ",(0,s.jsx)(t.em,{children:"nasty"})," numbers."]}),"\n",(0,s.jsx)(t.pre,{children:(0,s.jsx)(t.code,{className:"language-cpp",children:"struct custom_hash {\n    size_t operator()(uint64_t x) const {\n        return x + 7529;\n    }\n};\n"})}),"\n",(0,s.jsx)(t.p,{children:"As you may have noticed, this is not very helpful, since it just shifts the\nissue by some number. Better option is to use a shift from random number\ngenerator:"}),"\n",(0,s.jsx)(t.pre,{children:(0,s.jsx)(t.code,{className:"language-cpp",children:"struct custom_hash {\n    size_t operator()(uint64_t x) const {\n        static const uint64_t FIXED_RANDOM =\n            chrono::steady_clock::now().time_since_epoch().count();\n        return x + FIXED_RANDOM;\n    }\n};\n"})}),"\n",(0,s.jsx)(t.p,{children:"In this case the hash is using a high-precision clock to shift the number, which\nis much harder to break."}),"\n",(0,s.jsx)(t.h2,{id:"better-random-seed",children:"Better random seed"}),"\n",(0,s.jsxs)(t.p,{children:["Building on the previous solution, we can do some ",(0,s.jsx)(t.em,{children:"bit magic"})," instead of the\nshifting:"]}),"\n",(0,s.jsx)(t.pre,{children:(0,s.jsx)(t.code,{className:"lang