Commit graph

7 commits

Author SHA1 Message Date
Jason A. Donenfeld
1ff35ded67 UPSTREAM: crypto: poly1305 - add new 32 and 64-bit generic versions
These two C implementations from Zinc -- a 32x32 one and a 64x64 one,
depending on the platform -- come from Andrew Moon's public domain
poly1305-donna portable code, modified for usage in the kernel. The
precomputation in the 32-bit version and the use of 64x64 multiplies in
the 64-bit version make these perform better than the code it replaces.
Moon's code is also very widespread and has received many eyeballs of
scrutiny.

There's a bit of interference between the x86 implementation, which
relies on internal details of the old scalar implementation. In the next
commit, the x86 implementation will be replaced with a faster one that
doesn't rely on this, so none of this matters much. But for now, to keep
this passing the tests, we inline the bits of the old implementation
that the x86 implementation relied on. Also, since we now support a
slightly larger key space, via the union, some offsets had to be fixed
up.

Nonce calculation was folded in with the emit function, to take
advantage of 64x64 arithmetic. However, Adiantum appeared to rely on no
nonce handling in emit, so this path was conditionalized. We also
introduced a new struct, poly1305_core_key, to represent the precise
amount of space that particular implementation uses.

Testing with kbench9000, depending on the CPU, the update function for
the 32x32 version has been improved by 4%-7%, and for the 64x64 by
19%-30%. The 32x32 gains are small, but I think there's great value in
having a parallel implementation to the 64x64 one so that the two can be
compared side-by-side as nice stand-alone units.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
(cherry picked from commit 1c08a104360f3e18f4ee6346c21cc3923efb952e)
Bug: 152722841
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@google.com>
Change-Id: Ie53f7e47335863df3d82dbc268c6d8323ae5f559
2020-10-25 11:47:54 +01:00
Ard Biesheuvel
4afb116cc1 UPSTREAM: crypto: poly1305 - move core routines into a separate library
Move the core Poly1305 routines shared between the generic Poly1305
shash driver and the Adiantum and NHPoly1305 drivers into a separate
library so that using just this pieces does not pull in the crypto
API pieces of the generic Poly1305 routine.

In a subsequent patch, we will augment this generic library with
init/update/final routines so that Poyl1305 algorithm can be used
directly without the need for using the crypto API's shash abstraction.

Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
(cherry picked from commit 48ea8c6ebc96bc0990e12ee1c43d0832c23576bb)
Bug: 152722841
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@google.com>
Change-Id: I1d1ebae722acdb3a908822b8a5b126689e2147c3
2020-10-24 14:43:40 +02:00
Eric Biggers
7ae6788c68 UPSTREAM: crypto: adiantum - initialize crypto_spawn::inst
crypto_grab_*() doesn't set crypto_spawn::inst, so templates must set it
beforehand.  Otherwise it will be left NULL, which causes a crash in
certain cases where algorithms are dynamically loaded/unloaded.  E.g.
with CONFIG_CRYPTO_CHACHA20_X86_64=m, the following caused a crash:

    insmod chacha-x86_64.ko
    python -c 'import socket; socket.socket(socket.AF_ALG, 5, 0).bind(("skcipher", "adiantum(xchacha12,aes)"))'
    rmmod chacha-x86_64.ko
    python -c 'import socket; socket.socket(socket.AF_ALG, 5, 0).bind(("skcipher", "adiantum(xchacha12,aes)"))'

Fixes: 059c2a4d8e16 ("crypto: adiantum - add Adiantum support")
Signed-off-by: Eric Biggers <ebiggers@google.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
(cherry picked from commit 6db43410179bc40419a9859ebb333f178a49829d)
Test: Adiantum self-tests
Change-Id: I248548c979b0ee9e63a35f8ae779741bb5967b6e
2019-01-18 12:36:04 -08:00
Eric Biggers
ce3045a60d UPSTREAM: crypto: adiantum - fix leaking reference to hash algorithm
crypto_alg_mod_lookup() takes a reference to the hash algorithm but
crypto_init_shash_spawn() doesn't take ownership of it, hence the
reference needs to be dropped in adiantum_create().

