"Fossies" - the Fresh Open Source Software Archive

Member "passwdqc-2.0.3/passwdqc_check.c" (23 Jun 2023, 16179 Bytes) of package /linux/privat/passwdqc-2.0.3.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "passwdqc_check.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 1.4.0_vs_2.0.0.

    1 /*
    2  * Copyright (c) 2000-2002,2010,2013,2016,2020 by Solar Designer.  See LICENSE.
    3  */
    4 
    5 #ifdef _MSC_VER
    6 #define _CRT_SECURE_NO_WARNINGS /* we use fopen(), sprintf(), strncat() */
    7 #endif
    8 
    9 #include <stdio.h>
   10 #include <stdlib.h>
   11 #include <string.h>
   12 #include <ctype.h>
   13 
   14 #include "passwdqc.h" /* also provides <pwd.h> or equivalent "struct passwd" */
   15 #include "passwdqc_filter.h"
   16 #include "wordset_4k.h"
   17 
   18 #include "passwdqc_i18n.h"
   19 
   20 #define REASON_ERROR \
   21     _("check failed")
   22 
   23 #define REASON_SAME \
   24     _("is the same as the old one")
   25 #define REASON_SIMILAR \
   26     _("is based on the old one")
   27 
   28 #define REASON_SHORT \
   29     _("too short")
   30 #define REASON_LONG \
   31     _("too long")
   32 
   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")
   37 
   38 #define REASON_PERSONAL \
   39     _("based on personal login information")
   40 
   41 #define REASON_WORD \
   42     _("based on a dictionary word and not a passphrase")
   43 
   44 #define REASON_SEQ \
   45     _("based on a common sequence of characters and not a passphrase")
   46 
   47 #define REASON_WORDLIST \
   48     _("based on a word list entry")
   49 
   50 #define REASON_DENYLIST \
   51     _("is in deny list")
   52 
   53 #define REASON_FILTER \
   54     _("appears to be in a database")
   55 
   56 #define FIXED_BITS          15
   57 
   58 typedef unsigned long fixed;
   59 
   60 /*
   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).
   65  */
   66 static int expected_different(int charset, int length)
   67 {
   68     fixed x, y, z;
   69 
   70     x = ((fixed)(charset - 1) << FIXED_BITS) / charset;
   71     y = x;
   72     while (--length > 0)
   73         y = (y * x) >> FIXED_BITS;
   74     z = (fixed)charset * (((fixed)1 << FIXED_BITS) - y);
   75 
   76     return (int)(z >> FIXED_BITS);
   77 }
   78 
   79 /*
   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.
   83  *
   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.
   90  */
   91 static int is_simple(const passwdqc_params_qc_t *params, const char *newpass,
   92     int bias, int passphrase_bias)
   93 {
   94     int length, classes, words, chars;
   95     int digits, lowers, uppers, others, unknowns;
   96     int c, p;
   97 
   98     length = classes = words = chars = 0;
   99     digits = lowers = uppers = others = unknowns = 0;
  100     p = ' ';
  101     while ((c = (unsigned char)newpass[length])) {
  102         length++;
  103 
  104         if (!isascii(c))
  105             unknowns++;
  106         else if (isdigit(c))
  107             digits++;
  108         else if (islower(c))
  109             lowers++;
  110         else if (isupper(c))
  111             uppers++;
  112         else
  113             others++;
  114 
  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. */
  119         if (isascii(p)) {
  120             if (isascii(c)) {
  121                 if (isalpha(c) && !isalpha(p))
  122                     words++;
  123             } else if (isspace(p))
  124                 words++;
  125         }
  126         p = c;
  127 
  128 /* Count this character just once: when we're not going to see it anymore */
  129         if (!strchr(&newpass[length], c))
  130             chars++;
  131     }
  132 
  133     if (!length)
  134         return 1;
  135 
  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))
  140         uppers--;
  141     c = (unsigned char)newpass[length - 1];
  142     if (digits && isascii(c) && isdigit(c))
  143         digits--;
  144 
  145 /* Count the number of different character classes we've seen.  We assume
  146  * that there are no non-ASCII characters for digits. */
  147     classes = 0;
  148     if (digits)
  149         classes++;
  150     if (lowers)
  151         classes++;
  152     if (uppers)
  153         classes++;
  154     if (others)
  155         classes++;
  156     if (unknowns && classes <= 1 && (!classes || digits || words >= 2))
  157         classes++;
  158 
  159     for (; classes > 0; classes--)
  160     switch (classes) {
  161     case 1:
  162         if (length + bias >= params->min[0] &&
  163             chars >= expected_different(10, params->min[0]) - 1)
  164             return 0;
  165         return 1;
  166 
  167     case 2:
  168         if (length + bias >= params->min[1] &&
  169             chars >= expected_different(36, params->min[1]) - 1)
  170             return 0;
  171         if (!params->passphrase_words ||
  172             words < params->passphrase_words)
  173             continue;
  174         if (length + passphrase_bias >= params->min[2] &&
  175             chars >= expected_different(27, params->min[2]) - 1)
  176             return 0;
  177         continue;
  178 
  179     case 3:
  180         if (length + bias >= params->min[3] &&
  181             chars >= expected_different(62, params->min[3]) - 1)
  182             return 0;
  183         continue;
  184 
  185     case 4:
  186         if (length + bias >= params->min[4] &&
  187             chars >= expected_different(95, params->min[4]) - 1)
  188             return 0;
  189         continue;
  190     }
  191 
  192     return 1;
  193 }
  194 
  195 static char *unify(char *dst, const char *src)
  196 {
  197     const char *sptr;
  198     char *dptr;
  199     int c;
  200 
  201     if (!dst && !(dst = malloc(strlen(src) + 1)))
  202         return NULL;
  203 
  204     sptr = src;
  205     dptr = dst;
  206     do {
  207         c = (unsigned char)*sptr;
  208         if (isascii(c) && isupper(c))
  209             c = tolower(c);
  210         switch (c) {
  211         case 'a': case '@':
  212             c = '4'; break;
  213         case 'e':
  214             c = '3'; break;
  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. */
  219         case 'i': case '|':
  220             c = '!'; break;
  221         case 'l':
  222             c = '1'; break;
  223         case 'o':
  224             c = '0'; break;
  225         case 's': case '$':
  226             c = '5'; break;
  227         case 't': case '+':
  228             c = '7'; break;
  229         }
  230         *dptr++ = c;
  231     } while (*sptr++);
  232 
  233     return dst;
  234 }
  235 
  236 static char *reverse(const char *src)
  237 {
  238     const char *sptr;
  239     char *dst, *dptr;
  240 
  241     if (!(dst = malloc(strlen(src) + 1)))
  242         return NULL;
  243 
  244     sptr = &src[strlen(src)];
  245     dptr = dst;
  246     while (sptr > src)
  247         *dptr++ = *--sptr;
  248     *dptr = '\0';
  249 
  250     return dst;
  251 }
  252 
  253 static void clean(char *dst)
  254 {
  255     if (!dst)
  256         return;
  257     _passwdqc_memzero(dst, strlen(dst));
  258     free(dst);
  259 }
  260 
  261 /*
  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.
  266  */
  267 static int is_based(const passwdqc_params_qc_t *params,
  268     const char *haystack, const char *needle, const char *original,
  269     int mode)
  270 {
  271     char *scratch;
  272     int length;
  273     int i, j;
  274     const char *p;
  275     int worst_bias;
  276 
  277     if (!params->match_length)  /* disabled */
  278         return 0;
  279 
  280     if (params->match_length < 0)   /* misconfigured */
  281         return 1;
  282 
  283     scratch = NULL;
  284     worst_bias = 0;
  285 
  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 */
  294                 if (!scratch) {
  295                     if (!(scratch = malloc(length + 1)))
  296                         return 1;
  297                 }
  298                 /* remove j chars */
  299                 {
  300                     int pos = length - (i + j);
  301                     if (!(mode & 0x100)) /* not reversed */
  302                         pos = i;
  303                     memcpy(scratch, original, pos);
  304                     memcpy(&scratch[pos],
  305                         &original[pos + j],
  306                         length + 1 - (pos + j));
  307                 }
  308                 /* add credit for match_length - 1 chars */
  309                 bias = params->match_length - 1;
  310                 if (is_simple(params, scratch, bias, bias)) {
  311                     clean(scratch);
  312                     return 1;
  313                 }
  314             } else { /* discount */
  315 /* Require a 1 character longer match for substrings containing leetspeak
  316  * when matching against dictionary words */
  317                 bias = -1;
  318                 if ((mode & 0xff) == 1) { /* words */
  319                     int pos = i, end = i + j;
  320                     if (mode & 0x100) { /* reversed */
  321                         pos = length - end;
  322                         end = length - i;
  323                     }
  324                     for (; pos < end; pos++)
  325                     if (!isalpha((int)(unsigned char)
  326                         original[pos])) {
  327                         if (j == params->match_length)
  328                             goto next_match_length;
  329                         bias = 0;
  330                         break;
  331                     }
  332                 }
  333 
  334                 /* discount j - (match_length + bias) chars */
  335                 bias += (int)params->match_length - j;
  336                 /* bias <= -1 */
  337                 if (bias < worst_bias) {
  338                     if (is_simple(params, original, bias,
  339                         (mode & 0xff) == 1 ? 0 : bias))
  340                         return 1;
  341                     worst_bias = bias;
  342                 }
  343             }
  344         }
  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. */
  349         if (!bias)
  350             break;
  351 next_match_length:
  352         ;
  353     }
  354 
  355     clean(scratch);
  356 
  357     return 0;
  358 }
  359 
  360 #define READ_LINE_MAX 8192
  361 #define READ_LINE_SIZE (READ_LINE_MAX + 2)
  362 
  363 static char *read_line(FILE *f, char *buf)
  364 {
  365     buf[READ_LINE_MAX] = '\n';
  366 
  367     if (!fgets(buf, READ_LINE_SIZE, f))
  368         return NULL;
  369 
  370     if (buf[READ_LINE_MAX] != '\n') {
  371         int c;
  372         do {
  373             c = getc(f);
  374         } while (c != EOF && c != '\n');
  375         if (ferror(f))
  376             return NULL;
  377     }
  378 
  379     char *p;
  380     if ((p = strpbrk(buf, "\r\n")))
  381         *p = '\0';
  382 
  383     return buf;
  384 }
  385 
  386 /*
  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
  393  * characters.
  394  */
  395 const char * const seq[] = {
  396     "0123456789",
  397     "`1234567890-=",
  398     "~!@#$%^&*()_+",
  399     "abcdefghijklmnopqrstuvwxyz",
  400     "a1b2c3d4e5f6g7h8i9j0",
  401     "1a2b3c4d5e6f7g8h9i0j",
  402     "abc123",
  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[-]=\\",
  411     "1qaz1qaz",
  412     "1qaz!qaz", /* can't unify '1' and '!' - see comment in unify() */
  413     "1qazzaq1",
  414     "zaq!1qaz",
  415     "zaq!2wsx"
  416 };
  417 
  418 /*
  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).
  429  */
  430 static const char *is_word_based(const passwdqc_params_qc_t *params,
  431     const char *unified, const char *reversed, const char *original)
  432 {
  433     const char *reason = REASON_ERROR;
  434     char word[WORDSET_4K_LENGTH_MAX + 1], *buf = NULL;
  435     FILE *f = NULL;
  436     unsigned int i;
  437 
  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)
  444             continue;
  445         if (!memcmp(word, _passwdqc_wordset_4k[i + 1], length))
  446             continue;
  447         unify(word, word);
  448         if (is_based(params, word, unified, original, 1) ||
  449             is_based(params, word, reversed, original, 0x101)) {
  450             reason = REASON_WORD;
  451             goto out;
  452         }
  453     }
  454 
  455     if (params->match_length)
  456     for (i = 0; i < sizeof(seq) / sizeof(seq[0]); i++) {
  457         char *seq_i = unify(NULL, seq[i]);
  458         if (!seq_i)
  459             goto out;
  460         if (is_based(params, seq_i, unified, original, 2) ||
  461             is_based(params, seq_i, reversed, original, 0x102)) {
  462             clean(seq_i);
  463             reason = REASON_SEQ;
  464             goto out;
  465         }
  466         clean(seq_i);
  467     }
  468 
  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)) {
  474             reason = REASON_SEQ;
  475             goto out;
  476         }
  477     }
  478 
  479     if (params->wordlist || params->denylist)
  480         if (!(buf = malloc(READ_LINE_SIZE)))
  481             goto out;
  482 
  483     if (params->wordlist) {
  484         if (!(f = fopen(params->wordlist, "r")))
  485             goto out;
  486         while (read_line(f, buf)) {
  487             unify(buf, buf);
  488             if (!strcmp(buf, unified) || !strcmp(buf, reversed))
  489                 goto out_wordlist;
  490             if (!params->match_length ||
  491                 strlen(buf) < (size_t)params->match_length)
  492                 continue;
  493             if (is_based(params, buf, unified, original, 1) ||
  494                 is_based(params, buf, reversed, original, 0x101)) {
  495 out_wordlist:
  496                 reason = REASON_WORDLIST;
  497                 goto out;
  498             }
  499         }
  500         if (ferror(f))
  501             goto out;
  502         fclose(f); f = NULL;
  503     }
  504 
  505     if (params->denylist) {
  506         if (!(f = fopen(params->denylist, "r")))
  507             goto out;
  508         while (read_line(f, buf)) {
  509             if (!strcmp(buf, original)) {
  510                 reason = REASON_DENYLIST;
  511                 goto out;
  512             }
  513         }
  514         if (ferror(f))
  515             goto out;
  516     }
  517 
  518     reason = NULL;
  519 
  520 out:
  521     if (f)
  522         fclose(f);
  523     if (buf) {
  524         _passwdqc_memzero(buf, READ_LINE_SIZE);
  525         free(buf);
  526     }
  527     _passwdqc_memzero(word, sizeof(word));
  528     return reason;
  529 }
  530 
  531 const char *passwdqc_check(const passwdqc_params_qc_t *params,
  532     const char *newpass, const char *oldpass, const struct passwd *pw)
  533 {
  534     char truncated[9];
  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;
  539 
  540     size_t length = strlen(newpass);
  541 
  542     if (length < (size_t)params->min[4]) {
  543         reason = REASON_SHORT;
  544         goto out;
  545     }
  546 
  547     if (length > 10000) {
  548         reason = REASON_LONG;
  549         goto out;
  550     }
  551 
  552     if (length > (size_t)params->max) {
  553         if (params->max == 8) {
  554             truncated[0] = '\0';
  555             strncat(truncated, newpass, 8);
  556             newpass = truncated;
  557             length = 8;
  558             if (oldpass && !strncmp(oldpass, newpass, 8)) {
  559                 reason = REASON_SAME;
  560                 goto out;
  561             }
  562         } else {
  563             reason = REASON_LONG;
  564             goto out;
  565         }
  566     }
  567 
  568     if (oldpass && !strcmp(oldpass, newpass)) {
  569         reason = REASON_SAME;
  570         goto out;
  571     }
  572 
  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;
  578         goto out;
  579     }
  580 
  581     if (!(u_newpass = unify(NULL, newpass)))
  582         goto out; /* REASON_ERROR */
  583     if (!(u_reversed = reverse(u_newpass)))
  584         goto out;
  585     if (oldpass && !(u_oldpass = unify(NULL, oldpass)))
  586         goto out;
  587     if (pw) {
  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)))
  591             goto out;
  592     }
  593 
  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;
  598         goto out;
  599     }
  600 
  601     if (pw &&
  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;
  609         goto out;
  610     }
  611 
  612     reason = is_word_based(params, u_newpass, u_reversed, newpass);
  613 
  614     if (!reason && params->filter) {
  615         passwdqc_filter_t flt;
  616         reason = REASON_ERROR;
  617         if (passwdqc_filter_open(&flt, params->filter))
  618             goto out;
  619         int result = passwdqc_filter_lookup(&flt, newpass);
  620         passwdqc_filter_close(&flt);
  621         if (result < 0)
  622             goto out;
  623         reason = result ? REASON_FILTER : NULL;
  624     }
  625 
  626 out:
  627     _passwdqc_memzero(truncated, sizeof(truncated));
  628     clean(u_newpass);
  629     clean(u_reversed);
  630     clean(u_oldpass);
  631     clean(u_name);
  632     clean(u_gecos);
  633     clean(u_dir);
  634 
  635     return reason;
  636 }