Patternless Detection of Lateral Movement Attacks
*****By Gal Sadeh, Sr. Data Scientist, Silverfort*****
Lateral Movement refers to techniques adversaries use after gaining initial access to the network, to progressively move through the network, in their search of target assets and data. It is notoriously hard to detect and block lateral movement because it involves the compromise of legitimate user accounts, privileged accounts, and devices. These attacks are typically accomplished by using a number of different techniques. Some of the most popular ones are credential theft and Pass the Hash (PtH) in which the adversary exploits non-sensitive machines that hold credentials of other accounts. These credentials may be used to gain direct, or indirect, access to target systems.
This blog will explain one of the methods we at Silverfort use to uniquely identify and protect against these attacks. This method doesn’t assume there was a use of known attack patterns. Instead, it recognizes changes in user behaviors and deviations from the user’s predictable authentication pattern in real-time.
This method is used in conjunction with other lateral movement detection methods to provide a more accurate lateral movement detection.
Table Of Contents
The Shortcomings of Traditional Pattern-Based Lateral Movement Detection
In a Lateral Movement attack, an attacker typically propagates in the network by gaining access to a non-sensitive account, leveraging that account to gain access to additional accounts/assets, until reaching the target. Traditional lateral movement detection methods rely on known activities that can potentially indicate an attack. For example:
- Frequent access by a specific user to Windows file shares – Windows file shares are a prime target because they contain valuable information and are used by multiple users whose credentials can be harvested.
- Use of tools that can be used by hackers for stealing user’s tokens/hashes. Examples include Mimikatz, Windows Credential Editor and more.
- Use of admin tools like PSexec – PSexec is typically used by admins to upload, execute and interact with an executable on a remote host. If used by a hacker, it can enable the same operations without alerting anyone on the malicious use.
If you want to read more about this, I highly recommend on lateral movement tactics. this paper.
The full list contains many more patterns. However, overtime we see that attackers are deviating from the list, becoming more creative and sophisticated. This means that using a black-list of known malicious attack patterns is becoming less relevant, and using black-lists to detect evolving threats is no longer effective. That’s why a different method is needed – one that doesn’t not use a black-list to detect lateral movement.
Patternless Movement Detection Algorithm – A Deep Dive:
To identify lateral movement we want the algorithm to find a sequence of consecutive authentication requests that occurred in a short period between entities that usually don’t communicate with each other. The output will be a sequence of authentication requests that is suspected as a lateral movement attack.
The way we do it, is by constructing a statistical model that helps us estimate the probability of occurrence for each authentication request monitored by Silverfort. Then we look for a sequence of authenitcaiton requests with low probabilities.
Here is a very high level description of the algorithm:
- The algorithm takes as an input the monitored authentications from Silverfort’s platform and builds a Community Graph: a data structure that describes connections between entities in the network and how frequently they communicate with each other.
- It then executes the Louvain Algorithm on the Community Graph to cluster the entities into communities – for more details please read my previous blog post.
- Next, it builds a statistical model in order to estimate the probability of communications between any two entities – whether within a community or across communities.
- Then, it uses the statistical model to build a Lateral Movement Graph: the graph is an object that is built on the latest monitored authentication data. The weight of each edge in the graph is calculated by this statistical model.
- The algorithm then searches the graph for short paths that can represent Lateral Movement attacks.
Silverfort’s Patternless Detection Algorithm – A Deep Dive:
Data Collection and Construction of the Community graph
A Community Graph – Gcom, is constructed from authentication traffic periodically, based on human authentication requests monitored over a specific period of time. Let’s call that period of time A and let T=|A| be the duration of that period. The nodes in the community graph are entities (users and servers) and the edges are authentication requests. Every edge (u, s) in the graph is associated with a weight that represents the number of authentication requests between u and s in A. Let V be the group of entities in the network and let Auth be the list of authentication requests in A. The following process builds the community graph:
- Initialize an empty graph Gcom=(V, ∅)
- For a=(u, s) in Auth:
If (u, s)∈ E → w(u, s) = w(u, s) + 1
else → E = E ∪(u, s), w(u, s) = 1
3. Find Communities in Gcom using the Louvain method. Let |C|=c be the communities the algorithm found, denote by C(u) the community the user u belongs to.
4. From the Community graph we build an induced matrix M, a symmetric matrix of size c x c where M[i, j] is the number of authentication requests detected from community i to community j.
Constructing a Statistical Model and a Lateral Movement Graph
We want to estimate the probability of authentication request occurrence between two entities in a short period of time |B|=t. We assume that the number of occurrences of authentication requests between two entities over a select time period can be modeled by the Poisson Distribution: The Poisson distribution represents the rate of events that occur in a short period, and it depends on a single parameter λ – in our case λ represents the expected number of authentication requests in B. For every authentication request between user (u) and server (s), we assume that the number of authentication requests between the entities in the window is distributed Poisson with λ (u, s)=M[C(u), C(s)] / P where P = T/t. M[C(u), C(s)]is the number of authentication monitored in A, dividing by P gives us the expected number of authentication requests in B.
- Create an empty Graph Glat=(V, ∅)
- For every authentication between user u and server s in that window update the edges:
E = E∪(u, s), w(u, s) = -log(p(u, s))
As I wrote in the beginning of the blog, we would like to find the probability of the occurrence of a path. The probability of a path is the product of the probabilities of all the edges in it. Instead of multiplying the probabilities, we sum the logarithms of them – it’s easier for the algorithm to sum logs than multiply probabilities. Since ∀u p(u, s) ≤ 1, we have that the weights of the edges in the Lateral Movement Graph are non-negative, and the weight of the edge is higher when the probability of the authentication request is smaller.
Looking for Lateral Movement attacks in the Lateral Movement Graph
Now, we are ready to find lateral movement attacks in the graph we built!
Wherever the weight of the path is high, we suspect that a path represents a lateral movement attack (because the overall weight of the path is higher when the probability of the authentication requests in it is smaller). So, the higher the weight of the path, the lower the probability of seeing this path in a “normal” environment.
Since all the weights are positive, relatively long paths, with many edges, will have a high weight compared to shorter paths. So, to ensure consistency, we need to limit the number of edges that can be included in a single path. The advantage of having only positive weights is that we can scan the network for paths very fast using the “Dijkstra” algorithm with a few minor modifications. We set a threshold and look for paths with weights greater than that threshold – these paths are suspected for the lateral movement attack.
Let’s say we have three users: user1, user2 and user3. These users belong to different departments in the organization, therefore they are likely to belong to different communities. These communities don’t communicate much with each other often. If an attacker obtained the credentials of user1, and used them to authenticate to a server in a different community (server2), the attacker can get the credentials of users connecting to this server (server2), waits for someone else to connect server2 to steal their credentials (user2).
Now the attacker can authenticate as user2 to another server (server3) and harvest more credentials, and so on.
Lateral Movement Detection – The advantages of Silverforts Method
The method we described in this blog post has some advantages over other methods that are currently used for finding suspicious Lateral Movement paths:
- It can detect suspicious paths that are not part of known lateral movement patterns
- Since it analyzes the paths frequently, it detects lateral movement attacks very quickly
- Combining this method with other pattern-based methods improves the lateral movement detection capabilities of Silverfort’s platform
There is much more I’d like to write about but there is only so much I can include in a single blog post. In my next blog I’d like to explain how we differentiate user accounts from service accounts (those used for machine-to-machine communications). More will come after that.
Gal Sadeh, Sr. Data Scientist, Silverfort
Gal is a Senior Data Scientist in Silverfort’s research team. He is responsible for big data analytics and developing AI engines. He joined Silverfort after many years of research and leadership roles at the 8200 elite cyber unit of the Israel Defense Forces. Gal holds a B. Sc. in Mathematics and Computer Science from Tel Aviv University.