Fixes: 059c2a4d8e16 ("crypto: adiantum - add Adiantum support")
Signed-off-by: Eric Biggers <ebiggers@google.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
(cherry picked from commit 00c9fe37a7f27a306bcaa5737f0787fe139f8aba)
Test: Adiantum self-tests
Change-Id: Ic609144bc3c72cc2c4ccbbaf450168193f3df7db
2019-01-18 12:36:01 -08:00
Eric Biggers
188d82f4cc UPSTREAM: crypto: adiantum - adjust some comments to match latest paper
The 2018-11-28 revision of the Adiantum paper has revised some notation:

- 'M' was replaced with 'L' (meaning "Left", for the left-hand part of
  the message) in the definition of Adiantum hashing, to avoid confusion
  with the full message
- ε-almost-∆-universal is now abbreviated as ε-∆U instead of εA∆U
- "block" is now used only to mean block cipher and Poly1305 blocks

Also, Adiantum hashing was moved from the appendix to the main paper.

To avoid confusion, update relevant comments in the code to match.

Signed-off-by: Eric Biggers <ebiggers@google.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
(cherry picked from commit c6018e1a00b5c70610cdfb3650cc5622c917ed17)
Test: Adiantum self-tests
Change-Id: Idd371e46408a449f7ff2ba77af2d4414979aadbf
2019-01-18 12:35:59 -08:00
Eric Biggers
8a962db7eb UPSTREAM: crypto: adiantum - propagate CRYPTO_ALG_ASYNC flag to instance
If the stream cipher implementation is asynchronous, then the Adiantum
instance must be flagged as asynchronous as well.  Otherwise someone
asking for a synchronous algorithm can get an asynchronous algorithm.

There are no asynchronous xchacha12 or xchacha20 implementations yet
which makes this largely a theoretical issue, but it should be fixed.

