Simplify polynomial doubling code

GCC and Clang generate effectively identical code for a template
with parameters, vs completely unrolled code as was used previously.

Add a little-endian variant so XTS can use it. This extends XTS support
to cover 256 and 512-bit ciphers. I was not able to find another
implementation that supports both XTS and ciphers with large blocks,
so the XTS test vectors are self-generated.

6 files changed, 95 insertions, 156 deletions

diff --git a/src/lib/mac/cmac/cmac.cpp b/src/lib/mac/cmac/cmac.cpp
index 4d76e4a20..665bfe3c0 100644
--- a/src/lib/mac/cmac/cmac.cpp
+++ b/src/lib/mac/cmac/cmac.cpp
@@ -15,8 +15,8 @@ namespace Botan {
 */
 secure_vector<uint8_t> CMAC::poly_double(const secure_vector<uint8_t>& in)
    {
-   secure_vector<uint8_t> out = in;
-   poly_double_n(out.data(), out.size());
+   secure_vector<uint8_t> out(in.size());
+   poly_double_n(out.data(), in.data(), out.size());
    return out;
    }
 
@@ -81,9 +81,7 @@ void CMAC::key_schedule(const uint8_t key[], size_t length)
    m_cipher->set_key(key, length);
    m_cipher->encrypt(m_B);
    poly_double_n(m_B.data(), m_B.size());
-
-   m_P = m_B;
-   poly_double_n(m_P.data(), m_P.size());
+   poly_double_n(m_P.data(), m_B.data(), m_P.size());
    }
 
 /*
diff --git a/src/lib/modes/aead/ocb/ocb.cpp b/src/lib/modes/aead/ocb/ocb.cpp
index 42118c25c..aa8532526 100644
--- a/src/lib/modes/aead/ocb/ocb.cpp
+++ b/src/lib/modes/aead/ocb/ocb.cpp
@@ -56,8 +56,8 @@ class L_computer
 
       secure_vector<uint8_t> poly_double(const secure_vector<uint8_t>& in) const
          {
-         secure_vector<uint8_t> out = in;
-         poly_double_n(out.data(), out.size());
+         secure_vector<uint8_t> out(in.size());
+         poly_double_n(out.data(), in.data(), out.size());
          return out;
          }
 
diff --git a/src/lib/modes/xts/xts.cpp b/src/lib/modes/xts/xts.cpp
index 9487bd835..4a4250f84 100644
--- a/src/lib/modes/xts/xts.cpp
+++ b/src/lib/modes/xts/xts.cpp
@@ -8,51 +8,19 @@
 
 #include <botan/xts.h>
 #include <botan/loadstor.h>
+#include <botan/internal/poly_dbl.h>
 
 namespace Botan {
 
-namespace {
-
-void poly_double_128(uint8_t out[], const uint8_t in[])
-   {
-   uint64_t X0 = load_le<uint64_t>(in, 0);
-   uint64_t X1 = load_le<uint64_t>(in, 1);
-
-   const bool carry = static_cast<bool>((X1 >> 63) != 0);
-
-   X1 = (X1 << 1) | (X0 >> 63);
-   X0 = (X0 << 1);
-
-   if(carry)
-      X0 ^= 0x87;
-
-   store_le(out, X0, X1);
-   }
-
-void poly_double_64(uint8_t out[], const uint8_t in[])
-   {
-   uint64_t X = load_le<uint64_t>(in, 0);
-   const bool carry = static_cast<bool>((X >> 63) != 0);
-   X <<= 1;
-   if(carry)
-      X ^= 0x1B;
-   store_le(X, out);
-   }
-
-inline void poly_double(uint8_t out[], const uint8_t in[], size_t size)
-   {
-   if(size == 8)
-      poly_double_64(out, in);
-   else
-      poly_double_128(out, in);
-   }
-
-}
-
 XTS_Mode::XTS_Mode(BlockCipher* cipher) : m_cipher(cipher)
    {
-   if(m_cipher->block_size() != 8 && m_cipher->block_size() != 16)
-      throw Invalid_Argument("Bad cipher for XTS: " + cipher->name());
+   if(m_cipher->block_size() != 8 &&
+      m_cipher->block_size() != 16 &&
+      m_cipher->block_size() != 32 &&
+      m_cipher->block_size() != 64)
+      {
+      throw Invalid_Argument("Cannot use " + cipher->name() + " with XTS");
+      }
 
    m_tweak_cipher.reset(m_cipher->clone());
    m_tweak.resize(update_granularity());
@@ -127,12 +95,12 @@ void XTS_Mode::update_tweak(size_t which)
    const size_t BS = m_tweak_cipher->block_size();
 
    if(which > 0)
-      poly_double(m_tweak.data(), &m_tweak[(which-1)*BS], BS);
+      poly_double_n_le(m_tweak.data(), &m_tweak[(which-1)*BS], BS);
 
    const size_t blocks_in_tweak = update_granularity() / BS;
 
    for(size_t i = 1; i < blocks_in_tweak; ++i)
-      poly_double(&m_tweak[i*BS], &m_tweak[(i-1)*BS], BS);
+      poly_double_n_le(&m_tweak[i*BS], &m_tweak[(i-1)*BS], BS);
    }
 
 size_t XTS_Encryption::output_length(size_t input_length) const
@@ -173,7 +141,7 @@ void XTS_Encryption::finish(secure_vector<uint8_t>& buffer, size_t offset)
    const size_t sz = buffer.size() - offset;
    uint8_t* buf = buffer.data() + offset;
 
-   BOTAN_ASSERT(sz >= minimum_final_size(), "Have sufficient final input");
+   BOTAN_ASSERT(sz >= minimum_final_size(), "Have sufficient final input in XTS encrypt");
 
    const size_t BS = cipher().block_size();
 
@@ -249,7 +217,7 @@ void XTS_Decryption::finish(secure_vector<uint8_t>& buffer, size_t offset)
    const size_t sz = buffer.size() - offset;
    uint8_t* buf = buffer.data() + offset;
 
-   BOTAN_ASSERT(sz >= minimum_final_size(), "Have sufficient final input");
+   BOTAN_ASSERT(sz >= minimum_final_size(), "Have sufficient final input in XTS decrypt");
 
    const size_t BS = cipher().block_size();
 
diff --git a/src/lib/utils/poly_dbl.cpp b/src/lib/utils/poly_dbl.cpp
index 0cea4957b..2b989db57 100644
--- a/src/lib/utils/poly_dbl.cpp
+++ b/src/lib/utils/poly_dbl.cpp
@@ -10,120 +10,74 @@
 
 namespace Botan {
 
-void poly_double_n(uint8_t b[], size_t n)
-   {
-   if(n == 8)
-      return poly_double_8(b);
-   else if(n == 16)
-      return poly_double_16(b);
-   else if(n == 24)
-      return poly_double_24(b);
-   else if(n == 32)
-      return poly_double_32(b);
-   else if(n == 64)
-      return poly_double_64(b);
-   else
-      throw Invalid_Argument("Unsupported size for poly_double_n");
-   }
-
-void poly_double_8(uint8_t b[8])
-   {
-   const uint64_t poly = 0x1B;
-   uint64_t b0 = load_be<uint64_t>(b, 0);
-   const uint64_t carry0 = (b0 >> 63);
-   b0 = (b0 << 1) ^ (carry0 * poly);
-   store_be(b0, b);
-   }
+namespace {
 
-void poly_double_16(uint8_t b[16])
+template<size_t LIMBS, uint64_t POLY>
+void poly_double(uint8_t out[], const uint8_t in[])
    {
-   const uint64_t poly = 0x87;
+   uint64_t W[LIMBS];
+   load_be(W, in, LIMBS);
 
-   uint64_t b0 = load_be<uint64_t>(b, 0);
-   uint64_t b1 = load_be<uint64_t>(b, 1);
+   const uint64_t carry = POLY * (W[0] >> 63);
+   for(size_t i = 0; i != LIMBS - 1; ++i)
+      W[i] = (W[i] << 1) ^ (W[i+1] >> 63);
+   W[LIMBS-1] = (W[LIMBS-1] << 1) ^ carry;
 
-   const uint64_t carry0 = (b0 >> 63);
-
-   b0 = (b0 << 1) ^ (b1 >> 63);
-   b1 = (b1 << 1) ^ (carry0 * poly);
-
-   store_be(b0, b);
-   store_be(b1, b+8);
+   copy_out_be(out, LIMBS*8, W);
    }
 
-void poly_double_24(uint8_t b[24])
+template<size_t LIMBS, uint64_t POLY>
+void poly_double_le(uint8_t out[], const uint8_t in[])
    {
-   const uint64_t poly = 0x87;
-
-   uint64_t b0 = load_be<uint64_t>(b, 0);
-   uint64_t b1 = load_be<uint64_t>(b, 1);
-   uint64_t b2 = load_be<uint64_t>(b, 2);
+   uint64_t W[LIMBS];
+   load_le(W, in, LIMBS);
 
-   const uint64_t carry0 = (b0 >> 63);
+   const uint64_t carry = POLY * (W[LIMBS-1] >> 63);
+   for(size_t i = 0; i != LIMBS - 1; ++i)
+      W[LIMBS-1-i] = (W[LIMBS-1-i] << 1) ^ (W[LIMBS-2-i] >> 63);
+   W[0] = (W[0] << 1) ^ carry;
 
-   b0 = (b0 << 1) ^ (b1 >> 63);
-   b1 = (b1 << 1) ^ (b2 >> 63);
-   b2 = (b2 << 1) ^ (carry0 * poly);
-
-   store_be(b0, b);
-   store_be(b1, b+8);
-   store_be(b2, b+16);
+   copy_out_le(out, LIMBS*8, W);
    }
 
-void poly_double_32(uint8_t b[32])
-   {
-   const uint64_t poly = 0x425;
-
-   uint64_t b0 = load_be<uint64_t>(b, 0);
-   uint64_t b1 = load_be<uint64_t>(b, 1);
-   uint64_t b2 = load_be<uint64_t>(b, 2);
-   uint64_t b3 = load_be<uint64_t>(b, 3);
-
-   const uint64_t carry0 = (b0 >> 63);
-
-   b0 = (b0 << 1) ^ (b1 >> 63);
-   b1 = (b1 << 1) ^ (b2 >> 63);
-   b2 = (b2 << 1) ^ (b3 >> 63);
-   b3 = (b3 << 1) ^ (carry0 * poly);
+}
 
-   store_be(b0, b);
-   store_be(b1, b+8);
-   store_be(b2, b+16);
-   store_be(b3, b+24);
+void poly_double_n(uint8_t out[], const uint8_t in[], size_t n)
+   {
+   switch(n)
+      {
+      case 8:
+         return poly_double<1, 0x1B>(out, in);
+      case 16:
+         return poly_double<2, 0x87>(out, in);
+      case 24:
+         return poly_double<3, 0x87>(out, in);
+      case 32:
+         return poly_double<4, 0x425>(out, in);
+      case 64:
+         return poly_double<8, 0x125>(out, in);
+      default:
+         throw Invalid_Argument("Unsupported size for poly_double_n");
+      }
    }
 
-void poly_double_64(uint8_t b[64])
+void poly_double_n_le(uint8_t out[], const uint8_t in[], size_t n)
    {
-   const uint64_t poly = 0x125;
-
-   uint64_t b0 = load_be<uint64_t>(b, 0);
-   uint64_t b1 = load_be<uint64_t>(b, 1);
-   uint64_t b2 = load_be<uint64_t>(b, 2);
-   uint64_t b3 = load_be<uint64_t>(b, 3);
-   uint64_t b4 = load_be<uint64_t>(b, 4);
-   uint64_t b5 = load_be<uint64_t>(b, 5);
-   uint64_t b6 = load_be<uint64_t>(b, 6);
-   uint64_t b7 = load_be<uint64_t>(b, 7);
-
-   const uint64_t carry0 = (b0 >> 63);
-
-   b0 = (b0 << 1) ^ (b1 >> 63);
-   b1 = (b1 << 1) ^ (b2 >> 63);
-   b2 = (b2 << 1) ^ (b3 >> 63);
-   b3 = (b3 << 1) ^ (b4 >> 63);
-   b4 = (b4 << 1) ^ (b5 >> 63);
-   b5 = (b5 << 1) ^ (b6 >> 63);
-   b6 = (b6 << 1) ^ (b7 >> 63);
-   b7 = (b7 << 1) ^ (carry0 * poly);
-
-   store_be(b0, b);
-   store_be(b1, b+8);
-   store_be(b2, b+16);
-   store_be(b3, b+24);
-   store_be(b4, b+32);
-   store_be(b5, b+40);
-   store_be(b6, b+48);
-   store_be(b7, b+56);
+   switch(n)
+      {
+      case 8:
+         return poly_double_le<1, 0x1B>(out, in);
+      case 16:
+         return poly_double_le<2, 0x87>(out, in);
+      case 24:
+         return poly_double_le<3, 0x87>(out, in);
+      case 32:
+         return poly_double_le<4, 0x425>(out, in);
+      case 64:
+         return poly_double_le<8, 0x125>(out, in);
+      default:
+         throw Invalid_Argument("Unsupported size for poly_double_n_le");
+      }
    }
 
 }
diff --git a/src/lib/utils/poly_dbl.h b/src/lib/utils/poly_dbl.h
index df3b419c3..c79af3ada 100644
--- a/src/lib/utils/poly_dbl.h
+++ b/src/lib/utils/poly_dbl.h
@@ -11,14 +11,20 @@
 
 namespace Botan {
 
-void BOTAN_DLL poly_double_n(uint8_t b[], size_t n);
+/**
+* Polynomial doubling in GF(2^n)
+*/
+void BOTAN_DLL poly_double_n(uint8_t out[], const uint8_t in[], size_t n);
 
