crypto: Speck support

Add an ARM NEON-accelerated implementation of Speck-XTS. It operates on 128-byte chunks at a time, i.e. 8 blocks for Speck128 or 16 blocks for Speck64. Each 128-byte chunk goes through XTS preprocessing, then is encrypted/decrypted (doing one cipher round for all the blocks, then the next round, etc.), then goes through XTS postprocessing.

The performance depends on the processor but can be about 3 times faster than the generic code. For example, on an ARMv7 processor we observe the following performance with Speck128/256-XTS:

    xts-speck128-neon:     Encryption 107.9 MB/s, Decryption 108.1 MB/s
    xts(speck128-generic): Encryption  32.1 MB/s, Decryption  36.6 MB/s

In comparison to AES-256-XTS without the Cryptography Extensions:

    xts-aes-neonbs:        Encryption  41.2 MB/s, Decryption  36.7 MB/s
    xts(aes-asm):          Encryption  31.7 MB/s, Decryption  30.8 MB/s
    xts(aes-generic):      Encryption  21.2 MB/s, Decryption  20.9 MB/s

Speck64/128-XTS is even faster:

    xts-speck64-neon:      Encryption 138.6 MB/s, Decryption 139.1 MB/s

Note that as with the generic code, only the Speck128 and Speck64 variants are supported. Also, for now only the XTS mode of operation is supported, to target the disk and file encryption use cases. The NEON code also only handles the portion of the data that is evenly divisible into 128-byte chunks, with any remainder handled by a C fallback. Of course, other modes of operation could be added later if needed, and/or the NEON code could be updated to handle other buffer sizes.

The XTS specification is only defined for AES which has a 128-bit block size, so for the GF(2^64) math needed for Speck64-XTS we use the reducing polynomial 'x^64 + x^4 + x^3 + x + 1' given by the original XEX paper. Of course, when possible users should use Speck128-XTS, but even that may be too slow on some processors; Speck64-XTS can be faster.

Signed-off-by Eric Biggers <[email protected]>

---
 arch/arm/crypto/Kconfig           |   6 +
 arch/arm/crypto/Makefile          |   2 +
 arch/arm/crypto/speck-neon-core.S | 432 ++++++++++++++++++++++++++++++++++++++
 arch/arm/crypto/speck-neon-glue.c | 290 +++++++++++++++++++++++++
 4 files changed, 730 insertions(+)
 create mode 100644 arch/arm/crypto/speck-neon-core.S
 create mode 100644 arch/arm/crypto/speck-neon-glue.c

arch/arm/crypto/Kconfig +6 -0

index b8e69fe282b8..925d1364727a 100644
@@ -121,4 +121,10 @@ config CRYPTO_CHACHA20_NEON
        select CRYPTO_BLKCIPHER
        select CRYPTO_CHACHA20
 
+config CRYPTO_SPECK_NEON
+       tristate "NEON accelerated Speck cipher algorithms"
+       depends on KERNEL_MODE_NEON
+       select CRYPTO_BLKCIPHER
+       select CRYPTO_SPECK
+
 endif

arch/arm/crypto/Makefile +2 -0

index 30ef8e291271..a758107c5525 100644
@@ -10,6 +10,7 @@ obj-$(CONFIG_CRYPTO_SHA1_ARM_NEON) += sha1-arm-neon.o
 obj-$(CONFIG_CRYPTO_SHA256_ARM) += sha256-arm.o
 obj-$(CONFIG_CRYPTO_SHA512_ARM) += sha512-arm.o
 obj-$(CONFIG_CRYPTO_CHACHA20_NEON) += chacha20-neon.o
+obj-$(CONFIG_CRYPTO_SPECK_NEON) += speck-neon.o
 
 ce-obj-$(CONFIG_CRYPTO_AES_ARM_CE) += aes-arm-ce.o
 ce-obj-$(CONFIG_CRYPTO_SHA1_ARM_CE) += sha1-arm-ce.o

@@ -53,6 +54,7 @@ ghash-arm-ce-y        := ghash-ce-core.o ghash-ce-glue.o
 crct10dif-arm-ce-y     := crct10dif-ce-core.o crct10dif-ce-glue.o
 crc32-arm-ce-y:= crc32-ce-core.o crc32-ce-glue.o
 chacha20-neon-y := chacha20-neon-core.o chacha20-neon-glue.o
+speck-neon-y := speck-neon-core.o speck-neon-glue.o
 
 quiet_cmd_perl = PERL    $@
       cmd_perl = $(PERL) $(<) > $(@)

arch/arm/crypto/speck-neon-core.S new file +432 -0

