Regex Dos with Api Keys

Regular expression denial of service (ReDoS) attacks exploit poorly constructed regex patterns to cause exponential time complexity during pattern matching. In API key validation contexts, this vulnerability becomes particularly dangerous because attackers can craft malicious keys that trigger catastrophic backtracking.

Consider a common API key validation pattern:

const validateApiKey = (key) => {
  const regex = /^([A-Za-z0-9]{20,40})$/;
  return regex.test(key);
};

While this appears safe, nested quantifiers create vulnerabilities. A pattern like ^(([a-z]+)+[0-9]+)+$ can cause exponential backtracking when processing keys with carefully constructed alternating character sequences.

The attack vector works through catastrophic backtracking. When a regex engine encounters nested quantifiers, it must explore all possible ways to match the pattern. With malicious input containing alternating characters, the engine creates a combinatorial explosion of matching attempts.

API key endpoints are particularly susceptible because:

• Keys are often processed on every request without rate limiting
• Validation occurs before authentication, so unauthenticated attackers can trigger the vulnerability
• API keys typically follow predictable formats (alphanumeric, fixed length) that can be exploited
• Services may validate keys against multiple patterns or databases, amplifying the impact
• Denial of service can block legitimate users from accessing protected resources

Real-world impact includes complete service unavailability, increased infrastructure costs from CPU exhaustion, and potential cascading failures if the validation service is critical to application functionality.

Detecting regex DoS vulnerabilities in API key validation requires both static analysis and dynamic testing approaches. The most effective detection combines pattern analysis with runtime validation testing.

Static analysis tools examine regex patterns for known anti-patterns:

function detectReDoSRegex(pattern) {
  const antiPatterns = [
    /(/.+)+/,          // nested quantifiers
    /(/.+)*//,        // optional nested quantifiers
    /(a+)+b/,          // catastrophic backtracking
    /(a*)*b/,          // optional catastrophic backtracking
    /(a+)+b/,          // multiple nested groups
  ];
  
  for (const antiPattern of antiPatterns) {
    if (antiPattern.test(pattern)) {
      return true;
    }
  }
  return false;
}

Dynamic testing involves submitting crafted payloads to API endpoints:

async function testApiForKeyReDoS(endpoint) {
  const testCases = [
    // Alternating characters to trigger backtracking
    'a'.repeat(20) + '1'.repeat(20),
    'ab'.repeat(30),
    'abc'.repeat(25),
    // Long keys with nested patterns
    'A'.repeat(40) + 'B'.repeat(40),
  ];
  
  for (const testCase of testCases) {
    const startTime = Date.now();
    const response = await fetch(`${endpoint}?api_key=${encodeURIComponent(testCase)}`, {
      method: 'GET',
      headers: { 'X-API-Key': testCase }
    });
    
    const duration = Date.now() - startTime;
    if (duration > 1000) { // 1 second threshold
      console.log(`Potential ReDoS: ${duration}ms for key: ${testCase.substring(0, 20)}...`);
    }
  }
}

Automated scanning tools like middleBrick can identify these vulnerabilities by testing API endpoints with malicious payloads and measuring response times. The scanner evaluates regex patterns in your codebase and tests runtime behavior against crafted inputs.

middleBrick specifically checks for:

• Regex patterns with nested quantifiers in API key validation code
• API endpoints that process keys without timeout protection
• Services that validate keys against multiple patterns sequentially
• Endpoints vulnerable to timing attacks that could indicate regex processing delays

The scanner provides detailed reports showing which endpoints are vulnerable, the specific regex patterns causing issues, and recommended remediation steps.

Remediating regex DoS vulnerabilities in API key validation requires a multi-layered approach. The most effective strategy combines safe regex patterns, input validation, and fallback mechanisms.

First, replace vulnerable regex patterns with safe alternatives:

// Vulnerable pattern
const unsafePattern = /^([A-Za-z0-9]{20,40})$/;

