Random-Access Authenticated Encryption

1.1. Related Work

CHAIN ([HRRV15]) is a segmented authenticated-encryption construction that chains state from one segment to the next. It is sequential by construction and supports neither independent random-access reads nor in-place segment rewrites.¶

STREAM ([HRRV15]) turns a nonce-based AEAD into a segmented construction using induced nonces that encode a message nonce, the segment index, and a final-segment bit. STREAM supports random-access decryption and encryption of individual segments, but defines neither authenticated snapshots nor authenticated rewrites. SEAL's derived nonce mode (Section 4.5.3.2) follows STREAM's counter-plus-final-bit structure and adds those operations.¶

Tink Streaming AEAD ([Tink]) and OpenPGP v2 Symmetrically Encrypted and Integrity Protected Data (SEIPD) packets ([RFC9580]) are deployed STREAM-family formats. Both derive a message key and nonce prefix from a key and a salt, encrypt each chunk under an AEAD nonce carrying the chunk index, and detect truncation with a final tag over the empty string. Tink derives an AES-GCM key with the HMAC-based Key Derivation Function (HKDF) ([RFC5869]), while v2 SEIPD selects its cipher and AEAD from packet identifiers. Each chunk is independently authenticated and can be verified locally at its boundary. Neither format defines an in-place rewrite operation or a snapshot authenticator over an updatable set of segment tags.¶

SEAL's snapshot authenticator addresses exactly that gap. Its per-segment input is the segment leaf (Section 4.7.2), which binds the segment's content when the ciphertext digest is set. It verifies the whole segment set against the snapshot, and optionally a designated subset (Section 4.7.1). A consuming protocol that authenticates the one keyed snapshot obtains integrity over the whole segment set and its count. Where the ciphertext digest is set over a strict ordering (Section 4.7.1), the authenticated snapshot also pins each index to one ciphertext, even against holders of the content-encryption key (CEK).¶

Tahoe-LAFS ([TAHOE]) authenticates separately encrypted pieces with a signed Merkle tree: it encrypts a mutable file in segments, builds Merkle hash trees over its erasure-coded blocks, and has the writer sign a value that includes the tree's root with an RSA key, so a reader checks one segment against the signature through the hashes on its path. A signature over an unkeyed root gives integrity and origin to a verifier that holds no decryption key. SEAL's keyed snapshot does not do that on its own. The counterpart in SEAL is the public snapshot that every strict authenticator defines, for a consuming protocol to sign (Section 4.7.3).¶

Fábrega et al. ([FLRR25]) formalized random-access AEAD security over a raAE primitive syntax in which segment encryption and decryption may be invoked in arbitrary order, and gave a construction, FLOE (Fast Lightweight Online Encryption), proved to meet it. FLOE realizes the base interface: segments are written once, and there is no snapshot. SEAL realizes that primitive with the extension of this document, and Section 5.1 defines the security notions used in its analysis.¶

Each precedent covers part of the random-access AE design space. raAE is the abstract interface that generalizes the family with three capabilities none of the precedents combines: arbitrary-order encryption, in-place authenticated rewrite, and a snapshot over the whole segment set. SEAL realizes all three in one construction.¶

2.1. Taxonomy

raAE primitive:

The abstract random-access AE interface and security target.¶

Extended raAE interface:

The base interface plus snapshot maintenance and verification.¶

SEAL construction:

The construction specified in Section 4.¶

Cipher suite:

The AEAD and KDF algorithms and their sizes.¶

Profile:

A named set of fixed parameter choices, identified by a protocol_id, needed for interoperability.¶

Parameter set:

The per-object values that affect derivation and verification.¶

Consuming protocol:

The protocol or format that stores objects and manages keys.¶

Serialization:

The consuming protocol's wire or storage encoding.¶

Segment:

A zero-based independently encrypted plaintext unit.¶

Epoch:

A group of 2^epoch_length segment indices sharing one epoch key.¶

Keyed snapshot:

The value, computed under snap_key, that authenticates one segment set when a snapshot authenticator is configured.¶

Snapshot authenticator:

A pluggable SEAL component that produces and verifies the snapshot. Its abstract interface is Section 4.7.1, and its concrete instantiations are in [I-D.sullivan-seal-concrete].¶

Public snapshot:

The unkeyed counterpart of the keyed snapshot, which a strict snapshot authenticator defines for a verifier that holds no key: a snapshot of the same leaves, payload_info, the commitment, and the count, computed with an empty ikm in place of snap_key (Section 4.7.3).¶

Per-segment authenticity:

AEAD verification for one segment only.¶

Snapshot integrity:

Verification of the segment set, or of a designated subset or, by prefix verification, a prefix of it, against the snapshot.¶

Ciphertext digest:

LH(ct_i) (Section 4.3), the digest of one segment's ciphertext, stored in that segment's metadata and carried first in the strict authenticators' leaf when the instantiation sets it; the payload_info parameter segment_commitment selects it. It binds the segment's content, not its position (Section 4.7.1), and is distinct from the commitment, which binds the CEK, payload_info, and G.¶

External freshness:

Rollback protection supplied outside raAE.¶

2.2. Notation

I2OSP(n, w):

The w-octet big-endian encoding of the non-negative integer n, as defined in [RFC8017].¶

uint8(n), uint16(n), uint32(n), uint64(n):

Shorthand for I2OSP(n, 1), I2OSP(n, 2), I2OSP(n, 4), and I2OSP(n, 8) respectively.¶

||:

Octet string concatenation.¶

XOR:

Bitwise exclusive-or of two octet strings of equal length.¶

X[a:b]:

Octets a through b-1 inclusive of X (zero-based, half-open interval).¶

[x, y, ...]:

An ordered list of octet strings. A single-element list is written [x]. The brackets denote a list, not an optional parameter.¶

frame, encode:

The length-prefixed injective encoding used by SEAL, defined in Section 4.3. frame is total over all field lengths. The construction requires an injective framing (Section 5.4) but does not mandate this encoding. Another profile MAY use any injective encoding that meets Section 5.4.¶

Nk:

Key size in octets for the chosen AEAD algorithm.¶

Nn:

Nonce size in octets for the chosen AEAD algorithm.¶

Np:

Presented nonce size in octets: the per-segment nonce stored in metadata. Np = Nn in random nonce mode (Section 4.5.3) and Np = 0 in derived nonce mode (Section 4.5.3.2), where the nonce is recomputed from the key schedule.¶

Nh:

Hash or pseudorandom function (PRF) output size in octets for the chosen KDF.¶

Nt:

Authentication tag size in octets for the chosen AEAD algorithm.¶

Nb:

Cipher block size in octets for the chosen AEAD algorithm, defined only for an AEAD built on a block cipher. The block-size birthday limit of Section 5.8 is expressed in Nb and does not apply to an AEAD with no block-cipher structure.¶

Na:

The keyed snapshot length in octets, the output size of the configured snapshot authenticator. It MAY depend on the segment count n_seg, and is 0 when none (Section 4.7).¶

n_seg:

The number of ciphertext segments in a stored message. Written n_seg (lowercase) to distinguish it from the per-message nonce N in the raAE interface (Section 3.2).¶

n_ep:

The number of epochs in a stored message, ceil(n_seg / 2^epoch_length).¶

3.1. Overview

Random-access authenticated encryption (raAE) partitions a message into segments, each encrypted and decrypted on its own and in any order. A reader can open one segment without the rest of the message, and a writer can encrypt one without holding the others. In the base interface [FLRR25], each segment is written once and thereafter only read.¶

The extended raAE interface keeps that base and adds one capability: a segment already written may be replaced in place, without disturbing the rest. Rewriting changes the threat model. Per-segment authentication binds each segment in isolation, so it cannot tie the segments a reader assembles to a single recorded version of the object: a storage layer holding the ciphertext can roll a segment back to an older valid copy, substitute one valid same-index segment for another, or drop one, and each segment it presents still authenticates. An optional snapshot authenticates the segment set as the writer recorded it, so a reader can detect these changes. The extension (Section 3.3) defines the snapshot and the operations that maintain it.¶

The security notions follow the interface. raAE and its rewrites target ra-ROR (random-access real-or-random) and ra-CMT (random-access context commitment) (Section 5.1). Rewriting leaves the ra-CMT definition untouched, and the ra-ROR definition too in random nonce mode (Section 4.5.3), since replacing a segment there is an encryption the read-only adversary could already ask for. In derived nonce mode a rewrite is deterministic and relies on an equality-leakage relaxation of ra-ROR (Appendix C.5), and in any nonce mode the ra-ROR bounds of [FLRR25] do not cover it (Section 5.1.1). Snapshot authentication adds the one notion of its own, snapshot integrity (Section 5.1.4).¶

3.2. Interface

The base raAE interface, from [FLRR25], is a tuple of five algorithms: KeyGen, StartEnc, EncSeg, StartDec, and DecSeg.¶

KeyGen:

Randomized key generation. Takes no input. Outputs a secret key K.¶

StartEnc(K, N, G):

Deterministic. Takes a secret key K, nonce N, and global associated data G. Outputs a ciphertext header T_g and an initial per-message encryption state S.¶

EncSeg(S, p, A_i, M_i):

Randomized. Takes the encryption state S, a position identifier p, per-segment associated data A_i, and message segment M_i. Outputs a ciphertext segment C_i. S is not modified. EncSeg may be called with the same S at any position, in any order, or concurrently.¶

StartDec(K, N, G, T_g):

Deterministic. Takes key K, nonce N, global associated data G, and ciphertext header T_g. Outputs a per-message decryption state S or an error.¶

DecSeg(S, p, A_i, C_i):

