2 * Copyright (c) 2000-2002,2010,2013,2016,2020 by Solar Designer. See LICENSE.
6 #define _CRT_SECURE_NO_WARNINGS /* we use fopen(), sprintf(), strncat() */
14 #include "passwdqc.h" /* also provides <pwd.h> or equivalent "struct passwd" */
15 #include "passwdqc_filter.h"
16 #include "wordset_4k.h"
18 #include "passwdqc_i18n.h"
20 #define REASON_ERROR \
24 _("is the same as the old one")
25 #define REASON_SIMILAR \
26 _("is based on the old one")
28 #define REASON_SHORT \
33 #define REASON_SIMPLESHORT \
34 _("not enough different characters or classes for this length")
35 #define REASON_SIMPLE \
36 _("not enough different characters or classes")
38 #define REASON_PERSONAL \
39 _("based on personal login information")
42 _("based on a dictionary word and not a passphrase")
45 _("based on a common sequence of characters and not a passphrase")
47 #define REASON_WORDLIST \
48 _("based on a word list entry")
50 #define REASON_DENYLIST \
53 #define REASON_FILTER \
54 _("appears to be in a database")
58 typedef unsigned long fixed
;
61 * Calculates the expected number of different characters for a random
62 * password of a given length. The result is rounded down. We use this
63 * with the _requested_ minimum length (so longer passwords don't have
64 * to meet this strict requirement for their length).
66 static int expected_different(int charset
, int length
)
70 x
= ((fixed
)(charset
- 1) << FIXED_BITS
) / charset
;
73 y
= (y
* x
) >> FIXED_BITS
;
74 z
= (fixed
)charset
* (((fixed
)1 << FIXED_BITS
) - y
);
76 return (int)(z
>> FIXED_BITS
);
80 * A password is too simple if it is too short for its class, or doesn't
81 * contain enough different characters for its class, or doesn't contain
82 * enough words for a passphrase.
84 * The biases are added to the length, and they may be positive or negative.
85 * The passphrase length check uses passphrase_bias instead of bias so that
86 * zero may be passed for this parameter when the (other) bias is non-zero
87 * because of a dictionary word, which is perfectly normal for a passphrase.
88 * The biases do not affect the number of different characters, character
89 * classes, and word count.
91 static int is_simple(const passwdqc_params_qc_t
*params
, const char *newpass
,
92 int bias
, int passphrase_bias
)
94 int length
, classes
, words
, chars
;
95 int digits
, lowers
, uppers
, others
, unknowns
;
98 length
= classes
= words
= chars
= 0;
99 digits
= lowers
= uppers
= others
= unknowns
= 0;
101 while ((c
= (unsigned char)newpass
[length
])) {
115 /* A word starts when a letter follows a non-letter or when a non-ASCII
116 * character follows a space character. We treat all non-ASCII characters
117 * as non-spaces, which is not entirely correct (there's the non-breaking
118 * space character at 0xa0, 0x9a, or 0xff), but it should not hurt. */
121 if (isalpha(c
) && !isalpha(p
))
123 } else if (isspace(p
))
128 /* Count this character just once: when we're not going to see it anymore */
129 if (!strchr(&newpass
[length
], c
))
136 /* Upper case characters and digits used in common ways don't increase the
137 * strength of a password */
138 c
= (unsigned char)newpass
[0];
139 if (uppers
&& isascii(c
) && isupper(c
))
141 c
= (unsigned char)newpass
[length
- 1];
142 if (digits
&& isascii(c
) && isdigit(c
))
145 /* Count the number of different character classes we've seen. We assume
146 * that there are no non-ASCII characters for digits. */
156 if (unknowns
&& classes
<= 1 && (!classes
|| digits
|| words
>= 2))
159 for (; classes
> 0; classes
--)
162 if (length
+ bias
>= params
->min
[0] &&
163 chars
>= expected_different(10, params
->min
[0]) - 1)
168 if (length
+ bias
>= params
->min
[1] &&
169 chars
>= expected_different(36, params
->min
[1]) - 1)
171 if (!params
->passphrase_words
||
172 words
< params
->passphrase_words
)
174 if (length
+ passphrase_bias
>= params
->min
[2] &&
175 chars
>= expected_different(27, params
->min
[2]) - 1)
180 if (length
+ bias
>= params
->min
[3] &&
181 chars
>= expected_different(62, params
->min
[3]) - 1)
186 if (length
+ bias
>= params
->min
[4] &&
187 chars
>= expected_different(95, params
->min
[4]) - 1)
195 static char *unify(char *dst
, const char *src
)
201 if (!dst
&& !(dst
= malloc(strlen(src
) + 1)))
207 c
= (unsigned char)*sptr
;
208 if (isascii(c
) && isupper(c
))
215 /* Unfortunately, if we translate both 'i' and 'l' to '1', this would
216 * associate these two letters with each other - e.g., "mile" would
217 * match "MLLE", which is undesired. To solve this, we'd need to test
218 * different translations separately, which is not implemented yet. */
236 static char *reverse(const char *src
)
241 if (!(dst
= malloc(strlen(src
) + 1)))
244 sptr
= &src
[strlen(src
)];
253 static void clean(char *dst
)
257 _passwdqc_memzero(dst
, strlen(dst
));
262 * Needle is based on haystack if both contain a long enough common
263 * substring and needle would be too simple for a password with the
264 * substring either removed with partial length credit for it added
265 * or partially discounted for the purpose of the length check.
267 static int is_based(const passwdqc_params_qc_t
*params
,
268 const char *haystack
, const char *needle
, const char *original
,
277 if (!params
->match_length
) /* disabled */
280 if (params
->match_length
< 0) /* misconfigured */
286 length
= (int)strlen(needle
);
287 for (i
= 0; i
<= length
- params
->match_length
; i
++)
288 for (j
= params
->match_length
; i
+ j
<= length
; j
++) {
289 int bias
= 0, j1
= j
- 1;
290 const char q0
= needle
[i
], *q1
= &needle
[i
+ 1];
291 for (p
= haystack
; *p
; p
++)
292 if (*p
== q0
&& !strncmp(p
+ 1, q1
, j1
)) { /* or memcmp() */
293 if ((mode
& 0xff) == 0) { /* remove & credit */
295 if (!(scratch
= malloc(length
+ 1)))
300 int pos
= length
- (i
+ j
);
301 if (!(mode
& 0x100)) /* not reversed */
303 memcpy(scratch
, original
, pos
);
304 memcpy(&scratch
[pos
],
306 length
+ 1 - (pos
+ j
));
308 /* add credit for match_length - 1 chars */
309 bias
= params
->match_length
- 1;
310 if (is_simple(params
, scratch
, bias
, bias
)) {
314 } else { /* discount */
315 /* Require a 1 character longer match for substrings containing leetspeak
316 * when matching against dictionary words */
318 if ((mode
& 0xff) == 1) { /* words */
319 int pos
= i
, end
= i
+ j
;
320 if (mode
& 0x100) { /* reversed */
324 for (; pos
< end
; pos
++)
325 if (!isalpha((int)(unsigned char)
327 if (j
== params
->match_length
)
328 goto next_match_length
;
334 /* discount j - (match_length + bias) chars */
335 bias
+= (int)params
->match_length
- j
;
337 if (bias
< worst_bias
) {
338 if (is_simple(params
, original
, bias
,
339 (mode
& 0xff) == 1 ? 0 : bias
))
345 /* Zero bias implies that there were no matches for this length. If so,
346 * there's no reason to try the next substring length (it would result in
347 * no matches as well). We break out of the substring length loop and
348 * proceed with all substring lengths for the next position in needle. */
360 #define READ_LINE_MAX 8192
361 #define READ_LINE_SIZE (READ_LINE_MAX + 2)
363 static char *read_line(FILE *f
, char *buf
)
365 buf
[READ_LINE_MAX
] = '\n';
367 if (!fgets(buf
, READ_LINE_SIZE
, f
))
370 if (buf
[READ_LINE_MAX
] != '\n') {
374 } while (c
!= EOF
&& c
!= '\n');
380 if ((p
= strpbrk(buf
, "\r\n")))
387 * Common sequences of characters.
388 * We don't need to list any of the entire strings in reverse order because the
389 * code checks the new password in both "unified" and "unified and reversed"
390 * form against these strings (unifying them first indeed). We also don't have
391 * to include common repeats of characters (e.g., "777", "!!!", "1000") because
392 * these are often taken care of by the requirement on the number of different
395 const char * const seq
[] = {
399 "abcdefghijklmnopqrstuvwxyz",
400 "a1b2c3d4e5f6g7h8i9j0",
401 "1a2b3c4d5e6f7g8h9i0j",
403 "qwertyuiop[]\\asdfghjkl;'zxcvbnm,./",
404 "qwertyuiop{}|asdfghjkl:\"zxcvbnm<>?",
405 "qwertyuiopasdfghjklzxcvbnm",
406 "1qaz2wsx3edc4rfv5tgb6yhn7ujm8ik,9ol.0p;/-['=]\\",
407 "!qaz@wsx#edc$rfv%tgb^yhn&ujm*ik<(ol>)p:?_{\"+}|",
408 "qazwsxedcrfvtgbyhnujmikolp",
409 "1q2w3e4r5t6y7u8i9o0p-[=]",
410 "q1w2e3r4t5y6u7i8o9p0[-]=\\",
412 "1qaz!qaz", /* can't unify '1' and '!' - see comment in unify() */
419 * This wordlist check is now the least important given the checks above
420 * and the support for passphrases (which are based on dictionary words,
421 * and checked by other means). It is still useful to trap simple short
422 * passwords (if short passwords are allowed) that are word-based, but
423 * passed the other checks due to uncommon capitalization, digits, and
424 * special characters. We (mis)use the same set of words that are used
425 * to generate random passwords. This list is much smaller than those
426 * used for password crackers, and it doesn't contain common passwords
427 * that aren't short English words. We also support optional external
428 * wordlist (for inexact matching) and deny list (for exact matching).
430 static const char *is_word_based(const passwdqc_params_qc_t
*params
,
431 const char *unified
, const char *reversed
, const char *original
)
433 const char *reason
= REASON_ERROR
;
434 char word
[WORDSET_4K_LENGTH_MAX
+ 1], *buf
= NULL
;
438 word
[WORDSET_4K_LENGTH_MAX
] = '\0';
439 if (params
->match_length
)
440 for (i
= 0; _passwdqc_wordset_4k
[i
][0]; i
++) {
441 memcpy(word
, _passwdqc_wordset_4k
[i
], WORDSET_4K_LENGTH_MAX
);
442 int length
= (int)strlen(word
);
443 if (length
< params
->match_length
)
445 if (!memcmp(word
, _passwdqc_wordset_4k
[i
+ 1], length
))
448 if (is_based(params
, word
, unified
, original
, 1) ||
449 is_based(params
, word
, reversed
, original
, 0x101)) {
450 reason
= REASON_WORD
;
455 if (params
->match_length
)
456 for (i
= 0; i
< sizeof(seq
) / sizeof(seq
[0]); i
++) {
457 char *seq_i
= unify(NULL
, seq
[i
]);
460 if (is_based(params
, seq_i
, unified
, original
, 2) ||
461 is_based(params
, seq_i
, reversed
, original
, 0x102)) {
469 if (params
->match_length
&& params
->match_length
<= 4)
470 for (i
= 1900; i
<= 2039; i
++) {
471 sprintf(word
, "%u", i
);
472 if (is_based(params
, word
, unified
, original
, 2) ||
473 is_based(params
, word
, reversed
, original
, 0x102)) {
479 if (params
->wordlist
|| params
->denylist
)
480 if (!(buf
= malloc(READ_LINE_SIZE
)))
483 if (params
->wordlist
) {
484 if (!(f
= fopen(params
->wordlist
, "r")))
486 while (read_line(f
, buf
)) {
488 if (!strcmp(buf
, unified
) || !strcmp(buf
, reversed
))
490 if (!params
->match_length
||
491 strlen(buf
) < (size_t)params
->match_length
)
493 if (is_based(params
, buf
, unified
, original
, 1) ||
494 is_based(params
, buf
, reversed
, original
, 0x101)) {
496 reason
= REASON_WORDLIST
;
505 if (params
->denylist
) {
506 if (!(f
= fopen(params
->denylist
, "r")))
508 while (read_line(f
, buf
)) {
509 if (!strcmp(buf
, original
)) {
510 reason
= REASON_DENYLIST
;
524 _passwdqc_memzero(buf
, READ_LINE_SIZE
);
527 _passwdqc_memzero(word
, sizeof(word
));
531 const char *passwdqc_check(const passwdqc_params_qc_t
*params
,
532 const char *newpass
, const char *oldpass
, const struct passwd
*pw
)
535 char *u_newpass
= NULL
, *u_reversed
= NULL
;
536 char *u_oldpass
= NULL
;
537 char *u_name
= NULL
, *u_gecos
= NULL
, *u_dir
= NULL
;
538 const char *reason
= REASON_ERROR
;
540 size_t length
= strlen(newpass
);
542 if (length
< (size_t)params
->min
[4]) {
543 reason
= REASON_SHORT
;
547 if (length
> 10000) {
548 reason
= REASON_LONG
;
552 if (length
> (size_t)params
->max
) {
553 if (params
->max
== 8) {
555 strncat(truncated
, newpass
, 8);
558 if (oldpass
&& !strncmp(oldpass
, newpass
, 8)) {
559 reason
= REASON_SAME
;
563 reason
= REASON_LONG
;
568 if (oldpass
&& !strcmp(oldpass
, newpass
)) {
569 reason
= REASON_SAME
;
573 if (is_simple(params
, newpass
, 0, 0)) {
574 reason
= REASON_SIMPLE
;
575 if (length
< (size_t)params
->min
[1] &&
576 params
->min
[1] <= params
->max
)
577 reason
= REASON_SIMPLESHORT
;
581 if (!(u_newpass
= unify(NULL
, newpass
)))
582 goto out
; /* REASON_ERROR */
583 if (!(u_reversed
= reverse(u_newpass
)))
585 if (oldpass
&& !(u_oldpass
= unify(NULL
, oldpass
)))
588 if (!(u_name
= unify(NULL
, pw
->pw_name
)) ||
589 !(u_gecos
= unify(NULL
, pw
->pw_gecos
)) ||
590 !(u_dir
= unify(NULL
, pw
->pw_dir
)))
594 if (oldpass
&& params
->similar_deny
&&
595 (is_based(params
, u_oldpass
, u_newpass
, newpass
, 0) ||
596 is_based(params
, u_oldpass
, u_reversed
, newpass
, 0x100))) {
597 reason
= REASON_SIMILAR
;
602 (is_based(params
, u_name
, u_newpass
, newpass
, 0) ||
603 is_based(params
, u_name
, u_reversed
, newpass
, 0x100) ||
604 is_based(params
, u_gecos
, u_newpass
, newpass
, 0) ||
605 is_based(params
, u_gecos
, u_reversed
, newpass
, 0x100) ||
606 is_based(params
, u_dir
, u_newpass
, newpass
, 0) ||
607 is_based(params
, u_dir
, u_reversed
, newpass
, 0x100))) {
608 reason
= REASON_PERSONAL
;
612 reason
= is_word_based(params
, u_newpass
, u_reversed
, newpass
);
614 if (!reason
&& params
->filter
) {
615 passwdqc_filter_t flt
;
616 reason
= REASON_ERROR
;
617 if (passwdqc_filter_open(&flt
, params
->filter
))
619 int result
= passwdqc_filter_lookup(&flt
, newpass
);
620 passwdqc_filter_close(&flt
);
623 reason
= result
? REASON_FILTER
: NULL
;
627 _passwdqc_memzero(truncated
, sizeof(truncated
));