Subversion Repositories bluespec_md6

/* File:    md6_compress.c

** Author:  Ronald L. Rivest

**          (with optimizations by Jayant Krishnamurthy)

** Address: Room 32G-692 Stata Center

**          32 Vassar Street

**          Cambridge, MA 02139

** Email:   rivest@mit.edu

** Date:    9/25/2008

**

** (The following license is known as "The MIT License")

**

** Copyright (c) 2008 Ronald L. Rivest and Jayant Krishnamurthy

**

** Permission is hereby granted, free of charge, to any person obtaining a copy

** of this software and associated documentation files (the "Software"), to deal

** in the Software without restriction, including without limitation the rights

** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

** copies of the Software, and to permit persons to whom the Software is

** furnished to do so, subject to the following conditions:

**

** The above copyright notice and this permission notice shall be included in

** all copies or substantial portions of the Software.

**

** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

** AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

** LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

** OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

** THE SOFTWARE.

**

** (end of license)

**

** This is part of the definition of the MD6 hash function.

** The files defining the md6 hash function are:

**    md6.h

**    md6_compress.c

**    md6_mode.c

**

** The files defining the interface between MD6 and the NIST SHA-3

** API are:

**    md6_nist.h

**    md6_nist.c

** The NIST SHA-3 API is defined in:

**    http://www.csrc.nist.gov/groups/ST/hash/documents/SHA3-C-API.pdf

**

** See  http://groups.csail.mit.edu/cis/md6  for more information.

**

*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "md6.h"

/* Useful macros: min and max */

#ifndef min

#define min(a,b) ((a)<(b)? (a) : (b))

#endif

#ifndef max

#define max(a,b) ((a)>(b)? (a) : (b))

#endif

/* Variables defining lengths of various values */

#define   w   md6_w  /* # bits in a word (64) */

#define   n   md6_n  /* # words in compression input (89) */

#define   c   md6_c  /* # words in compression output (16) */

#define   b   md6_b  /* # message words per compression input block (64) */

#define   v   md6_v  /* # words in control word (1) */

#define   u   md6_u  /* # words in unique nodeID (1) */

#define   k   md6_k  /* # key words per compression input block (8) */

#define   q   md6_q  /* # Q words per compression input block (15) */

/* "Tap positions" for feedback shift-register */

#if (n==89)

#define  t0   17     /* index for linear feedback */

#define  t1   18     /* index for first input to first and */

#define  t2   21     /* index for second input to first and */

#define  t3   31     /* index for first input to second and */

#define  t4   67     /* index for second input to second and */

#define  t5   89     /* last tap */

#endif

/* Loop-unrolling setup.

**

** Define macros for loop-unrolling within compression function

** These expand to:     loop_body(right-shift,left-shift,step)

** These are given for word sizes 64, 32, 16, and 8, although

** only w=64 is needed for the standard MD6 definition.

**

** Also given for each word size are the constants S0 and Smask

** needed in the recurrence for round constants.

*/

#if (w==64)                        /* for standard word size */

#define RL00 loop_body(10,11, 0)

#define RL01 loop_body( 5,24, 1)

#define RL02 loop_body(13, 9, 2)

#define RL03 loop_body(10,16, 3)

#define RL04 loop_body(11,15, 4)

#define RL05 loop_body(12, 9, 5)

#define RL06 loop_body( 2,27, 6)

#define RL07 loop_body( 7,15, 7)

#define RL08 loop_body(14, 6, 8)

#define RL09 loop_body(15, 2, 9)

#define RL10 loop_body( 7,29,10)

#define RL11 loop_body(13, 8,11)

#define RL12 loop_body(11,15,12)

#define RL13 loop_body( 7, 5,13)

#define RL14 loop_body( 6,31,14)

#define RL15 loop_body(12, 9,15)

const md6_word S0 = (md6_word)0x0123456789abcdefULL;

const md6_word Smask = (md6_word)0x7311c2812425cfa0ULL;

