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

[John Mattsson <[e-mail]>]

I would personally be fine with an IETF–CFRG split.

Will raAE and SEAL be discussed anywhere in Vienna (CFRG, DISPATCH, Hackathon, side-meeting, etc.)? I think they should be.

Standardizing raAE and defining interoperable formats for its use would be one of the most useful ideas I have seen in a long time. I believe such a specification would see broad adoption across a wide range of protocols and applications.

Cheers,
John Preuß Mattsson

From: Nick Sullivan <[e-mail]>
Date: Wednesday, 15 July 2026 at 15:06
To: Martin Thomson <[e-mail]>; [e-mail] <[e-mail]>
Cc: [e-mail] <[e-mail]>; [e-mail] <[e-mail]>
Subject: [CFRG] Re: Random-access authenticated encryption (raAE) draft

Hi Martin,

Following up on your point that this belongs in the IETF. After some reflection, I propose a pressure test: run raAE and SEAL through the two-lane model in draft-sullivan-crypto-publication (https://datatracker.ietf.org/doc/draft-sullivan-crypto-publication/) the pattern generalized from the HPKE WG. SEAL sits at the same abstraction layer as HPKE, so it could be a good test of the model.

The two lanes:

  engineering lane (IETF)   |   research lane (CFRG)
                            |
  MLS (attachments)         |
  file encryption (TBD)     |
  MoQ (?)   OpenPGP (?)     |
           |                |
           v                |
         SEAL <------------------>  raAE
     concrete raAE          |    abstract primitive
     via dispatch           |    analogous to AEAD


Consumers pool their requirements into SEAL, the engineering piece, which goes to dispatch to find its IETF home. raAE stays in CFRG as the security foundation for SEAL: the abstract definition, requirements, and security reductions for random-access authenticated encryption, building on validated public research. The file encryption John suggested in this thread could become its own working group or land in an existing one, with SEAL under the hood.

There are concrete benefits over current designs for the potential consumers marked with a question mark:
- MoQ adopted an SFrame-based scheme for end-to-end objects in March (draft-ietf-moq-secure-objects). It encrypts a whole object in one AEAD call, and the draft notes that a large object must arrive in full before any validation can start. A SEAL payload validates segment by segment as bytes arrive, and a reader can verify one segment of a cached object without reading the rest.
- OpenPGP verifies a signature only after decrypting and hashing the entire message. A SEIPD v3 built on SEAL would sign the one snapshot value, so a reader verifies a signature over any part of a message without reading the rest. raAE also helps with editing.

I've cc'd the authors of both in case there's interest. There are also opportunities to consolidate other designs under the raAE primitive interface, even if SEAL is not the exact raAE chosen.

What do you think?

Best,
Nick

On Tue, Jul 14, 2026 at 10:06 AM Nick Sullivan <[e-mail]<mailto:[e-mail]>> wrote:
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]<mailto:[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]<mailto:[e-mail]>
> To unsubscribe send an email to [e-mail]<mailto:[e-mail]>

_______________________________________________
CFRG mailing list -- [e-mail]<mailto:[e-mail]>
To unsubscribe send an email to [e-mail]<mailto:[e-mail]>