Deterministic. Takes the decryption state S, position identifier p, per-segment associated data A_i, and ciphertext segment C_i. Outputs message segment M_i or an error.¶

The position identifier p = (i, b) consists of a segment number i and a terminal bit b in {0, 1}. They impose a total ordering on segments and carry a truncation defense: a ciphertext lacking a segment with b = 1 is incomplete. The encryption state S is immutable, so EncSeg calls are order-independent and can run in parallel. The ciphertext header T_g commits to K, the nonce N, and global associated data G. A headerless scheme emits T_g = empty.¶

3.3. Extended Interface

Replacing a segment already written, without re-encrypting the others, requires no new operation: re-encrypting a position is an ordinary EncSeg call over the immutable state. The ra-CMT definition applies to it unchanged, and so does the ra-ROR definition in random nonce mode (Section 5.1.1).¶

A scheme that supports rewriting MAY carry a snapshot, a value over the current set of segments that a reader checks to detect tampering that per-segment authentication does not catch. A write-once scheme MAY carry one too: a single value that a consuming protocol authenticates once for the whole segment set (Section 4.7.1).¶

Two operations, added by this document, maintain and check the snapshot. RewriteSeg replaces a segment and updates the snapshot in the same step. SnapVerify decides whether a given set of segments is one the writer recorded under the snapshot presented.¶

The keyed snapshot is a deterministic function of the per-message state, the (index, input) set, and the count. It is not part of the immutable encryption state S. The add, remove, set_length, and snapshot() operations of Section 4.7.1 update it over the writer's (index, input) set or over the authenticator's summary of that set, and the consuming protocol serializes those updates as that section requires. The verify() operation runs over the (index, input) set recomputed from the segments presented to SnapVerify, with any witness it is given.¶

