Botan 3.6.1
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
10#include <botan/exceptn.h>
11#include <botan/pbkdf2.h>
12#include <botan/internal/bit_ops.h>
13#include <botan/internal/fmt.h>
14#include <botan/internal/loadstor.h>
15#include <botan/internal/salsa20.h>
16#include <botan/internal/timer.h>
17
18namespace Botan {
19
20namespace {
21
22size_t scrypt_memory_usage(size_t N, size_t r, size_t p) {
23 return 128 * r * (N + p);
24}
25
26} // namespace
27
28std::string Scrypt_Family::name() const {
29 return "Scrypt";
30}
31
32std::unique_ptr<PasswordHash> Scrypt_Family::default_params() const {
33 return std::make_unique<Scrypt>(32768, 8, 1);
34}
35
36std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,
37 std::chrono::milliseconds msec,
38 size_t max_memory_usage_mb,
39 std::chrono::milliseconds tune_time) const {
40 BOTAN_UNUSED(output_length);
41
42 /*
43 * Some rough relations between scrypt parameters and runtime.
44 * Denote here by stime(N,r,p) the msec it takes to run scrypt.
45 *
46 * Emperically for smaller sizes:
47 * stime(N,8*r,p) / stime(N,r,p) is ~ 6-7
48 * stime(N,r,8*p) / stime(N,r,8*p) is ~ 7
49 * stime(2*N,r,p) / stime(N,r,p) is ~ 2
50 *
51 * Compute stime(8192,1,1) as baseline and extrapolate
52 */
53
54 // This is zero if max_memory_usage_mb == 0 (unbounded)
55 const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024;
56
57 // Starting parameters
58 size_t N = 8 * 1024;
59 size_t r = 1;
60 size_t p = 1;
61
62 Timer timer("Scrypt");
63
64 auto pwdhash = this->from_params(N, r, p);
65
66 timer.run_until_elapsed(tune_time, [&]() {
67 uint8_t output[32] = {0};
68 pwdhash->derive_key(output, sizeof(output), "test", 4, nullptr, 0);
69 });
70
71 // No timer events seems strange, perhaps something is wrong - give
72 // up on this and just return default params
73 if(timer.events() == 0) {
74 return default_params();
75 }
76
77 // nsec per eval of scrypt with initial params
78 const uint64_t measured_time = timer.value() / timer.events();
79
80 const uint64_t target_nsec = msec.count() * static_cast<uint64_t>(1000000);
81
82 uint64_t est_nsec = measured_time;
83
84 // In below code we invoke scrypt_memory_usage with p == 0 as p contributes
85 // (very slightly) to memory consumption, but N is the driving factor.
86 // Including p leads to using an N half as large as what the user would expect.
87
88 // First increase r by 8x if possible
89 if(max_memory_usage == 0 || scrypt_memory_usage(N, r * 8, 0) <= max_memory_usage) {
90 if(target_nsec / est_nsec >= 5) {
91 r *= 8;
92 est_nsec *= 5;
93 }
94 }
95
96 // Now double N as many times as we can
97 while(max_memory_usage == 0 || scrypt_memory_usage(N * 2, r, 0) <= max_memory_usage) {
98 if(target_nsec / est_nsec >= 2) {
99 N *= 2;
100 est_nsec *= 2;
101 } else {
102 break;
103 }
104 }
105
106 // If we have extra runtime budget, increment p
107 if(target_nsec / est_nsec >= 2) {
108 p *= std::min<size_t>(1024, static_cast<size_t>(target_nsec / est_nsec));
109 }
110
111 return std::make_unique<Scrypt>(N, r, p);
112}
113
114std::unique_ptr<PasswordHash> Scrypt_Family::from_params(size_t N, size_t r, size_t p) const {
115 return std::make_unique<Scrypt>(N, r, p);
116}
117
118std::unique_ptr<PasswordHash> Scrypt_Family::from_iterations(size_t iter) const {
119 const size_t r = 8;
120 const size_t p = 1;
121
122 size_t N = 8192;
123
124 if(iter > 50000) {
125 N = 16384;
126 }
127 if(iter > 100000) {
128 N = 32768;
129 }
130 if(iter > 150000) {
131 N = 65536;
132 }
133
134 return std::make_unique<Scrypt>(N, r, p);
135}
136
137Scrypt::Scrypt(size_t N, size_t r, size_t p) : m_N(N), m_r(r), m_p(p) {
138 if(!is_power_of_2(N)) {
139 throw Invalid_Argument("Scrypt N parameter must be a power of 2");
140 }
141
142 if(p == 0 || p > 1024) {
143 throw Invalid_Argument("Invalid or unsupported scrypt p");
144 }
145 if(r == 0 || r > 256) {
146 throw Invalid_Argument("Invalid or unsupported scrypt r");
147 }
148 if(N < 1 || N > 4194304) {
149 throw Invalid_Argument("Invalid or unsupported scrypt N");
150 }
151}
152
153std::string Scrypt::to_string() const {
154 return fmt("Scrypt({},{},{})", m_N, m_r, m_p);
155}
156
158 const size_t N = memory_param();
159 const size_t p = parallelism();
160 const size_t r = iterations();
161
162 return scrypt_memory_usage(N, r, p);
163}
164
165namespace {
166
167void scryptBlockMix(size_t r, uint8_t* B, uint8_t* Y) {
168 uint32_t B32[16];
170 copy_mem(X.data(), &B[(2 * r - 1) * 64], 64);
171
172 for(size_t i = 0; i != 2 * r; i++) {
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 copy_mem(&B[i * 64], &Y[(i * 2) * 64], 64);
181 }
182
183 for(size_t i = 0; i < r; ++i) {
184 copy_mem(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64);
185 }
186}
187
188void scryptROMmix(size_t r, size_t N, uint8_t* B, secure_vector<uint8_t>& V) {
189 const size_t S = 128 * r;
190
191 for(size_t i = 0; i != N; ++i) {
192 copy_mem(&V[S * i], B, S);
193 scryptBlockMix(r, B, &V[N * S]);
194 }
195
196 for(size_t i = 0; i != N; ++i) {
197 // compiler doesn't know here that N is power of 2
198 const size_t j = load_le<uint32_t>(&B[(2 * r - 1) * 64], 0) & (N - 1);
199 xor_buf(B, &V[j * S], S);
200 scryptBlockMix(r, B, &V[N * S]);
201 }
202}
203
204} // namespace
205
206void Scrypt::derive_key(uint8_t output[],
207 size_t output_len,
208 const char* password,
209 size_t password_len,
210 const uint8_t salt[],
211 size_t salt_len) const {
212 const size_t N = memory_param();
213 const size_t p = parallelism();
214 const size_t r = iterations();
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 hmac_sha256->set_key(cast_char_ptr_to_uint8(password), password_len);
225 } catch(Invalid_Key_Length&) {
226 throw Invalid_Argument("Scrypt cannot accept passphrases of the provided length");
227 }
228
229 pbkdf2(*hmac_sha256, B.data(), B.size(), salt, salt_len, 1);
230
231 // these can be parallel
232 for(size_t i = 0; i != p; ++i) {
233 scryptROMmix(r, N, &B[128 * r * i], V);
234 }
235
236 pbkdf2(*hmac_sha256, output, output_len, B.data(), B.size(), 1);
237}
238
239} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:118
static std::unique_ptr< MessageAuthenticationCode > create_or_throw(std::string_view algo_spec, std::string_view provider="")
Definition mac.cpp:148
static void salsa_core(uint8_t output[64], const uint32_t input[16], size_t rounds)
Definition salsa20.cpp:62
std::unique_ptr< PasswordHash > from_params(size_t N, size_t r, size_t p) const override
Definition scrypt.cpp:114
std::unique_ptr< PasswordHash > tune(size_t output_length, std::chrono::milliseconds msec, size_t max_memory, std::chrono::milliseconds tune_msec) const override
Definition scrypt.cpp:36
std::unique_ptr< PasswordHash > from_iterations(size_t iter) const override
Definition scrypt.cpp:118
std::string name() const override
Definition scrypt.cpp:28
std::unique_ptr< PasswordHash > default_params() const override
Definition scrypt.cpp:32
std::string to_string() const override
Definition scrypt.cpp:153
size_t memory_param() const override
Definition scrypt.h:44
size_t iterations() const override
Definition scrypt.h:40
size_t parallelism() const override
Definition scrypt.h:42
size_t total_memory_usage() const override
Definition scrypt.cpp:157
Scrypt(size_t N, size_t r, size_t p)
Definition scrypt.cpp:137
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:206
uint64_t value() const
Definition timer.h:66
uint64_t events() const
Definition timer.h:81
void run_until_elapsed(std::chrono::milliseconds msec, F f)
Definition timer.h:60
FE_25519 Y
Definition ge.cpp:26
FE_25519 X
Definition ge.cpp:25
constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:45
std::string fmt(std::string_view format, const T &... args)
Definition fmt.h:53
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:521
constexpr void xor_buf(ranges::contiguous_output_range< uint8_t > auto &&out, ranges::contiguous_range< uint8_t > auto &&in)
Definition mem_ops.h:341
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
size_t pbkdf2(MessageAuthenticationCode &prf, uint8_t out[], size_t out_len, std::string_view password, const uint8_t salt[], size_t salt_len, size_t iterations, std::chrono::milliseconds msec)
Definition pbkdf2.cpp:78
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:146
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition mem_ops.h:273