/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 | | } |