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

[Martin Thomson <[e-mail]>]

This looks substantially simpler than TLS, which was done in the IETF.  I think that CFRG time is better spent on other things.

On Tue, Jul 14, 2026, at 11:06, Nick Sullivan 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]> 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]