tmmhv2.c

srtp-1.3.20 security RTP source

/*
 * tmmhv2.c
 *
 * tmmhv2 is the mmh hash function, with authenticated truncation,
 * version two
 *
 * David A. McGrew
 * Cisco Systems, Inc.
 *
 */

/*
 *	
 * Copyright (c) 2001-2004, Cisco Systems, Inc.
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 *   Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * 
 *   Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following
 *   disclaimer in the documentation and/or other materials provided
 *   with the distribution.
 * 
 *   Neither the name of the Cisco Systems, Inc. nor the names of its
 *   contributors may be used to endorse or promote products derived
 *   from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */


#include <stdlib.h>      /* for xalloc()            */
#include "auth.h"
#include "tmmhv2.h"
#include "alloc.h"

#define DEBUG_VERBOSE 0 /* set to 1 for lots of debugging output */

/* the debug module for tmmhv2 */

debug_module_t mod_tmmhv2 = {
  0,                  /* debugging is off by default */
  "ust tmmh v2"       /* printable name for module   */
};


err_status_t
tmmhv2_alloc(auth_t **a, int key_len, int out_len) {
  extern auth_type_t tmmhv2;
  int tmp;
  octet_t *pointer;
  tmmhv2_ctx_t *tmmh_state;
  
  debug_print(mod_tmmhv2, "allocating auth func with key length %d", key_len);
  debug_print(mod_tmmhv2, "                          tag length %d", out_len);

  /* check parameters */
  if ((key_len & 1) || (key_len != (70 + 6 * out_len))) {
    *a = NULL;                     /* indicate alloc failure */             
    return err_status_bad_param;
  }
  
  /*
   * allocate memory for an auth func of type tmmhv2
   *
   * note that there are 70 + 6 * out_len octets of key
   */
  tmp = (sizeof(tmmhv2_ctx_t) + sizeof(auth_t) + (70 + 6 * out_len));
  pointer = xalloc(tmp);
  *a = (auth_t *)pointer;
  if (*a == NULL) 
    return err_status_alloc_fail;


  /* set pointers and parameters */

  /*
   * format:
   *
   *  +--------+--------------+--------------+
   *  | auth_t | tmmhv2_ctx_t |    value     |
   *  +--------+--------------+--------------+
   *
   */
  tmmh_state    = (tmmhv2_ctx_t *) (pointer + sizeof(auth_t));
  (*a)->type    = &tmmhv2;
  (*a)->state   = tmmh_state;
  (*a)->out_len = out_len;
  (*a)->prefix_len = out_len;
  (*a)->key_len = key_len;
  tmmh_state->value = (uint16_t *)
    (pointer + sizeof(auth_t) + sizeof(tmmhv2_ctx_t));
  
  /* increment ref_count */
  tmmhv2.ref_count++;

  return err_status_ok;  
}

err_status_t
tmmhv2_dealloc(auth_t *a) {
  extern auth_type_t tmmhv2;

  /* zeroize entire state*/
  octet_string_set_to_zero((octet_t *)a, 
			   sizeof(tmmhv2_ctx_t) + sizeof(auth_t) 
			   + 70 + 6 * a->out_len);

  /* deallocate memory */
  xfree(a);

  /* decrement ref count */
  tmmhv2.ref_count--;

  return err_status_ok;
}

err_status_t
tmmhv2_init(tmmhv2_ctx_t *state, const octet_t *key, int key_len) {
  int i;
  uint16_t *key_ptr = (uint16_t *)key;
    
  /* copy key and convert into host byte order */
  for (i=0; i < key_len/2; i++) {
    state->value[i] = ntohs(*key_ptr);
    key_ptr++;
  }

  return err_status_ok;
}


/*
 * tmmhv2_compute_4 computes TMMH v.2 with four-octet tags
 * (e.g. TAG_WORDS = 2)
 */

