Cross-site search (XS-search) attacks circumvent the same-origin policy and extract sensitive information, by using the time it takes for the browser to receive responses to search queries. This side-channel is usually considered impractical, due to the limited attack duration and high variability of delays. This may be true for naive XS-search attacks; however, we show that the use of better tools facilitates effective XS-search attacks, exposing information efficiently and precisely.
We present and evaluate three types of tools: (1) appropriate statistical tests, (2) amplification of the timing side-channel, by `inflating' communication or computation, and (3) optimized, tailored divide-and-conquer algorithms, to identify terms from large `dictionaries'. These techniques may be applicable in other scenarios.
We implemented and evaluated the attacks against the popular Gmail and Bing services, in several environments and ethical experiments, taking careful, IRB-approved measures to avoid exposure of personal information.