Date:   Fri, 8 Dec 2017 09:11:12 +0000
From:   Ard Biesheuvel <ard.biesheuvel@...aro.org>
To:     Eric Biggers <ebiggers3@...il.com>
Cc:     linux-fscrypt@...r.kernel.org, "Theodore Ts'o" <tytso@....edu>,
        linux-ext4@...r.kernel.org, linux-f2fs-devel@...ts.sourceforge.net,
        linux-mtd@...ts.infradead.org, linux-fsdevel@...r.kernel.org,
        "linux-crypto@...r.kernel.org" <linux-crypto@...r.kernel.org>,
        Jaegeuk Kim <jaegeuk@...nel.org>,
        Michael Halcrow <mhalcrow@...gle.com>,
        Paul Crowley <paulcrowley@...gle.com>,
        Martin Willi <martin@...ongswan.org>,
        David Gstir <david@...ma-star.at>,
        "Jason A . Donenfeld" <Jason@...c4.com>,
        Eric Biggers <ebiggers@...gle.com>
Subject: Re: [PATCH] fscrypt: add support for ChaCha20 contents encryption

Hi Eric,

On 8 December 2017 at 01:38, Eric Biggers <ebiggers3@...il.com> wrote:
> From: Eric Biggers <ebiggers@...gle.com>
>
> fscrypt currently only supports AES encryption.  However, many low-end
> mobile devices still use older CPUs such as ARMv7, which do not support
> the AES instructions (the ARMv8 Cryptography Extensions).  This results
> in very poor AES performance, even if the NEON bit-sliced implementation
> is used.  Roughly 20-40 MB/s is a typical number, in comparison to
> 300-800 MB/s on CPUs that support the AES instructions.  Switching from
> AES-256 to AES-128 only helps by about 30%.
>
> The result is that vendors don't enable encryption on these devices,
> leaving users unprotected.
>
> A performance difference of similar magnitude can also be observed on
> x86, between CPUs with and without the AES-NI instruction set.
>
> This patch provides an alternative to AES by updating fscrypt to support
> the ChaCha20 stream cipher (RFC7539) for contents encryption.  ChaCha20
> was designed to have a large security margin, to be efficient on
> general-purpose CPUs without dedicated instructions, and to be
> vectorizable.  It is already supported by the Linux crypto API,
> including a vectorized implementation for ARM using NEON instructions,
> and vectorized implementations for x86 using SSSE3 or AVX2 instructions.
>
> On 32-bit ARM processors with NEON support, ChaCha20 is about 3.2 times
> faster than AES-128-XTS (chacha20-neon vs. xts-aes-neonbs).  Without
> NEON support, ChaCha20 is about 1.5 times as fast (chacha20-generic vs.
> xts(aes-asm)).  The improvement over AES-256-XTS is even greater.
>
> Note that stream ciphers are not an ideal choice for disk encryption,
> since each data block has to be encrypted with the same IV each time it
> is overwritten.  Consequently, an adversary who observes the ciphertext
> both before and after a write can trivially recover the keystream if
> they can guess one of the plaintexts.  Moreover, an adversary who can
> write to the ciphertext can flip arbitrary bits in the plaintext, merely
> by flipping the corresponding bits in the ciphertext.  A block cipher
> operating in the XTS or CBC-ESSIV mode provides some protection against
> these types of attacks -- albeit not full protection, which would at
> minimum require the use an authenticated encryption mode with nonces.
>
> Unfortunately, we are unaware of any block cipher which performs as well
> as ChaCha20, has a similar or greater security margin, and has been
> subject to as much public security analysis.  We do not consider Speck
> to be a viable alternative at this time.
>
> Still, a stream cipher is sufficient to protect data confidentiality in
> the event of a single point-in-time permanent offline compromise of the
> disk, which currently is the primary threat model for fscrypt.  Thus,
> when the alternative is quite literally *no encryption*, we might as
> well use a stream cipher.
>
> We offer ChaCha20 rather than the reduced-round variants ChaCha8 or
> ChaCha12 because ChaCha20 has a much higher security margin, and we are
> primarily targeting CPUs where ChaCha20 is fast enough, in particular
> CPUs that have vector instructions such as NEON or SSSE3.  Also, the
> crypto API currently only supports ChaCha20.  Still, if ChaCha8 and/or
> ChaCha12 support were to be added to the crypto API, it would be
> straightforward to support them in fscrypt too.
>
> Currently, stream ciphers cannot be used for filenames encryption with
> fscrypt because all filenames in a directory have to be encrypted with
> the same IV.  Therefore, we offer ChaCha20 for contents encryption only.
> Filenames encryption still must use AES-256-CTS-CBC.  This is acceptable
> because filenames encryption is not as performance-critical as contents
> encryption.
>
> Reviewed-by: Michael Halcrow <mhalcrow@...gle.com>
> Signed-off-by: Eric Biggers <ebiggers@...gle.com>
> ---
>  Documentation/filesystems/fscrypt.rst | 43 +++++++++++++++++++---
>  fs/crypto/Kconfig                     |  1 +
>  fs/crypto/crypto.c                    | 69 ++++++++++++++++++++++++++++-------
>  fs/crypto/keyinfo.c                   |  2 +
>  include/linux/fscrypt.h               |  6 ++-
>  include/uapi/linux/fs.h               |  1 +
>  6 files changed, 102 insertions(+), 20 deletions(-)
>
> diff --git a/Documentation/filesystems/fscrypt.rst b/Documentation/filesystems/fscrypt.rst
> index 776ddc655f79..927d3c88816b 100644
> --- a/Documentation/filesystems/fscrypt.rst
> +++ b/Documentation/filesystems/fscrypt.rst
> @@ -184,6 +184,9 @@ replaced with HKDF or another more standard KDF in the future.
>  Encryption modes and usage
>  ==========================
>
> +Available modes
> +---------------
> +
>  fscrypt allows one encryption mode to be specified for file contents
>  and one encryption mode to be specified for filenames.  Different
>  directory trees are permitted to use different encryption modes.
> @@ -191,24 +194,52 @@ Currently, the following pairs of encryption modes are supported:
>
>  - AES-256-XTS for contents and AES-256-CTS-CBC for filenames
>  - AES-128-CBC for contents and AES-128-CTS-CBC for filenames
> +- ChaCha20 for contents and AES-256-CTS-CBC for filenames
>
>  It is strongly recommended to use AES-256-XTS for contents encryption.
>  AES-128-CBC was added only for low-powered embedded devices with
>  crypto accelerators such as CAAM or CESA that do not support XTS.
>
> +Similarly, ChaCha20 was only added for low-end devices that have
> +neither a CPU with AES instructions, nor a hardware crypto
> +accelerator.  Note that since ChaCha20 is a stream cipher, it is
> +easily broken if an attacker can view encrypted data both before and
> +after it is overwritten.  Thus, even moreso than the other modes,
> +ChaCha20 can protect data confidentiality *only* in the event of a
> +single point-in-time, permanent offline compromise of the storage.
> +Also, ChaCha20 is supported only for contents encryption, not
> +filenames encryption, because all filenames in a directory have to be
> +encrypted with the same IV, which would be especially inappropriate
> +for a stream cipher.
> +
>  New encryption modes can be added relatively easily, without changes
>  to individual filesystems.  However, authenticated encryption (AE)
>  modes are not currently supported because of the difficulty of dealing
>  with ciphertext expansion.
>
> +Contents encryption
> +-------------------
> +
>  For file contents, each filesystem block is encrypted independently.
>  Currently, only the case where the filesystem block size is equal to
> -the system's page size (usually 4096 bytes) is supported.  With the
> -XTS mode of operation (recommended), the logical block number within
> -the file is used as the IV.  With the CBC mode of operation (not
> -recommended), ESSIV is used; specifically, the IV for CBC is the
> -logical block number encrypted with AES-256, where the AES-256 key is
> -the SHA-256 hash of the inode's data encryption key.
> +the system's page size (usually 4096 bytes) is supported.
> +
> +With the XTS mode of operation, the logical block number within the
> +file is used as the IV.
> +
> +With the CBC mode of operation, ESSIV is used.  Specifically, the IV
> +is the file logical block number encrypted with AES-256, where the
> +AES-256 key is the SHA-256 hash of the inode's data encryption key.
> +
> +With ChaCha20, the file logical block number is also used as the IV,
> +but it is formatted differently to ensure that it is copied into the
> +"nonce" portion of the ChaCha20 initial state (words 14-15) rather
> +than the "block counter" portion (words 12-13).  This detail is
> +critical, since otherwise different portions of the file would be
> +encrypted with the same keystream.
> +
> +Filenames encryption
> +--------------------
>
>  For filenames, the full filename is encrypted at once.  Because of the
>  requirements to retain support for efficient directory lookups and
> diff --git a/fs/crypto/Kconfig b/fs/crypto/Kconfig
> index 02b7d91c9231..44f052e9d842 100644
> --- a/fs/crypto/Kconfig
> +++ b/fs/crypto/Kconfig
> @@ -3,6 +3,7 @@ config FS_ENCRYPTION
>         select CRYPTO
>         select CRYPTO_AES
>         select CRYPTO_CBC
> +       select CRYPTO_CHACHA20
>         select CRYPTO_ECB
>         select CRYPTO_XTS
>         select CRYPTO_CTS
> diff --git a/fs/crypto/crypto.c b/fs/crypto/crypto.c
> index 732a786cce9d..d5c95a18db59 100644
> --- a/fs/crypto/crypto.c
> +++ b/fs/crypto/crypto.c
> @@ -126,15 +126,66 @@ struct fscrypt_ctx *fscrypt_get_ctx(const struct inode *inode, gfp_t gfp_flags)
>  }
>  EXPORT_SYMBOL(fscrypt_get_ctx);
>
> +struct fscrypt_iv {
> +       __le64 first_half;
> +       __le64 second_half;
> +};
> +
> +/*
> + * Generate the IV for encrypting/decrypting the block at the given logical
> + * block number within a file.
> + */
> +static void fscrypt_generate_iv(struct fscrypt_iv *iv, u64 lblk_num,
> +                               const struct fscrypt_info *ci)
> +{
> +       BUILD_BUG_ON(sizeof(*iv) != FS_IV_SIZE);
> +
> +       if (ci->ci_data_mode == FS_ENCRYPTION_MODE_CHACHA20) {
> +               /*
> +                * ChaCha20 interprets its IV as a block counter followed by a
> +                * nonce.  We *MUST NOT* use the file logical block number as
> +                * the Chacha block counter because the ChaCha block counter
> +                * counts 64-byte ChaCha blocks, which are much smaller than
> +                * file blocks.  If we did, then portions of the keystream would
> +                * be repeated, which would be catastrophic.
> +                *

OK, so you are saying that LBA n + 1 will share its keystream with LBA
n but shift by 64 blocks, right? Yeah, that's terrible.

But I severely dislike having to make the fscrypt code intimately
aware of this. Why can't we just encrypt the IV like we do for
AES-CBC? We already pull in that code for the filenames anyway.
Alternatively, we could have a IV mangling wrapper around chacha20
that moves this special handling out of fscrypt.

> +                * We could initialize the block counter with the offset in the
> +                * file in ChaCha blocks.  But RFC7539 defines the ChaCha20
> +                * block counter to be 32-bit, which is only enough for a 256GiB
> +                * keystream.  Confusingly, this differs from the original
> +                * ChaCha paper which defines the block counter to be 64-bit.
> +                *
> +                * To be compatible with either convention, just put the file
> +                * logical block number in the second half of the IV, so that it
> +                * goes into the "nonce" portion of the ChaCha initial state
> +                * (words 14-15).  The ChaCha block counter then starts at 0 for
> +                * each file block.  In other words, we use one keystream per
> +                * file block instead of one keystream per file.
> +                */
> +               iv->first_half = 0;
> +               iv->second_half = cpu_to_le64(lblk_num);
> +
> +               BUG_ON(ci->ci_essiv_tfm != NULL);
> +       } else {
> +               /* XTS or CBC */
> +               iv->first_half = cpu_to_le64(lblk_num);
> +               iv->second_half = 0;
> +
> +               if (ci->ci_essiv_tfm != NULL) {
> +                       /* CBC */
> +                       BUILD_BUG_ON(AES_BLOCK_SIZE != FS_IV_SIZE);
> +                       crypto_cipher_encrypt_one(ci->ci_essiv_tfm,
> +                                                 (u8 *)iv, (u8 *)iv);
> +               }
> +       }
> +}
> +
>  int fscrypt_do_page_crypto(const struct inode *inode, fscrypt_direction_t rw,
>                            u64 lblk_num, struct page *src_page,
>                            struct page *dest_page, unsigned int len,
>                            unsigned int offs, gfp_t gfp_flags)
>  {
> -       struct {
> -               __le64 index;
> -               u8 padding[FS_IV_SIZE - sizeof(__le64)];
> -       } iv;
> +       struct fscrypt_iv iv;
>         struct skcipher_request *req = NULL;
>         DECLARE_CRYPTO_WAIT(wait);
>         struct scatterlist dst, src;
> @@ -144,15 +195,7 @@ int fscrypt_do_page_crypto(const struct inode *inode, fscrypt_direction_t rw,
>
>         BUG_ON(len == 0);
>
> -       BUILD_BUG_ON(sizeof(iv) != FS_IV_SIZE);
> -       BUILD_BUG_ON(AES_BLOCK_SIZE != FS_IV_SIZE);
> -       iv.index = cpu_to_le64(lblk_num);
> -       memset(iv.padding, 0, sizeof(iv.padding));
> -
> -       if (ci->ci_essiv_tfm != NULL) {
> -               crypto_cipher_encrypt_one(ci->ci_essiv_tfm, (u8 *)&iv,
> -                                         (u8 *)&iv);
> -       }
> +       fscrypt_generate_iv(&iv, lblk_num, ci);
>
>         req = skcipher_request_alloc(tfm, gfp_flags);
>         if (!req) {
> diff --git a/fs/crypto/keyinfo.c b/fs/crypto/keyinfo.c
> index 5e6e846f5a24..bae4cce2389a 100644
> --- a/fs/crypto/keyinfo.c
> +++ b/fs/crypto/keyinfo.c
> @@ -13,6 +13,7 @@
>  #include <linux/scatterlist.h>
>  #include <linux/ratelimit.h>
>  #include <crypto/aes.h>
> +#include <crypto/chacha20.h>
>  #include <crypto/sha.h>
>  #include "fscrypt_private.h"
>
> @@ -134,6 +135,7 @@ static const struct {
>                                              FS_AES_128_CBC_KEY_SIZE },
>         [FS_ENCRYPTION_MODE_AES_128_CTS] = { "cts(cbc(aes))",
>                                              FS_AES_128_CTS_KEY_SIZE },
> +       [FS_ENCRYPTION_MODE_CHACHA20]    = { "chacha20", CHACHA20_KEY_SIZE },
>  };
>
>  static int determine_cipher_type(struct fscrypt_info *ci, struct inode *inode,
> diff --git a/include/linux/fscrypt.h b/include/linux/fscrypt.h
> index 08b4b40c5aa8..1cfb7950f915 100644
> --- a/include/linux/fscrypt.h
> +++ b/include/linux/fscrypt.h
> @@ -100,11 +100,15 @@ static inline bool fscrypt_dummy_context_enabled(struct inode *inode)
>  static inline bool fscrypt_valid_enc_modes(u32 contents_mode,
>                                         u32 filenames_mode)
>  {
> +       if (contents_mode == FS_ENCRYPTION_MODE_AES_256_XTS &&
> +           filenames_mode == FS_ENCRYPTION_MODE_AES_256_CTS)
> +               return true;
> +
>         if (contents_mode == FS_ENCRYPTION_MODE_AES_128_CBC &&
>             filenames_mode == FS_ENCRYPTION_MODE_AES_128_CTS)
>                 return true;
>
> -       if (contents_mode == FS_ENCRYPTION_MODE_AES_256_XTS &&
> +       if (contents_mode == FS_ENCRYPTION_MODE_CHACHA20 &&
>             filenames_mode == FS_ENCRYPTION_MODE_AES_256_CTS)
>                 return true;
>
> diff --git a/include/uapi/linux/fs.h b/include/uapi/linux/fs.h
> index 4199f8acbce5..5a25eb2994b1 100644
> --- a/include/uapi/linux/fs.h
> +++ b/include/uapi/linux/fs.h
> @@ -275,6 +275,7 @@ struct fsxattr {
>  #define FS_ENCRYPTION_MODE_AES_256_CTS         4
>  #define FS_ENCRYPTION_MODE_AES_128_CBC         5
>  #define FS_ENCRYPTION_MODE_AES_128_CTS         6
> +#define FS_ENCRYPTION_MODE_CHACHA20            7
>
>  struct fscrypt_policy {
>         __u8 version;
> --
> 2.15.1.424.g9478a66081-goog
>

Powered by blists - more mailing lists