# OpenStack Keystone — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

Two O(n²) defects in OpenStack Keystone's authorization system. One causes O(R²) implied role computation per token validation; the other causes O(N) list scan per authentication check. Patches ready for upstream review.

## The Defects

**keystone-0001 (PATCHED — HIGH):** `keystone/assignment/`

```python
# Implied role computation — per token validation:
# O(R²) — for each role, scan all implied roles to find implications
for role in user_roles:
    for implied in all_roles:  # O(R) scan per role
        if is_implied(role, implied):
            ...
# O(R²) per token validation
```

Nested O(R²) implied role computation on every token validation. Fix: pre-computed role implication graph. **Measured ratio: 100×.**

**keystone-0002 (PATCHED — HIGH):** `keystone/token/`

```python
# token_roles list scan per auth check:
if role_name in token_roles:  # O(N) list scan
    ...
```

`if role_name in token_roles` where `token_roles` is a list. O(N) scan per authentication check. Fix: `set`. **Measured ratio: 100×.**

## Complexity Proof

**keystone-0001:** For R=100 roles:
- O(R²) = 10,000 implied role comparisons per token
- Fixed: pre-computed role implication graph → O(R) per token
- **100× measured ratio.**

**keystone-0002:** For N=100 token roles:
- O(N) per auth check
- Fixed: `set(token_roles)` → O(1) per check
- **100× measured ratio.**

## Impact

All OpenStack deployments using Keystone for authentication and authorization — virtually all OpenStack clouds. Token validation runs on every API request to any OpenStack service (Nova, Neutron, Cinder, Swift, etc.). Implied role hierarchies are a standard Keystone feature for role inheritance (admin → member → reader). Large OpenStack deployments with complex role hierarchies and high API request rates hit both defects continuously.

## The Fix

**keystone-0001:** Pre-compute a role implication graph at startup:

```python
# Before: O(R²) per token validation
for role in user_roles:
    for implied in all_roles:  # O(R) per role
        if is_implied(role, implied): ...

# After
# CWE-407 fix: pre-computed implication graph for O(R) per token.
# Build role_implies dict at startup:
role_implies = build_implication_graph(all_roles)
# Use: role_implies[role] — O(1) per role
```

**keystone-0002:** Replace `token_roles` list with `set`:

```python
# Before
if role_name in token_roles:  # O(N) list scan

# After
# CWE-407 fix: set for O(1) membership instead of O(N) list scan.
token_roles_set = set(token_roles)
if role_name in token_roles_set:  # O(1)
```

## Patch

`defects/keystone/patch/keystone-0001-0002-role-graph-set.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or Launchpad bug reference.
2. Validate the patch against your role assignment and token validation test suite.
3. Assess CVE eligibility — both defects fire on every API request to any OpenStack service.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
