/** A local MD4 implementation

 *

 * @note license is LGPL, but largely derived from a public domain source.

 *

 * @file src/lib/util/md4.c

 */

RCSID("$Id: 041a5475b03843098de143e61cca8af5b7bab0e0 $")

#include <freeradius-devel/util/debug.h>

#include <freeradius-devel/util/strerror.h>

#include <freeradius-devel/util/atexit.h>

/*

 *  FORCE MD4 TO USE OUR MD4 HEADER FILE!

 *  If we don't do this, it might pick up the systems broken MD4.

 */

#include <freeradius-devel/util/md4.h>

/** The thread local free list

 *

 * Any entries remaining in the list will be freed when the thread is joined

 */

#define ARRAY_SIZE (8)

typedef struct {

  bool    used;

  fr_md4_ctx_t  *md_ctx;

} fr_md4_free_list_t;

static _Thread_local fr_md4_free_list_t *md4_array;

static void fr_md4_local_ctx_reset(fr_md4_ctx_t *ctx);

static void fr_md4_local_ctx_copy(fr_md4_ctx_t *dst, fr_md4_ctx_t const *src);

static fr_md4_ctx_t *fr_md4_local_ctx_alloc(void);

static void fr_md4_local_ctx_free(fr_md4_ctx_t **ctx);

static void fr_md4_local_update(fr_md4_ctx_t *ctx, uint8_t const *in, size_t inlen);

static void fr_md4_local_final(uint8_t out[static MD4_DIGEST_LENGTH], fr_md4_ctx_t *ctx);

static fr_md4_funcs_t md4_local_funcs = {

  .reset = fr_md4_local_ctx_reset,

  .copy = fr_md4_local_ctx_copy,

  .alloc = fr_md4_local_ctx_alloc,

  .free = fr_md4_local_ctx_free,

  .update = fr_md4_local_update,

  .final = fr_md4_local_final

};

fr_md4_funcs_t const *fr_md4_funcs = &md4_local_funcs;

/*

 *  If we have OpenSSL's EVP API available, then build wrapper functions.

 *

 *  We always need to build the local MD4 functions as OpenSSL could

 *  be operating in FIPS mode where MD4 digest functions are unavailable.

 */

#ifdef HAVE_OPENSSL_EVP_H

#  include <freeradius-devel/tls/openssl_user_macros.h>

#  include <openssl/evp.h>

#  include <openssl/crypto.h>

#  include <openssl/err.h>

#  include <openssl/provider.h>

/** @copydoc fr_md4_ctx_reset

 *

 */

static void fr_md4_openssl_ctx_reset(fr_md4_ctx_t *ctx)

{

  EVP_MD_CTX *md_ctx = ctx;

  EVP_MD_CTX_reset(md_ctx);

  EVP_DigestInit_ex(md_ctx, EVP_md4(), NULL);

}

/** @copydoc fr_md4_ctx_copy

 *

 */

static void fr_md4_openssl_ctx_copy(fr_md4_ctx_t *dst, fr_md4_ctx_t const *src)

{

  EVP_MD_CTX_copy_ex(dst, src);

}

/** @copydoc fr_md4_ctx_alloc

 *

 */

static fr_md4_ctx_t *fr_md4_openssl_ctx_alloc(void)

{

  EVP_MD_CTX *md_ctx;

  md_ctx = EVP_MD_CTX_new();

  if (unlikely(!md_ctx)) return NULL;

  if (EVP_DigestInit_ex(md_ctx, EVP_md4(), NULL) != 1) {

    char buffer[256];

    ERR_error_string_n(ERR_get_error(), buffer, sizeof(buffer));

    fr_strerror_printf("Failed initialising md4 ctx: %s", buffer);

    EVP_MD_CTX_free(md_ctx);

    return NULL;

  }

  return md_ctx;

}

/** @copydoc fr_md4_ctx_free

 *

 */

static void fr_md4_openssl_ctx_free(fr_md4_ctx_t **ctx)

{

  EVP_MD_CTX_free(*ctx);

  *ctx = NULL;

}

