26703548991

Committed 30 May 2026 09:57PM UTC coverage: 89.37% (+0.009%) from 89.361%

Build # 26703548991

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5629 from randombit/jack/pwhash-limit-mem

In Argon2 and Scrypt provide some reasonable upper bound on memory consumption

Coverage Stats

110243 of 123356 relevant lines covered (89.37%)

11053253.82 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

80.67

/src/lib/pbkdf/scrypt/scrypt.cpp

/**
* (C) 2018 Jack Lloyd
* (C) 2018 Ribose Inc
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/scrypt.h>

#include <botan/exceptn.h>
#include <botan/pbkdf2.h>
#include <botan/internal/bit_ops.h>
#include <botan/internal/fmt.h>
#include <botan/internal/int_utils.h>
#include <botan/internal/loadstor.h>
#include <botan/internal/mem_utils.h>
#include <botan/internal/salsa20.h>
#include <botan/internal/time_utils.h>

namespace Botan {

namespace {

constexpr size_t MAX_SCRYPT_N = 4194304;
constexpr size_t MAX_SCRYPT_MEMORY_GB = sizeof(size_t) == 4 ? 2 : 8;
constexpr size_t MAX_SCRYPT_MEMORY_BYTES = MAX_SCRYPT_MEMORY_GB * 1024 * 1024 * 1024 + 65536;

std::optional<size_t> scrypt_memory_usage(size_t N, size_t r, size_t p) {
   // 128 * r * (N + p) rejecting on overflow
   const auto block_size = checked_mul(static_cast<size_t>(128), r);
   const auto blocks = checked_add(N, p);
   if(block_size && blocks) {
      return checked_mul(block_size.value(), blocks.value());
   } else {
      return {};
   }
}

}  // namespace

std::string Scrypt_Family::name() const {
   return "Scrypt";
}

std::unique_ptr<PasswordHash> Scrypt_Family::default_params() const {
   return std::make_unique<Scrypt>(32768, 8, 1);
}

std::unique_ptr<PasswordHash> Scrypt_Family::tune_params(size_t /*output_length*/,
                                                         uint64_t desired_msec,
                                                         std::optional<size_t> max_memory,
                                                         uint64_t tuning_msec) const {
   /*
   * Some rough relations between scrypt parameters and runtime.
   * Denote here by stime(N,r,p) the msec it takes to run scrypt.
   *
   * Empirically for smaller sizes:
   * stime(N,8*r,p) / stime(N,r,p) is ~ 6-7
   * stime(N,r,8*p) / stime(N,r,8*p) is ~ 7
   * stime(2*N,r,p) / stime(N,r,p) is ~ 2
   *
   * Compute stime(8192,1,1) as baseline and extrapolate
   */

   // If max_memory is nullopt or zero this becomes zero and is ignored
   const size_t max_memory_bytes = std::min(MAX_SCRYPT_MEMORY_BYTES, max_memory.value_or(0) * 1024 * 1024);

   // In below code we invoke scrypt_memory_usage with p == 0 as p contributes
   // (very slightly) to memory consumption, but N is the driving factor.
   // Including p leads to using an N half as large as what the user would expect.

   auto scrypt_parameters_acceptable = [&](size_t N, size_t r) -> bool {
      if(N > MAX_SCRYPT_N) {
         return false;
      }
      if(const auto consumed = scrypt_memory_usage(N, r, 0)) {
         if(max_memory_bytes > 0 && *consumed > max_memory_bytes) {
            return false;
         } else {
            return true;
         }
      } else {
         return false;
      }
   };

   // Starting parameters
   size_t N = 8 * 1024;
   size_t r = 1;
   size_t p = 1;

   auto pwdhash = this->from_params(N, r, p);

   const uint64_t measured_time = measure_cost(tuning_msec, [&]() {
      uint8_t output[32] = {0};
      pwdhash->derive_key(output, sizeof(output), "test", 4, nullptr, 0);
   });

   const uint64_t target_nsec = desired_msec * static_cast<uint64_t>(1000000);

   uint64_t est_nsec = measured_time;

   // First increase r by 8x if possible
   if(scrypt_parameters_acceptable(N, r * 8)) {
      if(target_nsec / est_nsec >= 5) {
         r *= 8;
         est_nsec *= 5;
      }
   }

   // Now double N as many times as we can
   while(scrypt_parameters_acceptable(N * 2, r)) {
      if(target_nsec / est_nsec >= 2) {
         N *= 2;
         est_nsec *= 2;
      } else {
         break;
      }
   }

   // If we have extra runtime budget, increment p
   if(target_nsec / est_nsec >= 2) {
      p *= std::min<size_t>(1024, static_cast<size_t>(target_nsec / est_nsec));
   }

   return std::make_unique<Scrypt>(N, r, p);
}

