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 <stdint.h>
  11 #include <string.h>
  12 #include <assert.h>
  13
  14 #define ROL64(a, offset) ((offset) ? (((a) << offset) | ((a) >> (64-offset))) \
  15                                    : a)
  16
  17 static void Theta(uint64_t A[5][5])
  18 {
  19     uint64_t C[5], D[5];
  20     size_t y;
  21
  22     C[0] = A[0][0] ^ A[1][0] ^ A[2][0] ^ A[3][0] ^ A[4][0];
  23     C[1] = A[0][1] ^ A[1][1] ^ A[2][1] ^ A[3][1] ^ A[4][1];
  24     C[2] = A[0][2] ^ A[1][2] ^ A[2][2] ^ A[3][2] ^ A[4][2];
  25     C[3] = A[0][3] ^ A[1][3] ^ A[2][3] ^ A[3][3] ^ A[4][3];
  26     C[4] = A[0][4] ^ A[1][4] ^ A[2][4] ^ A[3][4] ^ A[4][4];
  27
  28     D[0] = ROL64(C[1], 1) ^ C[4];
  29     D[1] = ROL64(C[2], 1) ^ C[0];
  30     D[2] = ROL64(C[3], 1) ^ C[1];
  31     D[3] = ROL64(C[4], 1) ^ C[2];
  32     D[4] = ROL64(C[0], 1) ^ C[3];
  33
  34     for (y = 0; y < 5; y++) {
  35         A[y][0] ^= D[0];
  36         A[y][1] ^= D[1];
  37         A[y][2] ^= D[2];
  38         A[y][3] ^= D[3];
  39         A[y][4] ^= D[4];
  40     }
  41 }
  42
  43 static void Rho(uint64_t A[5][5])
  44 {
  45     static const unsigned char rhotates[5][5] = {
  46         {  0,  1, 62, 28, 27 },
  47         { 36, 44,  6, 55, 20 },
  48         {  3, 10, 43, 25, 39 },
  49         { 41, 45, 15, 21,  8 },
  50         { 18,  2, 61, 56, 14 }
  51     };
  52     size_t y;
  53
  54     for (y = 0; y < 5; y++) {
  55         A[y][0] = ROL64(A[y][0], rhotates[y][0]);
  56         A[y][1] = ROL64(A[y][1], rhotates[y][1]);
  57         A[y][2] = ROL64(A[y][2], rhotates[y][2]);
  58         A[y][3] = ROL64(A[y][3], rhotates[y][3]);
  59         A[y][4] = ROL64(A[y][4], rhotates[y][4]);
  60     }
  61 }
  62
  63 static void Pi(uint64_t A[5][5])
  64 {
  65     uint64_t T[5][5];
  66
  67     /*
  68      * T = A
  69      * A[y][x] = T[x][(3*y+x)%5]
  70      */
  71     memcpy(T, A, sizeof(T));
  72
  73     A[0][0] = T[0][0];
  74     A[0][1] = T[1][1];
  75     A[0][2] = T[2][2];
  76     A[0][3] = T[3][3];
  77     A[0][4] = T[4][4];
  78
  79     A[1][0] = T[0][3];
  80     A[1][1] = T[1][4];
  81     A[1][2] = T[2][0];
  82     A[1][3] = T[3][1];
  83     A[1][4] = T[4][2];
  84
  85     A[2][0] = T[0][1];
  86     A[2][1] = T[1][2];
  87     A[2][2] = T[2][3];
  88     A[2][3] = T[3][4];
  89     A[2][4] = T[4][0];
  90
  91     A[3][0] = T[0][4];
  92     A[3][1] = T[1][0];
  93     A[3][2] = T[2][1];
  94     A[3][3] = T[3][2];
  95     A[3][4] = T[4][3];
  96
  97     A[4][0] = T[0][2];
  98     A[4][1] = T[1][3];
  99     A[4][2] = T[2][4];
 100     A[4][3] = T[3][0];
 101     A[4][4] = T[4][1];
 102 }
 103
 104 static void Chi(uint64_t A[5][5])
 105 {
 106     uint64_t C[5];
 107     size_t y;
 108
 109     for (y = 0; y < 5; y++) {
 110         C[0] = A[y][0] ^ (~A[y][1] & A[y][2]);
 111         C[1] = A[y][1] ^ (~A[y][2] & A[y][3]);
 112         C[2] = A[y][2] ^ (~A[y][3] & A[y][4]);
 113         C[3] = A[y][3] ^ (~A[y][4] & A[y][0]);
 114         C[4] = A[y][4] ^ (~A[y][0] & A[y][1]);
 115
 116         A[y][0] = C[0];
 117         A[y][1] = C[1];
 118         A[y][2] = C[2];
 119         A[y][3] = C[3];
 120         A[y][4] = C[4];
 121     }
 122 }
 123
 124 static void Iota(uint64_t A[5][5], size_t i)
 125 {
 126     static const uint64_t iotas[] = {
 127         0x0000000000000001U, 0x0000000000008082U, 0x800000000000808aU,
 128         0x8000000080008000U, 0x000000000000808bU, 0x0000000080000001U,
 129         0x8000000080008081U, 0x8000000000008009U, 0x000000000000008aU,
 130         0x0000000000000088U, 0x0000000080008009U, 0x000000008000000aU,
 131         0x000000008000808bU, 0x800000000000008bU, 0x8000000000008089U,
 132         0x8000000000008003U, 0x8000000000008002U, 0x8000000000000080U,
 133         0x000000000000800aU, 0x800000008000000aU, 0x8000000080008081U,
 134         0x8000000000008080U, 0x0000000080000001U, 0x8000000080008008U
 135     };
 136
 137     assert(i < (sizeof(iotas) / sizeof(iotas[0])));
 138     A[0][0] ^= iotas[i];
 139 }
 140
 141 void KeccakF1600(uint64_t A[5][5])
 142 {
 143     size_t i;
 144
 145     for (i = 0; i < 24; i++) {
 146         Theta(A);
 147         Rho(A);
 148         Pi(A);
 149         Chi(A);
 150         Iota(A, i);
 151     }
 152 }
 153
 154 /*
 155  * SHA3_absorb can be called multiple times, but at each invocation
 156  * largest multiple of |r| out of |len| bytes are processed. Then
 157  * remaining amount of bytes are returned. This is done to spare caller
 158  * trouble of calculating the largest multiple of |r|, effectively the
 159  * blocksize. It is commonly (1600 - 256*n)/8, e.g. 168, 136, 104, 72,
 160  * but can also be (1600 - 448)/8 = 144. All this means that message
 161  * padding and intermediate sub-block buffering, byte- or bitwise, is
 162  * caller's reponsibility.
 163  */
 164 size_t SHA3_absorb(uint64_t A[5][5], const unsigned char *inp, size_t len,
 165                    size_t r)
 166 {
 167     uint64_t *A_flat = (uint64_t *)A;
 168     size_t i, w = r / 8;
 169
 170     assert(r < (25 * sizeof(A[0][0])) && (r % 8) == 0);
 171
 172     while (len >= r) {
 173         for (i = 0; i < w; i++) {
 174             A_flat[i] ^= (uint64_t)inp[0]       | (uint64_t)inp[1] << 8  |
 175                          (uint64_t)inp[2] << 16 | (uint64_t)inp[3] << 24 |
 176                          (uint64_t)inp[4] << 32 | (uint64_t)inp[5] << 40 |
 177                          (uint64_t)inp[6] << 48 | (uint64_t)inp[7] << 56;
 178             inp += 8;
 179         }
 180         KeccakF1600(A);
 181         len -= r;
 182     }
 183
 184     return len;
 185 }
 186
 187 /*
 188  * SHA3_squeeze is called once at the end to generate |out| hash value
 189  * of |len| bytes.
 190  */
 191 void SHA3_squeeze(uint64_t A[5][5], unsigned char *out, size_t len, size_t r)
 192 {
 193     uint64_t *A_flat = (uint64_t *)A;
 194     size_t i, rem, w = r / 8;
 195
 196     assert(r < (25 * sizeof(A[0][0])) && (r % 8) == 0);
 197
 198     while (len >= r) {
 199         for (i = 0; i < w; i++) {
 200             uint64_t Ai = A_flat[i];
 201
 202             out[0] = (unsigned char)(Ai);
 203             out[1] = (unsigned char)(Ai >> 8);
 204             out[2] = (unsigned char)(Ai >> 16);
 205             out[3] = (unsigned char)(Ai >> 24);
 206             out[4] = (unsigned char)(Ai >> 32);
 207             out[5] = (unsigned char)(Ai >> 40);
 208             out[6] = (unsigned char)(Ai >> 48);
 209             out[7] = (unsigned char)(Ai >> 56);
 210             out += 8;
 211         }
 212         len -= r;
 213         if (len)
 214             KeccakF1600(A);
 215     }
 216
 217     rem = len % 8;
 218     len /= 8;
 219
 220     for (i = 0; i < len; i++) {
 221         uint64_t Ai = A_flat[i];
 222
 223         out[0] = (unsigned char)(Ai);
 224         out[1] = (unsigned char)(Ai >> 8);
 225         out[2] = (unsigned char)(Ai >> 16);
 226         out[3] = (unsigned char)(Ai >> 24);
 227         out[4] = (unsigned char)(Ai >> 32);
 228         out[5] = (unsigned char)(Ai >> 40);
 229         out[6] = (unsigned char)(Ai >> 48);
 230         out[7] = (unsigned char)(Ai >> 56);
 231         out += 8;
 232     }
 233
 234     if (rem) {
 235         uint64_t Ai = A_flat[i];
 236
 237         for (i = 0; i < rem; i++) {
 238             *out++ = (unsigned char)Ai;
 239             Ai >>= 8;
 240         }
 241     }
 242 }
 243
 244 #ifdef SELFTEST
 245 /*
 246  * Post-padding one-shot implementations would look as following:
 247  *
 248  * SHA3_224     SHA3_sponge(inp, len, out, 224/8, (1600-448)/8);
 249  * SHA3_256     SHA3_sponge(inp, len, out, 256/8, (1600-512)/8);
 250  * SHA3_384     SHA3_sponge(inp, len, out, 384/8, (1600-768)/8);
 251  * SHA3_512     SHA3_sponge(inp, len, out, 512/8, (1600-1024)/8);
 252  * SHAKE_128    SHA3_sponge(inp, len, out, d, (1600-256)/8);
 253  * SHAKE_256    SHA3_sponge(inp, len, out, d, (1600-512)/8);
 254  */
 255
 256 void SHA3_sponge(const unsigned char *inp, size_t len,
 257                  unsigned char *out, size_t d, size_t r)
 258 {
 259     uint64_t A[5][5];
 260
 261     memset(A, 0, sizeof(A));
 262     SHA3_absorb(A, inp, len, r);
 263     SHA3_squeeze(A, out, d, r);
 264 }
 265
 266 # include <stdio.h>
 267
 268 int main()
 269 {
 270     /*
 271      * This is 5-bit SHAKE128 test from http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing
 272      */
 273     unsigned char test[168] = { '\xf3', '\x3' };
 274     unsigned char out[512];
 275     size_t i;
 276     static const unsigned char result[512] = {
 277         0x2E, 0x0A, 0xBF, 0xBA, 0x83, 0xE6, 0x72, 0x0B,
 278         0xFB, 0xC2, 0x25, 0xFF, 0x6B, 0x7A, 0xB9, 0xFF,
 279         0xCE, 0x58, 0xBA, 0x02, 0x7E, 0xE3, 0xD8, 0x98,
 280         0x76, 0x4F, 0xEF, 0x28, 0x7D, 0xDE, 0xCC, 0xCA,
 281         0x3E, 0x6E, 0x59, 0x98, 0x41, 0x1E, 0x7D, 0xDB,
 282         0x32, 0xF6, 0x75, 0x38, 0xF5, 0x00, 0xB1, 0x8C,
 283         0x8C, 0x97, 0xC4, 0x52, 0xC3, 0x70, 0xEA, 0x2C,
 284         0xF0, 0xAF, 0xCA, 0x3E, 0x05, 0xDE, 0x7E, 0x4D,
 285         0xE2, 0x7F, 0xA4, 0x41, 0xA9, 0xCB, 0x34, 0xFD,
 286         0x17, 0xC9, 0x78, 0xB4, 0x2D, 0x5B, 0x7E, 0x7F,
 287         0x9A, 0xB1, 0x8F, 0xFE, 0xFF, 0xC3, 0xC5, 0xAC,
 288         0x2F, 0x3A, 0x45, 0x5E, 0xEB, 0xFD, 0xC7, 0x6C,
 289         0xEA, 0xEB, 0x0A, 0x2C, 0xCA, 0x22, 0xEE, 0xF6,
 290         0xE6, 0x37, 0xF4, 0xCA, 0xBE, 0x5C, 0x51, 0xDE,
 291         0xD2, 0xE3, 0xFA, 0xD8, 0xB9, 0x52, 0x70, 0xA3,
 292         0x21, 0x84, 0x56, 0x64, 0xF1, 0x07, 0xD1, 0x64,
 293         0x96, 0xBB, 0x7A, 0xBF, 0xBE, 0x75, 0x04, 0xB6,
 294         0xED, 0xE2, 0xE8, 0x9E, 0x4B, 0x99, 0x6F, 0xB5,
 295         0x8E, 0xFD, 0xC4, 0x18, 0x1F, 0x91, 0x63, 0x38,
 296         0x1C, 0xBE, 0x7B, 0xC0, 0x06, 0xA7, 0xA2, 0x05,
 297         0x98, 0x9C, 0x52, 0x6C, 0xD1, 0xBD, 0x68, 0x98,
 298         0x36, 0x93, 0xB4, 0xBD, 0xC5, 0x37, 0x28, 0xB2,
 299         0x41, 0xC1, 0xCF, 0xF4, 0x2B, 0xB6, 0x11, 0x50,
 300         0x2C, 0x35, 0x20, 0x5C, 0xAB, 0xB2, 0x88, 0x75,
 301         0x56, 0x55, 0xD6, 0x20, 0xC6, 0x79, 0x94, 0xF0,
 302         0x64, 0x51, 0x18, 0x7F, 0x6F, 0xD1, 0x7E, 0x04,
 303         0x66, 0x82, 0xBA, 0x12, 0x86, 0x06, 0x3F, 0xF8,
 304         0x8F, 0xE2, 0x50, 0x8D, 0x1F, 0xCA, 0xF9, 0x03,
 305         0x5A, 0x12, 0x31, 0xAD, 0x41, 0x50, 0xA9, 0xC9,
 306         0xB2, 0x4C, 0x9B, 0x2D, 0x66, 0xB2, 0xAD, 0x1B,
 307         0xDE, 0x0B, 0xD0, 0xBB, 0xCB, 0x8B, 0xE0, 0x5B,
 308         0x83, 0x52, 0x29, 0xEF, 0x79, 0x19, 0x73, 0x73,
 309         0x23, 0x42, 0x44, 0x01, 0xE1, 0xD8, 0x37, 0xB6,
 310         0x6E, 0xB4, 0xE6, 0x30, 0xFF, 0x1D, 0xE7, 0x0C,
 311         0xB3, 0x17, 0xC2, 0xBA, 0xCB, 0x08, 0x00, 0x1D,
 312         0x34, 0x77, 0xB7, 0xA7, 0x0A, 0x57, 0x6D, 0x20,
 313         0x86, 0x90, 0x33, 0x58, 0x9D, 0x85, 0xA0, 0x1D,
 314         0xDB, 0x2B, 0x66, 0x46, 0xC0, 0x43, 0xB5, 0x9F,
 315         0xC0, 0x11, 0x31, 0x1D, 0xA6, 0x66, 0xFA, 0x5A,
 316         0xD1, 0xD6, 0x38, 0x7F, 0xA9, 0xBC, 0x40, 0x15,
 317         0xA3, 0x8A, 0x51, 0xD1, 0xDA, 0x1E, 0xA6, 0x1D,
 318         0x64, 0x8D, 0xC8, 0xE3, 0x9A, 0x88, 0xB9, 0xD6,
 319         0x22, 0xBD, 0xE2, 0x07, 0xFD, 0xAB, 0xC6, 0xF2,
 320         0x82, 0x7A, 0x88, 0x0C, 0x33, 0x0B, 0xBF, 0x6D,
 321         0xF7, 0x33, 0x77, 0x4B, 0x65, 0x3E, 0x57, 0x30,
 322         0x5D, 0x78, 0xDC, 0xE1, 0x12, 0xF1, 0x0A, 0x2C,
 323         0x71, 0xF4, 0xCD, 0xAD, 0x92, 0xED, 0x11, 0x3E,
 324         0x1C, 0xEA, 0x63, 0xB9, 0x19, 0x25, 0xED, 0x28,
 325         0x19, 0x1E, 0x6D, 0xBB, 0xB5, 0xAA, 0x5A, 0x2A,
 326         0xFD, 0xA5, 0x1F, 0xC0, 0x5A, 0x3A, 0xF5, 0x25,
 327         0x8B, 0x87, 0x66, 0x52, 0x43, 0x55, 0x0F, 0x28,
 328         0x94, 0x8A, 0xE2, 0xB8, 0xBE, 0xB6, 0xBC, 0x9C,
 329         0x77, 0x0B, 0x35, 0xF0, 0x67, 0xEA, 0xA6, 0x41,
 330         0xEF, 0xE6, 0x5B, 0x1A, 0x44, 0x90, 0x9D, 0x1B,
 331         0x14, 0x9F, 0x97, 0xEE, 0xA6, 0x01, 0x39, 0x1C,
 332         0x60, 0x9E, 0xC8, 0x1D, 0x19, 0x30, 0xF5, 0x7C,
 333         0x18, 0xA4, 0xE0, 0xFA, 0xB4, 0x91, 0xD1, 0xCA,
 334         0xDF, 0xD5, 0x04, 0x83, 0x44, 0x9E, 0xDC, 0x0F,
 335         0x07, 0xFF, 0xB2, 0x4D, 0x2C, 0x6F, 0x9A, 0x9A,
 336         0x3B, 0xFF, 0x39, 0xAE, 0x3D, 0x57, 0xF5, 0x60,
 337         0x65, 0x4D, 0x7D, 0x75, 0xC9, 0x08, 0xAB, 0xE6,
 338         0x25, 0x64, 0x75, 0x3E, 0xAC, 0x39, 0xD7, 0x50,
 339         0x3D, 0xA6, 0xD3, 0x7C, 0x2E, 0x32, 0xE1, 0xAF,
 340         0x3B, 0x8A, 0xEC, 0x8A, 0xE3, 0x06, 0x9C, 0xD9
 341     };
 342
 343     test[167] = '\x80';
 344     SHA3_sponge(test, sizeof(test), out, sizeof(out), sizeof(test));
 345
 346     /*
 347      * Rationale behind keeping output [formatted as below] is that
 348      * one should be able to redirect it to a file, then copy-n-paste
 349      * final "output val" from official example to another file, and
 350      * compare the two with diff(1).
 351      */
 352     for (i = 0; i < sizeof(out);) {
 353         printf("%02X", out[i]);
 354         printf(++i % 16 && i != sizeof(out) ? " " : "\n");
 355     }
 356
 357     if (memcmp(out,result,sizeof(out))) {
 358         fprintf(stderr,"failure\n");
 359         return 1;
 360     } else {
 361         fprintf(stderr,"success\n");
 362         return 0;
 363     }
 364 }
 365 #endif