OAuth 2.0 and OpenID Connect in Cybersecurity - Time & Space Complexity

Time Complexity: OAuth 2.0 and OpenID Connect

O(n)

Understanding Time Complexity

When working with OAuth 2.0 and OpenID Connect, it is important to understand how the time to process authentication and authorization requests grows as more users or tokens are involved.

We want to know how the system's work increases when handling more requests or tokens.

Scenario Under Consideration

Analyze the time complexity of the following simplified token validation process.

function validateToken(token, tokenStore) {
  for (let storedToken of tokenStore) {
    if (storedToken.id === token.id) {
      return storedToken.isValid;
    }
  }
  return false;
}
    

This code checks if a given token exists and is valid by searching through a list of stored tokens.

Identify Repeating Operations

Look for repeated steps that take time as input grows.

• Primary operation: Looping through the list of stored tokens to find a match.
• How many times: Up to once for each token in the store until a match is found or the list ends.

How Execution Grows With Input

As the number of stored tokens increases, the time to find a token grows roughly in direct proportion.

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

Pattern observation: The work grows steadily as the list gets longer, roughly one check per token.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Token validation time stays the same no matter how many tokens are stored."

[OK] Correct: Because the code checks tokens one by one, more tokens mean more checks, so time grows with the list size.

Interview Connect

Understanding how token validation scales helps you explain real-world system behavior and design better authentication flows.

Self-Check

"What if the tokenStore was changed from a list to a hash map? How would the time complexity change?"

Practice

1. What is the main purpose of OAuth 2.0 in online applications?

easy

A. To allow apps to access user data without sharing passwords

B. To encrypt all user data during transmission

C. To replace passwords with biometric authentication

D. To store user passwords securely on servers

Solution

1. Step 1: Understand OAuth 2.0's role

   OAuth 2.0 is designed to let apps get permission to access user data without needing the user's password.

2. Step 2: Compare options to OAuth 2.0's purpose

   Storing passwords securely, encrypting data during transmission, and replacing passwords with biometrics describe other security features but not OAuth 2.0's main function.

3. Final Answer:

   To allow apps to access user data without sharing passwords -> Option A

4. Quick Check:

   OAuth 2.0 = Access without password [OK]

Hint: OAuth 2.0 = permission without password sharing [OK]

Common Mistakes:

• Confusing OAuth 2.0 with encryption protocols
• Thinking OAuth 2.0 replaces passwords
• Assuming OAuth 2.0 stores passwords

2. Which of the following is a correct OAuth 2.0 grant type?

easy

A. Authorization Code

B. Password Encryption

C. Token Hashing

D. User Authentication

Solution

1. Step 1: Identify OAuth 2.0 grant types

   OAuth 2.0 defines several grant types, including Authorization Code, Implicit, Client Credentials, and Resource Owner Password Credentials.

2. Step 2: Match options to known grant types

   Only 'Authorization Code' is a valid OAuth 2.0 grant type; others are incorrect terms.

3. Final Answer:

   Authorization Code -> Option A

4. Quick Check:

   Grant type = Authorization Code [OK]

Hint: Grant types include Authorization Code, not encryption terms [OK]

Common Mistakes:

• Confusing grant types with encryption methods
• Selecting made-up OAuth terms
• Mixing authentication with grant types

3. Given this OAuth 2.0 flow snippet:

1. User clicks login
2. App redirects to Authorization Server
3. User grants permission
4. Authorization Server sends code to App
5. App exchanges code for access token

What is the purpose of step 5?

medium

A. To get the user's password

B. To obtain an access token for API calls

C. To verify the user's identity directly

D. To log the user out of the app

Solution

1. Step 1: Understand step 5 in OAuth 2.0 flow

   Step 5 is where the app exchanges the authorization code for an access token from the authorization server.

2. Step 2: Identify the purpose of the access token

   The access token allows the app to make authorized API calls on behalf of the user without needing their password.

3. Final Answer:

   To obtain an access token for API calls -> Option B

4. Quick Check:

   Step 5 = Get access token [OK]

Hint: Code exchanged for access token to call APIs [OK]

Common Mistakes:

• Thinking step 5 gets the password
• Confusing access token with identity verification
• Assuming step 5 logs out the user

4. A developer uses OpenID Connect but forgets to validate the ID token signature. What is the main risk?

medium

A. User passwords will be exposed

B. The app will crash immediately

C. The app might accept fake user identities

D. The access token will expire too soon

Solution

1. Step 1: Understand ID token validation

   Validating the ID token signature ensures the token is from a trusted source and not tampered with.

2. Step 2: Identify risk of skipping validation

   If validation is skipped, attackers could send fake tokens, letting unauthorized users impersonate others.

3. Final Answer:

   The app might accept fake user identities -> Option C

4. Quick Check:

   ID token validation prevents fake identities [OK]

Hint: Always validate ID token signature to trust identity [OK]

Common Mistakes:

• Assuming app crashes without validation
• Confusing token validation with password exposure
• Thinking token expiration is affected

5. An app uses OAuth 2.0 with OpenID Connect to authenticate users. It wants to get the user's email and profile info securely. Which token should the app request and verify?

hard

A. Refresh token only

B. ID token only

C. Access token only

D. Both access token and ID token

Solution

1. Step 1: Understand token roles in OpenID Connect

   The ID token proves the user's identity and contains profile info. The access token allows access to user data APIs.

2. Step 2: Determine which tokens to use for email and profile

   The app should verify the ID token for identity and use the access token to request additional user info securely.

3. Final Answer:

   Both access token and ID token -> Option D

4. Quick Check:

   ID token + access token = secure user info [OK]

Hint: Use ID token for identity, access token for data [OK]

Common Mistakes:

• Using only access token and ignoring ID token
• Using only ID token without access token
• Confusing refresh token with identity info