Add Poly1305, based on poly1305-donna by Andrew Moon.

8 files changed, 298 insertions, 11 deletions

diff --git a/src/lib/engine/core_engine/lookup_mac.cpp b/src/lib/engine/core_engine/lookup_mac.cpp
index 32275b559..acb8da019 100644
--- a/src/lib/engine/core_engine/lookup_mac.cpp
+++ b/src/lib/engine/core_engine/lookup_mac.cpp
@@ -21,6 +21,10 @@
   #include <botan/hmac.h>
 #endif
 
+#if defined(BOTAN_HAS_POLY1305)
+  #include <botan/poly1305.h>
+#endif
+
 #if defined(BOTAN_HAS_SSL3_MAC)
   #include <botan/ssl3_mac.h>
 #endif
@@ -38,10 +42,9 @@ MessageAuthenticationCode*
 Core_Engine::find_mac(const SCAN_Name& request,
                       Algorithm_Factory& af) const
    {
-
-#if defined(BOTAN_HAS_CBC_MAC)
-   if(request.algo_name() == "CBC-MAC" && request.arg_count() == 1)
-      return new CBC_MAC(af.make_block_cipher(request.arg(0)));
+#if defined(BOTAN_HAS_HMAC)
+   if(request.algo_name() == "HMAC" && request.arg_count() == 1)
+      return new HMAC(af.make_hash_function(request.arg(0)));
 #endif
 
 #if defined(BOTAN_HAS_CMAC)
@@ -49,9 +52,14 @@ Core_Engine::find_mac(const SCAN_Name& request,
       return new CMAC(af.make_block_cipher(request.arg(0)));
 #endif
 
-#if defined(BOTAN_HAS_HMAC)
-   if(request.algo_name() == "HMAC" && request.arg_count() == 1)
-      return new HMAC(af.make_hash_function(request.arg(0)));
+#if defined(BOTAN_HAS_POLY1305)
+   if(request.algo_name() == "Poly1305")
+      return new Poly1305;
+#endif
+
+#if defined(BOTAN_HAS_CBC_MAC)
+   if(request.algo_name() == "CBC-MAC" && request.arg_count() == 1)
+      return new CBC_MAC(af.make_block_cipher(request.arg(0)));
 #endif
 
 #if defined(BOTAN_HAS_SSL3_MAC)
diff --git a/src/lib/mac/poly1305/info.txt b/src/lib/mac/poly1305/info.txt
new file mode 100644
index 000000000..84491aa41
--- /dev/null
+++ b/src/lib/mac/poly1305/info.txt
@@ -0,0 +1,9 @@
+define POLY1305 20141227
+
+<header:public>
+poly1305.h
+</header:public>
+
+<header:internal>
+poly1305_donna.h
+</header:internal>
diff --git a/src/lib/mac/poly1305/poly1305.cpp b/src/lib/mac/poly1305/poly1305.cpp
new file mode 100644
index 000000000..32ab64d7e
--- /dev/null
+++ b/src/lib/mac/poly1305/poly1305.cpp
@@ -0,0 +1,73 @@
+/*
+* Poly1305
+* (C) 2014 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/poly1305.h>
+#include <botan/internal/poly1305_donna.h>
+
+namespace Botan {
+
+void Poly1305::clear()
+   {
+   zap(m_poly);
+   zap(m_buf);
+   m_buf_pos = 0;
+   }
+
+void Poly1305::key_schedule(const byte key[], size_t key_len)
+   {
+   m_buf_pos = 0;
+   m_buf.resize(16);
+   m_poly.resize(8);
+
+   poly1305_init(m_poly, key);
+   }
+
+void Poly1305::add_data(const byte input[], size_t length)
+   {
+   BOTAN_ASSERT_EQUAL(m_poly.size(), 8, "Initialized");
+
+   if(m_buf_pos)
+      {
+      buffer_insert(m_buf, m_buf_pos, input, length);
+
+      if(m_buf_pos + length >= m_buf.size())
+         {
+         poly1305_blocks(m_poly, &m_buf[0], 1);
+         input += (m_buf.size() - m_buf_pos);
+         length -= (m_buf.size() - m_buf_pos);
+         m_buf_pos = 0;
+         }
+      }
+
+   const size_t full_blocks = length / m_buf.size();
+   const size_t remaining   = length % m_buf.size();
+
+   if(full_blocks)
+      poly1305_blocks(m_poly, input, full_blocks);
+
+   buffer_insert(m_buf, m_buf_pos, input + full_blocks * m_buf.size(), remaining);
+   m_buf_pos += remaining;
+   }
+
+void Poly1305::final_result(byte out[])
+   {
+   BOTAN_ASSERT_EQUAL(m_poly.size(), 8, "Initialized");
+
+   if(m_buf_pos != 0)
+      {
+      m_buf[m_buf_pos] = 1;
+      clear_mem(&m_buf[m_buf_pos+1], m_buf.size() - m_buf_pos);
+      poly1305_blocks(m_poly, &m_buf[0], 1, true);
+      }
+
+   poly1305_finish(m_poly, out);
+
+   m_poly.clear();
+   m_buf_pos = 0;
+   }
+
+}
diff --git a/src/lib/mac/poly1305/poly1305.h b/src/lib/mac/poly1305/poly1305.h
new file mode 100644
index 000000000..8334edb03
--- /dev/null
+++ b/src/lib/mac/poly1305/poly1305.h
@@ -0,0 +1,48 @@
+/*
+* Poly1305
+* (C) 2014 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#ifndef BOTAN_MAC_POLY1305_H__
+#define BOTAN_MAC_POLY1305_H__
+
+#include <botan/mac.h>
+#include <memory>
+
+namespace Botan {
+
+/**
+* DJB's Poly1305
+* Important note: each key can only be used once
+*/
+class BOTAN_DLL Poly1305 : public MessageAuthenticationCode
+   {
+   public:
+      std::string name() const override { return "Poly1305"; }
+
+      MessageAuthenticationCode* clone() const { return new Poly1305; }
+
+      void clear();
+
+      size_t output_length() const { return 16; }
+
+      Key_Length_Specification key_spec() const
+         {
+         return Key_Length_Specification(32);
+         }
+
+   private:
+      void add_data(const byte[], size_t);
+      void final_result(byte[]);
+      void key_schedule(const byte[], size_t);
+
+      secure_vector<u64bit> m_poly;
+      secure_vector<byte> m_buf;
+      size_t m_buf_pos = 0;
+   };
+
+}
+
+#endif
diff --git a/src/lib/mac/poly1305/poly1305_donna.h b/src/lib/mac/poly1305/poly1305_donna.h
new file mode 100644
index 000000000..f0f3fe387
--- /dev/null
+++ b/src/lib/mac/poly1305/poly1305_donna.h
@@ -0,0 +1,152 @@
+/*
+* Derived from poly1305-donna-64.h by Andrew Moon <[email protected]>
+* in https://github.com/floodyberry/poly1305-donna
+*
+* (C) 2014 Andrew Moon
+* (C) 2014 Jack Lloyd
+* Distributed under the terms of the Botan license
+*/
+
+#ifndef BOTAN_POLY1305_DONNA_H__
+#define BOTAN_POLY1305_DONNA_H__
+
+#include <botan/loadstor.h>
+#include <botan/mul128.h>
+
+#if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
+  #include <botan/internal/donna128.h>
+#endif
+
+namespace Botan {
+
+namespace {
+
+#if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
+typedef donna128 uint128_t;
+#else
+inline u64bit carry_shift(const uint128_t a, size_t shift)
+   {
+   return static_cast<u64bit>(a >> shift);
+   }
+#endif
+
+void poly1305_init(secure_vector<u64bit>& X, const byte key[32])
+   {
+   /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
+   const u64bit t0 = load_le<u64bit>(key, 0);
+   const u64bit t1 = load_le<u64bit>(key, 1);
+
+   X[0] = ( t0                    ) & 0xffc0fffffff;
+   X[1] = ((t0 >> 44) | (t1 << 20)) & 0xfffffc0ffff;
+   X[2] = ((t1 >> 24)             ) & 0x00ffffffc0f;
+
+   /* h = 0 */
+   X[3] = 0;
+   X[4] = 0;
+   X[5] = 0;
+
+   /* save pad for later */
+   X[6] = load_le<u64bit>(key, 2);
+   X[7] = load_le<u64bit>(key, 3);
+   }
+
+void poly1305_blocks(secure_vector<u64bit>& X, const byte *m, size_t blocks, bool is_final = false)
+   {
+   const u64bit hibit = is_final ? 0 : (static_cast<u64bit>(1) << 40); /* 1 << 128 */
+   //u64bit c;
+
+   const u64bit r0 = X[0];
+   const u64bit r1 = X[1];
+   const u64bit r2 = X[2];
+
+   u64bit h0 = X[3+0];
+   u64bit h1 = X[3+1];
+   u64bit h2 = X[3+2];
+
+   const u64bit s1 = r1 * (5 << 2);
+   const u64bit s2 = r2 * (5 << 2);
+
+   while(blocks--)
+      {
+      /* h += m[i] */
+      const u64bit t0 = load_le<u64bit>(m, 0);
+      const u64bit t1 = load_le<u64bit>(m, 1);
+
+      h0 += (( t0                    ) & 0xfffffffffff);
+      h1 += (((t0 >> 44) | (t1 << 20)) & 0xfffffffffff);
+      h2 += (((t1 >> 24)             ) & 0x3ffffffffff) | hibit;
+
+      /* h *= r */
+      uint128_t d0 = uint128_t(h0) * r0 + uint128_t(h1) * s2 + uint128_t(h2) * s1;
+      uint128_t d1 = uint128_t(h0) * r1 + uint128_t(h1) * r0 + uint128_t(h2) * s2;
+      uint128_t d2 = uint128_t(h0) * r2 + uint128_t(h1) * r1 + uint128_t(h2) * r0;
+
+      /* (partial) h %= p */
+      u64bit        c = carry_shift(d0, 44); h0 = d0 & 0xfffffffffff;
+      d1 += c;      c = carry_shift(d1, 44); h1 = d1 & 0xfffffffffff;
+      d2 += c;      c = carry_shift(d2, 42); h2 = d2 & 0x3ffffffffff;
+      h0  += c * 5; c = carry_shift(h0, 44); h0 = h0 & 0xfffffffffff;
+      h1  += c;
+
+      m += 16;
+      }
+
+   X[3+0] = h0;
+   X[3+1] = h1;
+   X[3+2] = h2;
+   }
+
+void poly1305_finish(secure_vector<u64bit>& X, byte mac[16])
+   {
+   /* fully carry h */
+   u64bit h0 = X[3+0];
+   u64bit h1 = X[3+1];
+   u64bit h2 = X[3+2];
+
+   u64bit c;
+                c = (h1 >> 44); h1 &= 0xfffffffffff;
+   h2 += c;     c = (h2 >> 42); h2 &= 0x3ffffffffff;
+   h0 += c * 5; c = (h0 >> 44); h0 &= 0xfffffffffff;
+   h1 += c;     c = (h1 >> 44); h1 &= 0xfffffffffff;
+   h2 += c;     c = (h2 >> 42); h2 &= 0x3ffffffffff;
+   h0 += c * 5; c = (h0 >> 44); h0 &= 0xfffffffffff;
+   h1 += c;
+
+   /* compute h + -p */
+   u64bit g0 = h0 + 5; c = (g0 >> 44); g0 &= 0xfffffffffff;
+   u64bit g1 = h1 + c; c = (g1 >> 44); g1 &= 0xfffffffffff;
+   u64bit g2 = h2 + c - ((u64bit)1 << 42);
+
+   /* select h if h < p, or h + -p if h >= p */
+   c = (g2 >> ((sizeof(u64bit) * 8) - 1)) - 1;
+   g0 &= c;
+   g1 &= c;
+   g2 &= c;
+   c = ~c;
+   h0 = (h0 & c) | g0;
+   h1 = (h1 & c) | g1;
+   h2 = (h2 & c) | g2;
+
+   /* h = (h + pad) */
+   const u64bit t0 = X[6];
+   const u64bit t1 = X[7];
+
+   h0 += (( t0                    ) & 0xfffffffffff)    ; c = (h0 >> 44); h0 &= 0xfffffffffff;
+   h1 += (((t0 >> 44) | (t1 << 20)) & 0xfffffffffff) + c; c = (h1 >> 44); h1 &= 0xfffffffffff;
+   h2 += (((t1 >> 24)             ) & 0x3ffffffffff) + c;                 h2 &= 0x3ffffffffff;
+
+   /* mac = h % (2^128) */
+   h0 = ((h0      ) | (h1 << 44));
+   h1 = ((h1 >> 20) | (h2 << 24));
+
+   store_le(&mac[0], h0, h1);
+
+   /* zero out the state */
+   zero_mem(&X[0], X.size());
+   }
+
+}
+
+}
+
+#endif
diff --git a/src/lib/pubkey/curve25519/info.txt b/src/lib/pubkey/curve25519/info.txt
index 68c417056..6139dc32f 100644
--- a/src/lib/pubkey/curve25519/info.txt
+++ b/src/lib/pubkey/curve25519/info.txt
@@ -3,7 +3,3 @@ define CURVE_25519 20141227
 <header:public>
 curve25519.h
 </header:public>
-
-<header:internal>
-donna128.h
-</header:internal>
diff --git a/src/lib/pubkey/curve25519/donna128.h b/src/lib/utils/donna128.h
index f2b2d88ea..f2b2d88ea 100644
--- a/src/lib/pubkey/curve25519/donna128.h
+++ b/src/lib/utils/donna128.h
diff --git a/src/lib/utils/info.txt b/src/lib/utils/info.txt
index 9ba51f193..84e1c8740 100644
--- a/src/lib/utils/info.txt
+++ b/src/lib/utils/info.txt
@@ -4,6 +4,7 @@ load_on always
 
 <header:internal>
 bit_ops.h
+donna128.h
 prefetch.h
 rounding.h
 semaphore.h