193787Sdes/* 294691Sdes * Copyright (c) 2000-2002 by Solar Designer. See LICENSE. 393787Sdes */ 493787Sdes 593787Sdes#include <stdlib.h> 693787Sdes#include <string.h> 793787Sdes#include <ctype.h> 893787Sdes#include <pwd.h> 993787Sdes 1093787Sdes#include "passwdqc.h" 1193787Sdes 1293787Sdes#define REASON_ERROR \ 1393787Sdes "check failed" 1493787Sdes 1593787Sdes#define REASON_SAME \ 1693787Sdes "is the same as the old one" 1793787Sdes#define REASON_SIMILAR \ 1893787Sdes "is based on the old one" 1993787Sdes 2093787Sdes#define REASON_SHORT \ 2193787Sdes "too short" 2293787Sdes#define REASON_LONG \ 2393787Sdes "too long" 2493787Sdes 2593787Sdes#define REASON_SIMPLESHORT \ 2693787Sdes "not enough different characters or classes for this length" 2793787Sdes#define REASON_SIMPLE \ 2893787Sdes "not enough different characters or classes" 2993787Sdes 3093787Sdes#define REASON_PERSONAL \ 3193787Sdes "based on personal login information" 3293787Sdes 3393787Sdes#define REASON_WORD \ 3493787Sdes "based on a dictionary word and not a passphrase" 3593787Sdes 3693787Sdes#define FIXED_BITS 15 3793787Sdes 3893787Sdestypedef unsigned long fixed; 3993787Sdes 4093787Sdes/* 4193787Sdes * Calculates the expected number of different characters for a random 4293787Sdes * password of a given length. The result is rounded down. We use this 4393787Sdes * with the _requested_ minimum length (so longer passwords don't have 4493787Sdes * to meet this strict requirement for their length). 4593787Sdes */ 4693787Sdesstatic int expected_different(int charset, int length) 4793787Sdes{ 4893787Sdes fixed x, y, z; 4993787Sdes 5093787Sdes x = ((fixed)(charset - 1) << FIXED_BITS) / charset; 5193787Sdes y = x; 5293787Sdes while (--length > 0) y = (y * x) >> FIXED_BITS; 5393787Sdes z = (fixed)charset * (((fixed)1 << FIXED_BITS) - y); 5493787Sdes 5593787Sdes return (int)(z >> FIXED_BITS); 5693787Sdes} 5793787Sdes 5893787Sdes/* 5993787Sdes * A password is too simple if it is too short for its class, or doesn't 6093787Sdes * contain enough different characters for its class, or doesn't contain 6193787Sdes * enough words for a passphrase. 6293787Sdes */ 6394691Sdesstatic int is_simple(passwdqc_params_t *params, const char *newpass) 6493787Sdes{ 6593787Sdes int length, classes, words, chars; 6693787Sdes int digits, lowers, uppers, others, unknowns; 6793787Sdes int c, p; 6893787Sdes 6993787Sdes length = classes = words = chars = 0; 7093787Sdes digits = lowers = uppers = others = unknowns = 0; 7193787Sdes p = ' '; 7293787Sdes while ((c = (unsigned char)newpass[length])) { 7393787Sdes length++; 7493787Sdes 7593787Sdes if (!isascii(c)) unknowns++; else 7693787Sdes if (isdigit(c)) digits++; else 7793787Sdes if (islower(c)) lowers++; else 7893787Sdes if (isupper(c)) uppers++; else 7993787Sdes others++; 8093787Sdes 8193787Sdes if (isascii(c) && isalpha(c) && isascii(p) && !isalpha(p)) 8293787Sdes words++; 8393787Sdes p = c; 8493787Sdes 8593787Sdes if (!strchr(&newpass[length], c)) 8693787Sdes chars++; 8793787Sdes } 8893787Sdes 8993787Sdes if (!length) return 1; 9093787Sdes 9193787Sdes/* Upper case characters and digits used in common ways don't increase the 9293787Sdes * strength of a password */ 9393787Sdes c = (unsigned char)newpass[0]; 9493787Sdes if (uppers && isascii(c) && isupper(c)) uppers--; 9593787Sdes c = (unsigned char)newpass[length - 1]; 9693787Sdes if (digits && isascii(c) && isdigit(c)) digits--; 9793787Sdes 9893787Sdes/* Count the number of different character classes we've seen. We assume 9993787Sdes * that there're no non-ASCII characters for digits. */ 10093787Sdes classes = 0; 10193787Sdes if (digits) classes++; 10293787Sdes if (lowers) classes++; 10393787Sdes if (uppers) classes++; 10493787Sdes if (others) classes++; 10593787Sdes if (unknowns && (!classes || (digits && classes == 1))) classes++; 10693787Sdes 10793787Sdes for (; classes > 0; classes--) 10893787Sdes switch (classes) { 10993787Sdes case 1: 11093787Sdes if (length >= params->min[0] && 11193787Sdes chars >= expected_different(10, params->min[0]) - 1) 11293787Sdes return 0; 11393787Sdes return 1; 11493787Sdes 11593787Sdes case 2: 11693787Sdes if (length >= params->min[1] && 11793787Sdes chars >= expected_different(36, params->min[1]) - 1) 11893787Sdes return 0; 11993787Sdes if (!params->passphrase_words || 12093787Sdes words < params->passphrase_words) 12193787Sdes continue; 12293787Sdes if (length >= params->min[2] && 12393787Sdes chars >= expected_different(27, params->min[2]) - 1) 12493787Sdes return 0; 12593787Sdes continue; 12693787Sdes 12793787Sdes case 3: 12893787Sdes if (length >= params->min[3] && 12993787Sdes chars >= expected_different(62, params->min[3]) - 1) 13093787Sdes return 0; 13193787Sdes continue; 13293787Sdes 13393787Sdes case 4: 13493787Sdes if (length >= params->min[4] && 13593787Sdes chars >= expected_different(95, params->min[4]) - 1) 13693787Sdes return 0; 13793787Sdes continue; 13893787Sdes } 13993787Sdes 14093787Sdes return 1; 14193787Sdes} 14293787Sdes 14394691Sdesstatic char *unify(const char *src) 14493787Sdes{ 14594691Sdes const char *sptr; 14694691Sdes char *dst, *dptr; 14793787Sdes int c; 14893787Sdes 14993787Sdes if (!(dst = malloc(strlen(src) + 1))) 15093787Sdes return NULL; 15193787Sdes 15293787Sdes sptr = src; 15393787Sdes dptr = dst; 15493787Sdes do { 15593787Sdes c = (unsigned char)*sptr; 15693787Sdes if (isascii(c) && isupper(c)) 15793787Sdes *dptr++ = tolower(c); 15893787Sdes else 15993787Sdes *dptr++ = *sptr; 16093787Sdes } while (*sptr++); 16193787Sdes 16293787Sdes return dst; 16393787Sdes} 16493787Sdes 16594691Sdesstatic char *reverse(const char *src) 16693787Sdes{ 16794691Sdes const char *sptr; 16894691Sdes char *dst, *dptr; 16993787Sdes 17093787Sdes if (!(dst = malloc(strlen(src) + 1))) 17193787Sdes return NULL; 17293787Sdes 17393787Sdes sptr = &src[strlen(src)]; 17493787Sdes dptr = dst; 17593787Sdes while (sptr > src) 17693787Sdes *dptr++ = *--sptr; 17793787Sdes *dptr = '\0'; 17893787Sdes 17993787Sdes return dst; 18093787Sdes} 18193787Sdes 18293787Sdesstatic void clean(char *dst) 18393787Sdes{ 18493787Sdes if (dst) { 18593787Sdes memset(dst, 0, strlen(dst)); 18693787Sdes free(dst); 18793787Sdes } 18893787Sdes} 18993787Sdes 19093787Sdes/* 19193787Sdes * Needle is based on haystack if both contain a long enough common 19293787Sdes * substring and needle would be too simple for a password with the 19393787Sdes * substring removed. 19493787Sdes */ 19593787Sdesstatic int is_based(passwdqc_params_t *params, 19694691Sdes const char *haystack, const char *needle, const char *original) 19793787Sdes{ 19893787Sdes char *scratch; 19993787Sdes int length; 20093787Sdes int i, j; 20194691Sdes const char *p; 20293787Sdes int match; 20393787Sdes 20493787Sdes if (!params->match_length) /* disabled */ 20593787Sdes return 0; 20693787Sdes 20793787Sdes if (params->match_length < 0) /* misconfigured */ 20893787Sdes return 1; 20993787Sdes 21093787Sdes if (strstr(haystack, needle)) /* based on haystack entirely */ 21193787Sdes return 1; 21293787Sdes 21393787Sdes scratch = NULL; 21493787Sdes 21593787Sdes length = strlen(needle); 21693787Sdes for (i = 0; i <= length - params->match_length; i++) 21793787Sdes for (j = params->match_length; i + j <= length; j++) { 21893787Sdes match = 0; 21993787Sdes for (p = haystack; *p; p++) 22093787Sdes if (*p == needle[i] && !strncmp(p, &needle[i], j)) { 22193787Sdes match = 1; 22293787Sdes if (!scratch) { 22393787Sdes if (!(scratch = malloc(length + 1))) 22493787Sdes return 1; 22593787Sdes } 22693787Sdes memcpy(scratch, original, i); 22793787Sdes memcpy(&scratch[i], &original[i + j], 22893787Sdes length + 1 - (i + j)); 22993787Sdes if (is_simple(params, scratch)) { 23093787Sdes clean(scratch); 23193787Sdes return 1; 23293787Sdes } 23393787Sdes } 23493787Sdes if (!match) break; 23593787Sdes } 23693787Sdes 23793787Sdes clean(scratch); 23893787Sdes 23993787Sdes return 0; 24093787Sdes} 24193787Sdes 24293787Sdes/* 24393787Sdes * This wordlist check is now the least important given the checks above 24493787Sdes * and the support for passphrases (which are based on dictionary words, 24593787Sdes * and checked by other means). It is still useful to trap simple short 24693787Sdes * passwords (if short passwords are allowed) that are word-based, but 24793787Sdes * passed the other checks due to uncommon capitalization, digits, and 24893787Sdes * special characters. We (mis)use the same set of words that are used 24993787Sdes * to generate random passwords. This list is much smaller than those 25093787Sdes * used for password crackers, and it doesn't contain common passwords 25193787Sdes * that aren't short English words. Perhaps support for large wordlists 25293787Sdes * should still be added, even though this is now of little importance. 25393787Sdes */ 25493787Sdesstatic int is_word_based(passwdqc_params_t *params, 25594691Sdes const char *needle, const char *original) 25693787Sdes{ 25793787Sdes char word[7]; 25893787Sdes char *unified; 25994691Sdes int i; 26093787Sdes 26193787Sdes word[6] = '\0'; 26294691Sdes for (i = 0; i < 0x1000; i++) { 26394691Sdes memcpy(word, _passwdqc_wordset_4k[i], 6); 26494691Sdes if ((int)strlen(word) < params->match_length) continue; 26593787Sdes unified = unify(word); 26693787Sdes if (is_based(params, unified, needle, original)) { 26793787Sdes clean(unified); 26893787Sdes return 1; 26993787Sdes } 27093787Sdes clean(unified); 27193787Sdes } 27293787Sdes 27393787Sdes return 0; 27493787Sdes} 27593787Sdes 27694691Sdesconst char *_passwdqc_check(passwdqc_params_t *params, 27794691Sdes const char *newpass, const char *oldpass, struct passwd *pw) 27893787Sdes{ 27993787Sdes char truncated[9], *reversed; 28093787Sdes char *u_newpass, *u_reversed; 28193787Sdes char *u_oldpass; 28293787Sdes char *u_name, *u_gecos; 28394691Sdes const char *reason; 28493787Sdes int length; 28593787Sdes 28693787Sdes reversed = NULL; 28793787Sdes u_newpass = u_reversed = NULL; 28893787Sdes u_oldpass = NULL; 28993787Sdes u_name = u_gecos = NULL; 29093787Sdes 29193787Sdes reason = NULL; 29293787Sdes 29393787Sdes if (oldpass && !strcmp(oldpass, newpass)) 29493787Sdes reason = REASON_SAME; 29593787Sdes 29693787Sdes length = strlen(newpass); 29793787Sdes 29893787Sdes if (!reason && length < params->min[4]) 29993787Sdes reason = REASON_SHORT; 30093787Sdes 30193787Sdes if (!reason && length > params->max) { 30293787Sdes if (params->max == 8) { 30393787Sdes truncated[0] = '\0'; 30493787Sdes strncat(truncated, newpass, 8); 30593787Sdes newpass = truncated; 30693787Sdes if (oldpass && !strncmp(oldpass, newpass, 8)) 30793787Sdes reason = REASON_SAME; 30893787Sdes } else 30993787Sdes reason = REASON_LONG; 31093787Sdes } 31193787Sdes 31293787Sdes if (!reason && is_simple(params, newpass)) { 31393787Sdes if (length < params->min[1] && params->min[1] <= params->max) 31493787Sdes reason = REASON_SIMPLESHORT; 31593787Sdes else 31693787Sdes reason = REASON_SIMPLE; 31793787Sdes } 31893787Sdes 31993787Sdes if (!reason) { 32093787Sdes if ((reversed = reverse(newpass))) { 32193787Sdes u_newpass = unify(newpass); 32293787Sdes u_reversed = unify(reversed); 32393787Sdes if (oldpass) 32493787Sdes u_oldpass = unify(oldpass); 32593787Sdes if (pw) { 32693787Sdes u_name = unify(pw->pw_name); 32793787Sdes u_gecos = unify(pw->pw_gecos); 32893787Sdes } 32993787Sdes } 33093787Sdes if (!reversed || 33193787Sdes !u_newpass || !u_reversed || 33293787Sdes (oldpass && !u_oldpass) || 33393787Sdes (pw && (!u_name || !u_gecos))) 33493787Sdes reason = REASON_ERROR; 33593787Sdes } 33693787Sdes 33793787Sdes if (!reason && oldpass && params->similar_deny && 33893787Sdes (is_based(params, u_oldpass, u_newpass, newpass) || 33993787Sdes is_based(params, u_oldpass, u_reversed, reversed))) 34093787Sdes reason = REASON_SIMILAR; 34193787Sdes 34293787Sdes if (!reason && pw && 34393787Sdes (is_based(params, u_name, u_newpass, newpass) || 34493787Sdes is_based(params, u_name, u_reversed, reversed) || 34593787Sdes is_based(params, u_gecos, u_newpass, newpass) || 34693787Sdes is_based(params, u_gecos, u_reversed, reversed))) 34793787Sdes reason = REASON_PERSONAL; 34893787Sdes 34994691Sdes if (!reason && (int)strlen(newpass) < params->min[2] && 35093787Sdes (is_word_based(params, u_newpass, newpass) || 35193787Sdes is_word_based(params, u_reversed, reversed))) 35293787Sdes reason = REASON_WORD; 35393787Sdes 35493787Sdes memset(truncated, 0, sizeof(truncated)); 35593787Sdes clean(reversed); 35693787Sdes clean(u_newpass); clean(u_reversed); 35793787Sdes clean(u_oldpass); 35893787Sdes clean(u_name); clean(u_gecos); 35993787Sdes 36093787Sdes return reason; 36193787Sdes} 362