#elif (w==32)                      /* for variant word size */

#define RL00 loop_body( 5, 4, 0)

#define RL01 loop_body( 3, 7, 1)

#define RL02 loop_body( 6, 7, 2)

#define RL03 loop_body( 5, 9, 3)

#define RL04 loop_body( 4,13, 4)

#define RL05 loop_body( 6, 8, 5)

#define RL06 loop_body( 7, 4, 6)

#define RL07 loop_body( 3,14, 7)

#define RL08 loop_body( 5, 7, 8)

#define RL09 loop_body( 6, 4, 9)

#define RL10 loop_body( 5, 8,10)

#define RL11 loop_body( 5,11,11)

#define RL12 loop_body( 4, 5,12)

#define RL13 loop_body( 6, 8,13)

#define RL14 loop_body( 7, 2,14)

#define RL15 loop_body( 5,11,15)

const md6_word S0 = (md6_word)0x01234567UL;

const md6_word Smask = (md6_word)0x7311c281UL;

/* Loop-unrolling setup (continued).

**

*/

#elif (w==16)                      /* for variant word size */

#define RL00 loop_body( 5, 6, 0)

#define RL01 loop_body( 4, 7, 1)

#define RL02 loop_body( 3, 2, 2)

#define RL03 loop_body( 5, 4, 3)

#define RL04 loop_body( 7, 2, 4)

#define RL05 loop_body( 5, 6, 5)

#define RL06 loop_body( 5, 3, 6)

#define RL07 loop_body( 2, 7, 7)

#define RL08 loop_body( 4, 5, 8)

#define RL09 loop_body( 3, 7, 9)

#define RL10 loop_body( 4, 6,10)

#define RL11 loop_body( 3, 5,11)

#define RL12 loop_body( 4, 5,12)

#define RL13 loop_body( 7, 6,13)

#define RL14 loop_body( 7, 4,14)

#define RL15 loop_body( 2, 3,15)

const md6_word S0 = (md6_word)0x01234;

const md6_word Smask = (md6_word)0x7311;

#elif (w==8)                     /* for variant word size */

#define RL00 loop_body( 3, 2, 0)

#define RL01 loop_body( 3, 4, 1)

#define RL02 loop_body( 3, 2, 2)

#define RL03 loop_body( 4, 3, 3)

#define RL04 loop_body( 3, 2, 4)

#define RL05 loop_body( 3, 2, 5)

#define RL06 loop_body( 3, 2, 6)

#define RL07 loop_body( 3, 4, 7)

#define RL08 loop_body( 2, 3, 8)

#define RL09 loop_body( 2, 3, 9)

#define RL10 loop_body( 3, 2,10)

#define RL11 loop_body( 2, 3,11)

#define RL12 loop_body( 2, 3,12)

#define RL13 loop_body( 3, 4,13)

#define RL14 loop_body( 2, 3,14)

#define RL15 loop_body( 3, 4,15)

const md6_word S0 = (md6_word)0x01;

const md6_word Smask = (md6_word)0x73;

#endif

/* Main compression loop.

**

*/

void md6_main_compression_loop( md6_word* A , int r )

/*

** Perform the md6 "main compression loop" on the array A.

** This is where most of the computation occurs; it is the "heart"

** of the md6 compression algorithm.

** Input:

**     A                  input array of length t+n already set up

**                        with input in the first n words.

**     r                  number of rounds to run (178); each is c steps

** Modifies:

**     A                  A[n..r*c+n-1] filled in.

*/

