js/aead.js

/*
 * aead.js — AEAD usage-limit math engine.
 *
 * Implements the advantage bounds and usage limits from
 * draft-irtf-cfrg-aead-limits (single-key limits in Section 6,
 * multi-key limits in Section 7), plus the claim-based limits from the
 * AEGIS specification and analyses cited by draft-irtf-cfrg-aegis-aead.
 *
 * All quantities are handled as log2 values, so limits like 2^64.5
 * stay exactly representable in double precision. Every function takes
 * and returns plain numbers on the log2 scale (Infinity means
 * "no limit", NaN means "no feasible value").
 *
 * Works both in the browser (exposed as window.AEADLimits) and under
 * Node.js (module.exports) so the self-test harness can run headless.
 */
(function (global) {
  'use strict';

  var LOG2_10 = Math.log2(10);

  /* ---------- small log2-domain helpers ---------- */

  // log2(2^a + 2^b); b may be -Infinity.
  function log2sum(a, b) {
    if (b === -Infinity || b === undefined) return a;
    if (a < b) { var t = a; a = b; b = t; }
    return a + Math.log2(1 + Math.pow(2, b - a));
  }

  // log2(2^a - 2^b), requires a > b.
  function log2diff(a, b) {
    if (b === -Infinity) return a;
    if (a <= b) return -Infinity;
    return a + Math.log2(1 - Math.pow(2, b - a));
  }

  // Smallest of the given log2 values (ignoring undefined).
  function minLog2() {
    var m = Infinity;
    for (var i = 0; i < arguments.length; i++) {
      var x = arguments[i];
      if (x === undefined) continue;
      if (x < m) m = x;
    }
    return m;
  }

  // Solve a*x^2 + b*x = C for x > 0, with a >= 0, b >= 0, C > 0,
  // given la = log2(a) (-Infinity if a = 0), lb = log2(b) (-Infinity if b = 0),
  // lC = log2(C). Returns log2(x).
  function solveQuadUsage(la, lb, lC) {
    if (la === -Infinity) return lC - lb;          // b*x = C
    if (lb === -Infinity) return (lC - la) / 2;    // a*x^2 = C
    // x = (sqrt(b^2 + 4aC) - b) / (2a) = 2C / (sqrt(b^2 + 4aC) + b)
    var disc = log2sum(2 * lb, la + lC + 2);       // log2(b^2 + 4aC)
    var denom = log2sum(disc, lb) + 1;             // log2(2*(sqrt(...)+b))
    return lC - denom;
  }

  // log2(2^e - 1), evaluated without losing precision when e is small.
  function log2PowMinusOne(e) {
    if (e === Infinity) return Infinity;
    if (e <= 0) return -Infinity;
    if (e > 53) return e;
    return e + Math.log1p(-Math.pow(2, -e)) / Math.LN2;
  }

  /*
   * log2(delta_n(a)) from Iwata–Ohashi–Minematsu, Equation (22):
   *
   *   delta_n(a) = (1 - (a - 1)/2^n)^(-a/2).
   *
   * lA is log2(a). Math.expm1/log1p preserve the small correction when
   * a is far below 2^n, which is the usual GCM operating range.
   */
  function log2GcmDelta(lA, n) {
    if (lA === -Infinity) return 0;
    if (!isFinite(lA) || lA >= n) return Infinity;
    var a = Math.pow(2, lA);
    var x = Math.expm1(lA * Math.LN2) * Math.pow(2, -n);
    if (x <= 0) return 0;
    if (x >= 1) return Infinity;
    return -(a / 2) * Math.log1p(-x) / Math.LN2;
  }

  /*
   * Maximum |AAD|_128 + |plaintext|_128 when only their combined byte length
   * is bounded. Poly1305 pads the two strings separately, so the worst split
   * can consume one more data block than ceil((|AAD| + |plaintext|) / 16).
   */
  function maxPoly1305DataBlocks(lBytes) {
    var bytes = Math.pow(2, lBytes);
    return Math.ceil((bytes + 15) / 16);
  }

  /*
   * Union bound on a same-key collision among independently uniform nonces.
   *
   * In the single-key setting, lM is Infinity and the bound is
   *
   *   q(q-1) / 2^(r+1).
   *
   * In the multi-key setting, q is the total number of protected messages
   * and M is the maximum under any one key.  If q_i is the number under key
   * i, then
   *
   *   sum_i q_i(q_i-1) / 2^(r+1)
   *     <= q(min(q,M)-1) / 2^(r+1).
   *
   * The min(q,M) makes the bound reduce to the single-key expression when
   * the aggregate usage has not yet reached M.  A missing lM deliberately
   * defaults to Infinity, which is the safe worst case where all messages
   * might use one key.
   */
  function randomNonceCollision(lq, nonceBits, lM) {
    if (lq === -Infinity) return -Infinity;
    if (lq === Infinity) return Infinity;
    var maxPerKey = lM === undefined ? Infinity : Math.max(0, lM);
    var pairWidth = Math.min(lq, maxPerKey);
    if (lq <= 0 || pairWidth <= 0) return -Infinity;
    return lq + log2PowMinusOne(pairWidth) - (nonceBits + 1);
  }

  // Invert randomNonceCollision on the log2(message-count) axis.
  function randomNonceLimit(lP, nonceBits, lM) {
    var maxPerKey = lM === undefined ? Infinity : Math.max(0, lM);
    if (maxPerKey === 0) return Infinity; // at most one message per key
    var lo = 0;
    var hi = Math.max(1, nonceBits + 2);
    // randomNonceCollision is monotone.  The fixed high endpoint is beyond
    // every meaningful root for the nonce sizes exposed by this module.
    for (var i = 0; i < 100; i++) {
      var mid = (lo + hi) / 2;
      if (randomNonceCollision(mid, nonceBits, maxPerKey) <= lP) lo = mid;
      else hi = mid;
    }
    return lo;
  }

  /* ---------- display formatting ---------- */

  function fmtPow(e, digits) {
    if (e === Infinity) return '∞';
    if (e === -Infinity) return '0';
    if (isNaN(e)) return 'n/a';
    var d = digits === undefined ? 1 : digits;
    if (Math.abs(e - Math.round(e)) < 1e-9) e = Math.round(e);
    return '2^' + e.toFixed(d).replace(/\.0+$/, '').replace(/(\.\d*?)0+$/, '$1');
  }

  function fmtNum(e) {
    if (e === Infinity) return '∞ (no limit)';
    if (e === -Infinity) return '0';
    if (isNaN(e)) return 'n/a';
    if (e < 0) return Math.pow(2, e).toExponential(2);
    if (e <= 64) {
      var v = Math.pow(2, e);
      return Math.round(v).toLocaleString('en-US');
    }
    // log10(2^e) = e / log2(10).
    var e10 = e / LOG2_10;
    var k = Math.floor(e10);
    var m = Math.pow(10, e10 - k);
    return m.toFixed(2) + ' × 10^' + k;
  }

  function fmtShort(e) {
    if (e === Infinity) return '∞';
    if (e === -Infinity) return '0';
    if (isNaN(e)) return 'n/a';
    if (e <= 30) return Math.round(Math.pow(2, e)).toLocaleString('en-US');
    return fmtPow(e, 1);
  }

  /* ---------- algorithm catalogue ---------- */

  var ALGORITHMS = {
    AEAD_AES_128_GCM: {
      name: 'AEAD_AES_128_GCM', family: 'GCM', k: 128, n: 128, t: 128, r: 96,
      blockBytes: 16
    },
    AEAD_AES_256_GCM: {
      name: 'AEAD_AES_256_GCM', family: 'GCM', k: 256, n: 128, t: 128, r: 96,
      blockBytes: 16
    },
    AEAD_CHACHA20_POLY1305: {
      name: 'AEAD_CHACHA20_POLY1305', family: 'ChaCha20-Poly1305',
      k: 256, n: 512, t: 128, r: 96,
      // Confidentiality uses 512-bit ChaCha20 blocks; the integrity term
      // counts Poly1305 blocks of 128 bits (L' in the draft). We expose
      // message size in bytes and convert per limit.
      blockBytes: 64, polyBlockBytes: 16
    },
    AEAD_AES_128_CCM: {
      name: 'AEAD_AES_128_CCM', family: 'CCM', k: 128, n: 128, t: 128, r: 96,
      blockBytes: 16
    },
    AEAD_AES_128_CCM_8: {
      name: 'AEAD_AES_128_CCM_8', family: 'CCM', k: 128, n: 128, t: 64, r: 96,
      blockBytes: 16
    },
    AEAD_AEGIS128L: {
      name: 'AEAD_AEGIS128L', family: 'AEGIS', k: 128, n: 128, t: 128, r: 128,
      tagBits: [128, 256], rateBytes: 32, differentialForgeryBits: 216
    },
    AEAD_AEGIS256: {
      name: 'AEAD_AEGIS256', family: 'AEGIS', k: 256, n: 128, t: 128, r: 256,
      tagBits: [128, 256], rateBytes: 16, differentialForgeryBits: 256
    }
  };

  /*
   * The AEGIS sources state security claims and attack complexities rather
   * than a reduction-style, q- and data-dependent advantage bound like the
   * bounds used elsewhere in this explorer. AEGIS v1.1 Claim 1 gives about
   * v/2^t success after v online forgery attempts for tags up to 128 bits.
   *
   * For a 256-bit tag, [SSI24] gives an exact 2^-216 differential
   * characteristic that directly yields a state-collision forgery against
   * AEGIS-128L. Repeating that chosen-message/verification trial v times gives
   * the attack-specific v/2^216 model when enough chosen-message material is
   * available. For AEGIS-256, generic 256-bit tag guessing is binding and the
   * paper supports 256-bit security against the differential attack class.
   */
  function applyAegisClaims(res, lP, lO, multiUser, selectedTagBits) {
    var alg = res.alg;
    var tagBits = selectedTagBits === 256 ? 256 : 128;
    // The cheapest modeled online forgery is either generic tag guessing or
    // the best differential forgery reported by SSI24.
    var forgeryBits = Math.min(tagBits, alg.differentialForgeryBits);
    res.ca = function () { return -Infinity; };
    res.ia = function (lv) { return lv - forgeryBits; };
    res.aea = function (lq, lv) {
      return log2sum(res.ia(lv), lO - alg.k);
    };
    res.qLimit = Infinity;
    res.vLimit = lP + forgeryBits;
    res.tagBits = tagBits;
    res.forgeryBits = forgeryBits;
    res.claimBased = true;

    if (tagBits === 128) {
      res.notes.push('AEGIS v1.1 Claim 1 says that v online forgery attempts ' +
        'succeed with probability about v/2^128. This is a design claim, not ' +
        'a reduction-style proof.');
    } else if (alg.differentialForgeryBits < tagBits) {
      res.notes.push('For AEGIS-128L, SSI24 gives a 2^-216 differential ' +
        'characteristic that directly yields a state-collision forgery. With ' +
        'one chosen-message source and one online verification per trial, the ' +
        'attack-specific model is about v/2^216 when enough source material is ' +
        'available. This is not a general reduction-style advantage proof.');
    } else {
      res.notes.push('For AEGIS-256 with a 256-bit tag, generic tag guessing ' +
        'gives about v/2^256 success, and SSI24 supports 256-bit security ' +
        'against the differential attack class it studies. This remains a ' +
        'claim-based model rather than a general reduction-style proof.');
    }
    res.notes.push('Birthday collisions among ' + tagBits + '-bit tag outputs ' +
      'become likely near 2^' + (tagBits / 2) + ' encrypted messages, but two ' +
      'already-valid tuples sharing a tag do not constitute a fresh forgery ' +
      'and do not imply an AEGIS internal-state collision. Therefore that ' +
      'output-collision probability does not add a q^2/2^' + tagBits +
      ' integrity term.');
    res.notes.push('The functional maximum for each plaintext and associated-data ' +
      'input is 2^61 - 1 bytes; the message-size control is far below that cap.');
    if (alg.r === 128) {
      res.notes.push('Nonces must not repeat. If they are chosen randomly, the ' +
        'AEGIS specification recommends at most 2^48 messages per key ' +
        '(about 2^-33 nonce-collision probability).');
    } else {
      res.notes.push('Nonces must not repeat. The AEGIS specification describes ' +
        'random 256-bit nonces as having no practical message-count limit.');
    }
    if (multiUser) {
      res.warnings.push('The AEGIS multi-key result assumes every key has a ' +
        'unique identifier encoded in unused nonce bits, which is the condition ' +
        'for the specification\'s no-multi-target-advantage statement. Without ' +
        'that domain separation, the cited sources do not provide a quantitative ' +
        'multi-user advantage bound.');
    }
    return res;
  }

  /* =====================================================================
   * Single-key setting (Section 6)
   * =====================================================================
   * params:  lP (target advantage p, log2), lL (max message length in
   *          blocks, log2), lO (offline work, log2), tagBits (AEGIS only).
   * returns: advantage functions (log2 q/v -> log2 advantage) and
   *          inverse limits (log2 count), plus assumption warnings.
   */
  function singleKey(algName, lP, lL, lO, tagBits) {
    var alg = ALGORITHMS[algName];
    var res = {
      alg: alg, setting: 'su',
      ca: null, ia: null, aea: null,   // advantage functions (log2 -> log2)
      qLimit: Infinity, vLimit: Infinity,
      warnings: [], notes: []
    };
    var fam = alg.family;
    var f;

    if (fam === 'AEGIS') {
      return applyAegisClaims(res, lP, lO, false, tagBits);
    } else if (fam === 'GCM') {
      // CA <= (s + q + 1)^2 / 2^129 with s <= q*L  (Section 6.2.1)
      res.ca = function (lq) {
        return 2 * log2sum(lq + lL, log2sum(lq, 0)) - 129;
      };
      res.qLimit = log2diff(lP / 2 + 64.5, 0) - Math.log2(Math.pow(2, lL) + 1);
      // exact form of the draft's (sqrt(p)*2^64.5 - 1)/(L+1)
      // Exact 96-bit-nonce integrity result from [GCMProofs], Equation (22):
      //
      // IA <= v*(L+1)/2^128 * delta_128(s+q+v+1), with s <= q*L.
      //
      // The draft replaces delta with 2 when s+q+v < 2^64. Evaluating delta
      // directly removes that simplifying assumption. Keep the draft's
      // independent v <= 2^64 cap.
      res.ia = function (lv, lq) {
        if (lq === undefined) lq = res.qLimit;
        var lA = log2sum(lq + lL, log2sum(lq, log2sum(lv, 0)));
        return lv + Math.log2(Math.pow(2, lL) + 1) - 128 +
          log2GcmDelta(lA, 128);
      };
      if (res.ia(64, res.qLimit) <= lP) {
        res.vLimit = 64;
      } else {
        var vlo = -1024, vhi = 64;
        for (var vi = 0; vi < 100; vi++) {
          var vmid = (vlo + vhi) / 2;
          if (res.ia(vmid, res.qLimit) <= lP) vlo = vmid;
          else vhi = vmid;
        }
        res.vLimit = vlo;
      }
      // Offline key search applies to every mode (Section 6.1).
      res.aea = function (lq, lv) {
        return log2sum(res.ca(lq), log2sum(res.ia(lv, lq), lO - alg.k));
      };
    } else if (fam === 'ChaCha20-Poly1305') {
      // CA <= 0: no limit beyond the PRF security of ChaCha20 (Section 6.3.1).
      res.ca = function () { return -Infinity; };
      res.qLimit = Infinity;
      // Corrected single-user theorem:
      //   IA <= v*epsilon(L')/2^128, epsilon(L') = 2^25*(L'+1).
      // This is algebraically equal to v*(L'+1)/2^103; evaluating epsilon
      // explicitly makes clear that 2^103 is not a rounded approximation.
      // Here lL is log2(L'), including the worst-case separate block rounding
      // of AAD and plaintext performed by compute().
      var lPolyEpsilon = 25 + Math.log2(Math.pow(2, lL) + 1);
      res.ia = function (lv) {
        return lv + lPolyEpsilon - 128;
      };
      res.vLimit = lP + 128 - lPolyEpsilon;
      res.aea = function (lq, lv) {
        return log2sum(res.ia(lv), lO - alg.k);
      };
      res.poly1305Epsilon = lPolyEpsilon;
      res.notes.push('Confidentiality: CA <= 0 — no limit on q beyond the ' +
        'PRF security of the ChaCha20 block function (and offline key search).');
    } else if (fam === 'CCM') {
      // CA <= (2Lq)^2 / 2^128  (Section 6.4.1)
      res.ca = function (lq) { return 2 * (1 + lL + lq) - 128; };
      // q <= sqrt(p)*2^64 / (2L) = sqrt(p)*2^63/L
      var qFromCA = lP / 2 + 63 - lL;
      // IA <= v/2^t + (2L(v+q))^2 / 2^128  (Section 6.4.2)
      res.ia = function (lv, lq) {
        return log2sum(lv - alg.t, 2 * (1 + lL + log2sum(lv, lq)) - 128);
      };
      res.aea = function (lq, lv) {
        return log2sum(res.ca(lq), log2sum(res.ia(lv, lq), lO - alg.k));
      };
      if (alg.t === 128) {
        // Draft simplification (v negligible next to the quadratic term):
        // v + q <= sqrt(p) * 2^63 / L.
        res.vLimit = lP / 2 + 63 - lL;
        res.qLimit = minLog2(qFromCA, res.vLimit);
        res.notes.push('Integrity limit uses the draft simplification ' +
          'v + q <= sqrt(p)·2^63/L, so q and v share one combined budget.');
      } else {
        // CCM_8: split the target evenly — v*2^64 <= p*2^127 gives
        // v <= p*2^63, and (2L(v+q))^2 <= p*2^127 gives the v+q budget
        // (Section 6.5).
        res.vLimit = lP + 63;
        var vq = (lP - 1) / 2 + 63 - lL;
        res.qLimit = minLog2(qFromCA, log2diff(vq, res.vLimit));
        res.notes.push('Short 64-bit tag: the draft splits the target as ' +
          'v·2^64 <= p·2^127 and (2L(v+q))^2 <= p·2^127, which makes v the ' +
          'binding constraint and allows a slightly larger q.');
      }
    }
    return res;
  }

  /* =====================================================================
   * Multi-key setting (Section 7)
   * =====================================================================
   * params:  lP, lL, lO and tagBits as above; lB = log2(max blocks encrypted
   *          by any key), nonceMode = 'randomized' (TLS 1.3 / QUIC style
   *          nonce randomization) or 'implicit' (random partially implicit
   *          nonces, TLS 1.2 style — GCM only).
   */
  function multiKey(algName, lP, lL, lO, lB, nonceMode, tagBits) {
    var alg = ALGORITHMS[algName];
    var res = {
      alg: alg, setting: 'mu', nonceMode: nonceMode,
      ca: null, ia: null, aea: null,
      qLimit: Infinity, vLimit: Infinity,
      warnings: [], notes: []
    };
    var fam = alg.family;

    if (fam === 'AEGIS') {
      return applyAegisClaims(res, lP, lO, true, tagBits);
    } else if (fam === 'GCM') {
      if (nonceMode === 'implicit') {
        // Random, partially implicit nonces (Theorem 5.3 of [GCM-MU2]).
        // AEA <= ((q+v)*o + (q+v)^2)/2^(k+26) + (q+v)*L*B/2^127
        var gcmAeTerm = function (lx) {
          return log2sum(log2sum(lx + lO, 2 * lx) - (alg.k + 26),
                         lx + lL + lB - 127);
        };
        res.aea = function (lq, lv) { return gcmAeTerm(log2sum(lq, lv)); };
        res.ca = function (lq) {
          return log2sum(log2sum(lq + lO, 2 * lq) - (alg.k + 26),
                         lq + lL + lB - 127);
        };
        res.ia = res.aea; // IA <= AEA (Section 7.1.3)
        if (alg.k === 256) {
          // First term negligible: q+v <= p*2^127/(L*B).
          // The draft's examples assume equal proportions for q and v,
          // so each individually gets half of the combined budget.
          res.qLimit = lP + 126 - lL - lB;
          res.vLimit = res.qLimit;
          res.notes.push('With k = 256 the offline-work term of the TLS 1.2 ' +
            'style bound is negligible, so the limit matches nonce randomization.');
        } else {
          // k = 128, assuming o <= q+v:
          // q+v <= min(sqrt(p)*2^76, p*2^126/(L*B)); halved for q and v
          // individually under the equal-proportions assumption.
          res.qLimit = minLog2(lP / 2 + 75, lP + 125 - lL - lB);
          res.vLimit = res.qLimit;
          res.notes.push('k = 128 with o <= q+v assumed: ' +
            'q+v <= min(√p·2^76, p·2^126/(L·B)).');
        }
      } else {
        // Nonce randomization: AEA <= (q+v)*L*B/2^127  (Section 7.1.1)
        res.aea = function (lq, lv) {
          return log2sum(lq, lv) + lL + lB - 127;
        };
        res.ca = function (lq) { return lq + lL + lB - 127; };
        res.ia = res.aea;
        // The draft's example table (Table 3) assumes equal proportions for
        // q and v, i.e. each gets half of the combined q+v budget:
        // q, v <= p*2^126/(L*B), written there as 2^69/B for p = 2^-50.
        res.qLimit = lP + 126 - lL - lB;
        res.vLimit = res.qLimit;
        res.notes.push('q and v share the combined budget ' +
          'q+v <= p·2^127/(L·B); shown per-value assuming equal proportions, ' +
          'as in the draft example table.');
        if (lB < Math.log2(100)) {
          res.warnings.push('Assumption B ≫ 100 is not met (B ≈ 2^' +
            lB.toFixed(1) + '). The draft says B should be increased by ' +
            (alg.k === 128 ? '161' : '97') + ' in this regime; the limits ' +
            'shown are optimistic. (Section 7.1.1)');
        }
        if (alg.k === 128 && lO > 70) {
          res.warnings.push('For AEAD_AES_128_GCM the bound assumes ' +
            'o <= 2^70; above that a term of order o/2^120 starts ' +
            'dominating and is not modelled here. (Section 7.1.1)');
        }
      }
    } else if (fam === 'ChaCha20-Poly1305') {
      // Exact nonce-randomized multi-user bound from [ChaCha20Poly1305-MU],
      // Theorem 7.2, instantiated with n=512, k=256, t=128 and mu=96.
      // The draft retains only the dominant v*epsilon(L')/2^128 term.
      var lMultiPolyEpsilon = 25 + Math.log2(Math.pow(2, lL) + 1);
      var lMultiPolyEpsilonPlus3 = log2sum(lMultiPolyEpsilon, Math.log2(3));
      // All allowed bytes may be plaintext, so this is the maximum number of
      // encrypted 512-bit ChaCha20 blocks in one query.
      var messageBlocks = Math.max(1,
        Math.ceil((Math.pow(2, lL) - 1) / 4));
      var lMessageBlocks = Math.log2(messageBlocks);

      function exactChaChaMultiAea(lq, lv) {
        var bound = log2sum(
          lv + lMultiPolyEpsilonPlus3 - 128,
          log2sum(
            1 + lO + Math.log2(512 - 256) - 256,
            log2sum(
              1 + lv + Math.log2(512 - 256 + 4 * 128) - 256,
              log2sum(-254, -254))));

        if (lq === -Infinity) return bound;

        var lSigma = lq + lMessageBlocks;
        bound = log2sum(bound, 2 * log2sum(lSigma, lq) - 513);

        // The theorem permits any delta > 0. For each integer d, the largest
        // delta that leaves d unchanged minimizes the nonce-randomization
        // term. The remaining discrete objective
        //
        //   d*(o+q)/2^256 + 2^(-delta*96)
        //
        // is convex. Evaluate the integers around its stationary point and
        // the smallest d satisfying Theorem 7.2's q-range condition.
        var denominator = Math.max(1, 96 - lq);
        var dScale = 96 / denominator;
        var deltaRequired = lq > 100 ? Math.pow(2, lq - 100) - 1 : 0;
        var dRequired = deltaRequired > 0
          ? Math.ceil(dScale * (deltaRequired + 1)) - 1
          : Math.floor(dScale);
        var lWorkAndQueries = log2sum(lO, lq);
        var lCoefficient = lWorkAndQueries - 256;
        var stationary = (96 - lCoefficient +
          Math.log2(Math.LN2 * denominator)) / denominator - 1;
        var center = Math.max(dRequired, stationary);
        var candidates = [
          dRequired,
          Math.max(dRequired, Math.floor(center) - 1),
          Math.max(dRequired, Math.floor(center)),
          Math.max(dRequired, Math.ceil(center)),
          Math.max(dRequired, Math.ceil(center) + 1)
        ];
        var bestVariable = Infinity;
        for (var ci = 0; ci < candidates.length; ci++) {
          var d = candidates[ci];
          var delta = ((d + 1) * denominator / 96) - 1;
          if (delta <= 0 ||
              lq > 96 + Math.log2((delta + 1) * 96 / 6) + 1e-12) {
            continue;
          }
          var dTerm = d === 0
            ? -Infinity
            : Math.log2(d) + lCoefficient;
          var variable = log2sum(dTerm, -delta * 96);
          if (variable < bestVariable) bestVariable = variable;
        }
        return log2sum(bound, bestVariable);
      }

      function solveExactLimit(fn, cap) {
        if (fn(-Infinity) > lP) return -Infinity;
        if (fn(cap) <= lP) return cap;
        var lo = -1024, hi = cap;
        for (var i = 0; i < 100; i++) {
          var mid = (lo + hi) / 2;
          if (fn(mid) <= lP) lo = mid;
          else hi = mid;
        }
        return lo;
      }

      res.aea = exactChaChaMultiAea;
      res.ia = function (lv, lq) {
        return exactChaChaMultiAea(
          lq === undefined ? -Infinity : lq, lv);
      };
      res.ca = function (lq) {
        return exactChaChaMultiAea(lq, -Infinity);
      };
      var lSigmaCap = 256 + Math.log2(256 / 6);
      var lQTheoremCap = lSigmaCap - lMessageBlocks;
      res.qLimit = solveExactLimit(res.ca, lQTheoremCap);
      res.vLimit = solveExactLimit(function (lv) {
        return res.ia(lv);
      }, 510);
      if (res.qLimit === lQTheoremCap) {
        res.qLimitReason = 'theorem encrypted-block cap';
      }
      res.poly1305Epsilon = lMultiPolyEpsilon;
      res.chachaMessageBlocks = messageBlocks;
      res.notes.push('Uses every term of the nonce-randomized multi-user ' +
        'bound in Theorem 7.2 and minimizes its delta/d tradeoff. q and v ' +
        'are totals across all keys; L\' is the maximum per query.');
      if (nonceMode === 'implicit') {
        res.warnings.push('The exact multi-key calculation shown is for the ' +
          '96-bit XN nonce-randomization transform, not the TLS 1.2-style ' +
          'partially implicit nonce construction selected here.');
      }
    } else if (fam === 'CCM') {
      // AEA <= (q+v)*L*B/2^127 + v/2^t + o/2^(k-6); assuming o <= q+v the
      // draft splits the target evenly across the first two terms
      // (Section 7.3). C = max blocks encrypted or decrypted by any key.
      res.aea = function (lq, lv) {
        return log2sum(log2sum(lq, lv) + lL + lB - 127,
                       log2sum(lv - alg.t, lO - (alg.k - 6)));
      };
      res.ca = function (lq) { return lq + lL + lB - 127; };
      res.ia = function (lv) { return lv - alg.t; };
      res.qLimit = lP - 1 + 127 - lL - lB; // even split: first term gets p/2
      res.vLimit = minLog2(lP - 1 + alg.t, res.qLimit);
      res.notes.push('Assumes o <= q+v and splits the target evenly between ' +
        'the (q+v)L·C/2^127 and v/2^t terms. The UI field is C (blocks ' +
        'encrypted or decrypted per key).');
      if (alg.t === 64) {
        res.notes.push('With the 64-bit tag, v <= p·2^(t-1) is usually the ' +
          'binding constraint.');
      }
    }
    return res;
  }

  /*
   * Compose a nonce-respecting result with the probability that independently
   * sampled nonces repeat under one key.  The existing q/v limits are
   * evaluated at half of the requested advantage and the other half is
   * reserved for the collision event.  Each affected CA, IA, or AEA expression
   * is composed from those two terms.  This does not change the underlying
   * result's conventions for allocating simultaneous q and v.
   *
   * The caller has already evaluated the conditional result at lP - 1 when a
   * collision is possible.  lM is log2(max protected messages per key) in the
   * multi-key setting and Infinity in the single-key setting.
   */
  function applyRandomNonces(res, lP, lM) {
    var alg = res.alg;
    var multiUser = res.setting === 'mu';
    var maxPerKey = multiUser
      ? (lM === undefined ? Infinity : Math.max(0, lM))
      : Infinity;
    var collisionPossible = maxPerKey !== 0;
    var collisionTarget = collisionPossible ? lP - 1 : -Infinity;
    var baseCA = res.ca;
    var baseIA = res.ia;
    var baseAEA = res.aea;

    res.nonceMode = 'random';
    res.randomNonces = true;
    res.randomNonceBits = alg.r;
    res.lM = maxPerKey;
    res.conditionalQLimit = res.qLimit;
    res.conditionalVLimit = res.vLimit;
    res.collisionBudget = collisionTarget;
    res.nonceCollision = function (lq) {
      return randomNonceCollision(lq, alg.r, maxPerKey);
    };
    res.nonceRespectingCa = baseCA;
    res.nonceRespectingIa = baseIA;
    res.nonceRespectingAea = baseAEA;

    if (baseCA) {
      res.ca = function (lq) {
        return log2sum(baseCA(lq), res.nonceCollision(lq));
      };
    }
    if (baseIA) {
      res.ia = function (lv, lq) {
        var conditional = baseIA.length >= 2 ? baseIA(lv, lq) : baseIA(lv);
        var collision = lq === undefined ? -Infinity : res.nonceCollision(lq);
        return log2sum(conditional, collision);
      };
    }
    if (baseAEA) {
      res.aea = function (lq, lv) {
        return log2sum(baseAEA(lq, lv), res.nonceCollision(lq));
      };
    }

    res.collisionLimit = collisionPossible
      ? randomNonceLimit(collisionTarget, alg.r, maxPerKey)
      : Infinity;
    if (res.collisionLimit < res.qLimit) {
      res.qLimit = res.collisionLimit;
      res.qLimitReason = 'nonce collision';
    }

    if (collisionPossible) {
      res.notes.push('Random-nonce mode evaluates the nonce-respecting q/v ' +
        'limits at half of the target advantage and reserves the other half ' +
        'for same-key nonce collisions. The collision probability is bounded by ' +
        (multiUser
          ? 'q·(min(q,M)-1)/2^(' + (alg.r + 1) + '), where M is the maximum messages per key.'
          : 'q·(q-1)/2^' + (alg.r + 1) + '.')
      );
    } else {
      res.notes.push('With at most one protected message per key, independently ' +
        'sampled nonces cannot collide under the same key, so no collision ' +
        'budget is needed.');
    }
    res.notes.push('The random-nonce calculation assumes independent, uniform, ' +
      'full-width samples from a cryptographically secure random generator ' +
      'and treats any same-key repeat as a security failure.');
    if (multiUser) {
      res.warnings.push('The AEAD-limits draft gives the concrete multi-key ' +
        'bounds used here for nonce randomization, not for independently ' +
        'sampled full nonces. This view uses that result as a conditional ' +
        'model and adds the same-key collision event; it is not a dedicated ' +
        'random-nonce multi-key proof.');
    }

    // Algorithm specifications impose requirements beyond the probability
    // calculation.  Keep those visible and, where a per-key numerical cap is
    // stated, enforce it for a single key and validate M for multiple keys.
    var perKeyCap;
    if (alg.family === 'GCM') {
      perKeyCap = 32;
      res.notes.push('NIST SP 800-38D permits its RBG-based IV construction ' +
        'but limits authenticated-encryption invocations to 2^32 per key ' +
        'across supported IV lengths.');
    } else if (alg.family === 'ChaCha20-Poly1305') {
      res.notes.push('RFC 8439 specifies unique, non-random nonces for its ' +
        'ChaCha20-Poly1305 profile. This independent-random-nonce view is a ' +
        'probabilistic construction outside that profile: it conditions the ' +
        'AEAD bound on no repeat and adds the same-key collision probability.');
    } else if (alg.family === 'CCM') {
      res.warnings.push('CCM requires a unique nonce for every invocation ' +
        'with a key. Independent random sampling cannot guarantee uniqueness; ' +
        'the numerical result illustrates collision risk rather than a ' +
        'conforming CCM nonce construction.');
    } else if (alg.name === 'AEAD_AEGIS128L') {
      perKeyCap = 48;
    }

    if (perKeyCap !== undefined) {
      res.randomNoncePerKeyCap = perKeyCap;
      if (!multiUser && perKeyCap < res.qLimit) {
        res.qLimit = perKeyCap;
        res.qLimitReason = alg.family === 'GCM'
          ? 'random-nonce invocation cap'
          : 'random-nonce guidance';
      } else if (multiUser && maxPerKey > perKeyCap) {
        res.warnings.push('M exceeds the ' + alg.name + ' per-key random-nonce ' +
          (alg.family === 'GCM' ? 'invocation cap' : 'guidance') +
          ' of 2^' + perKeyCap + '. Reduce M or rekey earlier.');
      }
    }

    // Make the displayed integrity limit usable together with the displayed
    // confidentiality limit: if the underlying convention leaves IA slightly
    // above p at (qLimit, vLimit), tighten v monotonically until the composed
    // IA reaches p.  This matters in particular for CCM, whose integrity term
    // contains q and v together.
    if (res.ia && isFinite(res.vLimit) &&
        res.ia(res.vLimit, res.qLimit) > lP) {
      var lo = -1024;
      var hi = res.vLimit;
      if (res.ia(-Infinity, res.qLimit) > lP) {
        res.vLimit = -Infinity;
      } else {
        for (var i = 0; i < 100; i++) {
          var mid = (lo + hi) / 2;
          if (res.ia(mid, res.qLimit) <= lP) lo = mid;
          else hi = mid;
        }
        res.vLimit = lo;
      }
      res.vLimitReason = 'at the displayed q limit';
    }
    return res;
  }

  /* ---------- orchestration ---------- */

  // opts: { alg, setting, nonceMode, tagBits, lP, lLBytes, lO, lB, lM }
  // lLBytes: log2 of max message size in BYTES (plaintext + AAD).
  // lB: log2 of max blocks (128-bit) encrypted (B) or encrypted+decrypted
  //     (C) per key, multi-key only.
  // lM: log2 of max protected messages per key, used for independently random
  //     nonces in the multi-key setting. If omitted, all q messages are
  //     conservatively allowed to fall under one key.
  function compute(opts) {
    var alg = ALGORITHMS[opts.alg];
    // Convert the byte length into the block count used by each bound.
    // GCM/CCM use 128-bit blocks. For ChaCha20-Poly1305, L' is
    // ceil(|AAD|/16) + ceil(|plaintext|/16); because the UI bounds their sum,
    // use the largest L' possible over every split of that byte allowance.
    // The claim-based AEGIS model does not depend on lL.
    var lL = opts.lLBytes - 4; // log2(bytes/16)
    if (lL < 0) lL = 0;
    var poly1305Blocks;
    if (alg.family === 'ChaCha20-Poly1305') {
      poly1305Blocks = maxPoly1305DataBlocks(opts.lLBytes);
      lL = Math.log2(poly1305Blocks);
    }
    var nonceMode = opts.nonceMode || 'randomized';
    var lM = opts.lM === undefined ? Infinity : Math.max(0, opts.lM);
    var collisionPossible = nonceMode === 'random' &&
      (opts.setting !== 'mu' || lM !== 0);
    var conditionalTarget = collisionPossible ? opts.lP - 1 : opts.lP;
    // The published multi-key formulas use nonce randomization. For the
    // independently random option we expose their use as a conditional model,
    // then add the collision bad event and warn that this is not a dedicated
    // random-nonce multi-key proof.
    var conditionalNonceMode = nonceMode === 'implicit' ? 'implicit' : 'randomized';
    var r = opts.setting === 'mu'
      ? multiKey(opts.alg, conditionalTarget, lL, opts.lO, opts.lB,
                 conditionalNonceMode, opts.tagBits)
      : singleKey(opts.alg, conditionalTarget, lL, opts.lO, opts.tagBits);
    r.lL = lL;
    if (poly1305Blocks !== undefined) r.poly1305Blocks = poly1305Blocks;
    r.targetAdvantage = opts.lP;
    r.conditionalTarget = conditionalTarget;
    if (nonceMode === 'random') applyRandomNonces(r, opts.lP, lM);
    else r.nonceMode = nonceMode;
    return r;
  }

  var API = {
    ALGORITHMS: ALGORITHMS,
    compute: compute,
    singleKey: singleKey,
    multiKey: multiKey,
    log2sum: log2sum,
    log2diff: log2diff,
    minLog2: minLog2,
    solveQuadUsage: solveQuadUsage,
    log2PowMinusOne: log2PowMinusOne,
    log2GcmDelta: log2GcmDelta,
    maxPoly1305DataBlocks: maxPoly1305DataBlocks,
    randomNonceCollision: randomNonceCollision,
    randomNonceLimit: randomNonceLimit,
    fmtPow: fmtPow,
    fmtNum: fmtNum,
    fmtShort: fmtShort,
    LOG2_10: LOG2_10
  };

  if (typeof module !== 'undefined' && module.exports) module.exports = API;
  else global.AEADLimits = API;
})(typeof window !== 'undefined' ? window : globalThis);