/** @copydoc fr_md4_update

 *

 */

static void fr_md4_openssl_update(fr_md4_ctx_t *ctx, uint8_t const *in, size_t inlen)

{

  EVP_DigestUpdate(ctx, in, inlen);

}

/** @copydoc fr_md4_final

 *

 */

static void fr_md4_openssl_final(uint8_t out[static MD4_DIGEST_LENGTH], fr_md4_ctx_t *ctx)

{

  unsigned int len;

  EVP_DigestFinal(ctx, out, &len);

  if (!fr_cond_assert(len == MD4_DIGEST_LENGTH)) return;

}

static fr_md4_funcs_t md4_openssl_funcs = {

  .reset = fr_md4_openssl_ctx_reset,

  .copy = fr_md4_openssl_ctx_copy,

  .alloc = fr_md4_openssl_ctx_alloc,

  .free = fr_md4_openssl_ctx_free,

  .update = fr_md4_openssl_update,

  .final = fr_md4_openssl_final

};

#endif

/*

 * This code implements the MD4 message-digest algorithm.

 * The algorithm is due to Ron Rivest.  This code was

 * written by Colin Plumb in 1993, no copyright is claimed.

 * This code is in the public domain; do with it what you wish.

 * Todd C. Miller modified the md4 code to do MD4 based on RFC 1186.

 *

 * Equivalent code is available from RSA Data Security, Inc.

 * This code has been tested against that, and is equivalent,

 * except that you don't need to include two pages of legalese

 * with every copy.

 *

 * To compute the message digest of a chunk of bytes, declare an

 * MD4Context structure, pass it to fr_md4_init, call fr_md4_update as

 * needed on buffers full of bytes, and then call fr_md4_final, which

 * will fill a supplied 16-byte array with the digest.

 */

#ifndef WORDS_BIGENDIAN

#  define htole32_4(buf)    /* Nothing */

#  define htole32_14(buf)   /* Nothing */

#  define htole32_16(buf)   /* Nothing */

#else

/* Sometimes defined by endian.h */

#  ifndef htole32

#    define htole32(x)\

  (((((uint32_t)x) & 0xff000000) >> 24) |\

  ((((uint32_t)x) & 0x00ff0000) >> 8) |\

  ((((uint32_t)x) & 0x0000ff00) << 8) |\

  ((((uint32_t)x) & 0x000000ff) << 24))

#  endif

#  define htole32_4(buf) do {\

  (buf)[0] = htole32((buf)[0]);\

  (buf)[1] = htole32((buf)[1]);\

  (buf)[2] = htole32((buf)[2]);\

  (buf)[3] = htole32((buf)[3]);\

} while (0)

#  define htole32_14(buf) do {\

  (buf)[0] = htole32((buf)[0]);\

  (buf)[1] = htole32((buf)[1]);\

  (buf)[2] = htole32((buf)[2]);\

  (buf)[3] = htole32((buf)[3]);\

  (buf)[4] = htole32((buf)[4]);\

  (buf)[5] = htole32((buf)[5]);\

  (buf)[6] = htole32((buf)[6]);\

  (buf)[7] = htole32((buf)[7]);\

  (buf)[8] = htole32((buf)[8]);\

  (buf)[9] = htole32((buf)[9]);\

  (buf)[10] = htole32((buf)[10]);\

  (buf)[11] = htole32((buf)[11]);\

  (buf)[12] = htole32((buf)[12]);\

  (buf)[13] = htole32((buf)[13]);\

} while (0)

#  define htole32_16(buf) do {\

  (buf)[0] = htole32((buf)[0]);\

  (buf)[1] = htole32((buf)[1]);\

  (buf)[2] = htole32((buf)[2]);\

  (buf)[3] = htole32((buf)[3]);\

  (buf)[4] = htole32((buf)[4]);\

  (buf)[5] = htole32((buf)[5]);\

  (buf)[6] = htole32((buf)[6]);\

  (buf)[7] = htole32((buf)[7]);\

  (buf)[8] = htole32((buf)[8]);\

  (buf)[9] = htole32((buf)[9]);\

  (buf)[10] = htole32((buf)[10]);\

  (buf)[11] = htole32((buf)[11]);\

  (buf)[12] = htole32((buf)[12]);\

  (buf)[13] = htole32((buf)[13]);\

  (buf)[14] = htole32((buf)[14]);\

  (buf)[15] = htole32((buf)[15]);\

} while (0)

