The Power of Evil Choices in Bloom Filters

Thomas Gerbet 1 Amrit Kumar 2 Cédric Lauradoux 2
2 PRIVATICS - Privacy Models, Architectures and Tools for the Information Society
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
Abstract : A Bloom filter is a probabilistic hash-based data structure extensively used in software including online security applications. This paper raises the following important question: Are Bloom filters correctly designed in a security context? The answer is no and the reasons are multiple: bad choices of parameters, lack of adversary models and misused hash functions. Indeed, developers truncate cryptographic digests without a second thought on the security implications. This work constructs adversary models for Bloom filters and illustrates attacks on three applications, namely Scrapy web spider, Bitly Dablooms spam filter and Squid cache proxy. As a general impact, filters are forced to systematically exhibit worst-case behavior. One of the reasons being that Bloom filter parameters are always computed in the average case. We compute the worst-case parameters in adversarial settings, show how to securely and efficiently use cryptographic hash functions and propose several other countermeasures to mitigate our attacks.
Type de document :
Communication dans un congrès
Annual IEEE/IFIP International Conference on Dependable Systems and Networks - DSN 2015, Jun 2015, Rio De Janeiro, Brazil. 2015, 〈http://2015.dsn.org/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01199150
Contributeur : Cédric Lauradoux <>
Soumis le : mardi 15 septembre 2015 - 08:03:36
Dernière modification le : jeudi 19 novembre 2015 - 01:20:49

Identifiants

  • HAL Id : hal-01199150, version 1

Collections

Citation

Thomas Gerbet, Amrit Kumar, Cédric Lauradoux. The Power of Evil Choices in Bloom Filters. Annual IEEE/IFIP International Conference on Dependable Systems and Networks - DSN 2015, Jun 2015, Rio De Janeiro, Brazil. 2015, 〈http://2015.dsn.org/〉. 〈hal-01199150〉

Partager

Métriques

Consultations de la notice

151