Merge GH #1570 Add Scrypt

12 files changed, 382 insertions, 9 deletions

diff --git a/doc/manual/pbkdf.rst b/doc/manual/pbkdf.rst
index c2a6f95c4..1a0ece3e8 100644
--- a/doc/manual/pbkdf.rst
+++ b/doc/manual/pbkdf.rst
@@ -86,3 +86,36 @@ be about right). Using both a reasonably sized salt and a large
 iteration count is highly recommended to prevent password guessing
 attempts.
 
+Scrypt
+----------
+
+Scrypt is a relatively newer design which is "memory hard" - in
+addition to requiring large amounts of CPU power it uses a large block
+of memory to compute the hash. This makes brute force attacks using
+ASICs substantially more expensive.
+
+Currently Scrypt uses a different interface from the standard PBKDF
+functions. This will be remedied in a future major release which
+redesigns the PBKDF interfaces.
+
+.. cpp:function:: 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)
+
+   Computes the Scrypt using the password and salt, and produces an output
+   of arbitrary length.
+
+   The N, r, p parameters control how much work and memory Scrypt
+   uses.  N is the primary control of the workfactor, and must be a
+   power of 2. For interactive logins use 32768, for protection of
+   secret keys or backups use 1048576.
+
+   The r parameter controls how 'wide' the internal hashing operation
+   is. It also increases the amount of memory that is used. Values
+   from 1 to 8 are reasonable.
+
+   Setting p parameter to greater than one splits up the work in a way
+   that up to p processors can work in parallel.
+
+   As a general recommendation, use N=32768, r=8, p=1
diff --git a/doc/todo.rst b/doc/todo.rst
index 0006e1132..7fcc693eb 100644
--- a/doc/todo.rst
+++ b/doc/todo.rst
@@ -19,7 +19,6 @@ Ciphers, Hashes, PBKDF
 * XSalsa20-Poly1305 AEAD compatible with NaCl
 * ASCON 1.2 (CAESAR)
 * NORX-64 3.0 (CAESAR)
-* scrypt PBKDF
 * Argon2 PBKDF (draft-irtf-cfrg-argon2)
 * bcrypt PBKDF
 * Skein-MAC
@@ -36,6 +35,7 @@ Public Key Crypto, Math
 * Curves for pairings (BN-256 is widely implemented)
 * Identity based encryption
 * BBS group signatures
+* Support Scrypt for private key encryption (RFC 7914)
 * Paillier homomorphic cryptosystem
 * Hashing onto an elliptic curve
 * SPHINCS-256
diff --git a/src/build-data/oids.txt b/src/build-data/oids.txt
index 0cf3d8d5d..314e4e44f 100644
--- a/src/build-data/oids.txt
+++ b/src/build-data/oids.txt
@@ -196,6 +196,8 @@
 1.2.840.113549.1.5.12 = PKCS5.PBKDF2
 1.2.840.113549.1.5.13 = PBE-PKCS5v20
 
+1.3.6.1.4.1.11591.4.11 = Scrypt
+
 [pkcs9]
 1.2.840.113549.1.9.1 = PKCS9.EmailAddress
 1.2.840.113549.1.9.2 = PKCS9.UnstructuredName
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index ecd810ba2..80ac35272 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -110,6 +110,10 @@
    #include <botan/newhope.h>
 #endif
 
+#if defined(BOTAN_HAS_SCRYPT)
+   #include <botan/scrypt.h>
+#endif
+
 namespace Botan_CLI {
 
 namespace {
@@ -892,6 +896,12 @@ class Speed final : public Command
                bench_newhope(provider, msec);
                }
 #endif
+#if defined(BOTAN_HAS_SCRYPT)
+            else if(algo == "scrypt")
+               {
+               bench_scrypt(provider, msec);
+               }
+#endif
 
 #if defined(BOTAN_HAS_DL_GROUP)
             else if(algo == "modexp")
@@ -2135,6 +2145,28 @@ class Speed final : public Command
          }
 #endif
 