#endif

#define MD4_BLOCK_LENGTH 64

/* The three core functions - F1 is optimized somewhat */

#define MD4_F1(x, y, z) (z ^ (x & (y ^ z)))

#define MD4_F2(x, y, z) ((x & y) | (x & z) | (y & z))

#define MD4_F3(x, y, z) (x ^ y ^ z)

/* This is the central step in the MD4 algorithm. */

#define MD4STEP(f, w, x, y, z, data, s) (w += f(x, y, z) + data, w = w << s | w >> (32 - s))

/** The core of the MD4 algorithm

 *

 * This alters an existing MD4 hash to reflect the addition of 16

 * longwords of new data.  fr_md4_update blocks the data and converts bytes

 * into longwords for this routine.

 *

 * @param[in] state 16 bytes of data to feed into the hashing function.

 * @param[in,out] block MD4 digest block to update.

 */

static void fr_md4_local_transform(uint32_t state[static 4], uint8_t const block[static MD4_BLOCK_LENGTH])

{

  uint32_t a, b, c, d;

  uint32_t const *in = (uint32_t const *)block;

  a = state[0];

  b = state[1];

  c = state[2];

  d = state[3];

  MD4STEP(MD4_F1, a, b, c, d, in[ 0],  3);

  MD4STEP(MD4_F1, d, a, b, c, in[ 1],  7);

  MD4STEP(MD4_F1, c, d, a, b, in[ 2], 11);

  MD4STEP(MD4_F1, b, c, d, a, in[ 3], 19);

  MD4STEP(MD4_F1, a, b, c, d, in[ 4],  3);

  MD4STEP(MD4_F1, d, a, b, c, in[ 5],  7);

  MD4STEP(MD4_F1, c, d, a, b, in[ 6], 11);

  MD4STEP(MD4_F1, b, c, d, a, in[ 7], 19);

  MD4STEP(MD4_F1, a, b, c, d, in[ 8],  3);

  MD4STEP(MD4_F1, d, a, b, c, in[ 9],  7);

  MD4STEP(MD4_F1, c, d, a, b, in[10], 11);

  MD4STEP(MD4_F1, b, c, d, a, in[11], 19);

  MD4STEP(MD4_F1, a, b, c, d, in[12],  3);

  MD4STEP(MD4_F1, d, a, b, c, in[13],  7);

  MD4STEP(MD4_F1, c, d, a, b, in[14], 11);

  MD4STEP(MD4_F1, b, c, d, a, in[15], 19);

  MD4STEP(MD4_F2, a, b, c, d, in[ 0] + 0x5a827999,  3);

  MD4STEP(MD4_F2, d, a, b, c, in[ 4] + 0x5a827999,  5);

  MD4STEP(MD4_F2, c, d, a, b, in[ 8] + 0x5a827999,  9);

  MD4STEP(MD4_F2, b, c, d, a, in[12] + 0x5a827999, 13);

  MD4STEP(MD4_F2, a, b, c, d, in[ 1] + 0x5a827999,  3);

  MD4STEP(MD4_F2, d, a, b, c, in[ 5] + 0x5a827999,  5);

  MD4STEP(MD4_F2, c, d, a, b, in[ 9] + 0x5a827999,  9);

  MD4STEP(MD4_F2, b, c, d, a, in[13] + 0x5a827999, 13);

  MD4STEP(MD4_F2, a, b, c, d, in[ 2] + 0x5a827999,  3);

  MD4STEP(MD4_F2, d, a, b, c, in[ 6] + 0x5a827999,  5);

  MD4STEP(MD4_F2, c, d, a, b, in[10] + 0x5a827999,  9);

  MD4STEP(MD4_F2, b, c, d, a, in[14] + 0x5a827999, 13);

  MD4STEP(MD4_F2, a, b, c, d, in[ 3] + 0x5a827999,  3);

  MD4STEP(MD4_F2, d, a, b, c, in[ 7] + 0x5a827999,  5);

  MD4STEP(MD4_F2, c, d, a, b, in[11] + 0x5a827999,  9);

  MD4STEP(MD4_F2, b, c, d, a, in[15] + 0x5a827999, 13);

  MD4STEP(MD4_F3, a, b, c, d, in[ 0] + 0x6ed9eba1,  3);

  MD4STEP(MD4_F3, d, a, b, c, in[ 8] + 0x6ed9eba1,  9);

  MD4STEP(MD4_F3, c, d, a, b, in[ 4] + 0x6ed9eba1, 11);

  MD4STEP(MD4_F3, b, c, d, a, in[12] + 0x6ed9eba1, 15);

  MD4STEP(MD4_F3, a, b, c, d, in[ 2] + 0x6ed9eba1,  3);

  MD4STEP(MD4_F3, d, a, b, c, in[10] + 0x6ed9eba1,  9);

  MD4STEP(MD4_F3, c, d, a, b, in[ 6] + 0x6ed9eba1, 11);

  MD4STEP(MD4_F3, b, c, d, a, in[14] + 0x6ed9eba1, 15);

  MD4STEP(MD4_F3, a, b, c, d, in[ 1] + 0x6ed9eba1,  3);

  MD4STEP(MD4_F3, d, a, b, c, in[ 9] + 0x6ed9eba1,  9);

  MD4STEP(MD4_F3, c, d, a, b, in[ 5] + 0x6ed9eba1, 11);

  MD4STEP(MD4_F3, b, c, d, a, in[13] + 0x6ed9eba1, 15);

  MD4STEP(MD4_F3, a, b, c, d, in[ 3] + 0x6ed9eba1,  3);

  MD4STEP(MD4_F3, d, a, b, c, in[11] + 0x6ed9eba1,  9);

  MD4STEP(MD4_F3, c, d, a, b, in[ 7] + 0x6ed9eba1, 11);

  MD4STEP(MD4_F3, b, c, d, a, in[15] + 0x6ed9eba1, 15);

  state[0] += a;

  state[1] += b;

  state[2] += c;

  state[3] += d;

}

