Coverage Report

Created: 2022-06-23 06:44

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