Nevertheless, there are other ways to capture such cookies. For instance one could use malware to capture search traffic, but the simplest solution remains to search SID cookies.
Using a malware to redirect the traffic of infected computers through a proxy controlled by the attack would allow to capture session cookies. Such infection has recently been detected by Google which displayed a banner on its search page . In that particular case, Google traffic redirection was merely a side effect which triggered the malware detection.
According to Google, a couple of millions of computers  were infected by this malware. Attackers could have captured a significant number of session cookies and run attacks described in our paper.
Googling for cookies
The simpler solution to find SID cookies is to search them. Typing the right query in Google provides a list of pages where people published captured HTTP traffic, including SID cookies (also works with Yahoo!).
If you replace your SID cookie by one of the cookies listed in these pages, you will receive the same personalized results than its owner. From these results you can quickly extract a list of visited results, Gmail contacts and Google+ acquaintances.
Not all these results contain full SID cookies and some of the listed SID cookies may have already expired, but this simple search should already provide many valid cookies to test the flaw. I've written a Chrome extension to simply replace the SID cookie for the "google.com" domain and quickly test different accounts. Once installed, click on the red button in the upper right corner, past the cookie value and click save.
On Firefox you could use the Web Developer extension to edit cookies (it does not seem to work on Firefox 5.0).
Linking data and PI
By publishing their (apparently innocuous) cookies users indirectly published part of their click-stream and associated it to their email address. Thus they established a public record of having visited these URLs , and this record is now linked to their name. From there, their full anonymized click-stream -- not reduced to visited search results -- could be de-anonymized by a tracking ad-network.
 Damian Menscher, "Using data to protect people from malware", http://googleonlinesecurity.blogspot.com/2011/07/using-data-to-protect-people-from.html
 Arvind Narayanan, "There is no such thing as anonymous online tracking", http://cyberlaw.stanford.edu/node/6701
Web Search History Information Leakage
Back in February, I re-discovered a small flaw in Google Search: result personalization leaks the list of results you clicked on. This leak was already known and mentioned in a paper by Castelluccia et al., but several features added by Google made it critical.
- First there is the possibility (for web search history users) to only view result that have already been visited (visit http://www.google.com/webhp?tbs=whv:1).
- Second, with Google Instant it is possible to view visited links quickly without living a trace in the victim Web Search history (the attack is not-destructive).
- Third, when Google display previously visited search results, it used to provide the query that led to the results searching when he clicked on the result, thus the attacker knew which keywords the victim was usually searching for and could have enter these keywords in a search box to get new results which will suggest new keywords to type and so forth and so on...
The third point has been addressed by Google very recently, when they introduced the new interface with the black top bar.
Vincent Verdot and I wrote a paper about this flaw. In order to conduct an experiment, we’ve been working on a proof of concept and an evaluation tool that we used to gather results.
Proof of concept based on Firesheep
This proof of concept is based on Firesheep (I just added a module and modify the attack launched when a SID cookie was captured). Firesheep is only working with the latest version of Firefox 3.6, do not expect to run it on Firefox 5.
With our version of Firesheep, when a Google SID cookie is captured, the account name appears in the Firesheep sidebar. Double clicking on it starts the attack; double clicking again displays the retrieved list of visited links.
The Evaluation tool
We also designed a Firefox extension which downloads your web search history on your computer, issue a couple of search queries (mostly searching for extensions like: « .com, .fr, .us, .html, www, … ») and see how many clicked links can be retrieved.
We’ve run this experiment with a dozen of account and sent the result to Google. We’ll soon publish the paper as a technical report.
How to protect your Click History
We’ve been in contact with Google Security Team who is working on a fix that should soon be deployed. In the meantime, make sure you’re not logged in your Google account when you’re connected on an unsecured network.
If you do not use Web Search History you may also purge it and disable the feature (visit https://www.google.com/history).
Also, TrackMeNot and Unsearch will reduce the exposition of your click history.
Running the Test
If you want to run the test 5 minutes:
- A Google Account with Web Search History enabled. To check that you activated it, visit https://www.google.com/history; if it asks you to turn on the feature, then you cannot help here. Thanks anyway for trying.
- Install this Firefox extension (http://unsearcher.org/Test%20Flawfirstname.lastname@example.org), download it and then drag it and drop it in Firefox. Once the extension has been installed, you should restart Firefox.
- Modify your Google Search preferences (http://www.google.com/preferences?hl=en) to disable “Google Instant” and set the number of returned result to 100 (instead of 10).
- Sign out and Sign in again on Google.com.
- In Firefox, click on “Tools-> ADMONITOR-> History”. A first message should appear to inform you that the extension is about to extract your search History. Click on OK and do not close the Firefox window.
- After five minutes, another message will be prompted to inform you that the test is finished. It’ll tell you where you can find the generated file. A Firefox window should have open (not necessarily taking the focus). You can send me the content of this window via e-mail and we’ll integrate it in our experiment results.
- You can remove the generated files and uninstall the sid@testextension.
Thanks for helping us.