Optional compact round keys for AES fixslice

[peterdettman]

In the current fixslice implementation there is some redundancy in the way keys are stored (2x for fixslice32, 4x for fixslice64). This enables the round keys to simply be XORed in for each round.

It is possible to store the round keys in a compact format and expand them in each round, which requires a few additional instructions (prototype code for fixslice64 puts this at 10% slower; the penalty will be smaller for fixslice32). The memory saving for the key storage is then: 50% i.e. 176/208/240 bytes for fixslice32 AES 128/192/256 respectively, or 75% i.e. 528/624/720 bytes for fixslice64.

Is there a standard cfg attribute for constrained memory devices, and/or should this project support a feature making smaller memory footprint a priority?

[newpavlov]

In some crates we have no_unroll feature (e.g. kuznyechik and keccak), which trades performance for reduced binary size.

It looks like expanding round keys per each encrypt_blocks call will be quite inefficient. We probably should first introduce a method which will process &mut [Block<Self>].

[tarcieri]

As of the latest release of cipher (v0.2.5) there are now BlockCipher::{encrypt_slice, decrypt_slice} methods:

https://docs.rs/cipher/0.2.5/cipher/block/trait.BlockCipher.html#method.encrypt_slice

These would allow you to expand the round keys before operating over a sequence of blocks.

[briansmith]

@peterdettman wrote:

It is possible to store the round keys in a compact format and expand them in each round, which requires a few additional instructions (prototype code for fixslice64 puts this at 10% slower; the penalty will be smaller for fixslice32). The memory saving for the key storage is then: 50% i.e. 176/208/240 bytes for fixslice32 AES 128/192/256 respectively, or 75% i.e. 528/624/720 bytes for fixslice64.

Put another way, implementing this suggestion would make the expanded keys the same size they are for AES-NI.

I agree this is highly desirable. Another use case is where the fixslice implementation is used as a fallback to an AES-NI implementation, and we want the fixslice expanded key to be no larger than the AES-NI key. Especially in the case where we are doing CPU feature detection to prefer AES-NI(-ish) when available and then fall back to fixslice when it isn't available, and where we want to store the expanded key, it's hard to accept the fallback implementation's key size to be larger than the fast one, if that would result in bloating the size of every key.

[briansmith]

@peterdettman Could you share your prototype somewhere? Thanks!