• Gary Willoughby (2/2) Aug 09 2014 What hashing algorithm is used for the D implementation of
• Damian Day (4/6) Aug 09 2014 https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aa...
• Mike Wey (7/9) Aug 09 2014 Paul Hsieh's SuperFastHash:
• Gary Willoughby (2/4) Aug 09 2014 Where is this implemented?
• Mike Wey (4/8) Aug 09 2014 https://github.com/D-Programming-Language/druntime/blob/master/src/rt/ut...
• "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (2/10) Aug 09 2014 Isn't SuperFastHash vulnerable to collision attacks?
• bearophile (10/11) Aug 14 2014 D AAs used to be not vulnerable to collision attacks because they
• "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (9/19) Aug 14 2014 IMO this is a _very_ dangerous stance. These kinds of attacks
• H. S. Teoh via Digitalmars-d-learn (6/27) Aug 14 2014 [...]
• safety0ff (27/30) Aug 14 2014 Slight corrections:
• Sean Kelly (3/3) Aug 14 2014 Superfast. Though Murmur has gotten good enough that I'm tempted

"Gary Willoughby" <dev nomad.so> writes:

What hashing algorithm is used for the D implementation of 
associative arrays? Where in the D source does the AA code live?

"Damian Day" <damianroyday gmail.com> writes:

On Saturday, 9 August 2014 at 09:33:12 UTC, Gary Willoughby wrote:
 What hashing algorithm is used for the D implementation of 
 associative arrays? Where in the D source does the AA code live?


https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d

I think it uses the objects generic TypeInfo getHash function - 
see line 170.

Mike Wey <mike-wey example.com> writes:

On 08/09/2014 11:33 AM, Gary Willoughby wrote:
 What hashing algorithm is used for the D implementation of associative
 arrays? Where in the D source does the AA code live?

Paul Hsieh's SuperFastHash:
http://www.azillionmonkeys.com/qed/hash.html

The source is here: 
https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d

-- 
Mike Wey

"Gary Willoughby" <dev nomad.so> writes:

On Saturday, 9 August 2014 at 10:28:02 UTC, Mike Wey wrote:
 Paul Hsieh's SuperFastHash:
 http://www.azillionmonkeys.com/qed/hash.html

Where is this implemented?

Mike Wey <mike-wey example.com> writes:

On 08/09/2014 01:43 PM, Gary Willoughby wrote:
 On Saturday, 9 August 2014 at 10:28:02 UTC, Mike Wey wrote:
 Paul Hsieh's SuperFastHash:
 http://www.azillionmonkeys.com/qed/hash.html

 Where is this implemented?

https://github.com/D-Programming-Language/druntime/blob/master/src/rt/util/hash.d

-- 
Mike Wey

"Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:

On Saturday, 9 August 2014 at 10:28:02 UTC, Mike Wey wrote:
 On 08/09/2014 11:33 AM, Gary Willoughby wrote:
 What hashing algorithm is used for the D implementation of 
 associative
 arrays? Where in the D source does the AA code live?

 Paul Hsieh's SuperFastHash:
 http://www.azillionmonkeys.com/qed/hash.html

 The source is here: 
 https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d

Isn't SuperFastHash vulnerable to collision attacks?

"bearophile" <bearophileHUGS lycos.com> writes:

Marc Schütz:

 Isn't SuperFastHash vulnerable to collision attacks?

D AAs used to be not vulnerable to collision attacks because they 
resolved collisions building a red-black tree for each bucket. 
Later buckets became linked lists for speed, leading to the 
current sensitivity to collision attacks. I think D is not yet in 
the stage of its development where it starts to care a lot about 
attacks. Currently D programs are able to "attack themselves" 
just fine :-) But as usual patches are (slowly) welcome.

Bye,
bearophile

"Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:

On Thursday, 14 August 2014 at 13:10:58 UTC, bearophile wrote:
 Marc Schütz:

 Isn't SuperFastHash vulnerable to collision attacks?

 D AAs used to be not vulnerable to collision attacks because 
 they resolved collisions building a red-black tree for each 
 bucket. Later buckets became linked lists for speed, leading to 
 the current sensitivity to collision attacks. I think D is not 
 yet in the stage of its development where it starts to care a 
 lot about attacks.

IMO this is a _very_ dangerous stance. These kinds of attacks 
became well known in 2011, when it turned out that almost all of 
the commonly used languages and web frameworks were vulnerable:
http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html

It would be nice if D behaved correctly before any actual attack 
becomes known.

Besides, AAs are probably already exposed to outside attackers in 
vibe.d (didn't check though).

 Currently D programs are able to "attack themselves" just fine 
 :-) But as usual patches are (slowly) welcome.

"H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:

On Thu, Aug 14, 2014 at 04:32:24PM +0000, via Digitalmars-d-learn wrote:
 On Thursday, 14 August 2014 at 13:10:58 UTC, bearophile wrote:
Marc Schütz:

Isn't SuperFastHash vulnerable to collision attacks?

D AAs used to be not vulnerable to collision attacks because they
resolved collisions building a red-black tree for each bucket. Later
buckets became linked lists for speed, leading to the current
sensitivity to collision attacks. I think D is not yet in the stage
of its development where it starts to care a lot about attacks.

 
 IMO this is a _very_ dangerous stance. These kinds of attacks became
 well known in 2011, when it turned out that almost all of the commonly
 used languages and web frameworks were vulnerable:
 http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html
 
 It would be nice if D behaved correctly before any actual attack
 becomes known.
 
 Besides, AAs are probably already exposed to outside attackers in
 vibe.d (didn't check though).

[...]

PR's to fix this issue would be greatly appreciated!


T

-- 
Nobody is perfect.  I am Nobody. -- pepoluan, GKC forum

"safety0ff" <safety0ff.dev gmail.com> writes:

On Thursday, 14 August 2014 at 13:10:58 UTC, bearophile wrote:
 D AAs used to be not vulnerable to collision attacks because 
 they resolved collisions building a red-black tree for each 
 bucket. Later buckets became linked lists for speed,

Slight corrections:
It was a effectively a randomized BST, it used the hash value + 
comparison function to place the elements in the tree.
E.g. The AA's node comparison function might be:

    if (hash == other.hash)
       return value.opCmp(other.value);
    else if (hash < other.hash)
       return -1;
    return 1;

The hash function has a significant influence on how balanced the 
BST will be.
Insertion and removal order also have performance influence since 
rebalancing was only done when growing the AA.
It had no performance guarantees.

I believe it was removed to reduce memory consumption, see the 
Mar 19 2010 cluster of commits by Walter Bright to aaA.d.
Since GC rounds up allocations to powers of two for small 
objects, the additional pointer doubles the allocation size per 
node.

A template library based AA implementation should be able to 
handily outperform built-in AAs and provide guarantees.
Furthermore, improved memory management could be a significant 
win.

Fun fact:
The AA implementation within DMD still uses the "randomized" BST 
though the hash functions are very rudimentary.

"Sean Kelly" <sean invisibleduck.org> writes:

Superfast. Though Murmur has gotten good enough that I'm tempted 
to switch.  At the time, Murmur didn't even have a license so it 
wasn't an option.