Timing Attacks Have Never Been So Practical:

Advanced Cross-Site Search
Attacks
Nethanel Gelernter

About me:
Nethanel Gelernter
Vic Tim• Security Researcher / Hacker– Web application security– Ph.D., hacks, research papers, talks, etc.

• Cyberpion– Exploring new attack vectors &developing defenses against them

• Leading the cyber-security
studies & research in the Collegeof Management, Israel

AgendaVic–Timpractical timing attacks• Cross-site search (XS-search) attacks &Response inflation• Challenges– When response inflation is impossible• Browser-based XS-search attacks• Second-order XS-search attacks

Nethanel Gelernter

Cross-Site Search Attacks• Gelernter & Herzberg, CCS’ 2015
• Exploit ‘search’ timing side-channel• ‘Search’ in private-data kept by web-service• Practical:– Tested on hundreds of Gmail users• Real world conditions• Example: find user name– From lists of 2000 common (first and last) names– Takes about a minuteNethanel Gelernter

Cross-site attacker model• Main model for web attacks• The victim’s browser is authenticated to services
that hold private records (e.g., Gmail)• The victim visits the attacker’s website...<script>…

Cross-site request

Nethanel Gelernter

Cross-site attacker model• Cross-site search over user’s data in service– Attacker cannot access the content of the response• Same Origin Policy– The attacker can measure the response time (T)...<script>…
GET SEARCH request𝑻

Nethanel Gelernter

Response

XS-Search
example: user nameVic Tim• Find out whether the user is Alice or Bob…
• Compare:– T(Bob): response time for ‘messages sent by Bob’
– T(Alice): response time for ‘messages sent by Alice’...<Script….>
GET q=in:sent&from:Bob𝑻(𝑩𝒐𝒃)Not found
GET q=in:sent&from:Alice𝑻(𝑨𝒍𝒊𝒄𝒆)
Nethanel Gelernter

result 1, result 2, ….

What else can XS-Search expose?
Email contentSearch
History

Structured
information

Contacts
Name
Relationships(follows, …)
Nethanel Gelernter

Search History

XS-Search:
Basic Flow
Vic Tim• Find the answer for a Boolean question• Three steps:– Transform the question into a search request– Send search requests and collect samples– Analyze response times  answer the question!

Nethanel Gelernter

XS-Search:
Basic Flow – 1st Step
Vic Tim• Is the name of the user Alice?
– in:sent from:Alice• Is she related to bob@gmail.com?
– bob@gmail.com&st=100• Does Alice have an affair with Charlie– “I love you” to:Charlie from:AliceNethanel Gelernter

XS-Search:
Basic Flow – 2nd Step
Vic Tim• Send a Challenge request– Is the user name Alice?

• True: a Full response is returned (has some content)• False: an empty response is returned...<Script….>
GET q=in:sent&from:Alice
𝑻(𝑪𝒉𝒂𝒍𝒍𝒆𝒏𝒈𝒆)

Nethanel Gelernter?

Unknown response

XS-Search:
Basic Flow – 2nd Step
Vic Tim• Send a Dummy request– Is the user name fdjakdhasd?
• The response is expected to be empty...<Script….>
GET q=in:sent&from:Alice
𝑻(𝑪𝒉𝒂𝒍𝒍𝒆𝒏𝒈𝒆)?

Unknown response

GET q=in:sent&from:fdjakdhasd𝑻(𝑫𝒖𝒎𝒎𝒚)Nethanel Gelernter

Empty response

XS-Search:
Basic Flow – 2nd Step
Vic Tim...<Script….>
GET q=in:sent&from:Alice
𝑻(𝑪𝒉𝒂𝒍𝒍𝒆𝒏𝒈𝒆)

Repeatseveraltimes?

Unknown response

GET q=in:sent&from:fdjakdhasd𝑻(𝑫𝒖𝒎𝒎𝒚)Nethanel Gelernter

Empty response

