Debian Codegraph @

crypto/sha3/keccak.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3 // (c) 2023 Nicholas Rodrigues Lordello <[email protected]>
4
5 use bytes;
6 use crypto::math;
7 use endian;
8
9 // The Keccak-p[1600,24] permutation function (also referred to as
10 // Keccak-f[1600]). This is an implementation of Algorithm 7 from FIPS 202 for
11 // b = 1600 and nr = 24.
12 fn keccakf(a: *[25]u64) void = {
13 let b: [25]u64 = [0...];
14 let c: [5]u64 = [0...];
15 let d: [5]u64 = [0...];
16
17 for (const rc .. RC) {
18 // π ∘ ρ ∘ θ:
19 c[0] = a[0] ^ a[5] ^ a[10] ^ a[15] ^ a[20];
20 c[1] = a[1] ^ a[6] ^ a[11] ^ a[16] ^ a[21];
21 c[2] = a[2] ^ a[7] ^ a[12] ^ a[17] ^ a[22];
22 c[3] = a[3] ^ a[8] ^ a[13] ^ a[18] ^ a[23];
23 c[4] = a[4] ^ a[9] ^ a[14] ^ a[19] ^ a[24];
24 d[0] = c[4] ^ math::rotl64(c[1], 1);
25 d[1] = c[0] ^ math::rotl64(c[2], 1);
26 d[2] = c[1] ^ math::rotl64(c[3], 1);
27 d[3] = c[2] ^ math::rotl64(c[4], 1);
28 d[4] = c[3] ^ math::rotl64(c[0], 1);
29 b[0] = a[0] ^ d[0];
30 b[1] = math::rotl64(a[6] ^ d[1], 44);
31 b[2] = math::rotl64(a[12] ^ d[2], 43);
32 b[3] = math::rotl64(a[18] ^ d[3], 21);
33 b[4] = math::rotl64(a[24] ^ d[4], 14);
34 b[5] = math::rotl64(a[3] ^ d[3], 28);
35 b[6] = math::rotl64(a[9] ^ d[4], 20);
36 b[7] = math::rotl64(a[10] ^ d[0], 3);
37 b[8] = math::rotl64(a[16] ^ d[1], 45);
38 b[9] = math::rotl64(a[22] ^ d[2], 61);
39 b[10] = math::rotl64(a[1] ^ d[1], 1);
40 b[11] = math::rotl64(a[7] ^ d[2], 6);
41 b[12] = math::rotl64(a[13] ^ d[3], 25);
42 b[13] = math::rotl64(a[19] ^ d[4], 8);
43 b[14] = math::rotl64(a[20] ^ d[0], 18);
44 b[15] = math::rotl64(a[4] ^ d[4], 27);
45 b[16] = math::rotl64(a[5] ^ d[0], 36);
46 b[17] = math::rotl64(a[11] ^ d[1], 10);
47 b[18] = math::rotl64(a[17] ^ d[2], 15);
48 b[19] = math::rotl64(a[23] ^ d[3], 56);
49 b[20] = math::rotl64(a[2] ^ d[2], 62);
50 b[21] = math::rotl64(a[8] ^ d[3], 55);
51 b[22] = math::rotl64(a[14] ^ d[4], 39);
52 b[23] = math::rotl64(a[15] ^ d[0], 41);
53 b[24] = math::rotl64(a[21] ^ d[1], 2);
54
55 // ι ∘ χ:
56 a[0] = b[0] ^ (~b[1] & b[2]) ^ rc;
57 a[1] = b[1] ^ (~b[2] & b[3]);
58 a[2] = b[2] ^ (~b[3] & b[4]);
59 a[3] = b[3] ^ (~b[4] & b[0]);
60 a[4] = b[4] ^ (~b[0] & b[1]);
61 a[5] = b[5] ^ (~b[6] & b[7]);
62 a[6] = b[6] ^ (~b[7] & b[8]);
63 a[7] = b[7] ^ (~b[8] & b[9]);
64 a[8] = b[8] ^ (~b[9] & b[5]);
65 a[9] = b[9] ^ (~b[5] & b[6]);
66 a[10] = b[10] ^ (~b[11] & b[12]);
67 a[11] = b[11] ^ (~b[12] & b[13]);
68 a[12] = b[12] ^ (~b[13] & b[14]);
69 a[13] = b[13] ^ (~b[14] & b[10]);
70 a[14] = b[14] ^ (~b[10] & b[11]);
71 a[15] = b[15] ^ (~b[16] & b[17]);
72 a[16] = b[16] ^ (~b[17] & b[18]);
73 a[17] = b[17] ^ (~b[18] & b[19]);
74 a[18] = b[18] ^ (~b[19] & b[15]);
75 a[19] = b[19] ^ (~b[15] & b[16]);
76 a[20] = b[20] ^ (~b[21] & b[22]);
77 a[21] = b[21] ^ (~b[22] & b[23]);
78 a[22] = b[22] ^ (~b[23] & b[24]);
79 a[23] = b[23] ^ (~b[24] & b[20]);
80 a[24] = b[24] ^ (~b[20] & b[21]);
81 };
82 };
83
84 // Pre-computed RC values per round index for the ι step. See Algorithms 5 and 6
85 // from FIPS 202.
86 const RC: [24]u64 = [
87 0x0000000000000001,
88 0x0000000000008082,
89 0x800000000000808a,
90 0x8000000080008000,
91 0x000000000000808b,
92 0x0000000080000001,
93 0x8000000080008081,
94 0x8000000000008009,
95 0x000000000000008a,
96 0x0000000000000088,
97 0x0000000080008009,
98 0x000000008000000a,
99 0x000000008000808b,
100 0x800000000000008b,
101 0x8000000000008089,
102 0x8000000000008003,
103 0x8000000000008002,
104 0x8000000000000080,
105 0x000000000000800a,
106 0x800000008000000a,
107 0x8000000080008081,
108 0x8000000000008080,
109 0x0000000080000001,
110 0x8000000080008008,
111 ];
112
113 // The Keccak sponge function is definied in Algorithm 8 from FIPS 202. The
114 // implementation here is split between the [[absorb]], [[pad]] and [[squeeze]]
115 // functions to allow streaming input into and output from the [[sponge]]:
116 //
117 // let e = sponge { ... };
118 // absorb(&e, input[..]);
119 // absorb(&e, input[..]);
120 // // ...
121 // pad(&e);
122 // squeeze(&e, output[..]);
123 // squeeze(&e, output[..]);
124 // // ...
125 //
126 // The shared [[sponge]] state contains fields:
127 // - rate: the number of input bytes processed or output bytes generated at a
128 // time.
129 // - ds: The domain separation byte for the sponge construction instance
130 // **including** the first bit of padding. Different domain separators are
131 // used for hashing and XOFs. See Table 6 from FIPS 202.
132 // - s: The 1600-bit/200-byte state of the sponge, stored as an array of u64s
133 // ready for the [[keccakf]] permutation function.
134 // - pos: The position in bytes to continue writing to (in case the sponge is
135 // [[absorb]]-ing) or reading from (in case the sponge is [[squeeze]]-ing).
136
137 export type sponge = struct {
138 rate: size,
139 ds: u8,
140 s: [25]u64,
141 pos: size,
142 };
143
144 // Absorb some data into the sponge. This function must not be called after
145 // [[pad]]-ing or [[squeeze]]-ing data from the sponge.
146 fn absorb(e: *sponge, data: const []u8) void = {
147 let d = data[..];
148 for (len(d) > 0) {
149 if (e.pos & 7 == 0 && len(d) >= 8) {
150 // fast-path: if we are at a 64-bit boundary and have a
151 // full 64-bit word to write.
152 e.s[e.pos >> 3] ^= endian::legetu64(d);
153 e.pos += 8;
154 d = d[8..];
155 } else {
156 // slow-path.
157 let buf: [8]u8 = [0...];
158 let o = e.pos & 7;
159 let n = 8 - o;
160 if (n > len(d)) {
161 n = len(d);
162 };
163 buf[o..][..n] = d[..n];
164 e.s[e.pos >> 3] ^= endian::legetu64(buf);
165 e.pos += n;
166 d = d[n..];
167 };
168
169 if (e.pos == e.rate) {
170 keccakf(&e.s);
171 e.pos = 0;
172 };
173 assert(e.pos < e.rate);
174 };
175 };
176
177 // Write the domain separation string and pad the input to the sponge. This
178 // function must only be called once, and before [[squeeze]]-ing data from the
179 // sponge. See Appendix B.2 from FIPS 202.
180 fn pad(e: *sponge) void = {
181 let sb = &e.s: *[200]u8;
182 sb[e.pos] ^= e.ds;
183 sb[e.rate - 1] ^= 0x80;
184 keccakf(&e.s);
185 e.pos = 0;
186 };
187
188 // Sqeeze some data out of the sponge. This function must not be called before
189 // [[pad]]-ing the sponge.
190 fn squeeze(e: *sponge, data: []u8) void = {
191 let d = data[..];
192 for (len(d) > 0) {
193 if (e.pos == e.rate) {
194 keccakf(&e.s);
195 e.pos = 0;
196 };
197 assert(e.pos < e.rate);
198
199 if (e.pos & 7 == 0 && len(d) >= 8) {
200 // fast-path: if we are at a 64-bit boundary and have a
201 // full 64-bit word to read.
202 endian::leputu64(d, e.s[e.pos >> 3]);
203 e.pos += 8;
204 d = d[8..];
205 } else {
206 // slow-path.
207 let buf: [8]u8 = [0...];
208 endian::leputu64(buf[..], e.s[e.pos >> 3]);
209 let o = e.pos & 7;
210 let n = 8 - o;
211 if (n > len(d)) {
212 n = len(d);
213 };
214 d[..n] = buf[o..][..n];
215 e.pos += n;
216 d = d[n..];
217 };
218 };
219 };
220
221 // Resets a sponge to its initial state.
222 fn reset(e: *sponge) void = {
223 let sb = &e.s: *[200]u8;
224 bytes::zero(sb[..]);
225 e.pos = 0;
226 };