1 /*- 2 * Copyright 2009 Colin Percival 3 * Copyright 2013 Alexander Peslyak 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 * This file was originally written by Colin Percival as part of the Tarsnap 28 * online backup system. 29 */ 30 31 #include <errno.h> 32 #include <limits.h> 33 #include <stdint.h> 34 #include <stdlib.h> 35 #include <string.h> 36 37 #include "../crypto_scrypt.h" 38 #include "../pbkdf2-sha256.h" 39 #include "private/common.h" 40 41 static inline void 42 blkcpy_64(escrypt_block_t *dest, const escrypt_block_t *src) 43 { 44 int i; 45 46 #if (ARCH_BITS == 32) 47 for (i = 0; i < 16; ++i) { 48 dest->w[i] = src->w[i]; 49 } 50 #else 51 for (i = 0; i < 8; ++i) { 52 dest->d[i] = src->d[i]; 53 } 54 #endif 55 } 56 57 static inline void 58 blkxor_64(escrypt_block_t *dest, const escrypt_block_t *src) 59 { 60 int i; 61 62 #if (ARCH_BITS == 32) 63 for (i = 0; i < 16; ++i) { 64 dest->w[i] ^= src->w[i]; 65 } 66 #else 67 for (i = 0; i < 8; ++i) { 68 dest->d[i] ^= src->d[i]; 69 } 70 #endif 71 } 72 73 static inline void 74 blkcpy(escrypt_block_t *dest, const escrypt_block_t *src, size_t len) 75 { 76 size_t i, L; 77 78 #if (ARCH_BITS == 32) 79 L = (len >> 2); 80 for (i = 0; i < L; ++i) { 81 dest->w[i] = src->w[i]; 82 } 83 #else 84 L = (len >> 3); 85 for (i = 0; i < L; ++i) { 86 dest->d[i] = src->d[i]; 87 } 88 #endif 89 } 90 91 static inline void 92 blkxor(escrypt_block_t *dest, const escrypt_block_t *src, size_t len) 93 { 94 size_t i, L; 95 96 #if (ARCH_BITS == 32) 97 L = (len >> 2); 98 for (i = 0; i < L; ++i) { 99 dest->w[i] ^= src->w[i]; 100 } 101 #else 102 L = (len >> 3); 103 for (i = 0; i < L; ++i) { 104 dest->d[i] ^= src->d[i]; 105 } 106 #endif 107 } 108 109 /** 110 * salsa20_8(B): 111 * Apply the salsa20/8 core to the provided block. 112 */ 113 static void 114 salsa20_8(uint32_t B[16]) 115 { 116 escrypt_block_t X; 117 uint32_t *x = X.w; 118 size_t i; 119 120 blkcpy_64(&X, (escrypt_block_t *) B); 121 for (i = 0; i < 8; i += 2) { 122 #define R(a, b) (((a) << (b)) | ((a) >> (32 - (b)))) 123 /* Operate on columns. */ 124 x[4] ^= R(x[0] + x[12], 7); 125 x[8] ^= R(x[4] + x[0], 9); 126 x[12] ^= R(x[8] + x[4], 13); 127 x[0] ^= R(x[12] + x[8], 18); 128 129 x[9] ^= R(x[5] + x[1], 7); 130 x[13] ^= R(x[9] + x[5], 9); 131 x[1] ^= R(x[13] + x[9], 13); 132 x[5] ^= R(x[1] + x[13], 18); 133 134 x[14] ^= R(x[10] + x[6], 7); 135 x[2] ^= R(x[14] + x[10], 9); 136 x[6] ^= R(x[2] + x[14], 13); 137 x[10] ^= R(x[6] + x[2], 18); 138 139 x[3] ^= R(x[15] + x[11], 7); 140 x[7] ^= R(x[3] + x[15], 9); 141 x[11] ^= R(x[7] + x[3], 13); 142 x[15] ^= R(x[11] + x[7], 18); 143 144 /* Operate on rows. */ 145 x[1] ^= R(x[0] + x[3], 7); 146 x[2] ^= R(x[1] + x[0], 9); 147 x[3] ^= R(x[2] + x[1], 13); 148 x[0] ^= R(x[3] + x[2], 18); 149 150 x[6] ^= R(x[5] + x[4], 7); 151 x[7] ^= R(x[6] + x[5], 9); 152 x[4] ^= R(x[7] + x[6], 13); 153 x[5] ^= R(x[4] + x[7], 18); 154 155 x[11] ^= R(x[10] + x[9], 7); 156 x[8] ^= R(x[11] + x[10], 9); 157 x[9] ^= R(x[8] + x[11], 13); 158 x[10] ^= R(x[9] + x[8], 18); 159 160 x[12] ^= R(x[15] + x[14], 7); 161 x[13] ^= R(x[12] + x[15], 9); 162 x[14] ^= R(x[13] + x[12], 13); 163 x[15] ^= R(x[14] + x[13], 18); 164 #undef R 165 } 166 for (i = 0; i < 16; i++) { 167 B[i] += x[i]; 168 } 169 } 170 171 /** 172 * blockmix_salsa8(Bin, Bout, X, r): 173 * Compute Bout = BlockMix_{salsa20/8, r}(Bin). The input Bin must be 128r 174 * bytes in length; the output Bout must also be the same size. The 175 * temporary space X must be 64 bytes. 176 */ 177 static void 178 blockmix_salsa8(const uint32_t *Bin, uint32_t *Bout, uint32_t *X, size_t r) 179 { 180 size_t i; 181 182 /* 1: X <-- B_{2r - 1} */ 183 blkcpy_64((escrypt_block_t *) X, 184 (escrypt_block_t *) &Bin[(2 * r - 1) * 16]); 185 186 /* 2: for i = 0 to 2r - 1 do */ 187 for (i = 0; i < 2 * r; i += 2) { 188 /* 3: X <-- H(X \xor B_i) */ 189 blkxor_64((escrypt_block_t *) X, (escrypt_block_t *) &Bin[i * 16]); 190 salsa20_8(X); 191 192 /* 4: Y_i <-- X */ 193 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */ 194 blkcpy_64((escrypt_block_t *) &Bout[i * 8], (escrypt_block_t *) X); 195 196 /* 3: X <-- H(X \xor B_i) */ 197 blkxor_64((escrypt_block_t *) X, (escrypt_block_t *) &Bin[i * 16 + 16]); 198 salsa20_8(X); 199 200 /* 4: Y_i <-- X */ 201 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */ 202 blkcpy_64((escrypt_block_t *) &Bout[i * 8 + r * 16], 203 (escrypt_block_t *) X); 204 } 205 } 206 207 /** 208 * integerify(B, r): 209 * Return the result of parsing B_{2r-1} as a little-endian integer. 210 */ 211 static inline uint64_t 212 integerify(const void *B, size_t r) 213 { 214 const uint32_t *X = (const uint32_t *) ((uintptr_t)(B) + (2 * r - 1) * 64); 215 216 return (((uint64_t)(X[1]) << 32) + X[0]); 217 } 218 219 /** 220 * smix(B, r, N, V, XY): 221 * Compute B = SMix_r(B, N). The input B must be 128r bytes in length; 222 * the temporary storage V must be 128rN bytes in length; the temporary 223 * storage XY must be 256r + 64 bytes in length. The value N must be a 224 * power of 2 greater than 1. The arrays B, V, and XY must be aligned to a 225 * multiple of 64 bytes. 226 */ 227 static void 228 smix(uint8_t *B, size_t r, uint64_t N, uint32_t *V, uint32_t *XY) 229 { 230 uint32_t *X = XY; 231 uint32_t *Y = &XY[32 * r]; 232 uint32_t *Z = &XY[64 * r]; 233 uint64_t i; 234 uint64_t j; 235 size_t k; 236 237 /* 1: X <-- B */ 238 for (k = 0; k < 32 * r; k++) { 239 X[k] = LOAD32_LE(&B[4 * k]); 240 } 241 /* 2: for i = 0 to N - 1 do */ 242 for (i = 0; i < N; i += 2) { 243 /* 3: V_i <-- X */ 244 blkcpy((escrypt_block_t *) &V[i * (32 * r)], (escrypt_block_t *) X, 245 128 * r); 246 247 /* 4: X <-- H(X) */ 248 blockmix_salsa8(X, Y, Z, r); 249 250 /* 3: V_i <-- X */ 251 blkcpy((escrypt_block_t *) &V[(i + 1) * (32 * r)], 252 (escrypt_block_t *) Y, 128 * r); 253 254 /* 4: X <-- H(X) */ 255 blockmix_salsa8(Y, X, Z, r); 256 } 257 258 /* 6: for i = 0 to N - 1 do */ 259 for (i = 0; i < N; i += 2) { 260 /* 7: j <-- Integerify(X) mod N */ 261 j = integerify(X, r) & (N - 1); 262 263 /* 8: X <-- H(X \xor V_j) */ 264 blkxor((escrypt_block_t *) X, (escrypt_block_t *) &V[j * (32 * r)], 265 128 * r); 266 blockmix_salsa8(X, Y, Z, r); 267 268 /* 7: j <-- Integerify(X) mod N */ 269 j = integerify(Y, r) & (N - 1); 270 271 /* 8: X <-- H(X \xor V_j) */ 272 blkxor((escrypt_block_t *) Y, (escrypt_block_t *) &V[j * (32 * r)], 273 128 * r); 274 blockmix_salsa8(Y, X, Z, r); 275 } 276 /* 10: B' <-- X */ 277 for (k = 0; k < 32 * r; k++) { 278 STORE32_LE(&B[4 * k], X[k]); 279 } 280 } 281 282 /** 283 * escrypt_kdf(local, passwd, passwdlen, salt, saltlen, 284 * N, r, p, buf, buflen): 285 * Compute scrypt(passwd[0 .. passwdlen - 1], salt[0 .. saltlen - 1], N, r, 286 * p, buflen) and write the result into buf. The parameters r, p, and buflen 287 * must satisfy r * p < 2^30 and buflen <= (2^32 - 1) * 32. The parameter N 288 * must be a power of 2 greater than 1. 289 * 290 * Return 0 on success; or -1 on error. 291 */ 292 int 293 escrypt_kdf_nosse(escrypt_local_t *local, const uint8_t *passwd, 294 size_t passwdlen, const uint8_t *salt, size_t saltlen, 295 uint64_t N, uint32_t _r, uint32_t _p, uint8_t *buf, 296 size_t buflen) 297 { 298 size_t B_size, V_size, XY_size, need; 299 uint8_t * B; 300 uint32_t *V, *XY; 301 size_t r = _r, p = _p; 302 uint32_t i; 303 304 /* Sanity-check parameters. */ 305 #if SIZE_MAX > UINT32_MAX 306 if (buflen > (((uint64_t)(1) << 32) - 1) * 32) { 307 errno = EFBIG; 308 return -1; 309 } 310 #endif 311 if ((uint64_t)(r) * (uint64_t)(p) >= ((uint64_t) 1 << 30)) { 312 errno = EFBIG; 313 return -1; 314 } 315 if (N > UINT32_MAX) { 316 errno = EFBIG; 317 return -1; 318 } 319 if (((N & (N - 1)) != 0) || (N < 2)) { 320 errno = EINVAL; 321 return -1; 322 } 323 if (r == 0 || p == 0) { 324 errno = EINVAL; 325 return -1; 326 } 327 if ((r > SIZE_MAX / 128 / p) || 328 #if SIZE_MAX / 256 <= UINT32_MAX 329 (r > SIZE_MAX / 256) || 330 #endif 331 (N > SIZE_MAX / 128 / r)) { 332 errno = ENOMEM; 333 return -1; 334 } 335 336 /* Allocate memory. */ 337 B_size = (size_t) 128 * r * p; 338 V_size = (size_t) 128 * r * (size_t) N; 339 need = B_size + V_size; 340 if (need < V_size) { 341 errno = ENOMEM; 342 return -1; 343 } 344 XY_size = (size_t) 256 * r + 64; 345 need += XY_size; 346 if (need < XY_size) { 347 errno = ENOMEM; 348 return -1; 349 } 350 if (local->size < need) { 351 if (free_region(local)) { 352 return -1; 353 } 354 if (!alloc_region(local, need)) { 355 return -1; 356 } 357 } 358 B = (uint8_t *) local->aligned; 359 V = (uint32_t *) ((uint8_t *) B + B_size); 360 XY = (uint32_t *) ((uint8_t *) V + V_size); 361 362 /* 1: (B_0 ... B_{p-1}) <-- PBKDF2(P, S, 1, p * MFLen) */ 363 PBKDF2_SHA256(passwd, passwdlen, salt, saltlen, 1, B, B_size); 364 365 /* 2: for i = 0 to p - 1 do */ 366 for (i = 0; i < p; i++) { 367 /* 3: B_i <-- MF(B_i, N) */ 368 smix(&B[(size_t) 128 * i * r], r, N, V, XY); 369 } 370 371 /* 5: DK <-- PBKDF2(P, B, 1, dkLen) */ 372 PBKDF2_SHA256(passwd, passwdlen, B, B_size, 1, buf, buflen); 373 374 /* Success! */ 375 return 0; 376 } 377