/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/internal/salsa20.h> |
11 | | #include <botan/internal/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::make_unique<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 | | |
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 | 0 | const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024; |
48 | | // Starting parameters |
49 | 0 | size_t N = 8192; |
50 | 0 | size_t r = 1; |
51 | 0 | size_t p = 1; |
52 | |
|
53 | 0 | Timer timer("Scrypt"); |
54 | 0 | const auto tune_time = BOTAN_PBKDF_TUNING_TIME; |
55 | |
|
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 | | |
61 | | // No timer events seems strange, perhaps something is wrong - give |
62 | | // up on this and just return default params |
63 | 0 | if(timer.events() == 0) |
64 | 0 | return default_params(); |
65 | | |
66 | | // nsec per eval of scrypt with initial params |
67 | 0 | const uint64_t measured_time = timer.value() / timer.events(); |
68 | |
|
69 | 0 | const uint64_t target_nsec = msec.count() * static_cast<uint64_t>(1000000); |
70 | |
|
71 | 0 | uint64_t est_nsec = measured_time; |
72 | | |
73 | | // First move increase r by 8x if possible |
74 | |
|
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 | | |
84 | | // Now double N as many times as we can |
85 | |
|
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 | | |
97 | | // If we have extra runtime budget, increment p |
98 | |
|
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 | |
|
102 | 0 | return std::make_unique<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::make_unique<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 | |
|
115 | 0 | size_t N = 8192; |
116 | |
|
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 | |
|
124 | 0 | return std::make_unique<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 | | |
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 | |
|
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 | |
|
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 | |
|
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 | |
|
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 | |
|
200 | 0 | for(size_t i = 0; i != N; ++i) |
201 | 0 | { |
202 | | // 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 | | // temp space |
219 | 0 | secure_vector<uint8_t> V((N+1) * S); |
220 | |
|
221 | 0 | auto hmac_sha256 = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)"); |
222 | |
|
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 | | |
232 | 0 | pbkdf2(*hmac_sha256.get(), |
233 | 0 | B.data(), B.size(), |
234 | 0 | salt, salt_len, |
235 | 0 | 1); |
236 | | |
237 | | // 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 | |
|
243 | 0 | pbkdf2(*hmac_sha256.get(), |
244 | 0 | output, output_len, |
245 | 0 | B.data(), B.size(), |
246 | 0 | 1); |
247 | 0 | } |
248 | | |
249 | | } |