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 } 235