sha3/sph_hefty1.c

   1 /*
   2  * HEFTY1 cryptographic hash function
   3  *
   4  * Copyright (c) 2014, dbcc14 <BM-NBx4AKznJuyem3dArgVY8MGyABpihRy5>
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright notice, this
  11  *    list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright notice,
  13  *    this list of conditions and the following disclaimer in the documentation
  14  *    and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
  20  * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  *
  27  * The views and conclusions contained in the software and documentation are those
  28  * of the authors and should not be interpreted as representing official policies,
  29  * either expressed or implied, of the FreeBSD Project.
  30  */
  31
  32 #include <assert.h>
  33 #include <string.h>
  34
  35 #include "sph_hefty1.h"
  36
  37 #define Min(A, B) (A <= B ? A : B)
  38 #define RoundFunc(ctx, A, B, C, D, E, F, G, H, W, K)                    \
  39     {                                                                   \
  40         /* To thwart parallelism, Br modifies itself each time it's     \
  41          * called.  This also means that calling it in different        \
  42          * orders yeilds different results.  In C the order of          \
  43          * evaluation of function arguments and + operands are          \
  44          * unspecified (and depends on the compiler), so we must make   \
  45          * the order of Br calls explicit.                              \
  46          */                                                             \
  47         uint32_t brG = Br(ctx, G);                                      \
  48         uint32_t tmp1 = Ch(E, Br(ctx, F), brG) + H + W + K;             \
  49         uint32_t tmp2 = tmp1 + Sigma1(Br(ctx, E));                      \
  50         uint32_t brC = Br(ctx, C);                                      \
  51         uint32_t brB = Br(ctx, B);                                      \
  52         uint32_t tmp3 = Ma(Br(ctx, A), brB, brC);                       \
  53         uint32_t tmp4 = tmp3 + Sigma0(Br(ctx, A));                      \
  54         H = G;                                                          \
  55         G = F;                                                          \
  56         F = E;                                                          \
  57         E = D + Br(ctx, tmp2);                                          \
  58         D = C;                                                          \
  59         C = B;                                                          \
  60         B = A;                                                          \
  61         A = tmp2 + tmp4;                                                \
  62     }                                                                   \
  63
  64 /* Nothing up my sleeve constants */
  65 const static uint32_t K[64] = {
  66     0x428a2f98UL, 0x71374491UL, 0xb5c0fbcfUL, 0xe9b5dba5UL,
  67     0x3956c25bUL, 0x59f111f1UL, 0x923f82a4UL, 0xab1c5ed5UL,
  68     0xd807aa98UL, 0x12835b01UL, 0x243185beUL, 0x550c7dc3UL,
  69     0x72be5d74UL, 0x80deb1feUL, 0x9bdc06a7UL, 0xc19bf174UL,
  70     0xe49b69c1UL, 0xefbe4786UL, 0x0fc19dc6UL, 0x240ca1ccUL,
  71     0x2de92c6fUL, 0x4a7484aaUL, 0x5cb0a9dcUL, 0x76f988daUL,
  72     0x983e5152UL, 0xa831c66dUL, 0xb00327c8UL, 0xbf597fc7UL,
  73     0xc6e00bf3UL, 0xd5a79147UL, 0x06ca6351UL, 0x14292967UL,
  74     0x27b70a85UL, 0x2e1b2138UL, 0x4d2c6dfcUL, 0x53380d13UL,
  75     0x650a7354UL, 0x766a0abbUL, 0x81c2c92eUL, 0x92722c85UL,
  76     0xa2bfe8a1UL, 0xa81a664bUL, 0xc24b8b70UL, 0xc76c51a3UL,
  77     0xd192e819UL, 0xd6990624UL, 0xf40e3585UL, 0x106aa070UL,
  78     0x19a4c116UL, 0x1e376c08UL, 0x2748774cUL, 0x34b0bcb5UL,
  79     0x391c0cb3UL, 0x4ed8aa4aUL, 0x5b9cca4fUL, 0x682e6ff3UL,
  80     0x748f82eeUL, 0x78a5636fUL, 0x84c87814UL, 0x8cc70208UL,
  81     0x90befffaUL, 0xa4506cebUL, 0xbef9a3f7UL, 0xc67178f2UL
  82 };
  83
  84 /* Initial hash values */
  85 const static uint32_t H[HEFTY1_STATE_WORDS] = {
  86     0x6a09e667UL,
  87     0xbb67ae85UL,
  88     0x3c6ef372UL,
  89     0xa54ff53aUL,
  90     0x510e527fUL,
  91     0x9b05688cUL,
  92     0x1f83d9abUL,
  93     0x5be0cd19UL
  94 };
  95
  96 static inline uint32_t Rr(uint32_t X, uint8_t n)
  97 {
  98     return (X >> n) | (X << (32 - n));
  99 }
 100
 101 static inline uint32_t Ch(uint32_t E, uint32_t F, uint32_t G)
 102 {
 103     return (E & F) ^ (~E & G);
 104 }
 105
 106 static inline uint32_t Sigma1(uint32_t E)
 107 {
 108     return Rr(E, 6) ^ Rr(E, 11) ^ Rr(E, 25);
 109 }
 110
 111 static inline uint32_t sigma1(uint32_t X)
 112 {
 113     return Rr(X, 17) ^ Rr(X, 19) ^ (X >> 10);
 114 }
 115
 116 static inline uint32_t Ma(uint32_t A, uint32_t B, uint32_t C)
 117 {
 118     return (A & B) ^ (A & C) ^ (B & C);
 119 }
 120
 121 static inline uint32_t Sigma0(uint32_t A)
 122 {
 123     return Rr(A, 2) ^ Rr(A, 13) ^ Rr(A, 22);
 124 }
 125
 126 static inline uint32_t sigma0(uint32_t X)
 127 {
 128     return Rr(X, 7) ^ Rr(X, 18) ^ (X >> 3);
 129 }
 130
 131 static inline uint32_t Reverse32(uint32_t n)
 132 {
 133     #if BYTE_ORDER == LITTLE_ENDIAN
 134         return n << 24 | (n & 0x0000ff00) << 8 | (n & 0x00ff0000) >> 8 | n >> 24;
 135     #else
 136         return n;
 137     #endif
 138 }
 139
 140 static inline uint64_t Reverse64(uint64_t n)
 141 {
 142     #if BYTE_ORDER == LITTLE_ENDIAN
 143         uint32_t a = n >> 32;
 144         uint32_t b = (n << 32) >> 32;
 145
 146         return (uint64_t)Reverse32(b) << 32 | Reverse32(a);
 147     #else
 148         return n;
 149     #endif
 150 }
 151
 152 /* Smoosh byte into nibble */
 153 static inline uint8_t Smoosh4(uint8_t X)
 154 {
 155     return (X >> 4) ^ (X & 0xf);
 156 }
 157
 158 /* Smoosh 32-bit word into 2-bits */
 159 static inline uint8_t Smoosh2(uint32_t X)
 160 {
 161     uint16_t w = (X >> 16) ^ (X & 0xffff);
 162     uint8_t n = Smoosh4((w >> 8) ^ (w & 0xff));
 163     return (n >> 2) ^ (n & 0x3);
 164 }
 165
 166 static void Mangle(uint32_t *S)
 167 {
 168     uint32_t *R = S;
 169     uint32_t *C = &S[1];
 170
 171     uint8_t r0 = Smoosh4(R[0] >> 24);
 172     uint8_t r1 = Smoosh4(R[0] >> 16);
 173     uint8_t r2 = Smoosh4(R[0] >> 8);
 174     uint8_t r3 = Smoosh4(R[0] & 0xff);
 175
 176     int i;
 177
 178     /* Diffuse */
 179     uint32_t tmp = 0;
 180     for (i = 0; i < HEFTY1_SPONGE_WORDS - 1; i++) {
 181         uint8_t r = Smoosh2(tmp);
 182         switch (r) {
 183         case 0:
 184             C[i] ^= Rr(R[0], i + r0);
 185             break;
 186         case 1:
 187             C[i] += Rr(~R[0], i + r1);
 188             break;
 189         case 2:
 190             C[i] &= Rr(~R[0], i + r2);
 191             break;
 192         case 3:
 193             C[i] ^= Rr(R[0], i + r3);
 194             break;
 195         }
 196         tmp ^= C[i];
 197     }
 198
 199     /* Compress */
 200     tmp = 0;
 201     for (i = 0; i < HEFTY1_SPONGE_WORDS - 1; i++)
 202         if (i % 2)
 203             tmp ^= C[i];
 204         else
 205             tmp += C[i];
 206     R[0] ^= tmp;
 207 }
 208
 209 static void Absorb(uint32_t *S, uint32_t X)
 210 {
 211     uint32_t *R = S;
 212     R[0] ^= X;
 213     Mangle(S);
 214 }
 215
 216 static uint32_t Squeeze(uint32_t *S)
 217 {
 218     uint32_t Y = S[0];
 219     Mangle(S);
 220     return Y;
 221 }
 222
 223 /* Branch, compress and serialize function */
 224 static inline uint32_t Br(HEFTY1_CTX *ctx, uint32_t X)
 225 {
 226     uint32_t R = Squeeze(ctx->sponge);
 227
 228     uint8_t r0 = R >> 8;
 229     uint8_t r1 = R & 0xff;
 230
 231     uint32_t Y = 1 << (r0 % 32);
 232
 233     switch (r1 % 4)
 234     {
 235     case 0:
 236         /* Do nothing */
 237         break;
 238     case 1:
 239         return X & ~Y;
 240     case 2:
 241         return X | Y;
 242     case 3:
 243         return X ^ Y;
 244     }
 245
 246     return X;
 247 }
 248
 249 static void HashBlock(HEFTY1_CTX *ctx)
 250 {
 251     uint32_t A, B, C, D, E, F, G, H;
 252     uint32_t W[HEFTY1_BLOCK_BYTES];
 253
 254     assert(ctx);
 255
 256     A = ctx->h[0];
 257     B = ctx->h[1];
 258     C = ctx->h[2];
 259     D = ctx->h[3];
 260     E = ctx->h[4];
 261     F = ctx->h[5];
 262     G = ctx->h[6];
 263     H = ctx->h[7];
 264
 265     int t = 0;
 266     for (; t < 16; t++) {
 267         W[t] = Reverse32(((uint32_t *)&ctx->block[0])[t]); /* To host byte order */
 268         Absorb(ctx->sponge, W[t] ^ K[t]);
 269     }
 270
 271     for (t = 0; t < 16; t++) {
 272         Absorb(ctx->sponge, D ^ H);
 273         RoundFunc(ctx, A, B, C, D, E, F, G, H, W[t], K[t]);
 274     }
 275     for (t = 16; t < 64; t++) {
 276         Absorb(ctx->sponge, H + D);
 277         W[t] = sigma1(W[t - 2]) + W[t - 7] + sigma0(W[t - 15]) + W[t - 16];
 278         RoundFunc(ctx, A, B, C, D, E, F, G, H, W[t], K[t]);
 279     }
 280
 281     ctx->h[0] += A;
 282     ctx->h[1] += B;
 283     ctx->h[2] += C;
 284     ctx->h[3] += D;
 285     ctx->h[4] += E;
 286     ctx->h[5] += F;
 287     ctx->h[6] += G;
 288     ctx->h[7] += H;
 289
 290     A = 0;
 291     B = 0;
 292     C = 0;
 293     D = 0;
 294     E = 0;
 295     F = 0;
 296     G = 0;
 297     H = 0;
 298
 299     memset(W, 0, sizeof(W));
 300 }
 301
 302 /* Public interface */
 303
 304 void HEFTY1_Init(HEFTY1_CTX *ctx)
 305 {
 306     assert(ctx);
 307
 308     memcpy(ctx->h, H, sizeof(ctx->h));
 309     memset(ctx->block, 0, sizeof(ctx->block));
 310     ctx->written = 0;
 311     memset(ctx->sponge, 0, sizeof(ctx->sponge));
 312 }
 313
 314 void HEFTY1_Update(HEFTY1_CTX *ctx, const void *buf, size_t len)
 315 {
 316     assert(ctx);
 317
 318     uint64_t read = 0;
 319     while (len) {
 320         uint64_t end = ctx->written % HEFTY1_BLOCK_BYTES;
 321         uint64_t count = Min(len, HEFTY1_BLOCK_BYTES - end);
 322         memcpy(&ctx->block[end], &((unsigned char *)buf)[read], count);
 323         len -= count;
 324         read += count;
 325         ctx->written += count;
 326         if (!(ctx->written % HEFTY1_BLOCK_BYTES))
 327             HashBlock(ctx);
 328     }
 329 }
 330
 331 void HEFTY1_Final(unsigned char *digest, HEFTY1_CTX *ctx)
 332 {
 333     assert(digest);
 334     assert(ctx);
 335
 336     /* Pad message (FIPS 180 Section 5.1.1) */
 337     uint64_t used = ctx->written % HEFTY1_BLOCK_BYTES;
 338     ctx->block[used++] = 0x80; /* Append 1 to end of message */
 339     if (used > HEFTY1_BLOCK_BYTES - 8) {
 340         /* We have already written into the last 64bits, so
 341          * we must continue into the next block. */
 342         memset(&ctx->block[used], 0, HEFTY1_BLOCK_BYTES - used);
 343         HashBlock(ctx);
 344         used = 0; /* Create a new block (below) */
 345     }
 346
 347     /* All remaining bits to zero */
 348     memset(&ctx->block[used], 0, HEFTY1_BLOCK_BYTES - 8 - used);
 349
 350     /* The last 64bits encode the length (in network byte order) */
 351     uint64_t *len = (uint64_t *)&ctx->block[HEFTY1_BLOCK_BYTES - 8];
 352     *len = Reverse64(ctx->written*8);
 353
 354     HashBlock(ctx);
 355
 356     /* Convert back to network byte order */
 357     int i = 0;
 358     for (; i < HEFTY1_STATE_WORDS; i++)
 359         ctx->h[i] = Reverse32(ctx->h[i]);
 360
 361     memcpy(digest, ctx->h, sizeof(ctx->h));
 362     memset(ctx, 0, sizeof(HEFTY1_CTX));
 363 }
 364
 365 unsigned char* HEFTY1(const unsigned char *buf, size_t len, unsigned char *digest)
 366 {
 367     HEFTY1_CTX ctx;
 368     static unsigned char m[HEFTY1_DIGEST_BYTES];
 369
 370     if (!digest)
 371         digest = m;
 372
 373     HEFTY1_Init(&ctx);
 374     HEFTY1_Update(&ctx, buf, len);
 375     HEFTY1_Final(digest, &ctx);
 376
 377     return digest;
 378 }