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

[John Mattsson <[e-mail]>]

Hi Nick,

Thanks for the explanation. I agree that there is a large research component here. However, I am not sure it is more research-oriented than IETF work such as IKEv2, TLS 1.3, LAKE, MLS, Privacy Pass, or Oblivious HTTP.

I do not really care where the work happens as long as it progresses. I strongly support this work no matter where it is done. CFRG participation would be great, and I do not mind whether the final result becomes an IETF RFC, and IRTF RFC, or both.

One problem with CFRG is that the work is constrained by the limited number of CFRG slots available. An IETF WG has the advantage of a dedicated mailing list and dedicated meeting time on the agenda. It is difficult to allocate, for example, 90 minutes of CFRG meeting time for a detailed discussion of raAE.

Cheers,
John Preuß Mattsson

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

Hi John,

Thanks for the support. You're right that even a write-once file encryption standard would be worth having. The bigger value, in my view, is making segmented encryption a first-order primitive like AEAD, rather than having to build it ad hoc in each protocol.

Ad hoc file and segment encryption has a long history of breaking. Disk encryption shows the pattern at its most extreme: the layout came first, so integrity was dropped entirely, and tampering goes undetected by design. Homegrown segmented schemes repeat one another's mistakes: nonce reuse, undetected truncation, missing key commitment, and
optional integrity checking, which in practice means none. Even the careful designs diverge, each marking end of message its own way, argued from scratch. And none of these schemes gives you anything to sign but the whole object, so verifying any part of a signed object means reading all of it.

The way out is to start from a formal treatment and distill the cryptographic elements abstractly, leaving layout to the consuming protocol. That's the AEAD model: AEAD is the analyzed primitive, and the consuming protocol handles framing, nonces, keys, and tags. raAE is a first-order primitive of the same kind, except the unit is segmented content rather than a single message. It takes a content key, binds the segments together (optionally), and leaves layout and key management to the protocol. So you could build an HPKE-raAE the way HPKE wraps an AEAD, for instance. When the guarantee lives in the primitive, the protocol using it inherits the guarantee. The protocol's layout choices can't bring the old issues back.

That's how this draft is built. raAE is the abstract primitive, with the interface and security notions from Fábrega et al.'s FLOE paper, extended with in-place rewrite and a snapshot that authenticates the full segment set and its count. SEAL is the construction: pick an AEAD, a KDF, and parameters, and you get a concrete instantiation in a write-once or mutable profile, analyzed against the stated requirements. A protocol that needs origin authentication signs the one snapshot value, and a reader verifies a single segment against it without reading the rest of the object.

The prior art lands as points in that design space. A write-once SEAL with derived nonces coincides with STREAM at the nonce and AEAD layer. Tink and OpenPGP v2 SEIPD are deployed formats in the same family. SEAL-simple in the appendix is the minimal instantiation: an implementation sketch and test vectors, enough to build a conforming encryptor and decryptor.

On venue: this draft is the research and requirements work, so in my view, it should sit in CFRG. The interoperable format is where the IETF comes in, and that's the path to the standardization you're after.

Best,
Nick


On Tue, Jul 14, 2026 at 9:27 AM John Mattsson <john.mattsson=[e-mail]<mailto:[e-mail]>> wrote:
Hi Nick,

Thanks for driving this!

I think this has a lot of value and something the IETF should work on. I think even standardizing file encryption even without random-access would have value. My experience is that very weak file options like openssl-enc, gpg, and deriving a keys from low entropy passwords are still commonly used in practice.

openssl-cms - CMS and age are modern secure options but lack random access.
https://github.com/filosottile/age

Disk encryption standards have random access but lack integrity.

Agree with Martin that this can/should be done in IETF.

Cheers,
John Preuß Mattsson

From: Martin Thomson <[e-mail]<mailto:[e-mail]>>
Date: Tuesday, 14 July 2026 at 10:01
To: [e-mail]<mailto:[e-mail]> <[e-mail]<mailto:[e-mail]>>
Subject: [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://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Farchive%2Fid%2Fdraft-sullivan-cfrg-raae-02.html%23name-seal-simple-implementation-&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C2b5d3a29f3b34311dba908dee17e2832%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C639196129131599926%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=RB6Qzta8cW2zXvpt2fuW8kUrZ%2FJLvch0g5kH9wBa6G0%3D&reserved=0<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://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Farchive%2Fid%2Fdraft-sullivan-cfrg-raae-02.html&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C2b5d3a29f3b34311dba908dee17e2832%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C639196129131636376%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=PEqj1VekOr39dDt1di4%2FQNvdrsuR%2BP23JEK635HWbWk%3D&reserved=0<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]>
_______________________________________________
CFRG mailing list -- [e-mail]<mailto:[e-mail]>
To unsubscribe send an email to [e-mail]<mailto:[e-mail]>