http://ticki.github.io/blog/horrible/

Some worthwhile insights into what makes a good collection type.

On 9/13/2016 4:47 PM, Walter Bright wrote:
> http://ticki.github.io/blog/horrible/
>
> Some worthwhile insights into what makes a good collection type.

https://news.ycombinator.com/item?id=12488233

Of particular interest is the advocacy of collision attack resistance. Is anyone interested in exploring this w.r.t. D's builtin hashes?

https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcollections_is_absolutely_horrible/

Of interest are the comments by the implementer of the hash.

On Wednesday, 14 September 2016 at 00:36:39 UTC, Walter Bright wrote:
> On 9/13/2016 4:47 PM, Walter Bright wrote:
>> http://ticki.github.io/blog/horrible/
>>
>> Some worthwhile insights into what makes a good collection type.
>
> https://news.ycombinator.com/item?id=12488233
>
> Of particular interest is the advocacy of collision attack resistance. Is anyone interested in exploring this w.r.t. D's builtin hashes?
>
> https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcollections_is_absolutely_horrible/
>
> Of interest are the comments by the implementer of the hash.

There's a benchmark of languages builtin hashmaps here:

http://vaskir.blogspot.fr/2016/05/hash-maps-rust-vs-f.html

It includes D and Rust. The author found that D wins for the lookups but was a bit behind for the insertions (due to GC maybe ?).

Rust results didn't seem that bad, despite of the cryptographic hash function it uses.

On Wednesday, 14 September 2016 at 00:36:39 UTC, Walter Bright wrote:
> On 9/13/2016 4:47 PM, Walter Bright wrote:
>> http://ticki.github.io/blog/horrible/
>>
>> Some worthwhile insights into what makes a good collection type.
>
> https://news.ycombinator.com/item?id=12488233
>
> Of particular interest is the advocacy of collision attack resistance. Is anyone interested in exploring this w.r.t. D's builtin hashes?
>
> https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcollections_is_absolutely_horrible/
>
> Of interest are the comments by the implementer of the hash.

Link to code?

On Wednesday, 14 September 2016 at 00:36:39 UTC, Walter Bright wrote:
> Of particular interest is the advocacy of collision attack resistance. Is anyone interested in exploring this w.r.t. D's builtin hashes?

Perl's approach is probably good enough https://issues.dlang.org/show_bug.cgi?id=14414
Reversibility of the hash looks irrelevant for dos attack.

On Wednesday, 14 September 2016 at 11:59:13 UTC, Kagamin wrote:
> On Wednesday, 14 September 2016 at 00:36:39 UTC, Walter Bright wrote:
>> Of particular interest is the advocacy of collision attack resistance. Is anyone interested in exploring this w.r.t. D's builtin hashes?
>
> Perl's approach is probably good enough https://issues.dlang.org/show_bug.cgi?id=14414
> Reversibility of the hash looks irrelevant for dos attack.

What do you mean by that? It's the basis of DoS attack against hashtables: being able to find many inputs with the same hash. What perl does isn't good IMHO because their solution is not the default behaviour and the security effect of changing the seed isn't made obvious to the programmer.

While I can understand prefering speed over security as default (although history shows that if it's not the default it's not used) I would rather have a security flag to change the algorithm at compile-time for a more secure one. Most programmers won't see the point of changing seed and we can definitely take advantage of templates here.

Also I'm not sure in our use-case fastest necessarily means less secure, there should be some benchmarking at work.

On Wednesday, 14 September 2016 at 03:49:35 UTC, Basile B. wrote:
> On Wednesday, 14 September 2016 at 00:36:39 UTC, Walter Bright wrote:
>> On 9/13/2016 4:47 PM, Walter Bright wrote:
>>> http://ticki.github.io/blog/horrible/
>>>
>>> Some worthwhile insights into what makes a good collection type.
>>
>> https://news.ycombinator.com/item?id=12488233
>>
>> Of particular interest is the advocacy of collision attack resistance. Is anyone interested in exploring this w.r.t. D's builtin hashes?
>>
>> https://www.reddit.com/r/rust/comments/52grcl/rusts_stdcollections_is_absolutely_horrible/
>>
>> Of interest are the comments by the implementer of the hash.
>
> There's a benchmark of languages builtin hashmaps here:
>
> http://vaskir.blogspot.fr/2016/05/hash-maps-rust-vs-f.html
>
> It includes D and Rust. The author found that D wins for the lookups but was a bit behind for the insertions (due to GC maybe ?).
>
> Rust results didn't seem that bad, despite of the cryptographic hash function it uses.

just ignore...get on ignoring.
tea vs coffee...cough

On Wednesday, 14 September 2016 at 16:53:03 UTC, cym13 wrote:
> What do you mean by that? It's the basis of DoS attack against hashtables: being able to find many inputs with the same hash.

That's a collision attack, not a preimage attack.

> Most programmers won't see the point of changing seed and we can definitely take advantage of templates here.

The seed is supposed to be changed by infrastructure, e.g. vibe.d, not by user code. Also it's only for server code.

On Thursday, 15 September 2016 at 08:02:44 UTC, Kagamin wrote:
> On Wednesday, 14 September 2016 at 16:53:03 UTC, cym13 wrote:
>> What do you mean by that? It's the basis of DoS attack against hashtables: being able to find many inputs with the same hash.
>
> That's a collision attack, not a preimage attack.
>
>> Most programmers won't see the point of changing seed and we can definitely take advantage of templates here.
>
> The seed is supposed to be changed by infrastructure, e.g. vibe.d, not by user code. Also it's only for server code.

DoS by collision attack are a form of preimage. The idea is to generate intentional collisions to force heavy computations on serveur side. It only works if finding collisions many collisions for the same hash is cheap which is directly linked to the ability to find a value that gives a given hash (although it doesn't have to be easy to find any hash).

On Thursday, 15 September 2016 at 10:13:47 UTC, cym13 wrote:
> DoS by collision attack are a form of preimage. The idea is to generate intentional collisions to force heavy computations on serveur side. It only works if finding collisions many collisions for the same hash is cheap which is directly linked to the ability to find a value that gives a given hash (although it doesn't have to be easy to find any hash).

You still need to decide which seed you compute collisions for.