Re: Critque of Rust's collection types

2016-09-15 Thread sarn via Digitalmars-d

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


Re: Critque of Rust's collection types

2016-09-15 Thread Kagamin via Digitalmars-d

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.


Re: Critque of Rust's collection types

2016-09-15 Thread cym13 via Digitalmars-d

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).


Re: Critque of Rust's collection types

2016-09-15 Thread Kagamin via Digitalmars-d

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.


Re: Critque of Rust's collection types

2016-09-14 Thread Klmp via Digitalmars-d

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



Re: Critque of Rust's collection types

2016-09-14 Thread cym13 via Digitalmars-d

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.


Re: Critque of Rust's collection types

2016-09-14 Thread Kagamin via Digitalmars-d
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.


Re: Critque of Rust's collection types

2016-09-14 Thread NVolcz via Digitalmars-d
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?


Re: Critque of Rust's collection types

2016-09-13 Thread Basile B. via Digitalmars-d
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.


Re: Critque of Rust's collection types

2016-09-13 Thread Walter Bright via Digitalmars-d

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.