[erlang-questions] Efficient Denial of Service Attacks on Web Application Platforms and it's effects in Erlang?

[Ulf Wiger]

On 30 Dec 2011, at 14:04, Jesper Louis Andersen wrote:

> The most worrisome place in Erlang is if you are using ETS in a mode where the underlying runtime uses a Hash, i.e, set or bag semantics. The ordered semantics use a tree and are thus not vulnerable - and the hash may not be either, but I don't know the details of that. There is a reason Dan J. Bernstein went for using critbit/radix/patricia trees in most of his software due to this. It is kind of a timing attack in a similar form.

Yes, ordered_set tables are nice, but as far as I can tell, the erlang:phash2/2 function gives a very even spread for strings. I did run some experiments, generating all possible strings of length 3, 4, 5, and counting the hash collisions for a given hash range, and the spread was very even. With a limited alphabet, I generated strings up to length 9, with similar results. Of course, trying a large number of lengths and hash ranges takes more time than I am willing to spend on this.

Also, ets tables use linear hashing. If the hash function doesn't manage to redistribute values after a resize, it would be problematic, but the hash function was redesigned exactly for this purpose, after Mats Cronquist had encountered a situation, many years ago, where tens of thousand keys ended up in the same bucket.

Here is the program I used:

-module(hsh).
-export([run/2]).

run(L, R) ->
    lists:sort(dict:to_list(run_(L, [], dict:new(), R))).

cs() ->
    "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".

run_(1, S, D0, R) ->
    lists:foldl(fun(C, D) ->
			log(S ++ [C], D, R)
		end, D0, cs());
run_(L, S, D0, R) when L > 1 ->
    lists:foldl(fun(C, D) ->
			run_(L-1, S++[C], D, R)
		end, D0, cs()).

log(S, D, R) ->
    dict:update_counter(erlang:phash2(S, R), 1, D).


BR,
Ulf W