Cross-site request forgery (CSRF) in Cybersecurity - Time & Space Complexity

Time Complexity: Cross-site request forgery (CSRF)

O(n)

Understanding Time Complexity

When analyzing CSRF protection, we want to understand how the time to check requests grows as more requests come in.

We ask: How does the system handle many requests and keep verifying tokens efficiently?

Scenario Under Consideration

Analyze the time complexity of the following CSRF token verification code.

function verifyCsrfToken(request) {
  const token = request.headers['csrf-token'];
  if (!token) return false;
  return validTokens.includes(token);
}
    

This code checks if the CSRF token sent in the request headers matches any valid token stored on the server.

Identify Repeating Operations

Look for repeated checks or loops in the code.

• Primary operation: Searching the list of valid tokens.
• How many times: Once per request, but the search scans through all stored tokens.

How Execution Grows With Input

As the number of valid tokens grows, the time to find a matching token grows too.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The time grows directly with the number of tokens to check.

Final Time Complexity

Time Complexity: O(n)

This means the time to verify a token grows linearly with the number of stored valid tokens.

Common Mistake

[X] Wrong: "Checking a CSRF token always takes the same time no matter how many tokens exist."

[OK] Correct: If tokens are stored in a list, the system must check each one until it finds a match, so more tokens mean more checks and longer time.

Interview Connect

Understanding how token verification scales helps you design secure systems that stay fast even with many users.

Self-Check

"What if valid tokens were stored in a hash set instead of a list? How would the time complexity change?"