Add Scrypt key dervation function

6 files changed, 161 insertions, 8 deletions

diff --git a/src/lib/asn1/oid_maps.cpp b/src/lib/asn1/oid_maps.cpp
index e9c671d16..7ba7dda70 100644
--- a/src/lib/asn1/oid_maps.cpp
+++ b/src/lib/asn1/oid_maps.cpp
@@ -1,7 +1,7 @@
 /*
 * OID maps
 *
-* This file was automatically generated by ./src/scripts/oids.py on 2018-05-02
+* This file was automatically generated by ./src/scripts/oids.py on 2018-05-16
 *
 * All manual edits to this file will be lost. Edit the script
 * then regenerate this source file.
@@ -115,6 +115,7 @@ std::unordered_map<std::string, std::string> OIDS::load_oid2str_map()
       { "1.3.36.3.3.2.8.1.1.9", "brainpool320r1" },
       { "1.3.6.1.4.1.11591.12.2", "Tiger(24,3)" },
       { "1.3.6.1.4.1.11591.15.1", "OpenPGP.Ed25519" },
+      { "1.3.6.1.4.1.11591.4.11", "Scrypt" },
       { "1.3.6.1.4.1.25258.1.3", "McEliece" },
       { "1.3.6.1.4.1.25258.1.5", "XMSS" },
       { "1.3.6.1.4.1.25258.1.6.1", "GOST-34.10/EMSA1(SHA-256)" },
@@ -351,6 +352,7 @@ std::unordered_map<std::string, OID> OIDS::load_str2oid_map()
       { "SM2_Kex", OID({1,2,156,10197,1,301,2}) },
       { "SM2_Sig", OID({1,2,156,10197,1,301,1}) },
       { "SM3", OID({1,2,156,10197,1,401}) },
+      { "Scrypt", OID({1,3,6,1,4,1,11591,4,11}) },
       { "Serpent/CBC", OID({1,3,6,1,4,1,25258,3,1}) },
       { "Serpent/GCM", OID({1,3,6,1,4,1,25258,3,101}) },
       { "Serpent/OCB", OID({1,3,6,1,4,1,25258,3,2,4}) },
diff --git a/src/lib/pbkdf/scrypt/info.txt b/src/lib/pbkdf/scrypt/info.txt
new file mode 100644
index 000000000..cd1551d3b
--- /dev/null
+++ b/src/lib/pbkdf/scrypt/info.txt
@@ -0,0 +1,10 @@
+<defines>
+SCRYPT -> 20180515
+</defines>
+
+<requires>
+salsa20
+pbkdf2
+hmac
+sha2_32
+</requires>
diff --git a/src/lib/pbkdf/scrypt/scrypt.cpp b/src/lib/pbkdf/scrypt/scrypt.cpp
new file mode 100644
index 000000000..81170bf89
--- /dev/null
+++ b/src/lib/pbkdf/scrypt/scrypt.cpp
@@ -0,0 +1,98 @@
+/**
+* (C) 2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/scrypt.h>
+#include <botan/pbkdf2.h>
+#include <botan/salsa20.h>
+#include <botan/loadstor.h>
+#include <botan/internal/bit_ops.h>
+
+namespace Botan {
+
+namespace {
+
+void scryptBlockMix(size_t r, uint8_t* B, uint8_t* Y)
+   {
+   uint32_t B32[16];
+   secure_vector<uint8_t> X(64);
+   copy_mem(X.data(), &B[(2*r-1)*64], 64);
+
+   for(size_t i = 0; i != 2*r; i++)
+      {
+      xor_buf(X.data(), &B[64*i], 64);
+      load_le<uint32_t>(B32, X.data(), 16);
+      Salsa20::salsa_core(X.data(), B32, 8);
+      copy_mem(&Y[64*i], X.data(), 64);
+      }
+
+   for(size_t i = 0; i < r; ++i)
+      {
+      copy_mem(&B[i*64], &Y[(i * 2) * 64], 64);
+      }
+
+   for(size_t i = 0; i < r; ++i)
+      {
+      copy_mem(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64);
+      }
+   }
+
+void scryptROMmix(size_t r, size_t N, uint8_t* B, secure_vector<uint8_t>& V)
+   {
+   const size_t S = 128 * r;
+
+   for(size_t i = 0; i != N; ++i)
+      {
+      copy_mem(&V[S*i], B, S);
+      scryptBlockMix(r, B, &V[N*S]);
+      }
+
+   for(size_t i = 0; i != N; ++i)
+      {
+      // compiler doesn't know here that N is power of 2
+      const size_t j = load_le<uint32_t>(&B[(2*r-1)*64], 0) & (N - 1);
+      xor_buf(B, &V[j*S], S);
+      scryptBlockMix(r, B, &V[N*S]);
+      }
+   }
+
+}
+
+void scrypt(uint8_t output[], size_t output_len,
+            const std::string& password,
+            const uint8_t salt[], size_t salt_len,
+            size_t N, size_t r, size_t p)
+   {
+   // Upper bounds here are much lower than scrypt maximums yet seem sufficient
+   BOTAN_ARG_CHECK(p <= 128, "Invalid scrypt p");
+   BOTAN_ARG_CHECK(N <= 4194304 && is_power_of_2(N), "Invalid scrypt N");
+   BOTAN_ARG_CHECK(r <= 64, "Invalid scrypt r");
+
+   const size_t S = 128 * r;
+   secure_vector<uint8_t> B(p * S);
+
+   PKCS5_PBKDF2 pbkdf2(MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)").release());
+
+   pbkdf2.pbkdf(B.data(), B.size(),
+                password,
+                salt, salt_len,
+                1, std::chrono::milliseconds(0));
+
+   // temp space
+   secure_vector<uint8_t> V((N+1) * S);
+
+   // these can be parallel
+   for(size_t i = 0; i != p; ++i)
+      {
+      scryptROMmix(r, N, &B[128*r*i], V);
+      }
+
+   pbkdf2.pbkdf(output, output_len,
+                password,
+                B.data(), B.size(),
+                1, std::chrono::milliseconds(0));
+   }
+
+}
diff --git a/src/lib/pbkdf/scrypt/scrypt.h b/src/lib/pbkdf/scrypt/scrypt.h
new file mode 100644
index 000000000..5eaa3a4fc
--- /dev/null
+++ b/src/lib/pbkdf/scrypt/scrypt.h
@@ -0,0 +1,38 @@
+/**
+* (C) 2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_SCRYPT_H_
+#define BOTAN_SCRYPT_H_
+
+#include <botan/types.h>
+#include <string>
+
+namespace Botan {
+
+/**
+* Scrypt key derivation function (RFC 7914)
+*
+* @param output the output will be placed here
+* @param output_len length of output
+* @param password the user password
+* @param salt the salt
+* @param salt_len length of salt
+* @param N the CPU/Memory cost parameter, must be power of 2
+* @param r the block size parameter
+* @param p the parallelization parameter
+*
+* Suitable parameters for most uses would be N = 16384, r = 8, p = 1
+*
+* Scrypt uses approximately (p + N + 1) * 128 * r bytes of memory
+*/
+void BOTAN_UNSTABLE_API scrypt(uint8_t output[], size_t output_len,
+                               const std::string& password,
+                               const uint8_t salt[], size_t salt_len,
+                               size_t N, size_t r, size_t p);
+
+}
+
+#endif
diff --git a/src/lib/stream/salsa20/salsa20.cpp b/src/lib/stream/salsa20/salsa20.cpp
index 46499e69e..faba12cdd 100644
--- a/src/lib/stream/salsa20/salsa20.cpp
+++ b/src/lib/stream/salsa20/salsa20.cpp
@@ -54,17 +54,22 @@ void hsalsa20(uint32_t output[8], const uint32_t input[16])
    output[7] = x09;
    }
 
