1 /*- 2 * Copyright 2009 Colin Percival 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 * 26 * This file was originally written by Colin Percival as part of the Tarsnap 27 * online backup system. 28 */ 29 #include "scrypt_platform.h" 30 31 #include <errno.h> 32 #include <stdint.h> 33 #include <stdlib.h> 34 #include <string.h> 35 36 #ifdef USE_OPENSSL_PBKDF2 37 #include <openssl/evp.h> 38 #else 39 #include "sha256.h" 40 #endif 41 #include "sysendian.h" 42 43 #include "crypto_scrypt.h" 44 45 static void blkcpy(uint8_t *, uint8_t *, size_t); 46 static void blkxor(uint8_t *, uint8_t *, size_t); 47 static void salsa20_8(uint8_t[64]); 48 static void blockmix_salsa8(uint8_t *, uint8_t *, size_t); 49 static uint64_t integerify(uint8_t *, size_t); 50 static void smix(uint8_t *, size_t, uint64_t, uint8_t *, uint8_t *); 51 52 static void 53 blkcpy(uint8_t * dest, uint8_t * src, size_t len) 54 { 55 size_t i; 56 57 for (i = 0; i < len; i++) 58 dest[i] = src[i]; 59 } 60 61 static void 62 blkxor(uint8_t * dest, uint8_t * src, size_t len) 63 { 64 size_t i; 65 66 for (i = 0; i < len; i++) 67 dest[i] ^= src[i]; 68 } 69 70 /** 71 * salsa20_8(B): 72 * Apply the salsa20/8 core to the provided block. 73 */ 74 static void 75 salsa20_8(uint8_t B[64]) 76 { 77 uint32_t B32[16]; 78 uint32_t x[16]; 79 size_t i; 80 81 /* Convert little-endian values in. */ 82 for (i = 0; i < 16; i++) 83 B32[i] = le32dec(&B[i * 4]); 84 85 /* Compute x = doubleround^4(B32). */ 86 for (i = 0; i < 16; i++) 87 x[i] = B32[i]; 88 for (i = 0; i < 8; i += 2) { 89 #define R(a,b) (((a) << (b)) | ((a) >> (32 - (b)))) 90 /* Operate on columns. */ 91 x[ 4] ^= R(x[ 0]+x[12], 7); x[ 8] ^= R(x[ 4]+x[ 0], 9); 92 x[12] ^= R(x[ 8]+x[ 4],13); x[ 0] ^= R(x[12]+x[ 8],18); 93 94 x[ 9] ^= R(x[ 5]+x[ 1], 7); x[13] ^= R(x[ 9]+x[ 5], 9); 95 x[ 1] ^= R(x[13]+x[ 9],13); x[ 5] ^= R(x[ 1]+x[13],18); 96 97 x[14] ^= R(x[10]+x[ 6], 7); x[ 2] ^= R(x[14]+x[10], 9); 98 x[ 6] ^= R(x[ 2]+x[14],13); x[10] ^= R(x[ 6]+x[ 2],18); 99 100 x[ 3] ^= R(x[15]+x[11], 7); x[ 7] ^= R(x[ 3]+x[15], 9); 101 x[11] ^= R(x[ 7]+x[ 3],13); x[15] ^= R(x[11]+x[ 7],18); 102 103 /* Operate on rows. */ 104 x[ 1] ^= R(x[ 0]+x[ 3], 7); x[ 2] ^= R(x[ 1]+x[ 0], 9); 105 x[ 3] ^= R(x[ 2]+x[ 1],13); x[ 0] ^= R(x[ 3]+x[ 2],18); 106 107 x[ 6] ^= R(x[ 5]+x[ 4], 7); x[ 7] ^= R(x[ 6]+x[ 5], 9); 108 x[ 4] ^= R(x[ 7]+x[ 6],13); x[ 5] ^= R(x[ 4]+x[ 7],18); 109 110 x[11] ^= R(x[10]+x[ 9], 7); x[ 8] ^= R(x[11]+x[10], 9); 111 x[ 9] ^= R(x[ 8]+x[11],13); x[10] ^= R(x[ 9]+x[ 8],18); 112 113 x[12] ^= R(x[15]+x[14], 7); x[13] ^= R(x[12]+x[15], 9); 114 x[14] ^= R(x[13]+x[12],13); x[15] ^= R(x[14]+x[13],18); 115 #undef R 116 } 117 118 /* Compute B32 = B32 + x. */ 119 for (i = 0; i < 16; i++) 120 B32[i] += x[i]; 121 122 /* Convert little-endian values out. */ 123 for (i = 0; i < 16; i++) 124 le32enc(&B[4 * i], B32[i]); 125 } 126 127 /** 128 * blockmix_salsa8(B, Y, r): 129 * Compute B = BlockMix_{salsa20/8, r}(B). The input B must be 128r bytes in 130 * length; the temporary space Y must also be the same size. 131 */ 132 static void 133 blockmix_salsa8(uint8_t * B, uint8_t * Y, size_t r) 134 { 135 uint8_t X[64]; 136 size_t i; 137 138 /* 1: X <-- B_{2r - 1} */ 139 blkcpy(X, &B[(2 * r - 1) * 64], 64); 140 141 /* 2: for i = 0 to 2r - 1 do */ 142 for (i = 0; i < 2 * r; i++) { 143 /* 3: X <-- H(X \xor B_i) */ 144 blkxor(X, &B[i * 64], 64); 145 salsa20_8(X); 146 147 /* 4: Y_i <-- X */ 148 blkcpy(&Y[i * 64], X, 64); 149 } 150 151 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */ 152 for (i = 0; i < r; i++) 153 blkcpy(&B[i * 64], &Y[(i * 2) * 64], 64); 154 for (i = 0; i < r; i++) 155 blkcpy(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64); 156 } 157 158 /** 159 * integerify(B, r): 160 * Return the result of parsing B_{2r-1} as a little-endian integer. 161 */ 162 static uint64_t 163 integerify(uint8_t * B, size_t r) 164 { 165 uint8_t * X = &B[(2 * r - 1) * 64]; 166 167 return (le64dec(X)); 168 } 169 170 /** 171 * smix(B, r, N, V, XY): 172 * Compute B = SMix_r(B, N). The input B must be 128r bytes in length; the 173 * temporary storage V must be 128rN bytes in length; the temporary storage 174 * XY must be 256r bytes in length. The value N must be a power of 2. 175 */ 176 static void 177 smix(uint8_t * B, size_t r, uint64_t N, uint8_t * V, uint8_t * XY) 178 { 179 uint8_t * X = XY; 180 uint8_t * Y = &XY[128 * r]; 181 uint64_t i; 182 uint64_t j; 183 184 /* 1: X <-- B */ 185 blkcpy(X, B, 128 * r); 186 187 /* 2: for i = 0 to N - 1 do */ 188 for (i = 0; i < N; i++) { 189 /* 3: V_i <-- X */ 190 blkcpy(&V[i * (128 * r)], X, 128 * r); 191 192 /* 4: X <-- H(X) */ 193 blockmix_salsa8(X, Y, r); 194 } 195 196 /* 6: for i = 0 to N - 1 do */ 197 for (i = 0; i < N; i++) { 198 /* 7: j <-- Integerify(X) mod N */ 199 j = integerify(X, r) & (N - 1); 200 201 /* 8: X <-- H(X \xor V_j) */ 202 blkxor(X, &V[j * (128 * r)], 128 * r); 203 blockmix_salsa8(X, Y, r); 204 } 205 206 /* 10: B' <-- X */ 207 blkcpy(B, X, 128 * r); 208 } 209 210 /** 211 * crypto_scrypt(passwd, passwdlen, salt, saltlen, N, r, p, buf, buflen): 212 * Compute scrypt(passwd[0 .. passwdlen - 1], salt[0 .. saltlen - 1], N, r, 213 * p, buflen) and write the result into buf. The parameters r, p, and buflen 214 * must satisfy r * p < 2^30 and buflen <= (2^32 - 1) * 32. The parameter N 215 * must be a power of 2. 216 * 217 * Return 0 on success; or -1 on error. 218 */ 219 int 220 crypto_scrypt(const uint8_t * passwd, size_t passwdlen, 221 const uint8_t * salt, size_t saltlen, uint64_t N, uint32_t r, uint32_t p, 222 uint8_t * buf, size_t buflen) 223 { 224 uint8_t * B; 225 uint8_t * V; 226 uint8_t * XY; 227 uint32_t i; 228 229 /* Sanity-check parameters. */ 230 #if SIZE_MAX > UINT32_MAX 231 if (buflen > (((uint64_t)(1) << 32) - 1) * 32) { 232 errno = EFBIG; 233 goto err0; 234 } 235 #endif 236 if ((uint64_t)(r) * (uint64_t)(p) >= (1 << 30)) { 237 errno = EFBIG; 238 goto err0; 239 } 240 if (((N & (N - 1)) != 0) || (N == 0)) { 241 errno = EINVAL; 242 goto err0; 243 } 244 if ((r > SIZE_MAX / 128 / p) || 245 #if SIZE_MAX / 256 <= UINT32_MAX 246 (r > SIZE_MAX / 256) || 247 #endif 248 (N > SIZE_MAX / 128 / r)) { 249 errno = ENOMEM; 250 goto err0; 251 } 252 253 /* Allocate memory. */ 254 if ((B = malloc(128 * r * p)) == NULL) 255 goto err0; 256 if ((XY = malloc(256 * r)) == NULL) 257 goto err1; 258 if ((V = malloc(128 * r * N)) == NULL) 259 goto err2; 260 261 /* 1: (B_0 ... B_{p-1}) <-- PBKDF2(P, S, 1, p * MFLen) */ 262 #ifdef USE_OPENSSL_PBKDF2 263 PKCS5_PBKDF2_HMAC((const char *)passwd, passwdlen, salt, saltlen, 1, EVP_sha256(), p * 128 * r, B); 264 #else 265 PBKDF2_SHA256(passwd, passwdlen, salt, saltlen, 1, B, p * 128 * r); 266 #endif 267 268 /* 2: for i = 0 to p - 1 do */ 269 for (i = 0; i < p; i++) { 270 /* 3: B_i <-- MF(B_i, N) */ 271 smix(&B[i * 128 * r], r, N, V, XY); 272 } 273 274 /* 5: DK <-- PBKDF2(P, B, 1, dkLen) */ 275 #ifdef USE_OPENSSL_PBKDF2 276 PKCS5_PBKDF2_HMAC((const char *)passwd, passwdlen, B, p * 128 * r, 1, EVP_sha256(), buflen, buf); 277 #else 278 PBKDF2_SHA256(passwd, passwdlen, B, p * 128 * r, 1, buf, buflen); 279 #endif 280 281 /* Free memory. */ 282 free(V); 283 free(XY); 284 free(B); 285 286 /* Success! */ 287 return (0); 288 289 err2: 290 free(XY); 291 err1: 292 free(B); 293 err0: 294 /* Failure! */ 295 return (-1); 296 } 297