std::unique_ptr<PasswordHash> Scrypt_Family::from_params(size_t N, size_t r, size_t p) const {
   return std::make_unique<Scrypt>(N, r, p);
}

std::unique_ptr<PasswordHash> Scrypt_Family::from_iterations(size_t iter) const {
   const size_t r = 8;
   const size_t p = 1;

   size_t N = 8192;

   if(iter > 50000) {
      N = 16384;
   }
   if(iter > 100000) {
      N = 32768;
   }
   if(iter > 150000) {
      N = 65536;
   }

   return std::make_unique<Scrypt>(N, r, p);
}

Scrypt::Scrypt(size_t N, size_t r, size_t p) : m_N(N), m_r(r), m_p(p) {
   if(!is_power_of_2(N)) {
      throw Invalid_Argument("Scrypt N parameter must be a power of 2");
   }

   if(p == 0 || p > 1024) {
      throw Invalid_Argument("Invalid or unsupported scrypt p");
   }
   if(r == 0 || r > 256) {
      throw Invalid_Argument("Invalid or unsupported scrypt r");
   }
   if(N < 1 || N > MAX_SCRYPT_N) {
      throw Invalid_Argument("Invalid or unsupported scrypt N");
   }

   if(const auto memory_usage = scrypt_memory_usage(N, r, p)) {
      if(memory_usage > MAX_SCRYPT_MEMORY_BYTES) {
         throw Invalid_Argument("Scrypt parameters exceed maximum allowed memory limit");
      }
   } else {
      throw Invalid_Argument("Scrypt parameters are too large for this platform");
   }
}

std::string Scrypt::to_string() const {
   return fmt("Scrypt({},{},{})", m_N, m_r, m_p);
}

size_t Scrypt::total_memory_usage() const {
   const size_t N = memory_param();
   const size_t p = parallelism();
   const size_t r = iterations();

   const auto consumption = scrypt_memory_usage(N, r, p);
   BOTAN_ASSERT_NOMSG(consumption.has_value());
   return consumption.value();
}

namespace {

void scryptBlockMix(size_t r, uint8_t* B, uint8_t* Y) {
   uint32_t B32[16];
   secure_vector<uint8_t> X(64);
   copy_mem(X.data(), &B[(2 * r - 1) * 64], 64);

   for(size_t i = 0; i != 2 * r; i++) {
      xor_buf(X.data(), &B[64 * i], 64);
      load_le<uint32_t>(B32, X.data(), 16);
      Salsa20::salsa_core(X.data(), B32, 8);
      copy_mem(&Y[64 * i], X.data(), 64);
   }

   for(size_t i = 0; i < r; ++i) {
      copy_mem(&B[i * 64], &Y[(i * 2) * 64], 64);
   }

   for(size_t i = 0; i < r; ++i) {
      copy_mem(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64);
   }
}

void scryptROMmix(size_t r, size_t N, uint8_t* B, secure_vector<uint8_t>& V) {
   const size_t S = 128 * r;

   for(size_t i = 0; i != N; ++i) {
      copy_mem(&V[S * i], B, S);
      scryptBlockMix(r, B, &V[N * S]);
   }

   for(size_t i = 0; i != N; ++i) {
      // compiler doesn't know here that N is power of 2
      const size_t j = load_le<uint32_t>(&B[(2 * r - 1) * 64], 0) & (N - 1);
      xor_buf(B, &V[j * S], S);
      scryptBlockMix(r, B, &V[N * S]);
   }
}

}  // namespace

