Botan  2.11.0
Crypto and TLS for C++11
scrypt.cpp
Go to the documentation of this file.
1 /**
2 * (C) 2018 Jack Lloyd
3 * (C) 2018 Ribose Inc
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/scrypt.h>
9 #include <botan/pbkdf2.h>
10 #include <botan/salsa20.h>
11 #include <botan/loadstor.h>
12 #include <botan/exceptn.h>
13 #include <botan/internal/bit_ops.h>
14 #include <botan/internal/timer.h>
15 #include <sstream>
16 
17 namespace Botan {
18 
19 std::string Scrypt_Family::name() const
20  {
21  return "Scrypt";
22  }
23 
24 std::unique_ptr<PasswordHash> Scrypt_Family::default_params() const
25  {
26  return std::unique_ptr<PasswordHash>(new Scrypt(32768, 8, 1));
27  }
28 
29 std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,
30  std::chrono::milliseconds msec,
31  size_t max_memory_usage_mb) const
32  {
34 
35  /*
36  * Some rough relations between scrypt parameters and runtime.
37  * Denote here by stime(N,r,p) the msec it takes to run scrypt.
38  *
39  * Emperically for smaller sizes:
40  * stime(N,8*r,p) / stime(N,r,p) is ~ 6-7
41  * stime(N,r,8*p) / stime(N,r,8*p) is ~ 7
42  * stime(2*N,r,p) / stime(N,r,p) is ~ 2
43  *
44  * Compute stime(8192,1,1) as baseline and extrapolate
45  */
46 
47  const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024;
48  // Starting parameters
49  size_t N = 8192;
50  size_t r = 1;
51  size_t p = 1;
52 
53  Timer timer("Scrypt");
54  const auto tune_time = BOTAN_PBKDF_TUNING_TIME;
55 
56  timer.run_until_elapsed(tune_time, [&]() {
57  uint8_t output[32] = { 0 };
58  scrypt(output, sizeof(output), "test", 4, nullptr, 0, N, r, p);
59  });
60 
61  // No timer events seems strange, perhaps something is wrong - give
62  // up on this and just return default params
63  if(timer.events() == 0)
64  return default_params();
65 
66  // nsec per eval of scrypt with initial params
67  const uint64_t measured_time = timer.value() / timer.events();
68 
69  const uint64_t target_nsec = msec.count() * static_cast<uint64_t>(1000000);
70 
71  uint64_t est_nsec = measured_time;
72 
73  // First move increase r by 8x if possible
74 
75  if(max_memory_usage == 0 || scrypt_memory_usage(N, r, p)*8 < max_memory_usage)
76  {
77  if(target_nsec / est_nsec >= 5)
78  {
79  r *= 8;
80  est_nsec *= 5;
81  }
82  }
83 
84  // Now double N as many times as we can
85 
86  while(max_memory_usage == 0 || scrypt_memory_usage(N, r, p)*2 < max_memory_usage)
87  {
88  if(target_nsec / est_nsec >= 2)
89  {
90  N *= 2;
91  est_nsec *= 2;
92  }
93  else
94  break;
95  }
96 
97  // If we have extra runtime budget, increment p
98 
99  if(target_nsec / est_nsec > 2)
100  p *= std::min<size_t>(1024, static_cast<size_t>(target_nsec / est_nsec));
101 
102  return std::unique_ptr<PasswordHash>(new Scrypt(N, r, p));
103  }
104 
105 std::unique_ptr<PasswordHash> Scrypt_Family::from_params(size_t N, size_t r, size_t p) const
106  {
107  return std::unique_ptr<PasswordHash>(new Scrypt(N, r, p));
108  }
109 
110 std::unique_ptr<PasswordHash> Scrypt_Family::from_iterations(size_t iter) const
111  {
112  const size_t r = 8;
113  const size_t p = 1;
114 
115  size_t N = 8192;
116 
117  if(iter > 50000)
118  N = 16384;
119  if(iter > 100000)
120  N = 32768;
121  if(iter > 150000)
122  N = 65536;
123 
124  return std::unique_ptr<PasswordHash>(new Scrypt(N, r, p));
125  }
126 
127 Scrypt::Scrypt(size_t N, size_t r, size_t p) :
128  m_N(N), m_r(r), m_p(p)
129  {
130  if(!is_power_of_2(N))
131  throw Invalid_Argument("Scrypt N parameter must be a power of 2");
132 
133  if(p == 0 || p > 1024)
134  throw Invalid_Argument("Invalid or unsupported scrypt p");
135  if(r == 0 || r > 256)
136  throw Invalid_Argument("Invalid or unsupported scrypt r");
137  if(N < 1 || N > 4194304)
138  throw Invalid_Argument("Invalid or unsupported scrypt N");
139  }
140 
141 std::string Scrypt::to_string() const
142  {
143  std::ostringstream oss;
144  oss << "Scrypt(" << m_N << "," << m_r << "," << m_p << ")";
145  return oss.str();
146  }
147 
148 size_t Scrypt::total_memory_usage() const
149  {
150  return scrypt_memory_usage(m_N, m_r, m_p);
151  }
152 
153 void Scrypt::derive_key(uint8_t output[], size_t output_len,
154  const char* password, size_t password_len,
155  const uint8_t salt[], size_t salt_len) const
156  {
159  salt, salt_len,
160  N(), r(), p());
161  }
162 
163 namespace {
164 
165 void scryptBlockMix(size_t r, uint8_t* B, uint8_t* Y)
166  {
167  uint32_t B32[16];
168  secure_vector<uint8_t> X(64);
169  copy_mem(X.data(), &B[(2*r-1)*64], 64);
170 
171  for(size_t i = 0; i != 2*r; i++)
172  {
173  xor_buf(X.data(), &B[64*i], 64);
174  load_le<uint32_t>(B32, X.data(), 16);
175  Salsa20::salsa_core(X.data(), B32, 8);
176  copy_mem(&Y[64*i], X.data(), 64);
177  }
178 
179  for(size_t i = 0; i < r; ++i)
180  {
181  copy_mem(&B[i*64], &Y[(i * 2) * 64], 64);
182  }
183 
184  for(size_t i = 0; i < r; ++i)
185  {
186  copy_mem(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64);
187  }
188  }
189 
190 void scryptROMmix(size_t r, size_t N, uint8_t* B, secure_vector<uint8_t>& V)
191  {
192  const size_t S = 128 * r;
193 
194  for(size_t i = 0; i != N; ++i)
195  {
196  copy_mem(&V[S*i], B, S);
197  scryptBlockMix(r, B, &V[N*S]);
198  }
199 
200  for(size_t i = 0; i != N; ++i)
201  {
202  // compiler doesn't know here that N is power of 2
203  const size_t j = load_le<uint32_t>(&B[(2*r-1)*64], 0) & (N - 1);
204  xor_buf(B, &V[j*S], S);
205  scryptBlockMix(r, B, &V[N*S]);
206  }
207  }
208 
209 }
210 
211 void scrypt(uint8_t output[], size_t output_len,
212  const char* password, size_t password_len,
213  const uint8_t salt[], size_t salt_len,
214  size_t N, size_t r, size_t p)
215  {
216  const size_t S = 128 * r;
217  secure_vector<uint8_t> B(p * S);
218  // temp space
219  secure_vector<uint8_t> V((N+1) * S);
220 
221  auto hmac_sha256 = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)");
222 
223  try
224  {
225  hmac_sha256->set_key(cast_char_ptr_to_uint8(password), password_len);
226  }
227  catch(Invalid_Key_Length&)
228  {
229  throw Invalid_Argument("Scrypt cannot accept passphrases of the provided length");
230  }
231 
232  pbkdf2(*hmac_sha256.get(),
233  B.data(), B.size(),
234  salt, salt_len,
235  1);
236 
237  // these can be parallel
238  for(size_t i = 0; i != p; ++i)
239  {
240  scryptROMmix(r, N, &B[128*r*i], V);
241  }
242 
243  pbkdf2(*hmac_sha256.get(),
245  B.data(), B.size(),
246  1);
247  }
248 
249 }
fe X
Definition: ge.cpp:27
uint32_t uint8_t output[]
Definition: ffi.h:512
BigInt const BigInt & p
Definition: numthry.h:150
size_t * output_length
Definition: ffi.h:280
size_t const char const uint8_t size_t size_t size_t r
Definition: ffi.h:628
fe Y
Definition: ge.cpp:28
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition: mem_ops.h:159
uint32_t load_le< uint32_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:196
void const BigInt BigInt BigInt & r
Definition: divide.h:23
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
char * name
Definition: ffi.h:330
size_t const char const uint8_t size_t size_t N
Definition: ffi.h:628
size_t scrypt_memory_usage(size_t N, size_t r, size_t p)
Definition: scrypt.h:118
class BOTAN_PUBLIC_API(2, 11) Argon2 final class BOTAN_PUBLIC_API(2, 11) Argon2_Family final void size_t const char size_t password_len
Definition: argon2.h:87
void xor_buf(uint8_t out[], const uint8_t in[], size_t length)
Definition: mem_ops.h:202
uint8_t size_t const char const uint8_t size_t salt_len
Definition: ffi.h:543
uint8_t size_t const std::string const uint8_t size_t size_t std::chrono::milliseconds msec
Definition: pbkdf2.h:19
size_t const char const uint8_t size_t size_t size_t size_t p
Definition: ffi.h:628
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43
class BOTAN_PUBLIC_API(2, 11) Argon2 final class BOTAN_PUBLIC_API(2, 11) Argon2_Family final void size_t output_len
Definition: argon2.h:87
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:122
Definition: alg_id.cpp:13
#define BOTAN_UNUSED(...)
Definition: assert.h:142
uint8_t size_t const char const uint8_t salt[]
Definition: ffi.h:543
void BlockCipher const uint8_t size_t uint8_t output[]
Definition: package.h:29
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
size_t pbkdf2(MessageAuthenticationCode &prf, uint8_t out[], size_t out_len, const std::string &password, const uint8_t salt[], size_t salt_len, size_t iterations, std::chrono::milliseconds msec)
Definition: pbkdf2.cpp:35
class BOTAN_PUBLIC_API(2, 8) Scrypt final class BOTAN_PUBLIC_API(2, 8) Scrypt_Family final void size_t const char size_t const uint8_t size_t size_t N
Definition: scrypt.h:85
void scrypt(uint8_t output[], size_t output_len, const char *password, size_t password_len, const uint8_t salt[], size_t salt_len, size_t N, size_t r, size_t p)
Definition: scrypt.cpp:211
size_t const char * password
Definition: ffi.h:910