Add SHAKE-128 as stream cipher

Updates NewHope to use that instead of the hard-coded SHAKE-128,
and adds toggle for BoringSSL compat mode using AES-128/CTR + SHA-256.

8 files changed, 240 insertions, 106 deletions

diff --git a/src/lib/pubkey/newhope/info.txt b/src/lib/pubkey/newhope/info.txt
index 08b68fc7a..74ceef989 100644
--- a/src/lib/pubkey/newhope/info.txt
+++ b/src/lib/pubkey/newhope/info.txt
@@ -1,5 +1,10 @@
-define NEWHOPE 20160829
+define NEWHOPE 20161018
 
 <requires>
 sha3
+shake_cipher
+
+sha2_32
+ctr
+aes
 </requires>
diff --git a/src/lib/pubkey/newhope/newhope.cpp b/src/lib/pubkey/newhope/newhope.cpp
index 25168cc58..35645e93c 100644
--- a/src/lib/pubkey/newhope/newhope.cpp
+++ b/src/lib/pubkey/newhope/newhope.cpp
@@ -10,7 +10,8 @@
 */
 
 #include <botan/newhope.h>
-#include <botan/sha3.h>
+#include <botan/hash.h>
+#include <botan/stream_cipher.h>
 #include <botan/loadstor.h>
 
 namespace Botan {
@@ -24,8 +25,6 @@ typedef newhope_poly poly;
 #define NEWHOPE_POLY_BYTES 1792
 #define NEWHOPE_SEED_BYTES 32
 
-#define SHAKE128_RATE 168
-
 namespace {
 
 /* Incomplete-reduction routines; for details on allowed input ranges
@@ -422,115 +421,57 @@ inline void rec(uint8_t *key, const poly *v, const poly *c)
   }
 }
 
-/* Based on the public domain implementation in
- * crypto_hash/keccakc512/simple/ from http://bench.cr.yp.to/supercop.html
- * by Ronny Van Keer
- * and the public domain "TweetFips202" implementation
- * from https://twitter.com/tweetfips202
- * by Gilles Van Assche, Daniel J. Bernstein, and Peter Schwabe */
-
-void keccak_absorb(uint64_t *s,
-                   unsigned int r,
-                   const uint8_t *m, size_t mlen,
-                   uint8_t p)
-{
-  size_t i;
-  uint8_t t[200];
-
-  for (i = 0; i < 25; ++i)
-    s[i] = 0;
-
-  while (mlen >= r)
-  {
-    for (i = 0; i < r / 8; ++i)
-       s[i] ^= load_le<u64bit>(m, i);
-
-    SHA_3::permute(s);
-    mlen -= r;
-    m += r;
-  }
-
-  for (i = 0; i < r; ++i)
-    t[i] = 0;
-  for (i = 0; i < mlen; ++i)
-    t[i] = m[i];
-  t[i] = p;
-  t[r - 1] |= 128;
-  for (i = 0; i < r / 8; ++i)
-     s[i] ^= load_le<u64bit>(t, i);
-}
-
-inline void keccak_squeezeblocks(uint8_t *h, size_t nblocks,
-                                 uint64_t *s, unsigned int r)
-{
-  while(nblocks > 0)
-     {
-     SHA_3::permute(s);
-
-     copy_out_le(h, r, s);
-
-     h += r;
-     nblocks--;
-     }
-}
-
-inline void shake128_absorb(uint64_t *s, const uint8_t *input, size_t inputByteLen)
-{
-  keccak_absorb(s, SHAKE128_RATE, input, inputByteLen, 0x1F);
-}
-
-inline void shake128_squeezeblocks(uint8_t *output, size_t nblocks, uint64_t *s)
-{
-  keccak_squeezeblocks(output, nblocks, s, SHAKE128_RATE);
-}
-
-void gen_a(poly *a, const uint8_t *seed)
-{
-  unsigned int pos=0, ctr=0;
-  uint16_t val;
-  uint64_t state[25];
-  unsigned int nblocks=16;
-  uint8_t buf[SHAKE128_RATE*16];
+void gen_a(poly *a, const uint8_t *seed, Newhope_Mode mode)
+   {
+   std::vector<uint8_t> buf(168*16);
 
-  shake128_absorb(state, seed, NEWHOPE_SEED_BYTES);
+   std::unique_ptr<StreamCipher> xof;
 
-  shake128_squeezeblocks((uint8_t *) buf, nblocks, state);
+   if(mode == Newhope_Mode::BoringSSL)
+      {
+      xof = StreamCipher::create("CTR(AES-128)");
+      xof->set_key(seed, 16);
+      xof->set_iv(seed + 16, 16);
+      }
+   else
+      {
+      xof = StreamCipher::create("SHAKE-128");
+      xof->set_key(seed, NEWHOPE_SEED_BYTES);
+      }
 
-  while(ctr < PARAM_N)
-  {
-    val = (buf[pos] | ((uint16_t) buf[pos+1] << 8)) & 0x3fff; // Specialized for q = 12889
-    if(val < PARAM_Q)
-      a->coeffs[ctr++] = val;
-    pos += 2;
-    if(pos > SHAKE128_RATE*nblocks-2)
-    {
-      nblocks=1;
-      shake128_squeezeblocks((uint8_t *) buf,nblocks,state);
-      pos = 0;
-    }
-  }
-}
+   zeroise(buf);
+   xof->encrypt(buf);
 
-void newhope_hash(uint8_t *output, const uint8_t *input, size_t inputByteLen)
-   {
-   SHA_3_256 sha3;
+   unsigned int pos=0, ctr=0;
 
-   sha3.update(input, inputByteLen);
-   sha3.final(output);
-}
+   while(ctr < PARAM_N)
+      {
+      uint16_t val = (buf[pos] | ((uint16_t) buf[pos+1] << 8)) & 0x3fff; // Specialized for q = 12889
+      if(val < PARAM_Q)
+         a->coeffs[ctr++] = val;
+      pos += 2;
+      if(pos >= buf.size())
+         {
+         zeroise(buf);
+         xof->encrypt(buf);
+         pos = 0;
+         }
+      }
+   }
 
 }
 
 // API FUNCTIONS
 
-void newhope_keygen(uint8_t *send, poly *sk, RandomNumberGenerator& rng)
+void newhope_keygen(uint8_t *send, poly *sk, RandomNumberGenerator& rng,
+                    Newhope_Mode mode)
 {
   poly a, e, r, pk;
   uint8_t seed[NEWHOPE_SEED_BYTES];
 
   rng.randomize(seed, NEWHOPE_SEED_BYTES);
 
-  gen_a(&a, seed);
+  gen_a(&a, seed, mode);
 
   poly_getnoise(rng, sk);
   poly_ntt(sk);
@@ -545,13 +486,14 @@ void newhope_keygen(uint8_t *send, poly *sk, RandomNumberGenerator& rng)
 }
 
 void newhope_sharedb(uint8_t *sharedkey, uint8_t *send, const uint8_t *received,
-                     RandomNumberGenerator& rng)
+                     RandomNumberGenerator& rng,
+                     Newhope_Mode mode)
 {
   poly sp, ep, v, a, pka, c, epp, bp;
   uint8_t seed[NEWHOPE_SEED_BYTES];
 
   decode_a(&pka, seed, received);
-  gen_a(&a, seed);
+  gen_a(&a, seed, mode);
 
   poly_getnoise(rng, &sp);
   poly_ntt(&sp);
@@ -573,11 +515,19 @@ void newhope_sharedb(uint8_t *sharedkey, uint8_t *send, const uint8_t *received,
 
   rec(sharedkey, &v, &c);
 
-  newhope_hash(sharedkey, sharedkey, 32);
+  std::unique_ptr<HashFunction> hash(HashFunction::create(
+     (mode == Newhope_Mode::SHA3) ? "SHA-3(256)" : "SHA-256"));
+
+  if(!hash)
+     throw Exception("NewHope hash function not available");
+
+  hash->update(sharedkey, 32);
+  hash->final(sharedkey);
 }
 
 
-void newhope_shareda(uint8_t *sharedkey, const poly *sk, const uint8_t *received)
+void newhope_shareda(uint8_t *sharedkey, const poly *sk, const uint8_t *received,
+                     Newhope_Mode mode)
 {
   poly v,bp, c;
 
@@ -588,7 +538,14 @@ void newhope_shareda(uint8_t *sharedkey, const poly *sk, const uint8_t *received
 
   rec(sharedkey, &v, &c);
 
-  newhope_hash(sharedkey, sharedkey, 32);
+  std::unique_ptr<HashFunction> hash(HashFunction::create(
+     (mode == Newhope_Mode::SHA3) ? "SHA-3(256)" : "SHA-256"));
+
+  if(!hash)
+     throw Exception("NewHope hash function not available");
+
+  hash->update(sharedkey, 32);
+  hash->final(sharedkey);
 }
 
 }
diff --git a/src/lib/pubkey/newhope/newhope.h b/src/lib/pubkey/newhope/newhope.h
index 875c6e092..667f1c4cf 100644
--- a/src/lib/pubkey/newhope/newhope.h
+++ b/src/lib/pubkey/newhope/newhope.h
@@ -28,9 +28,33 @@ typedef struct {
   uint16_t coeffs[1024];
 } newhope_poly;
 
-void BOTAN_DLL newhope_keygen(uint8_t *send, newhope_poly *sk, RandomNumberGenerator& rng);
-void BOTAN_DLL newhope_sharedb(uint8_t *sharedkey, uint8_t *send, const uint8_t *received, RandomNumberGenerator& rng);
-void BOTAN_DLL newhope_shareda(uint8_t *sharedkey, const newhope_poly *ska, const uint8_t *received);
+/**
+* This chooses the XOF + hash for NewHope
+
+* The official NewHope specification and reference implementation use
+* SHA-3 and SHAKE-128. BoringSSL instead uses SHA-256 and AES-128 in
+* CTR mode.
+*/
+enum class Newhope_Mode {
+   SHA3,
+   BoringSSL
+};
+
+void BOTAN_DLL newhope_keygen(uint8_t *send,
+                              newhope_poly *sk,
+                              RandomNumberGenerator& rng,
+                              Newhope_Mode = Newhope_Mode::SHA3);
+
+void BOTAN_DLL newhope_sharedb(uint8_t *sharedkey,
+                               uint8_t *send,
+                               const uint8_t *received,
+                               RandomNumberGenerator& rng,
+                               Newhope_Mode mode = Newhope_Mode::SHA3);
+
+void BOTAN_DLL newhope_shareda(uint8_t *sharedkey,
+                               const newhope_poly *ska,
+                               const uint8_t *received,
+                               Newhope_Mode mode = Newhope_Mode::SHA3);
 
 }
 
