The researchers also found another way to reconstruct users' search history. Another cookie--the one that authenticates a user to Google's search service--is also sent in the clear. By capturing this cookie and impersonating the user in communications with the search service, they were able to run algorithms that quickly reconstructed large portions of a user's Web search history.

Castelluccia says companies should recognize that they need to use secure channels whenever a user's personal information is being transmitted. "The main lesson of the attack is that companies should use https as much as possible," he says, adding, "Of course, https has a cost--it means Google has to use more servers, energy, and all that."

Google responded to the researchers by changing its Web History so that it does always use encrypted communications. The company also temporarily suspended its search suggestion service. And suggestions for Google Maps, which the researchers were also able to access, are now encrypted, too.

Alma Whitten, software engineer for Google's Security and Privacy arm, said in a statement that Google increased its use of https in response to the researchers. "Google has been and continues to be an industry leader in providing support for encryption in our services, which is designed to address precisely the issues that all major websites face when transmitting information over http to users connecting via an unsecured network channel," she said.

"Google was very reactive and very responsible," Castelluccia says. However, he notes that search suggestions are still being provided via mobile phones and are still vulnerable. The researchers are keeping track of which services are vulnerable on a website devoted to the project. (Update May 17, 2010: Google fixed the mobile issue described on April 28.)

Ben Adida, a fellow at Harvard University's Center for Research on Computation and Society, says that intercepting unencrypted traffic is "trivial" today, and "the consequences can be surprisingly privacy-invasive." He adds, "This work is nice because it concisely shows how half-measures often provide little protection: there is a growing need to move all sensitive services to [https]."

However, Adida warns that encryption won't solve all privacy problems. "We are slowly entrusting more of our data to large companies that then risk becoming targets of large-scale attacks," he says. "It's important to continuously secure these services, but it's equally important to realize the inherent risk we run by giving this data to third parties in the first place."