hash.c 11 KB
Newer Older
Johann Großschädl committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291
///////////////////////////////////////////////////////////////////////////////
// hash.c: Optimized C99 implementation of the hash function ESCH.           //
// This file is part of the SPARKLE submission to NIST's LW Crypto Project.  //
// Version 1.1.2 (2020-10-30), see <http://www.cryptolux.org/> for updates.  //
// Authors: The SPARKLE Group (C. Beierle, A. Biryukov, L. Cardoso dos       //
// Santos, J. Groszschaedl, L. Perrin, A. Udovenko, V. Velichkov, Q. Wang).  //
// License: GPLv3 (see LICENSE file), other licenses available upon request. //
// Copyright (C) 2019-2020 University of Luxembourg <http://www.uni.lu/>.    //
// ------------------------------------------------------------------------- //
// This program is free software: you can redistribute it and/or modify it   //
// under the terms of the GNU General Public License as published by the     //
// Free Software Foundation, either version 3 of the License, or (at your    //
// option) any later version. This program is distributed in the hope that   //
// it will be useful, but WITHOUT ANY WARRANTY; without even the implied     //
// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  //
// GNU General Public License for more details. You should have received a   //
// copy of the GNU General Public License along with this program. If not,   //
// see <http://www.gnu.org/licenses/>.                                       //
///////////////////////////////////////////////////////////////////////////////


// This source code file should be compiled with the following set of flags:
// -std=c99 -Wall -Wextra -Wshadow -fsanitize=address,undefined -O2


// gencat_hash.c shall be used to generate the test vector output file. The
// test vector output file shall be provided in the corresponding 
// crypto_hash/[algorithm]/ directory


#include <stddef.h>  // for size_t
#include <string.h>  // for memcpy, memset
#include "esch_cfg.h"
#include "sparkle_opt.h"


typedef unsigned char UChar;
typedef unsigned long long int ULLInt;


#define DIGEST_WORDS (ESCH_DIGEST_LEN/32)
#define DIGEST_BYTES (ESCH_DIGEST_LEN/8)

#define STATE_BRANS  (SPARKLE_STATE/64)
#define STATE_WORDS  (SPARKLE_STATE/32)
#define STATE_BYTES  (SPARKLE_STATE/8)
#define RATE_BRANS   (SPARKLE_RATE/64)
#define RATE_WORDS   (SPARKLE_RATE/32)
#define RATE_BYTES   (SPARKLE_RATE/8)
#define CAP_BRANS    (SPARKLE_CAPACITY/64)
#define CAP_WORDS    (SPARKLE_CAPACITY/32)
#define CAP_BYTES    (SPARKLE_CAPACITY/8)

#define CONST_M1 (((uint32_t) 1) << 24)
#define CONST_M2 (((uint32_t) 2) << 24)


///////////////////////////////////////////////////////////////////////////////
//// PREPROCESSOR DIRECTIVES TO REPLACE THE C CODE OF SPARKLE BY ASM CODE /////
///////////////////////////////////////////////////////////////////////////////


// When this file is compiled for an AVR microcontroller and SPARKLE_ASSEMBLER
// is defined in schwaemmconfig.h, then the AVR assembler implementation of the
// SPARKLE permutation is used. On the other hand, if SPARKLE_ASSEMBLER is not
// defined, then the C version (i.e. the function sparkle_opt) is used.

#if (defined(__AVR) || defined(__AVR__)) && defined(SPARKLE_ASSEMBLER)
extern void sparkle_avr(uint32_t *state, int brans, int steps);
#define sparkle_opt(state, brans, steps) sparkle_avr((state), (brans), (steps))
#endif  // if defined(__AVR__) && ...


// When this file is compiled for a MSP430 (or a MSP430X) microcontroller and
// SPARKLE_ASSEMBLER is defined in schwaemmconfig.h, then the MSP430 assembler
// implementation of the SPARKLE permutation is used. On the other hand, if
// SPARKLE_ASSEMBLER is not defined, then the C version (i.e. the function
// sparkle_opt) is used.

#if (defined(MSP430) || defined(__MSP430__)) && defined(SPARKLE_ASSEMBLER)
extern void sparkle_msp(uint32_t *state, int brans, int steps);
#define sparkle_opt(state, brans, steps) sparkle_msp((state), (brans), (steps))
#endif  // if (defined(MSP430) || ...