typedef struct {

  uint32_t state[4];      //!< State.

  uint32_t count[2];      //!< Number of bits, mod 2^64.

  uint8_t buffer[MD4_BLOCK_LENGTH]; //!< Input buffer.

} fr_md4_ctx_local_t;

/** @copydoc fr_md4_ctx_reset

 *

 */

static void fr_md4_local_ctx_reset(fr_md4_ctx_t *ctx)

{

  fr_md4_ctx_local_t  *ctx_local = talloc_get_type_abort(ctx, fr_md4_ctx_local_t);

  ctx_local->count[0] = 0;

  ctx_local->count[1] = 0;

  ctx_local->state[0] = 0x67452301;

  ctx_local->state[1] = 0xefcdab89;

  ctx_local->state[2] = 0x98badcfe;

  ctx_local->state[3] = 0x10325476;

}

/** @copydoc fr_md4_ctx_copy

 *

 */

static void fr_md4_local_ctx_copy(fr_md4_ctx_t *dst, fr_md4_ctx_t const *src)

{

  fr_md4_ctx_local_t const *ctx_local_src = talloc_get_type_abort_const(src, fr_md4_ctx_local_t);

  fr_md4_ctx_local_t *ctx_local_dst = talloc_get_type_abort(dst, fr_md4_ctx_local_t);

  memcpy(ctx_local_dst, ctx_local_src, sizeof(*ctx_local_dst));

}

/** @copydoc fr_md4_ctx_alloc

 *

 */

static fr_md4_ctx_t *fr_md4_local_ctx_alloc(void)

