[CFRG] Re: Random-access authenticated encryption (raAE) draft

[Nick Sullivan <[e-mail]>]

Hi Guilin,

Thanks for raising this question! They're complementary, and the comparison
is instructive about how powerful the raAE abstraction is. Content-defined
chunking cuts a data stream into chunks, choosing each cut point from the
bytes around it. An edit therefore re-cuts only its own neighborhood: the
chunk holding the edit changes, and every other chunk comes out
byte-identical, just shifted in the file. A store keeps one copy of each
chunk, so only the changed ones are stored again. raAE covers the other
half: authenticated encryption of segmented content, with random access and
one snapshot value a protocol can sign. A deduplicating store needs both,
and neither constrains the other.

The mapping is simple. A CDC chunk is a SEAL segment. Segments take any
length up to segment_max, so as long as CDC's maximum chunk size is at most
segment_max, chunks map to segments one to one, and boundaries are an input
raAE already accepts. What's nice is that two archive styles come
naturally: a static archive that grows by appending, and an updateable
archive with limited in-place edits, where a segment grows within the cap
or is rewritten outright. CDC decides where segments begin and end, and the
SEAL profile decides whether they can change afterward.

On your question about ciphertext changes: yes, in the locality sense. Each
segment is an independent AEAD ciphertext, so an altered segment fails its
own check while every other segment still decrypts and verifies. That's the
same locality CDC gives plaintext edits, applied to the ciphertext side.
Nothing slips through, though: the altered segment is rejected rather than
misdecrypted, and the object as a whole fails the snapshot check, so a
segment can't be changed or dropped unnoticed. A signed snapshot makes
verifying any segment one signature check plus a local read.

So the short summary is: yes, SEAL is a great fit for instantiating CDC,
backed by the security proofs extended raAE provides.

Best,
Nick

On Wed, Jul 15, 2026 at 4:18 AM Wang Guilin <Wang.Guilin=
[e-mail]> wrote:

> > Mutable objects, like encrypted file formats, encrypted disk images, and
> object stores that accept partial updates, also need in-place modification
> of any part without re-encrypting the whole.
>
> Does this mean that some changes in ciphertext do not affect decryption?
>
> raAE may relate to CDC (Content-Defined Chunking), a technology used in
> cloud backup setting. Here is a paper from the team of Prof. Kenny
> Paterson.
>
> Breaking and Fixing Content-Defined Chunking. CCS 2025: 2294-2308
>
> Cheers,
>
> Guilin
>
> *发件人：*Martin Thomson <[e-mail]>
> *收件人：*[e-mail] <[e-mail]>
> *时 间：*2026-07-14 16:02:33
> *主 题：*[CFRG] Re: Random-access authenticated encryption (raAE) draft
>
> Hi Nick,
>
> I'm going to suggest a DISPATCH outcome for this, which does not involve
> CFRG. I think that this is pure engineering and the IETF should be the
> place to take it up. The usual requirements apply, of course: we need to
> see the receipts on customers for the mechanism, etc...
>
> On Tue, Jul 14, 2026, at 00:54, Nick Sullivan wrote:
> > Hi all,
> >
> > Writing as an author, not a chair. I've been working on a draft I want
> > to share with the group. This is not a call for adoption, just sharing
> > the early draft in case there's interest. Comments and reviews welcome.
> >
> > *The **problem*. Applications dealing with large encrypted objects
> > (encrypted backups, encrypted archives, object stores) need to read any
> > part of the object without decrypting the whole thing. They also need
> > to verify that each part read belongs to the current object at its
> > claimed position, without processing the entire object. Mutable
> > objects, like encrypted file formats, encrypted disk images, and object
> > stores that accept partial updates, also need in-place modification of
> > any part without re-encrypting the whole. The positional and inclusion
> > proofs should also remain valid after each modification. Take an
> > encrypted database file or an encrypted disk image: any block is read
> > or written by index, and a reader wants to know that the block it reads
> > really belongs at the offset it came from in the current image, without
> > re-hashing every block on every write. No proven security notion in the
> > literature covers all of this under one primitive. As such, each
> > application ends up rolling its own segmented AE layer, mostly without
> > security proofs for the rewrite and whole-object cases.
> >
> > Prior work covers pieces of the problem. CHAIN (Hoang, Reyhanitabar,
> > Rogaway, Vizár 2015) is sequential. STREAM (same paper) supports
> > random-access decryption of individual segments and encodes a
> > final-segment bit for truncation detection, but has no whole-object
> > snapshot and no in-place rewrite. Its deployed relatives (Tink
> > Streaming AEAD, OpenPGP v2 SEIPD) are write-once streaming formats and
> > don't expose rewrite at all. The v2 SEIPD design is itself the outcome
> > of Efail (Poddebniak et al., USENIX 2018), where v1's whole-message
> > integrity failed and applications acted on unauthenticated plaintext.
> > FLOE (Fábrega, Len, Ristenpart, Rubin; ePrint 2025/2275) formalizes
> > random-access AEAD security cleanly and gives a proven construction.
> > This work builds on that formal foundation.
> >
> > I've posted draft-sullivan-cfrg-raae-02, "Random-Access Authenticated
> > Encryption." It covers the primitive, the security notions, the prior
> > constructions in the space, and a concrete family of instantiations
> > with test vectors called SEAL (Segmented Encryption and Authentication
> > Layer), as well as a security analysis (companion paper forthcoming)
> > and write/rewrite budgets.
> >
> > The draft has two layers. raAE is the abstract primitive: the base
> > interface and security notions come from Fábrega et al., which this
> > document extends. SEAL is one concrete construction of raAE,
> > parameterized by an AEAD, a KDF, and an epoch length. It has two
> > profiles (immutable and mutable) and an optional snapshot authenticator
> > that binds the whole segment set and updates cheaply on rewrite. A
> > protocol that would previously have signed the whole encrypted object
> > can sign the snapshot authenticator instead and get the same
> > authentication scope without touching the segments. The snapshot
> > authenticator is also not a single construction, different
> > authenticators fit different consuming-protocol contexts. For example,
> > settings that supply only a single CEKs and owner per object versus
> > settings with a shared CEK (as in MLS) necessitate different
> > authenticators.
> >
> > Freshness against whole-object rollback, storage transactions, and key
> > management are explicitly out of scope. Those belong in a consuming
> > protocol.
> >
> > The shortest path to a concrete, testable thing is to read
> > SEAL-simple(AES-256-GCM, HKDF-SHA-256) in Appendix E
> > <
> https://www.ietf.org/archive/id/draft-sullivan-cfrg-raae-02.html#name-seal-simple-implementation->,
>
> > which is the degenerate case for SEAL with no rewrites or snapshot
> > authentication and fixed legacy AEAD/KDF.
> >
> > Reviews and comments on the framing, the security notions, the
> > construction, or the scope are all useful.
> >
> > Draft: https://www.ietf.org/archive/id/draft-sullivan-cfrg-raae-02.html
> >
> > Best,
> > Nick
> > _______________________________________________
> > CFRG mailing list -- [e-mail]
> > To unsubscribe send an email to [e-mail]
>
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>