RewriteSeg(S, p, A_i, M'_i, C_i, snapshot, witness):

Randomized. Takes the encryption state S and position identifier p, per-segment associated data A_i, the new message segment M'_i, the existing ciphertext C_i at position p, the current snapshot, and a witness for the segment set before the update. Outputs replacement ciphertext C'_i and an updated keyed snapshot, snapshot', together with the updated summary where the authenticator keeps one.¶

SnapVerify(S, segments, snapshot, witness):

Deterministic. Takes a per-message state S, either the encryption state from StartEnc or the decryption state from StartDec, the segments to verify as (position, ciphertext segment, A_i) triples, with A_i empty where a segment has none, the snapshot, which the caller declares complete or open (an intermediate snapshot), and a witness, which is empty for the whole-object target. The segments are either the whole current object state or, where the authenticator supports it, a designated subset of it. Outputs accept or reject.¶

The extension also adds an output to StartEnc. In the extended interface:¶

StartEnc(K, N, G):

Deterministic. As in Section 3.2, and additionally outputs the initial keyed snapshot, the snapshot over the empty segment set.¶

EncSeg retains its base signature and outputs only C_i. The caller adds C_i to the object by updating the snapshot over the new (index, input) set and count with the authenticator's operations (Section 4.7.1), in place from a summary or by recomputing.¶

These additions define the extended raAE interface of this document: the tuple (KeyGen, StartEnc, EncSeg, StartDec, DecSeg, RewriteSeg, SnapVerify) over the keyed snapshot.¶

Changing a message's length is a composition of these operations, not a separate algorithm in either direction. Position-addressed encryption over immutable state already permits re-encrypting a position or encrypting at a higher index (see Section 5.1.1).¶

A holder appends by encrypting the new segments and re-marking the old final segment with RewriteSeg, which re-encrypts its existing plaintext to clear its terminal bit. It truncates to the first m segments by dropping the segments at index m and above and re-marking segment m-1 with RewriteSeg, which re-encrypts its existing plaintext to set its terminal bit. Appending to an empty object skips the re-mark, since there is no old final segment, and truncating to zero segments yields the empty object. Each length change updates the snapshot, and Section 4.9.3 gives the construction for both directions.¶

4.1. Construction Overview

The commitment lets a reader reject a wrong key or parameter set before decrypting. The snapshot, when present, authenticates the current segment set. SEAL realizes the raAE operations of Section 3.2 as follows:¶

SEAL's salt, payload_info, and G carry the raAE per-message inputs, and the commitment stands in for the header (Section 4.2).¶

4.2. Component Suite and Parameters

SEAL fixes the segment additional authenticated data (AAD) encoding (Section 4.4.2), the commitment derivation (Section 4.6), and the keyed snapshot (Section 4.7) identically across all suites. Their octet lengths still vary by suite, because Nh and Nt are suite-dependent.¶

4.3. The KDF Combiner

The KDF combiner uses a length-prefixed encoding for all of its inputs.¶

frame(x):
    if len(x) <= 0xFFFE:  return uint16(len(x)) || x     ;; literal
    else:                 return uint16(0xFFFF) || LH(x) ;; digest

encode(x1, ..., xn) = frame(x1) || ... || frame(xn)

frame is total over every field length. A field too large to emit literally is instead prefixed by the reserved length 0xFFFF and an Nh-octet digest LH(x).¶

LH(x), the over-large-field digest, runs the cipher suite's native KDF primitive directly on x, invoking neither encode nor frame, and returns Nh octets. The two-step and one-step classes are HPKE's: a two-step KDF ([RFC9180]) uses its extract step, and a one-step KDF ([I-D.ietf-hpke-pq]) its XOF, with x carried under the label "raAE-LP-v1":¶

two-step:  LH(x) = Extract("raAE-LP-v1", x)
one-step:  LH(x) = XOF("raAE-LP-v1" || x, Nh)

Running LH through the full KDF would re-enter frame on the over-large x and recurse. The direct native call avoids that.¶

Section 5.4 requires the construction to justify the collision resistance of the over-large-field digest. LH's is that of the cipher suite's KDF primitive at the suite's Nh. In the two-step class LH(x) is HMAC under the fixed public key "raAE-LP-v1", so a collision in LH yields a collision in the underlying hash: with the key fixed, an HMAC collision on distinct inputs is a collision of its inner or its outer hash call. In the one-step class LH(x) is the XOF itself over a domain-separated input, so a collision in LH is a collision in the XOF at that output length.¶

The injectivity of encode, and LH's domain separation from the literal encoding, are established in Section 5.4.¶

Key material is derived through a KDF with the interface¶

KDF(protocol_id, label, ikm, info, L)

• protocol_id: binds the output to a specific protocol version and application context.¶

• label: a unique ASCII string identifying the derivation role.¶

• ikm: input keying material, provided as a single octet string or an ordered list of octet strings.¶

• info: context information, provided as a single octet string or an ordered list of octet strings.¶

• L: the requested output length in octets.¶

This KDF binds protocol_id, a label, and inputs of any size into a derived value. frame reduces any over-large input to a fixed-size digest before the KDF sees it. Any protocol instantiates the combiner by supplying its own protocol_id, which domain-separates its derivations from those of every other protocol.¶

The KDF is built from the cipher suite's hash in one of two forms. The cipher suite's kdf_id selects which one.¶

KDF(protocol_id, label, ikm, info, L):
  extract_input = encode(protocol_id, label,
                         ...ikm)
  prk = Extract(salt=protocol_id,
                ikm=extract_input)
  expand_info = encode(protocol_id, label,
                       ...info, uint16(L))
  return Expand(prk, expand_info, L)

KDF(protocol_id, label, ikm, info, L):
  M = encode(protocol_id, label,
             encode(...ikm), encode(...info),
             uint16(L))
  return XOF(M, L)

4.4. SEAL Encodings and Labels

payload_info = [aead_id, segment_max_be, kdf_id, snap_id,
                segment_commitment, nonce_mode, epoch_length_u8, salt]

segment_aad(i, is_final, A_i):
  if nonce_mode is "random":
    if A_i is empty:
      return encode(aad_label, uint64(i), uint8(is_final))
    return encode(aad_label, uint64(i), uint8(is_final), A_i)
  ;; derived nonce mode
  if A_i is empty:
    return ""
  return encode(aad_label, A_i)

4.5. Key Schedule and Nonce Generation

A message's entire key hierarchy grows from two random values. All other keys are derived deterministically through the KDF of Section 4.3.¶

payload_info = [aead_id,
                uint32(segment_max),
                kdf_id,
                snap_id,
                segment_commitment,
                nonce_mode,
                uint8(epoch_length),
                salt]

commitment  = KDF(protocol_id, commit_label,
                  [CEK], [...payload_info, G], commitment_length)
payload_key = KDF(protocol_id, payload_key_label,
                  [CEK], payload_info, Nk)
snap_key     = KDF(protocol_id, snap_key_label,
                  [CEK], payload_info, Nh)

;; For derived nonce mode only:
nonce_base  = KDF(protocol_id, nonce_base_label,
                  [CEK], payload_info, Nn)

segment_key(i):
  epoch_index = i >> epoch_length
  return KDF(protocol_id, epoch_key_label,
             [payload_key],
             [uint64(epoch_index)], Nk)

nonce(i) = Random(Nn)

nonce(i) = nonce_base[0:Nn-8]
           || (nonce_base[Nn-8:Nn]
               XOR uint64((i << 1) | is_final))

4.6. Commitment

The commitment is a commitment_length-octet value the payload schedule derives from the CEK, payload_info, and the global associated data G (Section 4.5).¶

A reader MUST verify the commitment before decrypting any segment, deriving the expected value from the CEK, payload_info, and G and comparing it octet-for-octet with the stored value, and MUST treat a mismatch as an authentication failure for the object. A mismatch indicates a wrong key, parameter set, or G, or a corrupted header. This is the ra-CMT context commitment for fixed per-segment A_i (Section 5.1.2). The reduction outline and bound are in Section 5.6.¶

Because the commitment is fixed at creation, G is immutable: changing it invalidates the stored commitment, while segment contents stay rewritable through the snapshot authenticator (Section 4.7).¶

G defaults to the empty octet string, so an application that supplies no context commits over an empty final element. A wrong G fails the commitment check (Section 4.9.1.2) the same way a wrong CEK does (Section 6.4).¶

4.7. Snapshot Authenticator

The snapshot authenticator binds the current segment set into the keyed snapshot. A SEAL profile selects one with snap_id.¶

is_final(i) = 1 if i = n_seg - 1, else 0

leaf(i) = [LH(ct_i)] || tag_i || nonce_field(i)
          || segment_aad(i, is_final, A_i)

nonce_field(i) = nonce(i), as stored           ;; random nonce mode
               = uint64((i << 1) | is_final)   ;; derived nonce mode

4.8. Segment Algorithms

The construction defines the per-segment subroutines EncryptSegment, DecryptSegment, and RewriteSegment. In this random-access construction, is_final is an explicit input to each subroutine. Full-message encryption derives it from the total segment count n_seg, while random-access decryption and rewrite callers supply it directly. The full-message procedures (Section 4.9.1.1, Section 4.9.1.2, Section 4.9.3) and the rewrite procedure (Section 4.9.2.1) compose them.¶

Each subroutine is the cryptographic core of one operation of the base or extended raAE interface (Section 3.2, Section 3.3), refining Table 1 to the signature level. The primitive's position becomes the explicit arguments i and is_final, and its state is the payload schedule, which the segment_key(i), nonce(i), and segment_aad calls below read from context rather than take as an argument. A segment's plaintext is P_i, and its stored record is stored_i = (nonce_metadata_i, ct_i, tag_i), which names the stored values, not their order on the wire ([I-D.sullivan-seal-concrete]). leaf(i) is the segment's leaf (Section 4.7.2), and new_leaf(i) the leaf of the record that replaces segment i.¶

These subroutines emit ct_i and tag_i as separate fields, with ct_i of length len(P_i), at most segment_max. DecryptSegment splits stored_i using the ciphertext length the consuming format conveys (Section 4.4.2).¶

In every subroutine, i is the segment index (a non-negative integer), is_final is 1 for the last segment and 0 for all others, A_i is the caller-supplied associated data for segment i, and P_i is the segment plaintext. The subroutines call segment_key(i) and nonce(i) as defined in Section 4.5, with nonce(i) following the chosen nonce_mode, and segment_aad(i, is_final, A_i) as defined in Section 4.4.2.¶

nonce_metadata_i denotes the stored nonce metadata for segment i: nonce(i) when nonce_mode is "random", and empty when it is "derived". In random mode DecryptSegment reads its nonce from nonce_metadata_i, and in derived mode it recomputes nonce(i).¶

EncryptSegment(i, is_final, A_i, P_i):
  key   = segment_key(i)
  nonce = nonce(i)
  aad   = segment_aad(i, is_final, A_i)
  C_i   = AEAD.Encrypt(key, nonce, aad, P_i)
  split C_i into ct_i and tag_i
  return (nonce_metadata_i, ct_i, tag_i)

DecryptSegment(i, is_final, A_i, stored_i):
  nonce_metadata_i, ct_i, tag_i = stored_i
  key   = segment_key(i)
  nonce = nonce_metadata_i or nonce(i)
  aad   = segment_aad(i, is_final, A_i)
  C_i   = ct_i || tag_i
  P_i   = AEAD.Decrypt(key, nonce, aad, C_i)
          (on verification failure, return a decryption error)
  return P_i

4.9. Top-level Algorithms

The top-level algorithms compose the segment subroutines (Section 4.8) over complete messages. They call the snapshot-authenticator operations of Section 4.7 (snapshot() and verify() in every profile, add(i, input) wherever segments are written, set_length(n) at creation and on any length change, and remove(i, input) in a mutable or append-only profile) without referring to how any is computed. The profile's selected authenticator realizes those operations (Section 4.7.1).¶

These procedures do not expose per-segment associated data, so they pass an empty A_i to each subroutine. An application that needs per-segment A_i calls the subroutines directly.¶

derive  commitment, payload_key, snap_key from the payload schedule
        (and nonce_base, in derived mode)
store   commitment

for i in 0 .. n_seg-1:
    is_final = 1 if i = n_seg-1, else 0
    stored_i = EncryptSegment(i, is_final, empty, P_i)
    store stored_i

if snapshot authentication is enabled:
    set_length(n_seg)
    for i in 0 .. n_seg-1:
        add(i, leaf(i))
    snapshot = snapshot()
    store snapshot

derive  commitment from CEK, salt, and G
derive  payload_key, snap_key from CEK and salt
if stored commitment != derived commitment:  return error
P_i = DecryptSegment(i, is_final, empty, stored_i)
       (return its error on failure)
if snapshot authentication is enabled and the full set is available:
    if SnapVerify(snapshot) fails:  return error  (do not deliver P_i)
return P_i

def Rewrite(i, new_P_i):
  is_final = 1 if i = n_seg-1, else 0
  form leaf(i) from stored_i, is_final, and an empty A_i
  new_stored_i = RewriteSegment(i, is_final, empty, new_P_i)
  remove(i, leaf(i))
  add(i, new_leaf(i))
  snapshot = snapshot()
  store new_stored_i, snapshot

def Append(P_new):
  old_n_seg = n_seg
  k         = len(P_new)
  t         = old_n_seg - 1

  if k < 1:
    return an input error
  if any element of P_new is longer than segment_max:
    return an input error

  if old_n_seg > 0:
    P_t = DecryptSegment(t, 1, empty, stored_t)
          (return its error on failure)
    new_stored_t = RewriteSegment(t, 0, empty, P_t)
    form leaf(t) from stored_t, is_final = 1, and an empty A_i
    remove(t, leaf(t))   ;; leaf of the stored_t just decrypted

  set_length(old_n_seg + k)

  if old_n_seg > 0:
    store new_stored_t
    add(t, new_leaf(t))

  for j in old_n_seg .. old_n_seg+k-1:
    is_final = 1 if j == old_n_seg+k-1 else 0
    stored_j = EncryptSegment(j, is_final, empty,
                              P_new[j-old_n_seg])
    store stored_j
    add(j, leaf(j))

  store snapshot()

def Truncate(m):
  old_n_seg = n_seg
  t         = m - 1

  if m >= old_n_seg:
    return an input error

  if m > 0:
    P_t = DecryptSegment(t, 0, empty, stored_t)
          (return its error on failure)
    new_stored_t = RewriteSegment(t, 1, empty, P_t)
    form leaf(t) from stored_t, is_final = 0, and an empty A_i
    remove(t, leaf(t))   ;; leaf of the stored_t just decrypted

  for j in m .. old_n_seg-1:
    form leaf(j) from stored_j, an empty A_i, and is_final = 1
        only at j = old_n_seg-1
    remove(j, leaf(j))
  discard segments m .. old_n_seg-1

  set_length(m)

  if m > 0:
    store new_stored_t
    add(t, new_leaf(t))

  store snapshot()

5.1. Security Notions

raAE has two security tiers. The base tier comprises the notions of [FLRR25]: ra-ROR, ra-CMT, and its position-choosing variant ra-CMT-p. The extension tier adds one notion, snapshot integrity, defined by this document. A construction MAY provide the base tier only.¶

5.2. Relations to Other Notions

AEAD ([RFC5116]):

raAE generalizes AEAD to multi-segment content with arbitrary-order encryption. A single-segment raAE is an AEAD.¶

nOAE2 ([Tink]):

nOAE2 is the nonce-based online authenticated encryption notion for schemes that encrypt in order and support random-access decryption. Hoang and Shen introduced nOAE2 in their analysis of Tink Streaming AEAD ([Tink]), where they also show STREAM satisfies it. ra-ROR is strictly stronger: every ra-ROR-secure scheme is nOAE2-secure when used in order, but nOAE2-secure schemes can fail when encryption order is arbitrary ([FLRR25]).¶

Commitment ([RFC9771]):

CMT-1 and CMT-4 ([RFC9771]) are per-AEAD commitment notions. ra-CMT is the corresponding notion for segmented random-access schemes. See Section 5.1.2.¶

Rewrite safety and extension safety need no notions beyond ra-ROR and snapshot integrity. Replacing a segment in place is an EncSeg at an already-used position together with a snapshot update (Section 5.1.1). In derived nonce mode it repeats the segment nonce, so it MUST use an MRAE AEAD (Section 4.5.3.2). Each rewrite also counts against the AEAD usage budgets (Section 5.8).¶

Appending and truncating likewise add no algorithm (Section 4.9.3) and no notion. An adversary's ability to add, drop, reorder, or re-mark a terminal segment is exactly the snapshot integrity adversary of Section 5.1.4, and detection follows from the index and finality binding of Section 4.4.2 together with snapshot verification. Rollback of the whole object to an earlier honest (state, snapshot) after truncation is the freshness case that snapshot integrity excludes (Section 6.7).¶

5.3. Adversary Model and Assumptions

The adversary model is that of the ra-ROR game (Section 5.1.1, [FLRR25]). In the construction's terms: the adversary can observe all ciphertexts and content metadata, tamper with individual segments or their ordering, replace the keyed snapshot, and attempt decryption with chosen keys. The per-content salt is public metadata available to the adversary, and the arguments need it fresh and uniform, not secret. The confidentiality and integrity bounds assume the CEK is secret and uniform, the single-owner regime: an application MUST supply a CEK that is either generated uniformly at random or derived so that it is computationally indistinguishable from uniform, such as the output of a KDF keyed by a secret. When multiple messages share a CEK, the per-content salt separates payload schedule outputs across messages under the PRF assumption (Appendix C.2).¶

The commitment notions ra-CMT and ra-CMT-p (Section 5.6) also cover a shared-CEK regime, where the adversary holds the CEK and so can decrypt and forge segment tags at will.¶

One binding can still hold against a CEK holder, under three conditions that each close a distinct gap. The keyed snapshot MUST be authenticated outside the construction, because a CEK holder derives snap_key and can otherwise forge any keyed snapshot directly. The ciphertext digest MUST be set: without it a segment's leaf binds its ciphertext only through the AEAD tag, which a CEK holder forges for altered content. The authenticator's ordering MUST be strict: under a linear ordering a snap_key holder can present a different segment set with the same keyed snapshot even when every leaf commits to its content, and only a strict ordering makes finding one a collision problem. A snapshot meeting all three is the basis of the per-index binding of Section 5.6.¶

The persistent state of an raAE object, and the party that owns each item, is:¶

CEK:

Secret key-management state. It is the root secret for the object.¶

salt:

Public stored object metadata. It separates objects under one CEK.¶

parameter set:

Profile or object metadata. It fixes suite, maximum segment size, and epoch policy.¶

commitment:

Stored object metadata. It rejects wrong key or parameter context before decryption.¶

segment metadata:

Storage-format state. It holds AEAD tags, the per-segment nonces in random nonce mode, and, when set, each segment's ciphertext digest (Section 4.7.1).¶

snapshot:

Stored object metadata. It authenticates the segment set and segment count.¶

external freshness state:

Consuming-protocol state. It detects whole-object rollback.¶

The security argument relies on three distinct assumptions about the KDF. For derivations whose input keying material is secret and uniformly random, including payload_key, snap_key, nonce_base, epoch_key, and the snapshot authenticator's keyed derivations, the KDF is assumed to be a multi-user PRF with domain separation by protocol_id and label.¶

For commitment, the function¶

Commit(CEK, payload_info, G, L) =
    KDF(protocol_id, "commit", [CEK], [...payload_info, G], L)

is additionally assumed to be collision resistant over adversarially chosen tuples (CEK, payload_info, G), with G empty by default. PRF security alone is not sufficient for this property, because the commitment adversary may choose the CEK and context values.¶

For the plaintext-bound nonce construction, the plaintext digest step targets collision resistance, not PRF security.¶

5.4. raAE Construction Requirements

The bounds below rely on the KDF framing and the snapshot authenticator. Their requirements are obligations on the raAE construction, not part of the raAE primitive of Section 3. A profile selects the concrete framing for every derivation surface: the KDF input assembly (Section 4.5), the payload_info construction (Section 4.2), the segment AAD (Section 4.4.2), and the snapshot authenticator's keyed inputs (Section 4.7). Any such framing MUST meet the following contract. SEAL is one such framing (Section 4.3, Section 4.4).¶

Pseudorandomness:

KDF outputs MUST be computationally indistinguishable from random to an adversary that does not know the ikm, assuming the underlying hash or PRF is a secure pseudorandom function.¶

Injectivity:

A construction encodes the tuple (protocol_id, label, ikm, info, L) into the underlying primitive input, and that encoding MUST be injective: distinct tuples map to distinct primitive inputs. This is a requirement on the encoding, not on the KDF, which need not itself be injective. ikm and info MUST be unambiguously separable in the encoded input, whatever the number of elements each contains. The two-step form binds ikm and info in its separate Extract and Expand inputs. The one-step form frames ikm and info each as a single encode element. Where the encoding admits inputs too large to encode literally, it MAY substitute a fixed-length digest of the over-large field. The encoding is then injective only up to the collision resistance of that digest, which the construction MUST justify and domain-separate from the literal encoding (Section 4.3).¶

Label uniqueness:

Each derivation role, including commitment, payload key, snapshot authenticator key, nonce base, epoch key, segment nonce, hedged key, and the authenticator's internal roles, MUST use a distinct label string within each protocol version.¶

Protocol binding:

The protocol_id MUST appear as a distinct component of the KDF primitive input. Different application protocols using the same AEAD and KDF MUST use different protocol_id values.¶

Output length commitment:

The requested output length L MUST be part of the KDF primitive input, so a truncated longer output cannot pass as a shorter one.¶

Cross-role isolation:

Cross-role isolation follows from label uniqueness and PRF security of the underlying primitive: a KDF output for one derivation role, such as payload_key, is computationally independent of the output for any other role, such as snap_key, even when derived from the same CEK and payload_info.¶

Snapshot authenticator:

When a snapshot authenticator is configured, the construction MUST bind the current (index, input) set and the segment count into a keyed snapshot that an adversary without the authenticator's secret key cannot forge for a modified (index, input) set or count, even after observing keyed snapshots and their deltas across rewrites. How the value is computed, and whether a single-segment change updates it in place or rebuilds it, is the authenticator's choice. SEAL's snapshot authenticators are in Section 4.7.¶

SEAL's construction (Section 4) satisfies these requirements. Its KDF (Section 4.3), keyed by the CEK, is modeled as a pseudorandom function. Its encode framing (Section 4.3) is injective, up to LH collision resistance for over-large fields, and places protocol_id and the output length L in the primitive input, so injectivity, protocol binding, and output-length commitment hold. SEAL's labels (Table 4, each configured snapshot authenticator's own labels, the plaintext-bound construction's labels in Appendix A, and the hedged-randomness label in Appendix B) are distinct, giving label uniqueness and, with PRF security, cross-role isolation. Each configured snapshot authenticator satisfies the snapshot authenticator requirement, with its forgery argument accounted in Section 5.7. Of SEAL's fields only the caller-supplied G (Section 4.2.4) and A_i, and a strict authenticator's leaf, which carries A_i, can exceed 0xFFFE octets and so take the LH digest path. Cross-protocol separation comes from protocol_id in the KDF inputs and from aad_label in the segment AAD, not from LH (Section 4.3).¶

5.5. Segment Confidentiality and Integrity

The construction targets ra-ROR security (Section 5.1.1). The advantage bound, its adversary parameters, and the per-term analysis are in Appendix C.¶

Ciphertext cores are indistinguishable from random under the ra-ROR definition, up to the public length leakage and public metadata exposed by the consuming format (file-level headers, stored nonces in random mode, the salt, and the commitment). Re-encrypting a position is outside that bound in either nonce mode. Under a derived nonce and an MRAE AEAD it also reveals whether the new plaintext and associated data equal the old (Appendix C.5). Each segment AEAD ciphertext binds the segment to its own index and finality bit (through segment_aad in random nonce mode and through the nonce in derived nonce mode) so an adversary cannot modify or substitute a segment under a given index, or flip its finality bit, without causing an AEAD verification failure on that segment.¶

Three quadratic floors bound the multi-message advantage:¶

salt collision       q_m^2 / 2^256          all suites
epoch-key collision  n_ep^2 / 2^128         128-bit-key suite
nonce collision      q^2 / 2^(8*Nn + 1)     random nonce mode
                     q^2 / 2^97  at Nn = 12

In derived nonce mode the salt-collision floor is the only one for the 256-bit-key suites. The 128-bit-key suite also has the epoch-key collision floor, which dominates (Appendix C.2). In random nonce mode, with or without the plaintext-bound hedge, the nonce-collision floor applies, summed over keys (Section 5.8.2). Here q is the number of segment encryptions under one key, and Nn is the nonce length in octets. The block-size birthday term is derived in Section 5.8.¶

Segment size enters the analysis only through the forgery and block-size terms, both bounded in Section 5.8. A segment's length is authenticated implicitly by its AEAD tag, not through segment_aad or the nonce, so the analysis assumes the consuming format conveys each segment's true ciphertext length. Segments shorter than segment_max consume no more than their share of the per-key budget and need no separate accounting.¶

5.6. Commitment Security

raAE's commitment target here is ra-CMT for fixed per-segment A_i (Section 5.1.2), not the per-AEAD CMT-1 ([RFC9771]): the commitment binds the CEK and payload_info, which together carry the full parameter context affecting key derivation, AEAD operation, and AAD and nonce construction.¶

For fixed A_i, ra-CMT relies on collision resistance of the derivation map over the tuple (protocol_id, "commit", CEK, payload_info, G, commitment_length), with G empty by default (Section 5.3). SEAL sets commitment_length = Nh, so the commitment offers about 2^128 collision-search work at Nh = 32 and about 2^256 at Nh = 64. The reduction outline and the collision quantities for a general commitment_length are in Appendix C.4.¶

The commitment bounds ra-CMT where the positions and A_i match (Section 5.1.2). It does not bind the segment position. Position binding for the ra-CMT-p variant is inherited from the underlying AEAD's commitment level. Because the SEAL AEADs are not relied upon to provide it, position confusion under an adversarially chosen key is out of scope, consistent with [FLRR25]. A malicious encryptor that controls the CEK can craft a single ciphertext segment that opens at two positions, and the per-segment AEAD tag does not prevent it.¶

A strict authenticator with the ciphertext digest set pins each index to one ciphertext even against a CEK holder, where a profile selects it and a consuming protocol authenticates the one keyed snapshot outside the construction (Section 4.7.1, Section 5.3). Where that snapshot also binds the commitment, as SEAL's strict authenticators do, each index accepts one opening: one (CEK, nonce, plaintext) under which the commitment verifies and the stored ciphertext and tag at that index decrypt under that index's segment AAD. In random nonce mode the nonce field is the nonce. In derived nonce mode it is the counter, which fixes the nonce once the commitment fixes the CEK, so the binding holds for a decryptor that verifies the commitment. It holds in both nonce modes for every suite, for any A_i, and at the last index of an intermediate snapshot, where the leaf fixes is_final = 0.¶

Per-index binding is weaker than the ra-CMT-p of [FLRR25], which also rules out one ciphertext opening at two positions. The object's author can store one ciphertext at two indices whose epoch keys both accept it, and the snapshot then accepts it at both. For example, at epoch_length 10, indices 0 and 1024 fall under different epoch keys, and an AES-GCM ciphertext valid under both keys costs no search ([DGRW18]). Under ChaCha20-Poly1305 and AES-256-GCM-SIV the two indices need not fall under different epoch keys, since each index's nonce gives it its own authentication key ([ADG22]).¶

The per-segment associated data A_i is likewise outside the commitment: SEAL binds A_i through segment_aad and the AEAD tag for that segment, so contexts that differ only in A_i fall outside the ra-CMT claim (Section 5.1.2). A_i is also rewritable. The strict authenticators' leaf carries segment_aad, so an authenticated strict snapshot binds each index's A_i. A snapshot under a linear ordering does not, and an application that needs A_i bound under one MUST bind it externally.¶

A deployment that must defend against a malicious encryptor who controls the CEK can close the adversarial-key position gap by one of two changes, neither of which SEAL adds to the base construction. They are optional because only the object's author, who holds the CEK, can make one ciphertext open at two positions, which gains it nothing it could not already write, and the gap matters only to a system that identifies content by ciphertext independent of position, such as deduplication or content addressing.¶

• A context-committing AEAD, so that each segment ciphertext commits to its full decryption context rather than relying on the external commitment over (CEK, payload_info, G).¶

• A per-segment collision-resistant commitment over the segment's position and ciphertext, on the order of 16 to 64 octets per segment, bound alongside the segment so that no segment opens at two positions.¶

A strict authenticator with the ciphertext digest set narrows the gap without closing it, giving at most the per-index binding above (Section 4.7.1).¶

None of the SEAL AEADs is relied upon to provide CMT-1 or CMT-4 ([RFC9771]). In particular AES-256-GCM-SIV is not key-committing, with known attacks such as partitioning oracles.¶

With commitment_length = Nh and Nt = 16, ra-CMT for fixed A_i is bounded by commitment collision resistance, and ra-CMT-p for fixed A_i adds the AEAD position-commitment term (Appendix C.4). Under honestly generated keys the idealized per-pair tag-forgery floor is 2^(-128) because Nt = 16, and concrete per-AEAD authenticity bounds degrade with segment length (Section 5.8).¶

5.7. Snapshot Authenticator Security

Snapshot integrity is keyed by snap_key and protects the writer's current segment set against a storage or write adversary that does not hold snap_key. A verifier who holds snap_key, hence the CEK from which it is derived, detects any alteration of the segment set (Section 4.7.1). The value gives no protection among parties that share the CEK, which can recompute snap_key, and it is not a third-party-verifiable commitment to a segment set. Whether a fixed, externally authenticated keyed snapshot binds segment content against key holders depends on the authenticator (Section 4.7.1). An application that needs sender attribution or third-party verifiability MUST add a signing layer, over the keyed snapshot for a verifier that holds the CEK, or over a public snapshot for one that does not, where the authenticator defines one (Section 4.7.3).¶

A profile MUST keep each of an authenticator's KDF labels inside the injective encode frame (Section 4.3) so distinct roles cannot collide on the primitive input.¶

snap_key is derived per message from the CEK and salt and is not exposed through the interface.¶

5.8. Capacity and Usage Limits

These usage limits are organized around independent limit classes, not around named suites. The accounting unit is one segment encryption under one epoch key (Section 5.8.1).¶

The budgets depend on the AEAD's nonce, key, tag, and cipher block sizes (Nn, Nk, Nt, Nb), on the AEAD's own published confidentiality and integrity analysis, on the KDF's output size Nh and its mu-PRF security (Appendix C.2), and on the suite's segment_max. A suite that fixes those works out every figure below. The mu-PRF security allows epoch keys to be treated as independent random keys, subject to its distinguishing cost.¶

The length-dependent limits in this section are computed at the suite's segment_max, the largest plaintext one segment encryption carries. Independent of these per-key budgets, a segment-encryption procedure MUST respect each underlying AEAD's per-invocation input limits.¶

Adv_nonce_coll <= sum_j q_j^2 / 2^(8*Nn + 1)
CA_blocks      <= sum_j (s_j + q_j + 1)^2 / 2^(8*Nb + 1)
IA_forgery     <= sum_j v_j * F(segment_max)

q_j <= sqrt(epsilon_nonce * 2^(8*Nn + 1) / K)

encryptions per segment  =  2^((8*Nn + 1 - 32)/2) / 2^epoch_length

n_ep^2 / 2^(8*Nk)

P(collision) <= q^2 / 2^(8*Nn + 1)

CA <= ((s + q + 1)^2) / 2^(8*Nb + 1)

q  <=  2^((8*Nb + 1 - 32)/2) / n_blk

nonce collision:  q^2 / 2^(8*Nn + 1)
threshold:        n_blk^2 > 2^(8*(Nb - Nn))

IA <= v * F(segment_max)

C * L * B / 2^128,   C = 48*c + 30

C * L * B / 2^128 <= epsilon_data

one active pair:  L = B = n_rw * ell
H active pairs:   L = H * n_rw * ell,  B = n_rw * ell

one active pair:  n_rw <= sqrt(epsilon_data * 2^128 / C) / ell
H active pairs:   n_rw <= sqrt(epsilon_data * 2^128 / (C * H)) / ell

C * L_obj * B_obj <= 2^96,   about L_obj * B_obj <= 2^89.3 at C = 102

C * B / 2^128

6.1. Resource Exhaustion

An adversary can supply large segment counts, long ciphertexts or associated data, or repeated invalid objects to exhaust memory, storage, or verification time. Snapshot verification can require work over the entire segment set before rejecting an object. These are denial-of-service threats of the kind Section 4.6 of [RFC3552] describes. Cryptographic authentication does not prevent them, since a verifier does the work before it rejects.¶

Consuming protocols MUST define and enforce limits on segment and epoch counts, object and segment lengths, associated-data lengths, allocations, storage, and verification work. Implementations MUST check these limits before allocating from untrusted counts or lengths or undertaking the corresponding verification work. Offset and size arithmetic MUST be checked for overflow and for bounds within the supplied object before accessing data. A consuming protocol also needs limits on repeated presentations of objects, valid or not, since individually bounded objects can exhaust aggregate resources. It sets these limits according to its available resources; the cryptographic usage budgets alone do not supply them.¶

6.2. Detection Summary

The rows detected by SnapVerify assume a snapshot authenticator is configured. Without one, those modes go undetected, except the write-once truncation case that the finality requirement of Section 4.9.1.2 detects (the truncation row).¶

6.3. Nonce Misuse

Nonce reuse under a non-MRAE AEAD leaks plaintext: an adversary who observes two ciphertexts under the same key and nonce recovers the XOR of the plaintexts (for CTR-based AEADs) and can forge new ciphertexts. When such an AEAD's authenticator is a polynomial universal hash, nonce reuse also recovers the authentication key, enabling forgery of arbitrary messages.¶

Random nonce mode depends on the CSPRNG. If the CSPRNG returns duplicated state, segments collide unless a hedge prevents it (Appendix B, Appendix A). Derived nonce mode removes that dependence, since nonces are deterministic, but the determinism is itself a hazard: re-encrypting a segment with different content under its repeated derived nonce is a two-time pad, catastrophic for a non-MRAE AEAD.¶

A non-MRAE AEAD therefore uses derived nonces only under the write-once or append-only discipline of Section 4.5.3.2, which draws a fresh salt per object and never encrypts an (i, is_final) pair twice under that salt, including after a crash. Retransmission of saved ciphertext does not invoke encryption. An MRAE AEAD instead degrades only to equality leakage, not plaintext recovery.¶

The plaintext-bound construction (Appendix A) partially defends against CSPRNG duplication: different plaintexts or segment AAD at the same index produce different nonces because the derivation input differs, but an equal plaintext under equal segment AAD still collides. Implementations that need segment contents defended against random number generator (RNG) state duplication MUST use derived nonce mode with an MRAE AEAD, which limits what duplication reveals about segment contents to equality. HedgedRandom with a tag2 that stays unique covers duplication of the CSPRNG state alone (Appendix B), but an implementation rarely knows whether a restore also rolled back tag2, so the hedge does not meet this requirement.¶

6.4. Parameter Set Mismatch

The full parameter set that affects encryption, decryption, AAD construction, nonce construction, and key derivation is bound into payload_info (see Section 4.2) and therefore into the commitment. A reader using a different parameter set than the writer triggers a commitment mismatch before any AEAD operation is attempted. A reader supplying a different G than the encryptor likewise triggers a commitment mismatch (Section 4.6). Consuming protocols MUST still reject unrecognized or unsupported parameter values before decryption, since the commitment check detects mismatch but does not by itself indicate which parameter value the recipient is unable to support.¶

One profile-level constant is bound transitively rather than via payload_info: aad_label is bound through protocol_id (each profile fixes its own aad_label). Profiles MUST NOT share a protocol_id across distinct aad_label values. Reusing a protocol_id with a changed aad_label produces objects whose commitment matches the wrong reader but whose per-segment AEAD verification fails with no clear error attribution.¶

6.5. Framing and Label Errors

Two classes of implementation error break cross-role isolation. A non-injective framing function maps distinct KDF input tuples to the same primitive input, correlating outputs that should be independent. Implementations MUST verify injectivity per Section 5.4. Reusing a label across roles (for example, "commit" for both commitment and payload key) has the same effect. Labels MUST be distinct within a protocol version, and a new version that changes any derivation MUST change the protocol_id.¶

6.6. Parameter Misuse

The nonce mode and AEAD choice are coupled, and the table gives the rule for each pairing:¶

Rewrite is where the coupling matters: a derived nonce is reused where a random nonce is redrawn, and the consequences of that reuse by AEAD class are in Section 6.3 and Section 4.5.3.2.¶

6.7. Snapshot Integrity Limitations

A reader that does not run snapshot verification (Section 4.7) gets per-segment AEAD authenticity only (Section 5.1.4): the ciphertext core is authenticated under its index and finality bit, but substitution of a previous valid same-index segment, and dropping or rolling back other segments, go undetected. Such readers MUST still verify the commitment per Section 4.6. Applications that support random-access single-segment reads MUST either run snapshot verification on every read or explicitly document that they accept per-segment authenticity without snapshot freshness.¶

Snapshot verification authenticates the segment set, its positions, and the count. Without the ciphertext digest it does not confirm that a tag is a valid AEAD tag for the ciphertext beside it. With the ciphertext digest set, the strict authenticators bind the ciphertext bytes, tag, nonce field, and segment AAD, but do not establish that the tag opens the ciphertext under the AEAD (Section 4.7.1), which decrypting the segment does (Section 5.6).¶

Snapshot integrity does not provide freshness against whole-object rollback. A storage adversary that rolls back the entire encrypted object, including the snapshot, to a previously valid version is not detected by raAE alone, because the rolled-back snapshot is itself a valid snapshot for that prior state. This is replay, not forgery. Applications that require whole-object rollback resistance MUST bind an authenticated version field, timestamp, monotonic counter, or authenticated storage layer into the snapshot context. An update that meets the writer rule of Section 3.3.1 from a current verified snapshot cannot launder a rolled-back snapshot into a valid ongoing history.¶

Same-index rollback within a snapshot is detected when snapshot verification runs: replacing one segment with a previously valid same-index segment under the current keyed snapshot changes the recomputed value, so verification fails except with the forgery probability of Section 5.7.¶

Truncation, including removal of the final segment marked is_final = 1, is detected by snapshot verification, since the removed segment is absent from the recomputed value and the count n_seg no longer matches. Truncation to the count of an earlier complete version, presented with that version's snapshot, is the exception Section 4.7.1 states.¶

6.8. Salt Reuse

Reusing a salt with the same CEK, protocol_id, and other payload_info fields across two files produces the same payload_key, the same snap_key, and, in derived nonce mode, the same nonce_base. It defeats schedule-based object separation in every nonce mode, but it does not by itself make an individual swap pass a fixed snapshot.¶

With equal protocol_id and payload_info, a donor segment can pass the recipient's per-segment AEAD check at the same index when finality and A_i also match. That check binds the segment key, nonce, and effective AAD (Section 4.4.2); it does not separately bind the object's commitment or G. In random nonce mode the donor's stored nonce travels with the segment. Without a snapshot authenticator, a reader relying only on per-segment AEAD checks accepts this substitution.¶

An individual substitution that changes the authenticated leaf fails snapshot verification, except by forgery, if the recipient's current snapshot stays in place (Section 6.7).¶

Substitution together with donor snapshot state can pass when the resulting segment set, count, and bound context match that donor state. This includes replay of the donor's entire object in a recipient context that admits it. A keyed snapshot over indexed tags and the count alone binds, through snap_key, protocol_id and payload_info but not G. One that also includes the commitment, as SEAL's strict authenticators do, rejects a donor snapshot under a different recipient commitment ([I-D.sullivan-seal-concrete]). G changes the commitment but not payload_key, snap_key, or nonce_base (Section 4.5). Where all bound contexts match, no snapshot authenticator supplies a separate object identity to distinguish cross-object replay. A consuming protocol's authenticated object identity or freshness can reject that replay (Section 6.7).¶

In derived nonce mode the nonces also repeat across the two files, so an MRAE AEAD degrades to deterministic encryption and leaks plaintext equality between same-index segments. A non-MRAE AEAD then permits plaintext recovery: its discipline (Section 4.5.3.2) keeps derived nonces unique only within one object, and a reused salt repeats nonce_base, hence every derived nonce, across two.¶

In random nonce mode (and with the plaintext-bound hedge) fresh nonces keep confidentiality intact, although the per-key nonce-collision budget of Section 5.8.7.1 then counts encryptions across both files under each shared segment key. The object-separation failure above remains. Applications MUST therefore ensure salt uniqueness per CEK when creating a new message. The freshness requirement in Section 4.9.1.1 exists for this reason.¶

6.9. Rewrite Hazards

The tracking and freezing requirement of Section 5.8.5 applies to rewrites. In random nonce mode with Nn = 12 the per-key nonce-collision figure is roughly 2^32 encryptions per epoch key, and exceeding it risks nonce collisions, which a non-MRAE AEAD turns into plaintext recovery (Section 6.3).¶

A mutable profile with derived nonces and an MRAE AEAD reuses a segment's deterministic nonce across non-terminal rewrites, and a writer that encrypts when it retries after a crash reuses it once more. Confidentiality then rests not on nonce uniqueness but on the workload-dependent rewrite bound (Section 5.8.5): the AEAD degrades to equality leakage between identical rewrites rather than to plaintext recovery, as long as the per-object or allocated aggregate budget of Section 5.8.7.4 is respected.¶

The append-only profile has no such margin. It admits a non-MRAE AEAD, so its safety rests on never re-encrypting a segment with different content (Section 4.9.3.1), and a writer that breaks that rule gets a two-time pad rather than a bounded leak.¶

Per-segment associated data A_i is rewritable, so a reader cannot treat it as context fixed at creation (Section 4.4.2). An application that needs creation-fixed context places it in G, which the commitment binds (Section 4.6), not in A_i.¶

raAE also does not guarantee atomic rewrites. A segment rewrite touches the nonce metadata, ciphertext core, AEAD tag, the keyed snapshot, and any stored summary such as the masked accumulator or the epoch heads. A crash between any two of these leaves the content inconsistent. Applications MUST use write-ahead logging, copy-on-write, or an equivalent mechanism to make rewrites recoverable.¶

6.10. Constant-Time Implementation

Several raAE operations handle secret data and MUST be implemented in constant time to prevent timing side-channels.¶

The KDF calls in the payload schedule and epoch key derivation take the CEK or payload_key as input keying material. Implementations MUST ensure that the KDF's keyed operations execute in constant time with respect to their key inputs. For an HMAC-based KDF this is satisfied by implementations that do not branch on key octets.¶

Both the commitment comparison (Section 4.9.1.2) and the snapshot comparison in SnapVerify MUST use a constant-time octet comparison. A variable-time comparison lets an adversary who can retry tampered inputs learn the expected value one octet at a time, reducing the forgery cost of either check to a linear number of trials.¶

AEAD.Encrypt and AEAD.Decrypt operations inherit the constant-time requirements of the underlying AEAD. Implementations SHOULD use AEAD libraries that document constant-time guarantees.¶

6.11. Properties Not Provided

raAE protects segment content and binds segments together. Everything a complete storage or messaging system needs beyond that is the consuming protocol's responsibility.¶

Freshness and whole-object rollback:

Snapshot integrity binds the segment set of one recorded object state, not its recency. A party holding the ciphertext can present an earlier honest state in full, and both per-segment and snapshot verification still pass. Telling the current state from a stale one requires external freshness (Section 6.7).¶

Forward secrecy:

The CEK must remain available as long as any reader needs access, so raAE provides none.¶

Sender identity:

Ciphertexts are not bound to any sender. A signing or MAC layer is needed for sender authentication.¶

Unlinkability:

Key identifiers and structural features of the encrypted format are visible, so unlinkability requires application-layer measures.¶

Whole-message replacement:

Snapshot verification covers segments within a message but cannot detect replacement of the message itself. An adversary who swaps one encrypted message for another goes undetected unless the application binds message identity externally.¶

Serialization, storage, and key management:

raAE emits and consumes component values but defines no wire container, storage transactions, or key lifecycle. A consuming protocol supplies these.¶

6.12. Cross-Application Domain Separation

Two applications that both reuse the same SEAL profile label with the same input keying material, the same payload_info, and the same G derive identical commitments, keys, nonces, and AADs. The protocol_id provides cross-application domain separation only when it is distinct per application. Applications whose keying material may be shared across systems SHOULD use an application-specific protocol_id (for example, "myapp-backup-v1") rather than a SEAL profile label. An application adopting a SEAL profile unchanged MAY use that profile's label.¶

8.1. Normative References

[I-D.ietf-hpke-pq]

Barnes, R. and D. Connolly, "Post-Quantum and Post-Quantum/Traditional Hybrid Algorithms for HPKE", Work in Progress, Internet-Draft, draft-ietf-hpke-pq-05, 6 July 2026, <https://datatracker.ietf.org/doc/html/draft-ietf-hpke-pq-05>.

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

[RFC5116]

McGrew, D., "An Interface and Algorithms for Authenticated Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008, <https://www.rfc-editor.org/rfc/rfc5116>.

[RFC5869]

Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand Key Derivation Function (HKDF)", RFC 5869, DOI 10.17487/RFC5869, May 2010, <https://www.rfc-editor.org/rfc/rfc5869>.

[RFC8017]

Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016, <https://www.rfc-editor.org/rfc/rfc8017>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

[RFC8452]

Gueron, S., Langley, A., and Y. Lindell, "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption", RFC 8452, DOI 10.17487/RFC8452, April 2019, <https://www.rfc-editor.org/rfc/rfc8452>.

[RFC9180]

Barnes, R., Bhargavan, K., Lipp, B., and C. Wood, "Hybrid Public Key Encryption", RFC 9180, DOI 10.17487/RFC9180, February 2022, <https://www.rfc-editor.org/rfc/rfc9180>.

8.2. Informative References

[ADG22]

Albertini, A., Duong, T., Gueron, S., Kölbl, S., Luykx, A., and S. Schmieg, "How to Abuse and Fix Authenticated Encryption Without Key Commitment", USENIX Security 2022 pp. 3291-3308, 2022, <https://www.usenix.org/conference/usenixsecurity22/presentation/albertini>.

[BHT18]

Bose, P., Hoang, V. T., and S. Tessaro, "Revisiting AES-GCM-SIV: Multi-user Security, Faster Key Derivation, and Better Bounds", IACR ePrint 2018/136, 2018, <https://eprint.iacr.org/2018/136>.

[DGRW18]

Dodis, Y., Grubbs, P., Ristenpart, T., and J. Woodage, "Fast Message Franking: From Invisible Salamanders to Encryptment", CRYPTO 2018, LNCS vol. 10991, pp. 155-186, DOI 10.1007/978-3-319-96884-1_6, 2018, <https://doi.org/10.1007/978-3-319-96884-1_6>.

[FLRR25]

Fábrega, A., Len, J., Ristenpart, T., and G. Rubin, "Random-Access AEAD for Fast Lightweight Online Encryption", EUROCRYPT 2026, DOI 10.1007/978-3-032-25333-0_10, 2026, <https://eprint.iacr.org/2025/2275>.

[HRRV15]

Hoang, V. T., Reyhanitabar, R., Rogaway, P., and D. Vizár, "Online Authenticated-Encryption and its Nonce-Reuse Misuse-Resistance", IACR ePrint 2015/189, 2015, <https://eprint.iacr.org/2015/189>.

[I-D.irtf-cfrg-aead-limits]

Günther, F., Thomson, M., and C. A. Wood, "Usage Limits on AEAD Algorithms", Work in Progress, Internet-Draft, draft-irtf-cfrg-aead-limits-13, 3 September 2026, <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-aead-limits-13>.

[I-D.sullivan-seal-concrete]

Sullivan, N., "SEAL Cipher Suites and Instantiations", Work in Progress, Internet-Draft, draft-sullivan-seal-concrete-01, 2026, <https://datatracker.ietf.org/doc/html/draft-sullivan-seal-concrete-01>.

[NIST-SP-800-38D]

Dworkin, M., "Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC", NIST Special Publication 800-38D, November 2007, <https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf>.

[RFC3552]

Rescorla, E. and B. Korver, "Guidelines for Writing RFC Text on Security Considerations", BCP 72, RFC 3552, DOI 10.17487/RFC3552, July 2003, <https://www.rfc-editor.org/rfc/rfc3552>.

[RFC8446]

Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, <https://www.rfc-editor.org/rfc/rfc8446>.

[RFC8645]

Smyshlyaev, S., Ed., "Re-keying Mechanisms for Symmetric Keys", RFC 8645, DOI 10.17487/RFC8645, August 2019, <https://www.rfc-editor.org/rfc/rfc8645>.

[RFC8937]

Cremers, C., Garratt, L., Smyshlyaev, S., Sullivan, N., and C. Wood, "Randomness Improvements for Security Protocols", RFC 8937, DOI 10.17487/RFC8937, October 2020, <https://www.rfc-editor.org/rfc/rfc8937>.

[RFC9580]

Wouters, P., Ed., Huigens, D., Winter, J., and Y. Niibe, "OpenPGP", RFC 9580, DOI 10.17487/RFC9580, July 2024, <https://www.rfc-editor.org/rfc/rfc9580>.

[RFC9771]

Bozhko, A., Ed., "Properties of Authenticated Encryption with Associated Data (AEAD) Algorithms", RFC 9771, DOI 10.17487/RFC9771, May 2025, <https://www.rfc-editor.org/rfc/rfc9771>.

[SEALPROOFS]

Sullivan, N., "Security Analysis of the SEAL Construction: raAE, Snapshot Integrity, and Commitment", Work in Progress manuscript in preparation.

[TAHOE]

Wilcox-O'Hearn, Z. and B. Warner, "Tahoe: The Least-Authority Filesystem", StorageSS '08 pp. 21-26, DOI 10.1145/1456469.1456474, October 2008, <https://eprint.iacr.org/2012/524>.

[Tink]

Hoang, V. T. and Y. Shen, "Security of Streaming Encryption in Google's Tink Library", IACR ePrint 2020/1019, 2020, <https://eprint.iacr.org/2020/1019>.

C.1. Provenance of the Security Claims

C.2. Advantage Notation and Adversary Parameters

For a ra-ROR adversary (Section 5.3) whose messages and StartDec queries all use one parameter set (Section 4.2), using at most u distinct CEKs and q_m messages, each encrypted with an independent fresh 32-octet per-content salt (Section 4.9.1.1), across n_ep total epochs and making q_sd StartDec queries, and q_e encryption and q_d decryption segment queries with sigma = q_e + q_d, the advantage is bounded by:¶

Adv_raROR(A) <= Adv_salt_coll
                   + 2 * Adv_muPRF(KDF, B_KDF)
                   + q_sd / 2^(8*commitment_length)
                   + Adv_muROR$(AEAD, B_AEAD)
                   + Adv_nonce_coll  (plaintext-bound or
                                      hedged random nonces only)
                   + Adv_hedge       (HedgedRandom only)
                   + Adv_snap

The parameter set fixes the nonce mode (Section 4.5.3), on which the AEAD term depends. The bound holds for a position-respecting adversary, one that never queries EncSeg twice at one position of one session, as in [FLRR25]. In derived nonce mode the write-once and append-only disciplines guarantee that (Section 4.5.3.2, Section 5.1.1). Re-encrypting a position is outside the bound in either nonce mode, pending [SEALPROOFS]. Under a derived nonce the reduction fails for an in-place rewrite, which repeats the nonce with new content, and the claim itself fails for an identical re-encryption, which reproduces the first write's ciphertext where the random ra-ROR game would return a fresh one.¶

Adv_salt_coll

The probability that two messages encrypted under one CEK draw the same salt. Because the salt is a 32-octet value drawn uniformly at random, this term is at most q_m^2 / 2^256. A salt collision is not a PRF-distinguishing event: the KDF deterministically produces identical payload_key, snap_key, and nonce_base outputs whenever (CEK, payload_info) repeats, so the event must be charged separately. This term holds only under the fresh per-message uniform salt requirement of Section 4.9.1.1. A profile that reuses salts or draws them non-uniformly forfeits it and must argue payload-schedule separation by other means (Section 6.8).¶

Adv_muPRF(KDF, B_KDF)

The multi-user PRF advantage of the KDF, in a game that draws each user's key uniformly from that user's key space: 32 octets for a CEK, Nk for a payload_key, and Nh for a snap_key. The bound charges it twice (Appendix C.3). Level A is keyed by the CEK and produces the commitment, payload_key, snap_key, and nonce_base. It has u users and at most 4 * (q_m + q_sd) queries, four per StartEnc or StartDec call. Level B is keyed by payload_key (producing epoch_key per Section 4.5.2 and, in the plaintext-bound construction, per-segment nonces per Appendix A) and by snap_key (producing the snapshot authenticator's keyed derivations). It has up to 2 * q_m users, a payload_key and a snap_key per message, with at most 2 * q_e + q_d payload_key queries plus the snapshot authenticator's snap_key queries.¶

q_sd / 2^(8*commitment_length)

The header-forgery term. StartDec verifies the stored commitment (Section 4.6), and the random ra-ROR game accepts no header at StartDec, while the real game refuses as a trivial win any header a StartEnc produced ([FLRR25]). The term bounds the probability that one of the q_sd StartDec queries accepts a (salt, G, commitment) that no StartEnc under that CEK produced, the event [FLRR25] charges for its own header tag. At commitment_length = 32 it is q_sd / 2^256.¶

Adv_muROR$(AEAD, B_AEAD)

The multi-user real-or-random advantage of the AEAD over sigma total segment queries. When every nonce is nonce(i) = Random(Nn) taken directly from the CSPRNG, it is the advantage in the variant of [FLRR25] whose encryption oracle draws each nonce uniformly at random instead of taking it from the adversary, which is how those nonces are drawn. Otherwise, under a nonce hedge or in derived nonce mode, B_AEAD plays the nonce-respecting game of [FLRR25] and supplies the nonces itself, and Adv_muROR$ denotes that game's advantage. There is one mu-ROR user per epoch key, n_ep in total (n_ep = q_m when each message uses a single flat epoch key). This advantage absorbs a key-collision birthday term of about n_ep^2/2^(8*Nk) over the n_ep keys. For the 256-bit-key suites (Nk = 32) that term is about n_ep^2/2^256 and is negligible. For the 128-bit-key suite (Nk = 16) it is about n_ep^2/2^128 and is the binding epoch-key collision floor. Section 5.8.6 bounds n_ep for that suite.¶

Adv_nonce_coll

The probability of a nonce collision under any segment key. When every nonce is taken directly from the CSPRNG, Adv_muROR$(AEAD, B_AEAD) includes it, so the bound does not charge it separately: a nonce-respecting AEAD bound becomes a bound on Adv_muROR$ by adding this probability ([FLRR25]). Under a nonce hedge it is the term the bound adds, because B_AEAD's queries are nonce-respecting only while no nonce repeats under one segment key. In random nonce mode (with or without the plaintext-bound hedge) it is bounded per Section 5.8.7.1. Under HedgedRandom (Appendix B) that bound holds once Adv_hedge is charged. In derived nonce mode, within the scope above, it is zero (Appendix C.5).¶

Adv_hedge

Present only under HedgedRandom (Appendix B): the PRF advantage of the KDF keyed by sk on its one hedge_label query, plus that of the KDF keyed by hedge_key over the HedgedRandom calls, one per salt and per drawn nonce, none of which an Adv_muPRF level covers. Because tag2 gives every call a distinct input, replacing that KDF with a random function makes every HedgedRandom output, salt or nonce, uniform and independent, as a direct CSPRNG draw is (Appendix C.3). It assumes an sk sampled independently of all CEKs.¶

Adv_snap

The snapshot-forgery advantage of the configured snapshot authenticator in the combined game ([SEALPROOFS]), which adds SnapVerify to the game that the Level B and AEAD hops leave (Appendix C.3), where its snap_key-keyed KDF is a random function and each segment AEAD output is a random string. It is zero in the [FLRR25] game and under None (Section 4.7.4). It covers the forgery and any further terms the authenticator's own construction requires. An intermediate snapshot (Section 4.7.3) is one more SnapVerify target in that game, at its own count. Both replacements are charged elsewhere: the KDF's to the snap_key subset of Level B in Adv_muPRF(KDF, B_KDF), and the AEAD's to Adv_muROR$(AEAD, B_AEAD). A key-holder content-binding property, where an authenticator provides one, is a separate notion from this without-key advantage and is not counted here.¶

C.3. ra-ROR Reduction

The reduction follows the [FLRR25] hybrid over the two-level key schedule (Section 4.5). Under HedgedRandom, with sk sampled independently of all CEKs, it first replaces the KDF keyed by sk, on its one hedge_label query, with a random function, which makes hedge_key uniform, and then replaces the KDF keyed by hedge_key with a random function. The two hops together cost Adv_hedge, after which every HedgedRandom output is distributed as a direct CSPRNG draw. Condition on no salt collision (Adv_salt_coll). A flat epoch key is the single-epoch case of the same argument.¶

Level A PRF hop

Replace the KDF keyed by each CEK with an independent random function. A multi-user PRF adversary with one user per CEK, u users, runs A and answers every CEK-keyed derivation from its oracle. The hop costs that adversary's advantage. With no salt collision, distinct messages and roles reach the random function at distinct inputs, so the commitment, payload_key, snap_key, and nonce_base are now uniform and independent for every message.¶

Header hop

Make StartDec reject every (salt, G, commitment) that no StartEnc under that CEK produced. After the Level A hop such a tuple passes the commitment check only by matching a uniform value that A has not seen, so the q_sd StartDec queries together accept one with probability at most q_sd / 2^(8*commitment_length), the cost of this hop. Every decryption session from here on belongs to a message that StartEnc produced.¶

Level B PRF hop

Replace the KDF keyed by each payload_key and by each snap_key with an independent random function, through a second multi-user PRF adversary with one user per payload_key and one per snap_key, up to 2 * q_m users. The two levels cannot share one game: a multi-user PRF game draws each user's key uniformly and independently from that user's key space, and payload_key and snap_key have that distribution only after the Level A hop. The epoch keys are then uniform and independent, one per distinct epoch index under each payload_key. B_KDF runs one of the two hop adversaries, chosen uniformly at random, so the two hops together cost 2 * Adv_muPRF(KDF, B_KDF). B_KDF has the users and queries of the level it runs (Appendix C.2), so at most max(u, 2 * q_m) users.¶

AEAD hop

B_AEAD runs A with each epoch key as one user of its multi-user AEAD game, n_ep users over sigma segment queries, and answers every segment encryption and decryption from that game. The Level B hop made the epoch keys uniform and independent, as that game draws its keys. In the game's random world each segment ciphertext is a uniformly random string and each segment decryption fails. When every nonce is taken directly from the CSPRNG, the game draws each nonce as the construction does, so a nonce collision is one of the events Adv_muROR$ already measures. Under a nonce hedge B_AEAD supplies the nonces to the nonce-respecting game instead, which is valid except when a nonce repeats under one segment key, an event charged to the conditional Adv_nonce_coll term. In derived nonce mode B_AEAD supplies the derived nonces, which the injective transform keeps distinct at the distinct positions a position-respecting adversary encrypts, so Adv_nonce_coll is zero (Appendix C.5). The hop costs Adv_muROR$(AEAD, B_AEAD), plus the conditional Adv_nonce_coll term under a nonce hedge.¶

Snapshot remainder

The snapshot authenticator's forgery, a SnapVerify acceptance that snapshot integrity (Section 5.1.4) rules out, in the game the AEAD hop leaves. Its probability is Adv_snap (Appendix C.2, Section 5.7).¶

B_KDF and B_AEAD each run in time approximately that of A.¶

C.4. Commitment

For fixed per-segment A_i at the shared position, ra-CMT security reduces to collision resistance of the commitment derivation map over the tuple (protocol_id, "commit", CEK, payload_info, G, commitment_length), with G empty by default (Section 5.3). Openings that differ only in A_i are outside this reduction: the map has no A_i input. The full ra-CMT game needs an additional AEAD AAD-commitment term, for which no SEAL instantiation bound is established here.¶

For commitment_length = L octets, the relevant quantities are:¶

fixed-pair collision probability:  2^(-8*L)
q-query birthday probability:      q^2 / 2^(8*L + 1)
collision-search work factor:      about 2^(4*L)

Thus 16 octets gives about 2^64 collision-search work, 32 octets about 2^128, 48 octets about 2^192, and 64 octets about 2^256, each capped by the collision resistance of the underlying hash. The fixed-pair collision probabilities at 32, 48, and 64 octets are 2^(-256), 2^(-384), and 2^(-512), respectively.¶

For fixed A_i, the ra-CMT-p advantage is bounded by two terms: the commitment collision bound above and the underlying AEAD's commitment bound for the forged position. Against a CEK holder, SEAL's strict authenticators with the ciphertext digest set give, under an externally authenticated snapshot, only the per-index binding of Section 5.6, not ra-CMT-p (Appendix C.1).¶

C.5. Nonce Modes

The unique-nonce transform of Section 4.5.3.2, which XORs the segment index and finality bit into nonce_base, follows TLS 1.3 ([RFC8446]) static-IV-XOR-identifier and STREAM ([HRRV15]) counter-plus-final-bit precedent. The transform is injective in the pair (i, is_final). The leading Nn - 8 octets of nonce_base are unchanged; XOR by its fixed low 8-octet value is a bijection on 8-octet strings; and (i, is_final) maps to the integer (i << 1) | is_final, which is a bijection from the index range i < 2^63 onto the 64-bit values. Distinct pairs therefore yield distinct nonces, and a derived nonce repeats only when an object encrypts twice at one pair.¶

Under both disciplines of Section 4.5.3.2 every encryption invocation uses a distinct (i, is_final) pair (Section 6.3, Section 4.9.3.1), so each reduces to nonce-respecting AEAD security under distinct nonces. That reduction is precedent, not a new proof.¶

In derived nonce mode Adv_nonce_coll is therefore zero within the scope of the bound (Appendix C.2), conditional on no salt collision. A rewrite reuses a segment's derived nonce, so the construction relies on the underlying MRAE AEAD: re-encrypting the same plaintext and associated data under the same key and nonce reproduces the same ciphertext, which leaks only equality of those inputs, while distinct inputs stay real-or-random secure ([RFC8452]). The formal treatment, in preparation ([SEALPROOFS]), replaces the nonce-respecting AEAD assumption of [FLRR25] with deterministic-MRAE security.¶

D.1. Key Schedule Design Rationale

The per-content salt makes the payload schedule unique even when a CEK is reused across messages, which matters for applications that derive CEKs from group keys. The encryptor chooses the salt locally at write time. A per-message counter would instead require synchronized state.¶

The CEK is 32 octets regardless of the AEAD key size Nk, so a 128-bit-key AEAD still derives its keys from a 256-bit CEK.¶

Epoch keys bound the number of AEAD invocations under any one segment encryption key. The underlying AEAD's per-key bounds (the birthday bound for 96-bit-nonce schemes, the block-size bound for AES, and the forgery bound for every scheme) limit security long before the nonce space is exhausted. Large content reaches them under one key even when written once, and rewrites only reach them sooner. Rekeying all the content would defeat random access, so epoch keys cap the per-key count without a full re-encryption.¶

Labels separate derivation roles: commitment and payload_key share the same inputs but different labels, making them independent under the PRF assumption. Once CEK and salt are chosen the hierarchy is fixed, with no mutable state to synchronize across writers.¶

D.2. Nonce Mode Design Rationale

Random mode is simplest but trusts the CSPRNG completely. Derived mode removes that trust. In a mutable profile it requires an MRAE AEAD, because an in-place rewrite reuses the segment nonce (Section 6.6). In the write-once profile the write-once rule keeps every derived nonce unique, and in the append-only profile the append-only rules and the current-count rule of Section 3.3 do. Under either, derived mode therefore admits any AEAD. A third rule was available and rejected: permitting a length change in either direction would let a truncation free indices the object had already spent, for a later append to encrypt new content at (Section 4.9.3.1).¶

The nonce mode is a profile parameter: a profile selects a valid (nonce_mode, snap_id, segment_commitment) tuple, subject to the MRAE requirement above.¶