Floating Point Keys in JavaScript:

In this article we take a look at how JavaScript handles hash keys that are floating point numbers. JavaScript differs from other languages in that it provides two associative data structures that handle floating point keys differently. Normal objects are the most common associative data structure in JavaScript: internally objects convert all keys to character strings. In the case of floating point numbers this seems to be a convenient solution because it doesn’t require a special hash function for floats, but it means that the float-to-string conversion must be defined very carefully.

In addition, modern versions of JavaScript have a dedicated associative data structure called Map which doesn’t convert all keys to strings first. But Map still treats floating point keys differently than all the other hash tables we have seen so far: it defines a custom comparison operator for floating point numbers that differs from == and ===. One important property of this comparison operator is that it avoids the problems with NaN keys we saw with other programming languages, but at the cost of introducing yet another notion of equality to the language.

Let’s take a look at Object and Map hashing in turn.

Read More »

Advertisements

Floating Point Keys in Go: How to Make Hash Functions Unpredictable

The Go Programming Language has a built-in map datatype that is implemented using hash tables. The only types that can be used as map keys are those for which the language defines an equality operator ==; this includes primitive types like Booleans, strings, numbers, and pointers, but also composite types like arrays and structures. For all these types Go automatically generates a suitable hash function. Maps are not extensible, however: if you need a hash table that supports custom comparison or hash algorithms you have to write your own.

Floating point numbers can be used as map keys, and since Go follows the normal conventions for comparison, so maps treat all NaN keys as distinct since NaN ≠ NaN. As a consequence NaN keys can be inserted into maps but are unretrievable; in fact, any number of NaN keys can be inserted, and because they are all distinct it’s possible to end up with a map in which every entry is unretrievable. Normally this would be merely a curiosity, an interesting side effect of the quirky semantics of floating point numbers. But this curiosity can lead to an exploitable performance issue if the hash function being used maps every NaN to a single hash code. In this case all the NaN keys collide in the hash table and the runtime cost of inserting n of them drops to O(n2), down from the O(n) we would expect for uniformly distributed hash codes.

Overloading servers by causing hash table collisions has become a a real security threat in recent years. Many languages and hashing algorithms were found to be susceptible to these so-called hash-flooding attacks and had to be updated. In the following I will discuss how Go prevents hash-flooding attacks, in particular for the special of case floating point keys.

Read More »