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
read_loop(int fd,void * buffer,size_t count)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
passwdqc_random(const passwdqc_params_qc_t * params)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