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
rol64(secret uint64_t v,unsigned c)55 rol64(secret uint64_t v, unsigned c)
56 {
57
58 return ((v << c) | (v >> (64 - c)));
59 }
60
61 static inline void
keccakf1600_theta(secret uint64_t A[25])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
keccakf1600_rho_pi(secret uint64_t A[25])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
keccakf1600_chi(secret uint64_t A[25])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
keccakf1600_round(secret uint64_t A[25])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
keccakf1600(secret uint64_t A[25])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