new file mode 100644
index 000000000000..3c1e203e53b9
@@ -0,0 +1,432 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * NEON-accelerated implementation of Speck128-XTS and Speck64-XTS
+ *
+ * Copyright (c) 2018 Google, Inc
+ *
+ * Author: Eric Biggers <[email protected]>
+ */
+
+#include <linux/linkage.h>
+
+       .text
+       .fpu            neon
+
+       // arguments
+       ROUND_KEYS      .req    r0      // const {u64,u32} *round_keys
+       NROUNDS         .req    r1      // int nrounds
+       DST             .req    r2      // void *dst
+       SRC             .req    r3      // const void *src
+       NBYTES          .req    r4      // unsigned int nbytes
+       TWEAK           .req    r5      // void *tweak
+
+       // registers which hold the data being encrypted/decrypted
+       X0              .req    q0
+       X0_L            .req    d0
+       X0_H            .req    d1
+       Y0              .req    q1
+       Y0_H            .req    d3
+       X1              .req    q2
+       X1_L            .req    d4
+       X1_H            .req    d5
+       Y1              .req    q3
+       Y1_H            .req    d7
+       X2              .req    q4
+       X2_L            .req    d8
+       X2_H            .req    d9
+       Y2              .req    q5
+       Y2_H            .req    d11
+       X3              .req    q6
+       X3_L            .req    d12
+       X3_H            .req    d13
+       Y3              .req    q7
+       Y3_H            .req    d15
+
+       // the round key, duplicated in all lanes
+       ROUND_KEY       .req    q8
+       ROUND_KEY_L     .req    d16
+       ROUND_KEY_H     .req    d17
+
+       // index vector for vtbl-based 8-bit rotates
+       ROTATE_TABLE    .req    d18
+
+       // multiplication table for updating XTS tweaks
+       GF128MUL_TABLE  .req    d19
+       GF64MUL_TABLE   .req    d19
+
+       // current XTS tweak value(s)
+       TWEAKV          .req    q10
+       TWEAKV_L        .req    d20
+       TWEAKV_H        .req    d21
+
+       TMP0            .req    q12
+       TMP0_L          .req    d24
+       TMP0_H          .req    d25
+       TMP1            .req    q13
+       TMP2            .req    q14
+       TMP3            .req    q15
+
+       .align          4
+.Lror64_8_table:
+       .byte           1, 2, 3, 4, 5, 6, 7, 0
+.Lror32_8_table:
+       .byte           1, 2, 3, 0, 5, 6, 7, 4
+.Lrol64_8_table:
+       .byte           7, 0, 1, 2, 3, 4, 5, 6
+.Lrol32_8_table:
+       .byte           3, 0, 1, 2, 7, 4, 5, 6
+.Lgf128mul_table:
+       .byte           0, 0x87
+       .fill           14
+.Lgf64mul_table:
+       .byte           0, 0x1b, (0x1b << 1), (0x1b << 1) ^ 0x1b
+       .fill           12
+
+/*
+ * _speck_round_128bytes() - Speck encryption round on 128 bytes at a time
+ *
+ * Do one Speck encryption round on the 128 bytes (8 blocks for Speck128, 16 for
+ * Speck64) stored in X0-X3 and Y0-Y3, using the round key stored in all lanes
+ * of ROUND_KEY.  'n' is the lane size: 64 for Speck128, or 32 for Speck64.
+ *
+ * The 8-bit rotates are implemented using vtbl instead of vshr + vsli because
+ * the vtbl approach is faster on some processors and the same speed on others.
+ */
+.macro _speck_round_128bytes   n
+
+       // x = ror(x, 8)
+       vtbl.8          X0_L, {X0_L}, ROTATE_TABLE
+       vtbl.8          X0_H, {X0_H}, ROTATE_TABLE
+       vtbl.8          X1_L, {X1_L}, ROTATE_TABLE
+       vtbl.8          X1_H, {X1_H}, ROTATE_TABLE
+       vtbl.8          X2_L, {X2_L}, ROTATE_TABLE
+       vtbl.8          X2_H, {X2_H}, ROTATE_TABLE
+       vtbl.8          X3_L, {X3_L}, ROTATE_TABLE
+       vtbl.8          X3_H, {X3_H}, ROTATE_TABLE
+
+       // x += y
+       vadd.u\n        X0, Y0
+       vadd.u\n        X1, Y1
+       vadd.u\n        X2, Y2
+       vadd.u\n        X3, Y3
+
+       // x ^= k
+       veor            X0, ROUND_KEY
+       veor            X1, ROUND_KEY
+       veor            X2, ROUND_KEY
+       veor            X3, ROUND_KEY
+
+       // y = rol(y, 3)
+       vshl.u\n        TMP0, Y0, #3
+       vshl.u\n        TMP1, Y1, #3
+       vshl.u\n        TMP2, Y2, #3
+       vshl.u\n        TMP3, Y3, #3
+       vsri.u\n        TMP0, Y0, #(\n - 3)
+       vsri.u\n        TMP1, Y1, #(\n - 3)
+       vsri.u\n        TMP2, Y2, #(\n - 3)
+       vsri.u\n        TMP3, Y3, #(\n - 3)
+
+       // y ^= x
+       veor            Y0, TMP0, X0
+       veor            Y1, TMP1, X1
+       veor            Y2, TMP2, X2
+       veor            Y3, TMP3, X3
+.endm
+
+/*
+ * _speck_unround_128bytes() - Speck decryption round on 128 bytes at a time
+ *
+ * This is the inverse of _speck_round_128bytes().
+ */
+.macro _speck_unround_128bytes n
+
+       // y ^= x
+       veor            TMP0, Y0, X0
+       veor            TMP1, Y1, X1
+       veor            TMP2, Y2, X2
+       veor            TMP3, Y3, X3
+
+       // y = ror(y, 3)
+       vshr.u\n        Y0, TMP0, #3
+       vshr.u\n        Y1, TMP1, #3
+       vshr.u\n        Y2, TMP2, #3
+       vshr.u\n        Y3, TMP3, #3
+       vsli.u\n        Y0, TMP0, #(\n - 3)
+       vsli.u\n        Y1, TMP1, #(\n - 3)
+       vsli.u\n        Y2, TMP2, #(\n - 3)
+       vsli.u\n        Y3, TMP3, #(\n - 3)
+
+       // x ^= k
+       veor            X0, ROUND_KEY
+       veor            X1, ROUND_KEY
+       veor            X2, ROUND_KEY
+       veor            X3, ROUND_KEY
+
+       // x -= y
+       vsub.u\n        X0, Y0
+       vsub.u\n        X1, Y1
+       vsub.u\n        X2, Y2
+       vsub.u\n        X3, Y3
+
+       // x = rol(x, 8);
+       vtbl.8          X0_L, {X0_L}, ROTATE_TABLE
+       vtbl.8          X0_H, {X0_H}, ROTATE_TABLE
+       vtbl.8          X1_L, {X1_L}, ROTATE_TABLE
+       vtbl.8          X1_H, {X1_H}, ROTATE_TABLE
+       vtbl.8          X2_L, {X2_L}, ROTATE_TABLE
+       vtbl.8          X2_H, {X2_H}, ROTATE_TABLE
+       vtbl.8          X3_L, {X3_L}, ROTATE_TABLE
+       vtbl.8          X3_H, {X3_H}, ROTATE_TABLE
+.endm
+
+.macro _xts128_precrypt_one    dst_reg, tweak_buf, tmp
+
+       // Load the next source block
+       vld1.8          {\dst_reg}, [SRC]!
+
+       // Save the current tweak in the tweak buffer
+       vst1.8          {TWEAKV}, [\tweak_buf:128]!
+
+       // XOR the next source block with the current tweak
+       veor            \dst_reg, TWEAKV
+
+       /*
+        * Calculate the next tweak by multiplying the current one by x,
+        * modulo p(x) = x^128 + x^7 + x^2 + x + 1.
+        */
+       vshr.u64        \tmp, TWEAKV, #63
+       vshl.u64        TWEAKV, #1
+       veor            TWEAKV_H, \tmp\()_L
+       vtbl.8          \tmp\()_H, {GF128MUL_TABLE}, \tmp\()_H
+       veor            TWEAKV_L, \tmp\()_H
+.endm
+
+.macro _xts64_precrypt_two     dst_reg, tweak_buf, tmp
+
+       // Load the next two source blocks
+       vld1.8          {\dst_reg}, [SRC]!
+
+       // Save the current two tweaks in the tweak buffer
+       vst1.8          {TWEAKV}, [\tweak_buf:128]!
+
+       // XOR the next two source blocks with the current two tweaks
+       veor            \dst_reg, TWEAKV
+
+       /*
+        * Calculate the next two tweaks by multiplying the current ones by x^2,
+        * modulo p(x) = x^64 + x^4 + x^3 + x + 1.
+        */
+       vshr.u64        \tmp, TWEAKV, #62
+       vshl.u64        TWEAKV, #2
+       vtbl.8          \tmp\()_L, {GF64MUL_TABLE}, \tmp\()_L
+       vtbl.8          \tmp\()_H, {GF64MUL_TABLE}, \tmp\()_H
+       veor            TWEAKV, \tmp
+.endm
+
+/*
+ * _speck_xts_crypt() - Speck-XTS encryption/decryption
+ *
+ * Encrypt or decrypt NBYTES bytes of data from the SRC buffer to the DST buffer
+ * using Speck-XTS, specifically the variant with a block size of '2n' and round
+ * count given by NROUNDS.  The expanded round keys are given in ROUND_KEYS, and
+ * the current XTS tweak value is given in TWEAK.  It's assumed that NBYTES is a
+ * nonzero multiple of 128.
+ */
+.macro _speck_xts_crypt        n, decrypting
+       push            {r4-r7}
+       mov             r7, sp
+
+       /*
+        * The first four parameters were passed in registers r0-r3.  Load the
+        * additional parameters, which were passed on the stack.
+        */
+       ldr             NBYTES, [sp, #16]
+       ldr             TWEAK, [sp, #20]
+
+       /*
+        * If decrypting, modify the ROUND_KEYS parameter to point to the last
+        * round key rather than the first, since for decryption the round keys
+        * are used in reverse order.
+        */
+.if \decrypting
+.if \n == 64
+       add             ROUND_KEYS, ROUND_KEYS, NROUNDS, lsl #3
+       sub             ROUND_KEYS, #8
+.else
+       add             ROUND_KEYS, ROUND_KEYS, NROUNDS, lsl #2
+       sub             ROUND_KEYS, #4
+.endif
+.endif
+
+       // Load the index vector for vtbl-based 8-bit rotates
+.if \decrypting
+       ldr             r12, =.Lrol\n\()_8_table
+.else
+       ldr             r12, =.Lror\n\()_8_table
+.endif
+       vld1.8          {ROTATE_TABLE}, [r12:64]
+
+       // One-time XTS preparation
+
+       /*
+        * Allocate stack space to store 128 bytes worth of tweaks.  For
+        * performance, this space is aligned to a 16-byte boundary so that we
+        * can use the load/store instructions that declare 16-byte alignment.
+        */
+       sub             sp, #128
+       bic             sp, #0xf
+
+.if \n == 64
+       // Load first tweak
+       vld1.8          {TWEAKV}, [TWEAK]
+
+       // Load GF(2^128) multiplication table
+       ldr             r12, =.Lgf128mul_table
+       vld1.8          {GF128MUL_TABLE}, [r12:64]
+.else
+       // Load first tweak
+       vld1.8          {TWEAKV_L}, [TWEAK]
+
+       // Load GF(2^64) multiplication table
+       ldr             r12, =.Lgf64mul_table
+       vld1.8          {GF64MUL_TABLE}, [r12:64]
+
+       // Calculate second tweak, packing it together with the first
+       vshr.u64        TMP0_L, TWEAKV_L, #63
+       vtbl.u8         TMP0_L, {GF64MUL_TABLE}, TMP0_L
+       vshl.u64        TWEAKV_H, TWEAKV_L, #1
+       veor            TWEAKV_H, TMP0_L
+.endif
+
+.Lnext_128bytes_\@:
+
+       /*
+        * Load the source blocks into {X,Y}[0-3], XOR them with their XTS tweak
+        * values, and save the tweaks on the stack for later.  Then
+        * de-interleave the 'x' and 'y' elements of each block, i.e. make it so
+        * that the X[0-3] registers contain only the second halves of blocks,
+        * and the Y[0-3] registers contain only the first halves of blocks.
+        * (Speck uses the order (y, x) rather than the more intuitive (x, y).)
+        */
+       mov             r12, sp
+.if \n == 64
+       _xts128_precrypt_one    X0, r12, TMP0
+       _xts128_precrypt_one    Y0, r12, TMP0
+       _xts128_precrypt_one    X1, r12, TMP0
+       _xts128_precrypt_one    Y1, r12, TMP0
+       _xts128_precrypt_one    X2, r12, TMP0
+       _xts128_precrypt_one    Y2, r12, TMP0
+       _xts128_precrypt_one    X3, r12, TMP0
+       _xts128_precrypt_one    Y3, r12, TMP0
+       vswp            X0_L, Y0_H
+       vswp            X1_L, Y1_H
+       vswp            X2_L, Y2_H
+       vswp            X3_L, Y3_H
+.else
+       _xts64_precrypt_two     X0, r12, TMP0
+       _xts64_precrypt_two     Y0, r12, TMP0
+       _xts64_precrypt_two     X1, r12, TMP0
+       _xts64_precrypt_two     Y1, r12, TMP0
+       _xts64_precrypt_two     X2, r12, TMP0
+       _xts64_precrypt_two     Y2, r12, TMP0
+       _xts64_precrypt_two     X3, r12, TMP0
+       _xts64_precrypt_two     Y3, r12, TMP0
+       vuzp.32         Y0, X0
+       vuzp.32         Y1, X1
+       vuzp.32         Y2, X2
+       vuzp.32         Y3, X3
+.endif
+
+       // Do the cipher rounds
+
+       mov             r12, ROUND_KEYS
+       mov             r6, NROUNDS
+
+.Lnext_round_\@:
+.if \decrypting
+.if \n == 64
+       vld1.64         ROUND_KEY_L, [r12]
+       sub             r12, #8
+       vmov            ROUND_KEY_H, ROUND_KEY_L
+.else
+       vld1.32         {ROUND_KEY_L[],ROUND_KEY_H[]}, [r12]
+       sub             r12, #4
+.endif
+       _speck_unround_128bytes \n
+.else
+.if \n == 64
+       vld1.64         ROUND_KEY_L, [r12]!
+       vmov            ROUND_KEY_H, ROUND_KEY_L
+.else
+       vld1.32         {ROUND_KEY_L[],ROUND_KEY_H[]}, [r12]!
+.endif
+       _speck_round_128bytes   \n
+.endif
+       subs            r6, r6, #1
+       bne             .Lnext_round_\@
+
+       // Re-interleave the 'x' and 'y' elements of each block
+.if \n == 64
+       vswp            X0_L, Y0_H
+       vswp            X1_L, Y1_H
+       vswp            X2_L, Y2_H
+       vswp            X3_L, Y3_H
+.else
+       vzip.32         Y0, X0
+       vzip.32         Y1, X1
+       vzip.32         Y2, X2
+       vzip.32         Y3, X3
+.endif
+
+       // XOR the encrypted/decrypted blocks with the tweaks we saved earlier
+       mov             r12, sp
+       vld1.8          {TMP0, TMP1}, [r12:128]!
+       vld1.8          {TMP2, TMP3}, [r12:128]!
+       veor            X0, TMP0
+       veor            Y0, TMP1
+       veor            X1, TMP2
+       veor            Y1, TMP3
+       vld1.8          {TMP0, TMP1}, [r12:128]!
+       vld1.8          {TMP2, TMP3}, [r12:128]!
+       veor            X2, TMP0
+       veor            Y2, TMP1
+       veor            X3, TMP2
+       veor            Y3, TMP3
+
+       // Store the ciphertext in the destination buffer
+       vst1.8          {X0, Y0}, [DST]!
+       vst1.8          {X1, Y1}, [DST]!
+       vst1.8          {X2, Y2}, [DST]!
+       vst1.8          {X3, Y3}, [DST]!
+
+       // Continue if there are more 128-byte chunks remaining, else return
+       subs            NBYTES, #128
+       bne             .Lnext_128bytes_\@
+
+       // Store the next tweak
+.if \n == 64
+       vst1.8          {TWEAKV}, [TWEAK]
+.else
+       vst1.8          {TWEAKV_L}, [TWEAK]
+.endif
+
+       mov             sp, r7
+       pop             {r4-r7}
+       bx              lr
+.endm
+
+ENTRY(speck128_xts_encrypt_neon)
+       _speck_xts_crypt        n=64, decrypting=0
+ENDPROC(speck128_xts_encrypt_neon)
+
+ENTRY(speck128_xts_decrypt_neon)
+       _speck_xts_crypt        n=64, decrypting=1
+ENDPROC(speck128_xts_decrypt_neon)
+
+ENTRY(speck64_xts_encrypt_neon)
+       _speck_xts_crypt        n=32, decrypting=0
+ENDPROC(speck64_xts_encrypt_neon)
+
+ENTRY(speck64_xts_decrypt_neon)
+       _speck_xts_crypt        n=32, decrypting=1
+ENDPROC(speck64_xts_decrypt_neon)

arch/arm/crypto/speck-neon-glue.c new file +290 -1

new file mode 100644
index 000000000000..3987dd6e063e
@@ -0,0 +1,290 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * NEON-accelerated implementation of Speck128-XTS and Speck64-XTS
+ *
+ * Copyright (c) 2018 Google, Inc
+ *
+ * Note: the NIST recommendation for XTS only specifies a 128-bit block size,
+ * but a 64-bit version (needed for Speck64) is fairly straightforward; the math
+ * is just done in GF(2^64) instead of GF(2^128), with the reducing polynomial
+ * x^64 + x^4 + x^3 + x + 1 from the original XEX paper (Rogaway, 2004:
+ * "Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes
+ * OCB and PMAC"), represented as 0x1B.
+ */
+
+#include <asm/hwcap.h>
+#include <asm/neon.h>
+#include <asm/simd.h>
+#include <crypto/algapi.h>
+#include <crypto/gf128mul.h>
+#include <crypto/internal/skcipher.h>
+#include <crypto/speck.h>
+#include <crypto/xts.h>
+#include <linux/kernel.h>
+#include <linux/module.h>
+
+/* The assembly functions only handle multiples of 128 bytes */
+#define SPECK_NEON_CHUNK_SIZE  128
+
+/* Speck128 */
+
+struct speck128_xts_tfm_ctx {
+       struct speck128_tfm_ctx main_key;
+       struct speck128_tfm_ctx tweak_key;
+};
+
+asmlinkage void speck128_xts_encrypt_neon(const u64 *round_keys, int nrounds,
+                                         void *dst, const void *src,
+                                         unsigned int nbytes, void *tweak);
+
+asmlinkage void speck128_xts_decrypt_neon(const u64 *round_keys, int nrounds,
+                                         void *dst, const void *src,
+                                         unsigned int nbytes, void *tweak);
+
+typedef void (*speck128_crypt_one_t)(const struct speck128_tfm_ctx *,
+                                    u8 *, const u8 *);
+typedef void (*speck128_xts_crypt_many_t)(const u64 *, int, void *,
+                                         const void *, unsigned int, void *);
+
+
+static __always_inline int
+__speck128_xts_crypt(struct skcipher_request *req,
+                    speck128_crypt_one_t crypt_one,
+                    speck128_xts_crypt_many_t crypt_many)
+{
+       struct crypto_skcipher *tfm = crypto_skcipher_reqtfm(req);
+       const struct speck128_xts_tfm_ctx *ctx = crypto_skcipher_ctx(tfm);
+       struct skcipher_walk walk;
+       le128 tweak;
+       int err;
+
+       err = skcipher_walk_virt(&walk, req, true);
+
+       crypto_speck128_encrypt(&ctx->tweak_key, (u8 *)&tweak, walk.iv);
+
+       while (walk.nbytes > 0) {
+               unsigned int nbytes = walk.nbytes;
+               u8 *dst = walk.dst.virt.addr;
+               const u8 *src = walk.src.virt.addr;
+
+               if (nbytes >= SPECK_NEON_CHUNK_SIZE && may_use_simd()) {
+                       unsigned int count;
+
+                       count = round_down(nbytes, SPECK_NEON_CHUNK_SIZE);
+                       kernel_neon_begin();
+                       (*crypt_many)(ctx->main_key.round_keys,
+                                     ctx->main_key.nrounds,
+                                     dst, src, count, &tweak);
+                       kernel_neon_end();
+                       dst += count;
+                       src += count;
+                       nbytes -= count;
+               }
+
+               /* Handle any remainder with generic code */
+               while (nbytes >= sizeof(le128)) {
+                       le128_xor((le128 *)dst, (const le128 *)src, &tweak);
+                       (*crypt_one)(&ctx->main_key, dst, dst);
+                       le128_xor((le128 *)dst, (const le128 *)dst, &tweak);
+                       gf128mul_x_ble(&tweak, &tweak);
+
+                       dst += sizeof(le128);
+                       src += sizeof(le128);
+                       nbytes -= sizeof(le128);
+               }
+               err = skcipher_walk_done(&walk, nbytes);
+       }
+
+       return err;
+}
+
+static int speck128_xts_encrypt(struct skcipher_request *req)
+{
+       return __speck128_xts_crypt(req, crypto_speck128_encrypt,
+                                   speck128_xts_encrypt_neon);
+
+}
+
+static int speck128_xts_decrypt(struct skcipher_request *req)
+{
+       return __speck128_xts_crypt(req, crypto_speck128_decrypt,
+                                   speck128_xts_decrypt_neon);
+}
+
+static int speck128_xts_setkey(struct crypto_skcipher *tfm, const u8 *key,
+                              unsigned int keylen)
+{
+       struct speck128_xts_tfm_ctx *ctx = crypto_skcipher_ctx(tfm);
+       int err;
+
+       err = xts_verify_key(tfm, key, keylen);
+       if (err)
+               return err;
+
+       keylen /= 2;
+
+       err = crypto_speck128_setkey(&ctx->main_key, key, keylen);
+       if (err)
+               return err;
+
+       return crypto_speck128_setkey(&ctx->tweak_key, key + keylen, keylen);
+}
+
+/* Speck64 */
+
+struct speck64_xts_tfm_ctx {
+       struct speck64_tfm_ctx main_key;
+       struct speck64_tfm_ctx tweak_key;
+};
+
+asmlinkage void speck64_xts_encrypt_neon(const u32 *round_keys, int nrounds,
+                                        void *dst, const void *src,
+                                        unsigned int nbytes, void *tweak);
+
+asmlinkage void speck64_xts_decrypt_neon(const u32 *round_keys, int nrounds,
+                                        void *dst, const void *src,
+                                        unsigned int nbytes, void *tweak);
+
+typedef void (*speck64_crypt_one_t)(const struct speck64_tfm_ctx *,
+                                   u8 *, const u8 *);
+typedef void (*speck64_xts_crypt_many_t)(const u32 *, int, void *,
+                                        const void *, unsigned int, void *);
+
+static __always_inline int
+__speck64_xts_crypt(struct skcipher_request *req, speck64_crypt_one_t crypt_one,
+                   speck64_xts_crypt_many_t crypt_many)
+{
+       struct crypto_skcipher *tfm = crypto_skcipher_reqtfm(req);
+       const struct speck64_xts_tfm_ctx *ctx = crypto_skcipher_ctx(tfm);
+       struct skcipher_walk walk;
+       u64 tweak;
+       int err;
+
+       err = skcipher_walk_virt(&walk, req, true);
+
+       crypto_speck64_encrypt(&ctx->tweak_key, (u8 *)&tweak, walk.iv);
+
+       while (walk.nbytes > 0) {
+               unsigned int nbytes = walk.nbytes;
+               u8 *dst = walk.dst.virt.addr;
+               const u8 *src = walk.src.virt.addr;
+
+               if (nbytes >= SPECK_NEON_CHUNK_SIZE && may_use_simd()) {
+                       unsigned int count;
+
+                       count = round_down(nbytes, SPECK_NEON_CHUNK_SIZE);
+                       kernel_neon_begin();
+                       (*crypt_many)(ctx->main_key.round_keys,
+                                     ctx->main_key.nrounds,
+                                     dst, src, count, &tweak);
+                       kernel_neon_end();
+                       dst += count;
+                       src += count;
+                       nbytes -= count;
+               }
+
+               /* Handle any remainder with generic code */
+               while (nbytes >= sizeof(u64)) {
+                       *(u64 *)dst = *(u64 *)src ^ tweak;
+                       (*crypt_one)(&ctx->main_key, dst, dst);
+                       *(u64 *)dst ^= tweak;
+                       tweak = (tweak << 1) ^
+                               ((tweak & (1ULL << 63)) ? 0x1B : 0);
+
+                       dst += sizeof(u64);
+                       src += sizeof(u64);
+                       nbytes -= sizeof(u64);
+               }
+               err = skcipher_walk_done(&walk, nbytes);
+       }
+
+       return err;
+}
+
+static int speck64_xts_encrypt(struct skcipher_request *req)
+{
+       return __speck64_xts_crypt(req, crypto_speck64_encrypt,
+                                  speck64_xts_encrypt_neon);
+}
+
+static int speck64_xts_decrypt(struct skcipher_request *req)
+{
+       return __speck64_xts_crypt(req, crypto_speck64_decrypt,
+                                  speck64_xts_decrypt_neon);
+}
+
+static int speck64_xts_setkey(struct crypto_skcipher *tfm, const u8 *key,
+                             unsigned int keylen)
+{
+       struct speck64_xts_tfm_ctx *ctx = crypto_skcipher_ctx(tfm);
+       int err;
+
+       err = xts_verify_key(tfm, key, keylen);
+       if (err)
+               return err;
+
+       keylen /= 2;
+
+       err = crypto_speck64_setkey(&ctx->main_key, key, keylen);
+       if (err)
+               return err;
+
+       return crypto_speck64_setkey(&ctx->tweak_key, key + keylen, keylen);
+}
+
+static struct skcipher_alg speck_algs[] = {
+       {
+               .base.cra_name          = "xts(speck128)",
+               .base.cra_driver_name   = "xts-speck128-neon",
+               .base.cra_priority      = 300,
+               .base.cra_blocksize     = SPECK128_BLOCK_SIZE,
+               .base.cra_ctxsize       = sizeof(struct speck128_xts_tfm_ctx),
+               .base.cra_alignmask     = 7,
+               .base.cra_module        = THIS_MODULE,
+               .min_keysize            = 2 * SPECK128_128_KEY_SIZE,
+               .max_keysize            = 2 * SPECK128_256_KEY_SIZE,
+               .ivsize                 = SPECK128_BLOCK_SIZE,
+               .walksize               = SPECK_NEON_CHUNK_SIZE,
+               .setkey                 = speck128_xts_setkey,
+               .encrypt                = speck128_xts_encrypt,
+               .decrypt                = speck128_xts_decrypt,
+       }, {
+               .base.cra_name          = "xts(speck64)",
+               .base.cra_driver_name   = "xts-speck64-neon",
+               .base.cra_priority      = 300,
+               .base.cra_blocksize     = SPECK64_BLOCK_SIZE,
+               .base.cra_ctxsize       = sizeof(struct speck64_xts_tfm_ctx),
+               .base.cra_alignmask     = 7,
+               .base.cra_module        = THIS_MODULE,
+               .min_keysize            = 2 * SPECK64_96_KEY_SIZE,
+               .max_keysize            = 2 * SPECK64_128_KEY_SIZE,
+               .ivsize                 = SPECK64_BLOCK_SIZE,
+               .walksize               = SPECK_NEON_CHUNK_SIZE,
+               .setkey                 = speck64_xts_setkey,
+               .encrypt                = speck64_xts_encrypt,
+               .decrypt                = speck64_xts_decrypt,
+       }
+};
+
+static int __init speck_neon_module_init(void)
+{
+       if (!(elf_hwcap & HWCAP_NEON))
+               return -ENODEV;
+       return crypto_register_skciphers(speck_algs, ARRAY_SIZE(speck_algs));
+}
+
+static void __exit speck_neon_module_exit(void)
+{
+       crypto_unregister_skciphers(speck_algs, ARRAY_SIZE(speck_algs));
+}
+
+module_init(speck_neon_module_init);
+module_exit(speck_neon_module_exit);
+
+MODULE_DESCRIPTION("Speck block cipher (NEON-accelerated)");
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Eric Biggers <[email protected]>");
+MODULE_ALIAS_CRYPTO("xts(speck128)");
+MODULE_ALIAS_CRYPTO("xts-speck128-neon");
+MODULE_ALIAS_CRYPTO("xts(speck64)");
+MODULE_ALIAS_CRYPTO("xts-speck64-neon");
--

2.16.0.rc1.238.g530d649a79-goog

Hi Eric,

Quoted 31 lines · Eric Biggers

Add an ARM NEON-accelerated implementation of Speck-XTS. It operates on 128-byte chunks at a time, i.e. 8 blocks for Speck128 or 16 blocks for Speck64. Each 128-byte chunk goes through XTS preprocessing, then is encrypted/decrypted (doing one cipher round for all the blocks, then the next round, etc.), then goes through XTS postprocessing.

The performance depends on the processor but can be about 3 times faster than the generic code. For example, on an ARMv7 processor we observe the following performance with Speck128/256-XTS:

    xts-speck128-neon:     Encryption 107.9 MB/s, Decryption 108.1 MB/s
    xts(speck128-generic): Encryption  32.1 MB/s, Decryption  36.6 MB/s

In comparison to AES-256-XTS without the Cryptography Extensions:

    xts-aes-neonbs:        Encryption  41.2 MB/s, Decryption  36.7 MB/s
    xts(aes-asm):          Encryption  31.7 MB/s, Decryption  30.8 MB/s
    xts(aes-generic):      Encryption  21.2 MB/s, Decryption  20.9 MB/s

Speck64/128-XTS is even faster:

    xts-speck64-neon:      Encryption 138.6 MB/s, Decryption 139.1 MB/s

Note that as with the generic code, only the Speck128 and Speck64 variants are supported. Also, for now only the XTS mode of operation is supported, to target the disk and file encryption use cases. The NEON code also only handles the portion of the data that is evenly divisible into 128-byte chunks, with any remainder handled by a C fallback. Of course, other modes of operation could be added later if needed, and/or the NEON code could be updated to handle other buffer sizes.

Quoted 6 lines

The XTS specification is only defined for AES which has a 128-bit block size, so for the GF(2^64) math needed for Speck64-XTS we use the reducing polynomial 'x^64 + x^4 + x^3 + x + 1' given by the original XEX paper. Of course, when possible users should use Speck128-XTS, but even that may be too slow on some processors; Speck64-XTS can be faster.

I think this is excellent work. Speck seems an appropriate solution to this problem, and I'm glad we are not ending up with a stream cipher for block encryption.

Also, I think an arm64 port would be nice. I may take a stab at this if nobody else beats me to it.

I did run into an issue with this code though: On big-endian, I get

[    0.272381] alg: skcipher: Test 1 failed (invalid result) on
encryption for xts-speck64-neon
[    0.276151] 00000000: 84 af 54 07 19 d4 7c a6 9c 8a ac f6 c2 14 04 d8
[    0.278541] 00000010: 7f 18 6c 43 56 ed 0b b3 92 21 a2 d9 17 59 e4 3b

so there may be a byte order corner case you missed in the rewrite (or the issue existed before, as I did not test your v1)

Hi Ard,

Quoted 45 lines · Ard Biesheuvel

Hi Eric,

Quoted 31 lines · Eric Biggers

Add an ARM NEON-accelerated implementation of Speck-XTS. It operates on 128-byte chunks at a time, i.e. 8 blocks for Speck128 or 16 blocks for Speck64. Each 128-byte chunk goes through XTS preprocessing, then is encrypted/decrypted (doing one cipher round for all the blocks, then the next round, etc.), then goes through XTS postprocessing.

The performance depends on the processor but can be about 3 times faster than the generic code. For example, on an ARMv7 processor we observe the following performance with Speck128/256-XTS:

    xts-speck128-neon:     Encryption 107.9 MB/s, Decryption 108.1 MB/s
    xts(speck128-generic): Encryption  32.1 MB/s, Decryption  36.6 MB/s

In comparison to AES-256-XTS without the Cryptography Extensions:

    xts-aes-neonbs:        Encryption  41.2 MB/s, Decryption  36.7 MB/s
    xts(aes-asm):          Encryption  31.7 MB/s, Decryption  30.8 MB/s
    xts(aes-generic):      Encryption  21.2 MB/s, Decryption  20.9 MB/s

Speck64/128-XTS is even faster:

    xts-speck64-neon:      Encryption 138.6 MB/s, Decryption 139.1 MB/s

Note that as with the generic code, only the Speck128 and Speck64 variants are supported. Also, for now only the XTS mode of operation is supported, to target the disk and file encryption use cases. The NEON code also only handles the portion of the data that is evenly divisible into 128-byte chunks, with any remainder handled by a C fallback. Of course, other modes of operation could be added later if needed, and/or the NEON code could be updated to handle other buffer sizes.

Quoted 6 lines

The XTS specification is only defined for AES which has a 128-bit block size, so for the GF(2^64) math needed for Speck64-XTS we use the reducing polynomial 'x^64 + x^4 + x^3 + x + 1' given by the original XEX paper. Of course, when possible users should use Speck128-XTS, but even that may be too slow on some processors; Speck64-XTS can be faster.

I think this is excellent work. Speck seems an appropriate solution to this problem, and I'm glad we are not ending up with a stream cipher for block encryption.

Quoted 2 lines

Also, I think an arm64 port would be nice. I may take a stab at this if nobody else beats me to it.

We don't really want to encourage people to use Speck over AES with the Cryptography Extensions, so that's why I didn't include an arm64 port. That being said, I suppose we can't stop people from adding an arm64 port if they really do prefer Speck, or maybe for use on arm64 CPUs that don't have the Cryptography Extensions (though I thought that almost all do).

Quoted 8 lines

I did run into an issue with this code though: On big-endian, I get

[ 0.272381] alg: skcipher: Test 1 failed (invalid result) on
encryption for xts-speck64-neon
[    0.276151] 00000000: 84 af 54 07 19 d4 7c a6 9c 8a ac f6 c2 14 04 d8
[    0.278541] 00000010: 7f 18 6c 43 56 ed 0b b3 92 21 a2 d9 17 59 e4 3b

Quoted 3 lines

so there may be a byte order corner case you missed in the rewrite (or the issue existed before, as I did not test your v1)

To be honest I haven't tested either version on a big endian ARM CPU yet. I don't really know how to do that currently; maybe it's possible with QEMU.

But assuming I haven't missed anything, in the assembly code everything is treated as byte arrays with the exception of the round keys which are 32-bit or 64-bit numbers in CPU endianness. The byte arrays are loaded and stored with vld1.8 and vst1.8 while the round keys are loaded with vld1.32 or vld1.64, so the assembly code *should* work correctly on a big endian CPU.

However, looking over it now, I think there is a bug in the glue code for Speck64-XTS when it handles buffers not evenly divisible into 128 bytes. Namely, the tweak is treated as CPU endian when it should be little endian. Could you try the following patch?

arch/arm/crypto/speck-neon-glue.c +3 -10

index 3987dd6e063e..960cc634b36f 100644
@@ -157,7 +157,7 @@ __speck64_xts_crypt(struct skcipher_request *req, speck64_crypt_one_t crypt_one,
        struct crypto_skcipher *tfm = crypto_skcipher_reqtfm(req);
        const struct speck64_xts_tfm_ctx *ctx = crypto_skcipher_ctx(tfm);
        struct skcipher_walk walk;
-       u64 tweak;
+       __le64 tweak;
        int err;
 
        err = skcipher_walk_virt(&walk, req, true);

@@ -184,16 +184,16 @@ __speck64_xts_crypt(struct skcipher_request *req, speck64_crypt_one_t crypt_one,
                }
 
                /* Handle any remainder with generic code */
-               while (nbytes >= sizeof(u64)) {
-                       *(u64 *)dst = *(u64 *)src ^ tweak;
+               while (nbytes >= sizeof(__le64)) {
+                       *(__le64 *)dst = *(__le64 *)src ^ tweak;
                        (*crypt_one)(&ctx->main_key, dst, dst);
-                       *(u64 *)dst ^= tweak;
-                       tweak = (tweak << 1) ^
-                               ((tweak & (1ULL << 63)) ? 0x1B : 0);
-
-                       dst += sizeof(u64);
-                       src += sizeof(u64);
-                       nbytes -= sizeof(u64);

Can we please not Speck?

It was just rejected by the ISO/IEC.

https://twitter.com/TomerAshur/status/988659711091228673

So, what do you propose replacing it with?

outside crypto review, vs. the many cryptanalysis papers on Speck. (In that respect the controversy about Speck has actually become an advantage, as it has received much more cryptanalysis than other lightweight block ciphers.)

The reason we chose Speck had nothing to do with the proposed ISO standard or any sociopolitical factors, but rather because it was the only algorithm we could find that met the performance and security requirements.

Note that Linux
doesn't bow down to any particular standards organization, and it offers algorithms that were specified in various places, even some with no more than a publication by the author. In fact, support for SM4 was just added too, which is a Chinese government standard. Are you going to send a patch to remove that too, or is it just NSA designed algorithms that are not okay?

(in fact, you'd
probably have a different opinion of it if the authors had simply worked somewhere else and published the exact same algorithm);

But I hope you can understand that all *technical* indicators are that Speck is secure enough

Quoted 1 line · Eric Biggers

So, what do you propose replacing it with?

Something more cryptographically justifiable.

That's the thing that worries me, actually. Many of the design decisions behind Speck haven't been justified.

Hi Eric,

Quoted 1 line · Eric Biggers

So, what do you propose replacing it with?

Something more cryptographically justifiable.

Quoted 3 lines

outside crypto review, vs. the many cryptanalysis papers on Speck. (In that respect the controversy about Speck has actually become an advantage, as it has received much more cryptanalysis than other lightweight block ciphers.)

That's the thing that worries me, actually. Many of the design decisions behind Speck haven't been justified.

Quoted 10 lines

The reason we chose Speck had nothing to do with the proposed ISO standard or any sociopolitical factors, but rather because it was the only algorithm we could find that met the performance and security requirements.

Note that Linux
doesn't bow down to any particular standards organization, and it offers algorithms that were specified in various places, even some with no more than a publication by the author. In fact, support for SM4 was just added too, which is a Chinese government standard. Are you going to send a patch to remove that too, or is it just NSA designed algorithms that are not okay?

No need to be belittling; I have much less tinfoil strapped around my head than perhaps you think. I'm not blindly opposed to government-designed algorithms. Take SHA2, for example -- built by the NSA.

But I do care quite a bit about using ciphers that have acceptance of the academic community and a large body of literature documenting its design decisions and analyzing it. Some of the best symmetric cryptographers in academia have expressed reservations about it, and it was just rejected from a major standard's body. Linux, of course, is free to disagree -- or "bow down" as you oddly put it -- but I'd make sure you've got a pretty large bucket of justifications for that disagreement.

Quoted 3 lines

(in fact, you'd
probably have a different opinion of it if the authors had simply worked somewhere else and published the exact same algorithm);

Again, no need to patronize. I don't actually have a bias like that.

Quoted 2 lines

But I hope you can understand that all *technical* indicators are that Speck is secure enough

That's the thing I'm worried about.

Other AES alternatives such as Twofish, Threefish, Camellia, CAST6, and Serpent aren't fast enough either; it seems that only a modern ARX cipher can provide sufficient performance on these devices.

We've also considered a novel length-preserving encryption mode based on ChaCha20 and Poly1305.

It's easy to say that, but do you have an actual suggestion?

Let's put the provenance of Speck aside for a moment, and suppose that it is an ideal block cipher. There are still some issues with this patch as it stands.

- The rationale seems off. Consider this bit from the commit message:

Quoted 3 lines

Other AES alternatives such as Twofish, Threefish, Camellia, CAST6, and Serpent aren't fast enough either; it seems that only a modern ARX cipher can provide sufficient performance on these devices.

One of these things is very much not like the others. Threefish _is_ a modern ARX cipher---a tweakable block cipher in fact, precluding the need for XEX-style masking. Is it too slow? Does it not have the correct block size?

Quoted 2 lines

We've also considered a novel length-preserving encryption mode based on ChaCha20 and Poly1305.

I'm very curious about this, namely as to what the role of Poly1305 would be here. ChaCha20's underlying permutation could, of course, be transformed into a 512-bit tweakable block cipher relatively painlessly, retaining the performance of regular ChaCha20 with marginal additional overhead. This would not be a standard construction, but clearly that is not an issue.

But the biggest problem here, in my mind, is that for all the talk of using 128-bit block Speck, this patch tacks on the 64-bit block variant of Speck into the kernel, and speck64-xts as well! As far as I can tell, this is the _only_ instance of a 64-bit XTS instance in the entire codebase. Now, if you wanted a fast 64-bit ARX block cipher, the kernel already had XTEA. Instead, this is adding yet another 64-bit block cipher into the crypto API, in a disk-encryption mode no less, so that it can be misused later. In the disk encryption setting, it's particularly concerning to be using such a small block size, as data volumes can quickly add up to the birthday bound.

Quoted 1 line

It's easy to say that, but do you have an actual suggestion?

I don't know how seriously you are actually asking this, but some 128-bit software-friendly block ciphers could be SPARX, LEA, RC5, or RC6. SPARX, in particular, has similarities to Speck but has some further AES-like design guarantees that other prior ARX block ciphers did not. Some other bitsliced designs, such as Noekeon or SKINNY, may also work well with NEON, but I don't know much about their performance there.

I agree that my explanation should have been better, and should have considered more crypto algorithms. The main difficulty is that we have extreme performance requirements -- it needs to be 50 MB/s at the very least on even low-end ARM devices like smartwatches. And even with the NEON-accelerated Speck128-XTS performance exceeding that after much optimization, we've been getting a lot of pushback as people want closer to 100 MB/s.

That's why I also included Speck64-XTS in the patches, since it was straightforward to include, and some devices may really need that last 20-30% of performance for encryption to be feasible at all. (And when the choice is between unencrypted and a 64-bit block cipher, used in a context where the weakest points in the cryptosystem are actually elsewhere such as the user's low-entropy PIN and the flash storage doing wear-leveling, I'd certainly take the 64-bit block cipher.) So far we haven't had to use Speck64 though, and if that continues to be the case I'd be fine with Speck64 being removed, leaving just Speck128.

Note that in practice, to have any chance at meeting the performance requirement the cipher needed to be NEON accelerated. That made benchmarking really hard and time-consuming, since to definitely know how an algorithm performs it can take upwards of a week to implement a NEON version. It needs to be very well optimized too, to compare the algorithms fairly -- e.g. with Speck I got a 20% performance improvement on some CPUs just by changing the NEON instructions used to implement the 8-bit rotates, an optimization that is not possible with ciphers that don't use rotate amounts that are multiples of 8. (This was an intentional design choice by the Speck designers; they do know what they're doing, actually.)

Thus, we had to be pretty aggressive about dropping algorithms from consideration if there were preliminary indications that they wouldn't perform well, or had too little cryptanalysis, or had other issues such as an unclear patent situation. Threefish for example I did test the C implementation at
https://github.com/wernerd/Skein3Fish, but on ARM32 it was over 4 times slower than my NEON implementation of Speck128/256-XTS. And I did not see a clear way that it could be improved over 4x with NEON, if at all, so I did not take the long time it would have taken to write an optimized NEON implementation to benchmark it properly. Perhaps that was a mistake. But, time is not unlimited.

As for the wide-block mode using ChaCha20 and Poly1305, you'd have to ask Paul Crowley to explain it properly, but briefly it's actually a pseudorandom permutation over an arbitrarily-sized message. So with dm-crypt for example, it would operate on a whole 512-byte sector, and if any bit of the 512-byte plaintext is changed, then every bit in the 512-byte ciphertext would change with 50% probability. To make this possible, the construction uses a polynomial evalution in GF(2^130-5) as a universal hash function, similar to the Poly1305 mode.

Using ChaCha20's underlying 512-bit permutation to build a tweakable block cipher is an interesting idea. But maybe in my crypto-naivety, it is not obvious to me how to do so. Do you have references to any relevant papers? Remember that we strongly prefer a published cipher to a custom one -- even if the core is reused, a mistake may be made in the way it is used. Thus, similarly to Paul's wide-block mode, I'd be concerned that we'd have to self-publish a new construction, then use it with no outside crypto review. *Maybe* it would be straightforward enough to be okay, but to know I'd need to see the details of how it would actually work.

But in the end, Speck seemed like the clear choice because it had multiple NEON implementations available already which showed it could be implemented very efficiently in NEON; it has over 70 cryptanalysis papers (far more than most ciphers) yet the security margin is still similar to AES; it has no intellectual property concerns; there is a paper clearly explaining the design decisions; it is naturally resistant to timing attacks; it supports a 128-bit block size, so it can be easily used in XTS mode; it supports the same key sizes as AES; and it has a simple and understandable design with no "magic numbers" besides 8 and 3 (compare to an actual backdoored algorithm like Dual_EC_DRGB, which basically had a public key embedded in the algorithm). Also as Paul mentioned he is confident in the construction, and he has published cryptanalysis on Salsa20, so his opinion is probably more significant than mine :-)

But I will definitely take a closer look at SPARX and some of the other ciphers you mentioned in case I missed something. I really do appreciate the suggestions, by the way, and in any case we do need to be very well prepared to justify our choices. I just hope that people can understand that we are implementing real-world crypto which must operate under *very* tight performance constraints on ARM processors, and it must be compatible with dm-crypt and fscrypt with no room for ciphertext expansion. Thus, many algorithms which may at first seem reasonable choices had to (unfortunately) be excluded.

Oh, OK, that sounds like something resembling Naor-Reingold or its relatives. That would work, but with 3 or 4 passes I guess it wouldn't be very fast.

Quoted 7 lines · Eric Biggers

I agree that my explanation should have been better, and should have considered more crypto algorithms. The main difficulty is that we have extreme performance requirements -- it needs to be 50 MB/s at the very least on even low-end ARM devices like smartwatches. And even with the NEON-accelerated Speck128-XTS performance exceeding that after much optimization, we've been getting a lot of pushback as people want closer to 100 MB/s.

I couldn't find any NEON-capable ARMv7 chip below 800 MHz, so this would put the performance upper bound around 15 cycles per byte, with the comfortable number being ~7. That's indeed tough, though not impossible.

Quoted 11 lines

That's why I also included Speck64-XTS in the patches, since it was straightforward to include, and some devices may really need that last 20-30% of performance for encryption to be feasible at all. (And when the choice is between unencrypted and a 64-bit block cipher, used in a context where the weakest points in the cryptosystem are actually elsewhere such as the user's low-entropy PIN and the flash storage doing wear-leveling, I'd certainly take the 64-bit block cipher.) So far we haven't had to use Speck64 though, and if that continues to be the case I'd be fine with Speck64 being removed, leaving just Speck128.

I would very much prefer that to be the case. As many of us know, "it's better than nothing" has been often used to justify other bad choices, like RC4, that end up preventing better ones from being adopted. At a time where we're trying to get rid of 64-bit ciphers in TLS, where data volumes per session are comparatively low, it would be unfortunate if the opposite starts happening on encryption at rest.

Quoted 12 lines

Note that in practice, to have any chance at meeting the performance requirement the cipher needed to be NEON accelerated. That made benchmarking really hard and time-consuming, since to definitely know how an algorithm performs it can take upwards of a week to implement a NEON version. It needs to be very well optimized too, to compare the algorithms fairly -- e.g. with Speck I got a 20% performance improvement on some CPUs just by changing the NEON instructions used to implement the 8-bit rotates, an optimization that is not possible with ciphers that don't use rotate amounts that are multiples of 8. (This was an intentional design choice by the Speck designers; they do know what they're doing, actually.)

Quoted 10 lines

Thus, we had to be pretty aggressive about dropping algorithms from consideration if there were preliminary indications that they wouldn't perform well, or had too little cryptanalysis, or had other issues such as an unclear patent situation. Threefish for example I did test the C implementation at
https://github.com/wernerd/Skein3Fish, but on ARM32 it was over 4 times slower than my NEON implementation of Speck128/256-XTS. And I did not see a clear way that it could be improved over 4x with NEON, if at all, so I did not take the long time it would have taken to write an optimized NEON implementation to benchmark it properly. Perhaps that was a mistake. But, time is not unlimited.

In my limited experience with NEON and 64-bit ARX, there's usually a ~2x speedup solely from NEON's native 64-bit operations on ARMv7-A. The extra speedup from encrypting 2 block in parallel is then somewhere between 1x and 2x, depending on various details. Getting near 4x might be feasible, but it is indeed time-consuming to get there.

Quoted 10 lines

As for the wide-block mode using ChaCha20 and Poly1305, you'd have to ask Paul Crowley to explain it properly, but briefly it's actually a pseudorandom permutation over an arbitrarily-sized message. So with dm-crypt for example, it would operate on a whole 512-byte sector, and if any bit of the 512-byte plaintext is changed, then every bit in the 512-byte ciphertext would change with 50% probability. To make this possible, the construction uses a polynomial evalution in GF(2^130-5) as a universal hash function, similar to the Poly1305 mode.

Oh, OK, that sounds like something resembling Naor-Reingold or its relatives. That would work, but with 3 or 4 passes I guess it wouldn't be very fast.

Quoted 11 lines

Using ChaCha20's underlying 512-bit permutation to build a tweakable block cipher is an interesting idea. But maybe in my crypto-naivety, it is not obvious to me how to do so. Do you have references to any relevant papers? Remember that we strongly prefer a published cipher to a custom one -- even if the core is reused, a mistake may be made in the way it is used. Thus, similarly to Paul's wide-block mode, I'd be concerned that we'd have to self-publish a new construction, then use it with no outside crypto review. *Maybe* it would be straightforward enough to be okay, but to know I'd need to see the details of how it would actually work.

This would be the 'tweakable Even-Mansour' construction and its variants. The variant I'm most familiar with would be MEM [1], focusing on software friendliness, but there is other provable security work in the same vein, including [3, 4, 5]. It's very similar to how the XEX mode turns a block cipher into a tweakable block cipher.

In [1, 2] we used a 1024-bit permutation out of BLAKE2 instead of ChaCha20's, but everything translates easily from one to the other. We also included cheap masks for 512-bit permutations, just in case.

[1] https://eprint.iacr.org/2015/999
[2] https://github.com/MEM-AEAD/mem-aead
[3] https://eprint.iacr.org/2015/539
[4] https://eprint.iacr.org/2015/476
[5] https://competitions.cr.yp.to/round2/minalpherv11.pdf

Quoted 14 lines

But in the end, Speck seemed like the clear choice because it had multiple NEON implementations available already which showed it could be implemented very efficiently in NEON; it has over 70 cryptanalysis papers (far more than most ciphers) yet the security margin is still similar to AES; it has no intellectual property concerns; there is a paper clearly explaining the design decisions; it is naturally resistant to timing attacks; it supports a 128-bit block size, so it can be easily used in XTS mode; it supports the same key sizes as AES; and it has a simple and understandable design with no "magic numbers" besides 8 and 3 (compare to an actual backdoored algorithm like Dual_EC_DRGB, which basically had a public key embedded in the algorithm). Also as Paul mentioned he is confident in the construction, and he has published cryptanalysis on Salsa20, so his opinion is probably more significant than mine :-)

Quoted 9 lines

But I will definitely take a closer look at SPARX and some of the other ciphers you mentioned in case I missed something. I really do appreciate the suggestions, by the way, and in any case we do need to be very well prepared to justify our choices. I just hope that people can understand that we are implementing real-world crypto which must operate under *very* tight performance constraints on ARM processors, and it must be compatible with dm-crypt and fscrypt with no room for ciphertext expansion. Thus, many algorithms which may at first seem reasonable choices had to (unfortunately) be excluded.

I understand it is a tough choice, and it's unfortunate that many of the algorithms we have cater mostly to either the high-hardware-accelerated-end or the extremely low-end, without a lot of good options at the middle-end.

Quoted 6 lines

Note that Linux
doesn't bow down to any particular standards organization, and it offers algorithms that were specified in various places, even some with no more than a publication by the author. In fact, support for SM4 was just added too, which is a Chinese government standard. Are you going to send a patch to remove that too, or is it just NSA designed algorithms that are not okay?

No need to be belittling; I have much less tinfoil strapped around my head than perhaps you think. I'm not blindly opposed to government-designed algorithms. Take SHA2, for example -- built by the NSA.

But I do care quite a bit about using ciphers that have acceptance of the academic community and a large body of literature documenting its design decisions and analyzing it.....

Can we please not Speck?

It was just rejected by the ISO/IEC.

https://twitter.com/TomerAshur/status/988659711091228673