Nearly one month ago I have written some thoughts on how the HashDoS problem presented at the 28C3 or other code defects could perhaps be fixed temporarily without interaction of vendors.
Now it's time to deeper investigate the complexity attack and have at look at the sources. I quitely assume that java.util.HashMap and java.util.Hashtable are the most common used data structures of Java which are affected by this attack, so this article will only focus the code behind these types.
A brief kick start to hash functions and indexed data structures
Hash indexed data structures are very popular because of their simple usage and benefits:
- no bothering with index tables to find the right position of desired data
- access to data by using keywords instead of index numbers
- nearly constant time for add or delete operations
To achieve these benefits hash indexed data structures follow a clever idea on how to index data. The index is computed by hashing a keyword which is associated with data behind it. Consider the following example for an easy code-like example:
myHashIndexedDataStructure[hash(keyword)] = particular data
Sounds perfect, but it has one major drawback: the used hash functions are in most cases not cryptograhic ones.
According to Wikipedia the only mandatory characteristic for a function to call itself hash function is to
"map[s] large data sets of variable length, called keys, to smaller data sets of a fixed length"
In contrast to call itself a cryptographic hash function (once again, a definition taken from Wikipedia) it has to fulfill further, even much stronger, requirements:
Read the rest of the article at the following URL: