Botan 2.19.2
Crypto and TLS for C&
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
17namespace Botan {
18
19std::string Scrypt_Family::name() const
20 {
21 return "Scrypt";
22 }
23
24std::unique_ptr<PasswordHash> Scrypt_Family::default_params() const
25 {
26 return std::unique_ptr<PasswordHash>(new Scrypt(32768, 8, 1));
27 }
28
29std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,
30 std::chrono::milliseconds msec,
31 size_t max_memory_usage_mb) const
32 {
33 BOTAN_UNUSED(output_length);
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
105std::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
110std::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
127Scrypt::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
141std::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
149 {
150 return scrypt_memory_usage(m_N, m_r, m_p);
151 }
152
153void 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 {
157 scrypt(output, output_len,
158 password, password_len,
159 salt, salt_len,
160 N(), r(), p());
161 }
162
163namespace {
164
165void scryptBlockMix(size_t r, uint8_t* B, uint8_t* Y)
166 {
167 uint32_t B32[16];
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
190void 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
211void 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(),
244 output, output_len,
245 B.data(), B.size(),
246 1);
247 }
248
249}
#define BOTAN_UNUSED(...)
Definition: assert.h:142
static std::unique_ptr< MessageAuthenticationCode > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: mac.cpp:139
static void salsa_core(uint8_t output[64], const uint32_t input[16], size_t rounds)
Definition: salsa20.cpp:61
std::unique_ptr< PasswordHash > tune(size_t output_length, std::chrono::milliseconds msec, size_t max_memory) const override
Definition: scrypt.cpp:29
std::unique_ptr< PasswordHash > from_params(size_t N, size_t r, size_t p) const override
Definition: scrypt.cpp:105
std::unique_ptr< PasswordHash > from_iterations(size_t iter) const override
Definition: scrypt.cpp:110
std::string name() const override
Definition: scrypt.cpp:19
std::unique_ptr< PasswordHash > default_params() const override
Definition: scrypt.cpp:24
std::string to_string() const override
Definition: scrypt.cpp:141
size_t N() const
Definition: scrypt.h:37
size_t total_memory_usage() const override
Definition: scrypt.cpp:148
size_t r() const
Definition: scrypt.h:38
Scrypt(size_t N, size_t r, size_t p)
Definition: scrypt.cpp:127
void derive_key(uint8_t out[], size_t out_len, const char *password, size_t password_len, const uint8_t salt[], size_t salt_len) const override
Definition: scrypt.cpp:153
size_t p() const
Definition: scrypt.h:39
uint64_t value() const
Definition: timer.h:90
uint64_t events() const
Definition: timer.h:119
void run_until_elapsed(std::chrono::milliseconds msec, F f)
Definition: timer.h:82
fe Y
Definition: ge.cpp:28
fe X
Definition: ge.cpp:27
Definition: alg_id.cpp:13
uint32_t load_le< uint32_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:198
size_t scrypt_memory_usage(size_t N, size_t r, size_t p)
Definition: scrypt.h:120
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 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
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:133
void xor_buf(uint8_t out[], const uint8_t in[], size_t length)
Definition: mem_ops.h:262
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition: mem_ops.h:190
size_t salt_len
Definition: x509_obj.cpp:25