+}
+
 /*
 * Generate Salsa20 cipher stream
 */
-void salsa20(uint8_t output[64], const uint32_t input[16])
+//static
+void Salsa20::salsa_core(uint8_t output[64], const uint32_t input[16], size_t rounds)
    {
+   BOTAN_ASSERT_NOMSG(rounds % 2 == 0);
+
    uint32_t x00 = input[ 0], x01 = input[ 1], x02 = input[ 2], x03 = input[ 3],
             x04 = input[ 4], x05 = input[ 5], x06 = input[ 6], x07 = input[ 7],
             x08 = input[ 8], x09 = input[ 9], x10 = input[10], x11 = input[11],
             x12 = input[12], x13 = input[13], x14 = input[14], x15 = input[15];
 
-   for(size_t i = 0; i != 10; ++i)
+   for(size_t i = 0; i != rounds / 2; ++i)
       {
       SALSA20_QUARTER_ROUND(x00, x04, x08, x12);
       SALSA20_QUARTER_ROUND(x05, x09, x13, x01);
@@ -95,8 +100,6 @@ void salsa20(uint8_t output[64], const uint32_t input[16])
    store_le(x15 + input[15], output + 4 * 15);
    }
 
-}
-
 #undef SALSA20_QUARTER_ROUND
 
 /*
@@ -112,7 +115,7 @@ void Salsa20::cipher(const uint8_t in[], uint8_t out[], size_t length)
       length -= (m_buffer.size() - m_position);
       in += (m_buffer.size() - m_position);
       out += (m_buffer.size() - m_position);
-      salsa20(m_buffer.data(), m_state.data());
+      salsa_core(m_buffer.data(), m_state.data(), 20);
 
       ++m_state[8];
       m_state[9] += (m_state[8] == 0);
@@ -210,7 +213,7 @@ void Salsa20::set_iv(const uint8_t iv[], size_t length)
    m_state[8] = 0;
    m_state[9] = 0;
 
-   salsa20(m_buffer.data(), m_state.data());
+   salsa_core(m_buffer.data(), m_state.data(), 20);
    ++m_state[8];
    m_state[9] += (m_state[8] == 0);
 
@@ -247,7 +250,7 @@ void Salsa20::seek(uint64_t offset)
    m_state[8]  = load_le<uint32_t>(counter8, 0);
    m_state[9] += load_le<uint32_t>(counter8, 1);
 
-   salsa20(m_buffer.data(), m_state.data());
+   salsa_core(m_buffer.data(), m_state.data(), 20);
 
    ++m_state[8];
    m_state[9] += (m_state[8] == 0);
diff --git a/src/lib/stream/salsa20/salsa20.h b/src/lib/stream/salsa20/salsa20.h
index a9a68c537..d21ee318e 100644
--- a/src/lib/stream/salsa20/salsa20.h
+++ b/src/lib/stream/salsa20/salsa20.h
@@ -34,6 +34,8 @@ class BOTAN_PUBLIC_API(2,0) Salsa20 final : public StreamCipher
       std::string name() const override;
       StreamCipher* clone() const override { return new Salsa20; }
 
+      static void salsa_core(uint8_t output[64], const uint32_t input[16], size_t rounds);
+
       void seek(uint64_t offset) override;
    private:
       void key_schedule(const uint8_t key[], size_t key_len) override;