A constant-time version of aes-gcm decrypt-in-place-detached?

[cbeck88]

Hi, I have a use-case that is roughly the following (simplified):

• A private key exists only in an SGX enclave
• A stream of ciphertexts are passed to the enclave, which it attempts to decrypt
• It must remain a secret which ones were decryptable by the enclave and which ones aren't, taking into account side-channel leakage via code and data access patterns.

Unfortunately I can't quite do that with the aes-gcm code as is:

    fn decrypt_in_place_detached(
        &self,
        nonce: &GenericArray<u8, NonceSize>,
        associated_data: &[u8],
        buffer: &mut [u8],
        tag: &Tag,
    ) -> Result<(), Error> {
        if buffer.len() as u64 > C_MAX || associated_data.len() as u64 > A_MAX {
            return Err(Error);
        }

        // TODO(tarcieri): interleave encryption with GHASH
        // See: <https://github.com/RustCrypto/AEADs/issues/74>
        let mut expected_tag = self.compute_tag(associated_data, buffer);
        let mut ctr = self.init_ctr(nonce);
        ctr.apply_keystream(&self.cipher, expected_tag.as_mut_slice());

        use subtle::ConstantTimeEq;
        if expected_tag.ct_eq(&tag).unwrap_u8() == 1 {
            ctr.apply_keystream(&self.cipher, buffer);
            Ok(())
        } else {
            Err(Error)
        }
    }

What I would really like is a version of this function that looks like this for example:

    fn ct_decrypt_in_place_detached(
        &self,
        nonce: &GenericArray<u8, NonceSize>,
        associated_data: &[u8],
        buffer: &mut [u8],
        tag: &Tag,
    ) -> bool {
        if buffer.len() as u64 > C_MAX || associated_data.len() as u64 > A_MAX {
            return false;
        }

        // TODO(tarcieri): interleave encryption with GHASH
        // See: <https://github.com/RustCrypto/AEADs/issues/74>
        let mut expected_tag = self.compute_tag(associated_data, buffer);
        let mut ctr = self.init_ctr(nonce);
        ctr.apply_keystream(&self.cipher, expected_tag.as_mut_slice());
        ctr.apply_keystream(&self.cipher, buffer);

        use subtle::ConstantTimeEq;
        bool::from(expected_tag.ct_eq(&tag))
    }

The key differences being:

• ctr.apply_keystream(&self.cipher, buffer); happens unconditionally and we never branch on the outcome of mac check
• Instead of returning Result, we return bool, or perhaps some subtle type. Because afaik there is no branchless way to access Result. (I don't know that I can assume that result.is_ok() won't contain a branch? I assume it boils down to a rust match against an enum, and would contain a branch unless the compiler optimized the branch away. I would hope that llvm can optimize this though.) But also, it's not clear that in rust, you can create Result type without branching?

What do you think? Would you take a patch that
(1) Adds ct_detached_in_place_decrypt to trait AeadInPlace in RustCrypto/traits? (and possibly, makes detached_in_place_decrypt chain to this by default?)
OR
(2) Adds a new trait AeadInPlaceCt or similar in RustCrypto/traits , and adds the function there, and implements it on AesGcm struct?

Slight preference for not putting subtle types in an API because it will ease versioning?

[tarcieri]

Is there a specific reason you need this to work with AES-GCM? Otherwise AES-GCM-SIV or AES-SIV already provide this property.

[cbeck88]

i don't think there is, let me look at those two versions to confirm they meet my needs

[cbeck88]

It seems to me that aes-gcm-siv does this right now:

