1 /* $NetBSD: keccak.c,v 1.1 2017/11/30 05:47:24 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2015 Taylor R. Campbell 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 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29 #include <sys/cdefs.h> 30 31 #if defined(_KERNEL) || defined(_STANDALONE) 32 __KERNEL_RCSID(0, "$NetBSD: keccak.c,v 1.1 2017/11/30 05:47:24 riastradh Exp $"); 33 34 #include <sys/types.h> 35 #else 36 __RCSID("$NetBSD: keccak.c,v 1.1 2017/11/30 05:47:24 riastradh Exp $"); 37 38 #include <stdint.h> 39 #endif 40 41 #include "keccak.h" 42 43 #define secret /* can't use in variable-time operations, should zero */ 44 45 #define FOR5(X, STMT) do \ 46 { \ 47 (X) = 0; STMT; \ 48 (X) = 1; STMT; \ 49 (X) = 2; STMT; \ 50 (X) = 3; STMT; \ 51 (X) = 4; STMT; \ 52 } while (0) 53 54 static inline secret uint64_t 55 rol64(secret uint64_t v, unsigned c) 56 { 57 58 return ((v << c) | (v >> (64 - c))); 59 } 60 61 static inline void 62 keccakf1600_theta(secret uint64_t A[25]) 63 { 64 secret uint64_t C0, C1, C2, C3, C4; 65 unsigned y; 66 67 C0 = C1 = C2 = C3 = C4 = 0; 68 FOR5(y, { 69 C0 ^= A[0 + 5*y]; 70 C1 ^= A[1 + 5*y]; 71 C2 ^= A[2 + 5*y]; 72 C3 ^= A[3 + 5*y]; 73 C4 ^= A[4 + 5*y]; 74 }); 75 FOR5(y, { 76 A[0 + 5*y] ^= C4 ^ rol64(C1, 1); 77 A[1 + 5*y] ^= C0 ^ rol64(C2, 1); 78 A[2 + 5*y] ^= C1 ^ rol64(C3, 1); 79 A[3 + 5*y] ^= C2 ^ rol64(C4, 1); 80 A[4 + 5*y] ^= C3 ^ rol64(C0, 1); 81 }); 82 } 83 84 static inline void 85 keccakf1600_rho_pi(secret uint64_t A[25]) 86 { 87 secret uint64_t T, U; 88 89 /* 90 * Permute by (x,y) |---> (y, 2x + 3y mod 5) starting at (1,0), 91 * rotate the ith element by (i + 1)(i + 2)/2 mod 64. 92 */ 93 U = A[ 1]; T = U; 94 U = A[10]; A[10] = rol64(T, 1); T = U; 95 U = A[ 7]; A[ 7] = rol64(T, 3); T = U; 96 U = A[11]; A[11] = rol64(T, 6); T = U; 97 U = A[17]; A[17] = rol64(T, 10); T = U; 98 U = A[18]; A[18] = rol64(T, 15); T = U; 99 U = A[ 3]; A[ 3] = rol64(T, 21); T = U; 100 U = A[ 5]; A[ 5] = rol64(T, 28); T = U; 101 U = A[16]; A[16] = rol64(T, 36); T = U; 102 U = A[ 8]; A[ 8] = rol64(T, 45); T = U; 103 U = A[21]; A[21] = rol64(T, 55); T = U; 104 U = A[24]; A[24] = rol64(T, 2); T = U; 105 U = A[ 4]; A[ 4] = rol64(T, 14); T = U; 106 U = A[15]; A[15] = rol64(T, 27); T = U; 107 U = A[23]; A[23] = rol64(T, 41); T = U; 108 U = A[19]; A[19] = rol64(T, 56); T = U; 109 U = A[13]; A[13] = rol64(T, 8); T = U; 110 U = A[12]; A[12] = rol64(T, 25); T = U; 111 U = A[ 2]; A[ 2] = rol64(T, 43); T = U; 112 U = A[20]; A[20] = rol64(T, 62); T = U; 113 U = A[14]; A[14] = rol64(T, 18); T = U; 114 U = A[22]; A[22] = rol64(T, 39); T = U; 115 U = A[ 9]; A[ 9] = rol64(T, 61); T = U; 116 U = A[ 6]; A[ 6] = rol64(T, 20); T = U; 117 A[ 1] = rol64(T, 44); 118 } 119 120 static inline void 121 keccakf1600_chi(secret uint64_t A[25]) 122 { 123 secret uint64_t B0, B1, B2, B3, B4; 124 unsigned y; 125 126 FOR5(y, { 127 B0 = A[0 + 5*y]; 128 B1 = A[1 + 5*y]; 129 B2 = A[2 + 5*y]; 130 B3 = A[3 + 5*y]; 131 B4 = A[4 + 5*y]; 132 A[0 + 5*y] ^= ~B1 & B2; 133 A[1 + 5*y] ^= ~B2 & B3; 134 A[2 + 5*y] ^= ~B3 & B4; 135 A[3 + 5*y] ^= ~B4 & B0; 136 A[4 + 5*y] ^= ~B0 & B1; 137 }); 138 } 139 140 static void 141 keccakf1600_round(secret uint64_t A[25]) 142 { 143 144 keccakf1600_theta(A); 145 keccakf1600_rho_pi(A); 146 keccakf1600_chi(A); 147 } 148 149 void 150 keccakf1600(secret uint64_t A[25]) 151 { 152 /* 153 * RC[i] = \sum_{j = 0,...,6} rc(j + 7i) 2^(2^j - 1), 154 * rc(t) = (x^t mod x^8 + x^6 + x^5 + x^4 + 1) mod x in GF(2)[x] 155 */ 156 static const uint64_t RC[24] = { 157 0x0000000000000001ULL, 158 0x0000000000008082ULL, 159 0x800000000000808aULL, 160 0x8000000080008000ULL, 161 0x000000000000808bULL, 162 0x0000000080000001ULL, 163 0x8000000080008081ULL, 164 0x8000000000008009ULL, 165 0x000000000000008aULL, 166 0x0000000000000088ULL, 167 0x0000000080008009ULL, 168 0x000000008000000aULL, 169 0x000000008000808bULL, 170 0x800000000000008bULL, 171 0x8000000000008089ULL, 172 0x8000000000008003ULL, 173 0x8000000000008002ULL, 174 0x8000000000000080ULL, 175 0x000000000000800aULL, 176 0x800000008000000aULL, 177 0x8000000080008081ULL, 178 0x8000000000008080ULL, 179 0x0000000080000001ULL, 180 0x8000000080008008ULL, 181 }; 182 unsigned i; 183 184 for (i = 0; i < 24; i++) { 185 keccakf1600_round(A); 186 A[0] ^= RC[i]; 187 } 188 } 189