www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Critque of Rust's collection types

reply Walter Bright <newshound2 digitalmars.com> writes:
http://ticki.github.io/blog/horrible/

Some worthwhile insights into what makes a good collection type.
Sep 13 2016
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Sep 13 2016
next sibling parent reply Basile B. <b2.temp gmx.com> writes:
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.
Sep 13 2016
parent Klmp <klmp nowhere.de> writes:
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
Sep 14 2016
prev sibling next sibling parent NVolcz <niklas.volcz gmail.com> writes:
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?
Sep 14 2016
prev sibling parent reply Kagamin <spam here.lot> writes:
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.
Sep 14 2016
parent reply cym13 <cpicard openmailbox.org> writes:
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.
Sep 14 2016
parent reply Kagamin <spam here.lot> writes:
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.
Sep 15 2016
parent reply cym13 <cpicard openmailbox.org> writes:
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).
Sep 15 2016
next sibling parent Kagamin <spam here.lot> writes:
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.
Sep 15 2016
prev sibling parent sarn <sarn theartofmachinery.com> writes:
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).
As a counterexample, collision attacks on MD5 are cheap and practical, but preimage attacks are still theoretical. Self-plug, but I wrote a bit more about hash function attacks a little while back: https://theartofmachinery.com/2016/01/03/what_difference_can_order_make_when_hashing.html
Sep 15 2016