Random-Access Authenticated Encryption
draft-sullivan-cfrg-raae-04
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
| Document | Type | Active Internet-Draft (individual) | |
|---|---|---|---|
| Author | Nick Sullivan | ||
| Last updated | 2026-11-02 | ||
| RFC stream | (None) | ||
| Intended RFC status | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-sullivan-cfrg-raae-04
Crypto Forum N. Sullivan
Internet-Draft Cryptography Consulting LLC
Intended status: Informational 2 November 2026
Expires: 6 May 2027
Random-Access Authenticated Encryption
draft-sullivan-cfrg-raae-04
Abstract
This document defines random-access authenticated encryption (raAE),
a primitive that partitions a message into an indexed sequence of
segments that can be encrypted and decrypted independently and in any
order. It also specifies SEAL (Segmented Encryption and
Authentication Layer), a parameterized construction that defines a
family of concrete raAE instantiations, one for each valid choice of
an Authenticated Encryption with Associated Data (AEAD) algorithm, a
key derivation function (KDF), and associated parameters.
SEAL supports immutable (write-once), append-only, and mutable (in-
place ciphertext rewrite) operations, each with per-segment
authentication. A separately configured snapshot authenticator can
additionally authenticate the complete, indexed segment set.
The document also defines the security notions of raAE, specifies the
requirements for conforming constructions, and analyzes SEAL against
those requirements. Concrete cipher suites, serialization layouts,
and test vectors for SEAL are specified in a companion document.
Discussion Venues
This note is to be removed before publishing as an RFC.
Discussion of this document takes place on the raae mailing list
(raae@ietf.org), which is archived at
https://mailarchive.ietf.org/arch/browse/raae/.
Source for this draft and an issue tracker can be found at
https://github.com/grittygrease/draft-sullivan-cfrg-raae.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Sullivan Expires 6 May 2027 [Page 1]
Internet-Draft raAE November 2026
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 6 May 2027.
Copyright Notice
Copyright (c) 2026 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Related Work . . . . . . . . . . . . . . . . . . . . . . 6
2. Conventions and Terminology . . . . . . . . . . . . . . . . . 7
2.1. Taxonomy . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2. Notation . . . . . . . . . . . . . . . . . . . . . . . . 10
3. The raAE Primitive . . . . . . . . . . . . . . . . . . . . . 12
3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2. Interface . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3. Extended Interface . . . . . . . . . . . . . . . . . . . 13
3.3.1. Witness Rules . . . . . . . . . . . . . . . . . . . . 15
4. The SEAL Construction . . . . . . . . . . . . . . . . . . . . 17
4.1. Construction Overview . . . . . . . . . . . . . . . . . . 19
4.2. Component Suite and Parameters . . . . . . . . . . . . . 19
4.2.1. Suite Choices . . . . . . . . . . . . . . . . . . . . 21
4.2.2. Profile-Level Constants . . . . . . . . . . . . . . . 22
4.2.3. Algorithm-Determined Sizes . . . . . . . . . . . . . 22
4.2.4. Per-Message Inputs . . . . . . . . . . . . . . . . . 22
4.3. The KDF Combiner . . . . . . . . . . . . . . . . . . . . 23
4.3.1. Two-Step KDF . . . . . . . . . . . . . . . . . . . . 24
4.3.2. One-Step KDF . . . . . . . . . . . . . . . . . . . . 25
4.4. SEAL Encodings and Labels . . . . . . . . . . . . . . . . 25
4.4.1. Payload Info Construction . . . . . . . . . . . . . . 25
4.4.2. Segment AAD . . . . . . . . . . . . . . . . . . . . . 26
Sullivan Expires 6 May 2027 [Page 2]
Internet-Draft raAE November 2026
4.4.3. Labels . . . . . . . . . . . . . . . . . . . . . . . 28
4.5. Key Schedule and Nonce Generation . . . . . . . . . . . . 28
4.5.1. Payload Schedule . . . . . . . . . . . . . . . . . . 29
4.5.2. Epoch Key Derivation . . . . . . . . . . . . . . . . 29
4.5.3. Nonce Generation . . . . . . . . . . . . . . . . . . 30
4.6. Commitment . . . . . . . . . . . . . . . . . . . . . . . 33
4.7. Snapshot Authenticator . . . . . . . . . . . . . . . . . 33
4.7.1. Interface and Requirements . . . . . . . . . . . . . 33
4.7.2. Segment Leaf . . . . . . . . . . . . . . . . . . . . 37
4.7.3. Intermediate and Public Snapshots . . . . . . . . . . 38
4.7.4. None . . . . . . . . . . . . . . . . . . . . . . . . 40
4.8. Segment Algorithms . . . . . . . . . . . . . . . . . . . 40
4.8.1. EncryptSegment . . . . . . . . . . . . . . . . . . . 41
4.8.2. DecryptSegment . . . . . . . . . . . . . . . . . . . 42
4.8.3. RewriteSegment . . . . . . . . . . . . . . . . . . . 42
4.9. Top-level Algorithms . . . . . . . . . . . . . . . . . . 42
4.9.1. Read-Only Operations . . . . . . . . . . . . . . . . 43
4.9.2. Rewritable Operations . . . . . . . . . . . . . . . . 47
4.9.3. Changing Message Length . . . . . . . . . . . . . . . 48
5. Security Analysis . . . . . . . . . . . . . . . . . . . . . . 52
5.1. Security Notions . . . . . . . . . . . . . . . . . . . . 52
5.1.1. ra-ROR . . . . . . . . . . . . . . . . . . . . . . . 52
5.1.2. ra-CMT . . . . . . . . . . . . . . . . . . . . . . . 54
5.1.3. ra-CMT-p . . . . . . . . . . . . . . . . . . . . . . 54
5.1.4. Snapshot Authentication . . . . . . . . . . . . . . . 54
5.2. Relations to Other Notions . . . . . . . . . . . . . . . 55
5.3. Adversary Model and Assumptions . . . . . . . . . . . . . 55
5.4. raAE Construction Requirements . . . . . . . . . . . . . 57
5.5. Segment Confidentiality and Integrity . . . . . . . . . . 59
5.6. Commitment Security . . . . . . . . . . . . . . . . . . . 60
5.7. Snapshot Authenticator Security . . . . . . . . . . . . . 62
5.8. Capacity and Usage Limits . . . . . . . . . . . . . . . . 63
5.8.1. Accounting Model . . . . . . . . . . . . . . . . . . 64
5.8.2. Aggregate Security Accounting . . . . . . . . . . . . 64
5.8.3. Limit Classes . . . . . . . . . . . . . . . . . . . . 65
5.8.4. Maximum Object Size . . . . . . . . . . . . . . . . . 66
5.8.5. Rewrite Capacity . . . . . . . . . . . . . . . . . . 68
5.8.6. Choosing epoch_length . . . . . . . . . . . . . . . . 69
5.8.7. Derivations . . . . . . . . . . . . . . . . . . . . . 70
6. Security Considerations . . . . . . . . . . . . . . . . . . . 73
6.1. Resource Exhaustion . . . . . . . . . . . . . . . . . . . 73
6.2. Detection Summary . . . . . . . . . . . . . . . . . . . . 74
6.3. Nonce Misuse . . . . . . . . . . . . . . . . . . . . . . 75
6.4. Parameter Set Mismatch . . . . . . . . . . . . . . . . . 76
6.5. Framing and Label Errors . . . . . . . . . . . . . . . . 77
6.6. Parameter Misuse . . . . . . . . . . . . . . . . . . . . 77
6.7. Snapshot Integrity Limitations . . . . . . . . . . . . . 77
6.8. Salt Reuse . . . . . . . . . . . . . . . . . . . . . . . 78
Sullivan Expires 6 May 2027 [Page 3]
Internet-Draft raAE November 2026
6.9. Rewrite Hazards . . . . . . . . . . . . . . . . . . . . . 79
6.10. Constant-Time Implementation . . . . . . . . . . . . . . 80
6.11. Properties Not Provided . . . . . . . . . . . . . . . . . 81
6.12. Cross-Application Domain Separation . . . . . . . . . . . 81
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 82
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.1. Normative References . . . . . . . . . . . . . . . . . . 82
8.2. Informative References . . . . . . . . . . . . . . . . . 83
Appendix A. Optional Plaintext-Bound Nonce Construction . . . . 85
Appendix B. Optional Hedged Randomness . . . . . . . . . . . . . 86
Appendix C. Proof Status and Security Claim Provenance . . . . . 87
C.1. Provenance of the Security Claims . . . . . . . . . . . . 88
C.2. Advantage Notation and Adversary Parameters . . . . . . . 90
C.3. ra-ROR Reduction . . . . . . . . . . . . . . . . . . . . 92
C.4. Commitment . . . . . . . . . . . . . . . . . . . . . . . 94
C.5. Nonce Modes . . . . . . . . . . . . . . . . . . . . . . . 95
Appendix D. Design Rationale . . . . . . . . . . . . . . . . . . 95
D.1. Key Schedule Design Rationale . . . . . . . . . . . . . . 95
D.2. Nonce Mode Design Rationale . . . . . . . . . . . . . . . 96
Appendix E. Changes Since -03 . . . . . . . . . . . . . . . . . 96
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 97
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 98
1. Introduction
Large encrypted content is often stored as a sequence of fixed-size
segments, so that an application can read or modify any part of it
without processing the whole. Encrypted backups, encrypted file
formats, object stores with partial updates, and full-disk encryption
over fixed-size blocks all work this way. Such a system needs to
encrypt, decrypt, or re-encrypt any individual segment on its own and
in arbitrary order, and to verify that the stored object as a whole
is authentic and complete, without re-encrypting the segments that
did not change.
This document specifies the raAE primitive (Section 3), whose base
interface and security notions come from Fábrega et al. ([FLRR25]),
and defines SEAL (Segmented Encryption and Authentication Layer), a
parameterized construction of raAE. The base algorithms encrypt and
decrypt segments in arbitrary order, so a caller can read or replace
any segment on its own. On top of that base, the extended raAE
interface adds in-place rewrite and a snapshot, a stored value that
authenticates the segment set and count the writer recorded for it.
A rewrite re-encrypts only the changed segment and updates the
snapshot, leaving every other segment untouched. Appending to the
end, or truncating from the end, composes the same per-segment
operations, so the snapshot stays consistent without a separate
algorithm.
Sullivan Expires 6 May 2027 [Page 4]
Internet-Draft raAE November 2026
SEAL builds the primitive from a chosen AEAD algorithm, a key
derivation function (KDF), and configuration parameters. Under a
snapshot authenticator, it binds every segment and the count into a
keyed snapshot that an adversary cannot forge without the content-
derived key.
.------------------------------.
| raAE primitive |
| abstract interface |
'------------------------------'
|
v
.--------------------------------------------------------------.
| SEAL construction |
| parameterized by a cipher suite (AEAD + KDF), a maximum |
| segment size, and an epoch length |
| |
| .----------------------. .----------------------. |
| | mutability: | | snapshot: | |
| | immutable | | none | present | |
| | append-only | | | |
| | mutable | | | |
| '----------------------' '----------------------' |
'--------------------------------------------------------------'
| provides
+----------------+----------------+
| |
v v
.----------------------------. .------------------------.
| per-segment authenticity | | snapshot integrity |
| (always present) | | (when present) |
'----------------------------' '------------------------'
Figure 1: The raAE primitive and the SEAL construction
raAE separates the two authentication scopes that applications often
conflate:
Per-segment authenticity: One AEAD tag verifies under the segment
index, a finality bit marking the last segment, and any caller-
supplied associated data. It does not establish that the segment
belongs to the current snapshot.
Snapshot integrity: When a snapshot authenticator is configured,
snapshot verification checks that the present segment set and the
count are exactly what the writer recorded for that snapshot,
under a content-derived key. Verification targets the whole
segment set, and, where the authenticator supports it, can instead
Sullivan Expires 6 May 2027 [Page 5]
Internet-Draft raAE November 2026
confirm that a designated subset of segments is included at their
recorded positions, without reading the others (Section 4.7.1).
It does not establish freshness against whole-object rollback,
which a consuming protocol must supply.
raAE and SEAL are deliberately distinct layers. A consuming protocol
supplies serialization, storage transactions, key management, and
rollback protection, which are out of scope here. The full boundary
of what raAE does not provide is Section 6.11.
The remainder of this document presents raAE first and SEAL second.
Section 1.1 situates raAE against prior segmented authenticated-
encryption (AE) constructions. Section 2 fixes terminology and
notation. Section 3 specifies the extended raAE primitive and its
snapshot operations. Section 4 defines SEAL. Section 5 states the
target security properties an raAE construction must meet, the
assumptions SEAL's components must satisfy, and the operational
limits on its use, and defines the security notions. Cipher suites,
serialization layouts, named instantiations, and test vectors are
specified in the companion document [I-D.sullivan-seal-concrete].
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.
Sullivan Expires 6 May 2027 [Page 6]
Internet-Draft raAE November 2026
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. Conventions and Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in
BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
A message segment is a unit of plaintext that is individually
encrypted and authenticated. Segments need not be uniform in length.
A construction MAY set a maximum segment size, and the construction
Sullivan Expires 6 May 2027 [Page 7]
Internet-Draft raAE November 2026
or its consuming format MAY set a minimum, which applies to every
segment, the final one included, unless the format exempts the final
segment. A segment may be any length within those bounds. The final
segment of a message is the one at its highest index, whatever that
segment's length.
A message is the content that one CEK and salt pair protects, the
unit the primitive encrypts. An object is that message in stored
form: the ciphertext segments, their metadata, and any snapshot that
a storage layer holds. Each object carries one message, whose
content may change through rewrite and length-changing operations.
A ciphertext core is the AEAD encryption output corresponding to one
message segment, excluding file-level headers and external segment
metadata. An AEAD-specific split divides this output into ct_i, the
encrypted segment body, and tag_i, the authentication tag.
A ciphertext segment is the stored representation of one encrypted
message segment. Depending on nonce_mode, it contains the ciphertext
core and may also contain a stored nonce or other per-segment
metadata.
Segment metadata is per-segment information needed to decrypt or
verify a ciphertext segment, such as a stored nonce, tag, finality
status, or profile-defined values.
This document writes AEAD.Encrypt and AEAD.Decrypt for the
authenticated encryption and decryption operations defined in
[RFC5116].
Symbol form follows the layer a name belongs to. The abstract
interface and the analysis use mathematical notation: a capital
letter is an operand of that interface, either an octet string (K, N,
G, T_g, A_i, M_i, C_i) or the per-message state (S). A lowercase
letter is an integer index or bound (i, e, r), except the position
identifier p, a pair (i, b) (Section 3.3).
N with a lowercase letter is a size that a chosen component fixes
rather than one a deployment picks: the AEAD (Nk, Nn, Nt, Nb), the
KDF (Nh), the snapshot authenticator (Na), or the nonce mode (Np).
Everything the construction names concretely uses lowercase
snake_case, whatever its type: octet strings (salt, commitment,
segment_key, ct_i), counts (n_seg, n_ep), lengths a deployment
configures (segment_max, commitment_length), and identifiers, which
take an _id suffix (aead_id, kdf_id, snap_id, protocol_id).
Sullivan Expires 6 May 2027 [Page 8]
Internet-Draft raAE November 2026
Names that take arguments follow the same split. Initialisms are
capitalized (LH, KDF, AEAD, and XOF, an extendable-output function),
and LH is defined in Section 4.3. The raAE tuple is CamelCase
(KeyGen, StartEnc, EncSeg, StartDec, DecSeg, RewriteSeg, SnapVerify),
while the methods of a component it parameterizes over are lowercase
(snapshot, verify, add, remove, and set_length of Section 4.7.1), so
a name shows which interface it belongs to. Derivations this
document defines are lowercase (encode and frame in Section 4.3, leaf
in Section 4.7.2, and nonce in Section 4.5.3).
A subscript selects one instance of a value: X_i is X for the segment
at index i, as in A_i, P_i, ct_i, and tag_i, and d_e is the epoch
head for epoch e ([I-D.sullivan-seal-concrete]). A value written
f(i), as in segment_key(i) or nonce(i), is the value that the named
derivation defines for index i.
Two suffixes and one prefix recur. A _label suffix is an ASCII
constant that separates one derivation from another (aad_label,
epoch_key_label). A _calc suffix marks a value recomputed for
comparison against a stored one (d_calc(e) and leaf_calc(i) in
[I-D.sullivan-seal-concrete]). An Adv_ prefix names an adversary's
advantage in the analysis (Adv_snap, Adv_muPRF).
The remaining terms (ikm, label, info, L, salt, CEK, protocol_id,
nonce_mode, payload_info, segment_commitment, epoch_length, epoch,
epoch_key, payload_key, segment_key, snap_key, and the commitment)
are defined in Section 4 where they first appear.
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.
Sullivan Expires 6 May 2027 [Page 9]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 10]
Internet-Draft raAE November 2026
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).
Sullivan Expires 6 May 2027 [Page 11]
Internet-Draft raAE November 2026
3. The raAE Primitive
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.
Sullivan Expires 6 May 2027 [Page 12]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 13]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 14]
Internet-Draft raAE November 2026
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.
3.3.1. Witness Rules
A witness is untrusted data that a subset SnapVerify reads in place
of the segments it does not verify: a deterministic function of the
subset presented, the (index, input) set, the count, and the snapshot
key, which may include the inputs of segments not presented. The
authenticator specifies its witness. Under a strict ordering
(Section 4.7.1) it is the count and per-segment inputs, or values
derived from them, so a witness supplies the A_i of the segments it
stands for (Section 4.7.2, [I-D.sullivan-seal-concrete]). A subset
SnapVerify that reads a witness checks it against the keyed snapshot,
so the witness adds no trust to that check. A witness is not part of
the keyed snapshot.
An update reads a witness for the segment set before the update: its
count and, in place of the inputs the update leaves unchanged, what
the authenticator needs to compute the new value. The authenticator
defines that witness and how it is checked
([I-D.sullivan-seal-concrete]).
An authenticator's summary is state it derives from the inputs and
keeps beside the object so that an update reads fewer of them;
[I-D.sullivan-seal-concrete] calls its stored form the aux region. A
whole-object SnapVerify does not validate a stored summary: it
recomputes the value from the segments and never reads the stored
copy.
The writer MUST NOT use a witness it has not authenticated: one it
produced itself as the sole writer, or one it has checked against a
verified snapshot for the same commitment and count (Section 6.7).
Sullivan Expires 6 May 2027 [Page 15]
Internet-Draft raAE November 2026
Each removed input MUST be one the writer produced itself as the sole
writer or be checked at its index against the same verified snapshot,
unless the authenticator permits its use without that check
([I-D.sullivan-seal-concrete]). An authenticator grants that
permission only where an incorrect input leaves no segment set, short
of a forgery, verifying against the resulting snapshot or any
snapshot derived from it. It lists the permitted cases and their
assumptions.
When an update decrypts a stored record, the input formed from the
same record bytes, under the finality bit and A_i it decrypted under,
MUST match the authenticated or locally trusted input at that
position. If the authenticator permits removal without checking the
input, the removed input MUST instead be that record's own input,
read once with the record. The update MUST fail if any required
check or decryption fails.
A snapshot is verified in one of two ways. It is known to be current
when it comes from the locally trusted storage of a sole writer or
from authentication outside the construction that carries external
freshness (Section 6.7). Otherwise a whole-object SnapVerify that
accepts the stored object verifies the stored snapshot.
In an application that requires whole-object rollback resistance
(Section 6.7), a writer MUST update only from a current verified
snapshot, or it would certify a rolled-back state as the next
version.
Under an append-only profile (Section 4.9.3.1) the count an append
starts from MUST be current, whatever the application's rollback
requirement: the writer takes n_seg from locally trusted storage or
from authentication outside the construction that carries external
freshness, never from the stored object alone. An append from a
rolled-back count can encrypt new content at (i, b) positions the
object has already used. In derived nonce mode that is the nonce
reuse of Section 6.3, unless the AEAD provides misuse-resistant
authenticated encryption (MRAE). In random nonce mode the two
encryptions draw independent nonces, so AEAD-level nonce reuse occurs
only by collision. Still, the pair is encrypted twice, which the
[FLRR25] hypothesis excludes regardless of nonce mode
(Section 5.1.1).
Sullivan Expires 6 May 2027 [Page 16]
Internet-Draft raAE November 2026
4. The SEAL Construction
SEAL is a construction for the raAE primitive of Section 3, realizing
its extended interface from a KDF, an AEAD, the labels, a nonce-
generation method, and an optional snapshot authenticator. Its KDF
combiner (Section 4.3) frames every derived key and input over any
KDF with a two-step or one-step form. SEAL provides commitment
around the AEAD, which need not itself commit.
A SEAL construction MAY select any AEAD, KDF, nonce mode, commitment
configuration, or snapshot authenticator that satisfies the
requirements of this section. Section 5 derives SEAL's bounds from
the abstract properties of these components. Concrete parameter
choices and interoperable suites are in [I-D.sullivan-seal-concrete].
In the key hierarchy below, a CEK and per-content salt feed the
payload schedule, which derives four per-message values
(Section 4.5).
Sullivan Expires 6 May 2027 [Page 17]
Internet-Draft raAE November 2026
CEK + salt
|
v
.-----------.
| Payload |
| Schedule |
'-----------'
/ | | \
v v v v
commit payload nonce snap
key base key
| | | |
v v v |
.---. .------. .-----. |
|cmt| |seg | |nonce| |
| | |key(i)| | (i) | |
'---' '------' '-----' |
\ / |
\ / |
v v |
.----------. |
| AEAD | |
| Seal(i) | |
'----------' |
/ \ |
v v |
ct_i tag_i |
\ |
v v
.-----------------.
| Snapshot |
| Authenticator |
'-----------------'
|
v
snapshot
Figure 2: SEAL Key Hierarchy
The figure shows each segment's tag feeding the authenticator. Its
actual per-segment input is the segment leaf, formed from the
metadata entry (Section 4.7.2).
Sullivan Expires 6 May 2027 [Page 18]
Internet-Draft raAE November 2026
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:
+============+====================================================+
| raAE | SEAL realization |
| operation | |
+============+====================================================+
| StartEnc | Derive the payload schedule from the CEK and salt, |
| | committing G (Section 4.5), and, under a snapshot |
| | authenticator, the snapshot over the empty set |
+------------+----------------------------------------------------+
| StartDec | Re-derive the schedule and verify the stored |
| | commitment (Section 4.6) |
+------------+----------------------------------------------------+
| EncSeg, | EncryptSegment and DecryptSegment (Section 4.8) |
| DecSeg | |
+------------+----------------------------------------------------+
| RewriteSeg | RewriteSegment, then update the snapshot |
| | authenticator for the changed segment |
| | (Section 4.9.2.1) |
+------------+----------------------------------------------------+
| SnapVerify | Check the index set, count, and authenticator |
| | inputs, then verify the snapshot via the |
| | authenticator (Section 4.7) |
+------------+----------------------------------------------------+
Table 1: raAE operations and their SEAL realizations
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
Table 2 lists the parameters, inputs, and derived values, with what
sets each and where it is defined.
+===================+===================+=============+==========+
| Parameter | Type or range | Set by | Defined |
| | | | in |
+===================+===================+=============+==========+
| AEAD | RFC 5116 | suite | Section |
| | algorithm | | 4.2.1 |
+-------------------+-------------------+-------------+----------+
| KDF | KDF algorithm | suite | Section |
Sullivan Expires 6 May 2027 [Page 19]
Internet-Draft raAE November 2026
| | | | 4.3 |
+-------------------+-------------------+-------------+----------+
| segment_max | power of two, at | suite | Section |
| | least 4096 | | 4.2.1 |
+-------------------+-------------------+-------------+----------+
| epoch_length | integer r in 0 to | suite | Section |
| | 63 | | 4.5.2 |
+-------------------+-------------------+-------------+----------+
| protocol_id | octet string | application | Section |
| | | | 6.12 |
+-------------------+-------------------+-------------+----------+
| nonce_mode | "random" or | message, | Section |
| | "derived" | within the | 4.5.3 |
| | | profile | |
+-------------------+-------------------+-------------+----------+
| aad_label | ASCII string | profile | Section |
| | | | 4.4.2 |
+-------------------+-------------------+-------------+----------+
| commitment_length | integer, at least | profile | Appendix |
| | 16, default Nh | | C.4 |
+-------------------+-------------------+-------------+----------+
| Nk, Nn, Nt, Nb | sizes in octets | AEAD | Section |
| | | | 2.2 |
+-------------------+-------------------+-------------+----------+
| Nh | size in octets | KDF | Section |
| | | | 2.2 |
+-------------------+-------------------+-------------+----------+
| CEK | 32 uniform random | message | Section |
| | octets | input | 4.5 |
+-------------------+-------------------+-------------+----------+
| salt | 32 uniform random | message | Section |
| | octets | input | 4.5 |
+-------------------+-------------------+-------------+----------+
| payload_info | ordered element | message | Section |
| | list | input | 4.4 |
+-------------------+-------------------+-------------+----------+
| G | octet string, | message | Section |
| | empty by default | input | 4.6 |
+-------------------+-------------------+-------------+----------+
| commitment | commitment_length | derived per | Section |
| | octets | message | 4.5 |
+-------------------+-------------------+-------------+----------+
| payload_key | Nk octets | derived per | Section |
| | | message | 4.5 |
+-------------------+-------------------+-------------+----------+
| snap_key | Nh octets | derived per | Section |
| | | message | 4.5 |
+-------------------+-------------------+-------------+----------+
Sullivan Expires 6 May 2027 [Page 20]
Internet-Draft raAE November 2026
| nonce_base | Nn octets, | derived per | Section |
| | derived mode only | message | 4.5 |
+-------------------+-------------------+-------------+----------+
| epoch_key(i) | Nk octets | derived per | Section |
| | | segment | 4.5.2 |
+-------------------+-------------------+-------------+----------+
| segment_key(i) | Nk octets | derived per | Section |
| | | segment | 4.5.2 |
+-------------------+-------------------+-------------+----------+
| nonce(i) | Nn octets | derived per | Section |
| | | segment | 4.5.3 |
+-------------------+-------------------+-------------+----------+
| segment_aad(i, | octet string | derived per | Section |
| is_final, A_i) | | segment | 4.4.2 |
+-------------------+-------------------+-------------+----------+
| tag_i | Nt octets | derived per | Section |
| | | segment | 4.8 |
+-------------------+-------------------+-------------+----------+
Table 2: Parameters, inputs, and derived values
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.2.1. Suite Choices
A suite is assembled from the following choices.
AEAD: An authenticated encryption with associated data algorithm
satisfying the interface of [RFC5116], with Nk-octet keys, Nn-
octet nonces, and Nt-octet authentication tags.
KDF: A key derivation function supporting the abstract interface
defined in Section 4.3.
segment_max: A positive integer, a power of two and at least 4096
octets. Each segment carries at most this many plaintext octets.
The length-dependent limits of Section 5.8 are computed at this
size.
epoch_length: A non-negative integer r in 0 to 63. Each epoch
covers 2^r consecutive segments aligned to a multiple of 2^r, so r
sets the key-rotation granularity: r = 0 gives a fresh epoch key
per segment and r = 63 one key for all segments (Section 4.5.2).
Profiles MAY restrict r further per AEAD.
Sullivan Expires 6 May 2027 [Page 21]
Internet-Draft raAE November 2026
protocol_id: An application-chosen octet string that binds all
derived values to a specific protocol version. Selection guidance
is in Section 6.12.
nonce_mode: A payload_info element selecting one of two nonce
constructions, "random" or "derived". The constructions are
defined in Section 4.5.3, and the valid (nonce_mode, snap_id,
segment_commitment) tuples depend on the profile.
4.2.2. Profile-Level Constants
One constant is fixed by the profile rather than carried per message.
aad_label: A profile-level ASCII string bound as the first element
of the segment AAD encoding (Section 4.4.2). Consuming protocols
MAY define their own profiles with a distinct aad_label.
4.2.3. Algorithm-Determined Sizes
The sizes Nk, Nn, Nt, and Nh are fixed by the chosen AEAD and KDF
rather than by the parameter set directly, as is Nb where it is
defined. They are defined in Section 2.2. One configurable length
defaults from Nh.
commitment_length: A positive integer of at least 16, defaulting to
Nh, the length in octets of the key commitment prefix. The
collision bounds for each length are given in Appendix C.4.
4.2.4. Per-Message Inputs
An encrypted message is built from four input values.
CEK: A 32-octet uniform random Content Encryption Key generated
fresh for each message. The CEK is input keying material for the
key schedule, not an AEAD key.
salt: A per-content value of 32 uniformly random octets. The salt
separates payload schedule outputs across messages even when the
CEK is reused. Section 4.9.1.1 and Section 4.9.3 give the rules
for generating and reusing it, and Section 6.8 analyzes the
consequences of reuse.
payload_info: The committed record of the object's configuration: an
ordered list of parameter set context elements covering key
derivation, AEAD operations, AAD construction, and nonce
construction, which the commitment (Section 4.6) binds. The
profile fixes the concrete element set and their encodings.
SEAL's payload_info is specified in Section 4.4.
Sullivan Expires 6 May 2027 [Page 22]
Internet-Draft raAE November 2026
G: An octet string of global associated data, the G input of
StartEnc in the raAE primitive (Section 3.2), binding whole-
message application context such as a name, version, or policy. G
defaults to the empty octet string and is never stored: a
decryptor supplies it from application context, and the commitment
binds it (Section 4.6).
The remaining symbols in Table 2 are derived values. The payload
schedule computes the per-message values once from the CEK and
payload_info, fixing them for the message's lifetime (Section 4.5).
The commitment additionally binds G (Section 4.6). Per-segment
values are defined where they are computed, in the sections Table 2
cites.
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
Sullivan Expires 6 May 2027 [Page 23]
Internet-Draft raAE November 2026
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.
4.3.1. Two-Step KDF
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)
The notation ...x means each element of the sequence x, whether ikm
or info, is a separate argument to encode. A single octet string is
the one-element sequence containing it. An absent value is the empty
sequence and contributes no arguments. The empty sequence and the
Sullivan Expires 6 May 2027 [Page 24]
Internet-Draft raAE November 2026
one-element sequence whose element is the empty octet string are
distinct: the first adds nothing to the encode, the second adds one
zero-length field. A derivation with no info MUST use the empty
sequence, not the empty octet string, so that every implementation
encodes a given (protocol_id, label, ikm, info, L) tuple to the same
octets. The protocol_id appears in both the Extract salt and the
extract_input as a defensive measure, and binding in either position
suffices for domain separation.
The label appears in both Extract and Expand so that label binding is
preserved even if one phase is weak in isolation. Implementations
MAY amortize the Extract computation internally when deriving
multiple outputs from the same protocol_id, label, and ikm.
4.3.2. One-Step KDF
KDF(protocol_id, label, ikm, info, L):
M = encode(protocol_id, label,
encode(...ikm), encode(...info),
uint16(L))
return XOF(M, L)
The XOF-based form frames ikm and info each as a single element of
one length-prefixed encode and squeezes L octets of output.
protocol_id binding is via the message-side encode prefix only. In
both forms the encoded input ends with uint16(L): the two-step form
places it last in expand_info and the one-step form places it last in
M. Within a fixed kdf_id, distinct (protocol_id, label, ikm, info,
L) tuples have distinct framed inputs, subject to the digest-
collision qualification in Section 5.4. KDF output pseudorandomness
is a separate requirement; distinct framed inputs can still produce
colliding outputs. The two forms are not mutually injective: a
cipher suite's kdf_id selects one form for that suite, and
payload_info commits to the kdf_id (Section 4.4), so no derivation
ever compares outputs across forms. The two-step form binds ikm in
Extract and info in Expand. A multi-value ikm or info is the encode
of its elements, so any number of elements is admitted.
4.4. SEAL Encodings and Labels
4.4.1. Payload Info Construction
payload_info = [aead_id, segment_max_be, kdf_id, snap_id,
segment_commitment, nonce_mode, epoch_length_u8, salt]
Element encodings for SEAL:
Sullivan Expires 6 May 2027 [Page 25]
Internet-Draft raAE November 2026
* aead_id: 2 octets, uint16(id), the unsigned 16-bit AEAD
identifier.
* segment_max_be: 4 octets, uint32(segment_max).
* kdf_id: 2 octets, uint16(id), the unsigned 16-bit KDF identifier.
* snap_id: 2 octets, uint16(id), the snapshot authenticator
identifier.
* segment_commitment: 1 octet, 0x00 when the leaf does not bind the
segment's content and 0x01 when it does (Section 4.7.1). It is a
choice independent of snap_id, but not every (snap_id,
segment_commitment) pair is sound, so a profile selects a valid
one.
* nonce_mode: 1 octet, the nonce construction: 0x00 for random, 0x01
for derived. A profile MAY select any valid (nonce_mode, snap_id,
segment_commitment) tuple.
* epoch_length_u8: 1 octet, uint8(epoch_length). Implementations
MUST reject epoch_length >= 64 on both encode and decode.
* salt: 32 raw octets, the per-message salt.
The aad_label is a profile-level constant for SEAL (see
Section 4.4.2) and is not carried in payload_info. The KDF
(Section 4.3) applies frame to each element of the list.
4.4.2. Segment AAD
The segment AAD binds each segment to its context. What it must
carry depends on the nonce mode: a random nonce binds neither the
segment index nor the finality bit, so the AAD must, whereas a
derived nonce binds both (Section 4.5.3.2).
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)
Sullivan Expires 6 May 2027 [Page 26]
Internet-Draft raAE November 2026
+=============+======================+============================+
| | Random nonce mode | Derived nonce mode |
+=============+======================+============================+
| Index i and | bound in the AAD | bound in the nonce |
| is_final | | |
+-------------+----------------------+----------------------------+
| A_i, when | appended as a fourth | the sole variable element |
| present | encode element | |
+-------------+----------------------+----------------------------+
| A_i, when | omitted, not a zero- | segment_aad is empty, with |
| empty | length element | no associated-data pass |
+-------------+----------------------+----------------------------+
Table 3: Segment AAD by nonce mode
aad_label is the profile-chosen label from the parameter set, the
index i is a big-endian 8-octet integer, and is_final is 1 for the
last segment and 0 for all others. Because encode length-prefixes
every element, omitting an empty A_i stays injective, so the index
and finality bit remain authenticated. Any profile that defines a
random-mode segment_aad MUST preserve injectivity and MUST
authenticate the segment index and finality bit. aad_label is bound
transitively through protocol_id (Section 6.4), so segment_aad need
not repeat it for cross-profile separation.
More generally, the binding of the triple (i, is_final, A_i) MUST be
unambiguous under one segment key, so that no two distinct triples
present the same inputs to the AEAD. In random nonce mode
segment_aad alone MUST injectively bind the triple, because the nonce
is an independent random draw. In derived nonce mode i and is_final
are bound in the nonce and A_i, when present, in segment_aad, and the
(nonce, segment_aad) pair MUST jointly determine the triple
(Section 4.5.3.2).
A_i is the caller-supplied per-segment associated data of EncSeg and
DecSeg (Section 3.2), passed to the segment algorithms (Section 4.8).
It MAY be empty and MAY differ per segment. Unlike a global
associated data value G, which the commitment fixes at creation
(Section 4.6), A_i rides the per-segment AEAD associated data and is
rewritable: a rewrite can change a segment's A_i.
The salt is not included in the AAD because it is already bound into
segment_key via the payload schedule. Different messages produce
different segment keys even at the same index. Transposing two
segments within a message fails because the AAD at each position
encodes the expected index.
Sullivan Expires 6 May 2027 [Page 27]
Internet-Draft raAE November 2026
Because each segment binds its index and finality bit (Table 3),
unauthorized truncation and extension fail per-segment
authentication, which Section 4.9.1.2 requires a decryptor to check.
Authorized truncation by the CEK holder re-marks the new last segment
as final, or empties the object, and updates the snapshot
(Section 4.9.3).
The per-segment AEAD binds a segment's index and finality, not its
length, by the same means. A segment's ciphertext length is
authenticated implicitly by the AEAD tag over the ciphertext:
altering, truncating, or splicing a segment ciphertext is an AEAD
forgery, not a parsing ambiguity. Because segments may be shorter
than segment_max, the consuming format MUST convey each segment's
ciphertext length to the decoder. A wrong length yields an AEAD
rejection, never a silent accept.
4.4.3. Labels
+============================+===================+===============+
| Derivation role | Label variable | Value |
+============================+===================+===============+
| Commitment | commit_label | "commit" |
+----------------------------+-------------------+---------------+
| Payload key | payload_key_label | "payload_key" |
+----------------------------+-------------------+---------------+
| Snapshot authenticator key | snap_key_label | "snap_key" |
+----------------------------+-------------------+---------------+
| Nonce base | nonce_base_label | "nonce_base" |
+----------------------------+-------------------+---------------+
| Epoch key | epoch_key_label | "epoch_key" |
+----------------------------+-------------------+---------------+
Table 4: SEAL core KDF labels by role
SEAL fixes each label to the value above. The construction formulas
reference labels by variable name, so the labels are SEAL parameters
rather than constants of the raAE construction. Each value is an
ASCII string and is distinct from all others. These are the always-
present key-schedule labels. The configured snapshot authenticator
(Section 4.7.1), the plaintext-bound nonce construction (Appendix A),
and hedged randomness (Appendix B) each define their own labels.
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.
Sullivan Expires 6 May 2027 [Page 28]
Internet-Draft raAE November 2026
4.5.1. Payload Schedule
Four values are derived from the CEK and per-content salt.
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)
G is the global associated data of Section 4.2.4, always the last
element of the commitment info. It defaults to the empty octet
string, one zero-length element, so every commitment derivation
includes it. The other three derivations never take G.
4.5.2. Epoch Key Derivation
An AEAD with a 96-bit nonce (Nn = 12) has, at a 2^(-32) collision-
probability target, a random-nonce budget of about 2^32 encryptions
per key. For rewritable content, this limit can be reached through
repeated modifications to the same segments. Epoch keys partition
the nonce space: each epoch key covers at most 2^r segment positions
(initial writes plus rewrites), so the per-key invocation count is
bounded regardless of the content's total size. Meeting an aggregate
target also requires Section 5.8.2.
When epoch_length = r is specified, the segment key for segment i is
an epoch key derived from the payload key:
segment_key(i):
epoch_index = i >> epoch_length
return KDF(protocol_id, epoch_key_label,
[payload_key],
[uint64(epoch_index)], Nk)
Sullivan Expires 6 May 2027 [Page 29]
Internet-Draft raAE November 2026
At epoch_length = 0 the shift is the identity, so each segment has
its own epoch key. At a large epoch_length every segment shares one
epoch key. Implementations MUST apply this derivation at every
epoch_length, including 0, and MUST NOT use payload_key directly as a
segment key. Epoch keys implement the parallel external rekeying
pattern of [RFC8645], adapted for random-access patterns.
4.5.3. Nonce Generation
Two nonce modes, random and derived, trade off AEAD flexibility,
storage cost, and trust in a cryptographically secure pseudorandom
number generator (CSPRNG). Derived mode needs misuse-resistant
authenticated encryption (MRAE) unless the profile's writer
discipline keeps every derived nonce unique. The chosen mode is part
of the parameter set and MUST be consistent across all segments of a
message.
Random: Derived:
nonce_base
Random(Nn) |
| XOR ((i<<1)|is_final)
v |
nonce(i) nonce(i)
Figure 3: The Two Nonce Modes
The two modes differ as follows:
Sullivan Expires 6 May 2027 [Page 30]
Internet-Draft raAE November 2026
+===============+===================+=============================+
| Property | Random nonce mode | Derived nonce mode |
+===============+===================+=============================+
| Per-segment | yes, in segment | no |
| nonce stored | metadata | |
+---------------+-------------------+-----------------------------+
| CSPRNG | yes | no |
| required | | |
+---------------+-------------------+-----------------------------+
| AEAD | any AEAD | MRAE, or any under a nonce- |
| requirement | | uniqueness discipline |
+---------------+-------------------+-----------------------------+
| Rewrite | fresh nonce each | nonce fixed by index, |
| | write | reused on rewrite |
+---------------+-------------------+-----------------------------+
| Per-segment | binds index and | empty when no A_i (index/ |
| AAD | finality | finality in nonce) |
+---------------+-------------------+-----------------------------+
| Minimum nonce | no added | at least 8 octets |
| size Nn | constraint | |
+---------------+-------------------+-----------------------------+
Table 5: Random and derived nonce modes
4.5.3.1. Random Nonce Mode
In random nonce mode (nonce_mode = "random"), each segment gets an
independent random nonce:
nonce(i) = Random(Nn)
Each segment's nonce is stored in per-segment metadata and MUST be
accessible to any reader that decrypts individual segments. This
mode requires a functioning CSPRNG. The nonce collision probability
across independently generated per-segment nonces follows the
standard birthday bound. See Section 5.8.
Two optional encryptor-side hedges harden this mode against different
threats. Hedged randomness (Appendix B) mixes a long-term key into
each draw and defends against a weak or predictable CSPRNG. The
hedge's inputs are the CSPRNG output and a per-call value, tag2. If
tag2 stays unique, duplicated CSPRNG state alone cannot repeat the
hedged output. Duplication that also rolls back tag2's source
replays the hedged output (Appendix B). Only the plaintext-bound
construction (Appendix A) defends against that, because it mixes in
the plaintext. It defends only segments whose plaintext or segment
AAD differ. Both hedges are implementation-local, leave the wire
format unchanged, and are not separate nonce modes.
Sullivan Expires 6 May 2027 [Page 31]
Internet-Draft raAE November 2026
4.5.3.2. Derived Nonce Mode
Derived nonce mode is intended for profiles that do not store a per-
segment nonce. Nonces are derived deterministically from the payload
schedule. Derived nonce mode is defined only for AEADs whose nonce
size Nn is at least 8 octets. The segment index occupies the high
bits of an 8-octet counter and the finality bit occupies the low bit,
so the per-segment AAD need not carry either one. The XOR is applied
to the last 8 octets of nonce_base, with the remaining octets
unchanged:
nonce(i) = nonce_base[0:Nn-8]
|| (nonce_base[Nn-8:Nn]
XOR uint64((i << 1) | is_final))
The encoded value (i << 1) | is_final MUST fit in the low 8 octets of
nonce_base, so the segment index i MUST be less than 2^63. This caps
an object at 2^63 segments, far beyond any reachable object. See
Section 5.8.4 for the resulting size limit.
A derived nonce is fixed by the segment's index and finality bit, so
re-encrypting a segment at the same index and finality repeats its
nonce. With unchanged plaintext and associated data, the repetition
reproduces the first ciphertext, because AEAD.Encrypt is a function
of its inputs.
With changed inputs the outcome depends on the AEAD. An MRAE AEAD
tolerates the repetition, degrading to equality leakage rather than
plaintext recovery, within the rewrite count its multi-user bound
allows (Section 5.8.7.4). A non-MRAE AEAD leaks plaintext. So with
a non-MRAE AEAD, derived nonce mode MUST be confined to a profile
whose discipline never re-encrypts a segment with a different
plaintext or associated data.
Two such disciplines matter here. A write-once profile rewrites
nothing and performs no length change, so no segment is re-encrypted
at all. An append-only profile re-encrypts one segment per append,
the re-mark that supersedes the old terminal segment, and that re-
mark carries the segment's existing plaintext and changes only the
finality bit, which changes the nonce (Section 4.9.3.1).
Under either discipline, each object MUST have its own fresh salt, so
its nonce base differs from every other object's. The encryptor MUST
NOT perform a second encryption at any (i, is_final) pair under that
salt, including after a crash (Section 6.3), and MUST NOT restart
encryption of an incomplete object under that salt, even at pairs it
has not used. Resending stored ciphertext and its metadata is not an
encryption; anything else needs a fresh salt. The restart rule keeps
Sullivan Expires 6 May 2027 [Page 32]
Internet-Draft raAE November 2026
each index to one finality form, which the terminal check of
Section 4.9.1.2 rests on. A writer interrupted after encrypting
index k as the final segment that restarted under the same salt with
a longer input would write a non-final segment at k beside the final
one, and a holder of the old bytes could present a truncation that
verifies.
Because the nonce binds index and finality, an immutable, write-once
profile in derived nonce mode coincides with STREAM (Section 1.1) at
the nonce-and-AEAD layer: a key-derived counter-plus-final-bit nonce
over a per-segment AEAD with no associated data.
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.
4.7.1. Interface and Requirements
A snapshot authenticator defines a per-segment input, one value per
segment. It produces and checks a keyed snapshot over the (index,
input) set and the count with two operations:
snapshot(): Produce the keyed snapshot over the current (index,
input) set and the count n_seg.
Sullivan Expires 6 May 2027 [Page 33]
Internet-Draft raAE November 2026
verify(snapshot): Recompute the keyed snapshot over the current
(index, input) set and the count, reading any witness SnapVerify
passes in place of the segments not presented (none for the whole-
object target), and accept only if it equals the stored snapshot
under a constant-time comparison.
The per-segment input is defined by the authenticator, and SEAL's
strict authenticators use the segment leaf (Section 4.7.2).
The AEAD tag binds the segment's index and finality bit against a
party without the key, through the segment AAD in random nonce mode
and through the nonce in derived nonce mode. A CEK holder can
produce a valid tag for altered content at any index. Setting the
ciphertext digest puts LH(ct_i) in the leaf, so changing the
ciphertext changes the keyed snapshot. The commitment is therefore
needed where the object is shared among CEK holders, and MAY be
omitted where the CEK has a single holder.
The ciphertext digest is necessary for that binding but not
sufficient. An ordering is linear when a holder of the snapshot key
can find a different segment set giving the same keyed snapshot below
the cost of a collision, and strict when finding one is a collision
problem, as the snapshot authenticators registry defines them
([I-D.sullivan-seal-concrete]). An authenticator with a strict
ordering defines a public snapshot and, at every count k at which the
object is open, an intermediate snapshot: its keyed or public
snapshot over segments 0..k-1 at count k, with segment k-1 written
non-final. Both are specified in Section 4.7.3. An authenticator
with a linear ordering carries no public snapshot, for the reason
given there, and defines no intermediate snapshot.
Every authenticator supports the whole-object target: verify the full
(index, input) set and the count. An authenticator MAY additionally
support a subset target: verify that a designated subset of (index,
input) pairs is included at their recorded positions without
presenting the other segments, reading a witness (Section 3.3) in
their place and checking it against the keyed snapshot. The keyed
snapshot stays a single target-independent value of length Na, with
no per-segment proof stored.
To change a stored object, an authenticator updates its keyed
snapshot. It MAY provide add(i, input), remove(i, input), and
set_length(n) to update the value in place from the changed segment
alone, or it MAY recompute the value over the changed (index, input)
set.
Sullivan Expires 6 May 2027 [Page 34]
Internet-Draft raAE November 2026
A snapshot update is not atomic against a second concurrent update,
so a consuming protocol MUST serialize concurrent updates to one
object. This document requires that a serialization exist and does
not say how to obtain it, which remains a storage-transaction concern
of the consuming protocol. Serialization is needed whether the
authenticator recomputes the value or updates it in place, and only
the failure differs. An authenticator that recomputes over the full
set binds whatever set it read, which is neither the state before the
interleaved update nor the state after. One that updates in place
loses an update, when two read-modify-write cycles on the stored
value interleave and the later write never observed the earlier
delta. This is the concurrent case, distinct from the crash case of
Section 6.9, where one update is interrupted rather than two
interleaved.
The scheme's RewriteSeg and SnapVerify (Section 3.3) are realized
from these operations. For the whole-object target, SnapVerify takes
no witness and checks a stored snapshot as follows:
1. Let n_seg be the number of present segments.
2. Verify that the present segments occupy exactly the indices
0..n_seg-1, each once.
3. Call verify(snapshot) over the present (index, input) set and the
count n_seg.
Where the authenticator's input carries the finality bit, as the
strict authenticators' leaf does, SnapVerify binds the declared
finality: it forms each input with is_final(i) for a snapshot
declared complete, and with 0 at every index for one declared open.
The terminal bit b of each presented position MUST agree with that
declaration: b = 1 only at index n_seg-1 of a snapshot declared
complete. SnapVerify rejects a set whose bits disagree. SnapVerify
does not decrypt, so it does not establish that a segment opens under
that finality. Segment decryption checks is_final through the
segment AEAD, and Section 4.9.1.2 rejects a present set whose
highest-indexed segment does not carry is_final = 1.
A duplicate or missing index is caught only by step 2, because an
authenticator's verify MAY accept a malformed index multiset. An
implementation MUST NOT skip the index-set check.
A conforming authenticator's snapshot() MUST bind both the (index,
input) set and the count n_seg, so a verifier detects any added,
dropped, reordered, or re-marked segment and any changed input, and
the keyed snapshot MUST be unforgeable by a party without the
authenticator's key, under that authenticator's security assumption.
Sullivan Expires 6 May 2027 [Page 35]
Internet-Draft raAE November 2026
The keyed snapshot is a fixed-length value of Na octets, with Na = 0
meaning no value.
In a complete object, a segment's finality is a function of its index
and the count:
is_final(i) = 1 if i = n_seg - 1, else 0
It is carried by that segment's input, and every segment of an
intermediate snapshot carries 0. Because finality follows the count,
changing n_seg moves the terminal position, so rewrite, extend, and
truncate are one update over the segments whose input changes, each
starting from a complete object:
1. Under the current count, remove each changed segment's current
input (remove(i, input)). The current n_seg fixes which segment
is terminal, so each removal carries that segment's current
finality.
2. Set the length to the new count (set_length(n)).
3. Under the new count, re-encrypt each surviving changed segment
under its new finality and add its new input (add(i, input)).
New segments are added here. Discarded segments are not added
back.
4. Call snapshot(), which recomputes the keyed snapshot over the new
count and segment set.
Each operation is an instance of that shape over different segments:
Sullivan Expires 6 May 2027 [Page 36]
Internet-Draft raAE November 2026
+===========+===========+==============+===========+==============+
| Operation | Count | Inputs | Inputs | Terminal re- |
| | | removed | added | mark |
+===========+===========+==============+===========+==============+
| Rewrite | unchanged | the changed | the | none |
| | | segment | changed | |
| | | | segment | |
+-----------+-----------+--------------+-----------+--------------+
| Extend by | n_seg to | old terminal | old | old final, 1 |
| k | n_seg+k | | terminal | to 0 (none |
| | | | and k new | if empty) |
+-----------+-----------+--------------+-----------+--------------+
| Truncate | n_seg to | segments m | the re- | m-1, 0 to 1 |
| to m | m | to n_seg-1, | marked | (none if |
| | | and the old | m-1 (none | m=0) |
| | | input at m-1 | if m=0) | |
+-----------+-----------+--------------+-----------+--------------+
Table 6: Rewrite, extend, and truncate
This sequence uses remove, the mutable-authenticator path. One that
omits remove instead resets and re-adds the surviving segments to
rebuild the value.
SnapVerify detects truncation in every case but one: the truncated
object is presented with the snapshot of an earlier complete version
at that shorter count, and presenting it is rollback (Section 6.7).
A snapshot at that count taken while the object was open is not that
case, since such a snapshot fixes is_final = 0 at its last index, and
so does not verify the shorter object declared complete.
4.7.2. Segment Leaf
The per-segment input, leaf(i), is formed from the segment's metadata
entry and its context. SEAL's strict authenticators use:
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
LH(ct_i) is present when the ciphertext digest is set. In random
nonce mode nonce_field(i) is the stored nonce(i). In derived nonce
mode it is the counter from which nonce(i) is derived
(Section 4.5.3.2), so nonce_base is never published, and once the
commitment fixes the CEK and payload_info the counter fixes the
nonce. The field segment_aad is the segment AAD the segment was
Sullivan Expires 6 May 2027 [Page 37]
Internet-Draft raAE November 2026
encrypted under (Section 4.4.2), so the leaf carries A_i in both
nonce modes, and a verifier needs each segment's A_i, empty or
supplied, to form its leaf. The bit is_final is the finality bit the
segment was encrypted under: is_final(i) above for a complete object,
and 0 at every index of an intermediate snapshot. The stored
metadata entry holds the leaf's leading fields, the optional
ciphertext digest, the tag, and the optional stored nonce, in the
same order ([I-D.sullivan-seal-concrete]). The masked multiset hash
uses tag_i alone as leaf(i).
4.7.3. Intermediate and Public Snapshots
A strict authenticator produces two snapshots over the same leaves
(Table 7), and either can be produced while the object is open.
+========+==============================+==============================+
| |Keyed snapshot |Public snapshot |
+========+==============================+==============================+
|Computed|under snap_key |with an empty ikm in place of |
| |([I-D.sullivan-seal-concrete])|snap_key |
| | |([I-D.sullivan-seal-concrete])|
+--------+------------------------------+------------------------------+
|Who can |holders of the CEK, from which|anyone who holds the segments |
|compute |snap_key derives |and their A_i |
|it | | |
+--------+------------------------------+------------------------------+
|Who can |holders of the CEK |anyone, but it is authentic |
|verify | |only under a signature or |
|it | |trusted reference |
+--------+------------------------------+------------------------------+
|Protects|a party without the CEK |anyone but the signer doing |
|against |altering, dropping, |the same, checked by any |
| |reordering, or truncating |verifier; the origin it gives |
| |segments; with the ciphertext |is the signer's |
| |digest, a CEK holder making a | |
| |fixed, externally | |
| |authenticated snapshot verify | |
| |a different segment set | |
+--------+------------------------------+------------------------------+
|Does not|CEK holders producing new |a signer signing several |
|protect |keyed snapshots for each |statements; rollback; |
|against |other; rollback; staleness |staleness; it proves neither |
| | |that a segment decrypts nor |
| | |which key derived the |
| | |commitment |
+--------+------------------------------+------------------------------+
Table 7: Keyed and public snapshots
Sullivan Expires 6 May 2027 [Page 38]
Internet-Draft raAE November 2026
The two snapshots overlap with the commitment, which binds the CEK,
payload_info, and G. A key holder checks the commitment before
decrypting, so a wrong key, parameter set, or G fails there
(Section 4.6). snap_key does not bind G, so SEAL's strict
authenticators include the commitment in both snapshots, which ties
each to that object's context. A verifier without the key cannot
check how the commitment was derived: for it the commitment is a
bound identifier, and payload_info is in the public snapshot so that
the parameters are authenticated. The ciphertext digest, LH(ct_i) in
the leaf, is what makes either snapshot bind ciphertext rather than
tags alone.
Under a strict authenticator a writer MAY produce the snapshot at a
count n at which the object is open, segment n-1 written with
is_final = 0 and the object not ended. It binds the (index, input)
set 0..n-1 and the count n as any snapshot does, so SnapVerify over
those segments with the snapshot declared open accepts, but it is not
a snapshot of a complete object, and the authenticator's
specification states what a reader of the prefix learns from it
([I-D.sullivan-seal-concrete]).
A public snapshot is an unkeyed function of payload_info, the
commitment, the count, and the ordered (index, input) set. A linear
ordering cannot carry one, because without a key every party is in
the snap_key holder's position, and a linear ordering lets that party
find a different segment set with the same value below the cost of a
collision. An authenticated public snapshot binds payload_info, the
commitment, the count, and each index's input in order, under the
collision resistance of the functions that compute it, and it is not
a hiding commitment: over inputs that are withheld it gives an
offline equality test for guesses at them.
A profile or consuming protocol that relies on a public snapshot MUST
set the ciphertext digest: without it the public snapshot binds tags
but not ciphertext, so anyone can replace a segment's ciphertext and
a verifier without the key still accepts the signed public snapshot.
A verifier MUST accept a public snapshot only under a signature, or
an authenticated reference from a party it trusts, over a statement
that names the object or stream, the count, whether the object was
open at that count or complete, and the value itself, and that binds
G where the verifier interprets G. From an accepted public snapshot
it learns that the leaves it recomputes from the segments it holds
and their A_i are those the signer authenticated, at those positions,
ciphertext included.
Sullivan Expires 6 May 2027 [Page 39]
Internet-Draft raAE November 2026
The two snapshots are computed separately and can cover different
segment sets, so a CEK holder can authenticate one segment set to key
holders and sign another for verifiers without the key. Where the
signer signed a public snapshot, a key holder that claims the
signer's origin for its segments MUST also verify the signature and
recompute the public snapshot over them, which establishes agreement
with the signed statement, not that the signer signed no other. A
public snapshot does not replace SnapVerify for a key holder, and
freshness, rollback, withholding, equivocation, and completeness are
out of its scope, as for the keyed snapshot (Section 6.7).
4.7.4. None
This selection configures no snapshot authenticator: no keyed
snapshot is produced (Na = 0), snapshot() and verify() are no-ops,
and an object rests on per-segment authentication alone. Such a
profile MUST NOT produce the empty object (n_seg = 0). With no keyed
snapshot to bind the zero count, a truncation that removed every
segment would be indistinguishable from a legitimate empty object, so
a valid object always has at least one segment.
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.
Sullivan Expires 6 May 2027 [Page 40]
Internet-Draft raAE November 2026
+================+================+==========================+
| Subroutine | Realizes | Composed by |
+================+================+==========================+
| EncryptSegment | the encryption | Section 4.9.1.1 and |
| | core of EncSeg | Section 4.9.3, which add |
| | | the snapshot bookkeeping |
+----------------+----------------+--------------------------+
| DecryptSegment | DecSeg | Section 4.9.1.2 |
+----------------+----------------+--------------------------+
| RewriteSegment | the encryption | Section 4.9.2.1 and |
| | core of | Section 4.9.3, which add |
| | RewriteSeg | the snapshot bookkeeping |
+----------------+----------------+--------------------------+
Table 8: Segment subroutines and the primitive operations
they realize
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).
4.8.1. EncryptSegment
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)
Sullivan Expires 6 May 2027 [Page 41]
Internet-Draft raAE November 2026
AEAD.Encrypt and AEAD.Decrypt are the interfaces of [RFC5116]
Sections 2.1 and 2.2. For an AEAD whose ciphertext places the tag in
its final Nt octets, ct_i is the first len(P_i) octets and C_i =
ct_i || tag_i.
The caller supplies the segment's leaf to the snapshot authenticator
(Section 4.7.2). EncryptSegment itself does no snapshot work.
4.8.2. DecryptSegment
DecryptSegment returns the segment plaintext, or a decryption error:
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.8.3. RewriteSegment
RewriteSegment assumes the caller has already verified the commitment
or otherwise confirmed it holds the correct CEK. A rewrite under the
wrong key produces unreadable ciphertext and corrupts the snapshot
authenticator's state. The error is detectable only on a subsequent
read.
RewriteSegment(i, is_final, A_i, new_P_i) is defined as
EncryptSegment(i, is_final, A_i, new_P_i): a rewrite is a fresh
encryption of the new plaintext new_P_i. The output record
new_stored_i replaces the stored record for segment i.
RewriteSegment produces the replacement record new_stored_i only.
The caller updates the snapshot authenticator with the old and new
leaves, calling remove(i, leaf(i)) then add(i, new_leaf(i))
(Section 4.9.2.1).
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
Sullivan Expires 6 May 2027 [Page 42]
Internet-Draft raAE November 2026
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.
4.9.1. Read-Only Operations
Encryption and decryption are available in every SEAL profile. They
write a message once and read individual segments. Neither rewrites
a stored segment. When the profile configures no snapshot
authenticator, the snapshot steps below are omitted, and a reader
relies on per-segment authentication alone.
4.9.1.1. Encryption
Encryption runs in two phases. The first derives the per-message
schedule and writes the commitment. The second encrypts each segment
independently, feeds its input to the snapshot authenticator, and
then calls snapshot() to bind the whole (index, input) set and the
count. Because the segments are independent, the second phase may
encrypt them in any order or in parallel. The snapshot calls mutate
one value under a single writer, so encryption is never the
concurrent case that Section 4.7.1 requires a protocol to order.
CEK, salt
|
v
payload schedule
|
+----+----------+----------+
v v v
commitment payload_key snap_key
|
v
EncryptSegment(i, P_i) using payload_key (one per segment)
|
v
ct_i, tag_i
Figure 4: Key Schedule and Segment Encryption
An application that writes a new message MUST generate a fresh,
uniformly random salt. Given a CEK, that salt, a parameter set, G,
and a plaintext P split into segments P_0 through P_{n_seg-1}:
Sullivan Expires 6 May 2027 [Page 43]
Internet-Draft raAE November 2026
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
Under an authenticator that recomputes, the set_length and add calls
collapse into one snapshot() over the (index, input) set
(Section 4.7.1).
A zero-length plaintext produces a single segment of length 0 with
is_final = 1. A writer encrypts each segment once its content is
complete and marks the last one final. A writer that does not know
where its input ends holds one complete segment back until more
content or the end of input arrives, so it knows whether that segment
is the last when it encrypts it. Re-marking the last segment
afterwards would be a re-encryption, which a write-once profile
forbids and an append-only profile admits only inside an append
(Section 4.9.3.1). Under a strict authenticator a writer may also
produce the keyed snapshot at any count while the object is open
(Section 4.7.3).
4.9.1.2. Decryption of Segment i
Opening a segment is a local operation: check the commitment to
reject a wrong key early, then AEAD-decrypt the one segment. This
yields per-segment authenticity over the ciphertext core, the segment
index, and the finality bit. Under a snapshot authenticator, whole-
set authenticity is a separate and stronger check that requires the
full present segment set. It detects any altered segment set,
including same-index rollback to an older sibling (Section 4.7.1). A
reader holding only one segment gets per-segment authenticity but
MUST NOT claim snapshot integrity until it runs SnapVerify
(Section 4.7). A profile with no snapshot authenticator defines no
snapshot, so per-segment authenticity is the whole integrity
guarantee.
Sullivan Expires 6 May 2027 [Page 44]
Internet-Draft raAE November 2026
Given the CEK, salt, parameter set, G, segment index i, finality
status, and the stored ciphertext segment for index i:
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
Here SnapVerify is the whole-object form of Section 3.3: S is the
decryption state derived above, segments is the full present set,
each with its A_i (Section 4.7.1), the snapshot is declared complete,
and no witness is passed.
Whole-object SnapVerify needs the leaf of every segment
(Section 4.7.2). A reader that streams segments in order can gate
their release on it only by buffering those leaves first, or by using
a layout that holds their leading fields in a header, completed with
each segment's A_i. Two cases need less. Where the authenticator
supports a subset target, a reader verifies the segments it holds
against the snapshot, reading a witness (Section 3.3) in place of the
others. Where the authenticator is strict and the writer produces an
intermediate snapshot at count n (Section 4.7.3), a reader that holds
segments 0..n-1 verifies them, declared open, against the value for
count n. It learns that they are the segments a snap_key holder
recorded at those positions, and nothing about later indices or
completeness (Section 4.7.3). Releasing plaintext on per-segment
authenticity alone forgoes snapshot freshness for that segment
(Section 6.7).
A streaming reader cannot rule out truncation before the end of the
stream. Plaintext delivered before the highest-indexed segment
verifies under is_final = 1, and before SnapVerify passes where a
snapshot authenticator is configured, MUST be treated as unverified
with respect to completeness.
A decryptor MUST reject a truncated object: one whose highest-indexed
present segment carries is_final = 0 is incomplete, and the decryptor
MUST fail rather than return the partial plaintext as the complete
message. A streaming reader that delivered plaintext as unverified,
as the preceding paragraph permits, reports that failure when the
stream ends.
Sullivan Expires 6 May 2027 [Page 45]
Internet-Draft raAE November 2026
The decryptor derives the finality each segment must carry from the
segment count n_seg the application supplies (Section 4.8), so the
last surviving segment of a truncated object, written non-final,
fails verification as the final segment. The finality bit is bound
per segment and unforgeable without the CEK, through the nonce or the
segment AAD per the nonce mode (Section 4.4.2).
Under a write-once profile no segment ever carried an earlier
terminal form, so an adversary cannot present a valid is_final = 1
segment at a truncated boundary: it cannot re-mark a non-final
segment, and this check detects every dropped trailing segment. An
append re-marks the old terminal segment (Section 4.9.3), so under a
profile that appends, a retained segment may have carried is_final =
1 under an earlier nonce. An adversary can replay that retained
terminal ciphertext at the shorter count, which this check alone
accepts. SnapVerify over the complete segment set then rejects the
replay, except where the shorter object is an earlier complete
version presented with its own snapshot, which is rollback
(Section 4.7.1). The mutable profile requires a snapshot
authenticator, so SnapVerify always runs there (Section 4.9.2).
Authorized truncation by the CEK holder to a nonempty prefix re-marks
the new last segment under is_final = 1 (Section 4.9.3), so a
legitimately truncated object still ends with is_final = 1 and
verifies. This check needs no snapshot authenticator.
Truncation to an empty object is covered too. Without a snapshot
authenticator a valid object has at least one segment, so a decryptor
MUST reject one with none. With a snapshot authenticator the
snapshot binds the count, making the empty object (n_seg = 0) a
distinct authenticated state (Section 4.7.1).
On a commitment mismatch the implementation MUST NOT proceed with
decryption, SHOULD zeroize derived key material, and MUST return an
error. The SnapVerify gate in the procedure above runs whenever a
snapshot authenticator is configured and the full present set is
available, for example a full read or an integrity audit.
Decryption can fail in up to three distinguishable ways:
Sullivan Expires 6 May 2027 [Page 46]
Internet-Draft raAE November 2026
+===========================+===============================+
| Failure | Cause |
+===========================+===============================+
| Commitment mismatch | wrong key or parameters |
+---------------------------+-------------------------------+
| AEAD verification failure | corrupted or tampered segment |
+---------------------------+-------------------------------+
| Snapshot mismatch | segment set or count modified |
| | (snapshot authenticator only) |
+---------------------------+-------------------------------+
Table 9: Decryption failure conditions
Implementations SHOULD report these as distinct error conditions for
local diagnosis, but SHOULD return a single opaque error to untrusted
callers to avoid leaking an oracle (for example, distinguishing
"wrong key" from "tampered segment" over a network).
4.9.2. Rewritable Operations
Rewriting is available only in a mutable profile, which requires a
snapshot authenticator. Length change is a separate operation
(Section 4.9.3), available in both directions in a mutable profile
and in the append direction alone in an append-only profile
(Section 4.9.3.1). The procedure below is written against the in-
place update path (add, remove, set_length; Section 4.7.1). Under an
authenticator that recomputes instead, the remove, add, and
set_length calls in this procedure collapse into a single snapshot()
over the updated (index, input) set, and the operations are otherwise
identical. A caller that cannot recover a re-encrypted segment's
plaintext cannot perform it.
4.9.2.1. Rewriting Segment i
A rewrite touches exactly one segment's ciphertext, and no other
segment is decrypted. Beyond that segment, it reads only the
verified snapshot and the witness its authenticator takes for the
update, checked against that snapshot (Section 3.3).
Rewrite takes the segment index i and the new plaintext new_P_i, at
most segment_max octets, and keeps the segment's finality bit. Only
a length change moves that bit (Section 4.9.3). The procedure is:
Sullivan Expires 6 May 2027 [Page 47]
Internet-Draft raAE November 2026
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
In derived nonce mode the nonce for segment i is deterministic, so a
rewrite reuses the same nonce under a key whose derivation context is
identical. A mutable profile that selects derived nonce mode
requires an MRAE AEAD.
A rewrite is an update under the writer rule of Section 3.3.1, so the
writer checks the witness and the removed input before the rewrite,
as that rule requires. Otherwise a storage adversary can swap stored
data for an older copy and have the writer launder it into a snapshot
that verifies going forward (Section 6.7). Full validation is a
separate operation performed with access to all tags, for example on
a full read or an integrity audit.
4.9.3. Changing Message Length
An application that holds the CEK MAY change a stored message's
length in either direction: appending new segments, or truncating to
a prefix. An append re-encrypts one retained segment, the old
terminal one, with its existing plaintext to clear its finality bit,
and none when appending to the empty object. A truncation re-
encrypts one retained segment, the new terminal one, with its
existing plaintext to set its finality bit, and none when truncating
to the empty object; it drops the segments past the prefix. Every
other changed segment is removed or added by tag, and the snapshot is
updated over the new count (Table 6). Both directions are updates
under the writer rule of Section 3.3, which the writer meets before
either changes the object.
Under a mutable profile, a writer that wants the start of the new
content in the old terminal segment's spare capacity rewrites that
segment first (Section 4.9.2.1) and then appends the rest.
Both directions reuse the existing salt: an application extending an
existing message MUST reuse the salt from the object it extends. A
fresh salt would change every payload schedule output and force re-
encryption of the retained segments.
Sullivan Expires 6 May 2027 [Page 48]
Internet-Draft raAE November 2026
Append takes P_new, the list of new segment plaintexts, each at most
segment_max octets, and requires k = len(P_new) >= 1. Content that
adds no segment is handled by a rewrite of the terminal segment under
a mutable profile (Section 4.9.2.1).
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()
Figure 5: Append
Truncate takes m < n_seg, the number of segments that survive. For m
> 0 it drops segments m and above and re-marks segment m-1 as final,
the reverse of the append re-mark, so the truncated object has m
segments. Truncate(0) drops every segment and yields the empty
object. For m = 0 it decrypts nothing, so, like RewriteSegment, it
assumes the caller has already verified the commitment or otherwise
confirmed it holds the correct CEK.
Sullivan Expires 6 May 2027 [Page 49]
Internet-Draft raAE November 2026
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()
Figure 6: Truncate
Where an authenticator's input is the stored tag alone, each add and
remove takes that tag, which already encodes the segment's is_final
bit, so an implementation never tracks finality separately. A strict
authenticator's leaf carries the bit explicitly, so each remove forms
the leaf with the finality the segment was encrypted under and each
add with the new one.
A botched in-place update corrupts the snapshot authenticator's state
silently, surfacing only at a later SnapVerify. An implementation
MAY run SnapVerify over the new segment set immediately after a
length change to catch this. An authenticator that recomputes
rebuilds the snapshot from the per-segment leaves, formed from the
stored entries, on every update, so it has no analogous silent-
corruption failure mode.
Both operations count against the same AEAD usage budgets as initial
encryption (Section 5.8). An append re-encrypts the old terminal
segment, except from the empty object, and a truncate re-encrypts the
Sullivan Expires 6 May 2027 [Page 50]
Internet-Draft raAE November 2026
new terminal segment, except to the empty object (m = 0). In derived
nonce mode the nonce of the segment each one encrypts is fixed by its
index and finality bit. Each re-mark flips the finality bit, so its
nonce differs from the segment's previous one, but a truncate's re-
mark at (m-1, 1) can land on a pair the object has used, as after an
earlier truncation to m, and repeated length changes in both
directions can make any pair recur. Only an MRAE AEAD tolerates the
resulting nonce reuse (Section 4.5). An append-only profile admits
no truncation and appends only from the current count (Section 3.3),
so no pair recurs and the AEAD need not be MRAE (Section 4.9.3.1).
Applications that do not need length changes MAY forbid them. The
salt-reuse requirement applies only when a length change is
performed. An application that re-encrypts the entire content can
generate a fresh salt and is not bound by the constraints in this
section.
4.9.3.1. Appending Under an Append-Only Profile
An append-only profile admits the append direction of this section
(Figure 5) and forbids truncation.
An encryptor under an append-only profile MUST NOT rewrite a segment
with a different plaintext or associated data, and MUST NOT truncate
(Figure 6).
The first rule is what lets the profile pair a derived nonce with any
AEAD, including a non-MRAE one. At a fixed index and finality the
key and the nonce are already fixed by the payload schedule, so the
plaintext and the associated data are the only inputs that can
differ, and the rule forbids exactly those. No nonce ever carries
two different plaintexts, which is the condition Section 4.5.3.2 sets
for a non-MRAE AEAD.
The segment an append re-encrypts keeps its existing plaintext
(Section 4.9.3), so the re-encryption satisfies the first rule: it
changes only the finality bit, not the plaintext or the associated
data (Section 4.5.3.2).
The second rule makes the profile append-only rather than non-
rewriting. It forbids the truncate direction, so a stored object can
only grow. Provided each append starts from the current count
(Section 3.3), an index the object has spent is never freed for a
later append to fill with different content. After an interrupted
append, the writer follows the crash rule of Section 4.5.3.2.
Sullivan Expires 6 May 2027 [Page 51]
Internet-Draft raAE November 2026
An append re-encrypts one retained segment, so each segment is
encrypted at most twice, and an epoch key covers at most
2^(epoch_length + 1) segment encryptions (Section 5.8.4).
An append keeps the re-encrypted segment's length (Section 4.9.3),
and this profile cannot rewrite that segment first. So an append to
an object whose terminal segment is short leaves a short interior
segment, which a layout with uniformly sized interior segments cannot
represent. A consuming protocol using this profile supplies a
serialization that conveys each segment's ciphertext length
(Section 4.4.2).
5. Security Analysis
The formal proofs are not reproduced here. The ra-ROR and ra-CMT
notions are taken unchanged from [FLRR25], which proved them for a
construction that instantiates the same component contracts other
than the snapshot authenticator (Section 5.4) and that never re-
encrypts a position (Section 3.3). Snapshot integrity is the one
notion this document defines. The configured authenticator argues
its bound (Section 5.7), and a combined proof is deferred to
[SEALPROOFS]. The limits of Section 5.8 are operational deployment
bounds, not proof obligations.
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.1.1. ra-ROR
ra-ROR (random-access real-or-random) is the joint confidentiality
and authenticity notion for raAE in a multi-user, nonce-respecting
setting. An adversary with adaptive encryption and decryption access
across many key instances, sessions, and arbitrary positions cannot
distinguish real ciphertexts and headers from random, and cannot make
an out-of-context ciphertext segment decrypt. The game is defined in
[FLRR25].
Sullivan Expires 6 May 2027 [Page 52]
Internet-Draft raAE November 2026
The encryption core of the extension operations is ordinary EncSeg.
A RewriteSeg produces its replacement ciphertext as a repeated EncSeg
at the same index. Appending is EncSeg at the positions past the
current end plus one RewriteSeg of the old final segment, and
truncating to a nonempty prefix is one RewriteSeg of the new final
segment. Under a mutable profile the positions either one writes
need not be fresh, since a truncate's re-mark can encrypt at a pair
the object has used and repeated length changes in both directions
can make any (index, finality bit) pair recur (Section 4.9.3).
In random nonce mode these draw fresh nonces, which repeat only by
collision. For an append whose positions are new, the ra-ROR bound
charges that collision, in Adv_muROR$ for directly drawn nonces and
in Adv_nonce_coll under a nonce hedge (Appendix C.2). A rewrite in
place still re-encrypts a position, and so can a length change under
a mutable profile. Either falls outside the ra-ROR bound in any
nonce mode, since that bound assumes a position-respecting adversary
(Appendix C.2). The ra-ROR bounds do not carry over in any nonce
mode: Theorems 4 and 6 of [FLRR25] assume an adversary that never
queries EncSeg twice at the same key instance, session, and position.
Re-encrypting a position falls outside them and needs an extended
analysis, deferred to [SEALPROOFS]. In derived nonce mode the
analysis turns on whether the profile permits a rewrite in place.
Where it does, a rewrite repeats the position's derived nonce with
new content. In derived nonce mode EncSeg at a position is
deterministic, so one repeated query separates the real and random
ra-ROR games. That is a deliberate nonce-repeating query, and the
underlying MRAE AEAD handles it under the equality-leakage relaxation
documented for derived nonce mode (Appendix C.5), not the unmodified
nonce-respecting game.
Where it does not, no query repeats a position with new content. The
write-once profile re-encrypts nothing. The append-only profile re-
encrypts only at the append's RewriteSeg, which flips the finality
bit and so writes a position the initial write did not use. A writer
recovering from a crash may resend saved ciphertext without another
EncSeg call. Both profiles use each position at most once in
encryption (Section 4.5.3.2, Section 4.9.3.1), so both meet the
[FLRR25] hypothesis that no position is encrypted twice, each derived
nonce is used once, and neither needs an MRAE AEAD.
The keyed snapshot these operations maintain is outside the [FLRR25]
syntax and is governed by snapshot integrity (Section 5.1.4), not by
ra-ROR.
Sullivan Expires 6 May 2027 [Page 53]
Internet-Draft raAE November 2026
5.1.2. ra-CMT
ra-CMT (random-access context commitment) is the segment-level
commitment notion: no single ciphertext segment decrypts successfully
under two different decryption contexts (key, nonce, global
associated data, and per-segment associated data). In this position-
matched notion the two contexts share a position. Because the scheme
is random access, committing one segment's context commits the full
ciphertext's context.
The external commitment in this construction establishes the
position-matched claim only for fixed per-segment associated data
A_i: both openings use the same A_i at the shared position. The full
notion also permits differing A_i, which the external commitment does
not bind. That case requires a separate AEAD AAD-commitment
assumption and is outside the claim established here (Section 5.6).
ra-CMT is distinct from the per-AEAD notions CMT-1 and CMT-4 of
[RFC9771]: a scheme can achieve ra-CMT through an external commitment
mechanism even when its underlying AEAD commits to nothing. The
Invisible Salamanders attacks ([DGRW18]) show what a non-committing
AEAD permits, and [ADG22] frames it as a key-commitment failure with
fixes.
5.1.3. ra-CMT-p
ra-CMT-p is the position-choosing variant of ra-CMT: the two
decryption contexts need not share a position, so the adversary binds
a segment's content to a position of its choice.
Under honest keys a construction inherits ra-CMT-p from the
underlying AEAD's commitment. Against a holder of the CEK it does
not follow from per-segment AEAD alone, and SEAL's snapshot
authenticators give at most the weaker per-index binding of
Section 5.6, under the conditions stated there (Section 5.3,
Appendix C.4).
5.1.4. Snapshot Authentication
Per-segment AEAD authenticates a segment at its position, but it does
not authenticate the current object snapshot: which set of segments
belongs to the current stored object state. An adversary with write
access to stored segments can silently substitute an old valid same-
index segment or delete a segment, and per-segment AEAD verification
at each presented segment still passes. (A segment moved to a
different index fails its AEAD check through the index binding of
Section 4.4.2.)
Sullivan Expires 6 May 2027 [Page 54]
Internet-Draft raAE November 2026
Snapshot integrity is the notion that covers that set. Its interface
is in Section 4.7.1 and its bound in Section 5.7. SEAL provides it
under a snapshot authenticator and omits it otherwise (Section 5.1).
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
Sullivan Expires 6 May 2027 [Page 55]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 56]
Internet-Draft raAE November 2026
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
Sullivan Expires 6 May 2027 [Page 57]
Internet-Draft raAE November 2026
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
Sullivan Expires 6 May 2027 [Page 58]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 59]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 60]
Internet-Draft raAE November 2026
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
Sullivan Expires 6 May 2027 [Page 61]
Internet-Draft raAE November 2026
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
+=================+=================+==============+===============+
| Guarantee | Established by | Scope | Provided by |
+=================+=================+==============+===============+
| Segment | AEAD decrypt, | segment | this |
| confidentiality | per segment | | construction |
| and integrity, | | | |
| index and | | | |
| finality bound | | | |
+-----------------+-----------------+--------------+---------------+
| Segment-set | SnapVerify over | whole object | this |
| integrity: per- | the keyed | | construction |
| segment input, | snapshot | | |
| position, count | | | |
+-----------------+-----------------+--------------+---------------+
| Segment-set | SnapVerify with | designated | this |
| integrity for a | a witness | subset | construction, |
| designated | | | under an |
| subset: per- | | | authenticator |
| segment input, | | | that supports |
| position | | | the subset |
| | | | target |
+-----------------+-----------------+--------------+---------------+
| Segment-set | SnapVerify over | prefix | this |
| integrity for a | a snapshot the | 0..n-1 | construction, |
| prefix (prefix | writer produced | | under a |
| verification): | at that count | | strict |
| per-segment | | | authenticator |
| input, | | | |
| position, count | | | |
+-----------------+-----------------+--------------+---------------+
| Sender | signature over | whole | consuming |
| attribution, | the keyed | object, or | protocol, not |
| third-party | snapshot, or | prefix | provided |
| verifiability | over a public | 0..n-1 under | |
| | snapshot for a | an | |
| | verifier | intermediate | |
| | without the CEK | snapshot | |
+-----------------+-----------------+--------------+---------------+
| Freshness, | external | whole object | consuming |
| whole-object | version or | | protocol, not |
| rollback | freshness state | | provided |
| protection | | | |
Sullivan Expires 6 May 2027 [Page 62]
Internet-Draft raAE November 2026
+-----------------+-----------------+--------------+---------------+
Table 10: What each layer guarantees
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.
Sullivan Expires 6 May 2027 [Page 63]
Internet-Draft raAE November 2026
5.8.1. Accounting Model
One segment encryption consumes one write from a segment-encryption
key's budget. Initial writes and rewrites are both segment
encryptions. The write budget belongs to the epoch key, not the CEK.
A derived-nonce MRAE AEAD's data-volume term is the exception: absent
an allocation it is counted in accounted blocks across all of the
object's epoch keys (Section 5.8.7.4).
epoch-key budget: the segment encryptions allowed under one epoch
key.
write (initial write): the first encryption of a segment.
rewrite: a later encryption of the same segment.
epoch_length (r): the base-2 log of the number of segments that
share one epoch key.
n_blk: the most AAD-plus-plaintext blocks one segment encryption
processes, for a block-cipher AEAD: about segment_max / Nb when
the segment AAD is short.
advantage target: the bound a budget is solved against. The
numerical confidentiality figures in this section use 2^-32 for
one of these scopes: one indicated term under one key; the
derived-nonce data-volume term over one object; one term across
the aggregate scope; or the stated isolated workload. The
exception is AES-GCM with random nonces, whose own specification
caps it at 2^32 encryptions per key, here the epoch key, rewrites
included ([NIST-SP-800-38D] Section 8.3). A budget quoted from an
AEAD's own analysis holds at the target that analysis states
(Section 5.8.2).
5.8.2. Aggregate Security Accounting
The scope of an aggregate target includes all objects and epoch keys
available to the adversary. Only the consuming protocol can see that
scope, so it allocates the target among the terms of Appendix C.2,
and the sum of these allocations stays within the target. For a
workload that re-encrypts a position, which the ra-ROR bound does not
cover, these terms are AEAD-level operating limits, not the ra-ROR
bound.
Sullivan Expires 6 May 2027 [Page 64]
Internet-Draft raAE November 2026
Let K count epoch keys in this scope, q_j their encryption counts,
s_j their processed block counts, and v_j their forgery-attempt
counts. A union bound gives the random-nonce term, and summing the
single-key block-size bounds, here AES-GCM's (Section 5.8.7.2), gives
a conservative contribution in the independent key hybrid:
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)
The applicable AEAD analysis supplies any further terms. Key
collisions and KDF distinguishing costs are charged separately as in
Appendix C.2. For equal q_j, allocating epsilon_nonce to nonce
collisions gives:
q_j <= sqrt(epsilon_nonce * 2^(8*Nn + 1) / K)
A published multi-user bound can improve on this conservative
accounting when applied with its full workload parameters and
hypotheses. Derived-nonce MRAE accounting is given in
Section 5.8.7.4.
5.8.3. Limit Classes
Five phenomena bound how much may be encrypted.
Sullivan Expires 6 May 2027 [Page 65]
Internet-Draft raAE November 2026
+===============+===============+===============+=================+
| Limit class | Applies to | Depends on | Failure mode |
+===============+===============+===============+=================+
| Random-nonce | random nonce | nonce size, | confidentiality |
| collision | modes | or a lower | and integrity |
| | | specification | |
| | | cap | |
+---------------+---------------+---------------+-----------------+
| Forgery bound | all AEADs | MAC strength, | integrity |
| | | segment size | |
+---------------+---------------+---------------+-----------------+
| Block-size | block-cipher | total blocks | confidentiality |
| birthday | AEADs | | |
+---------------+---------------+---------------+-----------------+
| Derived-nonce | derived-nonce | total blocks, | confidentiality |
| MRAE workload | MRAE | and blocks | and integrity |
| | | per (key, | |
| | | nonce) pair | |
+---------------+---------------+---------------+-----------------+
| Epoch-key | 128-bit-key | key size | confidentiality |
| collision | AEADs | | |
+---------------+---------------+---------------+-----------------+
Table 11: Usage-limit classes
5.8.4. Maximum Object Size
A write-once object is bounded by each epoch key's AEAD write budget,
the aggregate security budget (Section 5.8.2), and the 2^63 segment
index ceiling. The same limits bound an append-only object, at the
write counts given at the end of this section.
Under a flat key (one epoch key for the whole object), the AEAD
budget sets the size. Which class binds follows from the AEAD:
Sullivan Expires 6 May 2027 [Page 66]
Internet-Draft raAE November 2026
+=====================+============================================+
| Binding class | Flat-key write-once limit |
+=====================+============================================+
| Block-size birthday | the AEAD's own block-count bound, for AES- |
| | GCM 2^((8*Nb + 1 - 32)/2) / n_blk segments |
+---------------------+--------------------------------------------+
| Derived-nonce MRAE | the AEAD's coupled multi-user bound |
| workload | (Section 5.8.7.4) |
+---------------------+--------------------------------------------+
| No block-cipher | 2^63 segments, the index ceiling |
| structure | |
+---------------------+--------------------------------------------+
| No published block- | 2^63 segments, the index ceiling |
| size analysis | |
+---------------------+--------------------------------------------+
Table 12: Flat-key write-once size limit by binding class
The last two classes carry the same limit for different reasons. An
AEAD with no block-cipher structure, such as one built on a stream
cipher, has no block-size term. An AEAD whose analysis publishes
none may still have one, so a suite that places an AEAD in this class
says which case applies.
These figures assume derived nonce mode, which a non-MRAE AEAD may
use only under a nonce-uniqueness discipline, the write-once or
append-only profiles (Section 4.5.3.2). In random nonce mode such an
AEAD binds earlier, at the random-nonce-collision budget of 2^((8*Nn
+ 1 - 32)/2), about 2^32 per epoch key at Nn = 12 (Section 5.8.7.1),
or at a lower cap that the AEAD's own specification sets for random
nonces, such as AES-GCM's 2^32 encryptions per key (Section 5.8.1).
An append-only object re-encrypts one retained segment per append
(Section 4.9.3.1), so a segment appended one at a time is written
twice rather than once, at two distinct (i, is_final) pairs. The
block-size birthday figure, which counts blocks, therefore halves,
and an MRAE AEAD's multi-user bound counts the doubled writes in its
total workload (Section 5.8.7.4). The 2^63 index ceiling is
unchanged.
Epoch rotation supplies fresh keys but does not reset the aggregate
security budget. The structural ceiling is 2^63 segments, about 2^79
octets at segment_max 65536. Reaching it also requires the
applicable multi-user bounds to meet the aggregate target
(Section 5.8.2). An AEAD subject to the epoch-key collision class
additionally needs a sufficiently large epoch_length. At
epoch_length 0 that floor caps the total across every object in the
aggregate scope near 2^(4*Nk - 16) segments, about 2^48 at Nk = 16
Sullivan Expires 6 May 2027 [Page 67]
Internet-Draft raAE November 2026
(Section 5.8.6). Reaching 2^63 segments in one object then needs
epoch_length at least 15, which spends the scope's whole budget of
about 2^48 epoch keys on that object.
A rotating profile MUST keep each epoch key's 2^epoch_length initial
writes within its per-key budget. For a derived-nonce MRAE AEAD,
which has no per-key figure, the per-object rule of Section 5.8.7.4
takes the place of that budget absent an allocation. An append-only
profile adds one re-mark per superseded segment, so each epoch key
spans up to 2^(epoch_length + 1) pairs, and an encryptor MUST size
the per-key budget to cover those encryptions (Section 4.9.3.1).
Rewrite capacity is a separate condition (Section 5.8.5).
5.8.5. Rewrite Capacity
A rewrite consumes the same budget as an initial write. How that
budget is shared depends on the nonce mode.
For a random-nonce AEAD, epoch_length divides one per-epoch-key pool
among the 2^epoch_length segments that share the key. If encryptions
are spread evenly, the count each segment can take falls as
epoch_length rises:
encryptions per segment = 2^((8*Nn + 1 - 32)/2) / 2^epoch_length
The count includes each segment's initial write, so it leaves one
fewer rewrite. At Nn = 12 that is about 2^(32 - epoch_length): about
2^32 encryptions per segment at epoch_length 0, about 2^26 at 6, and
about 2^22 at 10. For AES-GCM the numerator is instead its cap of
2^32 (Section 5.8.1), which counts initial writes and rewrites
together, so at epoch_length 32 an AES-GCM epoch has room for its
initial writes and no rewrites.
For a derived-nonce MRAE AEAD, a rewrite reuses the segment's derived
nonce. Its isolated hot-segment cap depends on length, but its
allowed rewrite count also depends on the aggregate workload. For
AES-GCM-SIV, the multi-user bound couples total processed blocks to
the maximum blocks at one (epoch key, nonce) pair (Section 5.8.7.4).
Giving every segment the isolated hot-segment cap exceeds the same
advantage target. Distinct-nonce counts and forgery attempts also
enter that bound. An MRAE AEAD built another way uses its own
analysis.
The random-nonce figures above are per-key nonce-collision figures;
Section 5.8.2 scales them to an aggregate target. An AEAD whose
nonce size makes a flat key safe uses one, subject to its full
confidentiality and integrity bounds.
Sullivan Expires 6 May 2027 [Page 68]
Internet-Draft raAE November 2026
Applications MUST track segment encryptions per key, and for a
derived-nonce MRAE AEAD the accounted blocks of Section 5.8.7.4, and
freeze the object before a per-key, per-object, or aggregate budget
is exceeded. The CEK is fixed per object and cannot be rotated in
place, so continued writing requires a new object under a fresh CEK,
whose budgets are new but still count in the aggregate
(Section 5.8.2).
5.8.6. Choosing epoch_length
epoch_length means different things by mode. For the random-nonce
AEADs, a smaller epoch_length puts fewer segments under each key, so
each segment keeps a larger share of the random-nonce collision pool,
at the cost of more epoch keys to derive and hold. For a derived-
nonce MRAE AEAD, a smaller epoch_length reduces the distinct derived
nonces under an epoch key, but the allowed rewrite count still
depends on the aggregate workload (Section 5.8.7.4). An AEAD with a
256-bit nonce (Nn = 32) makes collision negligible and has a high
forgery floor, so a flat key (epoch_length 63) is the natural choice.
The cipher suite's default epoch_length, used when no epoch_length is
chosen, is 0 for the suites with an epoch_length range and 63 for the
suites whose nonce size makes a flat key safe. A referencing
protocol may choose directly, or by citing a profile or named
instantiation that fixes a value.
A referencing protocol that chooses an epoch_length tuned to its
expected segment count, rather than taking the default, trades some
rotation for fewer epoch keys while staying within budget. Because a
segment may be shorter than segment_max, size epoch_length by the
number of segments rather than the object's octet length.
The epoch keys are independent under the PRF security of the KDF
([RFC8645]), so the epoch_length parameter controls budget
distribution, not key strength.
An AEAD with a 128-bit key (Nk = 16) adds one further constraint.
The epoch-key collision term (Appendix C.2) over the n_ep distinct
epoch keys is about:
n_ep^2 / 2^(8*Nk)
A profile whose AEAD has Nk = 16 SHOULD keep total distinct epoch
keys in the aggregate scope below about 2^(4*Nk - 16), which is about
2^48 at Nk = 16 and holds that term within the 2^-32 target. At
epoch_length 0 this caps the total across every object in that scope
at about 2^48 segments, about 2^64 octets at segment_max 65536.
Sullivan Expires 6 May 2027 [Page 69]
Internet-Draft raAE November 2026
5.8.7. Derivations
5.8.7.1. Confidentiality (Nonce Collision)
For random nonce mode with Nn-octet nonces and q segment encryptions
under one key, the collision probability follows the birthday bound:
P(collision) <= q^2 / 2^(8*Nn + 1)
When epoch_length = r is specified, q counts encryptions per epoch
key (initial writes plus rewrites within that epoch), not across the
whole content. The probability of any collision across keys is the
sum bound in Section 5.8.2, so per-key budgets share an aggregate
allocation. A collision costs integrity as well. For a non-MRAE
AEAD whose authenticator is a polynomial universal hash it recovers
an authentication key (Section 6.3): under AES-GCM the GHASH key
([NIST-SP-800-38D]), which authenticates every nonce under that epoch
key, and under ChaCha20-Poly1305 the one-time Poly1305 key for that
nonce.
For derived nonce mode, nonces are deterministic and distinct across
segment indices, so this collision term does not apply. The limits
on reusing a derived nonce are in Section 5.8.7.4.
5.8.7.2. Confidentiality (Block-Size Birthday Bound)
Nonce collisions alone do not exhaust the confidentiality bound. A
block-cipher AEAD has a distinguishing bound that grows with the
total number of cipher blocks processed under a key, which each AEAD
takes from its own analysis. For AES-GCM, following the AEAD usage-
limits analysis ([I-D.irtf-cfrg-aead-limits]), if s is the total
number of AAD-plus-plaintext blocks, each Nb octets, and q is the
number of encryption queries under a key, the confidentiality
advantage is at most:
CA <= ((s + q + 1)^2) / 2^(8*Nb + 1)
Each encryption processes at most n_blk blocks, so s <= n_blk * q and
CA is at most about q^2 * n_blk^2 / 2^(8*Nb + 1). Solved against the
2^-32 target, the per-key budget is about:
q <= 2^((8*Nb + 1 - 32)/2) / n_blk
about 2^36 at Nb = 16 and n_blk = 4096. In random nonce mode the
nonce-collision bound dominates for typical deployments, and the
block-size term overtakes it only once n_blk^2 exceeds the threshold
below, which is 2^32 at Nb = 16 and Nn = 12:
Sullivan Expires 6 May 2027 [Page 70]
Internet-Draft raAE November 2026
nonce collision: q^2 / 2^(8*Nn + 1)
threshold: n_blk^2 > 2^(8*(Nb - Nn))
In derived nonce mode the nonce-collision term vanishes and the
block-size term is the binding confidentiality constraint.
An AEAD with no block-cipher structure, such as one built on a stream
cipher, has no comparable block-size bound, leaving nonce collision
and forgery as the only relevant terms. Nonce collision is
negligible at a large Nn, and the per-query forgery bound governs
integrity.
SEAL implementations MUST enforce usage budgets computed from the
AEAD-specific confidentiality and integrity bounds, not from nonce-
collision probability alone, and within any cap the AEAD's own
specification sets. The budgets derive from the consuming protocol's
allocation of the aggregate target (Section 5.8.2), or, absent an
allocation, are the per-key figures of this section, with the per-
object rule of Section 5.8.7.4 as the data-volume budget for a
derived-nonce MRAE AEAD.
5.8.7.3. Integrity (Forgery)
Each AEAD decryption query gives the adversary a chance to forge a
valid ciphertext. The forgery advantage per query depends on the
AEAD's own analysis and on segment_max:
IA <= v * F(segment_max)
where v is the number of forgery attempts and F(segment_max) is the
per-query forgery advantage the AEAD's analysis gives at a segment of
segment_max octets. F grows with segment_max, so a larger segment
lowers the attempt budget for a fixed target. The tag length bounds
F from below, at about 2^(-8*Nt), so no AEAD offers more than about
8*Nt bits of forgery resistance per query. An AEAD's authenticator
may achieve less than its tag length suggests, so F is not determined
by Nt and a suite takes F from the analysis of its own AEAD.
[I-D.irtf-cfrg-aead-limits] gives F for several AEADs.
5.8.7.4. Derived-Nonce Bounds
A derived-nonce MRAE AEAD needs its own multi-user analysis. Counts
of distinct nonces and repeated encryptions at each nonce are coupled
to the total workload and are not independent budgets.
For AES-GCM-SIV this section takes one term of the bound, the data-
volume term of [BHT18] Theorem 6, with c the theorem's hash
parameter:
Sullivan Expires 6 May 2027 [Page 71]
Internet-Draft raAE November 2026
C * L * B / 2^128, C = 48*c + 30
L is the total block length of encryption and verification queries.
B bounds encryption blocks at any one (user, nonce) pair, a user
being one epoch key here. Block accounting includes associated data
and padding as in that analysis. The theorem's bound is all-in-one,
so this term governs integrity as well as confidentiality. The full
bound adds a constant term and further terms in L, in the ideal-
cipher work, and in the cross-user nonce repetition, and its
hypotheses must hold. Those terms share the aggregate allocation of
Section 5.8.2. This section's figures take an adversary that reads
ciphertexts and makes no verification queries, so L counts encryption
blocks. Assigning epsilon_data to this term requires:
C * L * B / 2^128 <= epsilon_data
For an illustration of the scaling, let ell be the accounted blocks
per encryption, with the whole workload in scope n_rw encryptions at
one (key, nonce) pair and no other encryption, or H equally busy
pairs, each encrypted n_rw times:
one active pair: L = B = n_rw * ell
H active pairs: L = H * n_rw * ell, B = n_rw * ell
The allocated term gives:
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
POLYVAL has c = 1.5 ([BHT18] Remark 1), so C = 102, and an
epsilon_data of 2^-32 then gives one active pair about 2^34.7
encryptions of a 16 KiB segment and about 2^32.7 of a 64 KiB one.
Initial writes and the finality re-marks of appends and truncations
also contribute to the full workload.
Absent an allocation of the aggregate target (Section 5.8.2), the
object is the scope for this term. The encryptor tracks L_obj, the
accounted blocks of every segment encryption under the object's epoch
keys, and B_obj, the largest total of accounted blocks over all
encryptions at any one (epoch key, nonce) pair. It freezes the
object before the term exceeds 2^96, the term at 2^-32:
C * L_obj * B_obj <= 2^96, about L_obj * B_obj <= 2^89.3 at C = 102
Sullivan Expires 6 May 2027 [Page 72]
Internet-Draft raAE November 2026
Verifying a ciphertext that no encryption produced at the same (epoch
key, nonce, associated data) is a forgery attempt (Section 5.8.7.3),
and its blocks enter L as well. Each attempt adds about the
following for every block it processes, with B the largest encryption
load at any one pair, whichever pair the attempt targets:
C * B / 2^128
Where a deployment admits such attempts, L_obj also counts the blocks
of those the consuming protocol allows, which the encryptor does not
observe.
6. Security Considerations
For a position-respecting adversary, raAE's ra-ROR security target
(Section 5.1.1) rests on a multi-user real-or-random (mu-ROR$) AEAD,
a multi-user pseudorandom (mu-PRF) KDF, a fresh per-message salt,
and, where configured, nonces that do not collide under a nonce
hedge, the hedge KDF's PRF security under HedgedRandom, and the
snapshot authenticator's forgery resistance (Appendix C.2,
Appendix C.1). Integrity is bounded by the AEAD tag, about 8*Nt bits
per query (Section 5.8.7.3). A larger AEAD key raises
confidentiality margins, not the tag-length forgery floor.
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.
Sullivan Expires 6 May 2027 [Page 73]
Internet-Draft raAE November 2026
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).
+==============+===============================================+
| Failure mode | Detected by |
+==============+===============================================+
| Wrong CEK, | The commitment, before any segment decryption |
| salt, or | (Section 4.6), when reader and writer share |
| parameter | the payload_info construction. |
| set | |
+--------------+-----------------------------------------------+
| Modified | AEAD.Decrypt for the affected segment. |
| ciphertext | |
| core or AEAD | |
| tag | |
+--------------+-----------------------------------------------+
| Segment | AEAD.Decrypt: index and finality are bound by |
| moved to a | segment_aad (random nonce mode) or the nonce |
| different | (derived nonce mode). |
| index | |
+--------------+-----------------------------------------------+
| Segment | AEAD.Decrypt, when the source used a |
| copied from | different CEK or salt; a reused salt under |
| another | the same CEK breaks this separation |
| object at | (Section 6.8). |
| the same | |
| index | |
+--------------+-----------------------------------------------+
| Segment | SnapVerify, not per-segment AEAD alone, |
| copied from | unless the whole object including its |
| another | snapshot is rolled back to that earlier valid |
| version at | version, whether presented as is or after a |
| the same | writer updates it from a verified snapshot |
| index | that is not current (Section 3.3). |
+--------------+-----------------------------------------------+
| Dropped | Write-once: the finality requirement of |
| trailing | Section 4.9.1.2 (top present segment carries |
| segment(s) | is_final = 0). Length-changing: SnapVerify, |
| (truncation) | since a re-marked terminal (Section 4.9.3) |
| | can be replayed; the mutable profile always |
| | configures an authenticator. Truncation to |
| | the count of an intermediate snapshot, |
| | presented with that snapshot: SnapVerify with |
| | the value declared complete, and the finality |
Sullivan Expires 6 May 2027 [Page 74]
Internet-Draft raAE November 2026
| | requirement. Rollback (Section 6.7). |
| | Truncation to zero: the zero-segment |
| | prohibition (Section 4.7.4), or SnapVerify. |
+--------------+-----------------------------------------------+
| Missing | SnapVerify (index set, count, authenticator |
| interior, | inputs, recomputed keyed snapshot). |
| duplicated, | |
| reordered, | |
| or inserted | |
| segment | |
+--------------+-----------------------------------------------+
| Stale keyed | SnapVerify, unless the stale value is part of |
| snapshot | a whole-object rollback. |
+--------------+-----------------------------------------------+
| Whole-object | Not detected by raAE alone; the consuming |
| rollback | protocol needs authenticated external |
| | freshness state. |
+--------------+-----------------------------------------------+
| Equality | Not an authentication failure; rewriting |
| leakage in | equal plaintext at the same index can reveal |
| derived | equality (Section 4.5.3, Section 6.3). |
| nonce mode | |
+--------------+-----------------------------------------------+
Table 13: Failure modes and the checks that detect them
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.
Sullivan Expires 6 May 2027 [Page 75]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 76]
Internet-Draft raAE November 2026
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:
+======================+==============+===============+
| AEAD class / profile | random nonce | derived nonce |
+======================+==============+===============+
| non-MRAE, mutable | valid | unsafe |
+----------------------+--------------+---------------+
| non-MRAE, write-once | valid | valid |
| or append-only | | |
+----------------------+--------------+---------------+
| MRAE, any profile | wasteful | valid |
+----------------------+--------------+---------------+
Table 14: Nonce mode by AEAD class and profile
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
Sullivan Expires 6 May 2027 [Page 77]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 78]
Internet-Draft raAE November 2026
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).
Sullivan Expires 6 May 2027 [Page 79]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 80]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 81]
Internet-Draft raAE November 2026
7. IANA Considerations
This document has no IANA actions. It defines an abstract primitive
and a parameterized construction and requests no code points or
registries of its own. The cipher-suite code points and the
registries of named instantiations and snapshot authenticators are
specified in the companion ([I-D.sullivan-seal-concrete]).
The normative reference to [I-D.ietf-hpke-pq], which defines the one-
step KDF class this document's combiner admits, is a reference to a
work in progress, so publication of this document waits on it.
8. References
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>.
Sullivan Expires 6 May 2027 [Page 82]
Internet-Draft raAE November 2026
[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>.
Sullivan Expires 6 May 2027 [Page 83]
Internet-Draft raAE November 2026
[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.
Sullivan Expires 6 May 2027 [Page 84]
Internet-Draft raAE November 2026
[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>.
Appendix A. Optional Plaintext-Bound Nonce Construction
This appendix is informative. It describes an optional encryptor-
side construction that mixes plaintext content into the per-segment
nonce derivation to defend against RNG state duplication. The
construction is encryptor-only: the decryptor reads the resulting
nonce from the wire (in the same slot used by random mode) and never
invokes any of the machinery below. Implementations MAY use this
construction in place of a fresh CSPRNG call when generating nonces
under nonce_mode "random". The wire format is indistinguishable from
random mode and decryption is unaffected.
One such construction:
pt_digest(i) = LH(P_i)
encryption_params = [aead_id, segment_max_be, kdf_id]
pt_hash(i) = KDF(protocol_id, pt_hash_label,
[pt_digest(i)],
encryption_params, Nh)
nonce_ctx = encode(protocol_id, uint64(i), pt_hash(i),
segment_aad(i, is_final, A_i))
nonce(i) = KDF(protocol_id, pt_nonce_label,
[Random(Nn), payload_key],
[...payload_info, nonce_ctx], Nn)
This construction fixes two labels:
+==========================+================+============+
| Derivation role | Label variable | Value |
+==========================+================+============+
| Plaintext digest binding | pt_hash_label | "pt-nonce" |
+--------------------------+----------------+------------+
| Final nonce derivation | pt_nonce_label | "nonce" |
+--------------------------+----------------+------------+
Table 15: Plaintext-bound construction labels
Sullivan Expires 6 May 2027 [Page 85]
Internet-Draft raAE November 2026
Both labels are distinct from all other SEAL labels. Neither
derivation uses nonce_base_label (Table 4): the "nonce_base" label
belongs to derived nonce mode and does not appear in this
construction. In the final derivation nonce_ctx enters the info list
as one element after the payload_info elements: its encode output is
framed behind a length prefix like any other element, not spliced
flat into the list.
LH is the over-large-field digest of Section 4.3. Its collision
resistance is justified in Section 4.3.
nonce_ctx carries segment_aad (Section 4.4.2), so the derivation
binds the finality bit and A_i as well as the plaintext and index. A
derivation over the plaintext and index alone does not bind the
complete effective AEAD context. Under duplicated RNG state, an
unchanged-plaintext terminal re-mark or a change to A_i would repeat
the earlier nonce under different associated data. For a non-MRAE
AEAD with a polynomial-hash authenticator, that recovers the
authentication key (Section 6.3).
When the encryptor's CSPRNG produces duplicated state (for example,
from a virtual machine snapshot or a fork without reseed), two
encryptions that differ in plaintext or segment AAD at the same index
yield different derivation inputs, subject to LH and KDF collisions.
Nonce collisions remain subject to the Nn-octet output bound. Under
the same payload schedule, identical plaintexts, index, segment AAD,
and random input yield identical nonces and ciphertexts, revealing
only plaintext equality. An identical rewrite then also repeats its
tag, which voids the random-mode exemption that
[I-D.sullivan-seal-concrete] gives removed tags under the writer rule
(Section 3.3).
For rewrites under this construction, the encryptor recomputes
pt_hash(i) and nonce_ctx from the new plaintext and segment AAD,
derives a fresh nonce(i) with a new Random(Nn), seals the new
plaintext under the new nonce, and updates the keyed snapshot as in
Section 4.9.2.1.
Appendix B. Optional Hedged Randomness
When a long-term symmetric key sk of at least Nh octets is available
to the encryptor, implementations SHOULD mix it into random
generation using the hedging pattern of [RFC8937]. If only an
asymmetric private key is available, it MUST first be processed
through a KDF to produce a uniform symmetric key.
Sullivan Expires 6 May 2027 [Page 86]
Internet-Draft raAE November 2026
hedge_key = KDF(protocol_id, hedge_label, sk, [], Nh)
HedgedRandom(n, label):
;; tag2: unique to each call under hedge_key, such as a counter
return KDF(protocol_id, label,
[hedge_key, Random(n)], [tag2], n)
This construction fixes one label, hedge_label = "hedge", distinct
from all other SEAL labels. Here tag2 is the per-call nonce of
[RFC8937] Section 4: a value unique to each call under one hedge_key,
such as a counter that never repeats or a timer guaranteed to differ
per call. With it no two calls present the KDF the same input, even
when their CSPRNG draws repeat. Calls under one hedge_key MUST NOT
repeat tag2, including calls by another process or device that holds
sk and calls after a restart ([RFC8937] Section 4). A counter
therefore needs persistent state or an instance-unique prefix, the
role tag1 plays in [RFC8937].
HedgedRandom output depends on both the CSPRNG and sk, so a weak
CSPRNG alone cannot predict it. Hedging does not help when
duplicated state also rolls back tag2's source, as restoring a
virtual machine snapshot can roll back a counter: the CSPRNG output
and tag2 then repeat together, against the rule above, and
HedgedRandom repeats its output. Appendix A describes an optional
encryptor-side construction that partially defends against state
duplication. It is orthogonal to hedging and the two MAY be
combined.
Appendix C. Proof Status and Security Claim Provenance
This appendix is informative. Table 16 gives each security claim's
source, argument, and assumptions. Each is inherited from [FLRR25],
argued in this document, referenced from external work, or deferred
to the proof paper in preparation ([SEALPROOFS]). The one claim
proved in full here is the KDF combiner's injectivity.
The combiner's input encoding is injective by its length-prefixed
framing, not by any KDF property (Section 4.3, Section 5.4).
Collision resistance is assumed only of LH for over-large fields, of
the commitment derivation (Appendix C.4), and, with the ciphertext
digest set, of LH and, against a key holder, of the KDF under a known
snap_key, to bind each segment's ciphertext (Section 4.7.1).
Sullivan Expires 6 May 2027 [Page 87]
Internet-Draft raAE November 2026
C.1. Provenance of the Security Claims
+============+==============+========+==============================+
|Property |Source |Argument| Rests on |
+============+==============+========+==============================+
|ra-ROR |[FLRR25] |Appendix| mu-PRF KDF (two keying |
| |notion and |C.2, | levels), mu-ROR$ AEAD, a |
| |base proof; |Appendix| nonce-collision term only |
| |SEAL's |C.3 | under a nonce hedge, a PRF |
| |arbitrary- | | hedge KDF under HedgedRandom |
| |position ra- | | keyed by an sk sampled |
| |ROR syntax is | | independently of all CEKs, |
| |a SEAL- | | fresh per-message salt, an |
| |specific | | information-theoretic |
| |obligation; | | commitment guess for a |
| |re-encrypting | | forged StartDec header (q_sd |
| |a position is | | / 2^(8*commitment_length)), |
| |outside the | | and the configured snapshot |
| |base proof, | | authenticator's resistance |
| |formal | | to forgery (Adv_snap) |
| |treatment in | | |
| |[SEALPROOFS] | | |
+------------+--------------+--------+------------------------------+
|ra-CMT |[FLRR25] |Appendix| collision resistance of the |
|(commitment,|notion, |C.4 | commitment derivation map |
|position- |restricted | | over (protocol_id, "commit", |
|matched, |here to fixed | | CEK, payload_info, G, |
|fixed A_i) |A_i | | commitment_length); |
| | | | differing A_i requires a |
| | | | separate AEAD AAD-commitment |
| | | | term not established here |
+------------+--------------+--------+------------------------------+
|ra-CMT-p |[FLRR25] |Appendix| scoped ra-CMT collision |
|(position |notion and |C.4 | bound plus the underlying |
|commitment, |base proof; | | AEAD's commitment bound for |
|fixed A_i) |for fixed A_i | | the forged position, not |
| |it reduces to | | restored against a CEK |
| |the | | holder, where SEAL's strict |
| |underlying | | snapshot authenticators with |
| |AEAD's | | the ciphertext digest set |
| |commitment | | give the weaker per-index |
| |bound, which | | binding of Section 5.6 in |
| |SEAL's suites | | both nonce modes and every |
| |do not | | suite under an externally |
| |provide | | authenticated snapshot; |
| |against a CEK | | differing A_i remains |
| |holder, and | | outside the ra-CMT-p claim |
| |the weaker | | |
Sullivan Expires 6 May 2027 [Page 88]
Internet-Draft raAE November 2026
| |per-index | | |
| |binding of | | |
| |Section 5.6 | | |
| |applies; | | |
| |formal write- | | |
| |up in | | |
| |[SEALPROOFS] | | |
+------------+--------------+--------+------------------------------+
|KDF combiner|this document |Section | injectivity of the length- |
|injectivity |(injectivity |4.3, | prefixed encoding (KDF need |
|and domain |structural |Section | not be injective); collision |
|separation |and proof- |5.4 | resistance of LH for over- |
| |complete; | | large fields only; domain |
| |domain | | separation further rests on |
| |separation by | | HMAC used as a PRF through |
| |assumption) | | its message input in the |
| | | | two-step form, where the |
| | | | secret enters Extract's ikm |
| | | | under the public protocol_id |
| | | | salt, and on the XOF used as |
| | | | a PRF through a secret |
| | | | element of its framed input |
| | | | in the one-step form |
+------------+--------------+--------+------------------------------+
|Snapshot |this document |Section | unforgeability of the keyed |
|integrity |(notion, |5.7 | snapshot by a party without |
| |Section | | snap_key; per-object |
| |5.1.4); | | separation via salt-bound |
| |configured | | snap_key |
| |authenticator | | |
| |(bound, with | | |
| |no writer | | |
| |oracle; a | | |
| |game with one | | |
| |is deferred | | |
| |to | | |
| |[SEALPROOFS]) | | |
+------------+--------------+--------+------------------------------+
|AEAD usage, |external work |Section | [I-D.irtf-cfrg-aead-limits], |
|rewrite, and|(operational, |5.8, | [RFC8452] Section 9 with |
|max-object |not proven |Section | [BHT18], [NIST-SP-800-38D] |
|bounds |here) |5.8.4, | Section 8.3 for the AES-GCM |
| | |Section | random-nonce cap, 2^63 |
| | |5.8.7.4 | segment-index ceiling |
+------------+--------------+--------+------------------------------+
|Derived- |precedent, |Section | write-once or append-only |
|nonce |not proof |4.5.3.2,| uniqueness discipline |
|unique-nonce|(TLS 1.3 |Appendix| reducing to nonce-respecting |
Sullivan Expires 6 May 2027 [Page 89]
Internet-Draft raAE November 2026
|transform |[RFC8446], |C.5 | AEAD security |
| |STREAM | | |
| |[HRRV15]) | | |
+------------+--------------+--------+------------------------------+
|Derived- |this |Appendix| MRAE AEAD ([RFC8452]); the |
|nonce |document; |C.5 | coupled data-volume term of |
|equality |full proof in | | the AEAD's multi-user bound |
|leakage |[SEALPROOFS] | | (Section 5.8.7.4) |
|(MRAE) | | | |
+------------+--------------+--------+------------------------------+
Table 16: 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
Sullivan Expires 6 May 2027 [Page 90]
Internet-Draft raAE November 2026
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.
Sullivan Expires 6 May 2027 [Page 91]
Internet-Draft raAE November 2026
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
Sullivan Expires 6 May 2027 [Page 92]
Internet-Draft raAE November 2026
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,
Sullivan Expires 6 May 2027 [Page 93]
Internet-Draft raAE November 2026
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).
Sullivan Expires 6 May 2027 [Page 94]
Internet-Draft raAE November 2026
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.
Appendix D. Design Rationale
This appendix is informative.
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
Sullivan Expires 6 May 2027 [Page 95]
Internet-Draft raAE November 2026
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.
Appendix E. Changes Since -03
* The strict snapshot authenticators' segment leaf carries the
stored nonce in random nonce mode or the counter (i << 1) |
is_final in derived nonce mode, then the segment AAD, and metadata
entries hold its leading fields in leaf order. With the
ciphertext digest set, per-index binding under an authenticated
snapshot holds in both nonce modes for every suite, for any A_i,
and under an intermediate snapshot. SnapVerify takes each
segment's A_i and the snapshot's declared state.
* ra-CMT and ra-CMT-p are scoped to fixed A_i. An authenticated
strict snapshot with the ciphertext digest set gives per-index
binding, not ra-CMT-p. The plaintext-bound nonce derivation
frames the full segment AAD.
Sullivan Expires 6 May 2027 [Page 96]
Internet-Draft raAE November 2026
* EncSeg keeps its base signature and outputs only the ciphertext.
The snapshot is a function of the (index, input) set and the
count. RewriteSeg and SnapVerify take a witness, and before an
update the writer checks the witness, and any input it removes,
against a verified snapshot unless it produced them itself as the
sole writer. The crash-retry rule is reconciled.
* A truncation to a nonempty prefix drops the trailing segments and
re-marks the new last segment as final, the reverse of the append
re-mark, and the append-only profile forbids truncation itself
rather than a reduced count. An append's re-mark carries the
segment's existing plaintext, and Rewrite's inputs are bound.
* An authenticator with a strict ordering has intermediate
snapshots, its keyed and public snapshots at any count where the
object is open, and a linear one has none; what such a value binds
and how truncation to that count is detected are stated.
* A strict authenticator defines a public snapshot, an unkeyed
function of payload_info and the same inputs, which a verifier
without the CEK accepts only under a signed statement naming the
object, the count, whether the object was open or complete, and
the value. A key holder that claims the signer's origin checks
both values.
* The ra-ROR bound is restated with a header-forgery term and the
configured authenticator's Adv_snap; the LH collision argument is
stated precisely. HedgedRandom carries a per-call tag2.
* Aggregate usage accounting and the coupled MRAE rewrite bounds;
the AES-GCM random-nonce cap of 2^32 per epoch key; the salt-reuse
swap discussion.
* The salt is public in the threat model; resource-exhaustion
considerations are added; references are updated; the discussion
venue is raae@ietf.org.
* Terms: keyed snapshot, public snapshot, intermediate snapshot,
prefix verification, and ciphertext digest.
Acknowledgments
The author thanks Andrés Fábrega, Thomas Ristenpart, Gregory Rubin,
Richard Barnes, Brendan McMillion, Thibault Meunier, Kenny Paterson,
Christopher Patton, Martin Thomson, Stanislav V. Smyshlyaev, and
Christopher A. Wood for their reviews, comments, and discussions.
Sullivan Expires 6 May 2027 [Page 97]
Internet-Draft raAE November 2026
Author's Address
Nick Sullivan
Cryptography Consulting LLC
Email: nicholas.sullivan+ietf@gmail.com
Sullivan Expires 6 May 2027 [Page 98]