Crypto++ 7.0 Free C++ class library of cryptographic schemes

scrypt.cpp
1 // scrypt.cpp - written and placed in public domain by Jeffrey Walton.
2 // Based on reference source code by Colin Percival for
3 // Scrypt and Daniel Bernstein for Salsa20 core.
4
5 #include "pch.h"
6
7 #include "scrypt.h"
8 #include "algparam.h"
9 #include "argnames.h"
10 #include "pwdbased.h"
11 #include "stdcpp.h"
12 #include "salsa.h"
13 #include "misc.h"
14 #include "sha.h"
15
16 #include <sstream>
17 #ifdef _OPENMP
18 # include <omp.h>
19 #endif
20
21 ANONYMOUS_NAMESPACE_BEGIN
22
23 using CryptoPP::byte;
24 using CryptoPP::word32;
25 using CryptoPP::word64;
26 using CryptoPP::GetWord;
27 using CryptoPP::PutWord;
28 using CryptoPP::Salsa20_Core;
29 using CryptoPP::rotlConstant;
30 using CryptoPP::LITTLE_ENDIAN_ORDER;
31 using CryptoPP::AlignedSecByteBlock;
32
33 static inline void LE32ENC(byte* out, word32 in)
34 {
35 PutWord(false, LITTLE_ENDIAN_ORDER, out, in);
36 }
37
38 static inline word32 LE32DEC(const byte* in)
39 {
40 return GetWord<word32>(false, LITTLE_ENDIAN_ORDER, in);
41 }
42
43 static inline word64 LE64DEC(const byte* in)
44 {
45 return GetWord<word64>(false, LITTLE_ENDIAN_ORDER, in);
46 }
47
48 static inline void BlockCopy(byte* dest, byte* src, size_t len)
49 {
50 for (size_t i = 0; i < len; ++i)
51 dest[i] = src[i];
52 }
53
54 static inline void BlockXOR(byte* dest, byte* src, size_t len)
55 {
56 #pragma omp simd
57 for (size_t i = 0; i < len; ++i)
58 dest[i] ^= src[i];
59 }
60
61 static inline void PBKDF2_SHA256(byte* buf, size_t dkLen,
62 const byte* passwd, size_t passwdlen,
63 const byte* salt, size_t saltlen, byte count)
64 {
65 using CryptoPP::SHA256;
66 using CryptoPP::PKCS5_PBKDF2_HMAC;
67
68 PKCS5_PBKDF2_HMAC<SHA256> pbkdf;
69 pbkdf.DeriveKey(buf, dkLen, 0, passwd, passwdlen, salt, saltlen, count, 0.0f);
70 }
71
72 static inline void Salsa20_8(byte B[64])
73 {
74 word32 B32[16];
75
76 for (size_t i = 0; i < 16; ++i)
77 B32[i] = LE32DEC(&B[i * 4]);
78
79 Salsa20_Core(B32, 8);
80
81 for (size_t i = 0; i < 16; ++i)
82 LE32ENC(&B[4 * i], B32[i]);
83 }
84
85 static inline void BlockMix(byte* B, byte* Y, size_t r)
86 {
87 byte X[64];
88
89 // 1: X <-- B_{2r - 1}
90 BlockCopy(X, &B[(2 * r - 1) * 64], 64);
91
92 // 2: for i = 0 to 2r - 1 do
93 for (size_t i = 0; i < 2 * r; ++i)
94 {
95 // 3: X <-- H(X \xor B_i)
96 BlockXOR(X, &B[i * 64], 64);
97 Salsa20_8(X);
98
99 // 4: Y_i <-- X
100 BlockCopy(&Y[i * 64], X, 64);
101 }
102
103 // 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1})
104 for (size_t i = 0; i < r; ++i)
105 BlockCopy(&B[i * 64], &Y[(i * 2) * 64], 64);
106
107 for (size_t i = 0; i < r; ++i)
108 BlockCopy(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64);
109 }
110
111 static inline word64 Integerify(byte* B, size_t r)
112 {
113 byte* X = &B[(2 * r - 1) * 64];
114 return LE64DEC(X);
115 }
116
117 static inline void Smix(byte* B, size_t r, word64 N, byte* V, byte* XY)
118 {
119 byte* X = XY;
120 byte* Y = XY+128*r;
121
122 // 1: X <-- B
123 BlockCopy(X, B, 128 * r);
124
125 // 2: for i = 0 to N - 1 do
126 for (word64 i = 0; i < N; ++i)
127 {
128 // 3: V_i <-- X
129 BlockCopy(&V[i * (128 * r)], X, 128 * r);
130
131 // 4: X <-- H(X)
132 BlockMix(X, Y, r);
133 }
134
135 // 6: for i = 0 to N - 1 do
136 for (word64 i = 0; i < N; ++i)
137 {
138 // 7: j <-- Integerify(X) mod N
139 word64 j = Integerify(X, r) & (N - 1);
140
141 // 8: X <-- H(X \xor V_j)
142 BlockXOR(X, &V[j * (128 * r)], 128 * r);
143 BlockMix(X, Y, r);
144 }
145
146 // 10: B' <-- X
147 BlockCopy(B, X, 128 * r);
148 }
149
150 ANONYMOUS_NAMESPACE_END
151
152 NAMESPACE_BEGIN(CryptoPP)
153
154 size_t Scrypt::GetValidDerivedLength(size_t keylength) const
155 {
156 if (keylength > MaxDerivedLength())
157 return MaxDerivedLength();
158 return keylength;
159 }
160
161 void Scrypt::ValidateParameters(size_t derivedLen, word64 cost, word64 blockSize, word64 parallelization) const
162 {
163 // Optimizer should remove this on 32-bit platforms
164 if (std::numeric_limits<size_t>::max() > std::numeric_limits<word32>::max())
165 {
166 const word64 maxLen = ((static_cast<word64>(1) << 32) - 1) * 32;
167 if (derivedLen > maxLen) {
168 std::ostringstream oss;
169 oss << "derivedLen " << derivedLen << " is larger than " << maxLen;
170 throw InvalidArgument("Scrypt: " + oss.str());
171 }
172 }
173
174 CRYPTOPP_ASSERT(IsPowerOf2(cost));
175 if (IsPowerOf2(cost) == false)
176 throw InvalidArgument("Scrypt: cost must be a power of 2");
177
178 const word64 prod = static_cast<word64>(blockSize) * parallelization;
179 CRYPTOPP_ASSERT(prod < (1U << 30));
180
181 if (prod >= (1U << 30)) {
182 std::ostringstream oss;
183 oss << "r*p " << prod << " is larger than " << (1U << 30);
184 throw InvalidArgument("Scrypt: " + oss.str());
185 }
186
187 // Scrypt has several tests that effectively verify allocations like
188 // '128 * r * N' and '128 * r * p' do not overflow. They are the tests
189 // that set errno to ENOMEM. We can make the logic a little more clear
190 // using word128. At first blush the word128 may seem like overkill.
191 // However, this alogirthm is dominated by slow moving parts, so a
192 // one-time check is insignificant in the bigger picture.
193 #if defined(CRYPTOPP_WORD128_AVAILABLE)
194 const word128 maxElems = static_cast<word128>(SIZE_MAX);
195 bool bLimit = (maxElems >= static_cast<word128>(cost) * blockSize * 128U);
196 bool xyLimit = (maxElems >= static_cast<word128>(parallelization) * blockSize * 128U);
197 bool vLimit = (maxElems >= static_cast<word128>(blockSize) * 256U + 64U);
198 #else
199 const word64 maxElems = static_cast<word64>(SIZE_MAX);
200 bool bLimit = (blockSize < maxElems / 128U / cost);
201 bool xyLimit = (blockSize < maxElems / 128U / parallelization);
202 bool vLimit = (blockSize < (maxElems - 64U) / 256U);
203 #endif
204
205 CRYPTOPP_ASSERT(bLimit); CRYPTOPP_ASSERT(xyLimit); CRYPTOPP_ASSERT(vLimit);
206 if (!bLimit || !xyLimit || !vLimit)
207 throw std::bad_alloc();
208 }
209
210 size_t Scrypt::DeriveKey(byte*derived, size_t derivedLen,
211 const byte*secret, size_t secretLen, const NameValuePairs& params) const
212 {
213 CRYPTOPP_ASSERT(secret /*&& secretLen*/);
214 CRYPTOPP_ASSERT(derived && derivedLen);
215 CRYPTOPP_ASSERT(derivedLen <= MaxDerivedLength());
216
217 word64 cost=0, blockSize=0, parallelization=0;
218 if(params.GetValue("Cost", cost) == false)
219 cost = defaultCost;
220
221 if(params.GetValue("BlockSize", blockSize) == false)
222 blockSize = defaultBlockSize;
223
224 if(params.GetValue("Parallelization", parallelization) == false)
225 parallelization = defaultParallelization;
226
227 ConstByteArrayParameter salt;
228 (void)params.GetValue("Salt", salt);
229
230 return DeriveKey(derived, derivedLen, secret, secretLen, salt.begin(), salt.size(), cost, blockSize, parallelization);
231 }
232
233 size_t Scrypt::DeriveKey(byte*derived, size_t derivedLen, const byte*secret, size_t secretLen,
234 const byte*salt, size_t saltLen, word64 cost, word64 blockSize, word64 parallel) const
235 {
236 CRYPTOPP_ASSERT(secret /*&& secretLen*/);
237 CRYPTOPP_ASSERT(derived && derivedLen);
238 CRYPTOPP_ASSERT(derivedLen <= MaxDerivedLength());
239
240 ThrowIfInvalidDerivedLength(derivedLen);
241 ValidateParameters(derivedLen, cost, blockSize, parallel);
242
243 AlignedSecByteBlock B(static_cast<size_t>(blockSize * parallel * 128U));
244
245 // 1: (B_0 ... B_{p-1}) <-- PBKDF2(P, S, 1, p * MFLen)
246 PBKDF2_SHA256(B, B.size(), secret, secretLen, salt, saltLen, 1);
247
248 #ifdef _OPENMP
249 int threads = STDMIN(omp_get_max_threads(),
250 static_cast<int>(STDMIN(static_cast<size_t>(parallel),
251 static_cast<size_t>(std::numeric_limits<int>::max()))));
252 #endif
253
254 // http://stackoverflow.com/q/49604260/608639
255 #pragma omp parallel num_threads(threads)
256 {
257 // Each thread gets its own copy
258 AlignedSecByteBlock XY(static_cast<size_t>(blockSize * 256U));
259 AlignedSecByteBlock V(static_cast<size_t>(blockSize * cost * 128U));
260
261 // 2: for i = 0 to p - 1 do
262 #pragma omp for
263 for (size_t i = 0; i < static_cast<size_t>(parallel); ++i)
264 {
265 // 3: B_i <-- MF(B_i, N)
266 const ptrdiff_t offset = static_cast<ptrdiff_t>(blockSize*i*128);
267 Smix(B+offset, static_cast<size_t>(blockSize), cost, V, XY);
268 }
269 }
270
271 // 5: DK <-- PBKDF2(P, B, 1, dkLen)
272 PBKDF2_SHA256(derived, derivedLen, secret, secretLen, B, B.size(), 1);
273
274 return 1;
275 }
276
277 NAMESPACE_END
ConstByteArrayParameter
Used to pass byte array input as part of a NameValuePairs object.
Definition: algparam.h:20
argnames.h
Standard names for retrieving values by name when working with NameValuePairs.
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:202
algparam.h
Classes for working with NameValuePairs.
misc.h
Utility functions for the Crypto++ library.
ConstByteArrayParameter::size
size_t size() const
Length of the memory block.
Definition: algparam.h:84
PutWord
void PutWord(bool assumeAligned, ByteOrder order, byte *block, T value, const byte *xorBlock=NULL)
Access a block of memory.
Definition: misc.h:2362
stdcpp.h
Common C++ header files.
Scrypt::MaxDerivedLength
size_t MaxDerivedLength() const
Determine maximum number of bytes.
Definition: scrypt.h:48
LITTLE_ENDIAN_ORDER
byte order is little-endian
Definition: cryptlib.h:145
PKCS5_PBKDF2_HMAC
PBKDF2 from PKCS #5.
Definition: pwdbased.h:149
PKCS5_PBKDF2_HMAC::DeriveKey
size_t DeriveKey(byte *derived, size_t derivedLen, const byte *secret, size_t secretLen, const NameValuePairs &params=g_nullNameValuePairs) const
Derive a key from a seed.
Definition: pwdbased.h:215
GetWord
T GetWord(bool assumeAligned, ByteOrder order, const byte *block)
Access a block of memory.
Definition: misc.h:2320
ConstByteArrayParameter::begin
const byte * begin() const
Pointer to the first byte in the memory block.
Definition: algparam.h:80
rotlConstant
T rotlConstant(T x)
Performs a left rotate.
Definition: misc.h:1433
Salsa20_Core
void Salsa20_Core(word32 *data, unsigned int rounds)
Salsa20 core transform.
Definition: salsa.cpp:39
pch.h
Precompiled header file.
IsPowerOf2
bool IsPowerOf2(const T &value)
Tests whether a value is a power of 2.
Definition: misc.h:915
AlignedSecByteBlock
SecBlock using AllocatorWithCleanup<byte, true> typedef.
Definition: secblock.h:1056
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:563
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:60
scrypt.h
Classes for Scrypt from RFC 7914.
sha.h
Classes for SHA-1 and SHA-2 family of message digests.
salsa.h
Classes for Salsa and Salsa20 stream ciphers.
pwdbased.h
Password based key derivation functions.
Scrypt::DeriveKey
size_t DeriveKey(byte *derived, size_t derivedLen, const byte *secret, size_t secretLen, const NameValuePairs &params) const
Derive a key from a seed.
Definition: scrypt.cpp:210
CryptoPP
Crypto++ library namespace.
NameValuePairs::GetValue
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:350
Scrypt
Scrypt key derivation function.
Definition: scrypt.h:33
SecBlock::size
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:791
SIZE_MAX
#define SIZE_MAX
The maximum value of a machine word.
Definition: misc.h:85
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:293