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     /*
 267      * This is 5-bit SHAKE128 test from http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing
 268      */
 269     unsigned char test[168] = { '\xf3', '\x3' };
 270     unsigned char out[512];
 271     size_t i;
 272     static const unsigned char result[512] = {
 273         0x2E, 0x0A, 0xBF, 0xBA, 0x83, 0xE6, 0x72, 0x0B,
 274         0xFB, 0xC2, 0x25, 0xFF, 0x6B, 0x7A, 0xB9, 0xFF,
 275         0xCE, 0x58, 0xBA, 0x02, 0x7E, 0xE3, 0xD8, 0x98,
 276         0x76, 0x4F, 0xEF, 0x28, 0x7D, 0xDE, 0xCC, 0xCA,
 277         0x3E, 0x6E, 0x59, 0x98, 0x41, 0x1E, 0x7D, 0xDB,
 278         0x32, 0xF6, 0x75, 0x38, 0xF5, 0x00, 0xB1, 0x8C,
 279         0x8C, 0x97, 0xC4, 0x52, 0xC3, 0x70, 0xEA, 0x2C,
 280         0xF0, 0xAF, 0xCA, 0x3E, 0x05, 0xDE, 0x7E, 0x4D,
 281         0xE2, 0x7F, 0xA4, 0x41, 0xA9, 0xCB, 0x34, 0xFD,
 282         0x17, 0xC9, 0x78, 0xB4, 0x2D, 0x5B, 0x7E, 0x7F,
 283         0x9A, 0xB1, 0x8F, 0xFE, 0xFF, 0xC3, 0xC5, 0xAC,
 284         0x2F, 0x3A, 0x45, 0x5E, 0xEB, 0xFD, 0xC7, 0x6C,
 285         0xEA, 0xEB, 0x0A, 0x2C, 0xCA, 0x22, 0xEE, 0xF6,
 286         0xE6, 0x37, 0xF4, 0xCA, 0xBE, 0x5C, 0x51, 0xDE,
 287         0xD2, 0xE3, 0xFA, 0xD8, 0xB9, 0x52, 0x70, 0xA3,
 288         0x21, 0x84, 0x56, 0x64, 0xF1, 0x07, 0xD1, 0x64,
 289         0x96, 0xBB, 0x7A, 0xBF, 0xBE, 0x75, 0x04, 0xB6,
 290         0xED, 0xE2, 0xE8, 0x9E, 0x4B, 0x99, 0x6F, 0xB5,
 291         0x8E, 0xFD, 0xC4, 0x18, 0x1F, 0x91, 0x63, 0x38,
 292         0x1C, 0xBE, 0x7B, 0xC0, 0x06, 0xA7, 0xA2, 0x05,
 293         0x98, 0x9C, 0x52, 0x6C, 0xD1, 0xBD, 0x68, 0x98,
 294         0x36, 0x93, 0xB4, 0xBD, 0xC5, 0x37, 0x28, 0xB2,
 295         0x41, 0xC1, 0xCF, 0xF4, 0x2B, 0xB6, 0x11, 0x50,
 296         0x2C, 0x35, 0x20, 0x5C, 0xAB, 0xB2, 0x88, 0x75,
 297         0x56, 0x55, 0xD6, 0x20, 0xC6, 0x79, 0x94, 0xF0,
 298         0x64, 0x51, 0x18, 0x7F, 0x6F, 0xD1, 0x7E, 0x04,
 299         0x66, 0x82, 0xBA, 0x12, 0x86, 0x06, 0x3F, 0xF8,
 300         0x8F, 0xE2, 0x50, 0x8D, 0x1F, 0xCA, 0xF9, 0x03,
 301         0x5A, 0x12, 0x31, 0xAD, 0x41, 0x50, 0xA9, 0xC9,
 302         0xB2, 0x4C, 0x9B, 0x2D, 0x66, 0xB2, 0xAD, 0x1B,
 303         0xDE, 0x0B, 0xD0, 0xBB, 0xCB, 0x8B, 0xE0, 0x5B,
 304         0x83, 0x52, 0x29, 0xEF, 0x79, 0x19, 0x73, 0x73,
 305         0x23, 0x42, 0x44, 0x01, 0xE1, 0xD8, 0x37, 0xB6,
 306         0x6E, 0xB4, 0xE6, 0x30, 0xFF, 0x1D, 0xE7, 0x0C,
 307         0xB3, 0x17, 0xC2, 0xBA, 0xCB, 0x08, 0x00, 0x1D,
 308         0x34, 0x77, 0xB7, 0xA7, 0x0A, 0x57, 0x6D, 0x20,
 309         0x86, 0x90, 0x33, 0x58, 0x9D, 0x85, 0xA0, 0x1D,
 310         0xDB, 0x2B, 0x66, 0x46, 0xC0, 0x43, 0xB5, 0x9F,
 311         0xC0, 0x11, 0x31, 0x1D, 0xA6, 0x66, 0xFA, 0x5A,
 312         0xD1, 0xD6, 0x38, 0x7F, 0xA9, 0xBC, 0x40, 0x15,
 313         0xA3, 0x8A, 0x51, 0xD1, 0xDA, 0x1E, 0xA6, 0x1D,
 314         0x64, 0x8D, 0xC8, 0xE3, 0x9A, 0x88, 0xB9, 0xD6,
 315         0x22, 0xBD, 0xE2, 0x07, 0xFD, 0xAB, 0xC6, 0xF2,
 316         0x82, 0x7A, 0x88, 0x0C, 0x33, 0x0B, 0xBF, 0x6D,
 317         0xF7, 0x33, 0x77, 0x4B, 0x65, 0x3E, 0x57, 0x30,
 318         0x5D, 0x78, 0xDC, 0xE1, 0x12, 0xF1, 0x0A, 0x2C,
 319         0x71, 0xF4, 0xCD, 0xAD, 0x92, 0xED, 0x11, 0x3E,
 320         0x1C, 0xEA, 0x63, 0xB9, 0x19, 0x25, 0xED, 0x28,
 321         0x19, 0x1E, 0x6D, 0xBB, 0xB5, 0xAA, 0x5A, 0x2A,
 322         0xFD, 0xA5, 0x1F, 0xC0, 0x5A, 0x3A, 0xF5, 0x25,
 323         0x8B, 0x87, 0x66, 0x52, 0x43, 0x55, 0x0F, 0x28,
 324         0x94, 0x8A, 0xE2, 0xB8, 0xBE, 0xB6, 0xBC, 0x9C,
 325         0x77, 0x0B, 0x35, 0xF0, 0x67, 0xEA, 0xA6, 0x41,
 326         0xEF, 0xE6, 0x5B, 0x1A, 0x44, 0x90, 0x9D, 0x1B,
 327         0x14, 0x9F, 0x97, 0xEE, 0xA6, 0x01, 0x39, 0x1C,
 328         0x60, 0x9E, 0xC8, 0x1D, 0x19, 0x30, 0xF5, 0x7C,
 329         0x18, 0xA4, 0xE0, 0xFA, 0xB4, 0x91, 0xD1, 0xCA,
 330         0xDF, 0xD5, 0x04, 0x83, 0x44, 0x9E, 0xDC, 0x0F,
 331         0x07, 0xFF, 0xB2, 0x4D, 0x2C, 0x6F, 0x9A, 0x9A,
 332         0x3B, 0xFF, 0x39, 0xAE, 0x3D, 0x57, 0xF5, 0x60,
 333         0x65, 0x4D, 0x7D, 0x75, 0xC9, 0x08, 0xAB, 0xE6,
 334         0x25, 0x64, 0x75, 0x3E, 0xAC, 0x39, 0xD7, 0x50,
 335         0x3D, 0xA6, 0xD3, 0x7C, 0x2E, 0x32, 0xE1, 0xAF,
 336         0x3B, 0x8A, 0xEC, 0x8A, 0xE3, 0x06, 0x9C, 0xD9
 337     };
 338
 339     test[167] = '\x80';
 340     SHA3_sponge(test, sizeof(test), out, sizeof(out), sizeof(test));
 341
 342     /*
 343      * Rationale behind keeping output [formatted as below] is that
 344      * one should be able to redirect it to a file, then copy-n-paste
 345      * final "output val" from official example to another file, and
 346      * compare the two with diff(1).
 347      */
 348     for (i = 0; i < sizeof(out);) {
 349         printf("%02X", out[i]);
 350         printf(++i % 16 && i != sizeof(out) ? " " : "\n");
 351     }
 352
 353     if (memcmp(out,result,sizeof(out))) {
 354         fprintf(stderr,"failure\n");
 355         return 1;
 356     } else {
 357         fprintf(stderr,"success\n");
 358         return 0;
 359     }
 360 }
 361 #endif