contrib/pam_passwdqc/passwdqc_check.c

   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 }