publications

2024

1. Deletions and Dishonesty: Probabilistic Data Structures in Adversarial Settings

   Mia Filić, Keran Kocher, Ella Kummer, and 1 more author

   In Asiacrypt ’24, Dec 2024

   Abs Bib HTML

   Probabilistic data structures (PDS) are compact representations of high-volume data that provide approximate answers to queries about the data. They are commonplace in today’s computing systems, finding use in databases, networking and more. While PDS are designed to perform well under benign inputs, they are frequently used in applications where inputs may be adversarially chosen. This may lead to a violation of their expected behaviour, for example an increase in false positive rate.

   @inproceedings{fkku_AC24,
     title = {Deletions and Dishonesty: Probabilistic Data Structures in Adversarial Settings},
     author = {Filić, Mia and Kocher, Keran and Kummer, Ella and Unnikrishnan, Anupama},
     language = {en},
     booktitle = {{Asiacrypt} '24},
     month = dec,
     year = {2024},
     keywords = {mypapers},
   }

2. Privacy Implications of AMQ-Based PQ TLS Authentication

   Dimitri Francolla, Mia Filić, and Shannon Veitch

   In CoNEXT ’24, Dec 2024

   Abs Bib HTML

   During the TLS 1.3 handshake, an entity (e.g., a client application) commonly transmits a chain of certificates and certificates’ digital signatures to the remote party to authenticate themselves. Towards a transition to post-quantum TLS, several proposals have been made to switch to post-quantum digital signatures in these certificate chains.Since post-quantum digital signatures are much larger than those based on classical assumptions, there has been a significant line of work aiming to reduce the overhead required for post-quantum authentication. Notably, the privacy implications of the proposed changes to the authentication system in TLS have not been thoroughly evaluated. Several of these proposals suggest Intermediate Certificate Authority (ICA) suppression, in which certificates that are already known to the client can be removed from the certificate chain to reduce the communication cost. One approach uses probabilistic data structures to transmit this information; however, this technique introduces additional privacy leakage, revealing to the server all ICAs whose certificates the client used to authenticate one of their past connections.In this work, we evaluate the privacy implications of taking such approaches to ICA suppression and the severity of its impact on TLS clients. In doing so, we perform an exploratory analysis on the current state of certificate-based PKI, particularly focusing on the distribution of ICAs. We define an adversarial model and a set of experiments to concretely evaluate the privacy leakage under the outlined assumptions. Our work suggests there is a risk in including this additional vector of information to adversarial servers aiming to execute website fingerprinting attacks.

   @inproceedings{ffv_CoNEXT24,
     author = {Francolla, Dimitri and Fili\'{c}, Mia and Veitch, Shannon},
     title = {Privacy Implications of AMQ-Based PQ TLS Authentication},
     year = {2024},
     language = {en},
     booktitle = {{CoNEXT} '24},
     month = dec,
     keywords = {mypapers},
   }

3. Probabilistic Data Structures in the Wild: A Security Analysis of Redis

   Mia Filić, Jonas Hofmann, Sam A. Markelon, and 2 more authors

   In eprint, Aug 2024

   Abs Bib HTML

   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.

   @inproceedings{fhmpu_eprint24,
     author = {Filić, Mia and Hofmann, Jonas and Markelon, Sam A. and Paterson, Kenneth G. and Unnikrishnan, Anupama},
     title = {Probabilistic Data Structures in the Wild: A Security Analysis of Redis},
     year = {2024},
     language = {en},
     booktitle = {eprint},
     month = aug,
     keywords = {mypapers},
   }

4. A Formal Treatment of Key Transparency Systems with Scalability Improvements

   Nicholas Brandt, Mia Filić, and Sam A. Markelon

   In eprint, Dec 2024

   Abs Bib HTML

   Key Transparency (KT) systems have emerged as a critical technology for securely distributing and verifying the correctness of public keys used in end-to-end encrypted messaging services. Despite substantial academic interest, increased industry adoption, and IETF standardization efforts, KT systems lack a holistic and formalized security model, limiting their resilience to practical threats and constraining future development. In this paper, we introduce the first cryptographically sound formalization of KT as an ideal functionality, clarifying the assumptions, security properties, and potential vulnerabilities of deployed KT systems. We identify a significant security concern — a possible impersonation attack by a malicious service provider — and propose a backward-compatible solution. Additionally, we address a core scalability bottleneck by designing and implementing a novel, privacy-preserving verifiable Bloom filter (VBF) that significantly improves KT efficiency without compromising security. Experimental results demonstrate the effectiveness of our approach, marking a step forward in both the theoretical and practical deployment of scalable KT solutions.

   @inproceedings{bfm_eprint24,
     author = {Brandt, Nicholas and Filić, Mia and Markelon, Sam A.},
     title = {A Formal Treatment of Key Transparency Systems with Scalability Improvements},
     language = {en},
     booktitle = {{eprint}},
     month = dec,
     year = {2024},
     keywords = {mypapers},
   }

5. A note on securing insertion-only Cuckoo filters

   Fernando Virdia, and Mia Filić

   In eprint, Apr 2024

   Bib HTML

   @inproceedings{vf_eprint24,
     author = {Virdia, Fernando and Filić, Mia},
     title = {A note on securing insertion-only Cuckoo filters},
     language = {en},
     booktitle = {eprint},
     month = apr,
     year = {2024},
     keywords = {mypapers},
   }

2023

1. Compact Frequency Estimators in Adversarial Environments

   Sam A. Markelon, Mia Filić, and Thomas Shrimpton

   In CCS ’23, Nov 2023

   Abs Bib HTML

   Count-Min Sketch (CMS) and HeavyKeeper (HK) are two realizations of a compact frequency estimator (CFE). These are a class of probabilistic data structures that maintain a compact summary of (typically) high-volume streaming data, and provides approximately correct estimates of the number of times any particular element has appeared. CFEs are often the base structure in systems looking for the highest-frequency elements (i.e., top-K elements, heavy hitters, elephant flows). Traditionally, probabilistic guarantees on the accuracy of frequency estimates are proved under the implicit assumption that stream elements do not depend upon the internal randomness of the structure. Said another way, they are proved in the presence of data streams that are created by non-adaptive adversaries. Yet in many practical use-cases, this assumption is not well-matched with reality; especially, in applications where malicious actors are incentivized to manipulate the data stream. We show that the CMS and HK structures can be forced to make significant estimation errors, by concrete attacks that exploit adaptivity. We analyze these attacks analytically and experimentally, with tight agreement between the two. Sadly, these negative results seem unavoidable for (at least) sketch-based CFEs with parameters that are reasonable in practice. On the positive side, we give a new CFE (Count-Keeper) that can be seen as a composition of the CMS and HK structures. Count-Keeper estimates are typically more accurate (by at least a factor of two) than CMS for “honest” streams; our attacks against CMS and HK are less effective (and more resource intensive) when used against Count-Keeper; and Count-Keeper has a native ability to flag estimates that are suspicious, which neither CMS or HK (or any other CFE, to our knowledge) admits.

   @inproceedings{mfs_cfe_2023,
     title = {Compact Frequency Estimators in Adversarial Environments},
     language = {en},
     booktitle = {{CCS} '23},
     author = {Markelon, Sam A. and Filić, Mia and Shrimpton, Thomas},
     month = nov,
     year = {2023},
     keywords = {mypapers},
   }

2022

1. Adversarial Correctness and Privacy for Probabilistic Data Structures

   Mia Filić, Kenneth Paterson, Anupama Unnikrishnan, and 1 more author

   In CCS ’22, Nov 2022

   Abs Bib HTML

   We study the security of Probabilistic Data Structures (PDS) for handling Approximate Membership Queries (AMQ); prominent examples of AMQ-PDS are Bloom and Cuckoo filters. AMQ-PDS are increasingly being deployed in environments where adversaries can gain benefit from carefully selecting inputs, for example to increase the false positive rate of an AMQ-PDS. They are also being used in settings where the inputs are sensitive and should remain private in the face of adversaries who can access an AMQ-PDS through an API or who can learn its internal state by compromising the system running the AMQ-PDS. We develop simulation-based security definitions that speak to correctness and privacy of AMQ-PDS. Our definitions are general and apply to a broad range of adversarial settings. We use our definitions to analyse the behaviour of both Bloom filters and insertion-only Cuckoo filters. We show that these AMQ-PDS can be provably protected through replacement or composition of hash functions with keyed pseudorandom functions in their construction. We also examine the practical impact on storage size and computation of providing secure instances of Bloom and insertion-only Cuckoo filters.

   @inproceedings{filic_adversarial_2022,
     title = {Adversarial {Correctness} and {Privacy} for {Probabilistic} {Data} {Structures}},
     language = {en},
     booktitle = {{CCS} '22},
     author = {Filić, Mia and Paterson, Kenneth and Unnikrishnan, Anupama and Virdia, Fernando},
     month = nov,
     year = {2022},
     keywords = {mypapers},
     pages = {1037--1050},
   }

2018

1. Modelling the Connection between GNSS Positioning Performance Degradation, and Space Weather and Ionospheric Conditions using RReliefF Features Selection

   Mia Filić, and Renato Filjar

   In , Oct 2018

   Abs Bib HTML

   The relationship between space weather and ionospheric conditions and GNSS position degradation has been recognized in numerous scientific studies. However, the relationship quantification remains a valuable scientific goal. In this manuscript, recent refinements in modelling of the level of GNSS positioning performance degradation caused by space weather and ionospheric dynamics are presented. The selected supervised machine learning (ML) method based on Linear Models (LM) and RReliefF variable selection process are used on experimentally collected data set in a quiet space-weather period.

   @inproceedings{filic_modelling_2018,
     title = {Modelling the {Connection} between {GNSS} {Positioning} {Performance} {Degradation}, and {Space} {Weather} and {Ionospheric} {Conditions} using {RReliefF} {Features} {Selection}},
     author = {Filić, Mia and Filjar, Renato},
     month = oct,
     year = {2018},
     keywords = {mypapers},
     pages = {1999--2006},
   }

2. On Development of the Forecasting Model of GNSS Positioning Performance Degradation due to Space Weather and Ionospheric Conditions

   Mia Filić

   In 2018 2nd URSI Atlantic Radio Science Meeting (AT-RASC), May 2018

   Abs Bib HTML

   Space weather and ionospheric conditions effects on the Global Satellite Navigation System (GNSS) positioning performance and operation have already been identified. However, the qualification of this relationship is still a subject of scientific activities. A model forecasting the level of GNSS positioning performance degradation caused by space weather and ionospheric dynamics represents a valuable scientific goal. This manuscript addresses the refinement in forecasting model development procedure achieved through utilisation of selected supervised machine learning method based on Linear Models (LM) and Component Analysis (PCA) on experimentally collected data set of the quiet space-weather period.

   @inproceedings{filic_development_2018,
     title = {On {Development} of the {Forecasting} {Model} of {GNSS} {Positioning} {Performance} {Degradation} due to {Space} {Weather} and {Ionospheric} {Conditions}},
     booktitle = {2018 2nd {URSI} {Atlantic} {Radio} {Science} {Meeting} ({AT}-{RASC})},
     author = {Filić, Mia},
     month = may,
     year = {2018},
     keywords = {mypapers, Analytical models, Computational modeling, Data models, Forecasting, Global navigation satellite system, Meteorology, Predictive models},
     pages = {1--4},
   }