# 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

```c
/* 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.

```c
// 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);
```