Fixes: 059c2a4d8e16 ("crypto: adiantum - add Adiantum support")
Signed-off-by: Eric Biggers <ebiggers@google.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
(cherry picked from commit b299362ee48db8eab34208302ee9730ff9d6091c)
Test: Adiantum self-tests
Change-Id: Ic7207e4036a0f03fba81375ffe36f511af2eb08c
2019-01-18 12:35:47 -08:00
Eric Biggers
f467c4ad23 BACKPORT, FROMGIT: crypto: adiantum - add Adiantum support
Add support for the Adiantum encryption mode.  Adiantum was designed by
Paul Crowley and is specified by our paper:

    Adiantum: length-preserving encryption for entry-level processors
    (https://eprint.iacr.org/2018/720.pdf)

See our paper for full details; this patch only provides an overview.

Adiantum is a tweakable, length-preserving encryption mode designed for
fast and secure disk encryption, especially on CPUs without dedicated
crypto instructions.  Adiantum encrypts each sector using the XChaCha12
stream cipher, two passes of an ε-almost-∆-universal (εA∆U) hash
function, and an invocation of the AES-256 block cipher on a single
16-byte block.  On CPUs without AES instructions, Adiantum is much
faster than AES-XTS; for example, on ARM Cortex-A7, on 4096-byte sectors
Adiantum encryption is about 4 times faster than AES-256-XTS encryption,
and decryption about 5 times faster.

Adiantum is a specialization of the more general HBSH construction.  Our
earlier proposal, HPolyC, was also a HBSH specialization, but it used a
different εA∆U hash function, one based on Poly1305 only.  Adiantum's
εA∆U hash function, which is based primarily on the "NH" hash function
like that used in UMAC (RFC4418), is about twice as fast as HPolyC's;
consequently, Adiantum is about 20% faster than HPolyC.

This speed comes with no loss of security: Adiantum is provably just as
secure as HPolyC, in fact slightly *more* secure.  Like HPolyC,
Adiantum's security is reducible to that of XChaCha12 and AES-256,
subject to a security bound.  XChaCha12 itself has a security reduction
to ChaCha12.  Therefore, one need not "trust" Adiantum; one need only
trust ChaCha12 and AES-256.  Note that the εA∆U hash function is only
used for its proven combinatorical properties so cannot be "broken".

Adiantum is also a true wide-block encryption mode, so flipping any
plaintext bit in the sector scrambles the entire ciphertext, and vice
versa.  No other such mode is available in the kernel currently; doing
the same with XTS scrambles only 16 bytes.  Adiantum also supports
arbitrary-length tweaks and naturally supports any length input >= 16
bytes without needing "ciphertext stealing".

For the stream cipher, Adiantum uses XChaCha12 rather than XChaCha20 in
order to make encryption feasible on the widest range of devices.
Although the 20-round variant is quite popular, the best known attacks
on ChaCha are on only 7 rounds, so ChaCha12 still has a substantial
security margin; in fact, larger than AES-256's.  12-round Salsa20 is
also the eSTREAM recommendation.  For the block cipher, Adiantum uses
AES-256, despite it having a lower security margin than XChaCha12 and
needing table lookups, due to AES's extensive adoption and analysis
making it the obvious first choice.  Nevertheless, for flexibility this
patch also permits the "adiantum" template to be instantiated with
XChaCha20 and/or with an alternate block cipher.

We need Adiantum support in the kernel for use in dm-crypt and fscrypt,
where currently the only other suitable options are block cipher modes
such as AES-XTS.  A big problem with this is that many low-end mobile
devices (e.g. Android Go phones sold primarily in developing countries,
as well as some smartwatches) still have CPUs that lack AES
instructions, e.g. ARM Cortex-A7.  Sadly, AES-XTS encryption is much too
slow to be viable on these devices.  We did find that some "lightweight"
block ciphers are fast enough, but these suffer from problems such as
not having much cryptanalysis or being too controversial.

The ChaCha stream cipher has excellent performance but is insecure to
use directly for disk encryption, since each sector's IV is reused each
time it is overwritten.  Even restricting the threat model to offline
attacks only isn't enough, since modern flash storage devices don't
guarantee that "overwrites" are really overwrites, due to wear-leveling.
Adiantum avoids this problem by constructing a
"tweakable super-pseudorandom permutation"; this is the strongest
possible security model for length-preserving encryption.

Of course, storing random nonces along with the ciphertext would be the
ideal solution.  But doing that with existing hardware and filesystems
runs into major practical problems; in most cases it would require data
journaling (like dm-integrity) which severely degrades performance.
Thus, for now length-preserving encryption is still needed.

Signed-off-by: Eric Biggers <ebiggers@google.com>
Reviewed-by: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

(cherry picked from commit 059c2a4d8e164dccc3078e49e7f286023b019a98
 https://git.kernel.org/pub/scm/linux/kernel/git/herbert/cryptodev-2.6.git master)

Conflicts:
	crypto/tcrypt.c

Bug: 112008522

Test: Among other things, I ran the relevant crypto self-tests:

  1.) Build kernel with CONFIG_CRYPTO_MANAGER_DISABLE_TESTS *unset*, and
      all relevant crypto algorithms built-in, including:
         CONFIG_CRYPTO_ADIANTUM=y
         CONFIG_CRYPTO_CHACHA20=y
         CONFIG_CRYPTO_CHACHA20_NEON=y
         CONFIG_CRYPTO_NHPOLY1305=y
         CONFIG_CRYPTO_NHPOLY1305_NEON=y
         CONFIG_CRYPTO_POLY1305=y
         CONFIG_CRYPTO_AES=y
         CONFIG_CRYPTO_AES_ARM=y
  2.) Boot and check dmesg for test failures.
  3.) Instantiate "adiantum(xchacha12,aes)" and
      "adiantum(xchacha20,aes)" to trigger them to be tested.  There are
      many ways to do this, but one way is to create a dm-crypt target
      that uses them, e.g.

          key=$(hexdump -n 32 -e '16/4 "%08X" 1 "\n"' /dev/urandom)
          dmsetup create crypt --table "0 $((1<<17)) crypt xchacha12,aes-adiantum-plain64 $key 0 /dev/vdc 0"
          dmsetup remove crypt
          dmsetup create crypt --table "0 $((1<<17)) crypt xchacha20,aes-adiantum-plain64 $key 0 /dev/vdc 0"
          dmsetup remove crypt
   4.) Check dmesg for test failures again.
   5.) Do 1-4 on both x86_64 (for basic testing) and on arm32 (for
   testing the ARM32-specific implementations).  I did the arm32 kernel
   testing on Raspberry Pi 2, which is a BCM2836-based device that can
   run the upstream and Android common kernels.

   The same ARM32 assembly files for ChaCha, NHPoly1305, and AES are
   also included in the userspace Adiantum benchmark suite at
   https://github.com/google/adiantum, where they have undergone
   additional correctness testing.

Change-Id: Ic61c13b53facfd2173065be715a7ee5f3af8760b
Signed-off-by: Eric Biggers <ebiggers@google.com>
2018-12-05 09:48:15 -08:00