<div dir="ltr"><div><div><div><div><div><div>FYI,</div><div><br></div>I pushed the changes:<br><br></div>- first, the linked list and hash table were made generic (I needed a hash table to manage PIDs)</div><div><br></div>The the code was forked before 8e047dd53da900445dda569041ac602740d66de0 so some of that didn't get copied over (I noticed it while merging this week and testing was already painful enough); looking through it I think the always-circular change could be re-merged but as part of code explicitly allocating initializing and freeing the heaps and lists - to do dynamic sizing of the heap we'll need this anyway.<br></div><div><br></div>- the state contain 499 slots</div><div><br></div><div>There's a rule of thumb that says hash tables should be ~50% full (true?) but I've seen pluto with 1000 entries so we might need that dynamic resize code; hopefully I've structured things to be friendly to that change; later<br><br></div>- for icookies it uses:</div><div><br></div><div> * 251 is a prime close to 256 (so like <<8).<br> for (unsigned j = 0; j < COOKIE_SIZE; j++) {<br> hash = hash * 251 + icookie[j];<br> }<br><br></div>- and for icookie+rcookie it uses:<br><br> * 251 is a prime close to 256 aka <<8. 65521 is a prime<br> * close to 65536 aka <<16.<br> for (unsigned j = 0; j < COOKIE_SIZE; j++) {<br> hash = hash * 65521 + icookie[j] * 251 + rcookie[j];<br> }<br><div><br></div><div>- hopefully 499, 251 and 65521 are all primes</div><div><br></div><div>- like the comments also say, there's no real rationale for doing this.<br></div><br><div>- there's also an ordered list available</div><div><br></div><div>Andrew</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On 18 October 2017 at 16:40, Andrew Cagney <span dir="ltr"><<a href="mailto:andrew.cagney@gmail.com" target="_blank">andrew.cagney@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="">On 18 October 2017 at 15:51, D. Hugh Redelmeier <span dir="ltr"><<a href="mailto:hugh@mimosa.com" target="_blank">hugh@mimosa.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">| From: Andrew Cagney <<a href="mailto:andrew.cagney@gmail.com" target="_blank">andrew.cagney@gmail.com</a>><br>
| To: Libreswan Development List <<a href="mailto:swan-dev@lists.libreswan.org" target="_blank">swan-dev@lists.libreswan.org</a>><br>
<span><br>
| - icookie+zero-cookie (we probably shouldn't include the zero-cookie in the<br>
| hash but it should do no harm :-)<br>
| - icookie+rcookie<br>
|<br>
| these use:<br>
|<br>
| for (j = 0; j < COOKIE_SIZE; j++)<br>
| i = i * 407 + icookie[j] + rcookie[j];<br>
|<br>
| where 407 isn't prime (does anyone know where 407 came from? if not I'll<br>
| change that to a prime 521 which I'm choosing randomly) and I'll change the<br>
| math to:<br>
|<br>
| i * 521 + icookie << 8 + rcookie<br>
|<br>
| So that we don't allow the cookies to cancel out (I could reply with<br>
| rcookie = 255 - icookie making the hash very non-random),<br>
<br>
</span>I'm surely responsible for the hash. I'm sure that I had a reason for<br>
407 but if their is no comment, that reason is lost. I think that I<br>
wanted it to be in the middle of the range (256,512).<br>
<br></blockquote><div><br></div></span><div>So if I concatenate the two bytes, something between 32k and 64k would be better.<br></div><span class=""><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Faster hashing could be done by treating the cookies as a sequence of<br>
uint32_t values. I don't think that there has to be an alignment<br>
problem since the cookies are at the start of a packet.<br>
<br></blockquote><div> </div></span><div>That might be interesting. But from my pov, later.<br></div><span class=""><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
How should one combine the values? A commutative operation (^ or + or<br>
+) hashes permutations to the same value, which seems questionable.<br>
<br></blockquote><div><br></div></span><div>Ideally it should be viewed as a very large integer.</div><span class=""><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
To prevent some attacks, it might be good to mix in something private.<br>
That private thing ought to be determined once per run of pluto. (If<br>
it changes in the middle of a run, the has table would need to be<br>
rehashed. This is pointless if an attacker could deduce the private<br>
thing, say by a timing attack.<br>
<br><br></blockquote></span><div>I don't think it is worth it. Our half is always random so only when they carefully construct some strange sequence of cookies resulting in a single hash things will get slow. And if that happens the code requiring an initial cookie exchange would kick in.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>Andrew</div><div><br></div></font></span></div><br></div></div>
</blockquote></div><br></div>