/* Password hasher for the LPC crypt() function.
*
* The hasher is based on the MD5 message digest algorithm.
* In this module MD5 is implemented from scratch using RFC 1321.
* RFC 1321 is ``The MD5 Message-Digest Algorithm'', by R. Rivest.
*
* Implemented by Fermat@Equilibria <bjgras@cs.vu.nl> for MudOS.
*
* 970125: First version.
* 970131: Added crunchbuffer() to allow the crypting of passwords
* of (practically) arbitrary length -- custom_crypt() should now
* never return NULL.
* 970205: Added fix for little-endian systems (well, fix for 486 actually),
* plus `reference results'.
*
*
* Note:
*
* This should work equally on little- and big-endian, 16, 32 and 64 bit
* systems alike (well, everywhere really), but I can't test it everywhere.
* Please mail me if you can't reproduce any of the following results (and
* are prepared to work out the fixes with me):
*
* key: "thing"
* salt: "anhlklck!"
* result: "anhlklck!ggddl`l`lg`bjblodlfcljdcnhffib`c"
*
* key: "this is a ridiculously long PW that nobody would really use"
* salt: "saltstring"
* result: "nahhdhfc!dhbeclbjk`llmhifc`jedo`adbdboc`k"
*
* key: ""
* salt: ""
* salt: ""
* result: "ijegehja!j`kacklajkljde`od`ogdmlnbfl`bjfo"
*
* This doesn't apply, of course, if you change any of the settings
* or any other code before trying this.
*
* =Fermat
*
*/
#include "std.h"
#include "port.h"
#include "crypt.h"
#ifdef CUSTOM_CRYPT
#ifndef min
#define min(a,b) ((a) < (b) ? (a) : (b))
#endif
/* Can we cheat and just use network byte order (and htonl/ntohl) here?
* -Beek
*/
/* MIRROR: inverts the order of bytes in a 32-bit quantity, if
* necessary.
* Define this to be empty on big-endian systems:
* #define MIRROR(l)
* And for little-endian systems something like:
* #define MIRROR(l) ( (l) = ( ((l) << 24) | (((l) & 0x0000ff00) << 8)
| (((l) & 0x00ff0000) >> 8) | ((l) >> 24) ) )
*/
#ifdef BIGENDIAN
#define MIRROR(l)
#else
#define MIRROR(l) ( (l) = ( ((l) << 24) | (((l) & 0x0000ff00) << 8) | (((l) & 0x00ff0000) >> 8) | ((l) >> 24) ) )
#endif
/* Functions F, G, H and I as mentioned in RFC, section 3.4. */
#define F(X, Y, Z) (((X)&(Y))|((~(X))&(Z)))
#define G(X, Y, Z) (((X)&(Z))|((~(Z))&(Y)))
#define H(X, Y, Z) ((X)^(Y)^(Z))
#define I(X, Y, Z) ((Y)^((X)|(~(Z))))
/* Left rotation. */
#define RLEFT(a, n) (a) = (((a) << (n)) | ((a) >> (32-(n))))
/* Table T constructed from a sine function, mentioned in RFC, section 3.4.
* Table T[i], 1 <= i <= 64, = trunc (4294967296 * |sin i|).
*/
UINT32 T[64] = {
0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,0xf57c0faf,0x4787c62a,
0xa8304613,0xfd469501,0x698098d8,0x8b44f7af,0xffff5bb1,0x895cd7be,
0x6b901122,0xfd987193,0xa679438e,0x49b40821,0xf61e2562,0xc040b340,
0x265e5a51,0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905,0xfcefa3f8,
0x676f02d9,0x8d2a4c8a,0xfffa3942,0x8771f681,0x6d9d6122,0xfde5380c,
0xa4beea44,0x4bdecfa9,0xf6bb4b60,0xbebfbc70,0x289b7ec6,0xeaa127fa,
0xd4ef3085,0x04881d05,0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,
0xf4292244,0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92,
0xffeff47d,0x85845dd1,0x6fa87e4f,0xfe2ce6e0,0xa3014314,0x4e0811a1,
0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391
};
/* This function returns success, i.e. 0 on error. */
int MD5Digest( BytE *buf, /* Buffer to be digested. */
unsigned long buflen, /* Length of the buffer in bytes.
*/
BytE *Digest /* Output area: 16 raw bytes. */
)
{
#define OA 0x67452301 /* Per RFC, section 3.3. */
#define OB 0xefcdab89
#define OC 0x98badcfe
#define OD 0x10325476
UINT32 A = OA, B = OB, C = OC, D = OD;
static UINT32 Block[16]; /* One block: 512 bits. */
if(buflen > MD5_MAXLEN) return 0; /* Too large. */
/* Create the block we're going to digest: padded. */
memset(Block, 0, sizeof(Block));
memcpy(Block, buf, buflen);
{ int i; for(i = 0; i <= buflen/4; i++) { MIRROR(Block[i]); } }
Block[buflen>>2] |= 0x00000080 << (8 * (buflen % 4));
Block[14] = buflen << 3; /* Number of bits in original data. */
/* MD5 Transformation. */
#define Tr(a, b, c, d, k, s, i, x) (a) += x(b,c,d) + Block[k] + T[(i)-1]; RLEFT(a, s); (a) += (b);
/* Round 1 */
Tr(A,B,C,D, 0, 7, 1,F); Tr(D,A,B,C, 1,12, 2,F); Tr(C,D,A,B, 2,17, 3,F); Tr(B,C,D,A, 3,22, 4,F);
Tr(A,B,C,D, 4, 7, 5,F); Tr(D,A,B,C, 5,12, 6,F); Tr(C,D,A,B, 6,17, 7,F); Tr(B,C,D,A, 7,22, 8,F);
Tr(A,B,C,D, 8, 7, 9,F); Tr(D,A,B,C, 9,12,10,F); Tr(C,D,A,B,10,17,11,F); Tr(B,C,D,A,11,22,12,F);
Tr(A,B,C,D,12, 7,13,F); Tr(D,A,B,C,13,12,14,F); Tr(C,D,A,B,14,17,15,F); Tr(B,C,D,A,15,22,16,F);
/* Round 2 */
Tr(A,B,C,D, 1, 5,17,G); Tr(D,A,B,C, 6, 9,18,G); Tr(C,D,A,B,11,14,19,G); Tr(B,C,D,A, 0,20,20,G);
Tr(A,B,C,D, 5, 5,21,G); Tr(D,A,B,C,10, 9,22,G); Tr(C,D,A,B,15,14,23,G); Tr(B,C,D,A, 4,20,24,G);
Tr(A,B,C,D, 9, 5,25,G); Tr(D,A,B,C,14, 9,26,G); Tr(C,D,A,B, 3,14,27,G); Tr(B,C,D,A, 8,20,28,G);
Tr(A,B,C,D,13, 5,29,G); Tr(D,A,B,C, 2, 9,30,G); Tr(C,D,A,B, 7,14,31,G); Tr(B,C,D,A,12,20,32,G);
/* Round 3 */
Tr(A,B,C,D, 5, 4,33,H); Tr(D,A,B,C, 8,11,34,H); Tr(C,D,A,B,11,16,35,H); Tr(B,C,D,A,14,23,36,H);
Tr(A,B,C,D, 1, 4,37,H); Tr(D,A,B,C, 4,11,38,H); Tr(C,D,A,B, 7,16,39,H); Tr(B,C,D,A,10,23,40,H);
Tr(A,B,C,D,13, 4,41,H); Tr(D,A,B,C, 0,11,42,H); Tr(C,D,A,B, 3,16,43,H); Tr(B,C,D,A, 6,23,44,H);
Tr(A,B,C,D, 9, 4,45,H); Tr(D,A,B,C,12,11,46,H); Tr(C,D,A,B,15,16,47,H); Tr(B,C,D,A, 2,23,48,H);
/* Round 4 */
Tr(A,B,C,D, 0, 6,49,I); Tr(D,A,B,C, 7,10,50,I); Tr(C,D,A,B,14,15,51,I); Tr(B,C,D,A, 5,21,52,I);
Tr(A,B,C,D,12, 6,53,I); Tr(D,A,B,C, 3,10,54,I); Tr(C,D,A,B,10,15,55,I); Tr(B,C,D,A, 1,21,56,I);
Tr(A,B,C,D, 8, 6,57,I); Tr(D,A,B,C,15,10,58,I); Tr(C,D,A,B, 6,15,59,I); Tr(B,C,D,A,13,21,60,I);
Tr(A,B,C,D, 4, 6,61,I); Tr(D,A,B,C,11,10,62,I); Tr(C,D,A,B, 2,15,63,I); Tr(B,C,D,A, 9,21,64,I);
/* Final adjustment of registers. */
A += OA; B += OB; C += OC; D += OD;
/* Store output. */
MIRROR(A); memcpy( Digest, &A, sizeof(A));
MIRROR(B); memcpy(&(Digest[ 4]), &B, sizeof(B));
MIRROR(C); memcpy(&(Digest[ 8]), &C, sizeof(C));
MIRROR(D); memcpy(&(Digest[12]), &D, sizeof(D));
/* Burn; earlier registers are more useful in attacks. */
A = B = C = D = 195952365;
/* Ok. */
return 1;
}
/* Encode in a printable manner the raw input data. Return written bytes.
* The number of bytes required is always double the number of input
* bytes.
*
* It's pretty simple-minded encoding, but we're not scraping
* for bytes here. Besides, the only other possibilities are 5 or 6
* bits encoding per byte (instead of 4, as here), which look really
* messy, when implemented, compared to this.
*
* Hell, perhaps sprintf (printing in hex) should be used..
*/
int encode(unsigned char *whEre, BytE *data, int inputbytes)
{
int i, w = 0;
/* This number has to leave the 4 low-end bits free. */
#define ENCODER_OFFSET 96
for(i = 0; i < inputbytes; i++) {
whEre[i*2] = ENCODER_OFFSET + ( data[i] & 0x0f);
whEre[1+(i*2)] = ENCODER_OFFSET + ((data[i] >> 4) & 0x0f);
w += 2;
}
return w;
}
/* Gets raw data from printable string; opposite of encode(). */
void decode(BytE *whEre, BytE *string, int stringbytes)
{
int i;
for(i = 0; i < stringbytes; i+=2)
whEre[i/2] = (string[i] & 0x0f) | ((string[i+1] & 0x0f) << 4);
}
/* If there is a valid salt in the input, copy it. Otherwise,
* generate a new one.
*/
void getsalt(BytE *to, BytE *from)
{
int i;
/* This character seperates the salt encoding from the password encoding
* in the string returned by custom_crypt(). Configurable.
*/
#define MAGIC_SALTSEP '!'
if(from) {
BytE Digest[16];
if(strlen((char *)from) > MD5_SALTLEN * 2) {
if(from[2 * MD5_SALTLEN] == MAGIC_SALTSEP) {
/* It is possible, by a big fluke,
* that this string is not generated by custom_crypt()
* and encode(), and the MAGIC_SALTSEP
* is there by coincedence. That doesn't really
* matter, as long as we get consistently
* the same salt out of here, always. decode()
* takes care of this.
*/
decode(to, from, MD5_SALTLEN * 2);
return;
}
}
/* We have a salt value, but it's not generated by
* this function. Well, suit yourself, we'll /get/ a salt
* out of there.. However, we can't do any straightforward
* copying, because the `salt' is likely to be (also) the
* plain text, to be mashed up. So to generate a salt from
* any string, we digest it first, to avoid people being able
* to pry information from the salt.
*
* It is vital, for fairly obvious reasons, that MD5_VALID_SALT
* is indeed a valid, immediately accepted salt value (as above),
* otherwise we'll end up right here again.
*/
custom_crypt((char *) from, MD5_VALID_SALT, Digest);
memset(to, strlen((char *)from), MD5_SALTLEN);
for(i = 0; i < sizeof(Digest); i++)
to[i % MD5_SALTLEN] += Digest[i];
return;
}
/* We have to generate a random salt. */
for(i = 0; i < MD5_SALTLEN; i++)
to[i] = random_number(256); /* port.c */
return;
}
void crunchbuffer(BytE *buf, /* Buffer to be crunched. */
SIGNED int *len, /* Length now used in buf. */
char *addition, /* What to add to buf. */
SIGNED int addlen, /* Length of addition. */
int maxlen /* How many bytes in buf. */
)
{
int used;
used = *len;
while(addlen > 0) {
BytE Digest[16];
int crunched;
/* Reduce `buf' by digesting it. */
if(used > sizeof(Digest)) {
MD5Digest(buf, used, Digest);
memcpy(buf, Digest, sizeof(Digest));
used = sizeof(Digest);
}
/* Work out how many bytes we can add to `buf', and do it. */
crunched = min((maxlen - used), addlen);
memcpy(&(buf[used]), addition, crunched);
/* Update counters and pointers. */
used += crunched;
addition += crunched;
addlen -= crunched;
}
*len = used;
return;
}
/* Return hash of buffer `key' using salt `salt', which
* must both be null-terminated strings if given.
* - `key' must be given. This is the basic string to be hashed.
* - `salt' is optional. It can be NULL (in which case a random
* salt will be used), it can be output from a previous
* custom_crypt() call (in which case the salt used in that call
* will be used), or it can be any other string, in which case
* a salt derived from that string will be used.
* - `rawout' is optional. If non-NULL, the raw digest value
* (without any salt) is written to that buffer (16 bytes).
*
* At this point, custom_crypt() should never return NULL.
*
*/
char *custom_crypt(char *key, char *salt, unsigned char *rawout)
{
BytE Digest[16];
static BytE buffer[MD5_MAXLEN],
abuffer[MD5_MAXLEN],
thesalt[MD5_SALTLEN];
SIGNED int used = 0, len, i;
static BytE /* encode()d salt, encode()d digest, salt seperator
* and null terminating byte:
*/
ret[(MD5_SALTLEN*2) + 1 + (sizeof(Digest)*2) + 1];
/* Obtain the salt we have to use (either given in salt
* arg or randomly generated one).
*/
getsalt(thesalt, (BytE *)salt);
#define ADDBUFFER(b, l) if(used + (l) > sizeof(buffer)) \
crunchbuffer(buffer, &used, (char *)(b), (l), sizeof(buffer)); \
else { memcpy(&(buffer[used]), (b), (l)); \
used += (l); }
memset(buffer, 0, sizeof(buffer));
/* It's important the 0 byte is copied too. */
len = strlen(key) + 1; ADDBUFFER(key, len);
len = strlen(MD5_MAGIC) + 1; ADDBUFFER(MD5_MAGIC, len);
ADDBUFFER(thesalt, sizeof(thesalt));
memcpy(abuffer, buffer, sizeof(abuffer));
/* The iteration count should be high to thwart
* brute-force guessers. The choice of 3000 is
* fairly arbitrary, but you shouldn't set it much
* lower; but it's configurable.
*
* Here a `digest' value is generated to be included
* in the final to-be-digested buffer, along with the
* actual data.
*
* Make sure to make it length-dependant.
*/
len = strlen(key);
for(i = 3000+(11*len); i > 0; i--) {
if(!MD5Digest(abuffer, sizeof(abuffer), Digest)) return NULL;
memcpy(&(abuffer[(i + len) % (MD5_MAXLEN - sizeof(Digest))]), Digest, sizeof(Digest));
}
ADDBUFFER(Digest, sizeof(Digest));
/* Use this generated buffer to do the actual digesting. */
if(!MD5Digest(buffer, sizeof(buffer), Digest)) return NULL;
/* Pyre! */
memset(buffer, 0, sizeof(buffer));
/* Now code the salt and the digest into the return string. */
len = encode(ret, thesalt, sizeof(thesalt));
ret[len++] = MAGIC_SALTSEP;
len += encode(&(ret[len]), Digest, sizeof(Digest));
ret[len] = 0;
/* Give raw output (without salt info) if requested. */
if(rawout)
memcpy(rawout, Digest, sizeof(Digest));
return (char *)ret;
}
#endif
