20698655531

Committed 04 Jan 2026 08:25PM UTC coverage: 90.416% (-0.009%) from 90.425%

Build # 20698655531

Build Type

Pull #5124

github

Committed by

web-flow

Commit Message

Merge 627aed356 into f283c5d29

Pull Request Pull Request #5124: Cooperative Cancellation in PasswordHash

Run Details

101700 of 112480 relevant lines covered (90.42%)

13010053.87 hits per line

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

82.24

/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/loadstor.h>
#include <botan/internal/mem_utils.h>
#include <botan/internal/salsa20.h>
#include <botan/internal/time_utils.h>

namespace Botan {

namespace {

size_t scrypt_memory_usage(size_t N, size_t r, size_t p) {
   return 128 * r * (N + p);
}

}  // 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(size_t output_length,
                                                  std::chrono::milliseconds msec,
                                                  size_t max_memory_usage_mb,
                                                  std::chrono::milliseconds tune_time) const {
   BOTAN_UNUSED(output_length);

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

   // This is zero if max_memory_usage_mb == 0 (unbounded)
   const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024;

   // 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(tune_time, [&]() {
      uint8_t output[32] = {0};
      pwdhash->derive_key(output, sizeof(output), "test", 4, nullptr, 0);
   });

   const uint64_t target_nsec = msec.count() * static_cast<uint64_t>(1000000);

   uint64_t est_nsec = measured_time;

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

   // First increase r by 8x if possible
   if(max_memory_usage == 0 || scrypt_memory_usage(N, r * 8, 0) <= max_memory_usage) {
      if(target_nsec / est_nsec >= 5) {
         r *= 8;
         est_nsec *= 5;
      }
   }

   // Now double N as many times as we can
   while(max_memory_usage == 0 || scrypt_memory_usage(N * 2, r, 0) <= max_memory_usage) {
      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 > 4194304) {
      throw Invalid_Argument("Invalid or unsupported scrypt N");
   }
}

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();

   return scrypt_memory_usage(N, r, p);
}

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 std::optional<std::stop_token>& stop_token) {
   const size_t S = 128 * r;

   for(size_t i = 0; i != N; ++i) {
      if((i & 63) == 0 && stop_token.has_value() && stop_token->stop_requested()) {
         throw Botan::Operation_Canceled("scrypt");
      }
      copy_mem(&V[S * i], B, S);
      scryptBlockMix(r, B, &V[N * S]);
   }

   for(size_t i = 0; i != N; ++i) {
      if((i & 63) == 0 && stop_token.has_value() && stop_token->stop_requested()) {
         throw Botan::Operation_Canceled("scrypt");
      }
      // 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 std::optional<std::stop_token>& stop_token) const {
   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, stop_token);
   }

   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/loadstor.h>
