1/*
2 * Copyright (c) 2000-2002 by Solar Designer. See LICENSE.
3 */
4
5#include <stdlib.h>
6#include <string.h>
7#include <ctype.h>
8#include <pwd.h>
9
10#include "passwdqc.h"
11
12#define REASON_ERROR \
13	"check failed"
14
15#define REASON_SAME \
16	"is the same as the old one"
17#define REASON_SIMILAR \
18	"is based on the old one"
19
20#define REASON_SHORT \
21	"too short"
22#define REASON_LONG \
23	"too long"
24
25#define REASON_SIMPLESHORT \
26	"not enough different characters or classes for this length"
27#define REASON_SIMPLE \
28	"not enough different characters or classes"
29
30#define REASON_PERSONAL \
31	"based on personal login information"
32
33#define REASON_WORD \
34	"based on a dictionary word and not a passphrase"
35
36#define FIXED_BITS			15
37
38typedef unsigned long fixed;
39
40/*
41 * Calculates the expected number of different characters for a random
42 * password of a given length. The result is rounded down. We use this
43 * with the _requested_ minimum length (so longer passwords don't have
44 * to meet this strict requirement for their length).
45 */
46static int expected_different(int charset, int length)
47{
48	fixed x, y, z;
49
50	x = ((fixed)(charset - 1) << FIXED_BITS) / charset;
51	y = x;
52	while (--length > 0) y = (y * x) >> FIXED_BITS;
53	z = (fixed)charset * (((fixed)1 << FIXED_BITS) - y);
54
55	return (int)(z >> FIXED_BITS);
56}
57
58/*
59 * A password is too simple if it is too short for its class, or doesn't
60 * contain enough different characters for its class, or doesn't contain
61 * enough words for a passphrase.
62 */
63static int is_simple(passwdqc_params_t *params, const char *newpass)
64{
65	int length, classes, words, chars;
66	int digits, lowers, uppers, others, unknowns;
67	int c, p;
68
69	length = classes = words = chars = 0;
70	digits = lowers = uppers = others = unknowns = 0;
71	p = ' ';
72	while ((c = (unsigned char)newpass[length])) {
73		length++;
74
75		if (!isascii(c)) unknowns++; else
76		if (isdigit(c)) digits++; else
77		if (islower(c)) lowers++; else
78		if (isupper(c)) uppers++; else
79			others++;
80
81		if (isascii(c) && isalpha(c) && isascii(p) && !isalpha(p))
82			words++;
83		p = c;
84
85		if (!strchr(&newpass[length], c))
86			chars++;
87	}
88
89	if (!length) return 1;
90
91/* Upper case characters and digits used in common ways don't increase the
92 * strength of a password */
93	c = (unsigned char)newpass[0];
94	if (uppers && isascii(c) && isupper(c)) uppers--;
95	c = (unsigned char)newpass[length - 1];
96	if (digits && isascii(c) && isdigit(c)) digits--;
97
98/* Count the number of different character classes we've seen. We assume
99 * that there're no non-ASCII characters for digits. */
100	classes = 0;
101	if (digits) classes++;
102	if (lowers) classes++;
103	if (uppers) classes++;
104	if (others) classes++;
105	if (unknowns && (!classes || (digits && classes == 1))) classes++;
106
107	for (; classes > 0; classes--)
108	switch (classes) {
109	case 1:
110		if (length >= params->min[0] &&
111		    chars >= expected_different(10, params->min[0]) - 1)
112			return 0;
113		return 1;
114
115	case 2:
116		if (length >= params->min[1] &&
117		    chars >= expected_different(36, params->min[1]) - 1)
118			return 0;
119		if (!params->passphrase_words ||
120		    words < params->passphrase_words)
121			continue;
122		if (length >= params->min[2] &&
123		    chars >= expected_different(27, params->min[2]) - 1)
124			return 0;
125		continue;
126
127	case 3:
128		if (length >= params->min[3] &&
129		    chars >= expected_different(62, params->min[3]) - 1)
130			return 0;
131		continue;
132
133	case 4:
134		if (length >= params->min[4] &&
135		    chars >= expected_different(95, params->min[4]) - 1)
136			return 0;
137		continue;
138	}
139
140	return 1;
141}
142
143static char *unify(const char *src)
144{
145	const char *sptr;
146	char *dst, *dptr;
147	int c;
148
149	if (!(dst = malloc(strlen(src) + 1)))
150		return NULL;
151
152	sptr = src;
153	dptr = dst;
154	do {
155		c = (unsigned char)*sptr;
156		if (isascii(c) && isupper(c))
157			*dptr++ = tolower(c);
158		else
159			*dptr++ = *sptr;
160	} while (*sptr++);
161
162	return dst;
163}
164
165static char *reverse(const char *src)
166{
167	const char *sptr;
168	char *dst, *dptr;
169
170	if (!(dst = malloc(strlen(src) + 1)))
171		return NULL;
172
173	sptr = &src[strlen(src)];
174	dptr = dst;
175	while (sptr > src)
176		*dptr++ = *--sptr;
177	*dptr = '\0';
178
179	return dst;
180}
181
182static void clean(char *dst)
183{
184	if (dst) {
185		memset(dst, 0, strlen(dst));
186		free(dst);
187	}
188}
189
190/*
191 * Needle is based on haystack if both contain a long enough common
192 * substring and needle would be too simple for a password with the
193 * substring removed.
194 */
195static int is_based(passwdqc_params_t *params,
196    const char *haystack, const char *needle, const char *original)
197{
198	char *scratch;
199	int length;
200	int i, j;
201	const char *p;
202	int match;
203
204	if (!params->match_length)	/* disabled */
205		return 0;
206
207	if (params->match_length < 0)	/* misconfigured */
208		return 1;
209
210	if (strstr(haystack, needle))	/* based on haystack entirely */
211		return 1;
212
213	scratch = NULL;
214
215	length = strlen(needle);
216	for (i = 0; i <= length - params->match_length; i++)
217	for (j = params->match_length; i + j <= length; j++) {
218		match = 0;
219		for (p = haystack; *p; p++)
220		if (*p == needle[i] && !strncmp(p, &needle[i], j)) {
221			match = 1;
222			if (!scratch) {
223				if (!(scratch = malloc(length + 1)))
224					return 1;
225			}
226			memcpy(scratch, original, i);
227			memcpy(&scratch[i], &original[i + j],
228			    length + 1 - (i + j));
229			if (is_simple(params, scratch)) {
230				clean(scratch);
231				return 1;
232			}
233		}
234		if (!match) break;
235	}
236
237	clean(scratch);
238
239	return 0;
240}
241
242/*
243 * This wordlist check is now the least important given the checks above
244 * and the support for passphrases (which are based on dictionary words,
245 * and checked by other means). It is still useful to trap simple short
246 * passwords (if short passwords are allowed) that are word-based, but
247 * passed the other checks due to uncommon capitalization, digits, and
248 * special characters. We (mis)use the same set of words that are used
249 * to generate random passwords. This list is much smaller than those
250 * used for password crackers, and it doesn't contain common passwords
251 * that aren't short English words. Perhaps support for large wordlists
252 * should still be added, even though this is now of little importance.
253 */
254static int is_word_based(passwdqc_params_t *params,
255    const char *needle, const char *original)
256{
257	char word[7];
258	char *unified;
259	int i;
260
261	word[6] = '\0';
262	for (i = 0; i < 0x1000; i++) {
263		memcpy(word, _passwdqc_wordset_4k[i], 6);
264		if ((int)strlen(word) < params->match_length) continue;
265		unified = unify(word);
266		if (is_based(params, unified, needle, original)) {
267			clean(unified);
268			return 1;
269		}
270		clean(unified);
271	}
272
273	return 0;
274}
275
276const char *_passwdqc_check(passwdqc_params_t *params,
277    const char *newpass, const char *oldpass, struct passwd *pw)
278{
279	char truncated[9], *reversed;
280	char *u_newpass, *u_reversed;
281	char *u_oldpass;
282	char *u_name, *u_gecos;
283	const char *reason;
284	int length;
285
286	reversed = NULL;
287	u_newpass = u_reversed = NULL;
288	u_oldpass = NULL;
289	u_name = u_gecos = NULL;
290
291	reason = NULL;
292
293	if (oldpass && !strcmp(oldpass, newpass))
294		reason = REASON_SAME;
295
296	length = strlen(newpass);
297
298	if (!reason && length < params->min[4])
299		reason = REASON_SHORT;
300
301	if (!reason && length > params->max) {
302		if (params->max == 8) {
303			truncated[0] = '\0';
304			strncat(truncated, newpass, 8);
305			newpass = truncated;
306			if (oldpass && !strncmp(oldpass, newpass, 8))
307				reason = REASON_SAME;
308		} else
309			reason = REASON_LONG;
310	}
311
312	if (!reason && is_simple(params, newpass)) {
313		if (length < params->min[1] && params->min[1] <= params->max)
314			reason = REASON_SIMPLESHORT;
315		else
316			reason = REASON_SIMPLE;
317	}
318
319	if (!reason) {
320		if ((reversed = reverse(newpass))) {
321			u_newpass = unify(newpass);
322			u_reversed = unify(reversed);
323			if (oldpass)
324				u_oldpass = unify(oldpass);
325			if (pw) {
326				u_name = unify(pw->pw_name);
327				u_gecos = unify(pw->pw_gecos);
328			}
329		}
330		if (!reversed ||
331		    !u_newpass || !u_reversed ||
332		    (oldpass && !u_oldpass) ||
333		    (pw && (!u_name || !u_gecos)))
334			reason = REASON_ERROR;
335	}
336
337	if (!reason && oldpass && params->similar_deny &&
338	    (is_based(params, u_oldpass, u_newpass, newpass) ||
339	    is_based(params, u_oldpass, u_reversed, reversed)))
340		reason = REASON_SIMILAR;
341
342	if (!reason && pw &&
343	    (is_based(params, u_name, u_newpass, newpass) ||
344	    is_based(params, u_name, u_reversed, reversed) ||
345	    is_based(params, u_gecos, u_newpass, newpass) ||
346	    is_based(params, u_gecos, u_reversed, reversed)))
347		reason = REASON_PERSONAL;
348
349	if (!reason && (int)strlen(newpass) < params->min[2] &&
350	    (is_word_based(params, u_newpass, newpass) ||
351	    is_word_based(params, u_reversed, reversed)))
352		reason = REASON_WORD;
353
354	memset(truncated, 0, sizeof(truncated));
355	clean(reversed);
356	clean(u_newpass); clean(u_reversed);
357	clean(u_oldpass);
358	clean(u_name); clean(u_gecos);
359
360	return reason;
361}
362