{ md6_word x, S;

  int i,j;

  /*

  ** main computation loop for md6 compression

  */

  S = S0;

  for (j = 0, i = n; j<r*c; j+=c)

    {

/* ***************************************************************** */

#define loop_body(rs,ls,step)                                       \

      x = S;                                /* feedback constant     */ \

      x ^= A[i+step-t5];                    /* end-around feedback   */ \

      x ^= A[i+step-t0];                    /* linear feedback       */ \

      x ^= ( A[i+step-t1] & A[i+step-t2] ); /* first quadratic term  */ \

      x ^= ( A[i+step-t3] & A[i+step-t4] ); /* second quadratic term */ \

      x ^= (x >> rs);                       /* right-shift           */ \

      A[i+step] = x ^ (x << ls);            /* left-shift            */

/* ***************************************************************** */

      /*

      ** Unroll loop c=16 times. (One "round" of computation.)

      ** Shift amounts are embedded in macros RLnn.

      */

      RL00 RL01 RL02 RL03 RL04 RL05 RL06 RL07

      RL08 RL09 RL10 RL11 RL12 RL13 RL14 RL15

      /* Advance round constant S to the next round constant. */

      S = (S << 1) ^ (S >> (w-1)) ^ (S & Smask);

      i += 16;

    }

}

/* ``Bare'' compression routine.

**

** Compresses n-word input to c-word output.

*/

int md6_compress( md6_word *C,

                  md6_word *N,

                  int r,

                  md6_word *A

                 )

/* Assumes n-word input array N has been fully set up.

** Input:

**   N               input array of n w-bit words (n=89)

**   A               working array of a = rc+n w-bit words

**                   A is OPTIONAL, may be given as NULL

**                   (then md6_compress allocates and uses its own A).

**   r               number of rounds

** Modifies:

**   C               output array of c w-bit words (c=16)

** Returns one of the following:

**   MD6_SUCCESS (0)

**   MD6_NULL_N

**   MD6_NULL_C

**   MD6_BAD_r

**   MD6_OUT_OF_MEMORY

*/

{ md6_word* A_as_given = A;

  /* check that input is sensible */

  if ( N == NULL) return MD6_NULL_N;

  if ( C == NULL) return MD6_NULL_C;

  if ( r<0 || r > md6_max_r) return MD6_BAD_r;

  if ( A == NULL) A = calloc(r*c+n,sizeof(md6_word));

  if ( A == NULL) return MD6_OUT_OF_MEMORY;

  memcpy( A, N, n*sizeof(md6_word) );    /* copy N to front of A */

  md6_main_compression_loop( A, r );          /* do all the work */

  memcpy( C, A+(r-1)*c+n, c*sizeof(md6_word) ); /* output into C */

  if ( A_as_given == NULL )           /* zero and free A if nec. */

    { memset(A,0,(r*c+n)*sizeof(md6_word)); /* contains key info */

      free(A);

    }

  return MD6_SUCCESS;

}

/* Control words.

*/

md6_control_word md6_make_control_word( int r,

                                        int L,

                                        int z,

                                        int p,

                                        int keylen,

                                        int d

                                        )

/* Construct control word V for given inputs.

** Input:

**   r = number of rounds

**   L = mode parameter (maximum tree height)

**   z = 1 iff this is final compression operation

**   p = number of pad bits in a block to be compressed

**   keylen = number of bytes in key

**   d = desired hash output length

**   Does not check inputs for validity.

** Returns:

**   V = constructed control word

*/

{ md6_control_word V;

  V = ( (((md6_control_word) 0) << 60) | /* reserved, width  4 bits */

        (((md6_control_word) r) << 48) |           /* width 12 bits */

        (((md6_control_word) L) << 40) |           /* width  8 bits */

        (((md6_control_word) z) << 36) |           /* width  4 bits */

        (((md6_control_word) p) << 20) |           /* width 16 bits */

        (((md6_control_word) keylen) << 12 ) |     /* width  8 bits */

        (((md6_control_word) d)) );                /* width 12 bits */

  return V;

}

/* Node ID's.

*/

md6_nodeID md6_make_nodeID( int ell,                     /* level number */

                              int i    /* index (0,1,2,...) within level */

                            )

/* Make "unique nodeID" U based on level ell and position i

** within level; place it at specified destination.

** Inputs:

**    dest = address of where nodeID U should be placed

**    ell = integer level number, 1 <= ell <= ...

**    i = index within level, i = 0, 1, 2,...

** Returns

**    U = constructed nodeID

*/