15	#include <botan/internal/mem_utils.h>
16	#include <botan/internal/salsa20.h>
17	#include <botan/internal/time_utils.h>
18
19	namespace Botan {
20
21	namespace {
22
23	size_t scrypt_memory_usage(size_t N, size_t r, size_t p) {	27✔
24	return 128 * r * (N + p);	27✔
25	}
26
27	} // namespace
28
29	std::string Scrypt_Family::name() const {	1✔
30	return "Scrypt";	1✔
31	}
32
33	std::unique_ptr<PasswordHash> Scrypt_Family::default_params() const {	2✔
34	return std::make_unique<Scrypt>(32768, 8, 1);	2✔
35	}
36
37	std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,	243✔
38	std::chrono::milliseconds msec,
39	size_t max_memory_usage_mb,
40	std::chrono::milliseconds tune_time) const {
41	BOTAN_UNUSED(output_length);	243✔
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	* Empirically for smaller sizes:
48	* stime(N,8*r,p) / stime(N,r,p) is ~ 6-7
49	* stime(N,r,8p) / stime(N,r,8p) 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	// This is zero if max_memory_usage_mb == 0 (unbounded)
56	const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024;	243✔
57
58	// Starting parameters
59	size_t N = 8 * 1024;	243✔
60	size_t r = 1;	243✔
61	size_t p = 1;	243✔
62
63	auto pwdhash = this->from_params(N, r, p);	243✔
64
65	const uint64_t measured_time = measure_cost(tune_time, [&]() {	243✔
66	uint8_t output[32] = {0};	244✔
67	pwdhash->derive_key(output, sizeof(output), "test", 4, nullptr, 0);	244✔
68	});	244✔
69
70	const uint64_t target_nsec = msec.count() * static_cast<uint64_t>(1000000);	243✔
71
72	uint64_t est_nsec = measured_time;	243✔
73
74	// In below code we invoke scrypt_memory_usage with p == 0 as p contributes
75	// (very slightly) to memory consumption, but N is the driving factor.
76	// Including p leads to using an N half as large as what the user would expect.
77
78	// First increase r by 8x if possible
79	if(max_memory_usage == 0 \|\| scrypt_memory_usage(N, r * 8, 0) <= max_memory_usage) {	243✔
80	if(target_nsec / est_nsec >= 5) {	243✔
81	r *= 8;	5✔
82	est_nsec *= 5;	5✔
83	}
84	}
85
86	// Now double N as many times as we can
87	while(max_memory_usage == 0 \|\| scrypt_memory_usage(N * 2, r, 0) <= max_memory_usage) {	258✔
88	if(target_nsec / est_nsec >= 2) {	257✔
89	N *= 2;	15✔
90	est_nsec *= 2;	15✔
91	} else {
92	break;
93	}
94	}
95
96	// If we have extra runtime budget, increment p
97	if(target_nsec / est_nsec >= 2) {	243✔
98	p *= std::min<size_t>(1024, static_cast<size_t>(target_nsec / est_nsec));	2✔
99	}
100
101	return std::make_unique<Scrypt>(N, r, p);	243✔
102	}	243✔
103
104	std::unique_ptr<PasswordHash> Scrypt_Family::from_params(size_t N, size_t r, size_t p) const {	512✔
105	return std::make_unique<Scrypt>(N, r, p);	512✔
106	}
107
108	std::unique_ptr<PasswordHash> Scrypt_Family::from_iterations(size_t iter) const {	×
109	const size_t r = 8;	×
110	const size_t p = 1;	×
111
112	size_t N = 8192;	×
113
114	if(iter > 50000) {	×
115	N = 16384;	×
116	}
117	if(iter > 100000) {	×
118	N = 32768;	×
119	}
120	if(iter > 150000) {	×
121	N = 65536;	×
122	}
123
124	return std::make_unique<Scrypt>(N, r, p);	×
125	}
126
127	Scrypt::Scrypt(size_t N, size_t r, size_t p) : m_N(N), m_r(r), m_p(p) {	757✔
128	if(!is_power_of_2(N)) {	757✔
129	throw Invalid_Argument("Scrypt N parameter must be a power of 2");	×
130	}
131
132	if(p == 0 \|\| p > 1024) {	757✔
133	throw Invalid_Argument("Invalid or unsupported scrypt p");	×
134	}
135	if(r == 0 \|\| r > 256) {	757✔
136	throw Invalid_Argument("Invalid or unsupported scrypt r");	×
137	}
138	if(N < 1 \|\| N > 4194304) {	757✔
139	throw Invalid_Argument("Invalid or unsupported scrypt N");	×
140	}
141	}	757✔
142
143	std::string Scrypt::to_string() const {	4✔
144	return fmt("Scrypt({},{},{})", m_N, m_r, m_p);	4✔
145	}
146
147	size_t Scrypt::total_memory_usage() const {	20✔
148	const size_t N = memory_param();	20✔
149	const size_t p = parallelism();	20✔
150	const size_t r = iterations();	20✔
151
152	return scrypt_memory_usage(N, r, p);	20✔
153	}
154
155	namespace {
156
157	void scryptBlockMix(size_t r, uint8_t* B, uint8_t* Y) {	17,712,600✔
158	uint32_t B32[16];	17,712,600✔
159	secure_vector<uint8_t> X(64);	17,712,600✔
160	copy_mem(X.data(), &B[(2 * r - 1) * 64], 64);	17,712,600✔
161
162	for(size_t i = 0; i != 2 * r; i++) {	129,357,480✔
163	xor_buf(X.data(), &B[64 * i], 64);	111,644,880✔
164	load_le<uint32_t>(B32, X.data(), 16);	111,644,880✔
165	Salsa20::salsa_core(X.data(), B32, 8);	111,644,880✔
166	copy_mem(&Y[64 * i], X.data(), 64);	111,644,880✔
167	}
168
169	for(size_t i = 0; i < r; ++i) {	73,535,040✔
170	copy_mem(&B[i * 64], &Y[(i * 2) * 64], 64);	55,822,440✔
171	}
172
173	for(size_t i = 0; i < r; ++i) {	73,535,040✔
174	copy_mem(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64);	55,822,440✔
175	}
176	}	17,712,600✔
177
178	void scryptROMmix(	1,121✔
179	size_t r, size_t N, uint8_t* B, secure_vector<uint8_t>& V, const std::optional<std::stop_token>& stop_token) {
180	const size_t S = 128 * r;	1,121✔
181
182	for(size_t i = 0; i != N; ++i) {	8,857,421✔
183	if((i & 63) == 0 && stop_token.has_value() && stop_token->stop_requested()) {	8,856,301✔
184	throw Botan::Operation_Canceled("scrypt");	1✔
185	}
186	copy_mem(&V[S * i], B, S);	8,856,300✔
187	scryptBlockMix(r, B, &V[N * S]);	8,856,300✔
188	}
189
190	for(size_t i = 0; i != N; ++i) {	8,857,420✔
191	if((i & 63) == 0 && stop_token.has_value() && stop_token->stop_requested()) {	8,856,300✔
192	throw Botan::Operation_Canceled("scrypt");	×
193	}
194	// compiler doesn't know here that N is power of 2
195	const size_t j = load_le<uint32_t>(&B[(2 * r - 1) * 64], 0) & (N - 1);	8,856,300✔
196	xor_buf(B, &V[j * S], S);	8,856,300✔
197	scryptBlockMix(r, B, &V[N * S]);	8,856,300✔
198	}
199	}	1,120✔
200
201	} // namespace
202
203	void Scrypt::derive_key(uint8_t output[],	758✔
204	size_t output_len,
205	const char* password,
206	size_t password_len,
207	const uint8_t salt[],
208	size_t salt_len,
209	const std::optional<std::stop_token>& stop_token) const {
210	const size_t N = memory_param();	758✔
211	const size_t p = parallelism();	758✔
212	const size_t r = iterations();	758✔
213
214	const size_t S = 128 * r;	758✔
215	secure_vector<uint8_t> B(p * S);	758✔
216	// temp space
217	secure_vector<uint8_t> V((N + 1) * S);	759✔
218
219	auto hmac_sha256 = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)");	759✔
220
221	try {	758✔
222	hmac_sha256->set_key(as_span_of_bytes(password, password_len));	758✔
223	} catch(Invalid_Key_Length&) {	×
224	throw Invalid_Argument("Scrypt cannot accept passphrases of the provided length");	×
225	}	×
226
227	pbkdf2(*hmac_sha256, B.data(), B.size(), salt, salt_len, 1);	758✔
228
229	// these can be parallel
230	for(size_t i = 0; i != p; ++i) {	1,878✔
231	scryptROMmix(r, N, &B[128 * r * i], V, stop_token);	1,121✔
232	}
233
234	pbkdf2(*hmac_sha256, output, output_len, B.data(), B.size(), 1);	1,515✔
235	}	2,273✔
236
237	} // namespace Botan

randombit / botan / 20698655531

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