{

  fr_md4_ctx_local_t *ctx_local;

  ctx_local = talloc(NULL, fr_md4_ctx_local_t);

  if (unlikely(!ctx_local)) return NULL;

  fr_md4_local_ctx_reset(ctx_local);

  return ctx_local;

}

/** @copydoc fr_md4_ctx_free

 *

 */

static void fr_md4_local_ctx_free(fr_md4_ctx_t **ctx)

{

  talloc_free(*ctx);

  *ctx = NULL;

}

static const uint8_t *zero = (uint8_t[]){ 0x00 };

/** @copydoc fr_md4_update

 *

 */

static void fr_md4_local_update(fr_md4_ctx_t *ctx, uint8_t const *in, size_t inlen)

{

  uint32_t    count;

  fr_md4_ctx_local_t  *ctx_local = talloc_get_type_abort(ctx, fr_md4_ctx_local_t);

  /*

   *  Needed so we can calculate the zero

   *  length md4 hash correctly.

   *  ubsan doesn't like arithmetic on

   *  NULL pointers.

   */

  if (!in) {

    in = zero;

    inlen = 0;

  }

  /* Bytes already stored in ctx_local->buffer */

  count = (uint32_t)((ctx_local->count[0] >> 3) & 0x3f);

  /* Update bitcount */

/*  ctx_local->count += (uint64_t)inlen << 3;*/

  if ((ctx_local->count[0] += ((uint32_t)inlen << 3)) < (uint32_t)inlen) {

    /* Overflowed ctx_local->count[0] */

    ctx_local->count[1]++;

  }

  ctx_local->count[1] += ((uint32_t)inlen >> 29);

  /* Handle any leading odd-sized chunks */

  if (count) {

    unsigned char *p = (unsigned char *)ctx_local->buffer + count;

    count = MD4_BLOCK_LENGTH - count;

    if (inlen < count) {

      memcpy(p, in, inlen);

      return;

    }

    memcpy(p, in, count);

    htole32_16((uint32_t *)ctx_local->buffer);

    fr_md4_local_transform(ctx_local->state, ctx_local->buffer);

    in += count;

    inlen -= count;

  }

  /* Process data in MD4_BLOCK_LENGTH-byte chunks */

  while (inlen >= MD4_BLOCK_LENGTH) {

    memcpy(ctx_local->buffer, in, MD4_BLOCK_LENGTH);

    htole32_16((uint32_t *)ctx_local->buffer);

    fr_md4_local_transform(ctx_local->state, ctx_local->buffer);

    in += MD4_BLOCK_LENGTH;

    inlen -= MD4_BLOCK_LENGTH;

  }

  /* Handle any remaining bytes of data. */

  memcpy(ctx_local->buffer, in, inlen);

}

/** @copydoc fr_md4_final

 *

 */

static void fr_md4_local_final(uint8_t out[static MD4_DIGEST_LENGTH], fr_md4_ctx_t *ctx)

{

  uint32_t    count;

  unsigned char   *p;

  fr_md4_ctx_local_t  *ctx_local = talloc_get_type_abort(ctx, fr_md4_ctx_local_t);

  /* number of bytes mod 64 */

  count = (uint32_t)(ctx_local->count[0] >> 3) & 0x3f;

  /*

   * Set the first char of padding to 0x80.

   * This is safe since there is always at least one byte free.

   */

  p = ctx_local->buffer + count;

  *p++ = 0x80;

  /* Bytes of padding needed to make 64 bytes */

  count = 64 - 1 - count;

  /* Pad out to 56 mod 64 */

  if (count < 8) {

    /* Two lots of padding:  Pad the first block to 64 bytes */

    memset(p, 0, count);

    htole32_16((uint32_t *)ctx_local->buffer);

    fr_md4_local_transform(ctx_local->state, ctx_local->buffer);

    /* Now fill the next block with 56 bytes */

    memset(ctx_local->buffer, 0, 56);

  } else {

    /* Pad block to 56 bytes */

    memset(p, 0, count - 8);

  }

  htole32_14((uint32_t *)ctx_local->buffer);

  /* Append bit count and transform */

  ((uint32_t *)ctx_local->buffer)[14] = ctx_local->count[0];

  ((uint32_t *)ctx_local->buffer)[15] = ctx_local->count[1];

  fr_md4_local_transform(ctx_local->state, ctx_local->buffer);

  htole32_4(ctx_local->state);

  memcpy(out, ctx_local->state, MD4_DIGEST_LENGTH);

  memset(ctx_local, 0, sizeof(*ctx_local)); /* in case it's sensitive */

}

