Encrypted VoIP

Voice over IP (VoIP) technology is extremely popular these days and as a result it is important to study the security of the protocols being used. While most such technologies use strong encryption to protect the data, there are often side channel attacks that can be exploited. This paper from a couple of years ago presents an avenue of attack that assumes very little about the adversary while still achieving nontrivial results. The authors describe a process that uses a machine learning techniques combined with computational linguistic knowledge and specific audio codec properties to reconstruct potential transcripts of encrypted conversations. It's particularly impressive because they are able to combine the research advancements of different fields and apply it to a problem that has serious real-world implications.

In their model, the adversary needs only access to the packet lengths of the VoIP call (easily attainable by sniffing the network, e.g. over wireless) and knowledge of the language of the call (assumed to be English). Amazingly, with just these two pieces of information, it is possible to perform a limited reconstruction of the transcript of the call; not enough to deem the protocols complete broken, but enough to warrant a much closer look at how voice data should be encrypted. The attack begins by training on a large corpus of voice data that is passed through the known speech codec to build a model of phoneme boundaries based on packet lengths. This is the most novel part as they use observations about the codec itself, in particular variable bitrate encoding, as the basis for the model. By considering the length of each packet in relation to the surrounding packets and using dynamic programming, they construct the highest-probability phoneme boundaries for an entire sequence of packets.

Following the identification of the boundaries is the hardest task: classifying a sequence of packet lengths as an actual phoneme. Again, the authors use a combination of the training data and context to determine the most likely sequence of phonemes. For example, having a full dictionary of possible phoneme bigrams and trigrams in the English language will greatly limit the space of possible outputs; using a frequency distribution can further aid in choosing certain phonemes over others. Once the phonemes are identified (usually with error), the attack identifies word boundaries and finally maps the phoneme sequences into actual English words. There is some novelty in their approach to these latter two stages as well, but as I understand it those are well-known problems in the speech recognition field. The result of all this is some transcriptions that looks like this (the best ones, naturally):

• "Change involves the displacement of form." => "Codes involves the displacement of aim."
• "The two artists exchanged autographs." => "The two artists instance attendants."
• "Artificial intelligence is for real." => "Artificial intelligence is carry all."

Pretty impressive, as these sentences are spoken, encoded, encrypted, and then sent over the network, with the only observable factor being the resulting packet lengths. Being able to pick out words should be very worrisome for privacy, and even though the environment is controlled and some assumptions are made, the techniques presented are legitimately close to "breaking" the security of speech data encoded and sent over the network in this way.

This paper reinforces my thoughts on the sometimes misleading nature of "theoretical" security. Even using unbreakable encryption algorithms is not enough to provide security in the real world, as the possibility of side channel attacks is always present. Moreover, since every application has a different set of such attacks it is crucial to carefully design protocols to not be vulnerable, which is a significant burden. This topic of attacks based on packet lengths was also the basis of the StegoTorus project which I was a part of; we showed that the website you are visiting can often be identified based on packet lengths (when you cannot see the IP itself, e.g. over a proxy). Especially as Internet traffic becomes more dynamic and differentiated, patterns are emerging which can render encryption much less effective and may demonstrate the need for something more to protect privacy.

Anonymized Social Network Data

Social network analysis is a popular research area these days thanks to the rapid growth of networks like Facebook, Google+, and Twitter. Data for subsets of these networks is readily available, e.g. here, for researchers to analyze and discover interesting properties. Sometimes, these datasets are anonymized to protect the privacy of users while preserving the structure of the network; for example, instead of nodes being labelled with names, they are often replaced with a random ID. An interesting question that arises is whether this is secure, that is, can an attacker extract information from data anonymized in this way? Several years ago, it was shown that individuals could be identified from the anonymized Netflix Prize dataset, so this question is important for the research community to consider. In this paper, it is shown that an active attacker can quite easily defeat the naive random ID anonymization.

Let $G$ be the anonymized network with $n$ nodes that an attacker has access to. In this context, an active attacker is someone who has "user-level access" to the network prior to the creation of the anonymized dataset. For example, if $G$ is the anonymized Facebook network, an attacker can create accounts and friend people arbitrarily before $G$ is created such that those nodes and edges will be reflected in $G$. The resulting attack is quite simple. Let $H = \{ x_1, x_2, \ldots, x_k \}$ be the set of "fake" nodes created by the attacker and $W = \{ w_1, w_2, \ldots, w_b \}$ be the set of existing nodes that the attacker wants to compromise (in particular, learn about edges between $w_i$ and $w_j$). It is shown that with just $k = \Theta( \log{n} )$ attacker nodes, you can, with high probability, perform an attack efficiently on $b = \Theta( \log^2{n} )$ of the "real" nodes in the network. The attack is based on generating $H$ in such a way that it can easily be recovered from $G$ and connecting $H$ to $W$ so that each node in $W$ can be uniquely identified.

There are a few properties of $H$ that need to be guaranteed. There cannot be another induced subgraph in $G$ which is isomorphic to $H$, so that we can identify $H$, and there must be an efficient algorithm to find $H$ within $G$. To generate $H$, first include the edges $(x_i, x_{i+1})$ for $i = 1, 2, \ldots, k-1$ and then include every other edge with probability $1/2$. Then each $w_j$ is connected to a small, unique subset of nodes in $H$ so that we can recover all of the $w_j$'s once we find $H$. Furthermore, each $x_i$ has edges added randomly to nodes in $G - H$ until it reaches degree $\Delta_i = O(\log{n})$. Based on the structure of $H$ and the degrees, we can now recover it from $G$ using a search over short walks in $G$. Starting from each node, consider it as a potential $x_1$ and then, if that passes the degree requirements, consider all of its neighbors as potential $x_2$'s. For each neighbor that passes the degree requirements and the internal structure constraints of $H$, continue the walk, and repeat this until a walk with $k$ nodes is found. Through some delicate analysis, the authors show that, with high probability, there will be a unique walk that satisfies all the constraints (corresponding to $H$ itself) and that the search tree will have size $O(n^{1+\epsilon})$ so the algorithm is tractable on large datasets.

The paper describes experiments run on a LiveJournal dataset with over 4 million nodes and 70 million edges. With just $k = 7$ attacker nodes, they are able to successfully recover $H$ with roughly 90% probability, and it only goes up as $k$ increases. This means that it is simple to perform such attacks in practice and, perhaps more importantly, that the attacks have a sufficiently small effect in the network to avoid detection. The end result of the work is captured quite nicely by a quote from the paper, highlighting the observation that simple anonymization is not enough: "true safeguarding of privacy requires mathematical rigor, beginning with a clear description of what it means to compromise privacy, what are the computational and behavioral capabilities of the adversary, and to what information does it have access."