// Safe pattern using possessive quantifiers (if supported) or atomic groups
const safePattern = /^(?>[A-Za-z0-9]{20,40})$/;

// Alternative: use non-capturing groups and avoid nested quantifiers
const alternativePattern = /^[A-Za-z0-9]{20,40}$/;

// Even safer: use whitelist approach with character class
const whitelistPattern = /^[A-Za-z0-9]{20,40}$/;

Implement input validation before regex processing:

function validateApiKeyLengthAndFormat(key) {
  // Quick length check (constant time)
  if (key.length < 20 || key.length > 40) {
    return false;
  }
  
  // Character whitelist validation (O(n) guaranteed)
  for (let i = 0; i < key.length; i++) {
    const charCode = key.charCodeAt(i);
    if (!
      (charCode >= 48 && charCode <= 57) || // 0-9
      (charCode >= 65 && charCode <= 90) || // A-Z
      (charCode >= 97 && charCode <= 122)    // a-z
    ) {
      return false;
    }
  }
  
  return true;
}

// Use validation before regex
function safeApiKeyValidation(key) {
  if (!validateApiKeyLengthAndFormat(key)) {
    return false;
  }
  
  // Only proceed with regex if basic validation passes
  const regex = /^[A-Za-z0-9]{20,40}$/;
  return regex.test(key);
}

Add timeout protection for regex operations:

function timeoutableRegexTest(pattern, input, timeoutMs = 100) {
  return new Promise((resolve, reject) => {
    const timeoutId = setTimeout(() => {
      reject(new Error('Regex timeout'));
    }, timeoutMs);

    try {
      const result = pattern.test(input);
      clearTimeout(timeoutId);
      resolve(result);
    } catch (error) {
      clearTimeout(timeoutId);
      reject(error);
    }
  });
}

// Usage
async function validateWithTimeout(key) {
  const pattern = /^[A-Za-z0-9]{20,40}$/;
  
  try {
    const result = await timeoutableRegexTest(pattern, key, 100);
    return result;
  } catch (error) {
    console.warn('Regex validation timed out, falling back to safe validation');
    return validateApiKeyLengthAndFormat(key);
  }
}

Implement circuit breaker patterns for API key validation:

class ApiKeyValidator {
  constructor() {
    this.failureCount = 0;
    this.lastFailure = 0;
    this.circuitOpen = false;
  }

  async validate(key) {
    if (this.circuitOpen) {
      // Fallback to simple length check if circuit is open
      return key.length >= 20 && key.length <= 40;
    }

    try {
      const startTime = Date.now();
      const isValid = await this.performValidation(key);
      const duration = Date.now() - startTime;

      if (duration > 500) { // 500ms threshold
        this.registerFailure();
      } else {
        this.reset();
      }

      return isValid;
    } catch (error) {
      this.registerFailure();
      throw error;
    }
  }

  async performValidation(key) {
    const pattern = /^[A-Za-z0-9]{20,40}$/;
    return pattern.test(key);
  }

  registerFailure() {
    this.failureCount++;
    this.lastFailure = Date.now();
    
    if (this.failureCount > 3) {
      this.circuitOpen = true;
      setTimeout(() => {
        this.circuitOpen = false;
        this.failureCount = 0;
      }, 60000); // Close circuit after 1 minute
    }
  }

  reset() {
    this.failureCount = 0;
    this.circuitOpen = false;
  }
}

For Node.js applications, use the safe-regex library to detect potentially vulnerable patterns:

const safeRegex = require('safe-regex');

function isRegexSafe(pattern) {
  try {
    const regex = new RegExp(pattern);
    return safeRegex(regex);
  } catch (error) {
    return false;
  }
}

// Usage in validation
const userProvidedPattern = getPatternFromConfig();
if (!isRegexSafe(userProvidedPattern)) {
  throw new Error('Unsafe regex pattern detected');
}