𝑻 𝑪𝒉𝒂𝒍𝒍𝒆𝒏𝒈𝒆

𝑻 𝒅𝒖𝒎𝒎𝒚SampleSampleXS-Search: Basic Flow – 3rd Step
Statistical Test
𝑻 𝑪𝒉𝒂𝒍𝒍𝒆𝒏𝒈𝒆

𝑻 𝒅𝒖𝒎𝒎𝒚SampleSampleSignificant difference between thedistributions?

YESNO• Dist(Challenge) ≠ Dist(Dummy)• Dist(Challenge) = Dist(Dummy)•  Response for challenge is full•  Response for challenge is empty

User name is AliceUser name is NOT AliceNethanel GelernterPractical timing attacks: challenges• Timing attacks– Delays depend on dynamically-changing factors, e.g.:Congestion and concurrent processes in client and server• Practical attacks– Minimal time
• Exploit also short visits of users– Minimal number of requests• Avoid detection and blocking– E.g., by server’s anti-DoS defenses

Nethanel Gelernter

Response Inflation• Increase the size difference between full andempty responses• Larger difference in size  Larger difference intime

Larger  Slower
Nethanel Gelernter

Response Inflation• Search requests have many parameters• Some of them are reflected in the responses asa function of the number of results
https://example.com/search?reflected_parameter=valuevalueEmpty response

Nethanel Gelernter

value
value
value

value
value
value

value
value
value

Full responseResponse Inflation• Sometimes, the attacker send very long strings
as the value of the reflected parameterhttps://example.com/search?reflected_parameter=Long string

Long string.........................

Empty responseLong string.........................
Long string.........................
Long string.........................
Long string.........................
Long string.........................
Long string.........................
Long string.........................
Long string.........................
Long string.........................

Full response
Nethanel Gelernter

Response inflation example• Exploiting Gmail search in the HTML view
• The query itself!
– Appears once for each entry (50 max by default)– Can be inflated to 8KB• Up to 400KB response size inflation!

Nethanel Gelernter

But…

Nethanel Gelernter

What if there is no response inflation?

Nethanel Gelernter

What if there is no response inflation?
• Browser-based XS-search– When there is some difference in the response size

• Second-order XS-search– When there is no difference in the response size!

Nethanel Gelernter

Browser-based (BB) XS-Search• Statistical tests and divide and conquer
algorithms– Gelernter & Herzberg, CCS’ 2015

• Browser-based timingside channel– Van Goethem et al.,
CCS’ 2015• Algorithmic
improvements
Nethanel Gelernter

Classical vs. BB timing attacks• Classical timing attacks:– Load the resources from the server several
times to collect time measurements• Browser-based timing attacks:– Load all the resources from the server onceand cache them
– Then load them from the cache many times
to collect time measurements
Nethanel Gelernter

Classical vs. BB timing attacks• Exploiting / measurements affected by– Classical: network delay, server processing time,browser processing time
– Browser-based: browser processing time

• Can be used to differentiate between– Classical: large/small resources, high/low server
processing time
– Browser-based: large/small resources
Nethanel Gelernter

BB XS-Search:
Basic Flow
Vic Tim• Find the answer for a Boolean question• Changing only the second step of the original
XS-Search attack

Nethanel Gelernter

BB XS-Search:
Basic Flow – 2nd Step
Vic Tim• Send a Challenge request– Is the user name Alice?

• True: a Full response is returned (has some content)• False: an empty response is returned...<Script….>
GET q=in:sent&from:Alice
Cache
response

Nethanel Gelernter?

Unknown response

BB XS-Search:
Basic Flow – 2nd Step
Vic Tim• Send a Dummy request– Is the user name fdjakdhasd?
• The response is expected to be empty...<Script….>
GET q=in:sent&from:Alice
Cache
response
Cache
response
Nethanel Gelernter?

Unknown response

GET q=in:sent&from:fdjakdhasd
Empty response

BB XS-Search:
Basic Flow – 2nd Step
Vic Tim...<Script….>
GET q=in:sent&from:Alice?

