Coverage Report

Created: 2020-05-23 13:54

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