Privacy and Google Web History

Posted on ArXiV last night: Private Information Disclosure from Web Searches. (The case of Google Web History), by Claude Castelluccia, Emiliano De Cristofaro, Daniele Perito.

Our report was sent to Google on February 23rd, 2010. Google is investigating the problem and has decided to temporarily suspend search suggestions from Search History. Furthermore, Google Web History page is now offered over HTTPS only. Updated information about this project is available at: this http URL

The link above has some more details of their back and forth with Google on the matter, and at least it looks like Google’s on the losing end of it.

Search histories have a lot of information in them, since searches correlated with local events, such as disease spread (related and interesting is Twitter’s tracking of earthquakes). Since user sessions can be compromised by someone hijacking the cookies that maintain the session, Google requires HTTPS for many services, like GMail, but not for the “automatic suggestion” for searches. The authors implemented an attack called The Historiographer:

The Historiographer uses the fact that users signed in any Google service receive personalized suggestions for their search queries based on previously-searched keywords. Since Google Web Search transmits authentication cookies in clear, the Historiographer monitoring the network can capture such a cookie and exploit the search suggestions to reconstruct a user’s search history.

This attack is not looking at a short time-window of browsing history, but essentially the entire search history as stored by Google. They did real experiments, and found:

Results show that almost one third of monitored users were signed in their Google accounts and, among them, a half had Web History enabled, thus being vulnerable to our attack. Finally, we show that data from several other Google services can be collected with a simple session hijacking attack.

So how does it work? The program hijacks the SID cookie from the user by eavesdropping, and then issues prefixes to the suggestion services; that is, it simulates a user typing in the first few letters of a search query. Prefixes have to be at least 2-3 letters to trigger the suggestion, and the top 3 completions are given. Of course 26^3 is a lot of prefixes to try, so the system has to sample effectively. The system just queries the top 10% of most frequent 3-letter prefixes (based on the statistics of English), which amounts to 121 queries to the system. If a particular 2-letter prefix (e.g. “pr”) is a prefix for many 3-letter prefixes (e.g. “pre”, “pra”, “pro”) which result in 3 completions, they will proceed greedily to look at longer prefixes in that direction. Note that this is the same principle behind Dasher (or arithmetic coding, really).

Based on this, the system can reconstruct the search history for the hijacked user. By using Google’s personalized results service, they can also get more information about the user’s preferences. A little more worrying is this observation:

In fact, a malicious entity could set up a Tor exit node to hijack cookies and reconstruct search histories. The security design underlying the Tor network guarantees that the malicious Tor exit node, although potentially able to access unencrypted traffic, is not able to learn the origin of such traffic. However, it may take the malicious node just one Google SID cookie to reconstruct a user’s search history, the searched locations, the default location, etc., thus signi cantly increasing the probability of identifying a user.

It’s an interesting paper, and worth a read if you are interested in these issues.

self (the remix)

Last weekend I had a chance to see Mo’olelo Performing Arts Company‘s production (they also have a blog) of Robert Farid Karimi’s self (the remix) featuring Karimi and DJ D Double:

Storyteller/performance artist, def poetry jam performer, national poetry slam champion robert farid karimi — supported by an amazing soundscape spun live by Chicago DJ and Violator All-Star DJ D Double — mixes together stories, movement, and music to tell the tale of a first generation child of Iranian and Guatemalan immigrants learning how to survive the cultural imperialism of the United States on his quest to find wholeness in the fractured atmosphere of the 70s and 80s.

It’s a coming-of-age story that seems to have a new relevance given the current tensions between the US and Iran and the heated rhetoric around immigration. I usually enjoy solo performance, and although this is technically a dual performance, the “style” is similar to other narrative solo performances (c.f. Josh Kornbluth). What was particularly effective is the way in which DJ D Double weaves the soundtrack and effects into the narrative. It’s rapid-changing and pulls samples, beats, and songs from every direction, providing an structure to support Karimi’s performance while commenting and in an effect becoming its own character. In terms of “solo performance,” it’s some of the best use of sound I’ve seen.

The show only has a few more performances, starting tonight and going through this weekend. If you’re in San Diego and reading this (probably 5 people total), then go check it out!