Unknown andempty
responses arecached𝑻(𝑪𝒉𝒂𝒍𝒍𝒆𝒏𝒈𝒆)

Repeatmanytimes

𝑻(𝑫𝒖𝒎𝒎𝒚)Nethanel Gelernter

Unknown response

GET q=in:sent&from:fdjakdhasd
Empty response?

Unknown response

Empty responseBrowser-based (BB) XS-Search• Algorithmic improvements• Not for Boolean questions– Basic flow – only Boolean questions• Is the victim’s name Alice?

• Answering multiple choice questions– E.g., which names out of many options are matching
the victim?

• Optimally use the browser-based timing sidechannel
Nethanel Gelernter

Browser-based (BB) XS-Search• Evaluation compared to both the previous works• Repeating attacks/experiments done in each ofthem– Original XS-Search: extract victim’s names from Gmail– BB timing attacks: extract victim’s age from Facebook• Significant improvement!
• In this talk: only one example

Nethanel Gelernter

BB XS-Search vs. original XS-Search• Gmail example– The goal of the attacker: extract the first and lastnames of the victim out of a list of 2000 names– XS-Search results:• 90% success rate (both first and last namefound)• 1 minute on average• 2.6% false positive

Nethanel Gelernter

BB XS-Search vs. original XS-Search• How to answer multiple-answer questions
efficiently?
• The optimized multiple term identification(OMTI) algorithm– Divide and conquer algorithm• Relying on the OR operator– Different dummy search request is sent every
roundNethanel Gelernter

BB XS-Search vs. original XS-Search• Rely on browser-based timing side-channel tooptimize the OMTI algorithm• Observation: empty responses are (almost)identical– No need to send dummy requests in every round– No need to reload the empty response in everyround• Rely on previous measurements!
Nethanel Gelernter

BB XS-Search vs. original XS-Search• Evaluation of the attack on 5 different Gmail
accounts– 15-16 times on each of them• Significant improvement!
– 41.6 seconds on average (compared to 1 minute)– 92.3% success (compared to 89.7%)– 1.3% false positive (compared to 2.6%)

Nethanel Gelernter

BB XS-Search vs. original XS-Search• DEMONethanel Gelernter

Second-order (SO) XS-Search attacks• The problem: sometimes the size difference isnegligible• For example: a sentence that appears in asingle email
value

Empty response

Nethanel Gelernter

Full response

Second-order (SO) XS-Search attacks• Second-order attacks– First, manipulate the attacked web application• Make it (more) vulnerable– Exploit the vulnerability• Second-order XS-search attacks– First manipulate the attacked storage• Create significant response inflation– Launch browser-based XS-search attack
Nethanel Gelernter

Second-order (SO) XS-Search attacks• Two SO XS-search attacks– Simple– Inflating

Nethanel Gelernter

Second-order (SO) XS-Search attacks• Model– Storage– Many records– A secret appears in one of the records• Attacker can manipulate the storage remotely– E.g., email accounts– Another example later…

Nethanel Gelernter

Simple SO XS-Search attack• The problem: the secret appears only once inthe storage• Simple solution: the attacker will addadditional records that contain the secret!

Nethanel Gelernter

Simple SO XS-Search attack

Nethanel Gelernter

Simple SO XS-Search attack• Example: extracting Facebook password-resetcode from Yahoo! email
VictimHTTP GET
malicious Javascript

Repeatseveraltimes

Send reset
password code
XS-searchattack

6-digit reset code
Nethanel Gelernter

6-digit reset code

Inflating SO XS-Search attack• Creates significant response inflation effect– Increase the size difference between empty andfull response• Unlike all the previous attacks: the empty
response will be (significantly) larger than thefull response

Nethanel Gelernter

Inflating SO XS-Search attack• The challenge of the attacker:– Find a secret out of a large dictionary of possiblevalues• Notations– M - maximal number of results– Match-all record – a record that contains all thepossible values for the secret– Inflating record – a record that significantly
inflates the size of every response containing it
Nethanel Gelernter

