xref: /illumos-gate/usr/src/lib/crypt_modules/sunmd5/sunmd5.c (revision 1dbc1fed8be6e82e676ff3f124628dc470058bfb)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 #include <sys/types.h>
27 #include <sys/stat.h>
28 #include <fcntl.h>
29 #include <unistd.h>
30 #include <strings.h>
31 #include <pwd.h>
32 #include <errno.h>
33 #include <stdlib.h>
34 #include <syslog.h>
35 
36 #include <crypt.h>
37 #include <md5.h>
38 
39 #define	CRYPT_ALGNAME	"md5"
40 
41 
42 /* minimum number of rounds we do, not including the per-user ones */
43 
44 #define	BASIC_ROUND_COUNT 4096 /* enough to make things interesting */
45 #define	DIGEST_LEN	16
46 #define	ROUND_BUFFER_LEN	64
47 
48 /*
49  * Public domain quotation courtesy of Project Gutenberg.
50  * ftp://metalab.unc.edu/pub/docs/books/gutenberg/etext98/2ws2610.txt
51  * Hamlet III.ii - 1517 bytes, including trailing NUL
52  * ANSI-C string constant concatenation is a requirement here.
53  */
54 
55 static const char constant_phrase[] =
56 	"To be, or not to be,--that is the question:--\n"
57 	"Whether 'tis nobler in the mind to suffer\n"
58 	"The slings and arrows of outrageous fortune\n"
59 	"Or to take arms against a sea of troubles,\n"
60 	"And by opposing end them?--To die,--to sleep,--\n"
61 	"No more; and by a sleep to say we end\n"
62 	"The heartache, and the thousand natural shocks\n"
63 	"That flesh is heir to,--'tis a consummation\n"
64 	"Devoutly to be wish'd. To die,--to sleep;--\n"
65 	"To sleep! perchance to dream:--ay, there's the rub;\n"
66 	"For in that sleep of death what dreams may come,\n"
67 	"When we have shuffled off this mortal coil,\n"
68 	"Must give us pause: there's the respect\n"
69 	"That makes calamity of so long life;\n"
70 	"For who would bear the whips and scorns of time,\n"
71 	"The oppressor's wrong, the proud man's contumely,\n"
72 	"The pangs of despis'd love, the law's delay,\n"
73 	"The insolence of office, and the spurns\n"
74 	"That patient merit of the unworthy takes,\n"
75 	"When he himself might his quietus make\n"
76 	"With a bare bodkin? who would these fardels bear,\n"
77 	"To grunt and sweat under a weary life,\n"
78 	"But that the dread of something after death,--\n"
79 	"The undiscover'd country, from whose bourn\n"
80 	"No traveller returns,--puzzles the will,\n"
81 	"And makes us rather bear those ills we have\n"
82 	"Than fly to others that we know not of?\n"
83 	"Thus conscience does make cowards of us all;\n"
84 	"And thus the native hue of resolution\n"
85 	"Is sicklied o'er with the pale cast of thought;\n"
86 	"And enterprises of great pith and moment,\n"
87 	"With this regard, their currents turn awry,\n"
88 	"And lose the name of action.--Soft you now!\n"
89 	"The fair Ophelia!--Nymph, in thy orisons\n"
90 	"Be all my sins remember'd.\n";
91 
92 /* ------------------------------------------------------------------ */
93 
94 static int
md5bit(uint8_t * digest,int bit_num)95 md5bit(uint8_t *digest, int bit_num)
96 {
97 	int byte_off;
98 	int bit_off;
99 
100 	bit_num %= 128; /* keep this bounded for convenience */
101 	byte_off = bit_num / 8;
102 	bit_off = bit_num % 8;
103 
104 	/* return the value of bit N from the digest */
105 	return ((digest[byte_off] & (0x01 << bit_off)) ? 1 : 0);
106 }
107 
108 static uchar_t itoa64[] =		/* 0 ... 63 => ascii - 64 */
109 	"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
110 
111 static void
to64(char * s,uint64_t v,int n)112 to64(char *s, uint64_t v, int n)
113 {
114 	while (--n >= 0) {
115 		*s++ = itoa64[v & 0x3f];
116 		v >>= 6;
117 	}
118 }
119 
120 #define	ROUNDS		"rounds="
121 #define	ROUNDSLEN	(sizeof (ROUNDS) - 1)
122 
123 /*
124  * get the integer value after rounds= where ever it occurs in the string.
125  * if the last char after the int is a , or $ that is fine anything else is an
126  * error.
127  */
128 static uint32_t
getrounds(const char * s)129 getrounds(const char *s)
130 {
131 	char *r, *p, *e;
132 	long val;
133 
134 	if (s == NULL)
135 		return (0);
136 
137 	if ((r = strstr(s, ROUNDS)) == NULL) {
138 		return (0);
139 	}
140 
141 	if (strncmp(r, ROUNDS, ROUNDSLEN) != 0) {
142 		return (0);
143 	}
144 
145 	p = r + ROUNDSLEN;
146 	errno = 0;
147 	val = strtol(p, &e, 10);
148 	/*
149 	 * An error occurred or there is non-numeric stuff at the end
150 	 * which isn't one of the crypt(3c) special chars ',' or '$'
151 	 */
152 	if (errno != 0 || val < 0 ||
153 	    !(*e == '\0' || *e == ',' || *e == '$')) {
154 		syslog(LOG_WARNING,
155 		    "crypt_sunmd5: invalid rounds specification \"%s\"", s);
156 		return (0);
157 	}
158 
159 	return ((uint32_t)val);
160 }
161 
162 /* ARGSUSED3 */
163 char *
crypt_gensalt_impl(char * gsbuffer,size_t gsbufflen,const char * oldsalt,const struct passwd * userinfo,const char ** params)164 crypt_gensalt_impl(char *gsbuffer,
165 	    size_t gsbufflen,
166 	    const char *oldsalt,
167 	    const struct passwd *userinfo,
168 	    const char **params)
169 {
170 	uint32_t confrounds = 0;
171 	uint32_t saltrounds;
172 	int i;
173 	int fd;
174 	ssize_t got;
175 	uint64_t rndval;
176 	char rndstr[sizeof (rndval) + 1];	/* rndval as a base64 string */
177 
178 	for (i = 0; params != NULL && params[i] != NULL; i++) {
179 		if (strncmp(params[i], ROUNDS, ROUNDSLEN) == 0) {
180 			confrounds = getrounds(params[i]);
181 		} else {
182 			syslog(LOG_WARNING,
183 			    "crypt_sunmd5: invalid parameter %s", params[i]);
184 			errno = EINVAL;
185 			return (NULL);
186 		}
187 	}
188 
189 	/*
190 	 * If the config file has a higher value for rounds= than what
191 	 * was in the old salt use that, otherwise keep what was in the
192 	 * old salt.
193 	 */
194 	saltrounds = getrounds(oldsalt);
195 	if (confrounds > saltrounds) {
196 		saltrounds = confrounds;
197 	}
198 
199 	if ((fd = open("/dev/random", O_RDONLY)) == -1) {
200 		goto fail;
201 	}
202 
203 	got = read(fd, &rndval, sizeof (rndval));
204 	if (got < sizeof (rndval)) {
205 		int err = errno;
206 
207 		(void) close(fd);
208 		errno = err;
209 		goto fail;
210 	}
211 	(void) close(fd);
212 
213 	to64((char *)&rndstr, rndval, sizeof (rndval));
214 	rndstr[sizeof (rndstr) - 1] = '\0';
215 
216 	if (saltrounds > 0) {
217 		if (snprintf(gsbuffer, gsbufflen,
218 		    "$" CRYPT_ALGNAME "," ROUNDS "%d$",
219 		    saltrounds) >= gsbufflen)
220 			goto fail;
221 	} else {
222 		if (snprintf(gsbuffer, gsbufflen,
223 		    "$" CRYPT_ALGNAME "$") >= gsbufflen)
224 			goto fail;
225 	}
226 
227 	if (strlcat(gsbuffer, rndstr, gsbufflen) >= gsbufflen)
228 		goto fail;
229 	if (strlcat(gsbuffer, "$", gsbufflen) >= gsbufflen)
230 		goto fail;
231 
232 	return (gsbuffer);
233 
234 fail:
235 	bzero(gsbuffer, gsbufflen);
236 	return (NULL);
237 }
238 
239 
240 /*ARGSUSED4*/
241 char *
crypt_genhash_impl(char * ctbuffer,size_t ctbufflen,const char * plaintext,const char * salt,const char ** params)242 crypt_genhash_impl(char *ctbuffer,
243 	    size_t ctbufflen,
244 	    const char *plaintext,
245 	    const char *salt,
246 	    const char **params)
247 {
248 	int i;
249 	int round;
250 	int maxrounds = BASIC_ROUND_COUNT;
251 	uint32_t l;
252 	char *puresalt;
253 	char *saltend;
254 	char *p;
255 
256 	/* put all the sensitive data in a struct */
257 	struct {
258 		MD5_CTX context;	/* working buffer for MD5 algorithm */
259 		uint8_t digest[DIGEST_LEN]; /* where the MD5 digest is stored */
260 
261 		int indirect_4[16]; /* extracted array of 4bit values */
262 		int shift_4[16];	/* shift schedule, vals 0..4 */
263 
264 		int s7shift;	/* shift for shift_7 creation, vals  0..7 */
265 		int indirect_7[16]; /* extracted array of 7bit values */
266 		int shift_7[16];	/* shift schedule, vals 0..1 */
267 
268 		int indirect_a;	 /* 7bit index into digest */
269 		int shift_a;		/* shift schedule, vals 0..1 */
270 
271 		int indirect_b;	 /* 7bit index into digest */
272 		int shift_b;		/* shift schedule, vals 0..1 */
273 
274 		int bit_a;		  /* single bit for cointoss */
275 		int bit_b;		  /* single bit for cointoss */
276 
277 		char roundascii[ROUND_BUFFER_LEN]; /* ascii rep of roundcount */
278 	} data;
279 
280 
281 	/*
282 	 * Extract the puresalt (if it exists) from the existing salt string
283 	 * $md5[,rounds=%d]$<puresalt>$<optional existing encoding>
284 	 */
285 	saltend = strrchr(salt, '$');
286 	if (saltend == NULL || saltend == salt) {
287 		return (NULL);
288 	}
289 	if (saltend[1] != '\0') {
290 		size_t len = saltend - salt + 1;
291 		if ((puresalt = malloc(len)) == NULL) {
292 			return (NULL);
293 		}
294 		(void) strlcpy(puresalt, salt, len);
295 	} else {
296 		puresalt = strdup(salt);
297 		if (puresalt == NULL) {
298 			return (NULL);
299 		}
300 	}
301 
302 	maxrounds += getrounds(salt);
303 
304 	/* initialise the context */
305 
306 	MD5Init(&data.context);
307 
308 	/* update with the (hopefully entropic) plaintext */
309 
310 	MD5Update(&data.context, (uchar_t *)plaintext, strlen(plaintext));
311 
312 	/* update with the (publically known) salt */
313 
314 	MD5Update(&data.context, (uchar_t *)puresalt, strlen(puresalt));
315 
316 
317 	/* compute the digest */
318 
319 	MD5Final(data.digest, &data.context);
320 
321 	/*
322 	 * now to delay high-speed md5 implementations that have stuff
323 	 * like code inlining, loops unrolled and table lookup
324 	 */
325 
326 	for (round = 0; round < maxrounds; round++) {
327 		/* re-initialise the context */
328 
329 		MD5Init(&data.context);
330 
331 		/* update with the previous digest */
332 
333 		MD5Update(&data.context, data.digest, sizeof (data.digest));
334 
335 		/* populate the shift schedules for use later */
336 
337 		for (i = 0; i < 16; i++) {
338 			int j;
339 
340 		/* offset 3 -> occasionally span more than 1 int32 fetch */
341 			j = (i + 3) % 16;
342 			data.s7shift = data.digest[i] % 8;
343 			data.shift_4[i] = data.digest[j] % 5;
344 			data.shift_7[i] = (data.digest[j] >> data.s7shift)
345 			    & 0x01;
346 		}
347 
348 		data.shift_a = md5bit(data.digest, round);
349 		data.shift_b = md5bit(data.digest, round + 64);
350 
351 		/* populate indirect_4 with 4bit values extracted from digest */
352 
353 		for (i = 0; i < 16; i++) {
354 			/* shift the digest byte and extract four bits */
355 			data.indirect_4[i] =
356 			    (data.digest[i] >> data.shift_4[i]) & 0x0f;
357 		}
358 
359 		/*
360 		 * populate indirect_7 with 7bit values from digest
361 		 * indexed via indirect_4
362 		 */
363 
364 		for (i = 0; i < 16; i++) {
365 			/* shift the digest byte and extract seven bits */
366 			data.indirect_7[i] = (data.digest[data.indirect_4[i]]
367 			    >> data.shift_7[i]) & 0x7f;
368 		}
369 
370 		/*
371 		 * use the 7bit values to indirect into digest,
372 		 * and create two 8bit values from the results.
373 		 */
374 
375 		data.indirect_a = data.indirect_b = 0;
376 
377 		for (i = 0; i < 8; i++) {
378 			data.indirect_a |= (md5bit(data.digest,
379 			    data.indirect_7[i]) << i);
380 
381 			data.indirect_b |= (md5bit(data.digest,
382 			    data.indirect_7[i + 8]) << i);
383 		}
384 
385 
386 		/* shall we utilise the top or bottom 7 bits? */
387 
388 		data.indirect_a = (data.indirect_a >> data.shift_a) & 0x7f;
389 		data.indirect_b = (data.indirect_b >> data.shift_b) & 0x7f;
390 
391 
392 		/* extract two data.digest bits */
393 
394 		data.bit_a = md5bit(data.digest, data.indirect_a);
395 		data.bit_b = md5bit(data.digest, data.indirect_b);
396 
397 
398 #if ALGDEBUG
399 		for (i = 0; i < 15; i++) {
400 			(void) printf("%1x-", data.indirect_4[i]);
401 		}
402 		(void) printf("%1x ", data.indirect_4[15]);
403 		for (i = 0; i < 15; i++) {
404 			(void) printf("%02x-", data.indirect_7[i]);
405 		}
406 		(void) printf("%02x ", data.indirect_7[15]);
407 		(void) printf("%02x/%02x ", data.indirect_a, data.indirect_b);
408 		(void) printf("%d^%d\n", data.bit_a, data.bit_b);
409 #endif
410 
411 
412 		/* xor a coin-toss; if true, mix-in the constant phrase */
413 
414 		if (data.bit_a ^ data.bit_b) {
415 			MD5Update(&data.context,
416 			    (unsigned char *) constant_phrase,
417 			    sizeof (constant_phrase));
418 #if ALGDEBUG
419 			(void) printf("mixing constant_phrase\n");
420 #endif
421 		}
422 
423 
424 		/* digest a decimal sprintf of the current roundcount */
425 
426 		(void) snprintf(data.roundascii, ROUND_BUFFER_LEN, "%d", round);
427 		MD5Update(&data.context,
428 		    (unsigned char *) data.roundascii, strlen(data.roundascii));
429 
430 		/* compute/flush the digest, and loop */
431 
432 		MD5Final(data.digest, &data.context);
433 	}
434 
435 
436 #if ALGDEBUG
437 	/* print the digest */
438 	for (i = 0; i < 16; i++) {
439 		(void) printf("%02x", data.digest[i]);
440 	}
441 	(void) printf("\n");
442 #endif
443 
444 	(void) snprintf(ctbuffer, ctbufflen, "%s$", puresalt);
445 	p = ctbuffer + strlen(ctbuffer);
446 
447 	l = (data.digest[ 0]<<16) | (data.digest[ 6]<<8) | data.digest[12];
448 	to64(p, l, 4); p += 4;
449 	l = (data.digest[ 1]<<16) | (data.digest[ 7]<<8) | data.digest[13];
450 	to64(p, l, 4); p += 4;
451 	l = (data.digest[ 2]<<16) | (data.digest[ 8]<<8) | data.digest[14];
452 	to64(p, l, 4); p += 4;
453 	l = (data.digest[ 3]<<16) | (data.digest[ 9]<<8) | data.digest[15];
454 	to64(p, l, 4); p += 4;
455 	l = (data.digest[ 4]<<16) | (data.digest[10]<<8) | data.digest[ 5];
456 	to64(p, l, 4); p += 4;
457 	l = data.digest[11]; to64(p, l, 2); p += 2;
458 	*p = '\0';
459 
460 	/* tidy up after ourselves */
461 	bzero(&data, sizeof (data));
462 
463 	return (ctbuffer);
464 }
465