Anonymous rate-limiting in services with Direct Anonymous Attestation

Anonymous rate-limiting in services with Direct Anonymous Attestation – Alex Catarineu, Konark Modi

Abstract

Anonymous data collection systems allows users to contribute the data necessary to build services and applications while preserving their privacy.

Anonymity, however, can be abused by malicious agents, injecting fabricated data, aiming to subvert or to sabotage the data collection.

At Cliqz we deal with the same challenge. Our data collection systems in Cliqz Browser and Extension which power our search engine[1], anti-tracking systems[2] are designed in a way that server cannot link that two messages are from the same user. But if the user is fully anonymous, how can the system prevent an attacker from polluting the data collection?

We will showcase an efficient mechanism to block an attacker without compromising the privacy and anonymity of the users.

This system builds on top of Direct Anonymous Attestation, a proven cryptographic primitive to implement service rate-limiting in a scenario where messages between users and the service are sent anonymously and message unlinkability is to be preserved.

Rate-limiting constraints for a service are defined as an arbitrary mapping from every possible valid message to a ‘rate-limiting tag’ string, in such a way that the constraints can be enforced if the service never accepts more than one message from the same user with same tag.

Under this definition, we employ DAA protocol to enforce these ‘message quotas’ without being able to link user messages. If authorized, users receive credentials issued by the service. These can be used to sign messages with respect to a ‘basename’ string, in such a way that two signatures performed with the same credentials are unlinkable if and only if their basenames are different. By forcing the mentioned rate-limiting tag to be in the signature basename the rate-limiting constraints can be enforced.

Service will verify the signature according to the DAA protocol and accept the message if and only if the tag that maps to the rate-limiting ‘basename’ has still not been seen.

We present all components needed to build and deploy such protection on existing data collection systems with little overhead.

This system which is running in production for Cliqz browser is however not limited to browsers or extensions, it has been implemented in a scenario where user code is running in a web browser, thanks to WebAssembly and asm.js.