1 /*
2 * fast-pbkdf2 - Optimal PBKDF2-HMAC calculation
3 * Written in 2015 by Joseph Birr-Pixton <jpixton@gmail.com>
4 * Ported to cryptonite in 2017 by Nicolas Di Prima <nicolas@primetype.co.uk>
5 *
6 * To the extent possible under law, the author(s) have dedicated all
7 * copyright and related and neighboring rights to this software to the
8 * public domain worldwide. This software is distributed without any
9 * warranty.
10 *
11 * You should have received a copy of the CC0 Public Domain Dedication
12 * along with this software. If not, see
13 * <http://creativecommons.org/publicdomain/zero/1.0/>.
14 */
15
16 #include <assert.h>
17 #include <string.h>
18
19 #include "cryptonite_pbkdf2.h"
20 #include "cryptonite_bitfn.h"
21 #include "cryptonite_align.h"
22 #include "cryptonite_sha1.h"
23 #include "cryptonite_sha256.h"
24 #include "cryptonite_sha512.h"
25
26 /* --- MSVC doesn't support C99 --- */
27 #ifdef _MSC_VER
28 #define restrict
29 #define _Pragma __pragma
30 #endif
31
32 /* --- Common useful things --- */
33 #define MIN(a, b) ((a) > (b)) ? (b) : (a)
34
35 /* Prepare block (of blocksz bytes) to contain md padding denoting a msg-size
36 * message (in bytes). block has a prefix of used bytes.
37 *
38 * Message length is expressed in 32 bits (so suitable for sha1, sha256, sha512). */
md_pad(uint8_t * block,size_t blocksz,size_t used,size_t msg)39 static inline void md_pad(uint8_t *block, size_t blocksz, size_t used, size_t msg)
40 {
41 memset(block + used, 0, blocksz - used - 4);
42 block[used] = 0x80;
43 block += blocksz - 4;
44 store_be32(block, (uint32_t) (msg * 8));
45 }
46
47 /* Internal function/type names for hash-specific things. */
48 #define HMAC_CTX(_name) HMAC_ ## _name ## _ctx
49 #define HMAC_INIT(_name) HMAC_ ## _name ## _init
50 #define HMAC_UPDATE(_name) HMAC_ ## _name ## _update
51 #define HMAC_FINAL(_name) HMAC_ ## _name ## _final
52
53 #define PBKDF2_F(_name) pbkdf2_f_ ## _name
54 #define PBKDF2(_name) pbkdf2_ ## _name
55
56 /* This macro expands to decls for the whole implementation for a given
57 * hash function. Arguments are:
58 *
59 * _name like 'sha1', added to symbol names
60 * _blocksz block size, in bytes
61 * _hashsz digest output, in bytes
62 * _ctx hash context type
63 * _init hash context initialisation function
64 * args: (_ctx *c)
65 * _update hash context update function
66 * args: (_ctx *c, const void *data, size_t ndata)
67 * _final hash context finish function
68 * args: (void *out, _ctx *c)
69 * _xform hash context raw block update function
70 * args: (_ctx *c, const void *data)
71 * _xcpy hash context raw copy function (only need copy hash state)
72 * args: (_ctx * restrict out, const _ctx *restrict in)
73 * _xtract hash context state extraction
74 * args: args (_ctx *restrict c, uint8_t *restrict out)
75 * _xxor hash context xor function (only need xor hash state)
76 * args: (_ctx *restrict out, const _ctx *restrict in)
77 *
78 * The resulting function is named PBKDF2(_name).
79 */
80 #define DECL_PBKDF2(_name, _blocksz, _hashsz, _ctx, \
81 _init, _update, _xform, _final, _xcpy, _xtract, _xxor) \
82 typedef struct { \
83 _ctx inner; \
84 _ctx outer; \
85 } HMAC_CTX(_name); \
86 \
87 static inline void HMAC_INIT(_name)(HMAC_CTX(_name) *ctx, \
88 const uint8_t *key, size_t nkey) \
89 { \
90 /* Prepare key: */ \
91 uint8_t k[_blocksz]; \
92 \
93 /* Shorten long keys. */ \
94 if (nkey > _blocksz) \
95 { \
96 _init(&ctx->inner); \
97 _update(&ctx->inner, key, nkey); \
98 _final(&ctx->inner, k); \
99 \
100 key = k; \
101 nkey = _hashsz; \
102 } \
103 \
104 /* Standard doesn't cover case where blocksz < hashsz. */ \
105 assert(nkey <= _blocksz); \
106 \
107 /* Right zero-pad short keys. */ \
108 if (k != key) \
109 memcpy(k, key, nkey); \
110 if (_blocksz > nkey) \
111 memset(k + nkey, 0, _blocksz - nkey); \
112 \
113 /* Start inner hash computation */ \
114 uint8_t blk_inner[_blocksz]; \
115 uint8_t blk_outer[_blocksz]; \
116 \
117 for (size_t i = 0; i < _blocksz; i++) \
118 { \
119 blk_inner[i] = 0x36 ^ k[i]; \
120 blk_outer[i] = 0x5c ^ k[i]; \
121 } \
122 \
123 _init(&ctx->inner); \
124 _update(&ctx->inner, blk_inner, sizeof blk_inner); \
125 \
126 /* And outer. */ \
127 _init(&ctx->outer); \
128 _update(&ctx->outer, blk_outer, sizeof blk_outer); \
129 } \
130 \
131 static inline void HMAC_UPDATE(_name)(HMAC_CTX(_name) *ctx, \
132 const void *data, size_t ndata) \
133 { \
134 _update(&ctx->inner, data, ndata); \
135 } \
136 \
137 static inline void HMAC_FINAL(_name)(HMAC_CTX(_name) *ctx, \
138 uint8_t out[_hashsz]) \
139 { \
140 _final(&ctx->inner, out); \
141 _update(&ctx->outer, out, _hashsz); \
142 _final(&ctx->outer, out); \
143 } \
144 \
145 \
146 /* --- PBKDF2 --- */ \
147 static inline void PBKDF2_F(_name)(const HMAC_CTX(_name) *startctx, \
148 uint32_t counter, \
149 const uint8_t *salt, size_t nsalt, \
150 uint32_t iterations, \
151 uint8_t *out) \
152 { \
153 uint8_t countbuf[4]; \
154 store_be32(countbuf, counter); \
155 \
156 /* Prepare loop-invariant padding block. */ \
157 uint8_t Ublock[_blocksz]; \
158 md_pad(Ublock, _blocksz, _hashsz, _blocksz + _hashsz); \
159 \
160 /* First iteration: \
161 * U_1 = PRF(P, S || INT_32_BE(i)) \
162 */ \
163 HMAC_CTX(_name) ctx = *startctx; \
164 HMAC_UPDATE(_name)(&ctx, salt, nsalt); \
165 HMAC_UPDATE(_name)(&ctx, countbuf, sizeof countbuf); \
166 HMAC_FINAL(_name)(&ctx, Ublock); \
167 _ctx result = ctx.outer; \
168 \
169 /* Subsequent iterations: \
170 * U_c = PRF(P, U_{c-1}) \
171 */ \
172 for (uint32_t i = 1; i < iterations; i++) \
173 { \
174 /* Complete inner hash with previous U */ \
175 _xcpy(&ctx.inner, &startctx->inner); \
176 _xform(&ctx.inner, Ublock); \
177 _xtract(&ctx.inner, Ublock); \
178 /* Complete outer hash with inner output */ \
179 _xcpy(&ctx.outer, &startctx->outer); \
180 _xform(&ctx.outer, Ublock); \
181 _xtract(&ctx.outer, Ublock); \
182 _xxor(&result, &ctx.outer); \
183 } \
184 \
185 /* Reform result into output buffer. */ \
186 _xtract(&result, out); \
187 } \
188 \
189 static inline void PBKDF2(_name)(const uint8_t *pw, size_t npw, \
190 const uint8_t *salt, size_t nsalt, \
191 uint32_t iterations, \
192 uint8_t *out, size_t nout) \
193 { \
194 assert(iterations); \
195 assert(out && nout); \
196 \
197 /* Starting point for inner loop. */ \
198 HMAC_CTX(_name) ctx; \
199 HMAC_INIT(_name)(&ctx, pw, npw); \
200 \
201 /* How many blocks do we need? */ \
202 uint32_t blocks_needed = (uint32_t)(nout + _hashsz - 1) / _hashsz; \
203 \
204 for (uint32_t counter = 1; counter <= blocks_needed; counter++) \
205 { \
206 uint8_t block[_hashsz]; \
207 PBKDF2_F(_name)(&ctx, counter, salt, nsalt, iterations, block); \
208 \
209 size_t offset = (counter - 1) * _hashsz; \
210 size_t taken = MIN(nout - offset, _hashsz); \
211 memcpy(out + offset, block, taken); \
212 } \
213 }
214
sha1_extract(struct sha1_ctx * restrict ctx,uint8_t * restrict out)215 static inline void sha1_extract(struct sha1_ctx *restrict ctx, uint8_t *restrict out)
216 {
217 store_be32(out , ctx->h[0]);
218 store_be32(out+4 , ctx->h[1]);
219 store_be32(out+8 , ctx->h[2]);
220 store_be32(out+12, ctx->h[3]);
221 store_be32(out+16, ctx->h[4]);
222 }
223
sha1_cpy(struct sha1_ctx * restrict out,const struct sha1_ctx * restrict in)224 static inline void sha1_cpy(struct sha1_ctx *restrict out, const struct sha1_ctx *restrict in)
225 {
226 out->h[0] = in->h[0];
227 out->h[1] = in->h[1];
228 out->h[2] = in->h[2];
229 out->h[3] = in->h[3];
230 out->h[4] = in->h[4];
231 }
232
sha1_xor(struct sha1_ctx * restrict out,const struct sha1_ctx * restrict in)233 static inline void sha1_xor(struct sha1_ctx *restrict out, const struct sha1_ctx *restrict in)
234 {
235 out->h[0] ^= in->h[0];
236 out->h[1] ^= in->h[1];
237 out->h[2] ^= in->h[2];
238 out->h[3] ^= in->h[3];
239 out->h[4] ^= in->h[4];
240 }
241
cryptonite_sha1_transform(struct sha1_ctx * ctx,uint8_t block[SHA1_BLOCK_SIZE])242 void cryptonite_sha1_transform(struct sha1_ctx* ctx, uint8_t block[SHA1_BLOCK_SIZE])
243 {
244 cryptonite_sha1_update(ctx, block, SHA1_BLOCK_SIZE);
245 }
246
247 DECL_PBKDF2(sha1,
248 SHA1_BLOCK_SIZE,
249 SHA1_DIGEST_SIZE,
250 struct sha1_ctx,
251 cryptonite_sha1_init,
252 cryptonite_sha1_update,
253 cryptonite_sha1_transform,
254 cryptonite_sha1_finalize,
255 sha1_cpy,
256 sha1_extract,
257 sha1_xor);
258
sha256_extract(struct sha256_ctx * restrict ctx,uint8_t * restrict out)259 static inline void sha256_extract(struct sha256_ctx *restrict ctx, uint8_t *restrict out)
260 {
261 store_be32(out , ctx->h[0]);
262 store_be32(out+4 , ctx->h[1]);
263 store_be32(out+8 , ctx->h[2]);
264 store_be32(out+12, ctx->h[3]);
265 store_be32(out+16, ctx->h[4]);
266 store_be32(out+20, ctx->h[5]);
267 store_be32(out+24, ctx->h[6]);
268 store_be32(out+28, ctx->h[7]);
269 }
270
sha256_cpy(struct sha256_ctx * restrict out,const struct sha256_ctx * restrict in)271 static inline void sha256_cpy(struct sha256_ctx *restrict out, const struct sha256_ctx *restrict in)
272 {
273 out->h[0] = in->h[0];
274 out->h[1] = in->h[1];
275 out->h[2] = in->h[2];
276 out->h[3] = in->h[3];
277 out->h[4] = in->h[4];
278 out->h[5] = in->h[5];
279 out->h[6] = in->h[6];
280 out->h[7] = in->h[7];
281 }
282
sha256_xor(struct sha256_ctx * restrict out,const struct sha256_ctx * restrict in)283 static inline void sha256_xor(struct sha256_ctx *restrict out, const struct sha256_ctx *restrict in)
284 {
285 out->h[0] ^= in->h[0];
286 out->h[1] ^= in->h[1];
287 out->h[2] ^= in->h[2];
288 out->h[3] ^= in->h[3];
289 out->h[4] ^= in->h[4];
290 out->h[5] ^= in->h[5];
291 out->h[6] ^= in->h[6];
292 out->h[7] ^= in->h[7];
293 }
294
cryptonite_sha256_transform(struct sha256_ctx * ctx,uint8_t block[SHA256_BLOCK_SIZE])295 void cryptonite_sha256_transform(struct sha256_ctx* ctx, uint8_t block[SHA256_BLOCK_SIZE])
296 {
297 cryptonite_sha256_update(ctx, block, SHA256_BLOCK_SIZE);
298 }
299
300 DECL_PBKDF2(sha256,
301 SHA256_BLOCK_SIZE,
302 SHA256_DIGEST_SIZE,
303 struct sha256_ctx,
304 cryptonite_sha256_init,
305 cryptonite_sha256_update,
306 cryptonite_sha256_transform,
307 cryptonite_sha256_finalize,
308 sha256_cpy,
309 sha256_extract,
310 sha256_xor);
311
sha512_extract(struct sha512_ctx * restrict ctx,uint8_t * restrict out)312 static inline void sha512_extract(struct sha512_ctx *restrict ctx, uint8_t *restrict out)
313 {
314 store_be64(out , ctx->h[0]);
315 store_be64(out+8 , ctx->h[1]);
316 store_be64(out+16, ctx->h[2]);
317 store_be64(out+24, ctx->h[3]);
318 store_be64(out+32, ctx->h[4]);
319 store_be64(out+40, ctx->h[5]);
320 store_be64(out+48, ctx->h[6]);
321 store_be64(out+56, ctx->h[7]);
322 }
323
sha512_cpy(struct sha512_ctx * restrict out,const struct sha512_ctx * restrict in)324 static inline void sha512_cpy(struct sha512_ctx *restrict out, const struct sha512_ctx *restrict in)
325 {
326 out->h[0] = in->h[0];
327 out->h[1] = in->h[1];
328 out->h[2] = in->h[2];
329 out->h[3] = in->h[3];
330 out->h[4] = in->h[4];
331 out->h[5] = in->h[5];
332 out->h[6] = in->h[6];
333 out->h[7] = in->h[7];
334 }
335
sha512_xor(struct sha512_ctx * restrict out,const struct sha512_ctx * restrict in)336 static inline void sha512_xor(struct sha512_ctx *restrict out, const struct sha512_ctx *restrict in)
337 {
338 out->h[0] ^= in->h[0];
339 out->h[1] ^= in->h[1];
340 out->h[2] ^= in->h[2];
341 out->h[3] ^= in->h[3];
342 out->h[4] ^= in->h[4];
343 out->h[5] ^= in->h[5];
344 out->h[6] ^= in->h[6];
345 out->h[7] ^= in->h[7];
346 }
347
cryptonite_sha512_transform(struct sha512_ctx * ctx,uint8_t block[SHA512_BLOCK_SIZE])348 void cryptonite_sha512_transform(struct sha512_ctx* ctx, uint8_t block[SHA512_BLOCK_SIZE])
349 {
350 cryptonite_sha512_update(ctx, block, SHA512_BLOCK_SIZE);
351 }
352
353 DECL_PBKDF2(sha512,
354 SHA512_BLOCK_SIZE,
355 SHA512_DIGEST_SIZE,
356 struct sha512_ctx,
357 cryptonite_sha512_init,
358 cryptonite_sha512_update,
359 cryptonite_sha512_transform,
360 cryptonite_sha512_finalize,
361 sha512_cpy,
362 sha512_extract,
363 sha512_xor);
364
cryptonite_fastpbkdf2_hmac_sha1(const uint8_t * pw,size_t npw,const uint8_t * salt,size_t nsalt,uint32_t iterations,uint8_t * out,size_t nout)365 void cryptonite_fastpbkdf2_hmac_sha1( const uint8_t *pw, size_t npw
366 , const uint8_t *salt, size_t nsalt
367 , uint32_t iterations
368 , uint8_t *out, size_t nout
369 )
370 {
371 PBKDF2(sha1)(pw, npw, salt, nsalt, iterations, out, nout);
372 }
373
cryptonite_fastpbkdf2_hmac_sha256(const uint8_t * pw,size_t npw,const uint8_t * salt,size_t nsalt,uint32_t iterations,uint8_t * out,size_t nout)374 void cryptonite_fastpbkdf2_hmac_sha256( const uint8_t *pw, size_t npw
375 , const uint8_t *salt, size_t nsalt
376 , uint32_t iterations
377 , uint8_t *out, size_t nout
378 )
379 {
380 PBKDF2(sha256)(pw, npw, salt, nsalt, iterations, out, nout);
381 }
382
cryptonite_fastpbkdf2_hmac_sha512(const uint8_t * pw,size_t npw,const uint8_t * salt,size_t nsalt,uint32_t iterations,uint8_t * out,size_t nout)383 void cryptonite_fastpbkdf2_hmac_sha512( const uint8_t *pw, size_t npw
384 , const uint8_t *salt, size_t nsalt
385 , uint32_t iterations
386 , uint8_t *out, size_t nout
387 )
388 {
389 PBKDF2(sha512)(pw, npw, salt, nsalt, iterations, out, nout);
390 }
391