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

[Nick Sullivan <[e-mail]>]

Hi Martin,

I’m not sure I fully agree. Something like SEAL-simple or SEAL-attachment
is probably pure engineering, but it seems like it would be useful to have
a comprehensive research-adjacent document like this to lean on for
analysis.

Nick

On Tue, Jul 14, 2026 at 9:01 AM Martin Thomson <[e-mail]> wrote:

> 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]
>