// When this file is compiled for an ARM microcontroller and SPARKLE_ASSEMBLER
// is defined in schwaemmconfig.h, then one of the three branch-unrolled ARMv7M
// assembler implementations of the SPARKLE permutation is used, depending on
// the concrete ESCH instance. On the other hand, if SPARKLE_ASSEMBLER is not
// defined, then the C version (i.e. the function sparkle_opt) is used.

#if (defined(__arm__) || defined(_M_ARM)) && defined(SPARKLE_ASSEMBLER)
#if defined(ESCH256)
extern void sparkle384_arm(uint32_t *state, int steps);
#define sparkle_opt(state, brans, steps) sparkle384_arm((state), (steps))
#elif defined(ESCH384)
extern void sparkle512_arm(uint32_t *state, int steps);
#define sparkle_opt(state, brans, steps) sparkle512_arm((state), (steps))
#endif  // if defined(ESCH256)
#endif  // if defined(__arm__) && ...


///////////////////////////////////////////////////////////////////////////////
/////// HELPER FUNCTIONS AND MACROS (INJECTION OF MESSAGE BLOCK, ETC.) ////////
///////////////////////////////////////////////////////////////////////////////


#define ROT(x, n) (((x) >> (n)) | ((x) << (32-(n))))
#define ELL(x) (ROT(((x) ^ ((x) << 16)), 16))


// The message to be hashed is stored in arrays of type unsigned char. Casting
// such an unsigned-char-pointer to an uint32_t-pointer increases alignment
// requirements, i.e. the start address of the array has to be even on 16-bit
// architectures or a multiple of four (i.e. 4-byte aligned) on 32-bit and
// 64-bit platforms. The following preprocessor statements help to determine
// the alignment requirements for a uint32_t pointer.

#define MIN_SIZE(a, b) ((sizeof(a) < sizeof(b)) ? sizeof(a) : sizeof(b))
#if defined(_MSC_VER) && !defined(__clang__) && !defined(__ICL)
#define UI32_ALIGN_BYTES MIN_SIZE(unsigned __int32, size_t)
#else
#include <stdint.h>
#define UI32_ALIGN_BYTES MIN_SIZE(uint32_t, uint_fast8_t)
#endif


// Injection of a 16-byte block of the message to the state. According to the
// specification, the Feistel function is performed on a message block that is
// padded with 0-bytes to reach a length of STATE_BYTES/2 bytes (i.e. 24 bytes
// for ESCH256, 32 bytes for ESCH384). However, this padding can be omitted by
// adapting the Feistel function accordingly. The third parameter indicates
// whether the uint8_t-pointer 'in' is properly aligned to permit casting to a
// uint32_t-pointer. If this is the case then array 'in' is processed directly,
// otherwise it is first copied to an aligned buffer. 

static void add_msg_blk(uint32_t *state, const uint8_t *in, int aligned)
{
  uint32_t buffer[RATE_WORDS];
  uint32_t *in32;
  uint32_t tmpx = 0, tmpy = 0;
  int i;
  
  if (aligned) {  // 'in' can be casted to uint32_t pointer
    in32 = (uint32_t *) in;
  } else {  // 'in' is not sufficiently aligned for casting
    memcpy(buffer, in, RATE_BYTES);
    in32 = (uint32_t *) &buffer;
  }
  
  for(i = 0; i < RATE_WORDS; i += 2) {
    tmpx ^= in32[i];
    tmpy ^= in32[i+1];
  }
  tmpx = ELL(tmpx);
  tmpy = ELL(tmpy);
  for(i = 0; i < RATE_WORDS; i += 2) {
    state[i] ^= (in32[i] ^ tmpy);
    state[i+1] ^= (in32[i+1] ^ tmpx);
  }
  for(i = RATE_WORDS; i < (STATE_WORDS/2); i += 2) {
    state[i] ^= tmpy;
    state[i+1] ^= tmpx;
  }
}


// Injection of the last message block to the state. Since this last block may
// require padding, it is always copied to a buffer.

