[en] Classical Bloom filters may be used to elegantly check if an element e belongs to a set S, and, if not, to add e to S. They do not store any data and only provide boolean answers regarding the membership of a given element in the set, with some probability of false positive answers. Bloom filters are often used in caching system to check that some requested data actually exist before doing a costly lookup to retrieve them. However, security issues may arise for some other applications where an active attacker is able to inject data crafted to degrade the filters’ algorithmic properties, resulting for instance in a Denial of Service (DoS) situation. This leads us to the concept of hardened Bloom filters, combining classical Bloom filters with cryptographic hash functions and secret nonces. We show how this approach is successfully used in the TrueNyms unobservability system and protects it against replay attacks.
Disciplines :
Computer science
Author, co-author :
Bernard, Nicolas ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Leprévost, Franck ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Language :
English
Title :
Hardened Bloom Filters, with an Application to Unobservability
Publication date :
February 2013
Journal title :
Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
ISSN :
2083-3628
Publisher :
Uniwersytetu Marii Curie Sklodowskies, Lublin, Poland