contrib/pam_passwdqc/passwdqc_random.c

   1 /*
   2  * Copyright (c) 2000-2002,2005,2008,2010,2013,2016,2021 by Solar Designer
   3  * See LICENSE
   4  */
   5
   6 #ifdef _MSC_VER
   7 #define _CRT_NONSTDC_NO_WARNINGS /* we use POSIX function names */
   8 #include <windows.h>
   9 #include <wincrypt.h>
  10 #else
  11 #include <limits.h>
  12 #include <unistd.h>
  13 #include <errno.h>
  14 #include <fcntl.h>
  15 #endif
  16
  17 #include <string.h>
  18
  19 #include "passwdqc.h"
  20 #include "wordset_4k.h"
  21
  22 /*
  23  * We separate words in the generated "passphrases" with random special
  24  * characters out of a set of 16 (so we encode 4 bits per separator
  25  * character).  To enable the use of our "passphrases" within FTP URLs
  26  * (and similar), we pick characters that are defined by RFC 3986 as
  27  * being safe within "userinfo" part of URLs without encoding and
  28  * without having a special meaning.  Out of those, we avoid characters
  29  * that are visually ambiguous or difficult over the phone.  This
  30  * happens to leave us with exactly 8 symbols, and we add 8 digits that
  31  * are not visually ambiguous.  Unfortunately, the exclamation mark
  32  * might be confused for the digit 1 (which we don't use), though.
  33  */
  34 #define SEPARATORS                      "-_!$&*+=23456789"
  35
  36 /*
  37  * Number of bits encoded per separator character.
  38  */
  39 #define SEPARATOR_BITS                  4
  40
  41 /*
  42  * Number of bits encoded per word.  We use 4096 words, which gives 12 bits,
  43  * and we toggle the case of the first character, which gives one bit more.
  44  */
  45 #define WORD_BITS                       13
  46
  47 /*
  48  * Number of bits encoded per separator and word.
  49  */
  50 #define SWORD_BITS \
  51         (SEPARATOR_BITS + WORD_BITS)
  52
  53 /*
  54  * Maximum number of words to use.
  55  */
  56 #define WORDS_MAX                       8
  57
  58 /*
  59  * Minimum and maximum number of bits to encode.  With the settings above,
  60  * these are 24 and 136, respectively.
  61  */
  62 #define BITS_MIN \
  63         (2 * (WORD_BITS - 1))
  64 #define BITS_MAX \
  65         (WORDS_MAX * SWORD_BITS)
  66
  67 #ifndef _MSC_VER
  68 static ssize_t read_loop(int fd, void *buffer, size_t count)
  69 {
  70         ssize_t offset, block;
  71
  72         offset = 0;
  73         while (count > 0 && count <= SSIZE_MAX) {
  74                 block = read(fd, (char *)buffer + offset, count);
  75
  76                 if (block < 0) {
  77                         if (errno == EINTR)
  78                                 continue;
  79                         return block;
  80                 }
  81
  82                 if (!block)
  83                         return offset;
  84
  85                 offset += block;
  86                 count -= block;
  87         }
  88
  89         return offset;
  90 }
  91 #endif
  92
  93 char *passwdqc_random(const passwdqc_params_qc_t *params)
  94 {
  95         int bits = params->random_bits; /* further code assumes signed type */
  96         if (bits < BITS_MIN || bits > BITS_MAX)
  97                 return NULL;
  98
  99 /*
 100  * Calculate the number of words to use.  The first word is always present
 101  * (hence the "1 +" and the "- WORD_BITS").  Each one of the following words,
 102  * if any, is prefixed by a separator character, so we use SWORD_BITS when
 103  * calculating how many additional words to use.  We divide "bits - WORD_BITS"
 104  * by SWORD_BITS with rounding up (hence the addition of "SWORD_BITS - 1").
 105  */
 106         int word_count = 1 + (bits + (SWORD_BITS - 1 - WORD_BITS)) / SWORD_BITS;
 107
 108 /*
 109  * Special case: would we still encode enough bits if we omit the final word,
 110  * but keep the would-be-trailing separator?
 111  */
 112         int trailing_separator = (SWORD_BITS * (word_count - 1) >= bits);
 113         word_count -= trailing_separator;
 114
 115 /*
 116  * To determine whether we need to use different separator characters or maybe
 117  * not, calculate the number of words we'd need to use if we don't use
 118  * different separators.  We calculate it by dividing "bits" by WORD_BITS with
 119  * rounding up (hence the addition of "WORD_BITS - 1").  The resulting number
 120  * is either the same as or greater than word_count.  Use different separators
 121  * only if their use, in the word_count calculation above, has helped reduce
 122  * word_count.
 123  */
 124         int use_separators = ((bits + (WORD_BITS - 1)) / WORD_BITS != word_count);
 125         trailing_separator &= use_separators;
 126
 127 /*
 128  * Toggle case of the first character of each word only if we wouldn't achieve
 129  * sufficient entropy otherwise.
 130  */
 131         int toggle_case = (bits >
 132             ((WORD_BITS - 1) * word_count) +
 133             (use_separators ? (SEPARATOR_BITS * (word_count - !trailing_separator)) : 0));
 134
 135         char output[0x100];
 136
 137 /*
 138  * Calculate and check the maximum possible length of a "passphrase" we may
 139  * generate for a given word_count.  We add 1 to WORDSET_4K_LENGTH_MAX to
 140  * account for separators (whether different or not).  When there's no
 141  * trailing separator, we subtract 1.  The check against sizeof(output) uses
 142  * ">=" to account for NUL termination.
 143  */
 144         unsigned int max_length = word_count * (WORDSET_4K_LENGTH_MAX + 1) - !trailing_separator;
 145         if (max_length >= sizeof(output) || (int)max_length > params->max)
 146                 return NULL;
 147
 148         unsigned char rnd[WORDS_MAX * 3];
 149
 150 #ifdef _MSC_VER
 151         HCRYPTPROV hprov;
 152         if (!CryptAcquireContextA(&hprov, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT | CRYPT_SILENT))
 153                 return NULL;
 154         memset(rnd, 0, sizeof(rnd)); /* old Windows would use previous content as extra seed */
 155         if (!CryptGenRandom(hprov, sizeof(rnd), rnd)) {
 156                 CryptReleaseContext(hprov, 0);
 157                 return NULL;
 158         }
 159         CryptReleaseContext(hprov, 0);
 160 #else
 161         int fd;
 162         if ((fd = open("/dev/urandom", O_RDONLY)) < 0)
 163                 return NULL;
 164         if (read_loop(fd, rnd, sizeof(rnd)) != sizeof(rnd)) {
 165                 close(fd);
 166                 return NULL;
 167         }
 168         close(fd);
 169 #endif
 170
 171         size_t length = 0;
 172         const unsigned char *rndptr;
 173
 174         for (rndptr = rnd; rndptr <= rnd + sizeof(rnd) - 3; rndptr += 3) {
 175 /*
 176  * Append a word.
 177  *
 178  * Treating *rndptr as little-endian, we use bits 0 to 11 for the word index
 179  * and bit 13 for toggling the case of the first character.  Bits 12, 14, and
 180  * 15 are left unused.  Bits 16 to 23 are left for the separator.
 181  */
 182                 unsigned int i = (((unsigned int)rndptr[1] & 0x0f) << 8) | rndptr[0];
 183                 const char *start = _passwdqc_wordset_4k[i];
 184                 const char *end = memchr(start, '\0', WORDSET_4K_LENGTH_MAX);
 185                 if (!end)
 186                         end = start + WORDSET_4K_LENGTH_MAX;
 187                 size_t extra = end - start;
 188 /* The ">=" leaves room for either one more separator or NUL */
 189                 if (length + extra >= sizeof(output))
 190                         break;
 191                 memcpy(&output[length], start, extra);
 192                 if (toggle_case) {
 193 /* Toggle case if bit set (we assume ASCII) */
 194                         output[length] ^= rndptr[1] & 0x20;
 195                         bits--;
 196                 }
 197                 length += extra;
 198                 bits -= WORD_BITS - 1;
 199
 200                 if (bits <= 0)
 201                         break;
 202
 203 /*
 204  * Append a separator character.  We use bits 16 to 19.  Bits 20 to 23 are left
 205  * unused.
 206  *
 207  * Special case: we may happen to leave a trailing separator if it provides
 208  * enough bits on its own.  With WORD_BITS 13 and SEPARATOR_BITS 4, this
 209  * happens e.g. for bits values from 31 to 34, 48 to 51, 65 to 68.
 210  */
 211                 if (use_separators) {
 212                         i = rndptr[2] & 0x0f;
 213                         output[length++] = SEPARATORS[i];
 214                         bits -= SEPARATOR_BITS;
 215                 } else {
 216                         output[length++] = SEPARATORS[0];
 217                 }
 218
 219                 if (bits <= 0)
 220                         break;
 221         }
 222
 223         char *retval = NULL;
 224
 225         if (bits <= 0 && length < sizeof(output)) {
 226                 output[length] = '\0';
 227                 retval = strdup(output);
 228         }
 229
 230         _passwdqc_memzero(rnd, sizeof(rnd));
 231         _passwdqc_memzero(output, length);
 232
 233         return retval;
 234 }