static void add_msg_blk_last(uint32_t *state, const uint8_t *in, size_t inlen)
{
  uint32_t buffer[RATE_WORDS];
  uint8_t *bufptr;
  uint32_t tmpx = 0, tmpy = 0;
  int i;
  
  memcpy(buffer, in, inlen);
  if (inlen < RATE_BYTES) {  // padding
    bufptr = ((uint8_t *) buffer) + inlen;
    memset(bufptr, 0, (RATE_BYTES - inlen));
    *bufptr = 0x80;
  }
  
  for(i = 0; i < RATE_WORDS; i += 2) {
    tmpx ^= buffer[i];
    tmpy ^= buffer[i+1];
  }
  tmpx = ELL(tmpx);
  tmpy = ELL(tmpy);
  for(i = 0; i < RATE_WORDS; i += 2) {
    state[i] ^= (buffer[i] ^ tmpy);
    state[i+1] ^= (buffer[i+1] ^ tmpx);
  }
  for(i = RATE_WORDS; i < (STATE_WORDS/2); i += 2) {
    state[i] ^= tmpy;
    state[i+1] ^= tmpx;
  }
}


///////////////////////////////////////////////////////////////////////////////
///////////// LOW-LEVEL HASH FUNCTIONS (FOR USE WITH FELICS-HASH) /////////////
///////////////////////////////////////////////////////////////////////////////


// The Initialize function sets all branches of the state to 0.

void Initialize(uint32_t *state)
{
  int i;
  
  for (i = 0; i < STATE_WORDS; i++)
    state[i] = 0;
}


// The ProcessMessage function absorbs the message into the state (in blocks of
// 16 bytes). According to the specification, the constant Const_M is first
// transformed via the inverse Feistel function, added to the (padded) message
// block, and finally injected to the state via the Feistel function. Since the
// Feistel function and the inverse Feistel function cancel out, we can simply
// inject the constant directly to the state.

void ProcessMessage(uint32_t *state, const UChar *in, size_t inlen)
{
  // check whether 'in' can be casted to uint32_t pointer
  int aligned = ((size_t) in) % UI32_ALIGN_BYTES == 0;
  // printf("Address of 'in': %p\n", in);
  
  // Main Hashing Loop
  
  while (inlen > RATE_BYTES) {
    // addition of a message block to the state
    add_msg_blk(state, in, aligned);
    // execute SPARKLE with slim number of steps
    sparkle_opt(state, STATE_BRANS, SPARKLE_STEPS_SLIM);
    inlen -= RATE_BYTES;
    in += RATE_BYTES;
  }
  
  // Hashing of Last Block
  
  // addition of constant M1 or M2 to the state
  state[STATE_BRANS-1] ^= ((inlen < RATE_BYTES) ? CONST_M1 : CONST_M2);
  // addition of last msg block (incl. padding)
  add_msg_blk_last(state, in, inlen);
  // execute SPARKLE with big number of steps
  sparkle_opt(state, STATE_BRANS, SPARKLE_STEPS_BIG);
}


// The Finalize function generates the message digest by "squeezing" (i.e. by
// calling SPARKLE with a slim number of steps) until the digest has reached a
// byte-length of DIGEST_BYTES.

void Finalize(uint32_t *state, UChar *out)
{
  size_t outlen;
  
  memcpy(out, state, RATE_BYTES);
  outlen = RATE_BYTES;
  out += RATE_BYTES;
  while (outlen < DIGEST_BYTES) {
    sparkle_opt(state, STATE_BRANS, SPARKLE_STEPS_SLIM);
    memcpy(out, state, RATE_BYTES);
    outlen += RATE_BYTES;
    out += RATE_BYTES;
  }
}


///////////////////////////////////////////////////////////////////////////////
////////////// HIGH-LEVEL HASH FUNCTIONS (FOR USE WITH SUPERCOP) //////////////
///////////////////////////////////////////////////////////////////////////////


// To ensure compatibility with the SUPERCOP, the below implementation of 
// crypto_hash can handle overlapping input and output buffers.

int crypto_hash(UChar *out, const UChar *in, ULLInt inlen)
{
  uint32_t state[STATE_WORDS];
  size_t insize = (size_t) inlen;
  
  Initialize(state);
  ProcessMessage(state, in, insize);
  Finalize(state, out);
  
  return 0;
}