diff --git a/src/lib/stream/salsa20/salsa20.cpp b/src/lib/stream/salsa20/salsa20.cpp
index f11fe5e59..0d8942789 100644
--- a/src/lib/stream/salsa20/salsa20.cpp
+++ b/src/lib/stream/salsa20/salsa20.cpp
@@ -163,7 +163,7 @@ void Salsa20::key_schedule(const byte key[], size_t length)
    }
 
 /*
-* Return the name of this type
+* Set the Salsa IV
 */
 void Salsa20::set_iv(const byte iv[], size_t length)
    {
diff --git a/src/lib/stream/shake_cipher/info.txt b/src/lib/stream/shake_cipher/info.txt
new file mode 100644
index 000000000..53e6f5012
--- /dev/null
+++ b/src/lib/stream/shake_cipher/info.txt
@@ -0,0 +1 @@
+define SHAKE_CIPHER 20161018
diff --git a/src/lib/stream/shake_cipher/shake_cipher.cpp b/src/lib/stream/shake_cipher/shake_cipher.cpp
new file mode 100644
index 000000000..5701e7802
--- /dev/null
+++ b/src/lib/stream/shake_cipher/shake_cipher.cpp
@@ -0,0 +1,75 @@
+/*
+* SHAKE-128
+* (C) 2016 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/shake_cipher.h>
+#include <botan/sha3.h>
+#include <botan/loadstor.h>
+
+namespace Botan {
+
+SHAKE_128::SHAKE_128() :
+   m_state(25),
+   m_buffer((1600 - 256) / 8),
+   m_buf_pos(0)
+   {}
+
+void SHAKE_128::cipher(const byte in[], byte out[], size_t length)
+   {
+   while(length >= m_buffer.size() - m_buf_pos)
+      {
+      xor_buf(out, in, &m_buffer[m_buf_pos], m_buffer.size() - m_buf_pos);
+      length -= (m_buffer.size() - m_buf_pos);
+      in += (m_buffer.size() - m_buf_pos);
+      out += (m_buffer.size() - m_buf_pos);
+
+      SHA_3::permute(m_state.data());
+      copy_out_le(m_buffer.data(), m_buffer.size(), m_state.data());
+
+      m_buf_pos = 0;
+      }
+   xor_buf(out, in, &m_buffer[m_buf_pos], length);
+   m_buf_pos += length;
+   }
+
+void SHAKE_128::key_schedule(const byte key[], size_t length)
+   {
+   zeroise(m_state);
+
+   for(size_t i = 0; i < length/8; ++i)
+      {
+      m_state[i] ^= load_le<uint64_t>(key, i);
+      }
+
+   m_state[length/8] ^= 0x000000000000001F;
+   m_state[20]       ^= 0x8000000000000000;
+
+   SHA_3::permute(m_state.data());
+   copy_out_le(m_buffer.data(), m_buffer.size(), m_state.data());
+   }
+
+void SHAKE_128::clear()
+   {
+   zeroise(m_state);
+   zeroise(m_buffer);
+   m_buf_pos = 0;
+   }
+
+void SHAKE_128::set_iv(const byte[], size_t length)
+   {
+   /*
+   * This could be supported in some way (say, by treating iv as
+   * a prefix or suffix of the key).
+   */
+   if(length != 0)
+      throw Invalid_IV_Length(name(), length);
+   }
+
+void SHAKE_128::seek(u64bit)
+   {
+   throw Not_Implemented("SHAKE_128::seek");
+   }
+}
diff --git a/src/lib/stream/shake_cipher/shake_cipher.h b/src/lib/stream/shake_cipher/shake_cipher.h
new file mode 100644
index 000000000..57eda58a4
--- /dev/null
+++ b/src/lib/stream/shake_cipher/shake_cipher.h
@@ -0,0 +1,64 @@
+/*
+* SHAKE-128 as a stream cipher
+* (C) 2016 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_SHAKE128_CIPHER_H__
+#define BOTAN_SHAKE128_CIPHER_H__
+
+#include <botan/stream_cipher.h>
+#include <botan/secmem.h>
+
+namespace Botan {
+
+/**
+* SHAKE-128 XOF presented as a stream cipher
+*/
+class BOTAN_DLL SHAKE_128 final : public StreamCipher
+   {
+   public:
+      SHAKE_128();
+
+      /**
+      * Produce more XOF output
+      */
+      void cipher(const byte in[], byte out[], size_t length) override;
+
+      /**
+      * Seeking is not supported, this function will throw
+      */
+      void seek(u64bit offset) override;
+
+      /**
+      * IV not supported, this function will throw unless iv_len == 0
+      */
+      void set_iv(const byte iv[], size_t iv_len) override;
+
+      bool valid_iv_length(size_t iv_len) const override { return (iv_len == 0); }
+
+      /**
+      * In principle SHAKE can accept arbitrary length inputs, but this
+      * does not seem required for a stream cipher.
+      */
+      Key_Length_Specification key_spec() const override
+         {
+         return Key_Length_Specification(16, 160, 8);
+         }
+
+      void clear() override;
+      std::string name() const override { return "SHAKE-128"; }
+      StreamCipher* clone() const override { return new SHAKE_128; }
+
+   private:
+      void key_schedule(const byte key[], size_t key_len) override;
+
+      secure_vector<uint64_t> m_state; // internal state
+      secure_vector<byte> m_buffer; // ciphertext buffer
+      size_t m_buf_pos; // position in m_buffer
+   };
+
+}
+
+#endif
diff --git a/src/lib/stream/stream_cipher.cpp b/src/lib/stream/stream_cipher.cpp
index cd6400d8f..7c41722a0 100644
--- a/src/lib/stream/stream_cipher.cpp
+++ b/src/lib/stream/stream_cipher.cpp
@@ -16,6 +16,10 @@
   #include <botan/salsa20.h>
 #endif
 
+#if defined(BOTAN_HAS_SHAKE_CIPHER)
+  #include <botan/shake_cipher.h>
+#endif
+
 #if defined(BOTAN_HAS_CTR_BE)
   #include <botan/ctr.h>
 #endif
@@ -52,6 +56,10 @@ BOTAN_REGISTER_T_1LEN(StreamCipher, ChaCha, 20);
 BOTAN_REGISTER_T_NOARGS(StreamCipher, Salsa20);
 #endif
 
+#if defined(BOTAN_HAS_SHAKE_CIPHER)
+BOTAN_REGISTER_NAMED_T(StreamCipher, "SHAKE-128", SHAKE_128, make_new_T<SHAKE_128>);
+#endif
+
 #if defined(BOTAN_HAS_CTR_BE)
 BOTAN_REGISTER_NAMED_T(StreamCipher, "CTR-BE", CTR_BE, CTR_BE::make);
 #endif