The Power of Evil Choices in Bloom Filters - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2014

The Power of Evil Choices in Bloom Filters

Résumé

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.

Domaines

Informatique
Fichier principal
Vignette du fichier
RR-8627.pdf (800.16 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-01082158 , version 2

Citer

Thomas Gerbet, Amrit Kumar, Cédric Lauradoux. The Power of Evil Choices in Bloom Filters. [Research Report] RR-8627, INRIA Grenoble. 2014. ⟨hal-01082158v2⟩
684 Consultations
2250 Téléchargements

Partager

Gmail Facebook X LinkedIn More