1 /* Copyright (c) 2018 Zack Weinberg.
2 * All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
14 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
16 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
17 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
18 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
19 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
20 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
21 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
22 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
23 * SUCH DAMAGE.
24 *
25 * This is a clean-room reimplementation of the Sun-MD5 password hash,
26 * based on the prose description of the algorithm in the Passlib v1.7.1
27 * documentation:
28 * https://passlib.readthedocs.io/en/stable/lib/passlib.hash.sun_md5_crypt.html
29 */
30
31 #include "crypt-port.h"
32 #include "alg-md5.h"
33
34 #include <errno.h>
35 #include <stdlib.h>
36 #include <stdio.h>
37
38 #if INCLUDE_sunmd5
39
40 #define SUNMD5_PREFIX "$md5"
41 #define SUNMD5_PREFIX_LEN 4
42 #define SUNMD5_SALT_LEN 8
43 #define SUNMD5_MAX_SETTING_LEN 32 /* $md5,rounds=4294963199$12345678$ */
44 #define SUNMD5_BARE_OUTPUT_LEN 22 /* not counting the setting or the NUL */
45 #define SUNMD5_MAX_ROUNDS (0xFFFFFFFFul)
46
47 /* At each round of the algorithm, this string (including the trailing
48 NUL) may or may not be included in the input to MD5, depending on a
49 pseudorandom coin toss. It is Hamlet's famous soliloquy from the
50 play of the same name, which is in the public domain. Text from
51 <https://www.gutenberg.org/files/1524/old/2ws2610.tex> with double
52 blank lines replaced with `\n`. Note that more recent Project
53 Gutenberg editions of _Hamlet_ are punctuated differently. */
54 static const char hamlet_quotation[] =
55 "To be, or not to be,--that is the question:--\n"
56 "Whether 'tis nobler in the mind to suffer\n"
57 "The slings and arrows of outrageous fortune\n"
58 "Or to take arms against a sea of troubles,\n"
59 "And by opposing end them?--To die,--to sleep,--\n"
60 "No more; and by a sleep to say we end\n"
61 "The heartache, and the thousand natural shocks\n"
62 "That flesh is heir to,--'tis a consummation\n"
63 "Devoutly to be wish'd. To die,--to sleep;--\n"
64 "To sleep! perchance to dream:--ay, there's the rub;\n"
65 "For in that sleep of death what dreams may come,\n"
66 "When we have shuffled off this mortal coil,\n"
67 "Must give us pause: there's the respect\n"
68 "That makes calamity of so long life;\n"
69 "For who would bear the whips and scorns of time,\n"
70 "The oppressor's wrong, the proud man's contumely,\n"
71 "The pangs of despis'd love, the law's delay,\n"
72 "The insolence of office, and the spurns\n"
73 "That patient merit of the unworthy takes,\n"
74 "When he himself might his quietus make\n"
75 "With a bare bodkin? who would these fardels bear,\n"
76 "To grunt and sweat under a weary life,\n"
77 "But that the dread of something after death,--\n"
78 "The undiscover'd country, from whose bourn\n"
79 "No traveller returns,--puzzles the will,\n"
80 "And makes us rather bear those ills we have\n"
81 "Than fly to others that we know not of?\n"
82 "Thus conscience does make cowards of us all;\n"
83 "And thus the native hue of resolution\n"
84 "Is sicklied o'er with the pale cast of thought;\n"
85 "And enterprises of great pith and moment,\n"
86 "With this regard, their currents turn awry,\n"
87 "And lose the name of action.--Soft you now!\n"
88 "The fair Ophelia!--Nymph, in thy orisons\n"
89 "Be all my sins remember'd.\n";
90
91 /* Decide, pseudorandomly, whether or not to include the above quotation
92 in the input to MD5. */
93 static inline bool
94 get_nth_bit (const uint8_t digest[16], unsigned int n)
95 {
96 unsigned int byte = (n % 128) / 8;
97 unsigned int bit = (n % 128) % 8;
98 return !!(digest[byte] & (1 << bit));
99 }
100
101 static bool
102 muffet_coin_toss (const uint8_t prev_digest[16], unsigned int round_count)
103 {
104 unsigned int x, y, a, b, r, v, i;
105 for (i = 0, x = 0, y = 0; i < 8; i++)
106 {
107 a = prev_digest[(i + 0) % 16];
108 b = prev_digest[(i + 3) % 16];
109 r = a >> (b % 5);
110 v = prev_digest[r % 16];
111 if (b & (1u << (a % 8)))
112 v /= 2;
113 x |= ((unsigned int) +get_nth_bit (prev_digest, v)) << i;
114
115 a = prev_digest[(i + 8) % 16];
116 b = prev_digest[(i + 11) % 16];
117 r = a >> (b % 5);
118 v = prev_digest[r % 16];
119 if (b & (1u << (a % 8)))
120 v /= 2;
121 y |= ((unsigned int) +get_nth_bit (prev_digest, v)) << i;
122 }
123
124 if (get_nth_bit (prev_digest, round_count))
125 x /= 2;
126 if (get_nth_bit (prev_digest, round_count + 64))
127 y /= 2;
128
129 return !!(get_nth_bit (prev_digest, x) ^ get_nth_bit (prev_digest, y));
130 }
131
132 static inline void
133 write_itoa64_4 (uint8_t *output,
134 unsigned int b0, unsigned int b1, unsigned int b2)
135 {
136 unsigned int value = (b0 << 0) | (b1 << 8) | (b2 << 16);
137 output[0] = itoa64[value & 0x3f];
138 output[1] = itoa64[(value >> 6) & 0x3f];
139 output[2] = itoa64[(value >> 12) & 0x3f];
140 output[3] = itoa64[(value >> 18) & 0x3f];
141 }
142
143 /* used only for the last two bytes of crypt_sunmd5_rn output */
144 static inline void
145 write_itoa64_2 (uint8_t *output,
146 unsigned int b0, unsigned int b1, unsigned int b2)
147 {
148 unsigned int value = (b0 << 0) | (b1 << 8) | (b2 << 16);
149 output[0] = itoa64[value & 0x3f];
150 output[1] = itoa64[(value >> 6) & 0x3f];
151 }
152
153 /* Module entry points. */
154
155 void
156 crypt_sunmd5_rn (const char *phrase, size_t phr_size,
157 const char *setting, size_t ARG_UNUSED (set_size),
158 uint8_t *output, size_t out_size,
159 void *scratch, size_t scr_size)
160 {
161 struct crypt_sunmd5_scratch
162 {
163 MD5_CTX ctx;
164 uint8_t dg[16];
165 char rn[16];
166 };
167
168 /* If 'setting' doesn't start with the prefix, we should not have
169 been called in the first place. */
170 if (strncmp (setting, SUNMD5_PREFIX, SUNMD5_PREFIX_LEN)
171 || (setting[SUNMD5_PREFIX_LEN] != '$'
172 && setting[SUNMD5_PREFIX_LEN] != ','))
173 {
174 errno = EINVAL;
175 return;
176 }
177
178 /* For bug-compatibility with the original implementation, we allow
179 'rounds=' to follow either '$md5,' or '$md5$'. */
180 const char *p = setting + SUNMD5_PREFIX_LEN + 1;
181 unsigned int nrounds = 4096;
182 if (!strncmp (p, "rounds=", sizeof "rounds=" - 1))
183 {
184 p += sizeof "rounds=" - 1;
185 /* Do not allow an explicit setting of zero additional rounds,
186 nor leading zeroes on the number of rounds. */
187 if (!(*p >= '1' && *p <= '9'))
188 {
189 errno = EINVAL;
190 return;
191 }
192
193 errno = 0;
194 char *endp;
195 unsigned long arounds = strtoul (p, &endp, 10);
196 if (endp == p || arounds > SUNMD5_MAX_ROUNDS || errno)
197 {
198 errno = EINVAL;
199 return;
200 }
201 nrounds += (unsigned int)arounds;
202 p = endp;
203 if (*p != '$')
204 {
205 errno = EINVAL;
206 return;
207 }
208 p += 1;
209 }
210
211 /* p now points to the beginning of the actual salt. */
212 p += strspn (p, (const char *)itoa64);
213 if (*p != '\0' && *p != '$')
214 {
215 errno = EINVAL;
216 return;
217 }
218 /* For bug-compatibility with the original implementation, if p
219 points to a '$' and the following character is either another '$'
220 or NUL, the first '$' should be included in the salt. */
221 if (p[0] == '$' && (p[1] == '$' || p[1] == '\0'))
222 p += 1;
223
224 size_t saltlen = (size_t) (p - setting);
225 /* Do we have enough space? */
226 if (scr_size < sizeof (struct crypt_sunmd5_scratch)
227 || out_size < saltlen + SUNMD5_BARE_OUTPUT_LEN + 2)
228 {
229 errno = ERANGE;
230 return;
231 }
232
233 struct crypt_sunmd5_scratch *s = scratch;
234
235 /* Initial round. */
236 MD5_Init (&s->ctx);
237 MD5_Update (&s->ctx, phrase, phr_size);
238 MD5_Update (&s->ctx, setting, saltlen);
239 MD5_Final (s->dg, &s->ctx);
240
241 /* Stretching rounds. */
242 for (unsigned int i = 0; i < nrounds; i++)
243 {
244 MD5_Init (&s->ctx);
245
246 MD5_Update (&s->ctx, s->dg, sizeof s->dg);
247
248 /* The trailing nul is intentionally included. */
249 if (muffet_coin_toss (s->dg, i))
250 MD5_Update (&s->ctx, hamlet_quotation, sizeof hamlet_quotation);
251
252 int nwritten = snprintf (s->rn, sizeof s->rn, "%u", i);
253 assert (nwritten >= 1 && (unsigned int)nwritten + 1 <= sizeof s->rn);
254 MD5_Update (&s->ctx, s->rn, (unsigned int)nwritten);
255
256 MD5_Final (s->dg, &s->ctx);
257 }
258
259 memcpy (output, setting, saltlen);
260 *(output + saltlen + 0) = '$';
261 /* This is the same permuted order used by BSD md5-crypt ($1$). */
262 write_itoa64_4 (output + saltlen + 1, s->dg[12], s->dg[ 6], s->dg[0]);
263 write_itoa64_4 (output + saltlen + 5, s->dg[13], s->dg[ 7], s->dg[1]);
264 write_itoa64_4 (output + saltlen + 9, s->dg[14], s->dg[ 8], s->dg[2]);
265 write_itoa64_4 (output + saltlen + 13, s->dg[15], s->dg[ 9], s->dg[3]);
266 write_itoa64_4 (output + saltlen + 17, s->dg[ 5], s->dg[10], s->dg[4]);
267 write_itoa64_2 (output + saltlen + 21, s->dg[11], 0, 0);
268 *(output + saltlen + 23) = '\0';
269 }
270
271 void
272 gensalt_sunmd5_rn (unsigned long count,
273 const uint8_t *rbytes,
274 size_t nrbytes,
275 uint8_t *output,
276 size_t o_size)
277 {
278 if (o_size < SUNMD5_MAX_SETTING_LEN + 1)
279 {
280 errno = ERANGE;
281 return;
282 }
283 if (nrbytes < 6 + 2)
284 {
285 errno = EINVAL;
286 return;
287 }
288
289 /* The default number of rounds, 4096, is much too low. The actual
290 number of rounds is somewhat randomized to make construction of
291 rainbow tables more difficult (effectively this means an extra 16
292 bits of entropy are smuggled into the salt via the round number). */
293 if (count < 32768)
294 count = 32768;
295 else if (count > SUNMD5_MAX_ROUNDS - 65536)
296 count = SUNMD5_MAX_ROUNDS - 65536;
297
298 count += ((unsigned long)rbytes[0]) << 8;
299 count += ((unsigned long)rbytes[1]) << 0;
300
301 assert (count != 0);
302
303 size_t written = (size_t) snprintf ((char *)output, o_size,
304 "%s,rounds=%lu$", SUNMD5_PREFIX, count);
305
306
307 write_itoa64_4(output + written + 0, rbytes[2], rbytes[3], rbytes[4]);
308 write_itoa64_4(output + written + 4, rbytes[5], rbytes[6], rbytes[7]);
309
310 output[written + 8] = '$';
311 output[written + 9] = '\0';
312 }
313
314 #endif