java-topology/defects/wine-0003/TICKET.md

wine-0003 — CWE-407: crypt32 Chain Cycle Detection O(N²)

MOAD: 0001 — Sedimentary Defect (CWE-407) Severity: MEDIUM File: dlls/crypt32/chain.c Function: CRYPT_CheckSimpleChainForCycles() Lines: 422-427

Summary

CRYPT_CheckSimpleChainForCycles() uses a nested double loop to detect duplicate certificates in a chain (which would indicate a cycle). Our developer left a comment acknowledging the defect: "O(n^2) - I don't think there's a faster way". There is: a hash set of cert thumbprints.

Defect Pattern

/* O(n^2) - I don't think there's a faster way */
for (i = 0; !cyclicCertIndex && i < chain->cElement; i++)
    for (j = i + 1; !cyclicCertIndex && j < chain->cElement; j++)
        if (CertCompareCertificate(X509_ASN_ENCODING,
         chain->rgpElement[i]->pCertContext->pCertInfo,
         chain->rgpElement[j]->pCertContext->pCertInfo))
            cyclicCertIndex = j;

Each CertCompareCertificate call compares two full CERT_INFO structs (serial number, issuer, subject, public key). For a chain of N elements this is N*(N-1)/2 full struct comparisons.

Complexity

N (chain elements)	Comparisons (defect)	Comparisons (fixed)
10	45	10
50	1,225	50
100	4,950	100
200	19,900	200
500	124,750	500

Speedup ratio at N=200: ~99.5x. At N=500: ~249.5x.

Context

CertGetCertificateChain() is called during TLS handshake validation for every HTTPS connection Wine applications make (wininet, secur32, schannel). Chains longer than 5-10 are rare in practice but an adversarially crafted certificate chain (e.g. in a penetration test or fuzzing scenario) can induce quadratic cost.

Fix

Build a hash set of SHA-1 thumbprints (20 bytes each) on our single forward pass. Each lookup is O(1). Total cost: O(N).

Wine already has wine_rb_tree (a red-black tree providing O(log N) lookup) in include/wine/rbtree.h. An alternative is a lightweight open-addressed hash table keyed on 20-byte thumbprints.

// Pseudocode for O(N) replacement:
struct wine_rb_tree seen;
wine_rb_init(&seen, thumbprint_compare);
for (i = 0; i < chain->cElement; i++) {
    BYTE thumb[20];
    compute_sha1_thumbprint(chain->rgpElement[i], thumb);
    if (wine_rb_get(&seen, thumb)) { cyclicCertIndex = i; break; }
    wine_rb_put(&seen, thumb, &chain->rgpElement[i]->entry);
}
wine_rb_destroy(&seen, NULL, NULL);