void Scrypt::derive_key(uint8_t output[],
                        size_t output_len,
                        const char* password,
                        size_t password_len,
                        const uint8_t salt[],
                        size_t salt_len) const {
   if(output_len == 0) {
      return;
   }

   const size_t N = memory_param();
   const size_t p = parallelism();
   const size_t r = iterations();

   const size_t S = 128 * r;
   secure_vector<uint8_t> B(p * S);
   // temp space
   secure_vector<uint8_t> V((N + 1) * S);

   auto hmac_sha256 = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)");

   try {
      hmac_sha256->set_key(as_span_of_bytes(password, password_len));
   } catch(Invalid_Key_Length&) {
      throw Invalid_Argument("Scrypt cannot accept passphrases of the provided length");
   }

   pbkdf2(*hmac_sha256, B.data(), B.size(), salt, salt_len, 1);

   // these can be parallel
   for(size_t i = 0; i != p; ++i) {
      scryptROMmix(r, N, &B[128 * r * i], V);
   }

   pbkdf2(*hmac_sha256, output, output_len, B.data(), B.size(), 1);
}

}  // namespace Botan

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/int_utils.h>
15	#include <botan/internal/loadstor.h>
16	#include <botan/internal/mem_utils.h>
17	#include <botan/internal/salsa20.h>
18	#include <botan/internal/time_utils.h>
19
20	namespace Botan {
21
22	namespace {
23
24	constexpr size_t MAX_SCRYPT_N = 4194304;
25	constexpr size_t MAX_SCRYPT_MEMORY_GB = sizeof(size_t) == 4 ? 2 : 8;
26	constexpr size_t MAX_SCRYPT_MEMORY_BYTES = MAX_SCRYPT_MEMORY_GB * 1024 * 1024 * 1024 + 65536;
27
28	std::optional<size_t> scrypt_memory_usage(size_t N, size_t r, size_t p) {	1,280✔
29	// 128 * r * (N + p) rejecting on overflow
30	const auto block_size = checked_mul(static_cast<size_t>(128), r);	1,280✔
31	const auto blocks = checked_add(N, p);	1,280✔
32	if(block_size && blocks) {	1,280✔
33	return checked_mul(block_size.value(), blocks.value());	2,560✔
34	} else {
35	return {};	×
36	}
37	}
38
39	} // namespace
40
41	std::string Scrypt_Family::name() const {	1✔
42	return "Scrypt";	1✔
43	}
44
45	std::unique_ptr<PasswordHash> Scrypt_Family::default_params() const {	2✔
46	return std::make_unique<Scrypt>(32768, 8, 1);	2✔
47	}
48
49	std::unique_ptr<PasswordHash> Scrypt_Family::tune_params(size_t /output_length/,	242✔
50	uint64_t desired_msec,
51	std::optional<size_t> max_memory,
52	uint64_t tuning_msec) const {
53	/*
54	* Some rough relations between scrypt parameters and runtime.
55	* Denote here by stime(N,r,p) the msec it takes to run scrypt.
56	*
57	* Empirically for smaller sizes:
58	* stime(N,8*r,p) / stime(N,r,p) is ~ 6-7
59	* stime(N,r,8p) / stime(N,r,8p) is ~ 7
60	* stime(2*N,r,p) / stime(N,r,p) is ~ 2
61	*
62	* Compute stime(8192,1,1) as baseline and extrapolate
63	*/
64
65	// If max_memory is nullopt or zero this becomes zero and is ignored
66	const size_t max_memory_bytes = std::min(MAX_SCRYPT_MEMORY_BYTES, max_memory.value_or(0) * 1024 * 1024);	246✔
67
68	// In below code we invoke scrypt_memory_usage with p == 0 as p contributes
69	// (very slightly) to memory consumption, but N is the driving factor.
70	// Including p leads to using an N half as large as what the user would expect.
71
72	auto scrypt_parameters_acceptable = [&](size_t N, size_t r) -> bool {	747✔
73	if(N > MAX_SCRYPT_N) {	505✔
74	return false;
75	}
76	if(const auto consumed = scrypt_memory_usage(N, r, 0)) {	505✔
77	if(max_memory_bytes > 0 && *consumed > max_memory_bytes) {	505✔
78	return false;
79	} else {
80	return true;	505✔
81	}
82	} else {
83	return false;
84	}
85	};	242✔
86
87	// Starting parameters
88	size_t N = 8 * 1024;	242✔
89	size_t r = 1;	242✔
90	size_t p = 1;	242✔
91
92	auto pwdhash = this->from_params(N, r, p);	242✔
93
94	const uint64_t measured_time = measure_cost(tuning_msec, [&]() {	242✔
95	uint8_t output[32] = {0};	242✔
96	pwdhash->derive_key(output, sizeof(output), "test", 4, nullptr, 0);	242✔
97	});
98
99	const uint64_t target_nsec = desired_msec * static_cast<uint64_t>(1000000);	242✔
100
101	uint64_t est_nsec = measured_time;	242✔
102
103	// First increase r by 8x if possible
104	if(scrypt_parameters_acceptable(N, r * 8)) {	242✔
105	if(target_nsec / est_nsec >= 5) {	242✔
106	r *= 8;	1✔
107	est_nsec *= 5;	1✔
108	}
109	}
110
111	// Now double N as many times as we can
112	while(scrypt_parameters_acceptable(N * 2, r)) {	263✔
113	if(target_nsec / est_nsec >= 2) {	263✔
114	N *= 2;	21✔
115	est_nsec *= 2;	21✔
116	} else {
117	break;
118	}
119	}
120
121	// If we have extra runtime budget, increment p
122	if(target_nsec / est_nsec >= 2) {	242✔
123	p *= std::min<size_t>(1024, static_cast<size_t>(target_nsec / est_nsec));	×
124	}
125
126	return std::make_unique<Scrypt>(N, r, p);	242✔
127	}	242✔
128
129	std::unique_ptr<PasswordHash> Scrypt_Family::from_params(size_t N, size_t r, size_t p) const {	511✔
130	return std::make_unique<Scrypt>(N, r, p);	511✔
131	}
132
133	std::unique_ptr<PasswordHash> Scrypt_Family::from_iterations(size_t iter) const {	×
134	const size_t r = 8;	×
135	const size_t p = 1;	×
136
137	size_t N = 8192;	×
138
139	if(iter > 50000) {	×
140	N = 16384;	×
141	}
142	if(iter > 100000) {	×
143	N = 32768;	×
144	}
145	if(iter > 150000) {	×
146	N = 65536;	×
147	}
148
149	return std::make_unique<Scrypt>(N, r, p);	×
150	}
151
152	Scrypt::Scrypt(size_t N, size_t r, size_t p) : m_N(N), m_r(r), m_p(p) {	755✔
153	if(!is_power_of_2(N)) {	755✔
154	throw Invalid_Argument("Scrypt N parameter must be a power of 2");	×
155	}
156
157	if(p == 0 \|\| p > 1024) {	755✔
158	throw Invalid_Argument("Invalid or unsupported scrypt p");	×
159	}
160	if(r == 0 \|\| r > 256) {	755✔
161	throw Invalid_Argument("Invalid or unsupported scrypt r");	×
162	}
163	if(N < 1 \|\| N > MAX_SCRYPT_N) {	755✔
164	throw Invalid_Argument("Invalid or unsupported scrypt N");	×
165	}
166
167	if(const auto memory_usage = scrypt_memory_usage(N, r, p)) {	755✔
168	if(memory_usage > MAX_SCRYPT_MEMORY_BYTES) {	755✔
169	throw Invalid_Argument("Scrypt parameters exceed maximum allowed memory limit");	×
170	}
171	} else {
172	throw Invalid_Argument("Scrypt parameters are too large for this platform");	×
173	}
174	}	755✔
175
176	std::string Scrypt::to_string() const {	4✔
177	return fmt("Scrypt({},{},{})", m_N, m_r, m_p);	4✔
178	}
179
180	size_t Scrypt::total_memory_usage() const {	20✔
181	const size_t N = memory_param();	20✔
182	const size_t p = parallelism();	20✔
183	const size_t r = iterations();	20✔
184
185	const auto consumption = scrypt_memory_usage(N, r, p);	20✔
186	BOTAN_ASSERT_NOMSG(consumption.has_value());	20✔
187	return consumption.value();	20✔
188	}
189
190	namespace {
191
192	void scryptBlockMix(size_t r, uint8_t* B, uint8_t* Y) {	17,991,128✔
193	uint32_t B32[16];	17,991,128✔
194	secure_vector<uint8_t> X(64);	17,991,128✔
195	copy_mem(X.data(), &B[(2 * r - 1) * 64], 64);	17,991,128✔
196
197	for(size_t i = 0; i != 2 * r; i++) {	129,275,560✔
198	xor_buf(X.data(), &B[64 * i], 64);	111,284,432✔
199	load_le<uint32_t>(B32, X.data(), 16);	111,284,432✔
200	Salsa20::salsa_core(X.data(), B32, 8);	111,284,432✔
201	copy_mem(&Y[64 * i], X.data(), 64);	111,284,432✔
202	}
203
204	for(size_t i = 0; i < r; ++i) {	73,633,344✔
205	copy_mem(&B[i * 64], &Y[(i * 2) * 64], 64);	55,642,216✔
206	}
207
208	for(size_t i = 0; i < r; ++i) {	73,633,344✔
209	copy_mem(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64);	55,642,216✔
210	}
211	}	17,991,128✔
212
213	void scryptROMmix(size_t r, size_t N, uint8_t* B, secure_vector<uint8_t>& V) {	1,118✔
214	const size_t S = 128 * r;	1,118✔
215
216	for(size_t i = 0; i != N; ++i) {	8,996,682✔
217	copy_mem(&V[S * i], B, S);	8,995,564✔
218	scryptBlockMix(r, B, &V[N * S]);	8,995,564✔
219	}
220
221	for(size_t i = 0; i != N; ++i) {	8,996,682✔
222	// compiler doesn't know here that N is power of 2
223	const size_t j = load_le<uint32_t>(&B[(2 * r - 1) * 64], 0) & (N - 1);	8,995,564✔
224	xor_buf(B, &V[j * S], S);	8,995,564✔
225	scryptBlockMix(r, B, &V[N * S]);	8,995,564✔
226	}
227	}	1,118✔
228
229	} // namespace
230
231	void Scrypt::derive_key(uint8_t output[],	755✔
232	size_t output_len,
233	const char* password,
234	size_t password_len,
235	const uint8_t salt[],
236	size_t salt_len) const {
237	if(output_len == 0) {	755✔
238	return;	×
239	}
240
241	const size_t N = memory_param();	755✔
242	const size_t p = parallelism();	755✔
243	const size_t r = iterations();	755✔
244
245	const size_t S = 128 * r;	755✔
246	secure_vector<uint8_t> B(p * S);	755✔
247	// temp space
248	secure_vector<uint8_t> V((N + 1) * S);	755✔
249
250	auto hmac_sha256 = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)");	755✔
251
252	try {	755✔
253	hmac_sha256->set_key(as_span_of_bytes(password, password_len));	755✔
254	} catch(Invalid_Key_Length&) {	×
255	throw Invalid_Argument("Scrypt cannot accept passphrases of the provided length");	×
256	}	×
257
258	pbkdf2(*hmac_sha256, B.data(), B.size(), salt, salt_len, 1);	755✔
259
260	// these can be parallel
261	for(size_t i = 0; i != p; ++i) {	1,873✔
262	scryptROMmix(r, N, &B[128 * r * i], V);	1,118✔
263	}
264
265	pbkdf2(*hmac_sha256, output, output_len, B.data(), B.size(), 1);	755✔
266	}	2,265✔
267
268	} // namespace Botan

randombit / botan / 26703548991

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous