crypto/sha/keccak1600.c

   1 /*
   2  * Copyright 2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include <openssl/e_os2.h>
  11 #include <string.h>
  12 #include <assert.h>
  13
  14 #define ROL32(a, offset) (((a) << (offset)) | ((a) >> ((32 - (offset)) & 31)))
  15
  16 static uint64_t ROL64(uint64_t val, int offset)
  17 {
  18     if (offset == 0) {
  19         return val;
  20     } else if (sizeof(void *) == 8) {
  21         return (val << offset) | (val >> (64-offset));
  22     } else {
  23         uint32_t hi = (uint32_t)(val >> 32), lo = (uint32_t)val;
  24
  25         if (offset & 1) {
  26             uint32_t tmp = hi;
  27
  28             offset >>= 1;
  29             hi = ROL32(lo, offset);
  30             lo = ROL32(tmp, offset + 1);
  31         } else {
  32             offset >>= 1;
  33             lo = ROL32(lo, offset);
  34             hi = ROL32(hi, offset);
  35         }
  36
  37         return ((uint64_t)hi << 32) | lo;
  38     }
  39 }
  40
  41 static const unsigned char rhotates[5][5] = {
  42     {  0,  1, 62, 28, 27 },
  43     { 36, 44,  6, 55, 20 },
  44     {  3, 10, 43, 25, 39 },
  45     { 41, 45, 15, 21,  8 },
  46     { 18,  2, 61, 56, 14 }
  47 };
  48
  49 static const uint64_t iotas[] = {
  50     sizeof(void *) == 8 ? 0x0000000000000001U : 0x0000000000000001U,
  51     sizeof(void *) == 8 ? 0x0000000000008082U : 0x0000008900000000U,
  52     sizeof(void *) == 8 ? 0x800000000000808aU : 0x8000008b00000000U,
  53     sizeof(void *) == 8 ? 0x8000000080008000U : 0x8000808000000000U,
  54     sizeof(void *) == 8 ? 0x000000000000808bU : 0x0000008b00000001U,
  55     sizeof(void *) == 8 ? 0x0000000080000001U : 0x0000800000000001U,
  56     sizeof(void *) == 8 ? 0x8000000080008081U : 0x8000808800000001U,
  57     sizeof(void *) == 8 ? 0x8000000000008009U : 0x8000008200000001U,
  58     sizeof(void *) == 8 ? 0x000000000000008aU : 0x0000000b00000000U,
  59     sizeof(void *) == 8 ? 0x0000000000000088U : 0x0000000a00000000U,
  60     sizeof(void *) == 8 ? 0x0000000080008009U : 0x0000808200000001U,
  61     sizeof(void *) == 8 ? 0x000000008000000aU : 0x0000800300000000U,
  62     sizeof(void *) == 8 ? 0x000000008000808bU : 0x0000808b00000001U,
  63     sizeof(void *) == 8 ? 0x800000000000008bU : 0x8000000b00000001U,
  64     sizeof(void *) == 8 ? 0x8000000000008089U : 0x8000008a00000001U,
  65     sizeof(void *) == 8 ? 0x8000000000008003U : 0x8000008100000001U,
  66     sizeof(void *) == 8 ? 0x8000000000008002U : 0x8000008100000000U,
  67     sizeof(void *) == 8 ? 0x8000000000000080U : 0x8000000800000000U,
  68     sizeof(void *) == 8 ? 0x000000000000800aU : 0x0000008300000000U,
  69     sizeof(void *) == 8 ? 0x800000008000000aU : 0x8000800300000000U,
  70     sizeof(void *) == 8 ? 0x8000000080008081U : 0x8000808800000001U,
  71     sizeof(void *) == 8 ? 0x8000000000008080U : 0x8000008800000000U,
  72     sizeof(void *) == 8 ? 0x0000000080000001U : 0x0000800000000001U,
  73     sizeof(void *) == 8 ? 0x8000000080008008U : 0x8000808200000000U
  74 };
  75
  76 #if defined(KECCAK_REF)
  77 /*
  78  * This is straightforward or "maximum clarity" implementation aiming
  79  * to resemble section 3.2 of the FIPS PUB 202 "SHA-3 Standard:
  80  * Permutation-Based Hash and Extendible-Output Functions" as much as
  81  * possible. With one caveat. Because of the way C stores matrices,
  82  * references to A[x,y] in the specification are presented as A[y][x].
  83  * Implementation unrolls inner x-loops so that modulo 5 operations are
  84  * explicitly pre-computed.
  85  */
  86 static void Theta(uint64_t A[5][5])
  87 {
  88     uint64_t C[5], D[5];
  89     size_t y;
  90
  91     C[0] = A[0][0];
  92     C[1] = A[0][1];
  93     C[2] = A[0][2];
  94     C[3] = A[0][3];
  95     C[4] = A[0][4];
  96
  97     for (y = 1; y < 5; y++) {
  98         C[0] ^= A[y][0];
  99         C[1] ^= A[y][1];
 100         C[2] ^= A[y][2];
 101         C[3] ^= A[y][3];
 102         C[4] ^= A[y][4];
 103     }
 104
 105     D[0] = ROL64(C[1], 1) ^ C[4];
 106     D[1] = ROL64(C[2], 1) ^ C[0];
 107     D[2] = ROL64(C[3], 1) ^ C[1];
 108     D[3] = ROL64(C[4], 1) ^ C[2];
 109     D[4] = ROL64(C[0], 1) ^ C[3];
 110
 111     for (y = 0; y < 5; y++) {
 112         A[y][0] ^= D[0];
 113         A[y][1] ^= D[1];
 114         A[y][2] ^= D[2];
 115         A[y][3] ^= D[3];
 116         A[y][4] ^= D[4];
 117     }
 118 }
 119
 120 static void Rho(uint64_t A[5][5])
 121 {
 122     size_t y;
 123
 124     for (y = 0; y < 5; y++) {
 125         A[y][0] = ROL64(A[y][0], rhotates[y][0]);
 126         A[y][1] = ROL64(A[y][1], rhotates[y][1]);
 127         A[y][2] = ROL64(A[y][2], rhotates[y][2]);
 128         A[y][3] = ROL64(A[y][3], rhotates[y][3]);
 129         A[y][4] = ROL64(A[y][4], rhotates[y][4]);
 130     }
 131 }
 132
 133 static void Pi(uint64_t A[5][5])
 134 {
 135     uint64_t T[5][5];
 136
 137     /*
 138      * T = A
 139      * A[y][x] = T[x][(3*y+x)%5]
 140      */
 141     memcpy(T, A, sizeof(T));
 142
 143     A[0][0] = T[0][0];
 144     A[0][1] = T[1][1];
 145     A[0][2] = T[2][2];
 146     A[0][3] = T[3][3];
 147     A[0][4] = T[4][4];
 148
 149     A[1][0] = T[0][3];
 150     A[1][1] = T[1][4];
 151     A[1][2] = T[2][0];
 152     A[1][3] = T[3][1];
 153     A[1][4] = T[4][2];
 154
 155     A[2][0] = T[0][1];
 156     A[2][1] = T[1][2];
 157     A[2][2] = T[2][3];
 158     A[2][3] = T[3][4];
 159     A[2][4] = T[4][0];
 160
 161     A[3][0] = T[0][4];
 162     A[3][1] = T[1][0];
 163     A[3][2] = T[2][1];
 164     A[3][3] = T[3][2];
 165     A[3][4] = T[4][3];
 166
 167     A[4][0] = T[0][2];
 168     A[4][1] = T[1][3];
 169     A[4][2] = T[2][4];
 170     A[4][3] = T[3][0];
 171     A[4][4] = T[4][1];
 172 }
 173
 174 static void Chi(uint64_t A[5][5])
 175 {
 176     uint64_t C[5];
 177     size_t y;
 178
 179     for (y = 0; y < 5; y++) {
 180         C[0] = A[y][0] ^ (~A[y][1] & A[y][2]);
 181         C[1] = A[y][1] ^ (~A[y][2] & A[y][3]);
 182         C[2] = A[y][2] ^ (~A[y][3] & A[y][4]);
 183         C[3] = A[y][3] ^ (~A[y][4] & A[y][0]);
 184         C[4] = A[y][4] ^ (~A[y][0] & A[y][1]);
 185
 186         A[y][0] = C[0];
 187         A[y][1] = C[1];
 188         A[y][2] = C[2];
 189         A[y][3] = C[3];
 190         A[y][4] = C[4];
 191     }
 192 }
 193
 194 static void Iota(uint64_t A[5][5], size_t i)
 195 {
 196     assert(i < (sizeof(iotas) / sizeof(iotas[0])));
 197     A[0][0] ^= iotas[i];
 198 }
 199
 200 void KeccakF1600(uint64_t A[5][5])
 201 {
 202     size_t i;
 203
 204     for (i = 0; i < 24; i++) {
 205         Theta(A);
 206         Rho(A);
 207         Pi(A);
 208         Chi(A);
 209         Iota(A, i);
 210     }
 211 }
 212
 213 #elif defined(KECCAK_1X)
 214 /*
 215  * This implementation is optimization of above code featuring unroll
 216  * of even y-loops, their fusion and code motion. It also minimizes
 217  * temporary storage. Compiler would normally do all these things for
 218  * you, purpose of manual optimization is to provide "unobscured"
 219  * reference for assembly implementation [in case this approach is
 220  * chosen for implementation on some platform]. In the nutshell it's
 221  * equivalent of "plane-per-plane processing" approach discussed in
 222  * section 2.4 of "Keccak implementation overview".
 223  */
 224 static void Round(uint64_t A[5][5], size_t i)
 225 {
 226     uint64_t C[5], E[2];        /* registers */
 227     uint64_t D[5], T[2][5];     /* memory    */
 228
 229     assert(i < (sizeof(iotas) / sizeof(iotas[0])));
 230
 231     C[0] = A[0][0] ^ A[1][0] ^ A[2][0] ^ A[3][0] ^ A[4][0];
 232     C[1] = A[0][1] ^ A[1][1] ^ A[2][1] ^ A[3][1] ^ A[4][1];
 233     C[2] = A[0][2] ^ A[1][2] ^ A[2][2] ^ A[3][2] ^ A[4][2];
 234     C[3] = A[0][3] ^ A[1][3] ^ A[2][3] ^ A[3][3] ^ A[4][3];
 235     C[4] = A[0][4] ^ A[1][4] ^ A[2][4] ^ A[3][4] ^ A[4][4];
 236
 237 #if defined(__arm__)
 238     D[1] = E[0] = ROL64(C[2], 1) ^ C[0];
 239     D[4] = E[1] = ROL64(C[0], 1) ^ C[3];
 240     D[0] = C[0] = ROL64(C[1], 1) ^ C[4];
 241     D[2] = C[1] = ROL64(C[3], 1) ^ C[1];
 242     D[3] = C[2] = ROL64(C[4], 1) ^ C[2];
 243
 244     T[0][0] = A[3][0] ^ C[0]; /* borrow T[0][0] */
 245     T[0][1] = A[0][1] ^ E[0]; /* D[1] */
 246     T[0][2] = A[0][2] ^ C[1]; /* D[2] */
 247     T[0][3] = A[0][3] ^ C[2]; /* D[3] */
 248     T[0][4] = A[0][4] ^ E[1]; /* D[4] */
 249
 250     C[3] = ROL64(A[3][3] ^ C[2], rhotates[3][3]);   /* D[3] */
 251     C[4] = ROL64(A[4][4] ^ E[1], rhotates[4][4]);   /* D[4] */
 252     C[0] =       A[0][0] ^ C[0]; /* rotate by 0 */  /* D[0] */
 253     C[2] = ROL64(A[2][2] ^ C[1], rhotates[2][2]);   /* D[2] */
 254     C[1] = ROL64(A[1][1] ^ E[0], rhotates[1][1]);   /* D[1] */
 255 #else
 256     D[0] = ROL64(C[1], 1) ^ C[4];
 257     D[1] = ROL64(C[2], 1) ^ C[0];
 258     D[2] = ROL64(C[3], 1) ^ C[1];
 259     D[3] = ROL64(C[4], 1) ^ C[2];
 260     D[4] = ROL64(C[0], 1) ^ C[3];
 261
 262     T[0][0] = A[3][0] ^ D[0]; /* borrow T[0][0] */
 263     T[0][1] = A[0][1] ^ D[1];
 264     T[0][2] = A[0][2] ^ D[2];
 265     T[0][3] = A[0][3] ^ D[3];
 266     T[0][4] = A[0][4] ^ D[4];
 267
 268     C[0] =       A[0][0] ^ D[0]; /* rotate by 0 */
 269     C[1] = ROL64(A[1][1] ^ D[1], rhotates[1][1]);
 270     C[2] = ROL64(A[2][2] ^ D[2], rhotates[2][2]);
 271     C[3] = ROL64(A[3][3] ^ D[3], rhotates[3][3]);
 272     C[4] = ROL64(A[4][4] ^ D[4], rhotates[4][4]);
 273 #endif
 274     A[0][0] = C[0] ^ (~C[1] & C[2]) ^ iotas[i];
 275     A[0][1] = C[1] ^ (~C[2] & C[3]);
 276     A[0][2] = C[2] ^ (~C[3] & C[4]);
 277     A[0][3] = C[3] ^ (~C[4] & C[0]);
 278     A[0][4] = C[4] ^ (~C[0] & C[1]);
 279
 280     T[1][0] = A[1][0] ^ (C[3] = D[0]);
 281     T[1][1] = A[2][1] ^ (C[4] = D[1]); /* borrow T[1][1] */
 282     T[1][2] = A[1][2] ^ (E[0] = D[2]);
 283     T[1][3] = A[1][3] ^ (E[1] = D[3]);
 284     T[1][4] = A[2][4] ^ (C[2] = D[4]); /* borrow T[1][4] */
 285
 286     C[0] = ROL64(T[0][3],        rhotates[0][3]);
 287     C[1] = ROL64(A[1][4] ^ C[2], rhotates[1][4]);   /* D[4] */
 288     C[2] = ROL64(A[2][0] ^ C[3], rhotates[2][0]);   /* D[0] */
 289     C[3] = ROL64(A[3][1] ^ C[4], rhotates[3][1]);   /* D[1] */
 290     C[4] = ROL64(A[4][2] ^ E[0], rhotates[4][2]);   /* D[2] */
 291
 292     A[1][0] = C[0] ^ (~C[1] & C[2]);
 293     A[1][1] = C[1] ^ (~C[2] & C[3]);
 294     A[1][2] = C[2] ^ (~C[3] & C[4]);
 295     A[1][3] = C[3] ^ (~C[4] & C[0]);
 296     A[1][4] = C[4] ^ (~C[0] & C[1]);
 297
 298     C[0] = ROL64(T[0][1],        rhotates[0][1]);
 299     C[1] = ROL64(T[1][2],        rhotates[1][2]);
 300     C[2] = ROL64(A[2][3] ^ D[3], rhotates[2][3]);
 301     C[3] = ROL64(A[3][4] ^ D[4], rhotates[3][4]);
 302     C[4] = ROL64(A[4][0] ^ D[0], rhotates[4][0]);
 303
 304     A[2][0] = C[0] ^ (~C[1] & C[2]);
 305     A[2][1] = C[1] ^ (~C[2] & C[3]);
 306     A[2][2] = C[2] ^ (~C[3] & C[4]);
 307     A[2][3] = C[3] ^ (~C[4] & C[0]);
 308     A[2][4] = C[4] ^ (~C[0] & C[1]);
 309
 310     C[0] = ROL64(T[0][4],        rhotates[0][4]);
 311     C[1] = ROL64(T[1][0],        rhotates[1][0]);
 312     C[2] = ROL64(T[1][1],        rhotates[2][1]); /* originally A[2][1] */
 313     C[3] = ROL64(A[3][2] ^ D[2], rhotates[3][2]);
 314     C[4] = ROL64(A[4][3] ^ D[3], rhotates[4][3]);
 315
 316     A[3][0] = C[0] ^ (~C[1] & C[2]);
 317     A[3][1] = C[1] ^ (~C[2] & C[3]);
 318     A[3][2] = C[2] ^ (~C[3] & C[4]);
 319     A[3][3] = C[3] ^ (~C[4] & C[0]);
 320     A[3][4] = C[4] ^ (~C[0] & C[1]);
 321
 322     C[0] = ROL64(T[0][2],        rhotates[0][2]);
 323     C[1] = ROL64(T[1][3],        rhotates[1][3]);
 324     C[2] = ROL64(T[1][4],        rhotates[2][4]); /* originally A[2][4] */
 325     C[3] = ROL64(T[0][0],        rhotates[3][0]); /* originally A[3][0] */
 326     C[4] = ROL64(A[4][1] ^ D[1], rhotates[4][1]);
 327
 328     A[4][0] = C[0] ^ (~C[1] & C[2]);
 329     A[4][1] = C[1] ^ (~C[2] & C[3]);
 330     A[4][2] = C[2] ^ (~C[3] & C[4]);
 331     A[4][3] = C[3] ^ (~C[4] & C[0]);
 332     A[4][4] = C[4] ^ (~C[0] & C[1]);
 333 }
 334
 335 void KeccakF1600(uint64_t A[5][5])
 336 {
 337     size_t i;
 338
 339     for (i = 0; i < 24; i++) {
 340         Round(A, i);
 341     }
 342 }
 343
 344 #elif defined(KECCAK_2X)
 345 /*
 346  * This implementation is variant of KECCAK_1X above with outer-most
 347  * round loop unrolled twice. This allows to take temporary storage
 348  * out of round procedure and simplify references to it by alternating
 349  * it with actual data (see round loop below). Just like original, it's
 350  * rather meant as reference for an assembly implementation. It's likely
 351  * to provide best instruction per processed byte ratio at minimal
 352  * round unroll factor...
 353  */
 354 static void Round(uint64_t R[5][5], uint64_t A[5][5], size_t i)
 355 {
 356     uint64_t C[5], D[5];
 357
 358     assert(i < (sizeof(iotas) / sizeof(iotas[0])));
 359
 360     C[0] = A[0][0] ^ A[1][0] ^ A[2][0] ^ A[3][0] ^ A[4][0];
 361     C[1] = A[0][1] ^ A[1][1] ^ A[2][1] ^ A[3][1] ^ A[4][1];
 362     C[2] = A[0][2] ^ A[1][2] ^ A[2][2] ^ A[3][2] ^ A[4][2];
 363     C[3] = A[0][3] ^ A[1][3] ^ A[2][3] ^ A[3][3] ^ A[4][3];
 364     C[4] = A[0][4] ^ A[1][4] ^ A[2][4] ^ A[3][4] ^ A[4][4];
 365
 366     D[0] = ROL64(C[1], 1) ^ C[4];
 367     D[1] = ROL64(C[2], 1) ^ C[0];
 368     D[2] = ROL64(C[3], 1) ^ C[1];
 369     D[3] = ROL64(C[4], 1) ^ C[2];
 370     D[4] = ROL64(C[0], 1) ^ C[3];
 371
 372     C[0] =       A[0][0] ^ D[0]; /* rotate by 0 */
 373     C[1] = ROL64(A[1][1] ^ D[1], rhotates[1][1]);
 374     C[2] = ROL64(A[2][2] ^ D[2], rhotates[2][2]);
 375     C[3] = ROL64(A[3][3] ^ D[3], rhotates[3][3]);
 376     C[4] = ROL64(A[4][4] ^ D[4], rhotates[4][4]);
 377
 378 #ifdef KECCAK_COMPLEMENTING_TRANSFORM
 379     R[0][0] = C[0] ^ ( C[1] | C[2]) ^ iotas[i];
 380     R[0][1] = C[1] ^ (~C[2] | C[3]);
 381     R[0][2] = C[2] ^ ( C[3] & C[4]);
 382     R[0][3] = C[3] ^ ( C[4] | C[0]);
 383     R[0][4] = C[4] ^ ( C[0] & C[1]);
 384 #else
 385     R[0][0] = C[0] ^ (~C[1] & C[2]) ^ iotas[i];
 386     R[0][1] = C[1] ^ (~C[2] & C[3]);
 387     R[0][2] = C[2] ^ (~C[3] & C[4]);
 388     R[0][3] = C[3] ^ (~C[4] & C[0]);
 389     R[0][4] = C[4] ^ (~C[0] & C[1]);
 390 #endif
 391
 392     C[0] = ROL64(A[0][3] ^ D[3], rhotates[0][3]);
 393     C[1] = ROL64(A[1][4] ^ D[4], rhotates[1][4]);
 394     C[2] = ROL64(A[2][0] ^ D[0], rhotates[2][0]);
 395     C[3] = ROL64(A[3][1] ^ D[1], rhotates[3][1]);
 396     C[4] = ROL64(A[4][2] ^ D[2], rhotates[4][2]);
 397
 398 #ifdef KECCAK_COMPLEMENTING_TRANSFORM
 399     R[1][0] = C[0] ^ (C[1] |  C[2]);
 400     R[1][1] = C[1] ^ (C[2] &  C[3]);
 401     R[1][2] = C[2] ^ (C[3] | ~C[4]);
 402     R[1][3] = C[3] ^ (C[4] |  C[0]);
 403     R[1][4] = C[4] ^ (C[0] &  C[1]);
 404 #else
 405     R[1][0] = C[0] ^ (~C[1] & C[2]);
 406     R[1][1] = C[1] ^ (~C[2] & C[3]);
 407     R[1][2] = C[2] ^ (~C[3] & C[4]);
 408     R[1][3] = C[3] ^ (~C[4] & C[0]);
 409     R[1][4] = C[4] ^ (~C[0] & C[1]);
 410 #endif
 411
 412     C[0] = ROL64(A[0][1] ^ D[1], rhotates[0][1]);
 413     C[1] = ROL64(A[1][2] ^ D[2], rhotates[1][2]);
 414     C[2] = ROL64(A[2][3] ^ D[3], rhotates[2][3]);
 415     C[3] = ROL64(A[3][4] ^ D[4], rhotates[3][4]);
 416     C[4] = ROL64(A[4][0] ^ D[0], rhotates[4][0]);
 417
 418 #ifdef KECCAK_COMPLEMENTING_TRANSFORM
 419     R[2][0] =  C[0] ^ ( C[1] | C[2]);
 420     R[2][1] =  C[1] ^ ( C[2] & C[3]);
 421     R[2][2] =  C[2] ^ (~C[3] & C[4]);
 422     R[2][3] = ~C[3] ^ ( C[4] | C[0]);
 423     R[2][4] =  C[4] ^ ( C[0] & C[1]);
 424 #else
 425     R[2][0] = C[0] ^ (~C[1] & C[2]);
 426     R[2][1] = C[1] ^ (~C[2] & C[3]);
 427     R[2][2] = C[2] ^ (~C[3] & C[4]);
 428     R[2][3] = C[3] ^ (~C[4] & C[0]);
 429     R[2][4] = C[4] ^ (~C[0] & C[1]);
 430 #endif
 431
 432     C[0] = ROL64(A[0][4] ^ D[4], rhotates[0][4]);
 433     C[1] = ROL64(A[1][0] ^ D[0], rhotates[1][0]);
 434     C[2] = ROL64(A[2][1] ^ D[1], rhotates[2][1]);
 435     C[3] = ROL64(A[3][2] ^ D[2], rhotates[3][2]);
 436     C[4] = ROL64(A[4][3] ^ D[3], rhotates[4][3]);
 437
 438 #ifdef KECCAK_COMPLEMENTING_TRANSFORM
 439     R[3][0] =  C[0] ^ ( C[1] & C[2]);
 440     R[3][1] =  C[1] ^ ( C[2] | C[3]);
 441     R[3][2] =  C[2] ^ (~C[3] | C[4]);
 442     R[3][3] = ~C[3] ^ ( C[4] & C[0]);
 443     R[3][4] =  C[4] ^ ( C[0] | C[1]);
 444 #else
 445     R[3][0] = C[0] ^ (~C[1] & C[2]);
 446     R[3][1] = C[1] ^ (~C[2] & C[3]);
 447     R[3][2] = C[2] ^ (~C[3] & C[4]);
 448     R[3][3] = C[3] ^ (~C[4] & C[0]);
 449     R[3][4] = C[4] ^ (~C[0] & C[1]);
 450 #endif
 451
 452     C[0] = ROL64(A[0][2] ^ D[2], rhotates[0][2]);
 453     C[1] = ROL64(A[1][3] ^ D[3], rhotates[1][3]);
 454     C[2] = ROL64(A[2][4] ^ D[4], rhotates[2][4]);
 455     C[3] = ROL64(A[3][0] ^ D[0], rhotates[3][0]);
 456     C[4] = ROL64(A[4][1] ^ D[1], rhotates[4][1]);
 457
 458 #ifdef KECCAK_COMPLEMENTING_TRANSFORM
 459     R[4][0] =  C[0] ^ (~C[1] & C[2]);
 460     R[4][1] = ~C[1] ^ ( C[2] | C[3]);
 461     R[4][2] =  C[2] ^ ( C[3] & C[4]);
 462     R[4][3] =  C[3] ^ ( C[4] | C[0]);
 463     R[4][4] =  C[4] ^ ( C[0] & C[1]);
 464 #else
 465     R[4][0] = C[0] ^ (~C[1] & C[2]);
 466     R[4][1] = C[1] ^ (~C[2] & C[3]);
 467     R[4][2] = C[2] ^ (~C[3] & C[4]);
 468     R[4][3] = C[3] ^ (~C[4] & C[0]);
 469     R[4][4] = C[4] ^ (~C[0] & C[1]);
 470 #endif
 471 }
 472
 473 void KeccakF1600(uint64_t A[5][5])
 474 {
 475     uint64_t T[5][5];
 476     size_t i;
 477
 478 #ifdef KECCAK_COMPLEMENTING_TRANSFORM
 479     A[0][1] = ~A[0][1];
 480     A[0][2] = ~A[0][2];
 481     A[1][3] = ~A[1][3];
 482     A[2][2] = ~A[2][2];
 483     A[3][2] = ~A[3][2];
 484     A[4][0] = ~A[4][0];
 485 #endif
 486
 487     for (i = 0; i < 24; i += 2) {
 488         Round(T, A, i);
 489         Round(A, T, i + 1);
 490     }
 491
 492 #ifdef KECCAK_COMPLEMENTING_TRANSFORM
 493     A[0][1] = ~A[0][1];
 494     A[0][2] = ~A[0][2];
 495     A[1][3] = ~A[1][3];
 496     A[2][2] = ~A[2][2];
 497     A[3][2] = ~A[3][2];
 498     A[4][0] = ~A[4][0];
 499 #endif
 500 }
 501
 502 #else
 503 /*
 504  * This implementation is KECCAK_1X from above combined 4 times with
 505  * a twist that allows to omit temporary storage and perform in-place
 506  * processing. It's discussed in section 2.5 of "Keccak implementation
 507  * overview". It's likely to be best suited for processors with large
 508  * register bank...
 509  */
 510 static void FourRounds(uint64_t A[5][5], size_t i)
 511 {
 512     uint64_t B[5], C[5], D[5];
 513
 514     assert(i <= (sizeof(iotas) / sizeof(iotas[0]) - 4));
 515
 516     /* Round 4*n */
 517     C[0] = A[0][0] ^ A[1][0] ^ A[2][0] ^ A[3][0] ^ A[4][0];
 518     C[1] = A[0][1] ^ A[1][1] ^ A[2][1] ^ A[3][1] ^ A[4][1];
 519     C[2] = A[0][2] ^ A[1][2] ^ A[2][2] ^ A[3][2] ^ A[4][2];
 520     C[3] = A[0][3] ^ A[1][3] ^ A[2][3] ^ A[3][3] ^ A[4][3];
 521     C[4] = A[0][4] ^ A[1][4] ^ A[2][4] ^ A[3][4] ^ A[4][4];
 522
 523     D[0] = ROL64(C[1], 1) ^ C[4];
 524     D[1] = ROL64(C[2], 1) ^ C[0];
 525     D[2] = ROL64(C[3], 1) ^ C[1];
 526     D[3] = ROL64(C[4], 1) ^ C[2];
 527     D[4] = ROL64(C[0], 1) ^ C[3];
 528
 529     B[0] =       A[0][0] ^ D[0]; /* rotate by 0 */
 530     B[1] = ROL64(A[1][1] ^ D[1], rhotates[1][1]);
 531     B[2] = ROL64(A[2][2] ^ D[2], rhotates[2][2]);
 532     B[3] = ROL64(A[3][3] ^ D[3], rhotates[3][3]);
 533     B[4] = ROL64(A[4][4] ^ D[4], rhotates[4][4]);
 534
 535     C[0] = A[0][0] = B[0] ^ (~B[1] & B[2]) ^ iotas[i];
 536     C[1] = A[1][1] = B[1] ^ (~B[2] & B[3]);
 537     C[2] = A[2][2] = B[2] ^ (~B[3] & B[4]);
 538     C[3] = A[3][3] = B[3] ^ (~B[4] & B[0]);
 539     C[4] = A[4][4] = B[4] ^ (~B[0] & B[1]);
 540
 541     B[0] = ROL64(A[0][3] ^ D[3], rhotates[0][3]);
 542     B[1] = ROL64(A[1][4] ^ D[4], rhotates[1][4]);
 543     B[2] = ROL64(A[2][0] ^ D[0], rhotates[2][0]);
 544     B[3] = ROL64(A[3][1] ^ D[1], rhotates[3][1]);
 545     B[4] = ROL64(A[4][2] ^ D[2], rhotates[4][2]);
 546
 547     C[0] ^= A[2][0] = B[0] ^ (~B[1] & B[2]);
 548     C[1] ^= A[3][1] = B[1] ^ (~B[2] & B[3]);
 549     C[2] ^= A[4][2] = B[2] ^ (~B[3] & B[4]);
 550     C[3] ^= A[0][3] = B[3] ^ (~B[4] & B[0]);
 551     C[4] ^= A[1][4] = B[4] ^ (~B[0] & B[1]);
 552
 553     B[0] = ROL64(A[0][1] ^ D[1], rhotates[0][1]);
 554     B[1] = ROL64(A[1][2] ^ D[2], rhotates[1][2]);
 555     B[2] = ROL64(A[2][3] ^ D[3], rhotates[2][3]);
 556     B[3] = ROL64(A[3][4] ^ D[4], rhotates[3][4]);
 557     B[4] = ROL64(A[4][0] ^ D[0], rhotates[4][0]);
 558
 559     C[0] ^= A[4][0] = B[0] ^ (~B[1] & B[2]);
 560     C[1] ^= A[0][1] = B[1] ^ (~B[2] & B[3]);
 561     C[2] ^= A[1][2] = B[2] ^ (~B[3] & B[4]);
 562     C[3] ^= A[2][3] = B[3] ^ (~B[4] & B[0]);
 563     C[4] ^= A[3][4] = B[4] ^ (~B[0] & B[1]);
 564
 565     B[0] = ROL64(A[0][4] ^ D[4], rhotates[0][4]);
 566     B[1] = ROL64(A[1][0] ^ D[0], rhotates[1][0]);
 567     B[2] = ROL64(A[2][1] ^ D[1], rhotates[2][1]);
 568     B[3] = ROL64(A[3][2] ^ D[2], rhotates[3][2]);
 569     B[4] = ROL64(A[4][3] ^ D[3], rhotates[4][3]);
 570
 571     C[0] ^= A[1][0] = B[0] ^ (~B[1] & B[2]);
 572     C[1] ^= A[2][1] = B[1] ^ (~B[2] & B[3]);
 573     C[2] ^= A[3][2] = B[2] ^ (~B[3] & B[4]);
 574     C[3] ^= A[4][3] = B[3] ^ (~B[4] & B[0]);
 575     C[4] ^= A[0][4] = B[4] ^ (~B[0] & B[1]);
 576
 577     B[0] = ROL64(A[0][2] ^ D[2], rhotates[0][2]);
 578     B[1] = ROL64(A[1][3] ^ D[3], rhotates[1][3]);
 579     B[2] = ROL64(A[2][4] ^ D[4], rhotates[2][4]);
 580     B[3] = ROL64(A[3][0] ^ D[0], rhotates[3][0]);
 581     B[4] = ROL64(A[4][1] ^ D[1], rhotates[4][1]);
 582
 583     C[0] ^= A[3][0] = B[0] ^ (~B[1] & B[2]);
 584     C[1] ^= A[4][1] = B[1] ^ (~B[2] & B[3]);
 585     C[2] ^= A[0][2] = B[2] ^ (~B[3] & B[4]);
 586     C[3] ^= A[1][3] = B[3] ^ (~B[4] & B[0]);
 587     C[4] ^= A[2][4] = B[4] ^ (~B[0] & B[1]);
 588
 589     /* Round 4*n+1 */
 590     D[0] = ROL64(C[1], 1) ^ C[4];
 591     D[1] = ROL64(C[2], 1) ^ C[0];
 592     D[2] = ROL64(C[3], 1) ^ C[1];
 593     D[3] = ROL64(C[4], 1) ^ C[2];
 594     D[4] = ROL64(C[0], 1) ^ C[3];
 595
 596     B[0] =       A[0][0] ^ D[0]; /* rotate by 0 */
 597     B[1] = ROL64(A[3][1] ^ D[1], rhotates[1][1]);
 598     B[2] = ROL64(A[1][2] ^ D[2], rhotates[2][2]);
 599     B[3] = ROL64(A[4][3] ^ D[3], rhotates[3][3]);
 600     B[4] = ROL64(A[2][4] ^ D[4], rhotates[4][4]);
 601
 602     C[0] = A[0][0] = B[0] ^ (~B[1] & B[2]) ^ iotas[i + 1];
 603     C[1] = A[3][1] = B[1] ^ (~B[2] & B[3]);
 604     C[2] = A[1][2] = B[2] ^ (~B[3] & B[4]);
 605     C[3] = A[4][3] = B[3] ^ (~B[4] & B[0]);
 606     C[4] = A[2][4] = B[4] ^ (~B[0] & B[1]);
 607
 608     B[0] = ROL64(A[3][3] ^ D[3], rhotates[0][3]);
 609     B[1] = ROL64(A[1][4] ^ D[4], rhotates[1][4]);
 610     B[2] = ROL64(A[4][0] ^ D[0], rhotates[2][0]);
 611     B[3] = ROL64(A[2][1] ^ D[1], rhotates[3][1]);
 612     B[4] = ROL64(A[0][2] ^ D[2], rhotates[4][2]);
 613
 614     C[0] ^= A[4][0] = B[0] ^ (~B[1] & B[2]);
 615     C[1] ^= A[2][1] = B[1] ^ (~B[2] & B[3]);
 616     C[2] ^= A[0][2] = B[2] ^ (~B[3] & B[4]);
 617     C[3] ^= A[3][3] = B[3] ^ (~B[4] & B[0]);
 618     C[4] ^= A[1][4] = B[4] ^ (~B[0] & B[1]);
 619
 620     B[0] = ROL64(A[1][1] ^ D[1], rhotates[0][1]);
 621     B[1] = ROL64(A[4][2] ^ D[2], rhotates[1][2]);
 622     B[2] = ROL64(A[2][3] ^ D[3], rhotates[2][3]);
 623     B[3] = ROL64(A[0][4] ^ D[4], rhotates[3][4]);
 624     B[4] = ROL64(A[3][0] ^ D[0], rhotates[4][0]);
 625
 626     C[0] ^= A[3][0] = B[0] ^ (~B[1] & B[2]);
 627     C[1] ^= A[1][1] = B[1] ^ (~B[2] & B[3]);
 628     C[2] ^= A[4][2] = B[2] ^ (~B[3] & B[4]);
 629     C[3] ^= A[2][3] = B[3] ^ (~B[4] & B[0]);
 630     C[4] ^= A[0][4] = B[4] ^ (~B[0] & B[1]);
 631
 632     B[0] = ROL64(A[4][4] ^ D[4], rhotates[0][4]);
 633     B[1] = ROL64(A[2][0] ^ D[0], rhotates[1][0]);
 634     B[2] = ROL64(A[0][1] ^ D[1], rhotates[2][1]);
 635     B[3] = ROL64(A[3][2] ^ D[2], rhotates[3][2]);
 636     B[4] = ROL64(A[1][3] ^ D[3], rhotates[4][3]);
 637
 638     C[0] ^= A[2][0] = B[0] ^ (~B[1] & B[2]);
 639     C[1] ^= A[0][1] = B[1] ^ (~B[2] & B[3]);
 640     C[2] ^= A[3][2] = B[2] ^ (~B[3] & B[4]);
 641     C[3] ^= A[1][3] = B[3] ^ (~B[4] & B[0]);
 642     C[4] ^= A[4][4] = B[4] ^ (~B[0] & B[1]);
 643
 644     B[0] = ROL64(A[2][2] ^ D[2], rhotates[0][2]);
 645     B[1] = ROL64(A[0][3] ^ D[3], rhotates[1][3]);
 646     B[2] = ROL64(A[3][4] ^ D[4], rhotates[2][4]);
 647     B[3] = ROL64(A[1][0] ^ D[0], rhotates[3][0]);
 648     B[4] = ROL64(A[4][1] ^ D[1], rhotates[4][1]);
 649
 650     C[0] ^= A[1][0] = B[0] ^ (~B[1] & B[2]);
 651     C[1] ^= A[4][1] = B[1] ^ (~B[2] & B[3]);
 652     C[2] ^= A[2][2] = B[2] ^ (~B[3] & B[4]);
 653     C[3] ^= A[0][3] = B[3] ^ (~B[4] & B[0]);
 654     C[4] ^= A[3][4] = B[4] ^ (~B[0] & B[1]);
 655
 656     /* Round 4*n+2 */
 657     D[0] = ROL64(C[1], 1) ^ C[4];
 658     D[1] = ROL64(C[2], 1) ^ C[0];
 659     D[2] = ROL64(C[3], 1) ^ C[1];
 660     D[3] = ROL64(C[4], 1) ^ C[2];
 661     D[4] = ROL64(C[0], 1) ^ C[3];
 662
 663     B[0] =       A[0][0] ^ D[0]; /* rotate by 0 */
 664     B[1] = ROL64(A[2][1] ^ D[1], rhotates[1][1]);
 665     B[2] = ROL64(A[4][2] ^ D[2], rhotates[2][2]);
 666     B[3] = ROL64(A[1][3] ^ D[3], rhotates[3][3]);
 667     B[4] = ROL64(A[3][4] ^ D[4], rhotates[4][4]);
 668
 669     C[0] = A[0][0] = B[0] ^ (~B[1] & B[2]) ^ iotas[i + 2];
 670     C[1] = A[2][1] = B[1] ^ (~B[2] & B[3]);
 671     C[2] = A[4][2] = B[2] ^ (~B[3] & B[4]);
 672     C[3] = A[1][3] = B[3] ^ (~B[4] & B[0]);
 673     C[4] = A[3][4] = B[4] ^ (~B[0] & B[1]);
 674
 675     B[0] = ROL64(A[4][3] ^ D[3], rhotates[0][3]);
 676     B[1] = ROL64(A[1][4] ^ D[4], rhotates[1][4]);
 677     B[2] = ROL64(A[3][0] ^ D[0], rhotates[2][0]);
 678     B[3] = ROL64(A[0][1] ^ D[1], rhotates[3][1]);
 679     B[4] = ROL64(A[2][2] ^ D[2], rhotates[4][2]);
 680
 681     C[0] ^= A[3][0] = B[0] ^ (~B[1] & B[2]);
 682     C[1] ^= A[0][1] = B[1] ^ (~B[2] & B[3]);
 683     C[2] ^= A[2][2] = B[2] ^ (~B[3] & B[4]);
 684     C[3] ^= A[4][3] = B[3] ^ (~B[4] & B[0]);
 685     C[4] ^= A[1][4] = B[4] ^ (~B[0] & B[1]);
 686
 687     B[0] = ROL64(A[3][1] ^ D[1], rhotates[0][1]);
 688     B[1] = ROL64(A[0][2] ^ D[2], rhotates[1][2]);
 689     B[2] = ROL64(A[2][3] ^ D[3], rhotates[2][3]);
 690     B[3] = ROL64(A[4][4] ^ D[4], rhotates[3][4]);
 691     B[4] = ROL64(A[1][0] ^ D[0], rhotates[4][0]);
 692
 693     C[0] ^= A[1][0] = B[0] ^ (~B[1] & B[2]);
 694     C[1] ^= A[3][1] = B[1] ^ (~B[2] & B[3]);
 695     C[2] ^= A[0][2] = B[2] ^ (~B[3] & B[4]);
 696     C[3] ^= A[2][3] = B[3] ^ (~B[4] & B[0]);
 697     C[4] ^= A[4][4] = B[4] ^ (~B[0] & B[1]);
 698
 699     B[0] = ROL64(A[2][4] ^ D[4], rhotates[0][4]);
 700     B[1] = ROL64(A[4][0] ^ D[0], rhotates[1][0]);
 701     B[2] = ROL64(A[1][1] ^ D[1], rhotates[2][1]);
 702     B[3] = ROL64(A[3][2] ^ D[2], rhotates[3][2]);
 703     B[4] = ROL64(A[0][3] ^ D[3], rhotates[4][3]);
 704
 705     C[0] ^= A[4][0] = B[0] ^ (~B[1] & B[2]);
 706     C[1] ^= A[1][1] = B[1] ^ (~B[2] & B[3]);
 707     C[2] ^= A[3][2] = B[2] ^ (~B[3] & B[4]);
 708     C[3] ^= A[0][3] = B[3] ^ (~B[4] & B[0]);
 709     C[4] ^= A[2][4] = B[4] ^ (~B[0] & B[1]);
 710
 711     B[0] = ROL64(A[1][2] ^ D[2], rhotates[0][2]);
 712     B[1] = ROL64(A[3][3] ^ D[3], rhotates[1][3]);
 713     B[2] = ROL64(A[0][4] ^ D[4], rhotates[2][4]);
 714     B[3] = ROL64(A[2][0] ^ D[0], rhotates[3][0]);
 715     B[4] = ROL64(A[4][1] ^ D[1], rhotates[4][1]);
 716
 717     C[0] ^= A[2][0] = B[0] ^ (~B[1] & B[2]);
 718     C[1] ^= A[4][1] = B[1] ^ (~B[2] & B[3]);
 719     C[2] ^= A[1][2] = B[2] ^ (~B[3] & B[4]);
 720     C[3] ^= A[3][3] = B[3] ^ (~B[4] & B[0]);
 721     C[4] ^= A[0][4] = B[4] ^ (~B[0] & B[1]);
 722
 723     /* Round 4*n+3 */
 724     D[0] = ROL64(C[1], 1) ^ C[4];
 725     D[1] = ROL64(C[2], 1) ^ C[0];
 726     D[2] = ROL64(C[3], 1) ^ C[1];
 727     D[3] = ROL64(C[4], 1) ^ C[2];
 728     D[4] = ROL64(C[0], 1) ^ C[3];
 729
 730     B[0] =       A[0][0] ^ D[0]; /* rotate by 0 */
 731     B[1] = ROL64(A[0][1] ^ D[1], rhotates[1][1]);
 732     B[2] = ROL64(A[0][2] ^ D[2], rhotates[2][2]);
 733     B[3] = ROL64(A[0][3] ^ D[3], rhotates[3][3]);
 734     B[4] = ROL64(A[0][4] ^ D[4], rhotates[4][4]);
 735
 736     /* C[0] = */ A[0][0] = B[0] ^ (~B[1] & B[2]) ^ iotas[i + 3];
 737     /* C[1] = */ A[0][1] = B[1] ^ (~B[2] & B[3]);
 738     /* C[2] = */ A[0][2] = B[2] ^ (~B[3] & B[4]);
 739     /* C[3] = */ A[0][3] = B[3] ^ (~B[4] & B[0]);
 740     /* C[4] = */ A[0][4] = B[4] ^ (~B[0] & B[1]);
 741
 742     B[0] = ROL64(A[1][3] ^ D[3], rhotates[0][3]);
 743     B[1] = ROL64(A[1][4] ^ D[4], rhotates[1][4]);
 744     B[2] = ROL64(A[1][0] ^ D[0], rhotates[2][0]);
 745     B[3] = ROL64(A[1][1] ^ D[1], rhotates[3][1]);
 746     B[4] = ROL64(A[1][2] ^ D[2], rhotates[4][2]);
 747
 748     /* C[0] ^= */ A[1][0] = B[0] ^ (~B[1] & B[2]);
 749     /* C[1] ^= */ A[1][1] = B[1] ^ (~B[2] & B[3]);
 750     /* C[2] ^= */ A[1][2] = B[2] ^ (~B[3] & B[4]);
 751     /* C[3] ^= */ A[1][3] = B[3] ^ (~B[4] & B[0]);
 752     /* C[4] ^= */ A[1][4] = B[4] ^ (~B[0] & B[1]);
 753
 754     B[0] = ROL64(A[2][1] ^ D[1], rhotates[0][1]);
 755     B[1] = ROL64(A[2][2] ^ D[2], rhotates[1][2]);
 756     B[2] = ROL64(A[2][3] ^ D[3], rhotates[2][3]);
 757     B[3] = ROL64(A[2][4] ^ D[4], rhotates[3][4]);
 758     B[4] = ROL64(A[2][0] ^ D[0], rhotates[4][0]);
 759
 760     /* C[0] ^= */ A[2][0] = B[0] ^ (~B[1] & B[2]);
 761     /* C[1] ^= */ A[2][1] = B[1] ^ (~B[2] & B[3]);
 762     /* C[2] ^= */ A[2][2] = B[2] ^ (~B[3] & B[4]);
 763     /* C[3] ^= */ A[2][3] = B[3] ^ (~B[4] & B[0]);
 764     /* C[4] ^= */ A[2][4] = B[4] ^ (~B[0] & B[1]);
 765
 766     B[0] = ROL64(A[3][4] ^ D[4], rhotates[0][4]);
 767     B[1] = ROL64(A[3][0] ^ D[0], rhotates[1][0]);
 768     B[2] = ROL64(A[3][1] ^ D[1], rhotates[2][1]);
 769     B[3] = ROL64(A[3][2] ^ D[2], rhotates[3][2]);
 770     B[4] = ROL64(A[3][3] ^ D[3], rhotates[4][3]);
 771
 772     /* C[0] ^= */ A[3][0] = B[0] ^ (~B[1] & B[2]);
 773     /* C[1] ^= */ A[3][1] = B[1] ^ (~B[2] & B[3]);
 774     /* C[2] ^= */ A[3][2] = B[2] ^ (~B[3] & B[4]);
 775     /* C[3] ^= */ A[3][3] = B[3] ^ (~B[4] & B[0]);
 776     /* C[4] ^= */ A[3][4] = B[4] ^ (~B[0] & B[1]);
 777
 778     B[0] = ROL64(A[4][2] ^ D[2], rhotates[0][2]);
 779     B[1] = ROL64(A[4][3] ^ D[3], rhotates[1][3]);
 780     B[2] = ROL64(A[4][4] ^ D[4], rhotates[2][4]);
 781     B[3] = ROL64(A[4][0] ^ D[0], rhotates[3][0]);
 782     B[4] = ROL64(A[4][1] ^ D[1], rhotates[4][1]);
 783
 784     /* C[0] ^= */ A[4][0] = B[0] ^ (~B[1] & B[2]);
 785     /* C[1] ^= */ A[4][1] = B[1] ^ (~B[2] & B[3]);
 786     /* C[2] ^= */ A[4][2] = B[2] ^ (~B[3] & B[4]);
 787     /* C[3] ^= */ A[4][3] = B[3] ^ (~B[4] & B[0]);
 788     /* C[4] ^= */ A[4][4] = B[4] ^ (~B[0] & B[1]);
 789 }
 790
 791 void KeccakF1600(uint64_t A[5][5])
 792 {
 793     size_t i;
 794
 795     for (i = 0; i < 24; i += 4) {
 796         FourRounds(A, i);
 797     }
 798 }
 799
 800 #endif
 801
 802 static uint64_t BitInterleave(uint64_t Ai)
 803 {
 804     if (sizeof(void *) < 8) {
 805         uint32_t hi = 0, lo = 0;
 806         int j;
 807
 808         for (j = 0; j < 32; j++) {
 809             lo |= ((uint32_t)(Ai >> (2 * j))     & 1) << j;
 810             hi |= ((uint32_t)(Ai >> (2 * j + 1)) & 1) << j;
 811         }
 812
 813         Ai = ((uint64_t)hi << 32) | lo;
 814     }
 815
 816     return Ai;
 817 }
 818
 819 static uint64_t BitDeinterleave(uint64_t Ai)
 820 {
 821     if (sizeof(void *) < 8) {
 822         uint32_t hi = (uint32_t)(Ai >> 32), lo = (uint32_t)Ai;
 823         int j;
 824
 825         Ai = 0;
 826         for (j = 0; j < 32; j++) {
 827             Ai |= (uint64_t)((lo >> j) & 1) << (2 * j);
 828             Ai |= (uint64_t)((hi >> j) & 1) << (2 * j + 1);
 829         }
 830     }
 831
 832     return Ai;
 833 }
 834
 835 /*
 836  * SHA3_absorb can be called multiple times, but at each invocation
 837  * largest multiple of |r| out of |len| bytes are processed. Then
 838  * remaining amount of bytes is returned. This is done to spare caller
 839  * trouble of calculating the largest multiple of |r|. |r| can be viewed
 840  * as blocksize. It is commonly (1600 - 256*n)/8, e.g. 168, 136, 104,
 841  * 72, but can also be (1600 - 448)/8 = 144. All this means that message
 842  * padding and intermediate sub-block buffering, byte- or bitwise, is
 843  * caller's reponsibility.
 844  */
 845 size_t SHA3_absorb(uint64_t A[5][5], const unsigned char *inp, size_t len,
 846                    size_t r)
 847 {
 848     uint64_t *A_flat = (uint64_t *)A;
 849     size_t i, w = r / 8;
 850
 851     assert(r < (25 * sizeof(A[0][0])) && (r % 8) == 0);
 852
 853     while (len >= r) {
 854         for (i = 0; i < w; i++) {
 855             uint64_t Ai = (uint64_t)inp[0]       | (uint64_t)inp[1] << 8  |
 856                           (uint64_t)inp[2] << 16 | (uint64_t)inp[3] << 24 |
 857                           (uint64_t)inp[4] << 32 | (uint64_t)inp[5] << 40 |
 858                           (uint64_t)inp[6] << 48 | (uint64_t)inp[7] << 56;
 859             inp += 8;
 860
 861             A_flat[i] ^= BitInterleave(Ai);
 862         }
 863         KeccakF1600(A);
 864         len -= r;
 865     }
 866
 867     return len;
 868 }
 869
 870 /*
 871  * SHA3_squeeze is called once at the end to generate |out| hash value
 872  * of |len| bytes.
 873  */
 874 void SHA3_squeeze(uint64_t A[5][5], unsigned char *out, size_t len, size_t r)
 875 {
 876     uint64_t *A_flat = (uint64_t *)A;
 877     size_t i, rem, w = r / 8;
 878
 879     assert(r < (25 * sizeof(A[0][0])) && (r % 8) == 0);
 880
 881     while (len >= r) {
 882         for (i = 0; i < w; i++) {
 883             uint64_t Ai = BitDeinterleave(A_flat[i]);
 884
 885             out[0] = (unsigned char)(Ai);
 886             out[1] = (unsigned char)(Ai >> 8);
 887             out[2] = (unsigned char)(Ai >> 16);
 888             out[3] = (unsigned char)(Ai >> 24);
 889             out[4] = (unsigned char)(Ai >> 32);
 890             out[5] = (unsigned char)(Ai >> 40);
 891             out[6] = (unsigned char)(Ai >> 48);
 892             out[7] = (unsigned char)(Ai >> 56);
 893             out += 8;
 894         }
 895         len -= r;
 896         if (len)
 897             KeccakF1600(A);
 898     }
 899
 900     rem = len % 8;
 901     len /= 8;
 902
 903     for (i = 0; i < len; i++) {
 904         uint64_t Ai = BitDeinterleave(A_flat[i]);
 905
 906         out[0] = (unsigned char)(Ai);
 907         out[1] = (unsigned char)(Ai >> 8);
 908         out[2] = (unsigned char)(Ai >> 16);
 909         out[3] = (unsigned char)(Ai >> 24);
 910         out[4] = (unsigned char)(Ai >> 32);
 911         out[5] = (unsigned char)(Ai >> 40);
 912         out[6] = (unsigned char)(Ai >> 48);
 913         out[7] = (unsigned char)(Ai >> 56);
 914         out += 8;
 915     }
 916
 917     if (rem) {
 918         uint64_t Ai = BitDeinterleave(A_flat[i]);
 919
 920         for (i = 0; i < rem; i++) {
 921             *out++ = (unsigned char)Ai;
 922             Ai >>= 8;
 923         }
 924     }
 925 }
 926
 927 #ifdef SELFTEST
 928 /*
 929  * Post-padding one-shot implementations would look as following:
 930  *
 931  * SHA3_224     SHA3_sponge(inp, len, out, 224/8, (1600-448)/8);
 932  * SHA3_256     SHA3_sponge(inp, len, out, 256/8, (1600-512)/8);
 933  * SHA3_384     SHA3_sponge(inp, len, out, 384/8, (1600-768)/8);
 934  * SHA3_512     SHA3_sponge(inp, len, out, 512/8, (1600-1024)/8);
 935  * SHAKE_128    SHA3_sponge(inp, len, out, d, (1600-256)/8);
 936  * SHAKE_256    SHA3_sponge(inp, len, out, d, (1600-512)/8);
 937  */
 938
 939 void SHA3_sponge(const unsigned char *inp, size_t len,
 940                  unsigned char *out, size_t d, size_t r)
 941 {
 942     uint64_t A[5][5];
 943
 944     memset(A, 0, sizeof(A));
 945     SHA3_absorb(A, inp, len, r);
 946     SHA3_squeeze(A, out, d, r);
 947 }
 948
 949 # include <stdio.h>
 950
 951 int main()
 952 {
 953     /*
 954      * This is 5-bit SHAKE128 test from http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing
 955      */
 956     unsigned char test[168] = { '\xf3', '\x3' };
 957     unsigned char out[512];
 958     size_t i;
 959     static const unsigned char result[512] = {
 960         0x2E, 0x0A, 0xBF, 0xBA, 0x83, 0xE6, 0x72, 0x0B,
 961         0xFB, 0xC2, 0x25, 0xFF, 0x6B, 0x7A, 0xB9, 0xFF,
 962         0xCE, 0x58, 0xBA, 0x02, 0x7E, 0xE3, 0xD8, 0x98,
 963         0x76, 0x4F, 0xEF, 0x28, 0x7D, 0xDE, 0xCC, 0xCA,
 964         0x3E, 0x6E, 0x59, 0x98, 0x41, 0x1E, 0x7D, 0xDB,
 965         0x32, 0xF6, 0x75, 0x38, 0xF5, 0x00, 0xB1, 0x8C,
 966         0x8C, 0x97, 0xC4, 0x52, 0xC3, 0x70, 0xEA, 0x2C,
 967         0xF0, 0xAF, 0xCA, 0x3E, 0x05, 0xDE, 0x7E, 0x4D,
 968         0xE2, 0x7F, 0xA4, 0x41, 0xA9, 0xCB, 0x34, 0xFD,
 969         0x17, 0xC9, 0x78, 0xB4, 0x2D, 0x5B, 0x7E, 0x7F,
 970         0x9A, 0xB1, 0x8F, 0xFE, 0xFF, 0xC3, 0xC5, 0xAC,
 971         0x2F, 0x3A, 0x45, 0x5E, 0xEB, 0xFD, 0xC7, 0x6C,
 972         0xEA, 0xEB, 0x0A, 0x2C, 0xCA, 0x22, 0xEE, 0xF6,
 973         0xE6, 0x37, 0xF4, 0xCA, 0xBE, 0x5C, 0x51, 0xDE,
 974         0xD2, 0xE3, 0xFA, 0xD8, 0xB9, 0x52, 0x70, 0xA3,
 975         0x21, 0x84, 0x56, 0x64, 0xF1, 0x07, 0xD1, 0x64,
 976         0x96, 0xBB, 0x7A, 0xBF, 0xBE, 0x75, 0x04, 0xB6,
 977         0xED, 0xE2, 0xE8, 0x9E, 0x4B, 0x99, 0x6F, 0xB5,
 978         0x8E, 0xFD, 0xC4, 0x18, 0x1F, 0x91, 0x63, 0x38,
 979         0x1C, 0xBE, 0x7B, 0xC0, 0x06, 0xA7, 0xA2, 0x05,
 980         0x98, 0x9C, 0x52, 0x6C, 0xD1, 0xBD, 0x68, 0x98,
 981         0x36, 0x93, 0xB4, 0xBD, 0xC5, 0x37, 0x28, 0xB2,
 982         0x41, 0xC1, 0xCF, 0xF4, 0x2B, 0xB6, 0x11, 0x50,
 983         0x2C, 0x35, 0x20, 0x5C, 0xAB, 0xB2, 0x88, 0x75,
 984         0x56, 0x55, 0xD6, 0x20, 0xC6, 0x79, 0x94, 0xF0,
 985         0x64, 0x51, 0x18, 0x7F, 0x6F, 0xD1, 0x7E, 0x04,
 986         0x66, 0x82, 0xBA, 0x12, 0x86, 0x06, 0x3F, 0xF8,
 987         0x8F, 0xE2, 0x50, 0x8D, 0x1F, 0xCA, 0xF9, 0x03,
 988         0x5A, 0x12, 0x31, 0xAD, 0x41, 0x50, 0xA9, 0xC9,
 989         0xB2, 0x4C, 0x9B, 0x2D, 0x66, 0xB2, 0xAD, 0x1B,
 990         0xDE, 0x0B, 0xD0, 0xBB, 0xCB, 0x8B, 0xE0, 0x5B,
 991         0x83, 0x52, 0x29, 0xEF, 0x79, 0x19, 0x73, 0x73,
 992         0x23, 0x42, 0x44, 0x01, 0xE1, 0xD8, 0x37, 0xB6,
 993         0x6E, 0xB4, 0xE6, 0x30, 0xFF, 0x1D, 0xE7, 0x0C,
 994         0xB3, 0x17, 0xC2, 0xBA, 0xCB, 0x08, 0x00, 0x1D,
 995         0x34, 0x77, 0xB7, 0xA7, 0x0A, 0x57, 0x6D, 0x20,
 996         0x86, 0x90, 0x33, 0x58, 0x9D, 0x85, 0xA0, 0x1D,
 997         0xDB, 0x2B, 0x66, 0x46, 0xC0, 0x43, 0xB5, 0x9F,
 998         0xC0, 0x11, 0x31, 0x1D, 0xA6, 0x66, 0xFA, 0x5A,
 999         0xD1, 0xD6, 0x38, 0x7F, 0xA9, 0xBC, 0x40, 0x15,
1000         0xA3, 0x8A, 0x51, 0xD1, 0xDA, 0x1E, 0xA6, 0x1D,
1001         0x64, 0x8D, 0xC8, 0xE3, 0x9A, 0x88, 0xB9, 0xD6,
1002         0x22, 0xBD, 0xE2, 0x07, 0xFD, 0xAB, 0xC6, 0xF2,
1003         0x82, 0x7A, 0x88, 0x0C, 0x33, 0x0B, 0xBF, 0x6D,
1004         0xF7, 0x33, 0x77, 0x4B, 0x65, 0x3E, 0x57, 0x30,
1005         0x5D, 0x78, 0xDC, 0xE1, 0x12, 0xF1, 0x0A, 0x2C,
1006         0x71, 0xF4, 0xCD, 0xAD, 0x92, 0xED, 0x11, 0x3E,
1007         0x1C, 0xEA, 0x63, 0xB9, 0x19, 0x25, 0xED, 0x28,
1008         0x19, 0x1E, 0x6D, 0xBB, 0xB5, 0xAA, 0x5A, 0x2A,
1009         0xFD, 0xA5, 0x1F, 0xC0, 0x5A, 0x3A, 0xF5, 0x25,
1010         0x8B, 0x87, 0x66, 0x52, 0x43, 0x55, 0x0F, 0x28,
1011         0x94, 0x8A, 0xE2, 0xB8, 0xBE, 0xB6, 0xBC, 0x9C,
1012         0x77, 0x0B, 0x35, 0xF0, 0x67, 0xEA, 0xA6, 0x41,
1013         0xEF, 0xE6, 0x5B, 0x1A, 0x44, 0x90, 0x9D, 0x1B,
1014         0x14, 0x9F, 0x97, 0xEE, 0xA6, 0x01, 0x39, 0x1C,
1015         0x60, 0x9E, 0xC8, 0x1D, 0x19, 0x30, 0xF5, 0x7C,
1016         0x18, 0xA4, 0xE0, 0xFA, 0xB4, 0x91, 0xD1, 0xCA,
1017         0xDF, 0xD5, 0x04, 0x83, 0x44, 0x9E, 0xDC, 0x0F,
1018         0x07, 0xFF, 0xB2, 0x4D, 0x2C, 0x6F, 0x9A, 0x9A,
1019         0x3B, 0xFF, 0x39, 0xAE, 0x3D, 0x57, 0xF5, 0x60,
1020         0x65, 0x4D, 0x7D, 0x75, 0xC9, 0x08, 0xAB, 0xE6,
1021         0x25, 0x64, 0x75, 0x3E, 0xAC, 0x39, 0xD7, 0x50,
1022         0x3D, 0xA6, 0xD3, 0x7C, 0x2E, 0x32, 0xE1, 0xAF,
1023         0x3B, 0x8A, 0xEC, 0x8A, 0xE3, 0x06, 0x9C, 0xD9
1024     };
1025
1026     test[167] = '\x80';
1027     SHA3_sponge(test, sizeof(test), out, sizeof(out), sizeof(test));
1028
1029     /*
1030      * Rationale behind keeping output [formatted as below] is that
1031      * one should be able to redirect it to a file, then copy-n-paste
1032      * final "output val" from official example to another file, and
1033      * compare the two with diff(1).
1034      */
1035     for (i = 0; i < sizeof(out);) {
1036         printf("%02X", out[i]);
1037         printf(++i % 16 && i != sizeof(out) ? " " : "\n");
1038     }
1039
1040     if (memcmp(out,result,sizeof(out))) {
1041         fprintf(stderr,"failure\n");
1042         return 1;
1043     } else {
1044         fprintf(stderr,"success\n");
1045         return 0;
1046     }
1047 }
1048 #endif