📖
The Power of Evil Choices in Bloom Filters
Thomas Gerbet, Amrit Kumar, Cédric Lauradoux

The Power of Evil Choices in Bloom Filters

Science & Mathematics Published 2014 Verification Pending

Overview & Synopsis

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.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title The Power of Evil Choices in Bloom Filters
Author / Organization Thomas Gerbet, Amrit Kumar, Cédric Lauradoux
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2014
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-248724
Original Source Link Visit Source Page on hal.science »