aead: in-place AAD streaming

[chrysn]

For very constrained applications (no_std with only a few kB of RAM), constructing the complete as a contiguous buffer can be onerous to the application. (For example, for OSCORE the AAD can be up to a message size large if many Class-I options are used – not that those options would be common, but it's a worst-case).

Please consider adding a means to feed the AAD into an encryption/decryption process piecemeal; could look like this:

trait AeadWithStreamAd {
    type EncryptPrepraration<'a>: EncryptPreparation<'a>;
    fn encrypt_in_place_detached_streamad<'a>(
        &'a self,
        nonce: &'aGenericArray<u8, Self::NonceSize>,
        associated_data_hint: Option<usize>,
        buffer: &'amut [u8]
    ) -> Self::EncryptPreparation<'a>;
}
trait EncryptPreparation<'a> {
    fn feed_ad(&mut self, &[u8]);
    fn finish(self) -> Result<GenericArray<u8, Self::TagSize>, Error>;
}

(Straw-man proposal, not thought through w/rt associated type life times obviously).

It can then be used as

let state = aead.encrypt_in_place_streamad(nonce, prediced_ad_length, &mut buffer);
state.feed_ad(b"\x85\x48Encrypt0\x81\x18\x18");
for chunk in message.ad_components() {
    state.feed_ad(chunk);
}
state.finish().expect("Encryption failure");

An implementation of that trait would trivially implement the Aead trait, so this could be added without breaking the 0.2 API.

The associated_data_hint parameter gives the size of the AD (leaving it optional as some AEAD algorithms like ChaCha20/Poly1305 or AES-GCM don't need to know it in advance; for others it's an error to use without specifying; could be trait-dependent or just mandatory as well), not feeding exactly that many bytes could be caught as an error.

Previous discusson on this happened in libcose and in the context of monocypher (the latter concluded with using neatly-wrapped primitives of the AEAD algorithms instead, but I think with Rust's zero-cost approach and cleaner APIs, this could have a place here). OpenSSL supports this mode of operation for AES-GCM.

[tarcieri]

The general security framework for this concept I prefer is the notion of Online Authenticated Encryption (OAE) and within that framework there are two provably secure schemes for this developed by Phil Rogaway et al, one of which I've implemented in Miscreant which is the predecessor of the aes-siv crate:

• STREAM: provides nonce-based online authenticated encryption (nOAE), a segmented/streaming AEAD scheme
• CHAIN: (mentioned in the aforementioned paper) requires an MRAE cipher but provides a stronger notion of security called OAE2 which provably guarantees a sequence of AEAD messages was encrypted/decrypted in-order

Note that STREAM is presently implemented in Miscreant. It might be interesting to upstream its implementation somewhere in the RustCrypto project.

[chrysn]

Unless I misread the OAE abstract, these are not the features I ask: OAE is about streaming plaintext/ciphertext. I'm talking about streaming only the AAD, while the plain-/ciphertext is fully available (thus avoiding doom). That should be doable securely with the algorithms that satisfy the AEAD interface, and matters for implementing existing protocols.

(edit: removed link behind doom because it does not exactly describe what I meant, which is the threat of applications receiving and possibly processing online data before its authenticity is confirmed.)

[tarcieri]

Aah yes, that is a bit different, although note that both CHAIN and STREAM (at least in one formulation in the paper, and the version of STREAM as incremented by Miscreant) support per-segment AAD.

Looking at the protocol you linked:

For example, for OSCORE the AAD can be up to a message size large if many Class-I options are used – not that those options would be common, but it's a worst-case

I was trying to find where this was documented in the RFC you linked and was only able to find this:

https://tools.ietf.org/html/rfc8613#section-5.4

...which shows an example of 45 bytes AAD.

To me the Aead/AeadMut traits already seem a bit overloaded with three methods which all effectively do different flavors of the same thing. I'm curious if they could be refactored/decomposed into more traits (e.g. AeadDetached/AeadMutDetached) rather than continuing to overload them with more methods. I think it might make more sense for something like this to be a different trait (e.g. AeadMutStreamingAad or something), with a blanket impl for the non-streaming AAD cases.

Specifically for your use case, is more than one AEAD mode actually supported / required? Glancing at that RFC, it looks like AES-CCM is primarily supported (which presently we don't have an implementation of, although there is an aes-ccm crate built on various subcomponents of this project). I say that because unless there is, having this API as part of the trait probably won't be helpful.

[chrysn]

On Wed, Nov 27, 2019 at 08:51:00AM -0800, Tony Arcieri wrote:

...which shows an example of 45 bytes AAD.

The AAD contains, via external_aad, the options field, which is a reserialization of options found in the outer message. Now currently none of those are described, but the first one in the pipeline is the description of SCHC compression applied inside the ciphertext (see https://github.com/lp-wan/coap-compression/issues/9), and those will probably be a SHA256 hash or so -- point is, it's hard to predict, and thus hard to reserve space for.

To me the Aead/AeadMut traits already seem a bit overloaded with three methods which all effectively do different flavors of the same thing.

I'm open to any other way of doing this than packing onto that trait.

Specifically for your use case, is more than one AEAD mode actually supported / required?

Algorithm-wise, AES-CCM is mandatory-to-implement, but given crypto library support for AES-CCM is lacking, implementations with ChaCha20/Poly1305-only (or that plus AES-GCM) are already cropping up. (Disclaimer: I'm the author of the offender, and working with my current crypto backend to fix that).

OSCORE itself doesn't really touch on those but relies on COSE to specify that (OSCORE only speaks of the "ciphertext" which COSE readily provides as including both the ciphertext and the AEAD). I can't really put my finger on where they define that the COSE ciphertext is always "ciphertext | tag" (checking back with the authors; COSE only speaks of the longer ciphertext, but references RFC7539 which says "The output from the AEAD is twofold"), but that's how it's done there.

As far as I can tell, an OSCORE implementation should not need more per-algorithm information than the NewAead plus Aead[Mut] traits already provide (by implementation and associated lengths), except for the COSE numbers to look them up.

[tarcieri]

Ok. API-wise I'd suggest something which looks like like a combination of AeadMut and Mac, which works sort of like your EncryptPreparation trait, but instead of finish has an encrypt_in_place() and decrypt_in_place() methods instead. Something like this (which also impls NewAead):

(ignore the horrible name, but I'm having a hard time thinking of a good one)

pub trait AeadWithStreamingAad {
    fn input_aad(&mut self, aad: &[u8]) -> Result<(), Error>;
    fn encrypt_in_place(self, nonce: &GenericArray<u8, Self::NonceSize>, buffer: &mut impl Buffer) -> Result<(), Error>;
    fn decrypt_in_place(self, nonce: &GenericArray<u8, Self::NonceSize>, buffer: &mut impl Buffer) -> Result<(), Error>;
}

There could also be a blanket impl of AeadMut for all AeadWithStreamingAad.

[chrysn]

From interaction with algorithms, I think it'll need a bit more information already at AAD feeding time; that's why I started that lifetime monster. I don't know the algorithms well enough to know what exactly is needed, but at least the total AAD length needs to be known before AAD is fed the first time (AES-CCM needs that). I think I remember it'll need the nonce as well, and probably even the buffer (Poly1305 only needs the ciphertext when AAD is through, but AFAIR AES-CCM needs at least the ciphertext length at the start of the AAD).

[tarcieri]

Aah, that's unfortunate re: AES-CCM. Pretty much all of the modes I've implemented do the opposite: making the AAD the very first input into the MAC (with padding), then the ciphertext, then as the very last inputs to the MAC the lengths of each respectively.

Re: the nonce though, you're definitely right. Several ciphers need to know it in advance as they use it for key derivation (XChaCha20Poly1305 and AES-GCM-SIV come to mind)

Note: separately it looks like I can get aead crate trait impls into the aes-ccm crate.

[tarcieri]

I got a PR into the aes-ccm crate to have it use the aead API:

https://github.com/martindisch/aes-ccm/pull/3

That said...

@chrysn I under AES-CCM quite a bit better now, and just as a general point, it seems like it has some pretty Unusual Requirements for this sort of API which make it particularly ugly:

• As you noted, the length of the plaintext message and AAD need to be known in advance
• Not only does the AAD length need to be known up front, but AAD is MAC'd last rather than first, which I guess is what necessitates your original API as opposed to my suggestion which provides the nonce/message last. My suggestion won't work with AES-CCM at all.
• In general the way AES-CCM encodes the AAD is quite odd, using a variable-length length tag

[tarcieri]

Closing in favor of #1364 which is more general and covers both AAD and the input message