Welcome to the resource topic for 2024/1312
Title:
Probabilistic Data Structures in the Wild: A Security Analysis of Redis
Authors: Mia Filić, Jonas Hofmann, Sam A. Markelon, Kenneth G. Paterson, Anupama Unnikrishnan
Abstract:Redis (Remote Dictionary Server) is a general purpose, in-memory database that supports a rich array of functionality, including various Probabilistic Data Structures (PDS), such as Bloom filters, Cuckoo filters, as well as cardinality and frequency estimators.
These PDS typically perform well in the average case. However, given that Redis is intended to be used across a diverse array of applications, it is crucial to evaluate how these PDS perform under worst-case scenarios, i.e., when faced with adversarial inputs. We offer a comprehensive analysis to address this question.
We begin by carefully documenting the different PDS implementations in Redis, explaining how they deviate from those PDS as described in the literature.
Then we show that these deviations enable a total of 10 novel attacks that are more severe than the corresponding attacks for generic versions of the PDS.
We highlight the critical role of Redis’ decision to use non-cryptographic hash functions in the severity of these attacks.
We conclude by discussing countermeasures to the attacks, or explaining why, in some cases, countermeasures are not possible.
ePrint: https://eprint.iacr.org/2024/1312
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .