The Power of Evil Choices in Bloom Filters - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2014

The Power of Evil Choices in Bloom Filters

(1) , (2) , (2)


A Bloom filter is a probabilistic hash-based data structure extensively used insoftware products including online security applications. This paper raises the following importantquestion: Are Bloom filters correctly designed in a security context ? The answer is no andthe reasons are multiple: bad choices of parameters, lack of adversary models and misused hashfunctions. Indeed, developers truncate cryptographic digests without a second thought on thesecurity implications.This work constructs adversary models for Bloom filters and illustrates attacks on three applica-tions, namely Scrapy web spider, Bitly Dablooms spam filter and Squid cache proxy. Conse-quently, the adversary forces the filter to systematically exhibit worst-case behavior. One of thereasons being that Bloom filter parameters are always computed in the average case. We com-pute the worst-case parameters in adversarial settings, and show how to securely and efficientlyuse cryptographic hash functions. Finally, we propose several countermeasures to mitigate ourattacks.
Fichier principal
Vignette du fichier
RR-8627.pdf (800.16 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01082158 , version 1 (12-11-2014)
hal-01082158 , version 2 (24-02-2015)


  • HAL Id : hal-01082158 , version 2


Thomas Gerbet, Amrit Kumar, Cédric Lauradoux. The Power of Evil Choices in Bloom Filters. [Research Report] RR-8627, INRIA Grenoble. 2014. ⟨hal-01082158v2⟩
546 View
2065 Download


Gmail Facebook Twitter LinkedIn More