Repository: randombit/botan
Pull request #2565 (2020-12-27 21:32:08)

Add BMI2 3DES implementation
Even on Skylake with relatively fast pdep this is about 1/2 the speed of the table version (98 cpb vs 64 for large tables) which :( but here the lookup tables we need are only exactly 64 bytes long, which when aligned avoids most cache based side channels.

I'm 90% sure that it's possible to replace the `pdeps` with multiplications and use it everywhere, but haven't worked out the details yet.


Patch:
diff --git a/doc/dev_ref/todo.rst b/doc/dev_ref/todo.rst
index e82c885fa..6c69b3b77 100644
--- a/doc/dev_ref/todo.rst
+++ b/doc/dev_ref/todo.rst
@@ -29,7 +29,7 @@ Improved Ciphers Implementations
 * Poly1305 using AVX2
 * ChaCha using SSSE3
 * SHA-512 using BMI2+AVX2
-* Constant time DES using bitslicing and/or BMI2
+* Constant time DES using bitslicing
 * SIMD evaluation of SHA-2 and SHA-3 compression functions
 
 Public Key Crypto, Math
diff --git a/doc/side_channels.rst b/doc/side_channels.rst
index 72448a8dd..2f892ae0e 100644
--- a/doc/side_channels.rst
+++ b/doc/side_channels.rst
@@ -310,6 +310,12 @@ channel attacks. DES or 3DES should be avoided in new systems. The proper fix
 would be a scalar bitsliced implementation, this is not seen as worth the
 engineering investment given these algorithms end of life status.
 
+On systems supporting the BMI2 instruction set, an implementation using pdep is
+available which is slower but uses only cache-line sized tables. Thus it avoids
+most known cache-based side channels. It would still be vulnerable to cache-bank
+conflict side channels, but all hardware known to be vulnerable to such channels
+does not implement BMI2.
+
 Twofish
 ------------------------
 
diff --git a/src/lib/block/des/des.cpp b/src/lib/block/des/des.cpp
index c3afee6f5..2dc3e9c43 100644
--- a/src/lib/block/des/des.cpp
+++ b/src/lib/block/des/des.cpp
@@ -11,6 +11,7 @@
 #include <botan/internal/des.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/rotate.h>
+#include <botan/internal/cpuid.h>
 
 namespace Botan {
 
@@ -431,6 +432,13 @@ void TripleDES::encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) cons
    {
    verify_key_set(m_round_key.empty() == false);
 
+#if defined(BOTAN_HAS_DES_BMI2)
+   if(CPUID::has_bmi2() && CPUID::has_fast_pdep())
+      {
+      return bmi2_encrypt_n(in, out, blocks, &m_round_key[0]);
+      }
+#endif
+
    while(blocks >= 2)
       {
       uint32_t L0 = load_be<uint32_t>(in, 0);
@@ -481,6 +489,13 @@ void TripleDES::decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) cons
    {
    verify_key_set(m_round_key.empty() == false);
 
+#if defined(BOTAN_HAS_DES_BMI2)
+   if(CPUID::has_bmi2() && CPUID::has_fast_pdep())
+      {
+      return bmi2_decrypt_n(in, out, blocks, &m_round_key[0]);
+      }
+#endif
+
    while(blocks >= 2)
       {
       uint32_t L0 = load_be<uint32_t>(in, 0);
diff --git a/src/lib/block/des/des.h b/src/lib/block/des/des.h
index 394bbdc6e..2907ff0f1 100644
--- a/src/lib/block/des/des.h
+++ b/src/lib/block/des/des.h
@@ -43,6 +43,12 @@ class TripleDES final : public Block_Cipher_Fixed_Params<8, 16, 24, 8>
       std::string name() const override { return "TripleDES"; }
       BlockCipher* clone() const override { return new TripleDES; }
    private:
+
+#if defined(BOTAN_HAS_DES_BMI2)
+      static void bmi2_encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks, const uint32_t key[]);
+      static void bmi2_decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks, const uint32_t key[]);
+#endif
+
       void key_schedule(const uint8_t[], size_t) override;
 
       secure_vector<uint32_t> m_round_key;
diff --git a/src/lib/block/des/des_bmi2/des_bmi2.cpp b/src/lib/block/des/des_bmi2/des_bmi2.cpp
new file mode 100644
index 000000000..da3f5bd6d
--- /dev/null
+++ b/src/lib/block/des/des_bmi2/des_bmi2.cpp
@@ -0,0 +1,292 @@
+/*
+* (C) 2020 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/internal/des.h>
+#include <botan/internal/rotate.h>
+#include <botan/internal/loadstor.h>
+#include <immintrin.h>
+
+namespace Botan {
+
+namespace {
+
+namespace DES_BMI2_fn {
+
+alignas(64) const uint8_t SPBOX_CAT_0[64] = {
+   0xE, 0x0, 0x4, 0xF, 0xD, 0x7, 0x1, 0x4, 0x2, 0xE, 0xF, 0x2, 0xB, 0xD, 0x8, 0x1,
+   0x3, 0xA, 0xA, 0x6, 0x6, 0xC, 0xC, 0xB, 0x5, 0x9, 0x9, 0x5, 0x0, 0x3, 0x7, 0x8,
+   0x4, 0xF, 0x1, 0xC, 0xE, 0x8, 0x8, 0x2, 0xD, 0x4, 0x6, 0x9, 0x2, 0x1, 0xB, 0x7,
+   0xF, 0x5, 0xC, 0xB, 0x9, 0x3, 0x7, 0xE, 0x3, 0xA, 0xA, 0x0, 0x5, 0x6, 0x0, 0xD,
+};
+
+alignas(64) const uint8_t SPBOX_CAT_1[64] = {
+   0xF, 0xA, 0x2, 0x7, 0x4, 0x1, 0xD, 0xB, 0x9, 0xF, 0xE, 0x8, 0xA, 0x4, 0x1, 0xD,
+   0x6, 0x5, 0xB, 0x0, 0x8, 0x2, 0x7, 0xC, 0x5, 0x9, 0x0, 0x6, 0x3, 0xE, 0xC, 0x3,
+   0x0, 0x7, 0xD, 0x4, 0xB, 0xC, 0xE, 0x2, 0xC, 0xA, 0x1, 0xF, 0x7, 0x1, 0x2, 0x8,
+   0x3, 0xE, 0x4, 0x9, 0x5, 0xB, 0x9, 0x5, 0x6, 0x0, 0xA, 0x3, 0x8, 0xD, 0xF, 0x6,
+};
+
+alignas(64) const uint8_t SPBOX_CAT_2[64] = {
+   0x3, 0xE, 0x0, 0xD, 0xA, 0x0, 0x7, 0xA, 0x5, 0x9, 0x9, 0x4, 0xF, 0x5, 0xC, 0x3,
+   0x8, 0x1, 0xE, 0x2, 0x6, 0xC, 0xD, 0x7, 0xB, 0x6, 0x4, 0xB, 0x1, 0xF, 0x2, 0x8,
+   0xE, 0x8, 0x5, 0x3, 0x4, 0xE, 0xA, 0x0, 0x2, 0x5, 0xF, 0xA, 0x9, 0x2, 0x0, 0xD,
+   0xB, 0x4, 0x8, 0xF, 0x1, 0x7, 0x6, 0x9, 0xC, 0xB, 0x3, 0xC, 0x7, 0x1, 0xD, 0x6,
+};
+
+alignas(64) const uint8_t SPBOX_CAT_3[64] = {
+   0xD, 0x7, 0x7, 0x2, 0xE, 0xB, 0x9, 0x5, 0x0, 0xC, 0xC, 0xF, 0x3, 0x0, 0xA, 0x9,
+   0x1, 0x4, 0x8, 0xD, 0x2, 0x8, 0x5, 0x6, 0xB, 0x1, 0x6, 0xA, 0x4, 0xE, 0xF, 0x3,
+   0xA, 0x9, 0xC, 0xF, 0x3, 0x0, 0x0, 0xC, 0x6, 0xA, 0xB, 0x1, 0xD, 0x7, 0x7, 0x2,
+   0xF, 0x3, 0x1, 0x4, 0x9, 0x5, 0xE, 0xB, 0x5, 0x6, 0x8, 0xD, 0x2, 0x8, 0x4, 0xE,
+};
+
+alignas(64) const uint8_t SPBOX_CAT_4[64] = {
+   0x1, 0x7, 0x6, 0xD, 0x2, 0x1, 0x8, 0x6, 0xB, 0x2, 0x5, 0xB, 0xD, 0xE, 0x3, 0x8,
+   0x4, 0xA, 0xA, 0x0, 0x9, 0xF, 0xF, 0x5, 0xE, 0x9, 0x0, 0xC, 0x7, 0x4, 0xC, 0x3,
+   0x2, 0xD, 0x1, 0x4, 0x8, 0x6, 0xD, 0xB, 0x5, 0x8, 0xE, 0x7, 0xB, 0x1, 0x4, 0xE,
+   0xF, 0x3, 0xC, 0xF, 0x6, 0x0, 0xA, 0xC, 0x3, 0x5, 0x9, 0x2, 0x0, 0xA, 0x7, 0x9,
+};
+
+alignas(64) const uint8_t SPBOX_CAT_5[64] = {
+   0x9, 0xC, 0x2, 0xF, 0xC, 0x1, 0xF, 0x4, 0xA, 0x7, 0x4, 0x9, 0x5, 0xA, 0x8, 0x3,
+   0x0, 0x5, 0xB, 0x2, 0x6, 0xB, 0x1, 0xD, 0xD, 0x0, 0x7, 0xE, 0x3, 0x6, 0xE, 0x8,
+   0xA, 0x1, 0xD, 0x6, 0xF, 0x4, 0x3, 0x9, 0x4, 0xA, 0x8, 0x3, 0x9, 0xF, 0x6, 0xC,
+   0x7, 0xE, 0x0, 0xD, 0x1, 0x2, 0xC, 0x7, 0x2, 0x5, 0xB, 0x0, 0xE, 0x8, 0x5, 0xB,
+};
+
+alignas(64) const uint8_t SPBOX_CAT_6[64] = {
+   0x4, 0xD, 0xB, 0x0, 0x2, 0xB, 0x7, 0xE, 0xF, 0x4, 0x0, 0x9, 0x1, 0x8, 0xD, 0x3,
+   0xA, 0x7, 0x5, 0xA, 0x9, 0xC, 0xE, 0x5, 0xC, 0x2, 0x3, 0xF, 0x6, 0x1, 0x8, 0x6,
+   0x8, 0x6, 0x4, 0xB, 0xB, 0xD, 0xD, 0x1, 0x5, 0x8, 0xA, 0x4, 0xE, 0x3, 0x7, 0xE,
+   0x3, 0x9, 0xF, 0xC, 0x6, 0x0, 0x1, 0xF, 0x0, 0x7, 0xC, 0x2, 0x9, 0xA, 0x2, 0x5,
+};
+
+alignas(64) const uint8_t SPBOX_CAT_7[64] = {
+   0xB, 0x2, 0x4, 0xF, 0x8, 0xB, 0x1, 0x8, 0x5, 0xC, 0xF, 0x6, 0xE, 0x7, 0x2, 0x1,
+   0xC, 0x9, 0xA, 0x3, 0x6, 0x5, 0xD, 0xE, 0x3, 0x0, 0x0, 0xD, 0x9, 0xA, 0x7, 0x4,
+   0x7, 0x4, 0xE, 0x2, 0x1, 0xD, 0x2, 0x7, 0xA, 0x1, 0x9, 0xC, 0xD, 0x8, 0x4, 0xB,
+   0x0, 0xF, 0x5, 0x9, 0xC, 0xA, 0xB, 0x0, 0xF, 0x6, 0x6, 0x3, 0x3, 0x5, 0x8, 0xE,
+};
+
+inline uint32_t spbox(uint32_t T0, uint32_t T1)
+   {
+   return
+      _pdep_u32(SPBOX_CAT_0[get_byte(0, T0) % 64], 0x01010404) ^
+      _pdep_u32(SPBOX_CAT_1[get_byte(0, T1) % 64], 0x80108020) ^
+      _pdep_u32(SPBOX_CAT_2[get_byte(1, T0) % 64], 0x08020208) ^
+      _pdep_u32(SPBOX_CAT_3[get_byte(1, T1) % 64], 0x00802081) ^
+      _pdep_u32(SPBOX_CAT_4[get_byte(2, T0) % 64], 0x42080100) ^
+      _pdep_u32(SPBOX_CAT_5[get_byte(2, T1) % 64], 0x20404010) ^
+      _pdep_u32(SPBOX_CAT_6[get_byte(3, T0) % 64], 0x04200802) ^
+      _pdep_u32(SPBOX_CAT_7[get_byte(3, T1) % 64], 0x10041040);
+   }
+
+inline void des_encrypt(uint32_t& Lr, uint32_t& Rr,
+                        const uint32_t round_key[32])
+   {
+   uint32_t L = Lr;
+   uint32_t R = Rr;
+   for(size_t i = 0; i != 16; i += 2)
+      {
+      L ^= spbox(rotr<4>(R) ^ round_key[2*i  ], R ^ round_key[2*i+1]);
+      R ^= spbox(rotr<4>(L) ^ round_key[2*i+2], L ^ round_key[2*i+3]);
+      }
+
+   Lr = L;
+   Rr = R;
+   }
+
+inline void des_encrypt_x2(uint32_t& L0r, uint32_t& R0r,
+                           uint32_t& L1r, uint32_t& R1r,
+                           const uint32_t round_key[32])
+   {
+   uint32_t L0 = L0r;
+   uint32_t R0 = R0r;
+   uint32_t L1 = L1r;
+   uint32_t R1 = R1r;
+
+   for(size_t i = 0; i != 16; i += 2)
+      {
+      L0 ^= spbox(rotr<4>(R0) ^ round_key[2*i  ], R0 ^ round_key[2*i+1]);
+      L1 ^= spbox(rotr<4>(R1) ^ round_key[2*i  ], R1 ^ round_key[2*i+1]);
+
+      R0 ^= spbox(rotr<4>(L0) ^ round_key[2*i+2], L0 ^ round_key[2*i+3]);
+      R1 ^= spbox(rotr<4>(L1) ^ round_key[2*i+2], L1 ^ round_key[2*i+3]);
+      }
+
+   L0r = L0;
+   R0r = R0;
+   L1r = L1;
+   R1r = R1;
+   }
+
+inline void des_decrypt(uint32_t& Lr, uint32_t& Rr,
+                        const uint32_t round_key[32])
+   {
+   uint32_t L = Lr;
+   uint32_t R = Rr;
+   for(size_t i = 16; i != 0; i -= 2)
+      {
+      L ^= spbox(rotr<4>(R) ^ round_key[2*i - 2], R  ^ round_key[2*i - 1]);
+      R ^= spbox(rotr<4>(L) ^ round_key[2*i - 4], L  ^ round_key[2*i - 3]);
+      }
+   Lr = L;
+   Rr = R;
+   }
+
+inline void des_decrypt_x2(uint32_t& L0r, uint32_t& R0r,
+                           uint32_t& L1r, uint32_t& R1r,
+                           const uint32_t round_key[32])
+   {
+   uint32_t L0 = L0r;
+   uint32_t R0 = R0r;
+   uint32_t L1 = L1r;
+   uint32_t R1 = R1r;
+
+   for(size_t i = 16; i != 0; i -= 2)
+      {
+      L0 ^= spbox(rotr<4>(R0) ^ round_key[2*i - 2], R0  ^ round_key[2*i - 1]);
+      L1 ^= spbox(rotr<4>(R1) ^ round_key[2*i - 2], R1  ^ round_key[2*i - 1]);
+
+      R0 ^= spbox(rotr<4>(L0) ^ round_key[2*i - 4], L0  ^ round_key[2*i - 3]);
+      R1 ^= spbox(rotr<4>(L1) ^ round_key[2*i - 4], L1  ^ round_key[2*i - 3]);
+      }
+
+   L0r = L0;
+   R0r = R0;
+   L1r = L1;
+   R1r = R1;
+   }
+
+inline void des_IP(uint32_t& L, uint32_t& R, const uint8_t block[])
+   {
+   // IP sequence by Wei Dai, taken from public domain Crypto++
+   L = load_be<uint32_t>(block, 0);
+   R = load_be<uint32_t>(block, 1);
+
+   uint32_t T;
+   R = rotl<4>(R);
+   T = (L ^ R) & 0xF0F0F0F0;
+   L ^= T;
+   R = rotr<20>(R ^ T);
+   T = (L ^ R) & 0xFFFF0000;
+   L ^= T;
+   R = rotr<18>(R ^ T);
+   T = (L ^ R) & 0x33333333;
+   L ^= T;
+   R = rotr<6>(R ^ T);
+   T = (L ^ R) & 0x00FF00FF;
+   L ^= T;
+   R = rotl<9>(R ^ T);
+   T = (L ^ R) & 0xAAAAAAAA;
+   L = rotl<1>(L ^ T);
+   R ^= T;
+   }
+
+inline void des_FP(uint32_t L, uint32_t R, uint8_t out[])
+   {
+   // FP sequence by Wei Dai, taken from public domain Crypto++
+   uint32_t T;
+
+   R = rotr<1>(R);
+   T = (L ^ R) & 0xAAAAAAAA;
+   R ^= T;
+   L = rotr<9>(L ^ T);
+   T = (L ^ R) & 0x00FF00FF;
+   R ^= T;
+   L = rotl<6>(L ^ T);
+   T = (L ^ R) & 0x33333333;
+   R ^= T;
+   L = rotl<18>(L ^ T);
+   T = (L ^ R) & 0xFFFF0000;
+   R ^= T;
+   L = rotl<20>(L ^ T);
+   T = (L ^ R) & 0xF0F0F0F0;
+   R ^= T;
+   L = rotr<4>(L ^ T);
+   store_be(out, R, L);
+   }
+
+}
+
+}
+
+//static
+void TripleDES::bmi2_encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks, const uint32_t key[])
+   {
+   using namespace DES_BMI2_fn;
+   while(blocks >= 2)
+      {
+      uint32_t L0, R0;
+      uint32_t L1, R1;
+
+      des_IP(L0, R0, in);
+      des_IP(L1, R1, in + BLOCK_SIZE);
+
+      des_encrypt_x2(L0, R0, L1, R1, &key[0]);
+      des_decrypt_x2(R0, L0, R1, L1, &key[32]);
+      des_encrypt_x2(L0, R0, L1, R1, &key[64]);
+
+      des_FP(L0, R0, out);
+      des_FP(L1, R1, out + BLOCK_SIZE);
+
+      in += 2*BLOCK_SIZE;
+      out += 2*BLOCK_SIZE;
+      blocks -= 2;
+      }
+
+   for(size_t i = 0; i != blocks; ++i)
+      {
+      uint32_t L, R;
+      des_IP(L, R, in + BLOCK_SIZE*i);
+
+      des_encrypt(L, R, &key[0]);
+      des_decrypt(R, L, &key[32]);
+      des_encrypt(L, R, &key[64]);
+
+      des_FP(L, R, out + BLOCK_SIZE*i);
+      }
+   }
+
+//static
+void TripleDES::bmi2_decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks, const uint32_t key[])
+   {
+   using namespace DES_BMI2_fn;
+
+   while(blocks >= 2)
+      {
+      uint32_t L0, R0;
+      uint32_t L1, R1;
+
+      des_IP(L0, R0, in);
+      des_IP(L1, R1, in + BLOCK_SIZE);
+
+      des_decrypt_x2(L0, R0, L1, R1, &key[64]);
+      des_encrypt_x2(R0, L0, R1, L1, &key[32]);
+      des_decrypt_x2(L0, R0, L1, R1, &key[0]);
+
+      des_FP(L0, R0, out);
+      des_FP(L1, R1, out + BLOCK_SIZE);
+
+      in += 2*BLOCK_SIZE;
+      out += 2*BLOCK_SIZE;
+      blocks -= 2;
+      }
+
+   for(size_t i = 0; i != blocks; ++i)
+      {
+      uint32_t L, R;
+      des_IP(L, R, in + BLOCK_SIZE*i);
+
+      des_decrypt(L, R, &key[64]);
+      des_encrypt(R, L, &key[32]);
+      des_decrypt(L, R, &key[0]);
+
+      des_FP(L, R, out + BLOCK_SIZE*i);
+      }
+   }
+
+}
diff --git a/src/lib/block/des/des_bmi2/info.txt b/src/lib/block/des/des_bmi2/info.txt
new file mode 100644
index 000000000..a895c6964
--- /dev/null
+++ b/src/lib/block/des/des_bmi2/info.txt
@@ -0,0 +1,17 @@
+<defines>
+DES_BMI2 -> 20201204
+</defines>
+
+<isa>
+bmi2
+</isa>
+
+<arch>
+x86_64
+</arch>
+
+<cc>
+gcc
+clang
+msvc
+</cc>
diff --git a/src/lib/utils/cpuid/cpuid.h b/src/lib/utils/cpuid/cpuid.h
index db0bfe1a9..102ed9593 100644
--- a/src/lib/utils/cpuid/cpuid.h
+++ b/src/lib/utils/cpuid/cpuid.h
@@ -115,6 +115,7 @@ class BOTAN_PUBLIC_API(2,1) CPUID final
          CPUID_ADX_BIT        = (1ULL << 49),
          CPUID_BMI1_BIT       = (1ULL << 50),
          CPUID_BMI2_BIT       = (1ULL << 51),
+         CPUID_FAST_PDEP_BIT  = (1ULL << 52),
 #endif
 
 #if defined(BOTAN_TARGET_CPU_IS_PPC_FAMILY)
@@ -309,6 +310,12 @@ class BOTAN_PUBLIC_API(2,1) CPUID final
       static bool has_bmi2()
          { return has_cpuid_bit(CPUID_BMI2_BIT); }
 
+      /**
+      * Check if the processor supports fast PDEP/PEXT from BMI2
+      */
+      static bool has_fast_pdep()
+         { return has_cpuid_bit(CPUID_FAST_PDEP_BIT); }
+
       /**
       * Check if the processor supports AES-NI
       */
diff --git a/src/lib/utils/cpuid/cpuid_x86.cpp b/src/lib/utils/cpuid/cpuid_x86.cpp
index b8ae54f87..51e51fa8e 100644
--- a/src/lib/utils/cpuid/cpuid_x86.cpp
+++ b/src/lib/utils/cpuid/cpuid_x86.cpp
@@ -152,7 +152,20 @@ uint64_t CPUID::CPUID_Data::detect_cpu_features(size_t* cache_line_size)
          implements BMI2 but not BMI1.
          */
          if(flags7 & x86_CPUID_7_bits::BMI2)
+            {
             features_detected |= CPUID::CPUID_BMI2_BIT;
+
+            /*
+            Up until Zen3, AMD CPUs with BMI2 support had microcoded
+            pdep/pext, which works but is very slow.
+
+            TODO: check for Zen3 here
+            */
+            if(is_intel)
+               {
+               features_detected |= CPUID::CPUID_FAST_PDEP_BIT;
+               }
+            }
          }
 
       if(flags7 & x86_CPUID_7_bits::AVX512_F)


Test patch:
diff --git a/src/tests/data/block/des.vec b/src/tests/data/block/des.vec
index 42853248a..00b1160a8 100644
--- a/src/tests/data/block/des.vec
+++ b/src/tests/data/block/des.vec
@@ -1,3 +1,5 @@
+#test cpuid bmi2
+
 [DES]
 Key = 0113B970FD34F2CE
 In = 059B5E0851CF143A