Hi there! I'm Samir, a Computer Science student at Stanford University, with a focus in applied cryptography and computer security. This summer, I want to work (through GSoC) on computing usage statistics without keeping IP addresses in memory (see tickets #7532 and #15469) [1] [2]. Currently, we keep sets of IP's (or hashed IP's) in memory so that we can compute the number of unique client connections. This has been pointed out as a pretty serious concern, because the IP's themselves are sensitive info that we don't want an attacker to acquire, but the statistics are relatively valuable. As Nick first pointed out in #15469, we can use proven techniques to compute these statistics without actually explicitly storing any IP's (or IP hashes) in memory. The technique I want to use, "Probabilistic Counting with Stochastic Averaging", or PCSA, is relatively well-studied, and can provide good estimates (<5% error) of the number of unique elements in a time series. The basic idea is to count the number of 0's before the least significant 1 in every (Jenkins hashed) IP, and then recognize that the more unique IP's we encounter, the more likely it is that we see a hashed IP with a large number of 0's before the least significant 1. (Shoutout to Jaskaran and [3] for helping me understand this). A more detailed explanation and more resources for understanding PCSA are in the proposal. Here is my draft proposal (also attached, but links don't work): http://stanford.edu/~samir2/TorGSoCApplication.html I'd love to hear feedback on it - what's feasible, what's most useful, and what I should focus on, etc. You can also chat with me about it on IRC at `samir2`! Thanks, ~Samir Menon menon.samir@xxxxxxxxx Stanford University, B.S. Computer Science, 2019 [1] https://trac.torproject.org/projects/tor/ticket/7532 [2] https://trac.torproject.org/projects/tor/ticket/15469 [3] https://www.cs.princeton.edu/~rs/talks/AC11-Cardinality.pdf
Attachment:
TorGSoCAnonymousLocalStats.pdf
Description: Adobe PDF document
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev