lib/scrypt.c

   1 /*
   2  * Copyright (C) 2013 Gregor Pintar <grpintar@gmail.com>
   3  *
   4  * Permission is granted to deal in this work without any restriction,
   5  * including unlimited rights to use, publicly perform, publish,
   6  * reproduce, relicence, modify, merge, and/or distribute in any form,
   7  * for any purpose, with or without fee, and by any means.
   8  *
   9  * This work is provided "AS IS" and WITHOUT WARRANTY of any kind,
  10  * to the utmost extent permitted by applicable law. In no event
  11  * shall a licensor, author or contributor be held liable for any
  12  * issues arising in any way out of dealing in the work.
  13  */
  14
  15 #include <stdint.h>
  16 #include <stdlib.h>
  17 #include <string.h>
  18 #include <assert.h>
  19
  20 #include <kripto/memwipe.h>
  21 #include <kripto/cast.h>
  22 #include <kripto/loadstore.h>
  23 #include <kripto/rotate.h>
  24 #include <kripto/mac.h>
  25 #include <kripto/pbkdf2.h>
  26
  27 #include <kripto/scrypt.h>
  28
  29 #define QR(A, B, C, D)          \
  30 {                                                       \
  31         B ^= ROL32(A + D,  7);  \
  32         C ^= ROL32(B + A,  9);  \
  33         D ^= ROL32(C + B, 13);  \
  34         A ^= ROL32(D + C, 18);  \
  35 }
  36
  37 static void salsa20_core(uint32_t *x)
  38 {
  39         uint32_t x0 = x[0];
  40         uint32_t x1 = x[1];
  41         uint32_t x2 = x[2];
  42         uint32_t x3 = x[3];
  43         uint32_t x4 = x[4];
  44         uint32_t x5 = x[5];
  45         uint32_t x6 = x[6];
  46         uint32_t x7 = x[7];
  47         uint32_t x8 = x[8];
  48         uint32_t x9 = x[9];
  49         uint32_t x10 = x[10];
  50         uint32_t x11 = x[11];
  51         uint32_t x12 = x[12];
  52         uint32_t x13 = x[13];
  53         uint32_t x14 = x[14];
  54         uint32_t x15 = x[15];
  55
  56         /* columnround 1 */
  57         QR(x0, x4, x8, x12);
  58         QR(x5, x9, x13, x1);
  59         QR(x10, x14, x2, x6);
  60         QR(x15, x3, x7, x11);
  61
  62         /* rowround 2 */
  63         QR(x0, x1, x2, x3);
  64         QR(x5, x6, x7, x4);
  65         QR(x10, x11, x8, x9);
  66         QR(x15, x12, x13, x14);
  67
  68         /* columnround 3 */
  69         QR(x0, x4, x8, x12);
  70         QR(x5, x9, x13, x1);
  71         QR(x10, x14, x2, x6);
  72         QR(x15, x3, x7, x11);
  73
  74         /* rowround 4 */
  75         QR(x0, x1, x2, x3);
  76         QR(x5, x6, x7, x4);
  77         QR(x10, x11, x8, x9);
  78         QR(x15, x12, x13, x14);
  79
  80         /* columnround 5 */
  81         QR(x0, x4, x8, x12);
  82         QR(x5, x9, x13, x1);
  83         QR(x10, x14, x2, x6);
  84         QR(x15, x3, x7, x11);
  85
  86         /* rowround 6 */
  87         QR(x0, x1, x2, x3);
  88         QR(x5, x6, x7, x4);
  89         QR(x10, x11, x8, x9);
  90         QR(x15, x12, x13, x14);
  91
  92         /* columnround 7 */
  93         QR(x0, x4, x8, x12);
  94         QR(x5, x9, x13, x1);
  95         QR(x10, x14, x2, x6);
  96         QR(x15, x3, x7, x11);
  97
  98         /* rowround 8 */
  99         QR(x0, x1, x2, x3);
 100         QR(x5, x6, x7, x4);
 101         QR(x10, x11, x8, x9);
 102         QR(x15, x12, x13, x14);
 103
 104         x[0] += x0;
 105         x[1] += x1;
 106         x[2] += x2;
 107         x[3] += x3;
 108         x[4] += x4;
 109         x[5] += x5;
 110         x[6] += x6;
 111         x[7] += x7;
 112         x[8] += x8;
 113         x[9] += x9;
 114         x[10] += x10;
 115         x[11] += x11;
 116         x[12] += x12;
 117         x[13] += x13;
 118         x[14] += x14;
 119         x[15] += x15;
 120 }
 121
 122 static void blockmix(uint32_t *b, uint32_t *t, const size_t r)
 123 {
 124         uint32_t x[16];
 125         size_t i;
 126
 127         memcpy(x, b + (r << 5) - 16, 64);
 128
 129         for(i = 0; i < (r << 5);)
 130         {
 131                 x[0] ^= b[i++];
 132                 x[1] ^= b[i++];
 133                 x[2] ^= b[i++];
 134                 x[3] ^= b[i++];
 135                 x[4] ^= b[i++];
 136                 x[5] ^= b[i++];
 137                 x[6] ^= b[i++];
 138                 x[7] ^= b[i++];
 139                 x[8] ^= b[i++];
 140                 x[9] ^= b[i++];
 141                 x[10] ^= b[i++];
 142                 x[11] ^= b[i++];
 143                 x[12] ^= b[i++];
 144                 x[13] ^= b[i++];
 145                 x[14] ^= b[i++];
 146                 x[15] ^= b[i++];
 147
 148                 salsa20_core(x);
 149                 memcpy(t + i - 16, x, 64);
 150         }
 151
 152         for(i = 0; i < r; i++)
 153         {
 154                 memcpy(b + (i << 4), t + (i << 5), 64);
 155                 memcpy(b + ((i + r) << 4), t + (i << 5) + 16, 64);
 156         }
 157 }
 158
 159 static void smix
 160 (
 161         uint8_t *b,
 162         const size_t r,
 163         uint64_t n,
 164         uint32_t *t0,
 165         uint32_t *t1,
 166         uint32_t *t2
 167 )
 168 {
 169         uint64_t i;
 170         uint64_t tn;
 171         uint64_t j;
 172
 173         for(i = 0; i < (r << 5); i++)
 174                 t1[i] = LOAD32L(b + (i << 2));
 175
 176         for(i = 0; i < n; i++)
 177         {
 178                 memcpy(t0 + (r << 5) * i, t1, r << 7);
 179                 blockmix(t1, t2, r);
 180         }
 181
 182         for(i = 0; i < n; i++)
 183         {
 184                 /* integrify */
 185                 tn = (((uint64_t)t1[(r << 5) - 15] << 32)
 186                         | t1[(r << 5) - 16])
 187                         & (n - 1);
 188
 189                 for(j = 0; j < (r << 5); j++)
 190                         t1[j] ^= t0[(r << 5) * tn + j];
 191
 192                 blockmix(t1, t2, r);
 193         }
 194
 195         for(i = 0; i < (r << 5); i++)
 196                 STORE32L(t1[i], b + (i << 2));
 197 }
 198
 199 int kripto_scrypt
 200 (
 201         const kripto_mac_desc *mac,
 202         unsigned int mac_rounds,
 203         uint64_t n,
 204         uint32_t r,
 205         uint32_t p,
 206         const void *pass,
 207         unsigned int pass_len,
 208         const void *salt,
 209         unsigned int salt_len,
 210         void *out,
 211         size_t out_len
 212 )
 213 {
 214         uint8_t *b;
 215         uint32_t *t0;
 216         uint32_t *t1;
 217         uint32_t *t2;
 218         uint32_t i;
 219
 220         b = malloc((r << 7) * p + (r << 7) * n + (r << 8));
 221         if(!b) return -1;
 222
 223         t0 = (uint32_t *)(b + (r << 7) * p);
 224         t1 = t0 + (r << 5);
 225         t2 = t1 + (r << 5);
 226
 227         if(kripto_pbkdf2
 228         (
 229                 mac,
 230                 mac_rounds,
 231                 1,
 232                 pass,
 233                 pass_len,
 234                 salt,
 235                 salt_len,
 236                 b,
 237                 p * (r << 7)
 238         )) goto err;
 239
 240         for(i = 0; i < p; i++)
 241                 smix(b + (r << 7) * i, r, n, t0, t1, t2);
 242
 243         if(kripto_pbkdf2
 244         (
 245                 mac,
 246                 mac_rounds,
 247                 1,
 248                 pass,
 249                 pass_len,
 250                 b,
 251                 p * (r << 7),
 252                 out,
 253                 out_len
 254         )) goto err;
 255
 256         kripto_memwipe(b, (r << 7) * p + (r << 7) * n + (r << 8));
 257         free(b);
 258
 259         return 0;
 260
 261 err:
 262         kripto_memwipe(b, (r << 7) * p + (r << 7) * n + (r << 8));
 263         free(b);
 264
 265         return -1;
 266 }