java-topology/docs/tickets/hurd-0001.md

hurd-0001 — CWE-407: S_auth_makeauth — O(N×M×k) UID verification

Severity: HIGH File: auth/auth.c lines ~162–216 Function: S_auth_makeauth CWE: CWE-407 Algorithmic Complexity

Defect

Four nested loops over nauths × n{e,a}uids/n{e,a}gids. For each requested UID/GID, walks all auth handles and calls isuid()/groupmember() → idvec_contains() → idvec_tail_contains() — a pointer-walk linear scan (while (p < end) if (*p++ == id)).

for (i = 0; i < neuids; i++) {
  has_it = 0;
  for (j = 0; j < nauths; j++)
    if (auths[j] && isuid(euids[i], auths[j]))   // O(k) linear scan
      { has_it = 1; break; }
  if (!has_it) goto eperm;
}
// same pattern repeated for nauids, negids, nagids

Complexity: O((neuids + nauids + negids + nagids) × nauths × k)

Scale

nauths = number of auth ports passed in (no hard limit). idvec size (k) = supplementary UIDs/groups — easily 16–64. Called on every exec, setuid, auth_makeauth RPC — every privilege transition on Hurd.

Fix

Before the verification loops, build a uid_t hash set from the union of all auths[] idvecs. Replace each isuid()/groupmember() call with O(1) hash lookup. Cost drops from O(N×M×k) to O(M×k) construction + O(N) lookup.