/** Calculate the MD4 hash of the contents of a buffer

 *

 * @param[out] out Where to write the MD4 digest. Must be a minimum of MD4_DIGEST_LENGTH.

 * @param[in] in Data to hash.

 * @param[in] inlen Length of the data.

 */

void fr_md4_calc(uint8_t out[static MD4_DIGEST_LENGTH], uint8_t const *in, size_t inlen)

{

  fr_md4_ctx_t *ctx;

  ctx = fr_md4_ctx_alloc_from_list();

  fr_md4_update(ctx, in, inlen);

  fr_md4_final(out, ctx);

  fr_md4_ctx_free_from_list(&ctx);

}

static int _md4_ctx_free_on_exit(void *arg)

{

  int i;

  fr_md4_free_list_t *free_list = arg;

  for (i = 0; i < ARRAY_SIZE; i++) {

    if (free_list[i].used) continue;

    fr_md4_ctx_free(&free_list[i].md_ctx);

  }

  return talloc_free(free_list);

}

/** @copydoc fr_md4_ctx_alloc

 *

 */

fr_md4_ctx_t *fr_md4_ctx_alloc_from_list(void)

{

  int     i;

  fr_md4_ctx_t    *md_ctx;

  fr_md4_free_list_t  *free_list;

  if (unlikely(!md4_array)) {

    free_list = talloc_zero_array(NULL, fr_md4_free_list_t, ARRAY_SIZE);

    if (unlikely(!free_list)) {

    oom:

      fr_strerror_const("Out of Memory");

      return NULL;

    }

    fr_atexit_thread_local(md4_array, _md4_ctx_free_on_exit, free_list);

    /*

     *  Initialize all md4 contexts

     */

    for (i = 0; i < ARRAY_SIZE; i++) {

      md_ctx = fr_md4_ctx_alloc();

      if (unlikely(md_ctx == NULL)) goto oom;

      free_list[i].md_ctx = md_ctx;

    }

  } else {

    free_list = md4_array;

  }

  for (i = 0; i < ARRAY_SIZE; i++) {

    if (free_list[i].used) continue;

    free_list[i].used = true;

    return free_list[i].md_ctx;

  }

  /*

   *  No more free contexts, just allocate a new one.

   */

  return fr_md4_ctx_alloc();

}

/** @copydoc fr_md4_ctx_free

 *

 */

void fr_md4_ctx_free_from_list(fr_md4_ctx_t **ctx)

{

  int i;

  fr_md4_free_list_t *free_list = md4_array;

  if (free_list) {

    for (i = 0; i < ARRAY_SIZE; i++) {

      if (free_list[i].md_ctx == *ctx) {

        free_list[i].used = false;

        fr_md4_ctx_reset(*ctx);

        *ctx = NULL;

        return;

      }

    }

  }

  fr_md4_ctx_free(*ctx);

  *ctx = NULL;

}

#ifdef HAVE_OPENSSL_EVP_H

void fr_md4_openssl_init(void)

{

  /*

   *  If we are in FIPS mode, then we still use the local

   *  allocator.

   */

  if (!EVP_default_properties_is_fips_enabled(NULL)) return;

  /*

   *  OpenSSL isn't in FIPS mode.  Swap out the functions

   *  pointers for the OpenSSL versions.

   *

   *  We do this by swapping out a pointer to a structure

   *  containing the functions, as this prevents possible

   *  skew where some threads see a mixture of functions.

   */

  fr_md4_funcs = &md4_openssl_funcs;

}

void fr_md4_openssl_free(void)

{

  fr_md4_funcs = &md4_local_funcs;

}

#endif