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 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.
Type de document :
Rapport
[Research Report] RR-8627, INRIA Grenoble. 2014
Liste complète des métadonnées

Littérature citée [45 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01082158
Contributeur : Amrit Kumar <>
Soumis le : mardi 24 février 2015 - 14:15:29
Dernière modification le : lundi 30 avril 2018 - 15:02:01
Document(s) archivé(s) le : jeudi 28 mai 2015 - 16:45:50

Fichier

RR-8627.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01082158, version 2

Collections

Citation

Thomas Gerbet, Amrit Kumar, Cédric Lauradoux. The Power of Evil Choices in Bloom Filters. [Research Report] RR-8627, INRIA Grenoble. 2014. 〈hal-01082158v2〉

Partager

Métriques

Consultations de la notice

511

Téléchargements de fichiers

1300