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 38 typedef 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 */ 46 static 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 */ 63 static 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 are 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 143 static 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 165 static 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 182 static 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 */ 195 static 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 */ 254 static 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 276 const 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