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     while (len >= r) {
 171         for (i = 0; i < w; i++) {
 172             A_flat[i] ^= (uint64_t)inp[0]       | (uint64_t)inp[1] << 8  |
 173                          (uint64_t)inp[2] << 16 | (uint64_t)inp[3] << 24 |
 174                          (uint64_t)inp[4] << 32 | (uint64_t)inp[5] << 40 |
 175                          (uint64_t)inp[6] << 48 | (uint64_t)inp[7] << 56;
 176             inp += 8;
 177         }
 178         KeccakF1600(A);
 179         len -= r;
 180     }
 181
 182     return len;
 183 }
 184
 185 /*
 186  * SHA3_squeeze is called once at the end to generate |out| hash value
 187  * of |len| bytes.
 188  */
 189 void SHA3_squeeze(uint64_t A[5][5], unsigned char *out, size_t len, size_t r)
 190 {
 191     uint64_t *A_flat = (uint64_t *)A;
 192     size_t i, rem, w = r / 8;
 193
 194     while (len >= r) {
 195         for (i = 0; i < w; i++) {
 196             uint64_t Ai = A_flat[i];
 197
 198             out[0] = (unsigned char)(Ai);
 199             out[1] = (unsigned char)(Ai >> 8);
 200             out[2] = (unsigned char)(Ai >> 16);
 201             out[3] = (unsigned char)(Ai >> 24);
 202             out[4] = (unsigned char)(Ai >> 32);
 203             out[5] = (unsigned char)(Ai >> 40);
 204             out[6] = (unsigned char)(Ai >> 48);
 205             out[7] = (unsigned char)(Ai >> 56);
 206             out += 8;
 207         }
 208         len -= r;
 209         if (len)
 210             KeccakF1600(A);
 211     }
 212
 213     rem = len % 8;
 214     len /= 8;
 215
 216     for (i = 0; i < len; i++) {
 217         uint64_t Ai = A_flat[i];
 218
 219         out[0] = (unsigned char)(Ai);
 220         out[1] = (unsigned char)(Ai >> 8);
 221         out[2] = (unsigned char)(Ai >> 16);
 222         out[3] = (unsigned char)(Ai >> 24);
 223         out[4] = (unsigned char)(Ai >> 32);
 224         out[5] = (unsigned char)(Ai >> 40);
 225         out[6] = (unsigned char)(Ai >> 48);
 226         out[7] = (unsigned char)(Ai >> 56);
 227         out += 8;
 228     }
 229
 230     if (rem) {
 231         uint64_t Ai = A_flat[i];
 232
 233         for (i = 0; i < rem; i++) {
 234             *out++ = (unsigned char)Ai;
 235             Ai >>= 8;
 236         }
 237     }
 238 }
 239
 240 #ifdef SELFTEST
 241 /*
 242  * Post-padding one-shot implementations would look as following:
 243  *
 244  * SHA3_224     SHA3_sponge(inp, len, out, 224/8, (1600-448)/8);
 245  * SHA3_256     SHA3_sponge(inp, len, out, 256/8, (1600-512)/8);
 246  * SHA3_384     SHA3_sponge(inp, len, out, 384/8, (1600-768)/8);
 247  * SHA3_512     SHA3_sponge(inp, len, out, 512/8, (1600-1024)/8);
 248  * SHAKE_128    SHA3_sponge(inp, len, out, d, (1600-256)/8);
 249  * SHAKE_256    SHA3_sponge(inp, len, out, d, (1600-512)/8);
 250  */
 251
 252 void SHA3_sponge(const unsigned char *inp, size_t len,
 253                  unsigned char *out, size_t d, size_t r)
 254 {
 255     uint64_t A[5][5];
 256
 257     memset(A, 0, sizeof(A));
 258     SHA3_absorb(A, inp, len, r);
 259     SHA3_squeeze(A, out, d, r);
 260 }
 261
 262 # include <stdio.h>
 263
 264 int main()
 265 {
 266     unsigned char test[168] = { '\xf3', '\x3' };
 267     unsigned char out[512];
 268     size_t i;
 269
 270     /*
 271      * This is 5-bit SHAKE128 test from http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing
 272      */
 273     test[167] = '\x80';
 274     SHA3_sponge(test, sizeof(test), out, sizeof(out), sizeof(test));
 275
 276     for (i = 0; i < sizeof(out);) {
 277         printf("%02X", out[i]);
 278         printf(++i % 16 && i != sizeof(out) ? " " : "\n");
 279     }
 280 }
 281 #endif