+#if defined(BOTAN_HAS_SCRYPT)
+
+      void bench_scrypt(const std::string& /*provider*/,
+                        std::chrono::milliseconds msec)
+         {
+         std::unique_ptr<Timer> scrypt_timer = make_timer("scrypt");
+
+         uint8_t out[64];
+         uint8_t salt[8] = { 0 };
+
+         while(scrypt_timer->under(msec))
+            {
+            scrypt_timer->run([&] {
+               Botan::scrypt(out, sizeof(out), "password",
+                             salt, sizeof(salt), 16384, 8, 1);
+               });
+            }
+
+         record_result(scrypt_timer);
+         }
+
+#endif
 
 #if defined(BOTAN_HAS_NEWHOPE) && defined(BOTAN_HAS_CHACHA_RNG)
       void bench_newhope(const std::string& /*provider*/,
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;
diff --git a/src/tests/data/scrypt.vec b/src/tests/data/scrypt.vec
new file mode 100644
index 000000000..e63e7d6fa
--- /dev/null
+++ b/src/tests/data/scrypt.vec
@@ -0,0 +1,112 @@
+
+# From RFC 7914
+
+Passphrase =
+Salt =
+N = 16
+R = 1
+P = 1
+Output = 77D6576238657B203B19CA42C18A0497F16B4844E3074AE8DFDFFA3FEDE21442FCD0069DED0948F8326A753A0FC81F17E8D3E0FB2E0D3628CF35E20C38D18906
+
+Passphrase = password
+Salt = 4E61436C
+N = 1024
+R = 8
+P = 16
+Output = FDBABE1C9D3472007856E7190D01E9FE7C6AD7CBC8237830E77376634B3731622EAF30D92E22A3886FF109279D9830DAC727AFB94A83EE6D8360CBDFA2CC0640
+
+Passphrase = pleaseletmein
+Salt = 536F6469756D43686C6F72696465
+N = 16384
+R = 8
+P = 1
+Output = 7023BDCB3AFD7348461C06CD81FD38EBFDA8FBBA904F8E3EA9B543F6545DA1F2D5432955613F0FCF62D49705242A9AF9E61E85DC0D651E40DFCF017B45575887
+
+# Uses 1G memory
+Passphrase = pleaseletmein
+Salt = 536F6469756D43686C6F72696465
+N = 1048576
+R = 8
+P = 1
+Output = 2101CB9B6A511AAEADDBBE09CF70F881EC568D574A2FFD4DABE5EE9820ADAA478E56FD8F4BA5D09FFA1C6D927C40F4C337304049E8A952FBCBF45C6FA77A41A4
+
+# From PKCS#8 test
+Passphrase = Rabbit
+Salt = 4D6F757365
+N = 1048576
+R = 8
+P = 1
+Output = E277EA2CACB23EDAFC039D229B79DC13ECEDB601D99B182A9FEDBA1E2BFB4F58
+
+# Generated by OpenSSL 1.1.0 via Python hashlib
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 8192
+R = 5
+P = 1
+Output = a19e1c5ce6e0da022c64a7205da125dc
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 8192
+R = 6
+P = 1
+Output = c9060cb775114c0688df86e9990c62ab
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 8192
+R = 7
+P = 1
+Output = 424e439dafcc0fc438469241e9d6bdf8
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 8192
+R = 8
+P = 1
+Output = 18f3116479374acd05755a1bf43a3af2
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 4096
+R = 16
+P = 1
+Output = 485d55c1267e1afa60349fe28c4aa2d9
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 4096
+R = 32
+P = 1
+Output = a43d75bb3b899852c8297fe2cd3b9681
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 2
+R = 64
+P = 64
+Output = a1c68ee1a41bc4e8dcfdc3fa93700426
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 2
+R = 64
+P = 128
+Output = b58b8ec24738af168b4e24de079102f1
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 2
+R = 63
+P = 128
+Output = 61de26be0f6609462bf66d88dece2d3c
+
+Passphrase = password
+Salt = ce3b79848f2a254df1d60e1a3146165a
+N = 4
+R = 19
+P = 17
+Output = b21fc99ae1dd4067c2d2b906af62518e
+
diff --git a/src/tests/test_pbkdf.cpp b/src/tests/test_pbkdf.cpp
index 37d3c3125..6694e0522 100644
--- a/src/tests/test_pbkdf.cpp
+++ b/src/tests/test_pbkdf.cpp
@@ -14,6 +14,10 @@
    #include <botan/pgp_s2k.h>
 #endif
 
+#if defined(BOTAN_HAS_SCRYPT)
+   #include <botan/scrypt.h>
+#endif
+
 namespace Botan_Tests {
 
 namespace {
@@ -57,6 +61,43 @@ BOTAN_REGISTER_TEST("pbkdf", PBKDF_KAT_Tests);
 
 #endif
 
+#if defined(BOTAN_HAS_SCRYPT)
+
+class Scrypt_KAT_Tests final : public Text_Based_Test
+   {
+   public:
+      Scrypt_KAT_Tests() : Text_Based_Test("scrypt.vec", "Passphrase,Salt,N,R,P,Output") {}
+
+      Test::Result run_one_test(const std::string&, const VarMap& vars) override
+         {
+         const size_t N = get_req_sz(vars, "N");
+         const size_t R = get_req_sz(vars, "R");
+         const size_t P = get_req_sz(vars, "P");
+         const std::vector<uint8_t> salt = get_req_bin(vars, "Salt");
+         const std::string passphrase = get_req_str(vars, "Passphrase");
+         const std::vector<uint8_t> expected = get_req_bin(vars, "Output");
+
+         Test::Result result("scrypt");
+
+         if(N >= 1048576 && Test::run_long_tests() == false)
+            return result;
+
+         std::vector<uint8_t> output(expected.size());
+         Botan::scrypt(output.data(), output.size(),
+                       passphrase, salt.data(), salt.size(),
+                       N, R, P);
+
+         result.test_eq("derived key", output, expected);
+
+         return result;
+         }
+
+   };
+
+BOTAN_REGISTER_TEST("scrypt", Scrypt_KAT_Tests);
+
+#endif
+
 #if defined(BOTAN_HAS_PGP_S2K)
 
 class PGP_S2K_Iter_Test final : public Test