Inflating SO XS-Search attack• Attack process
First part:– Plant one match-all inflating record in thestorage– Plant additional M-1 match-all records– Additional record(s) may be added as a result of
the victim's operations, or via operations
triggered by the attacker
Second part:– Launch BB XS-search attack!
Nethanel Gelernter

Inflating SO XS-Search attack
Response for searching the right secret
New record (contains secret)
Match-all record
M-1

Match-all record

Match-all record

Inflating match-all record
Response for searching the wrong secretNethanel Gelernter

Inflating SO XS-Search attack• Inflating record in email service providers– Email headers• From• To

Nethanel Gelernter

Inflating SO XS-Search attack• Example: extracting Visa/Mastercard credit
card number– Structured information• VVVV-XXXX-YYYY-ZZZZ• First and last names: extract 2 out of 2000
– Done successfully!

• Credit card number: extract 4 out of 10000– Should not be much harder
Nethanel Gelernter

Inflating SO XS-Search attack• Example: extracting Visa/Mastercard credit
card number• Match-all record – a record that contains all
the possible 4-digit sequences– Possibly as an attachment• Inflating match-all record – a match-all
record with very long From field
Nethanel Gelernter

Inflating SO XS-Search attack• Gmail example• How?
– Cross-site search requests are now blocked inboth the HTML and standard views• Cross-site search attack without sending
cross-site search requests?

Nethanel Gelernter

Inflating SO XS-Search attack• Gmail example• Exploiting the autocomplete feature!

M=4(M = maximal
number ofresults)

Nethanel Gelernter

Inflating SO XS-Search attack• Gmail example: the manipulated storage

New record (contains secret)
Match-all record

M-1

Match-all record
Match-all record

Inflating match-all record

Nethanel Gelernter

Inflating SO XS-Search attack• Gmail example: full response (size is small)

New record (contains secret)
Match-all record

M-1

Match-all record
Match-all record

Nethanel Gelernter

Inflating SO XS-Search attack• Gmail example: empty response (size is very large)
Match-all record

M-1

Match-all record

Match-all record

Inflating match-all record

Nethanel Gelernter

Inflating SO XS-Search attack• DEMO

Nethanel Gelernter

Inflating SO XS-Search attack• Evaluation results– 96% success rate within less than 50 seconds• Yet, in the other 4% percent, 3 out of 4 sequenceswere found, and it was possible to detect the error andto fix it

Nethanel Gelernter

Stealthy SO XS-Search attacks• The challenge: manipulations on the storage
can be detected!
• Solution: manipulate the storage in a way thatwill not be detected by the user

• HOW?

Nethanel Gelernter

Stealthy SO XS-Search attacks• Emails solution: abuse anti-spam mechanisms• The planted emails will be marked as spam
– Users do not get notifications for spam emails– Users (usually) do not visit their spam folder• Only when it is possible to search in the spamand in the other folders using the same request– E.g., Gmail• in:inbox OR in:spam
Nethanel Gelernter

Stealthy SO XS-Search attacks• Search history• Two requirement for inflating SO XSSearch attack:– Inject records to the search history log• DONE: Gelernter & Grinstein & Herzberg, ACSAC
2015– Inject an inflating record
Nethanel Gelernter

Stealthy SO XS-Search attacks• Bingexample:inflating SOXS-Searchattack toextract
searchhistory

Nethanel Gelernter

Defenses (briefly)• If possible - blocking cross-site search requests• In other cases – make it harder to exploit– Block inflation techniques– Rate limit• Like (almost) every other web-application attack
the challenge is to find all the vulnerable spots
Nethanel Gelernter

Conclusions• Advanced cross-site search attacks– Browser-based– Second order• Practical!
• Many vulnerable websites– Including popular ones

Nethanel Gelernter

Thank you!

Nethanel Gelernter

Questions?
Nethanel Gelernter