Post-exploitation and pivoting in Cybersecurity - Time & Space Complexity

Time Complexity: Post-exploitation and pivoting

O(n²)

Understanding Time Complexity

When attackers gain access to one system, they often try to move to others. This process is called pivoting.

We want to understand how the effort to move through multiple systems grows as the number of systems increases.

Scenario Under Consideration

Analyze the time complexity of the following simplified pivoting process.

for each system in network:
    if system is reachable:
        exploit(system)
        gather_credentials(system)
        add system to compromised_list
        for each new_system in network:
            if new_system not in compromised_list:
                try pivot(new_system)
    

This code tries to exploit reachable systems and then pivot to new systems repeatedly.

Identify Repeating Operations

Identify the loops and repeated attempts to move between systems.

• Primary operation: Looping over all systems to exploit and pivot.
• How many times: For each system, it may attempt to pivot to many others, repeating nested loops.

How Execution Grows With Input

As the number of systems (n) grows, the number of pivot attempts grows faster because each compromised system tries to reach others.

Input Size (n)	Approx. Operations
10	About 100 attempts
100	About 10,000 attempts
1000	About 1,000,000 attempts

Pattern observation: The effort grows roughly by the square of the number of systems.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the number of systems, the work to pivot between them roughly quadruples.

Common Mistake

[X] Wrong: "Pivoting effort grows linearly with the number of systems."

[OK] Correct: Because each compromised system tries to reach many others, the attempts multiply, not just add up.

Interview Connect

Understanding how pivoting scales helps you think like an attacker and defender. It shows why networks with many systems need strong segmentation.

Self-Check

"What if pivoting only tries new systems once per compromised system instead of repeatedly? How would the time complexity change?"