#define SUBKEY_LEN (7 + TAG_WORDS)     /* words in a subkey          */

#define TAG_WORDS 2                    /* number of words in a tag   */

typedef uint16_t subkey[7+TAG_WORDS];  /* subkey; used at each level */

/*  
 *   The value TMMH_BUF_WORDS determines the size of the largest
 *   message that can be hashed.  In order to make this the maximum
 *   possible, this value should be set to 32768.
 */

#define TMMH_BUF_WORDS 32768           /* words in temporary buffer */

err_status_t
tmmhv2_update(tmmhv2_ctx_t *state, octet_t *message,
	       int msg_octets) {

  /*
   *  this function not yet supported for tmmhv2
   */

  return err_status_no_such_op;
}

err_status_t
tmmhv2_start(tmmhv2_ctx_t *state) {

  /*
   *  this function not yet supported for tmmhv2
   */

  return err_status_no_such_op;
}

err_status_t
tmmhv2_compute(tmmhv2_ctx_t *state, octet_t *message,
	       int msg_octets, int tag_len, octet_t *result) {
  int j;
  uint16_t *L;                          /* length multiplier list      */
  subkey *S;                            /* subkey list                 */
  uint16_t*keypointer;                  /* points into key             */  
  uint16_t buffer[TMMH_BUF_WORDS];      /* temporary buffer            */
  uint16_t *subkey;                     /* points to a subkey          */
  uint16_t tmp;                         /* used to align output        */
  uint32_t sum;
  int msg_len;
  const uint16_t *msg = (uint16_t*)message;
  int i;
  int len_octets;

  /* check tag length, return error if we can't provide the value expected */
  if (tag_len != 4)
    return err_status_bad_param;
  
  /* set L and S from key */
  keypointer = (uint16_t *)state->value;
  L = keypointer;
  S = (void *)(keypointer + TAG_WORDS);

#if DEBUG_VERBOSE /* define this if you want lots of output */
  /* print out L and S for sanity check */
  debug_print(mod_tmmhv2, "L: { ", NULL);
  for (i=0; i < TAG_WORDS; i++)
    debug_print(mod_tmmhv2, "%x ", L[i]);
  debug_print(mod_tmmhv2, "}\n", NULL);
  for (j=0; j < 5; j++) {
    debug_print(mod_tmmhv2, "S[%d]: {", j);
    for (i=0; i < (7 + TAG_WORDS); i++) 
      debug_print(mod_tmmhv2, "%x ", S[j][i]);
    debug_print(mod_tmmhv2, "}\n", NULL);
  }

  /* print out msg, for use in manual check of computations */
  debug_print(mod_tmmhv2, "msg octets: %d\n", msg_octets);
  debug_print(mod_tmmhv2, "msg: %s\n", 
	      octet_string_hex_string(message, msg_octets));
#endif 

  /* compute the first word of the tag */

  /* compute first level, compressing msg info buffer */
  msg = (uint16_t*)message;
  len_octets = msg_octets;
  j = 0;       /* set j to zero; it points into the temp buffer */
  subkey = keypointer + TAG_WORDS;
  while (len_octets >= 16) {
  
    /* multiply and acuumulate next eight words */
    sum =  (uint32_t) subkey[0] * ntohs(*msg); msg++;
    sum += (uint32_t) subkey[1] * ntohs(*msg); msg++;
    sum += (uint32_t) subkey[2] * ntohs(*msg); msg++;
    sum += (uint32_t) subkey[3] * ntohs(*msg); msg++;
    sum += (uint32_t) subkey[4] * ntohs(*msg); msg++;
    sum += (uint32_t) subkey[5] * ntohs(*msg); msg++;
    sum += (uint32_t) subkey[6] * ntohs(*msg); msg++;
    sum += (uint32_t) subkey[7] * ntohs(*msg); msg++;
    
    /* reduce and set next-level value */
    buffer[j++] = (uint16_t) (sum % tmmh_16_prime);
    
    len_octets -= 16;  
  }

  /*
   * if len_octets isn't zero, then multiply and accumulate remaining
   * (len_octets+1)/2 words, masking the last octet of the last word
   * to avoid including it in the message
   */
  if (len_octets) {
    sum = 0;
    for (i=0; i < (len_octets/2); i++) {
      sum += (uint32_t) subkey[i] * ntohs(msg[i]);
    }

    /*  handle odd-octet-length message case  */
    if (msg_octets & 1) {   
      sum += (uint32_t) subkey[i] * (ntohs(msg[i]) & 0xff00); 
    }

    /* set next-level value */
    buffer[j++] = (uint16_t) (sum % tmmh_16_prime);  
  }

  msg_len = j;    /* set msg_len to number of words in buffer */

  /* 
   * now loop over upper levels, compressing buffer into buffer 
   * 
   * note that endian-ness no longer matters, since the data in the
   * buffer is already in host-order
   */

  while (msg_len > 1) {
    j = 0;                             /* reset j to zero          */
    subkey += SUBKEY_LEN;              /* increment level          */

#if DEBUG_VERBOSE /* define this if you want lots of output */
    debug_print(mod_tmmhv2, "computing next level (tag one)\n");
#endif

    msg = buffer;                      /* set hash-start to buffer */
    while (msg_len >= 8) {
      
      /* multiply and acuumulate next eight words */
      sum =  (uint32_t) subkey[0] * *msg++;
      sum += (uint32_t) subkey[1] * *msg++;
      sum += (uint32_t) subkey[2] * *msg++;
      sum += (uint32_t) subkey[3] * *msg++;
      sum += (uint32_t) subkey[4] * *msg++;
      sum += (uint32_t) subkey[5] * *msg++;
      sum += (uint32_t) subkey[6] * *msg++;
      sum += (uint32_t) subkey[7] * *msg++;
      
      /* reduce and set next-level value */
      buffer[j++] = (uint16_t) (sum % tmmh_16_prime);     
      msg_len -= 8;  
    }

    /* multiply and accumulate remaining msg_len words */
    sum = 0;
    switch (msg_len) {
    case (7):
      sum += (uint32_t) subkey[6] * msg[6];
    case (6):			       
      sum += (uint32_t) subkey[5] * msg[5];
    case (5):			       
      sum += (uint32_t) subkey[4] * msg[4];
    case (4):			       
      sum += (uint32_t) subkey[3] * msg[3];
    case (3):			       
      sum += (uint32_t) subkey[2] * msg[2];
    case (2):			       
      sum += (uint32_t) subkey[1] * msg[1];
    case (1):			       
      sum += (uint32_t) subkey[0] * msg[0];
      buffer[j++] = (uint16_t) (sum % tmmh_16_prime);
    default:
      break;                             /* defensive coding */
    }
    msg_len = j;         /* set to number of words in buffer */

#if DEBUG_VERBOSE /* define this for lots of debugging output */
    debug_print(mod_tmmhv2, "buffer: %d\tsum: %x\n", buffer[0], sum);
    debug_print(mod_tmmhv2, "remaining message length: %d\n", msg_len);
#endif
  }

  /* multiply and accumulate message length */
  sum = (uint32_t) buffer[0] + (uint32_t) L[0] * msg_octets;

  /* reduce, then this is the final output */
  /* don't assume any alignment for octet_t *result */
  tmp = (((uint16_t) result[0]) << 8) & ((uint16_t) result[1]);
  tmp += (uint16_t) (sum % tmmh_16_prime);
  result[0] = (octet_t) (tmp >> 8);
  result[1] = (octet_t) tmp;

  /*
   *  now compute second word of tag 
   */  

#if DEBUG_VERBOSE /* define this for lots of debugging output */
  debug_print(mod_tmmhv2, "computing tag two\n");