https://github.com/RustCrypto/AEADs/blob/master/aes-gcm-siv/src/lib.rs#L347

    /// Decrypt the given message, first authenticating ciphertext integrity
    /// and returning an error if it's been tampered with.
    pub(crate) fn decrypt_in_place_detached(
        mut self,
        associated_data: &[u8],
        buffer: &mut [u8],
        tag: &Tag,
    ) -> Result<(), Error> {
        if buffer.len() as u64 > C_MAX || associated_data.len() as u64 > A_MAX {
            return Err(Error);
        }

        self.polyval.update_padded(associated_data);
        let mut ctr = Ctr32::new(tag);

        for chunk in buffer.chunks_mut(BLOCK_SIZE * B::ParBlocks::to_usize()) {
            ctr.apply_keystream(&self.enc_cipher, chunk);
            self.polyval.update_padded(chunk);
        }

        let expected_tag = self.finish_tag(associated_data.len(), buffer.len());

        use subtle::ConstantTimeEq;
        if expected_tag.ct_eq(&tag).unwrap_u8() == 1 {
            Ok(())
        } else {
            // On MAC verify failure, re-encrypt the plaintext buffer to
            // prevent accidental exposure.
            Ctr32::new(tag).apply_keystream(&self.enc_cipher, buffer);
            Err(Error)
        }
    }

So it's still branching on the mac, and conditionally touching the buffer, which
is what I'd like to avoid.

The aes-siv one looks like this:

https://github.com/RustCrypto/AEADs/blob/master/aes-siv/src/lib.rs#L225

    fn decrypt_in_place_detached(
        &self,
        nonce: &GenericArray<u8, Self::NonceSize>,
        associated_data: &[u8],
        buffer: &mut [u8],
        tag: &GenericArray<u8, Self::TagSize>,
    ) -> Result<(), Error> {
        Siv::<C, M>::new(self.key.clone()).decrypt_in_place_detached(
            &[associated_data, nonce.as_slice()],
            buffer,
            tag,
        )
    }

calling out to

https://github.com/RustCrypto/AEADs/blob/master/aes-siv/src/siv.rs#L207

    pub fn decrypt_in_place_detached<I, T>(
        &mut self,
        headers: I,
        ciphertext: &mut [u8],
        siv_tag: &Tag,
    ) -> Result<(), Error>
    where
        I: IntoIterator<Item = T>,
        T: AsRef<[u8]>,
    {
        self.xor_with_keystream(*siv_tag, ciphertext);
        let computed_siv_tag = s2v(&mut self.mac, headers, ciphertext)?;

        // Note: constant-time comparison of `crypto_mac::Output` values
        if crypto_mac::Output::<M>::new(computed_siv_tag) == crypto_mac::Output::new(*siv_tag) {
            Ok(())
        } else {
            // Re-encrypt the decrypted plaintext to avoid revealing it
            self.xor_with_keystream(*siv_tag, ciphertext);
            Err(Error)
        }
    }

So it's very similar to the aes-gcm-siv one.

I think in both of these cases, if there were a ct_decrypt_in_place_detached,
these functions could call that, and then branch on the result of mac check and
do the re-encryption -- but users who need not to have that branch could call
ct_decrypt_in_place_detached?

[tarcieri]

Yeah, you're right the re-encryption makes it variable-time.

Honestly I think maybe your best bet is to build a special crate for your use case. Avoiding that re-encryption step, in either an AES-GCM implementation that still decrypts the buffer, or an AES-(GCM-)-SIV, risks exposing the buffer containing the unauthenticated decryption, and since everything is built on in-place encryption, I'm not sure how you would avoid that with this sort of interface.

I'm not really a fan of exposing that as part of the API in these crates, but for your use case, it might be fine (especially if you had an always-allocating version which first copies the ciphertext into a Vec return buffer that can be discarded).

[cbeck88]

okay -- thank you!

[cbeck88]

For my understanding -- why is it so bad to expose the buffer containing the unauthenticated decryption? Presumably that buffer is just noise, right? Or is it like, if the attacker can get many such buffers then they can perhaps mount an attack, for some cipher types?

[tarcieri]

Or is it like, if the attacker can get many such buffers then they can perhaps mount an attack, for some cipher types?

Yes, if the attacker can learn anything from the decryption of the buffer, chosen ciphertext attacks become possible, which is what AEAD modes are supposed to strategically prevent.

[tarcieri]

FYI: I just cut a ctr v0.6.0-pre release which includes a Ctr32BE type, which as of #227 is now used by the aes-gcm crate.

You should be able to use this as part of your constant-time aes-gcm (or aes-gcm-siv with Ctr32LE) implementation.