usr/src/lib/crypt_modules/bsdbf/bcrypt.c

   1 /*      $OpenBSD: bcrypt.c,v 1.57 2016/08/26 08:25:02 guenther Exp $    */
   2
   3 /*
   4  * Copyright (c) 2014 Ted Unangst <tedu@openbsd.org>
   5  * Copyright (c) 1997 Niels Provos <provos@umich.edu>
   6  *
   7  * Permission to use, copy, modify, and distribute this software for any
   8  * purpose with or without fee is hereby granted, provided that the above
   9  * copyright notice and this permission notice appear in all copies.
  10  *
  11  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  12  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  13  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  14  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  15  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  16  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  17  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  18  */
  19 /* This password hashing algorithm was designed by David Mazieres
  20  * <dm@lcs.mit.edu> and works as follows:
  21  *
  22  * 1. state := InitState ()
  23  * 2. state := ExpandKey (state, salt, password)
  24  * 3. REPEAT rounds:
  25  *      state := ExpandKey (state, 0, password)
  26  *      state := ExpandKey (state, 0, salt)
  27  * 4. ctext := "OrpheanBeholderScryDoubt"
  28  * 5. REPEAT 64:
  29  *      ctext := Encrypt_ECB (state, ctext);
  30  * 6. RETURN Concatenate (salt, ctext);
  31  *
  32  */
  33
  34 #include <sys/types.h>
  35 #include <blf.h>
  36 #include <ctype.h>
  37 #include <errno.h>
  38 #include <pwd.h>
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <string.h>
  42 #include <time.h>
  43
  44 #define _PASSWORD_LEN   256
  45 extern int timingsafe_bcmp(const void *, const void *, size_t);
  46
  47 /* This implementation is adaptable to current computing power.
  48  * You can have up to 2^31 rounds which should be enough for some
  49  * time to come.
  50  */
  51
  52 #define BCRYPT_VERSION '2'
  53 #define BCRYPT_MAXSALT 16       /* Precomputation is just so nice */
  54 #define BCRYPT_WORDS 6          /* Ciphertext words */
  55 #define BCRYPT_MINLOGROUNDS 4   /* we have log2(rounds) in salt */
  56
  57 #define BCRYPT_SALTSPACE        (7 + (BCRYPT_MAXSALT * 4 + 2) / 3 + 1)
  58 #define BCRYPT_HASHSPACE        61
  59
  60 char   *bcrypt_gensalt(uint8_t);
  61
  62 static int encode_base64(char *, const uint8_t *, size_t);
  63 static int decode_base64(uint8_t *, size_t, const char *);
  64
  65 /*
  66  * Generates a salt for this version of crypt.
  67  */
  68 static int
  69 bcrypt_initsalt(int log_rounds, char *salt, size_t saltbuflen)
  70 {
  71         uint8_t csalt[BCRYPT_MAXSALT];
  72
  73         if (saltbuflen < BCRYPT_SALTSPACE) {
  74                 errno = EINVAL;
  75                 return -1;
  76         }
  77
  78         arc4random_buf(csalt, sizeof(csalt));
  79
  80         if (log_rounds < 4)
  81                 log_rounds = 4;
  82         else if (log_rounds > 31)
  83                 log_rounds = 31;
  84
  85         snprintf(salt, saltbuflen, "$2b$%2.2u$", log_rounds);
  86         encode_base64(salt + 7, csalt, sizeof(csalt));
  87
  88         return 0;
  89 }
  90
  91 /*
  92  * the core bcrypt function
  93  */
  94 static int
  95 bcrypt_hashpass(const char *key, const char *salt, char *encrypted,
  96     size_t encryptedlen)
  97 {
  98         blf_ctx state;
  99         uint32_t rounds, i, k;
 100         uint16_t j;
 101         size_t key_len;
 102         uint8_t salt_len, logr, minor;
 103         uint8_t ciphertext[4 * BCRYPT_WORDS] = "OrpheanBeholderScryDoubt";
 104         uint8_t csalt[BCRYPT_MAXSALT];
 105         uint32_t cdata[BCRYPT_WORDS];
 106
 107         if (encryptedlen < BCRYPT_HASHSPACE)
 108                 goto inval;
 109
 110         /* Check and discard "$" identifier */
 111         if (salt[0] != '$')
 112                 goto inval;
 113         salt += 1;
 114
 115         if (salt[0] != BCRYPT_VERSION)
 116                 goto inval;
 117
 118         /* Check for minor versions */
 119         switch ((minor = salt[1])) {
 120         case 'a':
 121                 key_len = (uint8_t)(strlen(key) + 1);
 122                 break;
 123         case 'b':
 124                 /* strlen() returns a size_t, but the function calls
 125                  * below result in implicit casts to a narrower integer
 126                  * type, so cap key_len at the actual maximum supported
 127                  * length here to avoid integer wraparound */
 128                 key_len = strlen(key);
 129                 if (key_len > 72)
 130                         key_len = 72;
 131                 key_len++; /* include the NUL */
 132                 break;
 133         default:
 134                  goto inval;
 135         }
 136         if (salt[2] != '$')
 137                 goto inval;
 138         /* Discard version + "$" identifier */
 139         salt += 3;
 140
 141         /* Check and parse num rounds */
 142         if (!isdigit((unsigned char)salt[0]) ||
 143             !isdigit((unsigned char)salt[1]) || salt[2] != '$')
 144                 goto inval;
 145         logr = (salt[1] - '0') + ((salt[0] - '0') * 10);
 146         if (logr < BCRYPT_MINLOGROUNDS || logr > 31)
 147                 goto inval;
 148         /* Computer power doesn't increase linearly, 2^x should be fine */
 149         rounds = 1U << logr;
 150
 151         /* Discard num rounds + "$" identifier */
 152         salt += 3;
 153
 154         if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT)
 155                 goto inval;
 156
 157         /* We dont want the base64 salt but the raw data */
 158         if (decode_base64(csalt, BCRYPT_MAXSALT, salt))
 159                 goto inval;
 160         salt_len = BCRYPT_MAXSALT;
 161
 162         /* Setting up S-Boxes and Subkeys */
 163         Blowfish_initstate(&state);
 164         Blowfish_expandstate(&state, csalt, salt_len,
 165             (uint8_t *) key, key_len);
 166         for (k = 0; k < rounds; k++) {
 167                 Blowfish_expand0state(&state, (uint8_t *) key, key_len);
 168                 Blowfish_expand0state(&state, csalt, salt_len);
 169         }
 170
 171         /* This can be precomputed later */
 172         j = 0;
 173         for (i = 0; i < BCRYPT_WORDS; i++)
 174                 cdata[i] = Blowfish_stream2word(ciphertext, 4 * BCRYPT_WORDS, &j);
 175
 176         /* Now do the encryption */
 177         for (k = 0; k < 64; k++)
 178                 blf_enc(&state, cdata, BCRYPT_WORDS / 2);
 179
 180         for (i = 0; i < BCRYPT_WORDS; i++) {
 181                 ciphertext[4 * i + 3] = cdata[i] & 0xff;
 182                 cdata[i] = cdata[i] >> 8;
 183                 ciphertext[4 * i + 2] = cdata[i] & 0xff;
 184                 cdata[i] = cdata[i] >> 8;
 185                 ciphertext[4 * i + 1] = cdata[i] & 0xff;
 186                 cdata[i] = cdata[i] >> 8;
 187                 ciphertext[4 * i + 0] = cdata[i] & 0xff;
 188         }
 189
 190
 191         snprintf(encrypted, 8, "$2%c$%2.2u$", minor, logr);
 192         encode_base64(encrypted + 7, csalt, BCRYPT_MAXSALT);
 193         encode_base64(encrypted + 7 + 22, ciphertext, 4 * BCRYPT_WORDS - 1);
 194         explicit_bzero(&state, sizeof(state));
 195         explicit_bzero(ciphertext, sizeof(ciphertext));
 196         explicit_bzero(csalt, sizeof(csalt));
 197         explicit_bzero(cdata, sizeof(cdata));
 198         return 0;
 199
 200 inval:
 201         errno = EINVAL;
 202         return -1;
 203 }
 204
 205 /*
 206  * user friendly functions
 207  */
 208 int
 209 bcrypt_newhash(const char *pass, int log_rounds, char *hash, size_t hashlen)
 210 {
 211         char salt[BCRYPT_SALTSPACE];
 212
 213         if (bcrypt_initsalt(log_rounds, salt, sizeof(salt)) != 0)
 214                 return -1;
 215
 216         if (bcrypt_hashpass(pass, salt, hash, hashlen) != 0)
 217                 return -1;
 218
 219         explicit_bzero(salt, sizeof(salt));
 220         return 0;
 221 }
 222
 223 int
 224 bcrypt_checkpass(const char *pass, const char *goodhash)
 225 {
 226         char hash[BCRYPT_HASHSPACE];
 227
 228         if (bcrypt_hashpass(pass, goodhash, hash, sizeof(hash)) != 0)
 229                 return -1;
 230         if (strlen(hash) != strlen(goodhash) ||
 231             timingsafe_bcmp(hash, goodhash, strlen(goodhash)) != 0) {
 232                 errno = EACCES;
 233                 return -1;
 234         }
 235
 236         explicit_bzero(hash, sizeof(hash));
 237         return 0;
 238 }
 239
 240 /*
 241  * Measure this system's performance by measuring the time for 8 rounds.
 242  * We are aiming for something that takes around 0.1s, but not too much over.
 243  */
 244 int
 245 _bcrypt_autorounds(void)
 246 {
 247         struct timespec before, after;
 248         int r = 8;
 249         char buf[_PASSWORD_LEN];
 250         int duration;
 251
 252         clock_gettime(CLOCK_THREAD_CPUTIME_ID, &before);
 253         bcrypt_newhash("testpassword", r, buf, sizeof(buf));
 254         clock_gettime(CLOCK_THREAD_CPUTIME_ID, &after);
 255
 256         duration = after.tv_sec - before.tv_sec;
 257         duration *= 1000000;
 258         duration += (after.tv_nsec - before.tv_nsec) / 1000;
 259
 260         /* too quick? slow it down. */
 261         while (r < 16 && duration <= 60000) {
 262                 r += 1;
 263                 duration *= 2;
 264         }
 265         /* too slow? speed it up. */
 266         while (r > 6 && duration > 120000) {
 267                 r -= 1;
 268                 duration /= 2;
 269         }
 270
 271         return r;
 272 }
 273
 274 /*
 275  * internal utilities
 276  */
 277 static const uint8_t Base64Code[] =
 278 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
 279
 280 static const uint8_t index_64[128] = {
 281         255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
 282         255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
 283         255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
 284         255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
 285         255, 255, 255, 255, 255, 255, 0, 1, 54, 55,
 286         56, 57, 58, 59, 60, 61, 62, 63, 255, 255,
 287         255, 255, 255, 255, 255, 2, 3, 4, 5, 6,
 288         7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
 289         17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
 290         255, 255, 255, 255, 255, 255, 28, 29, 30,
 291         31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
 292         41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
 293         51, 52, 53, 255, 255, 255, 255, 255
 294 };
 295 #define CHAR64(c)  ( (c) > 127 ? 255 : index_64[(c)])
 296
 297 /*
 298  * read buflen (after decoding) bytes of data from b64data
 299  */
 300 static int
 301 decode_base64(uint8_t *buffer, size_t len, const char *b64data)
 302 {
 303         uint8_t *bp = buffer;
 304         const uint8_t *p = (uint8_t *)b64data;
 305         uint8_t c1, c2, c3, c4;
 306
 307         while (bp < buffer + len) {
 308                 c1 = CHAR64(*p);
 309                 /* Invalid data */
 310                 if (c1 == 255)
 311                         return -1;
 312
 313                 c2 = CHAR64(*(p + 1));
 314                 if (c2 == 255)
 315                         return -1;
 316
 317                 *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4);
 318                 if (bp >= buffer + len)
 319                         break;
 320
 321                 c3 = CHAR64(*(p + 2));
 322                 if (c3 == 255)
 323                         return -1;
 324
 325                 *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2);
 326                 if (bp >= buffer + len)
 327                         break;
 328
 329                 c4 = CHAR64(*(p + 3));
 330                 if (c4 == 255)
 331                         return -1;
 332                 *bp++ = ((c3 & 0x03) << 6) | c4;
 333
 334                 p += 4;
 335         }
 336         return 0;
 337 }
 338
 339 /*
 340  * Turn len bytes of data into base64 encoded data.
 341  * This works without = padding.
 342  */
 343 static int
 344 encode_base64(char *b64buffer, const uint8_t *data, size_t len)
 345 {
 346         uint8_t *bp = (uint8_t *)b64buffer;
 347         const uint8_t *p = data;
 348         uint8_t c1, c2;
 349
 350         while (p < data + len) {
 351                 c1 = *p++;
 352                 *bp++ = Base64Code[(c1 >> 2)];
 353                 c1 = (c1 & 0x03) << 4;
 354                 if (p >= data + len) {
 355                         *bp++ = Base64Code[c1];
 356                         break;
 357                 }
 358                 c2 = *p++;
 359                 c1 |= (c2 >> 4) & 0x0f;
 360                 *bp++ = Base64Code[c1];
 361                 c1 = (c2 & 0x0f) << 2;
 362                 if (p >= data + len) {
 363                         *bp++ = Base64Code[c1];
 364                         break;
 365                 }
 366                 c2 = *p++;
 367                 c1 |= (c2 >> 6) & 0x03;
 368                 *bp++ = Base64Code[c1];
 369                 *bp++ = Base64Code[c2 & 0x3f];
 370         }
 371         *bp = '\0';
 372         return 0;
 373 }
 374
 375 /*
 376  * classic interface
 377  */
 378 char *
 379 bcrypt_gensalt(uint8_t log_rounds)
 380 {
 381         static char    gsalt[BCRYPT_SALTSPACE];
 382
 383         bcrypt_initsalt(log_rounds, gsalt, sizeof(gsalt));
 384
 385         return gsalt;
 386 }
 387
 388 char *
 389 bcrypt(const char *pass, const char *salt)
 390 {
 391         static char    gencrypted[BCRYPT_HASHSPACE];
 392
 393         if (bcrypt_hashpass(pass, salt, gencrypted, sizeof(gencrypted)) != 0)
 394                 return NULL;
 395
 396         return gencrypted;
 397 }