java-topology/whitepaper/outreach/wine-0004.md

Wine — CWE-407 Disclosure Brief (wine-0004)

2026-04-13 · Patch available — awaiting upstream merge

Finding

One O(n²) defect in Wine's wineserver token privilege system. token_find_privilege() performs an O(P) linear scan through a linked list of token privileges for each LUID lookup. Called inside loops in both token_adjust_privileges() and token_check_privileges(), the total cost reaches O(count × P) per syscall.

The Defect

wine-0004 (PATCHED — MEDIUM): server/token.c:808

// token_find_privilege — O(P) linear scan per lookup:
static struct privilege *token_find_privilege(struct token *token,
    struct luid luid, int enabled_only)
{
    struct privilege *privilege;
    LIST_FOR_EACH_ENTRY(privilege, &token->privileges, struct privilege, entry)
    {
        if (is_equal_luid(luid, privilege->luid))
            ...
    }
    return NULL;
}

// token_adjust_privileges — O(count) outer loop:
for (i = 0; i < count; i++)
{
    struct privilege *privilege = token_find_privilege(token, privs[i].luid, FALSE);
    // ^^ O(P) each iteration, O(count * P) total
}

Windows allows up to 1,023 privileges per AdjustTokenPrivileges call. A Wine token can hold ~21 standard privileges plus dynamically allocated ones.

Complexity Proof

count	P	Ops (defect)	Ops (fixed)	Speedup
21	21	441	21	21x
100	100	10,000	100	100x
1,023	1,023	1,046,529	1,023	1,023x

Impact

Token privilege operations fire during security checks throughout Win32 applications. AdjustTokenPrivileges and PrivilegeCheck are called by services, installers, and any application requesting elevated operations. The linear scan compounds with each privilege in the token.

The Fix

Replace list-based privilege storage with an indexed structure. All standard Windows privilege LUIDs have .low_part values 2-36. A flat array indexed by luid.low_part gives O(1) lookup for all standard privileges at the cost of ~70 pointers per token:

// Before: O(P) linked-list scan
LIST_FOR_EACH_ENTRY(privilege, &token->privileges, struct privilege, entry)

// After: O(1) array index for standard LUIDs (2-36)
struct privilege *priv_index[MAX_LUID + 1];  // ~35 pointers
// Lookup: priv_index[luid.low_part] if luid.high_part == 0 && luid.low_part <= MAX_LUID

Patch

Fix available: defects/wine-0004/patch/wine-0004-token-privilege-linear-scan.patch

Single-file patch in server/token.c. Documents the O(1) index approach for standard privilege LUIDs.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a reference on Wine Bugzilla or GitLab (wine/wine).
2. Assess severity — fires on every token privilege check and adjustment syscall.
3. Coordinate a disclosure date — we target 90 days from first contact.
4. We will credit the Wine team in the public disclosure. Preferred acknowledgment format welcome.

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