gistfile1.txt

• # Cryptographic review

  Verdict: do not deploy this protocol in its current form. The honest-party rerandomization argument is elegant and mostly convincing,
  but the integrity layer has a complete algebraic break. Separately, a malicious server can defeat resource-class sharding or assign
  clients explicit tracking tags using certificates that pass the proposed checks.

  I reviewed the documentation generated July 23, 2026, the reference implementation at commit 7a8e977
  (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/tree/7a8e977abf3fadfacdff52c4c9c9c3d9cc1f18ea), and the open Pkg.jl PR #4722
  (https://github.com/JuliaLang/Pkg.jl/pull/4722).

   Severity    Finding                                              Consequence
  ━━━━━━━━━━  ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━  ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
   Critical    Public (-1) chosen-rank forgery                      (B) accepted requests can saturate every HLL bucket
  ──────────  ───────────────────────────────────────────────────  ─────────────────────────────────────────────────────────────────────
   Critical    (g) is not certified                                 A malicious server can set (g=1), destroying class sharding
  ──────────  ───────────────────────────────────────────────────  ─────────────────────────────────────────────────────────────────────
   Critical    Certificates can be personalized                     The transmitted 32-bit ring ID becomes a persistent client tag
  ──────────  ───────────────────────────────────────────────────  ─────────────────────────────────────────────────────────────────────
   High        Traffic correlation composes independent HLL tags    A few linked package requests form a long-lived fingerprint
  ──────────  ───────────────────────────────────────────────────  ─────────────────────────────────────────────────────────────────────
   High        HLL error is treated as privacy noise                The proposed reporting floor is not a membership-privacy guarantee
  ──────────  ───────────────────────────────────────────────────  ─────────────────────────────────────────────────────────────────────
   Medium      Certificate proof and implementation differ          The advertised ((5/8)^n) soundness does not cover all accepted
                                                                    inputs
  ──────────  ───────────────────────────────────────────────────  ─────────────────────────────────────────────────────────────────────
   Medium      1024-bit example versus 112-bit target               Overall cryptographic strength is inconsistent

  ## The construction

  The server chooses

  [
  N=PQ=(2Bp+1)(2^m q+1),
  ]

  where (B) is odd and (P,Q,p,q) satisfy the stated primality and coprimality conditions. This gives

  [
  \mathbb Z_N^*
  \cong C_2\times C_B\times C_{2^m}\times C_{pq}.
  ]

  Relative to a public semigenerator (g), write an element as

  [
  \log_g(x)=(a,b,c,d).
  ]

  Its HLL sample is intended to be

  [
  \operatorname{hll}(x)=(b,\nu_2(c)),
  ]

  with (\nu_2(0)=m). For uniform (x), (b) is uniform and (\nu_2(c)) has the required truncated geometric distribution.

  A client stores (x_0\in J_N^-), derives a class secret

  [
  x_C=x_0g^{H(x_0,C)},
  ]

  and rerandomizes it for each request:

  [
  y=w x_C^t,\qquad
  w=z^{B2^m},\qquad
  t=2Bi+1.
  ]

  The server accepts (y) if (\operatorname{Jacobi}_N(y)=-1), then uses the factorization to decode its bucket and rank. This is
  described in the full construction (https://karpinski.org/HyperLogLogOverRSA.jl/dev/04-hyperloglog-over-rsa/) and protocol summary
  (https://karpinski.org/HyperLogLogOverRSA.jl/dev/06-protocol-summary/).

  This is not conventional RSA encryption: there is no RSA public exponent, padding scheme, IND-CPA game, or RSA-inversion reduction. It
  is better described as a trapdoor hidden-coordinate encoding in an RSA group.

  ## What works

  For an honestly generated ring, fixed class, and correct randomness, the rerandomization algebra is good:

  - (w) erases the (C_{pq}) coordinate without changing the other coordinates.
  - (t\equiv1\pmod B), so the bucket is preserved.
  - As (i) varies, (t\bmod2^m) covers all odd residues, making (tc) uniform among values with the same 2-adic valuation.
  - The Jacobi condition pins the remaining parity coordinate.

  Consequently, two clients with the same HLL pair generate the same token distribution. This is essentially information-theoretic and
  is the strongest part of the proposal.

  But it is only a conditional, single-class statement:

  > Given a correct fixed ring and two clients already known to have the same sketch, their tokens are indistinguishable.

  It does not prove malicious-client integrity, safe parameter selection, cross-class unlinkability under correlated traffic, or privacy
  of published queries.

  ## Critical break: anyone can forge any bucket and rank

  The malicious-client section argues that an attacker has no negative-Jacobi element whose hidden (C_{2^m}) coordinate is known. That
  is false because (-1) is such an element.

  Since (N\equiv3\pmod4),

  [
  \operatorname{Jacobi}_N(-1)=-1.
  ]

  Relative to the published semigenerator,

  [
  \log_g(-1)=\left(1,0,2^{m-1},0\right).
  ]

  The bucket coordinate is zero and the rank coordinate is publicly known.

  For (j=0,\ldots,B-1), define

  [
  h_j=2^{m-1}+2^m j
  ]

  and submit

  [
  \boxed{y_j=-g^{h_j}\pmod N}.
  ]

  Then:

  1. Every token passes validation:

     [
     \operatorname{Jacobi}_N(y_j)
     =\operatorname{Jacobi}_N(-1)\operatorname{Jacobi}_N(g)^{h_j}
     =-1.
     ]

  2. Its geometric coordinate is

     [
     2^{m-1}+h_j
     =2^m(j+1)
     \equiv0\pmod{2^m},
     ]

     so its rank is the maximum (m).

  3. Its bucket is (h_j\bmod B). Because (B) is odd, (2^m) is invertible modulo (B), so these (B) exponents cover every bucket.

  Thus exactly (B) accepted requests saturate the entire sketch. No factorization, discrete logarithm, count oracle, HMAC, or legitimate
  master key is needed. This directly refutes the malicious-client security argument
  (https://karpinski.org/HyperLogLogOverRSA.jl/dev/05-security-analysis/#Malicious-clients).

  More generally, for any desired rank (k<m), solve

  [
  h\equiv b\pmod B,\qquad
  h\equiv2^k-2^{m-1}\pmod{2^m}.
  ]

  This manufactures the chosen bucket and exact rank. Filtering only rank (m) therefore does not help.

  The attacker can also apply the protocol’s own (w,t) rerandomization to these forged representatives. The resulting tokens are
  distributed like honest tokens in that HLL fiber, so they cannot be recognized by syntax or blacklisting.

  I reproduced this against the reference implementation with (B=33,m=8): 33 forged values passed the Jacobi test, decoded to 33
  distinct buckets at rank 8, and caused hll_estimate to return Inf. The relevant decoder and estimator are in Ring.jl
  (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/blob/7a8e977abf3fadfacdff52c4c9c9c3d9cc1f18ea/src/Ring.jl#L223-L256) and
  Estimate.jl
  (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/blob/7a8e977abf3fadfacdff52c4c9c9c3d9cc1f18ea/src/Estimate.jl#L60-L80).

  This is a protocol-level failure, not merely the acknowledged absence of a reduction.

  There is also an internal inconsistency in the claimed inflation coefficient. The security page derives (\hat n=R/\ln2\approx1.44R),
  which means roughly 1.44 estimated units per request—or 0.693 requests per unit—not “1.44 requests per unit” as stated in the
  executive summary. The exact structured-scan coefficient needs rederivation, although the direct attack makes it moot.

  ## Critical malicious-server failures

  ### The certificate does not certify (g)

  Clients verify only

  [
  \operatorname{Jacobi}_N(g)=1.
  ]

  That is not evidence that (g) is a semigenerator. In particular, (g=1) passes. The implemented check is visible in Client.jl
  (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/blob/7a8e977abf3fadfacdff52c4c9c9c3d9cc1f18ea/src/Client.jl#L42-L87).

  With (g=1),

  [
  x_C=x_0,1^{H(x_0,C)}=x_0
  ]

  for every class. Every package, registry, and artifact therefore receives the same decoded HLL pair. This collapses the resource-
  sharding layer.

  I confirmed that a valid certificate with only (g) replaced by 1 is accepted, and unrelated resource classes all decode to the same
  pair.

  ### The server can give each client a different valid certificate

  Nothing requires all clients to see the same ((B,m,N,g)). There is no pinned parameter set, transparency log, gossip, independent
  signature, or consistency check.

  This is especially easy because the square-root challenges depend on (N), not (g). A server can reuse one valid (N) and root list
  while serving a different positive-Jacobi (g) to every client.

  The deployment then sends the first 32 bits of

  [
  \operatorname{SHA256}(B,m,N,g)
  ]

  on every request as the ring ID. A malicious server can choose client-specific (g) values until each gets an unused 32-bit ID,
  remember which initial IP received which value, and recognize that client after its IP changes. The ring-ID construction and daily
  certificate refresh are specified in the deployment section
  (https://karpinski.org/HyperLogLogOverRSA.jl/dev/06-protocol-summary/#Deployment-in-Julia’s-Pkg-client).

  Even proving that every (g) is a genuine semigenerator would not fix equivocation; the server knows the factorization and can generate
  many valid semigenerators. Global consistency is a separate requirement.

  ## HLL privacy is substantially weaker than the headline

  For rank probability

  [
  q_k=
  \begin{cases}
  2^{-(k+1)},&k<m,\
  2^{-m},&k=m,
  \end{cases}
  ]

  a particular pair ((b,k)) has probability (q_k/B). Therefore the expected fraction of clients whose pair is unique in a class of size
  (n) is

  [
  S(n)=\sum_k q_k
  \left(1-\frac{q_k}{B}\right)^{n-1}.
  ]

  For (B=4095,m=63):

   Clients in class    Expected clients with unique pair
  ━━━━━━━━━━━━━━━━━━  ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
              1,024                               92.10%
  ──────────────────  ───────────────────────────────────
              4,095                               72.82%
  ──────────────────  ───────────────────────────────────
             10,000                               48.84%
  ──────────────────  ───────────────────────────────────
            100,000                                5.91%

  So the proposed reporting floor (T=1024) is not an anonymity-set floor for the server or raw-log holder. At that size, about 943
  clients are expected to have a unique stable tag within the class. The writeup acknowledges the geometric tail, but its practical
  magnitude matters.

  Resource sharding makes these tags computationally independent; it does not stop them being joined through request metadata. The
  collision probability for one independently drawn HLL pair is approximately

  [
  \frac{1}{3B},
  ]

  or about 13.6 collision bits at (B=4095). If one package-operation burst groups three class tags using a connection, IP address, or
  timing, the composite has roughly 40.7 collision bits—already enough to be essentially unique among a million clients. Later
  overlapping requests can recognize it.

  Thus “cannot link across packages” only holds for records that have already been stripped of all grouping information. It does not
  hold for a server observing ordinary package-request traffic.

  ## HLL error is not a privacy mechanism

  The proposal treats HLL’s relative estimation error as if it were privacy noise: a one-client effect is compared with (1.04n/\sqrt B),
  producing the suggested publication floor.

  That is not a differential-privacy or membership-privacy argument. The client sketches are persistent, and a query over a fixed log is
  deterministic. Overlapping slices expose correlated functions of the same records, while repeated releases require composition
  analysis. HLL’s error is an accuracy property, not noise calibrated to neighboring-dataset sensitivity. See the original HyperLogLog
  paper (https://dmtcs.episciences.org/3545) versus the formal privacy approach in Dwork et al.
  (https://www.iacr.org/archive/tcc2006/38760266/38760266.pdf).

  A floor can be a useful operational policy, but it does not prove privacy or eliminate count oracles. The server also possesses the
  row-level values before any floor is applied.

  ## Modulus certificate assessment

  The certificate’s cleanest idea is the combinatorial observation that, for uniform (x,y\in J_N^+), a modulus with three or more
  distinct prime factors satisfies

  [
  x\text{ or }y\text{ or }xy\text{ is a square}
  ]

  with probability at most (5/8). Repeating (n) independent challenges gives the idealized ((5/8)^n) bound.

  Important limitations remain:

  - The noninteractive construction is a random-oracle/grinding argument, not a standard proof of semiprimality.
  - It establishes at most two distinct prime factors under its assumptions, not the precise intended factorization or a valid (g).
  - The implementation reduces a custom SHA-512 expansion modulo (N) instead of using an exact uniform sampler.
  - Hash outputs with Jacobi symbol zero are not rejected, although the theorem assumes units in (J_N^+).
  - Clients accept adversarial modulus sizes and moduli with small factors, where these proof-to-code differences need not be
    negligible.

  - The proof treats the Jacobi symbol over (N=\prod p_i^{n_i}) as unweighted parity of factor coordinates. It should be weighted by the
    exponents (n_i); the prime-power case therefore needs repair.

  None of these certificate issues is needed for the two critical attacks above.

  ## Parameters and implementation

  The example uses a 1024-bit modulus while requesting (2^{112}) certificate-grinding strength. NIST associates approximately 112-bit
  strength with 2048-bit RSA and 128-bit strength with 3072-bit RSA; 1024-bit RSA is at most roughly 80-bit strength. A novel structured
  modulus needs additional analysis, but it is not reasonable to claim a stronger baseline than generic RSA. NIST SP 800-57 Part 1 Rev.
  5 (https://csrc.nist.gov/pubs/sp/800/57/pt1/r5/final)

  Other notable issues:

  - There is no minimum modulus size.
  - The accepted maximum is one million bits, and the square-root list has no maximum length, creating a certificate-verification
    denial-of-service path.

  - The reference hll_estimate does not itself apply the documented Jacobi validation. Production code could add it, but the chosen-rank
    attack already passes that validation.

  - Tokens are not bound to a class, origin, time, request, or metadata slice and can be replayed elsewhere.
  - Ring rotation generates a new (x_0), so unique counts cannot be deduplicated across ring epochs.
  - The 128-bit class exponent has ample room at the default (m=63), but cannot be jointly uniform over (B\times2^{127}) at the accepted
    (m_{\max}=127).

  - The HMAC construction provides computational pseudorandomness, not the “statistical independence” claimed in places.

  ## Recommendation

  This needs redesign, not a patch.

  1. Do not deploy or enable the proposed endpoint.
  2. Disclose the (-g^h) attack to the author before wider deployment discussion.
  3. Replace the integrity mechanism with a construction having a precise unforgeability game and reduction. Rejecting (-1), maximum
     ranks, or recognizable representatives cannot fix this design.

  4. Treat the full public parameter set as security-critical. Use globally pinned or transparently logged epoch parameters with
     independent consistency checking.

  5. Define privacy over complete multi-request transcripts, chosen classes, parameter rotation, traffic metadata, and aggregate-output
     composition.

  6. If public slicing is required, use formal disclosure control—potentially differential privacy with a budget—rather than HLL
     estimator error.

  7. Minimize, shuffle, coarsen, and delete row-level request metadata before the party holding the RSA factors can access it.
  8. Only after redesign should implementation hardening, parameter selection, adversarial testing, and independent cryptographic review
     begin.

  The orbit-rerandomization primitive is mathematically interesting. But the RSA layer’s advertised purpose—preventing clients from
  choosing HLL values—is completely defeated, while the malicious-server protections do not cover all server-controlled parameters or
  their distribution.

gistfile2.txt

## Revised verdict

  The deeper audit found a substantially stronger failure. I would not treat draft PR #11 (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/pull/11) as a
  complete security fix.

  I rechecked the current head, 477c6fbb. The original public -1 forgery is fixed for properly validated, non-adaptive tokens, and the honest-ring anonymity argument
  is largely sound. But the published count becomes an adaptive oracle that recovers the hidden 2-adic coordinate and eventually produces maximum-rank tokens.

  ## Critical adaptive rank forgery

  Let (c_2) be the unknown (C_{2^m}) coordinate of the public element (2). For the intended primes, (\operatorname{Jacobi}_N(2)=-1), so all the following tokens pass
  the intended Jacobi validation.

  For an attacker-chosen (a), submit the batch

  [
  Y_a=\left{2g^{a+2^m j}:0\le j<B\right}.
  ]

  This batch has three useful properties:

  1. Since (2^m) is invertible modulo odd (B), the tokens cover every bucket exactly once.
  2. The (2^m j) term vanishes in the geometric coordinate, so every register gets the same rank
     [
     k=\min(v_2(c_2+a),m-1).
     ]

  3. When all registers equal (k<m-1), the implemented estimator returns exactly
     [
     \widehat n=\frac{B2^k}{\ln 2}.
     ]
     At the capped rank it returns Inf.

  Therefore the published aggregate reveals (k), even when rounded to an integer—the possible answers differ by factors of two. If (k<m-1), update

  [
  a\leftarrow a+2^k.
  ]

  This cancels the current least-significant nonzero bit of (c_2+a), so the next rank is strictly larger. After at most (m-1) rounds, all registers are saturated.

  For the proposed (B=4095,m=64), the worst-case work is fewer than 258,000 accepted requests. That is entirely polynomial and requires:

  - no factoring;
  - no square root of (-1);
  - no quartic character;
  - no initial knowledge of any discrete logarithm;
  - no malformed or Jacobi-positive tokens.

  Cumulative logs do not help: every new, higher-rank sweep overwrites all previous registers. Raw-token deduplication also does not help because the tokens can be
  publicly rerandomized while preserving their HLL values.

  I reproduced this at (B=4095,m=8):

  rank 1 -> estimate 11815.672
  rank 5 -> estimate 189050.758
  rank 6 -> estimate 378101.516
  rank 7 -> Inf

  The first response is already above the proposed (T=1024) floor. Consequently, the claim that the floor closes the count oracle is false in the protocol’s own
  malicious-client analysis
  (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/blob/477c6fbb5e9a11a8a1146b74ffdb516783412862/docs/src/05-security-analysis.md#L232-L266) and reporting
  guidance (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/blob/477c6fbb5e9a11a8a1146b74ffdb516783412862/docs/src/06-protocol-summary.md#L200-L206).

  The precise precondition is adaptive access to sufficiently accurate aggregate estimates for the same ring, plus the ability to inject (B) requests per round. A
  strictly one-shot release followed by immediate ring rotation would prevent this particular feedback loop. The documented floor alone does not.

  Without aggregate feedback, I still found no unconditional (O(B)) maximum-rank attack. The strongest static result remains the public-(2) factor-of-two bias.

  ## Other new findings

  - Identical group element, different persistent identifier. The client does not require (0<g<N). A server can send (g'=g+kN): it is mathematically the same
    semigenerator and produces identical tokens, but the documented ring-id hashes the unreduced decimal representation. I reproduced identical tokens with ring IDs
    82c19e89 and f57e630a. This gives the server a direct per-client tag even if a future proof establishes that (g) is a semigenerator. See the client check
    (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/blob/477c6fbb5e9a11a8a1146b74ffdb516783412862/src/Client.jl#L65-L67) and ring-id construction
    (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/blob/477c6fbb5e9a11a8a1146b74ffdb516783412862/docs/src/06-protocol-summary.md#L226-L238).

  - A stealthier malicious (g). Besides g=1, an accepted canonical (g) can preserve normal-looking rank variation while forcing the same bucket across every resource
    class. That creates a stable (\log_2 B)-bit cross-class tag—about 12 bits at (B=4095). A proof that (g) generates the required quotient is necessary.

  - Certificate hashing is type-dependent. The SHA-512 accumulator shifts in the Julia type of (N), truncating under Int64 and Int128; only BigInt retains the full
    digest. The same numeric certificate therefore hashes differently depending on its in-memory type, and documented TOML round-trips can invalidate certificates.
    See Hashing.jl (https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl/blob/477c6fbb5e9a11a8a1146b74ffdb516783412862/src/Hashing.jl#L5-L13).

  - The certificate does not establish RSA hardness or intended shape. I constructed an accepted 166-root certificate for (N=3q) with a large prime (q). One third of
    generated noise values were nonunits, and the modulus was trivially factorable. There is also no minimum modulus length or safe relationship between (m) and the
    modulus size.

  - The advertised certificate bound is too strong. For the genuinely fingerprinting modulus
    [
    B=3,\quad m=3,\quad N=1085=5\cdot7\cdot31,
    ]
    the implemented challenge transformation passes with probability about (0.650512), rather than at most (5/8). At 166 rounds that is approximately (2^{-103}), not
    the claimed (2^{-112.6}). Hashing by rejection sampling into units repairs this particular probability argument.

  - Estimator error is not privacy noise. The HLL standard error is variation over random sketches, not fresh noise applied to each published result. A known or
    Sybil-created common baseline makes differencing deterministic. The reporting floor is therefore neither a differential-privacy guarantee nor a reliable
    membership-inference defense.

  ## What remains sound

  The positive part is important:

  - PR #11 does close the original direct public -1 family when Jacobi validation is enforced.
  - The intended honest-ring same-class rerandomization/uniform-fiber argument checks out.
  - I found no public quartic or higher-character computation that directly reveals the remaining hidden bits without feedback.
  - The generalized anonymity theorem appears repairable by requiring (J_N^+/W_N) to be cyclic; the current abstract-embedding formulation is too weak.

  A credible repair now needs more than another modulus congruence:

  - prevent adaptive count feedback through fixed releases, contribution/query budgets, anti-Sybil controls, and preferably actual DP noise;
  - cryptographically limit one contribution per authorized principal or otherwise bind accepted tokens;
  - prove that (g) generates the required quotient;
  - enforce canonical representatives and a common, non-equivocating parameter view;
  - canonicalize certificate hashing and reject nonunits;
  - enforce modulus-size, balance, and (m)-versus-size constraints.

  The adaptive estimate attack is the main result of this pass: it converts the system’s intended output directly into the missing 2-adic discrete-log oracle.