crypto/kdf/scrypt.c

   1 /*
   2  * Copyright 2017-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include <stdlib.h>
  11 #include <stdarg.h>
  12 #include <string.h>
  13 #include <openssl/evp.h>
  14 #include <openssl/kdf.h>
  15 #include <openssl/err.h>
  16 #include "internal/evp_int.h"
  17 #include "internal/numbers.h"
  18 #include "kdf_local.h"
  19
  20 #ifndef OPENSSL_NO_SCRYPT
  21
  22 static void kdf_scrypt_reset(EVP_KDF_IMPL *impl);
  23 static void kdf_scrypt_init(EVP_KDF_IMPL *impl);
  24 static int atou64(const char *nptr, uint64_t *result);
  25 static int scrypt_alg(const char *pass, size_t passlen,
  26                       const unsigned char *salt, size_t saltlen,
  27                       uint64_t N, uint64_t r, uint64_t p, uint64_t maxmem,
  28                       unsigned char *key, size_t keylen);
  29
  30 struct evp_kdf_impl_st {
  31     unsigned char *pass;
  32     size_t pass_len;
  33     unsigned char *salt;
  34     size_t salt_len;
  35     uint64_t N;
  36     uint32_t r, p;
  37     uint64_t maxmem_bytes;
  38 };
  39
  40 /* Custom uint64_t parser since we do not have strtoull */
  41 static int atou64(const char *nptr, uint64_t *result)
  42 {
  43     uint64_t value = 0;
  44
  45     while (*nptr) {
  46         unsigned int digit;
  47         uint64_t new_value;
  48
  49         if ((*nptr < '0') || (*nptr > '9')) {
  50             return 0;
  51         }
  52         digit = (unsigned int)(*nptr - '0');
  53         new_value = (value * 10) + digit;
  54         if ((new_value < digit) || ((new_value - digit) / 10 != value)) {
  55             /* Overflow */
  56             return 0;
  57         }
  58         value = new_value;
  59         nptr++;
  60     }
  61     *result = value;
  62     return 1;
  63 }
  64
  65 static EVP_KDF_IMPL *kdf_scrypt_new(void)
  66 {
  67     EVP_KDF_IMPL *impl;
  68
  69     impl = OPENSSL_zalloc(sizeof(*impl));
  70     if (impl == NULL) {
  71         KDFerr(KDF_F_KDF_SCRYPT_NEW, ERR_R_MALLOC_FAILURE);
  72         return NULL;
  73     }
  74     kdf_scrypt_init(impl);
  75     return impl;
  76 }
  77
  78 static void kdf_scrypt_free(EVP_KDF_IMPL *impl)
  79 {
  80     kdf_scrypt_reset(impl);
  81     OPENSSL_free(impl);
  82 }
  83
  84 static void kdf_scrypt_reset(EVP_KDF_IMPL *impl)
  85 {
  86     OPENSSL_free(impl->salt);
  87     OPENSSL_clear_free(impl->pass, impl->pass_len);
  88     memset(impl, 0, sizeof(*impl));
  89     kdf_scrypt_init(impl);
  90 }
  91
  92 static void kdf_scrypt_init(EVP_KDF_IMPL *impl)
  93 {
  94     /* Default values are the most conservative recommendation given in the
  95      * original paper of C. Percival. Derivation uses roughly 1 GiB of memory
  96      * for this parameter choice (approx. 128 * r * N * p bytes).
  97      */
  98     impl->N = 1 << 20;
  99     impl->r = 8;
 100     impl->p = 1;
 101     impl->maxmem_bytes = 1025 * 1024 * 1024;
 102 }
 103
 104 static int scrypt_set_membuf(unsigned char **buffer, size_t *buflen,
 105                              const unsigned char *new_buffer,
 106                              size_t new_buflen)
 107 {
 108     if (new_buffer == NULL)
 109         return 1;
 110
 111     OPENSSL_clear_free(*buffer, *buflen);
 112
 113     if (new_buflen > 0) {
 114         *buffer = OPENSSL_memdup(new_buffer, new_buflen);
 115     } else {
 116         *buffer = OPENSSL_malloc(1);
 117     }
 118     if (*buffer == NULL) {
 119         KDFerr(KDF_F_SCRYPT_SET_MEMBUF, ERR_R_MALLOC_FAILURE);
 120         return 0;
 121     }
 122
 123     *buflen = new_buflen;
 124     return 1;
 125 }
 126
 127 static int is_power_of_two(uint64_t value)
 128 {
 129     return (value != 0) && ((value & (value - 1)) == 0);
 130 }
 131
 132 static int kdf_scrypt_ctrl(EVP_KDF_IMPL *impl, int cmd, va_list args)
 133 {
 134     uint64_t u64_value;
 135     uint32_t value;
 136     const unsigned char *p;
 137     size_t len;
 138
 139     switch (cmd) {
 140     case EVP_KDF_CTRL_SET_PASS:
 141         p = va_arg(args, const unsigned char *);
 142         len = va_arg(args, size_t);
 143         return scrypt_set_membuf(&impl->pass, &impl->pass_len, p, len);
 144
 145     case EVP_KDF_CTRL_SET_SALT:
 146         p = va_arg(args, const unsigned char *);
 147         len = va_arg(args, size_t);
 148         return scrypt_set_membuf(&impl->salt, &impl->salt_len, p, len);
 149
 150     case EVP_KDF_CTRL_SET_SCRYPT_N:
 151         u64_value = va_arg(args, uint64_t);
 152         if ((u64_value <= 1) || !is_power_of_two(u64_value))
 153             return 0;
 154
 155         impl->N = u64_value;
 156         return 1;
 157
 158     case EVP_KDF_CTRL_SET_SCRYPT_R:
 159         value = va_arg(args, uint32_t);
 160         if (value < 1)
 161             return 0;
 162
 163         impl->r = value;
 164         return 1;
 165
 166     case EVP_KDF_CTRL_SET_SCRYPT_P:
 167         value = va_arg(args, uint32_t);
 168         if (value < 1)
 169             return 0;
 170
 171         impl->p = value;
 172         return 1;
 173
 174     case EVP_KDF_CTRL_SET_MAXMEM_BYTES:
 175         u64_value = va_arg(args, uint64_t);
 176         if (u64_value < 1)
 177             return 0;
 178
 179         impl->maxmem_bytes = u64_value;
 180         return 1;
 181
 182     default:
 183         return -2;
 184     }
 185 }
 186
 187 static int kdf_scrypt_ctrl_uint32(EVP_KDF_IMPL *impl, int cmd,
 188                                   const char *value)
 189 {
 190     int int_value = atoi(value);
 191
 192     if (int_value < 0 || (uint64_t)int_value > UINT32_MAX) {
 193         KDFerr(KDF_F_KDF_SCRYPT_CTRL_UINT32, KDF_R_VALUE_ERROR);
 194         return 0;
 195     }
 196     return call_ctrl(kdf_scrypt_ctrl, impl, cmd, (uint32_t)int_value);
 197 }
 198
 199 static int kdf_scrypt_ctrl_uint64(EVP_KDF_IMPL *impl, int cmd,
 200                                   const char *value)
 201 {
 202     uint64_t u64_value;
 203
 204     if (!atou64(value, &u64_value)) {
 205         KDFerr(KDF_F_KDF_SCRYPT_CTRL_UINT64, KDF_R_VALUE_ERROR);
 206         return 0;
 207     }
 208     return call_ctrl(kdf_scrypt_ctrl, impl, cmd, u64_value);
 209 }
 210
 211 static int kdf_scrypt_ctrl_str(EVP_KDF_IMPL *impl, const char *type,
 212                                const char *value)
 213 {
 214     if (value == NULL) {
 215         KDFerr(KDF_F_KDF_SCRYPT_CTRL_STR, KDF_R_VALUE_MISSING);
 216         return 0;
 217     }
 218
 219     if (strcmp(type, "pass") == 0)
 220         return kdf_str2ctrl(impl, kdf_scrypt_ctrl, EVP_KDF_CTRL_SET_PASS,
 221                             value);
 222
 223     if (strcmp(type, "hexpass") == 0)
 224         return kdf_hex2ctrl(impl, kdf_scrypt_ctrl, EVP_KDF_CTRL_SET_PASS,
 225                             value);
 226
 227     if (strcmp(type, "salt") == 0)
 228         return kdf_str2ctrl(impl, kdf_scrypt_ctrl, EVP_KDF_CTRL_SET_SALT,
 229                             value);
 230
 231     if (strcmp(type, "hexsalt") == 0)
 232         return kdf_hex2ctrl(impl, kdf_scrypt_ctrl, EVP_KDF_CTRL_SET_SALT,
 233                             value);
 234
 235     if (strcmp(type, "N") == 0)
 236         return kdf_scrypt_ctrl_uint64(impl, EVP_KDF_CTRL_SET_SCRYPT_N, value);
 237
 238     if (strcmp(type, "r") == 0)
 239         return kdf_scrypt_ctrl_uint32(impl, EVP_KDF_CTRL_SET_SCRYPT_R, value);
 240
 241     if (strcmp(type, "p") == 0)
 242         return kdf_scrypt_ctrl_uint32(impl, EVP_KDF_CTRL_SET_SCRYPT_P, value);
 243
 244     if (strcmp(type, "maxmem_bytes") == 0)
 245         return kdf_scrypt_ctrl_uint64(impl, EVP_KDF_CTRL_SET_MAXMEM_BYTES,
 246                                       value);
 247
 248     return -2;
 249 }
 250
 251 static int kdf_scrypt_derive(EVP_KDF_IMPL *impl, unsigned char *key,
 252                              size_t keylen)
 253 {
 254     if (impl->pass == NULL) {
 255         KDFerr(KDF_F_KDF_SCRYPT_DERIVE, KDF_R_MISSING_PASS);
 256         return 0;
 257     }
 258
 259     if (impl->salt == NULL) {
 260         KDFerr(KDF_F_KDF_SCRYPT_DERIVE, KDF_R_MISSING_SALT);
 261         return 0;
 262     }
 263
 264     return scrypt_alg((char *)impl->pass, impl->pass_len, impl->salt,
 265                       impl->salt_len, impl->N, impl->r, impl->p,
 266                       impl->maxmem_bytes, key, keylen);
 267 }
 268
 269 const EVP_KDF_METHOD scrypt_kdf_meth = {
 270     EVP_KDF_SCRYPT,
 271     kdf_scrypt_new,
 272     kdf_scrypt_free,
 273     kdf_scrypt_reset,
 274     kdf_scrypt_ctrl,
 275     kdf_scrypt_ctrl_str,
 276     NULL,
 277     kdf_scrypt_derive
 278 };
 279
 280 #define R(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
 281 static void salsa208_word_specification(uint32_t inout[16])
 282 {
 283     int i;
 284     uint32_t x[16];
 285
 286     memcpy(x, inout, sizeof(x));
 287     for (i = 8; i > 0; i -= 2) {
 288         x[4] ^= R(x[0] + x[12], 7);
 289         x[8] ^= R(x[4] + x[0], 9);
 290         x[12] ^= R(x[8] + x[4], 13);
 291         x[0] ^= R(x[12] + x[8], 18);
 292         x[9] ^= R(x[5] + x[1], 7);
 293         x[13] ^= R(x[9] + x[5], 9);
 294         x[1] ^= R(x[13] + x[9], 13);
 295         x[5] ^= R(x[1] + x[13], 18);
 296         x[14] ^= R(x[10] + x[6], 7);
 297         x[2] ^= R(x[14] + x[10], 9);
 298         x[6] ^= R(x[2] + x[14], 13);
 299         x[10] ^= R(x[6] + x[2], 18);
 300         x[3] ^= R(x[15] + x[11], 7);
 301         x[7] ^= R(x[3] + x[15], 9);
 302         x[11] ^= R(x[7] + x[3], 13);
 303         x[15] ^= R(x[11] + x[7], 18);
 304         x[1] ^= R(x[0] + x[3], 7);
 305         x[2] ^= R(x[1] + x[0], 9);
 306         x[3] ^= R(x[2] + x[1], 13);
 307         x[0] ^= R(x[3] + x[2], 18);
 308         x[6] ^= R(x[5] + x[4], 7);
 309         x[7] ^= R(x[6] + x[5], 9);
 310         x[4] ^= R(x[7] + x[6], 13);
 311         x[5] ^= R(x[4] + x[7], 18);
 312         x[11] ^= R(x[10] + x[9], 7);
 313         x[8] ^= R(x[11] + x[10], 9);
 314         x[9] ^= R(x[8] + x[11], 13);
 315         x[10] ^= R(x[9] + x[8], 18);
 316         x[12] ^= R(x[15] + x[14], 7);
 317         x[13] ^= R(x[12] + x[15], 9);
 318         x[14] ^= R(x[13] + x[12], 13);
 319         x[15] ^= R(x[14] + x[13], 18);
 320     }
 321     for (i = 0; i < 16; ++i)
 322         inout[i] += x[i];
 323     OPENSSL_cleanse(x, sizeof(x));
 324 }
 325
 326 static void scryptBlockMix(uint32_t *B_, uint32_t *B, uint64_t r)
 327 {
 328     uint64_t i, j;
 329     uint32_t X[16], *pB;
 330
 331     memcpy(X, B + (r * 2 - 1) * 16, sizeof(X));
 332     pB = B;
 333     for (i = 0; i < r * 2; i++) {
 334         for (j = 0; j < 16; j++)
 335             X[j] ^= *pB++;
 336         salsa208_word_specification(X);
 337         memcpy(B_ + (i / 2 + (i & 1) * r) * 16, X, sizeof(X));
 338     }
 339     OPENSSL_cleanse(X, sizeof(X));
 340 }
 341
 342 static void scryptROMix(unsigned char *B, uint64_t r, uint64_t N,
 343                         uint32_t *X, uint32_t *T, uint32_t *V)
 344 {
 345     unsigned char *pB;
 346     uint32_t *pV;
 347     uint64_t i, k;
 348
 349     /* Convert from little endian input */
 350     for (pV = V, i = 0, pB = B; i < 32 * r; i++, pV++) {
 351         *pV = *pB++;
 352         *pV |= *pB++ << 8;
 353         *pV |= *pB++ << 16;
 354         *pV |= (uint32_t)*pB++ << 24;
 355     }
 356
 357     for (i = 1; i < N; i++, pV += 32 * r)
 358         scryptBlockMix(pV, pV - 32 * r, r);
 359
 360     scryptBlockMix(X, V + (N - 1) * 32 * r, r);
 361
 362     for (i = 0; i < N; i++) {
 363         uint32_t j;
 364         j = X[16 * (2 * r - 1)] % N;
 365         pV = V + 32 * r * j;
 366         for (k = 0; k < 32 * r; k++)
 367             T[k] = X[k] ^ *pV++;
 368         scryptBlockMix(X, T, r);
 369     }
 370     /* Convert output to little endian */
 371     for (i = 0, pB = B; i < 32 * r; i++) {
 372         uint32_t xtmp = X[i];
 373         *pB++ = xtmp & 0xff;
 374         *pB++ = (xtmp >> 8) & 0xff;
 375         *pB++ = (xtmp >> 16) & 0xff;
 376         *pB++ = (xtmp >> 24) & 0xff;
 377     }
 378 }
 379
 380 #ifndef SIZE_MAX
 381 # define SIZE_MAX    ((size_t)-1)
 382 #endif
 383
 384 /*
 385  * Maximum power of two that will fit in uint64_t: this should work on
 386  * most (all?) platforms.
 387  */
 388
 389 #define LOG2_UINT64_MAX         (sizeof(uint64_t) * 8 - 1)
 390
 391 /*
 392  * Maximum value of p * r:
 393  * p <= ((2^32-1) * hLen) / MFLen =>
 394  * p <= ((2^32-1) * 32) / (128 * r) =>
 395  * p * r <= (2^30-1)
 396  */
 397
 398 #define SCRYPT_PR_MAX   ((1 << 30) - 1)
 399
 400 static int scrypt_alg(const char *pass, size_t passlen,
 401                       const unsigned char *salt, size_t saltlen,
 402                       uint64_t N, uint64_t r, uint64_t p, uint64_t maxmem,
 403                       unsigned char *key, size_t keylen)
 404 {
 405     int rv = 0;
 406     unsigned char *B;
 407     uint32_t *X, *V, *T;
 408     uint64_t i, Blen, Vlen;
 409
 410     /* Sanity check parameters */
 411     /* initial check, r,p must be non zero, N >= 2 and a power of 2 */
 412     if (r == 0 || p == 0 || N < 2 || (N & (N - 1)))
 413         return 0;
 414     /* Check p * r < SCRYPT_PR_MAX avoiding overflow */
 415     if (p > SCRYPT_PR_MAX / r) {
 416         EVPerr(EVP_F_SCRYPT_ALG, EVP_R_MEMORY_LIMIT_EXCEEDED);
 417         return 0;
 418     }
 419
 420     /*
 421      * Need to check N: if 2^(128 * r / 8) overflows limit this is
 422      * automatically satisfied since N <= UINT64_MAX.
 423      */
 424
 425     if (16 * r <= LOG2_UINT64_MAX) {
 426         if (N >= (((uint64_t)1) << (16 * r))) {
 427             EVPerr(EVP_F_SCRYPT_ALG, EVP_R_MEMORY_LIMIT_EXCEEDED);
 428             return 0;
 429         }
 430     }
 431
 432     /* Memory checks: check total allocated buffer size fits in uint64_t */
 433
 434     /*
 435      * B size in section 5 step 1.S
 436      * Note: we know p * 128 * r < UINT64_MAX because we already checked
 437      * p * r < SCRYPT_PR_MAX
 438      */
 439     Blen = p * 128 * r;
 440     /*
 441      * Yet we pass it as integer to PKCS5_PBKDF2_HMAC... [This would
 442      * have to be revised when/if PKCS5_PBKDF2_HMAC accepts size_t.]
 443      */
 444     if (Blen > INT_MAX) {
 445         EVPerr(EVP_F_SCRYPT_ALG, EVP_R_MEMORY_LIMIT_EXCEEDED);
 446         return 0;
 447     }
 448
 449     /*
 450      * Check 32 * r * (N + 2) * sizeof(uint32_t) fits in uint64_t
 451      * This is combined size V, X and T (section 4)
 452      */
 453     i = UINT64_MAX / (32 * sizeof(uint32_t));
 454     if (N + 2 > i / r) {
 455         EVPerr(EVP_F_SCRYPT_ALG, EVP_R_MEMORY_LIMIT_EXCEEDED);
 456         return 0;
 457     }
 458     Vlen = 32 * r * (N + 2) * sizeof(uint32_t);
 459
 460     /* check total allocated size fits in uint64_t */
 461     if (Blen > UINT64_MAX - Vlen) {
 462         EVPerr(EVP_F_SCRYPT_ALG, EVP_R_MEMORY_LIMIT_EXCEEDED);
 463         return 0;
 464     }
 465
 466     /* Check that the maximum memory doesn't exceed a size_t limits */
 467     if (maxmem > SIZE_MAX)
 468         maxmem = SIZE_MAX;
 469
 470     if (Blen + Vlen > maxmem) {
 471         EVPerr(EVP_F_SCRYPT_ALG, EVP_R_MEMORY_LIMIT_EXCEEDED);
 472         return 0;
 473     }
 474
 475     /* If no key return to indicate parameters are OK */
 476     if (key == NULL)
 477         return 1;
 478
 479     B = OPENSSL_malloc((size_t)(Blen + Vlen));
 480     if (B == NULL) {
 481         EVPerr(EVP_F_SCRYPT_ALG, ERR_R_MALLOC_FAILURE);
 482         return 0;
 483     }
 484     X = (uint32_t *)(B + Blen);
 485     T = X + 32 * r;
 486     V = T + 32 * r;
 487     if (PKCS5_PBKDF2_HMAC(pass, passlen, salt, saltlen, 1, EVP_sha256(),
 488                           (int)Blen, B) == 0)
 489         goto err;
 490
 491     for (i = 0; i < p; i++)
 492         scryptROMix(B + 128 * r * i, r, N, X, T, V);
 493
 494     if (PKCS5_PBKDF2_HMAC(pass, passlen, B, (int)Blen, 1, EVP_sha256(),
 495                           keylen, key) == 0)
 496         goto err;
 497     rv = 1;
 498  err:
 499     if (rv == 0)
 500         EVPerr(EVP_F_SCRYPT_ALG, EVP_R_PBKDF2_ERROR);
 501
 502     OPENSSL_clear_free(B, (size_t)(Blen + Vlen));
 503     return rv;
 504 }
 505
 506 #endif