{ md6_nodeID U;

  U = ( (((md6_nodeID) ell) << 56) |

        ((md6_nodeID) i) );

  return U;

}

/* Assembling components of compression input.

*/

void md6_pack( md6_word*N,

               const md6_word* Q,

               md6_word* K,

               int ell, int i,

               int r, int L, int z, int p, int keylen, int d,

               md6_word* B )

/* Pack data before compression into n-word array N.

*/

{ int j;

  int ni;

  md6_nodeID U;

  md6_control_word V;

  ni = 0;

  for (j=0;j<q;j++) N[ni++] = Q[j];       /* Q: Q in words     0--14 */

  for (j=0;j<k;j++) N[ni++] = K[j];       /* K: key in words  15--22 */

  U = md6_make_nodeID(ell,i);             /* U: unique node ID in 23 */

  /* The following also works for variants

  ** in which u=0.

  */

  memcpy((unsigned char *)&N[ni],

         &U,

         min(u*(w/8),sizeof(md6_nodeID)));

  ni += u;

  V = md6_make_control_word(

                        r,L,z,p,keylen,d);/* V: control word in   24 */

  /* The following also works for variants

  ** in which v=0.

  */

  memcpy((unsigned char *)&N[ni],

         &V,

         min(v*(w/8),sizeof(md6_control_word)));

  ni += v;

  memcpy(N+ni,B,b*sizeof(md6_word));      /* B: data words    25--88 */

}

/* Standard compress: assemble components and then compress

*/

int md6_standard_compress( md6_word* C,

                           const md6_word* Q,

                           md6_word* K,

                           int ell, int i,

                           int r, int L, int z, int p, int keylen, int d,

                           md6_word* B

                           )

/* Perform md6 block compression using all the "standard" inputs.

** Input:

**     Q              q-word (q=15) approximation to (sqrt(6)-2)

**     K              k-word key input (k=8)

**     ell            level number

**     i              index within level

**     r              number of rounds in this compression operation

**     L              mode parameter (max tree height)

**     z              1 iff this is the very last compression

**     p              number of padding bits of input in payload B

**     keylen         number of bytes in key

**     d              desired output hash bit length

**     B              b-word (64-word) data input block (with zero padding)

** Modifies:

**     C              c-word output array (c=16)

** Returns one of the following:

**   MD6_SUCCESS (0)   MD6_BAD_p

**   MD6_NULL_B        MD6_BAD_HASHLEN

**   MD6_NULL_C        MD6_NULL_K

**   MD6_BAD_r         MD6_NULL_Q

**   MD6_BAD_ELL       MD6_OUT_OF_MEMORY

*/

{ md6_word N[md6_n];

  md6_word A[5000];       /* MS VS can't handle variable size here */

  /* check that input values are sensible */

  if ( (C == NULL) ) return MD6_NULL_C;

  if ( (B == NULL) ) return MD6_NULL_B;

  if ( (r<0) | (r>md6_max_r) ) return MD6_BAD_r;

  if ( (L<0) | (L>255) ) return MD6_BAD_L;

  if ( (ell < 0) || (ell > 255) ) return MD6_BAD_ELL;

  if ( (p < 0) || (p > b*w ) ) return MD6_BAD_p;

  if ( (d <= 0) || (d > c*w/2) ) return MD6_BADHASHLEN;

  if ( (K == NULL) ) return MD6_NULL_K;

  if ( (Q == NULL) ) return MD6_NULL_Q;

  /* pack components into N for compression */

  md6_pack(N,Q,K,ell,i,r,L,z,p,keylen,d,B);

  /* call compression hook if it is defined. */

  /* -- for testing and debugging.           */

  if (compression_hook != NULL)

    compression_hook(C,Q,K,ell,i,r,L,z,p,keylen,d,B);

  return md6_compress(C,N,r,A);

}

/* end of md6_compress.c */