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