ctr: use `BlockEncrypt` instead of `BlockEncryptMut`

[tarcieri]

As far as I can tell this is just a mistake: the only state in CTR mode is the counter, and there is no reason to mandate some sort of stateful block cipher as part of the bounds.

A BlockCipherMut bound is a significant impediment to upgrading the AEAD crates, which all impl AeadInPlace instead of AeadMutInPlace, store block cipher instances (which avoids re-expanding keys), and need to be able to share immutable references to those block cipher instances.

[tarcieri]

@newpavlov I notice that all of the crates in this repo seem to use BlockEncryptMut/BlockDecryptMut bounds. It seems like they should all be changed to BlockEncrypt/BlockDecrypt?

[newpavlov]

No, BlockEncryptMut is a less restrictive trait than BlockEncrypt. We have a blanket impl of the former for types which implement the latter, not the other way around. Imagine a hardware acceleration engine on an embedded device which requires exclusive access. We would like to be able to use wrapper around it in our block mode crates, but it can not implement BlockEncrypt, only BlockEncryptMut.

[tarcieri]

This makes it impossible to use the ctr crate without having a mutable reference to the block cipher instance, which likewise makes it impossible to share stateless AEAD instances, which is a complete nonstarter for my usages of AEADs, and I imagine holds for many other people too.

I'm aware of the embedded applications: I was the one who originally added BlockCipherMut in https://github.com/RustCrypto/traits/pull/179 specifically for this purpose. But to support those applications, we should have *Mut counterparts to AEADs without forcing stateless software implementations to require a mut reference too when there are no mutations to their state.

[newpavlov]

Ctr<&aes::Aes128> works in my private code without any issues. Note that we have a blanket impl of BlockEncrypt for &T where T: BlockEncrypt, which then gets chained with the blanket impl of BlockEncryptMut, thus &T should satisfy the BlockEncryptMut bound without any issues. Can you show a code snippet which could work, but currently does not?

[tarcieri]

Here's a contrived example (minimized from the aes-gcm crate):

pub struct MyAead<C> {
    cipher: C
}

impl<C> MyAead<C>
where
    C: BlockCipher + BlockEncrypt + BlockSizeUser<BlockSize = U16>,
{
    pub fn init_ctr(&self) -> Ctr32BE<&C> {
        Ctr32BE::inner_iv_init(&self.cipher, &Default::default())
    }
}

This results in the following error:

error[E0599]: no function or associated item named `inner_iv_init` found for struct `StreamCipherCoreWrapper` in the current scope
  --> src/main.rs:14:18
   |
14 |         Ctr32BE::inner_iv_init(&self.cipher, &Default::default())
   |                  ^^^^^^^^^^^^^ function or associated item not found in `StreamCipherCoreWrapper<CtrCore<_, Ctr32BE>>`                                                                   ++++++++++++++++++++++

If I try BlockEncryptMut:

error[E0277]: the trait bound `C: BlockEncrypt` is not satisfied
  --> src/main.rs:13:31
   |
13 |     pub fn init_ctr(&self) -> Ctr32BE<&C> {
   |                               ^^^^^^^^^^^ the trait `BlockEncrypt` is not implemented for `C`
   |
   = note: required because of the requirements on the impl of `BlockEncrypt` for `&C`
   = note: required because of the requirements on the impl of `BlockEncryptMut` for `&C`
   = note: required because of the requirements on the impl of `BlockSizeUser` for `CtrCore<&C, Ctr32BE>`
help: consider further restricting this bound
   |
11 |     C: BlockCipher + BlockEncryptMut + BlockSizeUser<BlockSize = U16> + cipher::BlockEncrypt,
   |                                                                       ++++++++++++++++++++++

If I try both:

error[E0599]: no function or associated item named `inner_iv_init` found for struct `StreamCipherCoreWrapper` in the current scope
  --> src/main.rs:14:18
   |
14 |         Ctr32BE::inner_iv_init(&self.cipher, &Default::default())
   |                  ^^^^^^^^^^^^^ function or associated item not found in `StreamCipherCoreWrapper<CtrCore<_, Ctr32BE>>`

If I try adding bounds to the reference type:

pub struct MyAead<C> {
    cipher: C
}

impl<C> MyAead<C>
where
    C: BlockCipher + BlockEncrypt + BlockSizeUser<BlockSize = U16>,
{
    pub fn init_ctr<'a>(&'a self) -> Ctr32BE<&'a C>
    where
        &'a C: BlockCipher + BlockEncryptMut + BlockSizeUser<BlockSize = U16>,
    {
        Ctr32BE::inner_iv_init(&self.cipher, &Default::default())
    }
}

then...

error[E0599]: no function or associated item named `inner_iv_init` found for struct `StreamCipherCoreWrapper` in the current scope
  --> src/main.rs:17:18
   |
17 |         Ctr32BE::inner_iv_init(&self.cipher, &Default::default())
   |                  ^^^^^^^^^^^^^ function or associated item not found in `StreamCipherCoreWrapper<CtrCore<_, Ctr32BE>>`

Even if there were a way to make this work, if I can't figure out how to do it, no one else will.

Stateless block ciphers are far and away going to be the most common use case, so I don't think it makes sense to attempt to gloss over mutability in ways that will cause a confusing user experience.

[newpavlov]

Ah, I see. The problem you are hitting here is outlined in this comment. I've chose to implement KeyIvInit and KeyInit over InnerIvInit, since they are used more often. We have a similar issue with being unable to implement BlockEncryptMut for &mut T where T: BlockEncryptMut since it conflicts with the blanket impl for BlockEncrypt. It applies to the *Init traits as well.

You can work around it by manually creating a core CTR instance first:

pub fn init_ctr(&self) -> Ctr32BE<&C> {
    let core = CtrCore::inner_iv_init(&self.cipher, &Default::default());
    Ctr32BE::from_core(core)
}

I agree that the current situation is not ideal, but I do not think that we should artificially limit block mode capabilities to work around language limitations.

[newpavlov]

BTW since in AEAD crates we allow processing of only fully available messages, you do not need the StreamCipherCoreWrapper for them. You could instead use the StreamCipherCore::try_apply_keystream_partial method.

[tarcieri]

I agree that the current situation is not ideal, but I do not think that we should artificially limit block mode capabilities to work around language limitations.

I think the proper and idiomatic Rust solution is to provide *Mut variants of each of the block mode types which permits &mut self access to the cipher state, rather than trying to force everything through *Mut traits and requiring errata to work around what very much feels like a leaky abstraction.

BlockEncrypt/BlockDecrypt are the common case. In fact, I can't find any real-world usages of BlockCipherMut. So it seems really bad to introduce unnecessary complications, complexity, and confusion in aid of what is at best an extremely niche use case and a leaky abstraction.

Speaking as the person who added BlockCipherMut originally for the embedded cryptographic accelerator use case, in hindsight I'm not sure it actually fits that case particularly well. I think embedded cryptographic accelerators would really benefit from an async API, where a block can be sent to a cryptographic accelerator/coprocessor to be encrypted while the host MCU is used to perform authentication on the previous block in an interleaved manner. When authentication is done, the cipher implementation can await() the accelerator's completion, signaled via an interrupt which is polled by something like an RTIC idle task.

With the forthcoming stabilization of GATs that will soon be possible in stable Rust. But if the trait moves from just &self vs &mut self to also incorporating async operation, it will become even less tenable to try to paper over the distinction with blanket impls. You would force everything to be async-first at that point, something I think is widely considered a mistake in the design of the WebCrypto API.

BTW since in AEAD crates we allow processing of only fully available messages, you do not need the StreamCipherCoreWrapper for them. You could instead use the StreamCipherCore::try_apply_keystream_partial method.

I'll try to make that work. It's a bit more complex than that as both AES-GCM and ChaCha20Poly1305 both require extracting the beginning of the keystream for a MAC parameter (a mask for AES-GCM, and the Poly1305 key for ChaCha20Poly1305). But I think it can be expressed in terms of StreamCipherCore.

[tarcieri]

Sidebar: I'm a bit confused why try_apply_keystream_partial consumes self. That doesn't quite seem "partial" to me?

Still might be able to make things work by using write_keystream_block

[newpavlov]

I think the proper and idiomatic Rust solution is to provide Mut variants of each of the block mode types which permits &mut self access to the cipher state, rather than trying to force everything through Mut traits and requiring errata to work around what very much feels like a leaky abstraction.

I disagree. It will be a completely unnecessary multiplication of exposed types.

Note that moving from BlockEncryptMut to BlockEncrypt in mode crates will do absolutely nothing to solve the issue encountered by you, so I think your arguments are misplaced here.

You may remember my negative opinion about Rust's approach to async, so I can not say much about potential extension of our traits to the async environment.

I'm a bit confused why try_apply_keystream_partial consumes self. That doesn't quite seem "partial" to me?

"Partial" here means that we use only a part of generated keystream last block and discard remaining bytes. Similarly to the padding methods, the idea is that a stream cipher instance should not be used after calling this method.

[tarcieri]

Note that moving from BlockEncryptMut to BlockEncrypt in mode crates will do absolutely nothing to solve the issue encountered by you, so I think your arguments are misplaced here.

