3 ms·

>The Go language designers noticed that people were relying on the fact that keys were normally stored in the order they were added in, so they randomized the o

>The Go language designers noticed that people were relying on the fact that keys were normally stored in the order they were added in, so they randomized the order in which the keys are iterated over. Um, I'm just a first-year CS student here, but isn't that a core part of how hash tables work? They can so efficiently store and lookup data because they essentially store contents in a list with the indices as the hashes of the content. As such, one can never reliably predict the order of the keys in a hash table, by design. That's not a feature of Go.

ImJasonH 12y ago
True, but since it works this way in practice in other languages most of the time, particularly for small maps, people come to depend on it, then get surprised when it isn't the case. Might as well keep people aware that key ordering can't be relied upon.
Scaevolus 12y ago
Yes, but there's more going on. Simple hash tables use a fixed hash function-- the order of keys is unpredictable, but consistent between runs of your program. This allows algorithmic denial of service attacks-- if you have a web server that puts querystring parameters into a hash table, and you know what bucket a key will hash to, you can force collisions and O(n^2) runtime complexity. Hash randomization avoids this attack. Go bug: https://code.google.com/p/go/issues/detail?id=2630 https://code.google.com/p/go/issues/detail?id=2630
- rurban 12y ago
  Hash randomization avoids the O(n) attack on collisions if the randomized seed is not detectable. But if you don't sort the output of keys, rather depend on the random seed to iterate over the keys, the seed provides no protection anymore for the O(n) attack. It is very exposed and a minor security risc for DDoS attacks. Perl is bit better than Go here, but not as good as Python. The real problem is exposing too much information of the seed by the ordering of the keys, and not preventing the algorithmic explosion on collision attacks. Such languages should really rework their collision handling strategy and not rely on randomized seeds (which can be brute forced or easily guessed such as here) or even worse, by strengthening the hash function. TL;DR: The poster has no idea about hash tables, what Go did, why they did it, what the problem is and what should be improved. PS: His cygwin git blog post is also completely wrong. He uses msysgit with some msys openssl version and complains about cert warnings. Of course, he is not using cygwin.
- takeda 12y ago
  Python solves that by generating salt on start that is used for hash generation. This way it is still extremely hard to commence such attack and at the same time not lose performance due to randomizing elements on each iteration. BTW: I'm not convinced this randomization even solves this vulnerability. The patch referenced doesn't look like the one that implemented this behavior. I suspect we are mixing up two different behaviors.
rdtsc 12y ago
If a map is implemented as a hash table then yes, that is a property. A map could also be implemented as a balanced tree, then sorted iteration order and range queries would be a feature to expose.

ImJasonH 12y ago

True, but since it works this way in practice in other languages most of the time, particularly for small maps, people come to depend on it, then get surprised when it isn't the case. Might as well keep people aware that key ordering can't be relied upon.

Scaevolus 12y ago

Yes, but there's more going on. Simple hash tables use a fixed hash function-- the order of keys is unpredictable, but consistent between runs of your program. This allows algorithmic denial of service attacks-- if you have a web server that puts querystring parameters into a hash table, and you know what bucket a key will hash to, you can force collisions and O(n^2) runtime complexity. Hash randomization avoids this attack. Go bug: https://code.google.com/p/go/issues/detail?id=2630 https://code.google.com/p/go/issues/detail?id=2630

rurban 12y ago
Hash randomization avoids the O(n) attack on collisions if the randomized seed is not detectable. But if you don't sort the output of keys, rather depend on the random seed to iterate over the keys, the seed provides no protection anymore for the O(n) attack. It is very exposed and a minor security risc for DDoS attacks. Perl is bit better than Go here, but not as good as Python. The real problem is exposing too much information of the seed by the ordering of the keys, and not preventing the algorithmic explosion on collision attacks. Such languages should really rework their collision handling strategy and not rely on randomized seeds (which can be brute forced or easily guessed such as here) or even worse, by strengthening the hash function. TL;DR: The poster has no idea about hash tables, what Go did, why they did it, what the problem is and what should be improved. PS: His cygwin git blog post is also completely wrong. He uses msysgit with some msys openssl version and complains about cert warnings. Of course, he is not using cygwin.
takeda 12y ago
Python solves that by generating salt on start that is used for hash generation. This way it is still extremely hard to commence such attack and at the same time not lose performance due to randomizing elements on each iteration. BTW: I'm not convinced this randomization even solves this vulnerability. The patch referenced doesn't look like the one that implemented this behavior. I suspect we are mixing up two different behaviors.

rdtsc 12y ago

If a map is implemented as a hash table then yes, that is a property. A map could also be implemented as a balanced tree, then sorted iteration order and range queries would be a feature to expose.