5079590438

Committed 25 May 2023 12:28PM UTC coverage: 92.228% (+0.5%) from 91.723%

Build # 5079590438

Build Type

Pull #3502

github

Pull Request Pull Request #3502: Apply clang-format to the codebase

Run Details

75589 of 81959 relevant lines covered (92.23%)

12139530.51 hits per line

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

79.0

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

namespace Botan {

namespace {

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

}

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

   // We include a bit of slop here (the + 512) to handle the fact that scrypt's
   // memory consumption is modified by all three parameters, and otherwise we
   // stop before hitting the desired target.

   const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024 + 512;
   // Starting parameters
   size_t N = 8 * 1024;
   size_t r = 1;
   size_t p = 1;

   Timer timer("Scrypt");

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

   timer.run_until_elapsed(tune_time, [&]() {
      uint8_t output[32] = {0};
      pwdhash->derive_key(output, sizeof(output), "test", 4, nullptr, 0);
   });

   // No timer events seems strange, perhaps something is wrong - give
   // up on this and just return default params
   if(timer.events() == 0)
      return default_params();

   // nsec per eval of scrypt with initial params
   const uint64_t measured_time = timer.value() / timer.events();

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

   uint64_t est_nsec = measured_time;

   // First move increase r by 8x if possible

   if(max_memory_usage == 0 || scrypt_memory_usage(N, r * 8, p) <= 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, p) <= 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 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]);
   }
}

}

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 {
   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(cast_char_ptr_to_uint8(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);
}

}

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
18	namespace Botan {
19
20	namespace {
21
22	size_t scrypt_memory_usage(size_t N, size_t r, size_t p) { return 128 * r * (N + p); }	226✔
23
24	}
25
26	std::string Scrypt_Family::name() const { return "Scrypt"; }	1✔
27
28	std::unique_ptr<PasswordHash> Scrypt_Family::default_params() const { return std::make_unique<Scrypt>(32768, 8, 1); }	2✔
29
30	std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,	103✔
31	std::chrono::milliseconds msec,
32	size_t max_memory_usage_mb,
33	std::chrono::milliseconds tune_time) const {
34	BOTAN_UNUSED(output_length);	103✔
35
36	/*
37	* Some rough relations between scrypt parameters and runtime.
38	* Denote here by stime(N,r,p) the msec it takes to run scrypt.
39	*
40	* Emperically for smaller sizes:
41	* stime(N,8*r,p) / stime(N,r,p) is ~ 6-7
42	* stime(N,r,8p) / stime(N,r,8p) is ~ 7
43	* stime(2*N,r,p) / stime(N,r,p) is ~ 2
44	*
45	* Compute stime(8192,1,1) as baseline and extrapolate
46	*/
47
48	// We include a bit of slop here (the + 512) to handle the fact that scrypt's
49	// memory consumption is modified by all three parameters, and otherwise we
50	// stop before hitting the desired target.
51
52	const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024 + 512;	103✔
53	// Starting parameters
54	size_t N = 8 * 1024;	103✔
55	size_t r = 1;	103✔
56	size_t p = 1;	103✔
57
58	Timer timer("Scrypt");	103✔
59
60	auto pwdhash = this->from_params(N, r, p);	103✔
61
62	timer.run_until_elapsed(tune_time, [&]() {	103✔
63	uint8_t output[32] = {0};	103✔
64	pwdhash->derive_key(output, sizeof(output), "test", 4, nullptr, 0);	103✔
65	});
66
67	// No timer events seems strange, perhaps something is wrong - give
68	// up on this and just return default params
69	if(timer.events() == 0)	103✔
70	return default_params();	×
71
72	// nsec per eval of scrypt with initial params
73	const uint64_t measured_time = timer.value() / timer.events();	103✔
74
75	const uint64_t target_nsec = msec.count() * static_cast<uint64_t>(1000000);	103✔
76
77	uint64_t est_nsec = measured_time;	103✔
78
79	// First move increase r by 8x if possible
80
81	if(max_memory_usage == 0 \|\| scrypt_memory_usage(N, r * 8, p) <= max_memory_usage) {	103✔
82	if(target_nsec / est_nsec >= 5) {	4✔
83	r *= 8;	×
84	est_nsec *= 5;	×
85	}
86	}
87
88	// Now double N as many times as we can
89
90	while(max_memory_usage == 0 \|\| scrypt_memory_usage(N * 2, r, p) <= max_memory_usage) {	103✔
91	if(target_nsec / est_nsec >= 2) {	4✔
92	N *= 2;	×
93	est_nsec *= 2;	×
94	} else
95	break;
96	}
97
98	// If we have extra runtime budget, increment p
99
100	if(target_nsec / est_nsec > 2)	103✔
101	p *= std::min<size_t>(1024, static_cast<size_t>(target_nsec / est_nsec));	8✔
102
103	return std::make_unique<Scrypt>(N, r, p);	103✔
104	}	103✔
105
106	std::unique_ptr<PasswordHash> Scrypt_Family::from_params(size_t N, size_t r, size_t p) const {	233✔
107	return std::make_unique<Scrypt>(N, r, p);	233✔
108	}
109
110	std::unique_ptr<PasswordHash> Scrypt_Family::from_iterations(size_t iter) const {	×
111	const size_t r = 8;	×
112	const size_t p = 1;	×
113
114	size_t N = 8192;	×
115
116	if(iter > 50000)	×
117	N = 16384;	×
118	if(iter > 100000)	×
119	N = 32768;	×
120	if(iter > 150000)	×
121	N = 65536;	×
122
123	return std::make_unique<Scrypt>(N, r, p);	×
124	}
125
126	Scrypt::Scrypt(size_t N, size_t r, size_t p) : m_N(N), m_r(r), m_p(p) {	338✔
127	if(!is_power_of_2(N))	338✔
128	throw Invalid_Argument("Scrypt N parameter must be a power of 2");	×
129
130	if(p == 0 \|\| p > 1024)	338✔
131	throw Invalid_Argument("Invalid or unsupported scrypt p");	×
132	if(r == 0 \|\| r > 256)	338✔
133	throw Invalid_Argument("Invalid or unsupported scrypt r");	×
134	if(N < 1 \|\| N > 4194304)	338✔
135	throw Invalid_Argument("Invalid or unsupported scrypt N");	×
136	}	338✔
137
138	std::string Scrypt::to_string() const { return fmt("Scrypt({},{},{})", m_N, m_r, m_p); }	4✔
139
140	size_t Scrypt::total_memory_usage() const {	20✔
141	const size_t N = memory_param();	20✔
142	const size_t p = parallelism();	20✔
143	const size_t r = iterations();	20✔
144
145	return scrypt_memory_usage(N, r, p);	20✔
146	}
147
148	namespace {
149
150	void scryptBlockMix(size_t r, uint8_t* B, uint8_t* Y) {	10,749,400✔
151	uint32_t B32[16];	10,749,400✔
152	secure_vector<uint8_t> X(64);	10,749,400✔
153	copy_mem(X.data(), &B[(2 * r - 1) * 64], 64);	10,749,400✔
154
155	for(size_t i = 0; i != 2 * r; i++) {	106,632,872✔
156	xor_buf(X.data(), &B[64 * i], 64);	95,883,472✔
157	load_le<uint32_t>(B32, X.data(), 16);	95,883,472✔
158	Salsa20::salsa_core(X.data(), B32, 8);	95,883,472✔
159	copy_mem(&Y[64 * i], X.data(), 64);	95,883,472✔
160	}
161
162	for(size_t i = 0; i < r; ++i) {	58,691,136✔
163	copy_mem(&B[i * 64], &Y[(i * 2) * 64], 64);	47,941,736✔
164	}
165
166	for(size_t i = 0; i < r; ++i) {	58,691,136✔
167	copy_mem(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64);	47,941,736✔
168	}
169	}	10,749,400✔
170
171	void scryptROMmix(size_t r, size_t N, uint8_t* B, secure_vector<uint8_t>& V) {	731✔
172	const size_t S = 128 * r;	731✔
173
174	for(size_t i = 0; i != N; ++i) {	5,375,431✔
175	copy_mem(&V[S * i], B, S);	5,374,700✔
176	scryptBlockMix(r, B, &V[N * S]);	5,374,700✔
177	}
178
179	for(size_t i = 0; i != N; ++i) {	5,375,431✔
180	// compiler doesn't know here that N is power of 2
181	const size_t j = load_le<uint32_t>(&B[(2 * r - 1) * 64], 0) & (N - 1);	5,374,700✔
182	xor_buf(B, &V[j * S], S);	5,374,700✔
183	scryptBlockMix(r, B, &V[N * S]);	5,374,700✔
184	}
185	}	731✔
186
187	}
188
189	void Scrypt::derive_key(uint8_t output[],	338✔
190	size_t output_len,
191	const char* password,
192	size_t password_len,
193	const uint8_t salt[],
194	size_t salt_len) const {
195	const size_t N = memory_param();	338✔
196	const size_t p = parallelism();	338✔
197	const size_t r = iterations();	338✔
198
199	const size_t S = 128 * r;	338✔
200	secure_vector<uint8_t> B(p * S);	338✔
201	// temp space
202	secure_vector<uint8_t> V((N + 1) * S);	338✔
203
204	auto hmac_sha256 = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)");	338✔
205
206	try {	338✔
207	hmac_sha256->set_key(cast_char_ptr_to_uint8(password), password_len);	338✔
208	} catch(Invalid_Key_Length&) { throw Invalid_Argument("Scrypt cannot accept passphrases of the provided length"); }	×
209
210	pbkdf2(*hmac_sha256, B.data(), B.size(), salt, salt_len, 1);	338✔
211
212	// these can be parallel
213	for(size_t i = 0; i != p; ++i) {	1,069✔
214	scryptROMmix(r, N, &B[128 * r * i], V);	731✔
215	}
216
217	pbkdf2(*hmac_sha256, output, output_len, B.data(), B.size(), 1);	338✔
218	}	1,014✔
219
220	}

randombit / botan / 5079590438

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