I confirmed that this PR would fix the issues I was encountering adapting the aes-gcm crate. Unfortunately I didn't check in a WIP and I have since moved on to trying to make things work as-is.

[tarcieri]

I disagree. It will be a completely unnecessary multiplication of exposed types.

If there's one thing we should be optimizing for above all else, it should be clarity.

Relying on chained blanket impls which allow invoking traits on reference types in order to allow you to pass an immutable reference to something that's expecting a mutable reference is not clear whatsoever.

It is extremely confusing. I was confused, and even after understanding how it's supposed to work I was still puzzling over the documentation trying to check which paths through the blanket impls are possible. It's some of the most confusing Rust code I've ever encountered. If I find it confusing, people with no experience with this codebase at all are going to find it extremely confusing.

And as you admitted, the abstraction leaks in several places:

I've chose to implement KeyIvInit and KeyInit over InnerIvInit, since they are used more often. We have a similar issue with being unable to implement BlockEncryptMut for &mut T where T: BlockEncryptMut since it conflicts with the blanket impl for BlockEncrypt. It applies to the *Init traits as well.

This is not a good abstraction. It's a leaky abstraction that's harming clarity and usability, and those matter a hell of a lot more than eliminating code duplication, especially in cryptography.

BlockEncryptMut/BlockDecryptMut have no users. It probably isn't the right abstraction to begin with. It should not be the primary API to the detriment of the one people actually want to use, where if the API people actually wanted to use were the primary one instead, things would be significantly clearer without weird abstraction leaks and corner cases that need weird workarounds.

[newpavlov]

Introducing a bunch of identical, but not quite, types will not help with clarity.

Let's limit this discussion strictly to encrypt/decrypt traits and their application to the block mode crates. If you want to discuss API of the initialization traits and the issue with the stream wrapper, I think it's better to do it in a separate traits issue.

It's a leaky abstraction

I think we have a different understanding of what a leaky abstraction is. To me it sounds like arguing that our use of typenum to work around the language limitations is "a leaky abstraction". Ideally, we would not have to write blanket impls for &T/&mut T if T implements a trait which has only &self/&mut self methods. Without them we would have only extremely clear blanket impls of ref-traits implementing their mut counterparts, without any chaining you find so confusing.

Same applies to the lack of mutually exclusive traits. If we had an ability to specify that a type can not implement both InnerInit and InnerIvInit (same with KeyInit and KeyIvInit), then you simply wouldn't have encountered the issue, since the stream wrapper would've implemented all the expected traits.

We can improve "clarity" by making methods inherent or by removing the generic wrappers and instead using macros to generate code. But in my opinion it would be significant a step back. Currently, the generic wrappers not only reduce code duplication, but also encapsulate unsafe and boilerplate code.

In abstract, I believe that after you get familiar with the current hierarchy of traits, it is a good and somewhat elegant approach (though I can not call myself impartial in this regard). Yes, we are hitting certain language limitations (not only mutually exclusive traits, but also lack of rank-2 closures), which does not make things easier. But I think we should push for language improvement instead of dumbing down current code, reducing its flexibility and ballooning amount of boilerplate in the process.

I admit that cipher v0.4 severely lacks documentation, which makes understanding it significantly harder than it has to. Naming also can be improved. In particular, I don't quite like the duplication of _mut in method names.

BlockEncryptMut/BlockDecryptMut have no users.

What? All block modes work through them. Maybe you meant that no one currently uses modes with a type which implements only *Mut traits without their ref counterparts?

I agree that having BlockEncryptMut in block mode bounds may be potentially confusing for users. But I think its probability can be significantly reduced by improving the trait documentation, so it would explicitly state that it's implemented for block ciphers and their shared references.

Assuming that the embedded use case will be properly covered by hypothetical async traits, I am open to potentially changing it in cipher v0.5. But in this case, it probably would make sense to remove the BlockCipher trait and bring back the old BlockCipher/BlockMode naming, i.e. BlockEncrypt and BlockEncryptMut would be renamed to BlockCipherEncrypt and BlockModeEncrypt respectively.

[tarcieri]

Assuming that the embedded use case will be properly covered by hypothetical async traits, I am open to potentially changing it in cipher v0.5. But in this case, it probably would make sense to remove the BlockCipher trait and bring back the old BlockCipher/BlockMode naming, i.e. BlockEncrypt and BlockEncryptMut would be renamed to BlockCipherEncrypt and BlockModeEncrypt respectively.

This sounds like a good solution to me which clearly reflects the usage patterns. Thanks!

Will close this PR then.