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

[John Mattsson <[e-mail]>]

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]>
Date: Tuesday, 14 July 2026 at 10:01
To: [e-mail] <[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]
> To unsubscribe send an email to [e-mail]

_______________________________________________
CFRG mailing list -- [e-mail]
To unsubscribe send an email to [e-mail]