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

   1 /*
   2  * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
   3  * Use is subject to license terms.
   4  */
   5
   6 /*      $OpenBSD: bcrypt.c,v 1.16 2002/02/19 19:39:36 millert Exp $     */
   7
   8 /*
   9  * Copyright 1997 Niels Provos <provos@physnet.uni-hamburg.de>
  10  * All rights reserved.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  * 3. All advertising materials mentioning features or use of this software
  21  *    must display the following acknowledgement:
  22  *      This product includes software developed by Niels Provos.
  23  * 4. The name of the author may not be used to endorse or promote products
  24  *    derived from this software without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  27  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  28  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  29  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  30  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  31  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  35  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 /*
  39  * This password hashing algorithm was designed by David Mazieres
  40  * <dm@lcs.mit.edu> and works as follows:
  41  *
  42  * 1. state := InitState ()
  43  * 2. state := ExpandKey (state, salt, password) 3.
  44  * REPEAT rounds:
  45  *      state := ExpandKey (state, 0, salt)
  46  *      state := ExpandKey(state, 0, password)
  47  * 4. ctext := "OrpheanBeholderScryDoubt"
  48  * 5. REPEAT 64:
  49  *      ctext := Encrypt_ECB (state, ctext);
  50  * 6. RETURN Concatenate (salt, ctext);
  51  *
  52  */
  53
  54 #if 0
  55 #include <stdio.h>
  56 #endif
  57
  58 #include <stdio.h>
  59 #include <stdlib.h>
  60 #include <sys/types.h>
  61 #include <string.h>
  62 #include <pwd.h>
  63 #include <blf.h>
  64
  65 extern uint32_t arc4random();
  66
  67 /*
  68  * This implementation is adaptable to current computing power.
  69  * You can have up to 2^31 rounds which should be enough for some
  70  * time to come.
  71  */
  72
  73 #define BCRYPT_VERSION  '2'
  74 #define BCRYPT_MAXSALT  16              /* Precomputation is just so nice */
  75 #define BCRYPT_BLOCKS   6               /* Ciphertext blocks */
  76 #define BCRYPT_MINLOGROUNDS     4       /* we have log2(rounds) in salt */
  77 #define BCRYPT_MAXLOGROUNDS     31
  78
  79 char   *bcrypt_gensalt(uint8_t);
  80
  81 static void encode_salt(char *, uint8_t *, uint16_t, uint8_t);
  82 static void encode_base64(uint8_t *, uint8_t *, uint16_t);
  83 static void decode_base64(uint8_t *, uint16_t, uint8_t *);
  84
  85 static char    encrypted[128]; /* _PASSWORD_LEN in <pwd.h> on OpenBSD */
  86 static char    gsalt[BCRYPT_MAXSALT * 4 / 3 + 1];
  87 static char    error[] = ":";
  88
  89 static uint8_t Base64Code[] =
  90 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
  91
  92 static uint8_t index_64[128] =
  93 {
  94         255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  95         255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  96         255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  97         255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  98         255, 255, 255, 255, 255, 255, 0, 1, 54, 55,
  99         56, 57, 58, 59, 60, 61, 62, 63, 255, 255,
 100         255, 255, 255, 255, 255, 2, 3, 4, 5, 6,
 101         7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
 102         17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
 103         255, 255, 255, 255, 255, 255, 28, 29, 30,
 104         31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
 105         41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
 106         51, 52, 53, 255, 255, 255, 255, 255
 107 };
 108 #define CHAR64(c)       ((c) > 127 ? 255 : index_64[(c)])
 109
 110 static void
 111 decode_base64(uint8_t *buffer, uint16_t len, uint8_t *data)
 112 {
 113         uint8_t *bp = buffer;
 114         uint8_t *p = data;
 115         uint8_t c1, c2, c3, c4;
 116         while (bp < buffer + len) {
 117                 c1 = CHAR64(*p);
 118                 c2 = CHAR64(*(p + 1));
 119
 120                 /* Invalid data */
 121                 if (c1 == 255 || c2 == 255)
 122                         break;
 123
 124                 *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4);
 125                 if (bp >= buffer + len)
 126                         break;
 127
 128                 c3 = CHAR64(*(p + 2));
 129                 if (c3 == 255)
 130                         break;
 131
 132                 *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2);
 133                 if (bp >= buffer + len)
 134                         break;
 135
 136                 c4 = CHAR64(*(p + 3));
 137                 if (c4 == 255)
 138                         break;
 139                 *bp++ = ((c3 & 0x03) << 6) | c4;
 140
 141                 p += 4;
 142         }
 143 }
 144
 145 static void
 146 encode_salt(char *salt, uint8_t *csalt, uint16_t clen, uint8_t logr)
 147 {
 148         salt[0] = '$';
 149         salt[1] = BCRYPT_VERSION;
 150         salt[2] = 'a';
 151         salt[3] = '$';
 152
 153         (void) snprintf(salt + 4, 4, "%2.2u$", logr);
 154
 155         encode_base64((uint8_t *)salt + 7, csalt, clen);
 156 }
 157 /*
 158  * Generates a salt for this version of crypt.
 159  * Since versions may change. Keeping this here
 160  * seems sensible.
 161  */
 162
 163 char *
 164 bcrypt_gensalt(uint8_t log_rounds)
 165 {
 166         uint8_t csalt[BCRYPT_MAXSALT];
 167         uint16_t i;
 168         uint32_t seed = 0;
 169
 170         for (i = 0; i < BCRYPT_MAXSALT; i++) {
 171                 if (i % 4 == 0)
 172                         seed = arc4random();
 173                 csalt[i] = seed & 0xff;
 174                 seed = seed >> 8;
 175         }
 176
 177         if (log_rounds < BCRYPT_MINLOGROUNDS)
 178                 log_rounds = BCRYPT_MINLOGROUNDS;
 179         else if (log_rounds > BCRYPT_MAXLOGROUNDS)
 180                 log_rounds = BCRYPT_MAXLOGROUNDS;
 181
 182         encode_salt(gsalt, csalt, BCRYPT_MAXSALT, log_rounds);
 183         return (gsalt);
 184 }
 185 /*
 186  * We handle $Vers$log2(NumRounds)$salt+passwd$
 187  *  i.e. $2$04$iwouldntknowwhattosayetKdJ6iFtacBqJdKe6aW7ou
 188  */
 189
 190 char   *
 191 bcrypt(key, salt)
 192         const char   *key;
 193         const char   *salt;
 194 {
 195         blf_ctx state;
 196         uint32_t rounds, i, k;
 197         uint16_t j;
 198         size_t key_len;
 199         uint8_t salt_len, logr, minor;
 200         uint8_t ciphertext[4 * BCRYPT_BLOCKS] = "OrpheanBeholderScryDoubt";
 201         uint8_t csalt[BCRYPT_MAXSALT];
 202         uint32_t cdata[BCRYPT_BLOCKS];
 203         char arounds[3];
 204
 205         /* Discard "$" identifier */
 206         salt++;
 207
 208         if (*salt > BCRYPT_VERSION) {
 209                 /* How do I handle errors ? Return ':' */
 210                 return (error);
 211         }
 212
 213         /* Check for minor versions */
 214         if (salt[1] != '$') {
 215                 switch (salt[1]) {
 216                     case 'a': /* 'ab' should not yield the same as 'abab' */
 217                     case 'b': /* cap input length at 72 bytes */
 218                         minor = salt[1];
 219                         salt++;
 220                         break;
 221                     default:
 222                         return (error);
 223                 }
 224         } else
 225                 minor = 0;
 226
 227         /* Discard version + "$" identifier */
 228         salt += 2;
 229
 230         if (salt[2] != '$')
 231                 /* Out of sync with passwd entry */
 232                 return (error);
 233
 234         (void) memcpy(arounds, salt, sizeof (arounds));
 235         if (arounds[sizeof (arounds) - 1] != '$')
 236                 return (error);
 237         if ((logr = atoi(arounds)) < BCRYPT_MINLOGROUNDS ||
 238             logr > BCRYPT_MAXLOGROUNDS)
 239                 return (error);
 240         /* Computer power doesn't increase linear, 2^x should be fine */
 241         rounds = 1U << logr;
 242
 243         /* Discard num rounds + "$" identifier */
 244         salt += 3;
 245
 246         if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT)
 247                 return (error);
 248
 249         /* We dont want the base64 salt but the raw data */
 250         decode_base64(csalt, BCRYPT_MAXSALT, (uint8_t *)salt);
 251         salt_len = BCRYPT_MAXSALT;
 252         if (minor <= 'a')
 253                 key_len = (uint8_t)(strlen(key) + (minor >= 'a' ? 1 : 0));
 254         else {
 255                 /*
 256                  * strlen() returns a size_t, but the function calls
 257                  * below result in implicit casts to a narrower integer
 258                  * type, so cap key_len at the actual maximum supported
 259                  * length here to avoid integer wraparound
 260                  */
 261                 key_len = strlen(key);
 262                 if (key_len > 72)
 263                         key_len = 72;
 264                 key_len++; /* include the NUL */
 265         }
 266
 267         /* Setting up S-Boxes and Subkeys */
 268         Blowfish_initstate(&state);
 269         Blowfish_expandstate(&state, csalt, salt_len,
 270             (uint8_t *)key, key_len);
 271         for (k = 0; k < rounds; k++) {
 272                 Blowfish_expand0state(&state, (uint8_t *)key, key_len);
 273                 Blowfish_expand0state(&state, csalt, salt_len);
 274         }
 275
 276         /* This can be precomputed later */
 277         j = 0;
 278         for (i = 0; i < BCRYPT_BLOCKS; i++)
 279                 cdata[i] = Blowfish_stream2word(ciphertext,
 280                     4 * BCRYPT_BLOCKS, &j);
 281
 282         /* Now do the encryption */
 283         for (k = 0; k < 64; k++)
 284                 blf_enc(&state, cdata, BCRYPT_BLOCKS / 2);
 285
 286         for (i = 0; i < BCRYPT_BLOCKS; i++) {
 287                 ciphertext[4 * i + 3] = cdata[i] & 0xff;
 288                 cdata[i] = cdata[i] >> 8;
 289                 ciphertext[4 * i + 2] = cdata[i] & 0xff;
 290                 cdata[i] = cdata[i] >> 8;
 291                 ciphertext[4 * i + 1] = cdata[i] & 0xff;
 292                 cdata[i] = cdata[i] >> 8;
 293                 ciphertext[4 * i + 0] = cdata[i] & 0xff;
 294         }
 295
 296
 297         i = 0;
 298         encrypted[i++] = '$';
 299         encrypted[i++] = BCRYPT_VERSION;
 300         if (minor)
 301                 encrypted[i++] = minor;
 302         encrypted[i++] = '$';
 303
 304         (void) snprintf(encrypted + i, 4, "%2.2u$", logr);
 305
 306         encode_base64((uint8_t *)encrypted + i + 3, csalt, BCRYPT_MAXSALT);
 307         encode_base64((uint8_t *)encrypted + strlen(encrypted), ciphertext,
 308             4 * BCRYPT_BLOCKS - 1);
 309         return (encrypted);
 310 }
 311
 312 static void
 313 encode_base64(uint8_t *buffer, uint8_t *data, uint16_t len)
 314 {
 315         uint8_t *bp = buffer;
 316         uint8_t *p = data;
 317         uint8_t c1, c2;
 318         while (p < data + len) {
 319                 c1 = *p++;
 320                 *bp++ = Base64Code[(c1 >> 2)];
 321                 c1 = (c1 & 0x03) << 4;
 322                 if (p >= data + len) {
 323                         *bp++ = Base64Code[c1];
 324                         break;
 325                 }
 326                 c2 = *p++;
 327                 c1 |= (c2 >> 4) & 0x0f;
 328                 *bp++ = Base64Code[c1];
 329                 c1 = (c2 & 0x0f) << 2;
 330                 if (p >= data + len) {
 331                         *bp++ = Base64Code[c1];
 332                         break;
 333                 }
 334                 c2 = *p++;
 335                 c1 |= (c2 >> 6) & 0x03;
 336                 *bp++ = Base64Code[c1];
 337                 *bp++ = Base64Code[c2 & 0x3f];
 338         }
 339         *bp = '\0';
 340 }
 341 #if 0
 342 void
 343 main()
 344 {
 345         char    blubber[73];
 346         char    salt[100];
 347         char   *p;
 348         salt[0] = '$';
 349         salt[1] = BCRYPT_VERSION;
 350         salt[2] = '$';
 351
 352         snprintf(salt + 3, 4, "%2.2u$", 5);
 353
 354         printf("24 bytes of salt: ");
 355         fgets(salt + 6, 94, stdin);
 356         salt[99] = 0;
 357         printf("72 bytes of password: ");
 358         fpurge(stdin);
 359         fgets(blubber, 73, stdin);
 360         blubber[72] = 0;
 361
 362         p = crypt(blubber, salt);
 363         printf("Passwd entry: %s\n\n", p);
 364
 365         p = bcrypt_gensalt(5);
 366         printf("Generated salt: %s\n", p);
 367         p = crypt(blubber, p);
 368         printf("Passwd entry: %s\n", p);
 369 }
 370 #endif