Time Travelers Busted: How to Detect Impossible Travel

In this month's Tradecraft Tuesday, our Developer Tech Lead Jamin Becker and Product Researcher Dave Kleinatland dove deep into the problem of Impossible Travel. Going in depth on the issue, they explain how it's detected and the challenges that come along with it. And to contextualize it all for us, they also provided real-world scenarios throughout the episode. 

If you’d like to watch the episode on-demand, you can find it here. If you’d like to read more about it, then we invite you to do so. With that said, let's recap.

‍

What is Impossible Travel?

Impossible Travel is a type of location-based anomaly detection that occurs when one user account performs actions in multiple geographical locations in a timeframe that’s impossible to achieve with normal physical travel. For example, User1 logs in from Chicago and then 15 minutes later they log in from Seattle. Unless User1 is teleporting, this sure doesn't seem possible. That's a very simple, straightforward example of what it means, but there are many intricacies that we'll get into.

Impossible Travel is one of the earliest indicators of user compromise that can be detected, and it works against any user-centric event that can be tied back to a location. When compared to other detection methodologies, the benefits of Impossible Travel include: 

• not relying on specific signatures or known attack patterns to detect anomalies
• being a fairly straightforward detection concept that’s easier to implement and understand
• flagging anomalies independent of user behavior

‍

Impossible Travel for Microsoft 365

While Impossible Travel detections can occur from any log source that contains a timestamp, a location attribute, and a user identity, we're mainly going to focus on Microsoft 365 log sources. The majority of events within Microsoft 365's Unified Audit Log meet the criteria, but we’ll specifically look at [.highlight]UserLoggedIn[.highlight] events, as these are rich with additional contextual information. Most importantly, they show that a user has already successfully authenticated and has a certain level of privilege within the environment.

One caveat to note is that when looking at location-based data, there's a lot of noise to sift through. We see upwards of 100,000 events per hour. Some of the noise we see is legitimate VPN or proxy activity, and even though it's a bad idea, we often see “legitimate” credential sharing that can trigger location-based anomaly detections. The goal of using Impossible Travel detections is to wade through some of the noise to get to the real scary stuff, like potential account or user takeovers.

‍

How Impossible Travel Detection Works

By itself, Impossible Travel anomaly detection casts a very wide net, but it helps reduce the number of events to focus on. Even with the reduction in events, there’s still a fair amount of filtering to be done to make the data useful. Using a standard detection pipeline for location-based anomalies, we can break this down into six general steps. The first half of the pipeline deals with determining which events are actually Impossible Travel, while the second half we're doing more of the user baselines, traditional enrichments, and applying risk heuristics that will help us receive actionables out of this dataset. 

‍

‍

Breaking this down step-by-step:

Step 1 - Create Event Pairs

• Receive user events
• Group by user attribute (like user ID or email address)

Step 2 - Calculate Implied Velocity

• The difference in time between the events
• Filter by a predetermined threshold

Step 3 - Exclude Possible Travel

• Review Event Pairs from the previous step to match on Impossible Travel criteria

Step 4 - Exclude Normal User Behavior

• Compare Anomalous User Event Pairs to the user’s baseline behavior

Step 5 - Assign a Risk Score

• Based on predetermined criteria that contributes or detracts from the risk

Step 6 - Exclude Low Risk

• This could be something like the credential sharing we talked about previously

‍

Challenges in Detection

While there are many challenges for correctly identifying Impossible Travel anomalies, one of the first we found was what we'll call "time traveling users''—users moving faster than the speed of light. Essentially, we saw multiple times where a user logged in from two very disparate locations with the same timestamp or only one second apart. We've determined there are various legitimate reasons this occurs—sadly, it's not time travel—like services running on different devices but authenticating to the same account, or if a user switches between private networks to mobile devices. Below is an example of some of the data we were receiving.

Time traveling is out, but we still have some common challenges we face often, including High Data Volume, Benign True Positives from Legitimate Usage, and False Positives from Bad Geolocation Information. Let's talk a bit about what causes each of these along with helpful solutions. 

‍

High Data Volume

Cause 

• Analyzing this data in real-time or even near real-time requires significant computational resources at scale

Solutions

• Prioritize which logs actually matter
• Aggregate around most recent user and location events
• Place more expensive operations later in the pipeline

‍‍

Benign True Positives from Legitimate Usage

Cause 

• By itself, Impossible Travel is not enough to determine whether or not an event pair is malicious

Solutions

• Context is everything and user-baselining is a great tool to exclude event pairs that don’t deviate from normal patterns of behavior
• Understand what each event is giving you and where additional enrichments would add value

‍

False Positives from Bad Geolocation Information

Cause 

• Geolocation services often contain inaccurate location information making any velocity calculations made from them incorrect as well

Solutions

• Longer distances between two geographic locations should increase confidence in velocity calculation
• Aggregate results across multiple location databases

‍

Wrapping Up

Impossible Travel is a topic that one blog post cannot conquer. While we gave a high-level overview here, there's far more information in the episode where you can hear Jamin and Dave really get into the weeds of it all. They even give some exciting real-world examples. If you want to watch the recording or other Tradecraft Tuesday episodes, you can always do so on-demand. And if you haven't yet, be sure to register for the next episode so you don't miss any of the upcoming fun!

‍

‍