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