-void poly_double_8(uint8_t b[8]);
-void poly_double_16(uint8_t b[16]);
-void poly_double_24(uint8_t b[24]);
-void poly_double_32(uint8_t b[32]);
-void poly_double_64(uint8_t b[64]);
+inline void poly_double_n(uint8_t buf[], size_t n)
+   {
+   return poly_double_n(buf, buf, n);
+   }
 
+/*
+* Little endian convention - used for XTS
+*/
+void poly_double_n_le(uint8_t out[], const uint8_t in[], size_t n);
 
 }
 
diff --git a/src/tests/data/modes/xts.vec b/src/tests/data/modes/xts.vec
index 99e8da0d5..7cff8346f 100644
--- a/src/tests/data/modes/xts.vec
+++ b/src/tests/data/modes/xts.vec
@@ -3583,3 +3583,16 @@ Nonce = F55B4EA476A09C16
 In = F3BF6B544D792A514B0E9A105DB900B4C5E649A4DDBF9C32400E296F8DE37C00788A1D8DA34AA4AB46C6F37A8C6B793E71F85BFE935C0D616D762749475E0539F690AA5ABF21D7995F6136910908EE9A9BB9876B9B26FB3038BE7293ED9116A5CC048B5B928FE4B72658061CF212E76A76E0B6C5C3D516BB09184A42E4F795FF8651EC6E999C3AAB35F8719BF72EF5AD6E60AF88185A68DECF957056418CD470D2180221B0897EE24BC7545E799AD8B6540CE30CDBB87E1444C54605833C592884C0A894869FA9C2129BADEEB32D4A23BDBE8A3EBABFBE735B601A693013E61478463D67818E2A3607D2CD4D24D069CB9AAA66D4ACB4CB0B065DF929BF97797C5CB1015DDF8BD33F5F503CB2159F64F748F543188FF8EBEA71A6A669907B117DF1535113A8E0FCA60AA095A43CAE9B21D20540C0D869CD7A970B16DAE3E52E84ECDD4DA73CB56763F72158D93AA6BC10A0456DDF54D4E23E47B0D0E4D376F90B10CAB0D6CE9EEB0792894B29104182B032BFA6F2812AF43CC05EF13BC7AFAA7469E133FDEF68823F8D700D6D88BFBD04F13C1F692785A31A36B53CF9AEE267EE4517C822BB9CCA44FA294601DFD0FB452B40C374E09542B0FA05AA264D35233F82C2C202FBFFDC50665740732F114B11CCC4BF786E0DBAD56D730AC05E12EC234BA17418154A968E946F87F7813479339911D16F3422B483F9B0FAB0E20B17549D2BB46E5BCB76
 Out = 29DF14368A0F03474DCBB394BED5227EF922C15EBE44718169EE7047D66EFFFA2E36AD3C4F3C1FC3759F9742B6E51356F3262AFE48A4D8ACAACE5B57B795BC8BA11A8609ED34A96B59A3051D3CD5668DD8A15796E8CBE2821525438043C7CEF181BF3E146D9905AA67457C07BBFA4D080E86EEBEA9324D57EF8D790CB10C643058CF5BE170A7BF0B03CEA9AA81B76A6A090B8FCCDDD159195C3D129D0D6692AEDCD6561CC61DE0EC9AD3A84EA6AD1178811113E84328E0F50B90AE9A23921FA545F58BA6E9B8F885FAA72B89952A6E889322948A7AF42896C80C03E0E1708A961DE724CB7607EB00BB6362C6E5C0826A40DE29DB0CC05E29D7880A9B3CA3776E6A435674C60C2CEB8B2EC3B386FB3F46A86935F5D1590DCC0815EADCD070A250BAB2464F0CD85AA8552C5506488602EBB46F80C3E6F9D5FE9F1BA1E8E3B94E4DB55FBDD3628BE894F35A932662B358BDE9E8EFEF273CD35A3605381E3DFB7FB5B1FB64F084D645C337C06376E3E1C30533036A2079DEFE4EB076EF7D254AC0848DE99AC6B6BFEB18AC14D531EF98C4B4F71813F82F5A76435C587BF0027AA376B24D09AA990B1EEC6E292E46A462B192E0B8EB85110F7B5870113E031D10E29B9B02A9AD8C52D397D3F77AD810364E66A0DCBF04B6948DC322A11980495A6B121F8B3A8CE2EC4477F96E9832FBD3D777547A1B0199BF7696094AD2883F643A81FA4580D5E73CFC
 
+[SHACAL2/XTS]
+# This was generated by Botan
+Key = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
+Nonce = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
+In    = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
+Out   = BD07DC61483564F517087264D85338B3D3A8FD7AE68C74A52E454916DB66597366
+
+[Threefish-512/XTS]
+# This was generated by Botan
+Key = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
+Nonce = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
+In    = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
+Out   = F188D041F059F2E68829F275DCCBCD3090369B809DEBCF88D97D0BF5EA18F6C6BF52ED5ECE77C8C8707252DB9CD1F1D6149BEEC981EB559232C701B434CD52F5AE