v

1
// Copyright (c) 2023 Kim Shrier. All rights reserved.
2
// Use of this source code is governed by an MIT license
3
// that can be found in the LICENSE file.
4
// Package sha3 implements the 512, 384, 256, and 224
5
// bit hash algorithms and the 128 and 256 bit
6
// extended output functions as defined in
7
// https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf.
8
// Last updated: August 2015
9
module sha3
10

11
import encoding.binary
12
import math.bits
13

14
// when the state is 1600 bits, a lane is 64 bits
15
type Lane = u64
16

17
// the state is a 5 x 5 array of lanes
18
struct State {
19
mut:
20
	a [5][5]Lane
21
}
22

23
// to_bytes converts the state into a byte array
24
//
25
// A 1600 bit state fits into 200 bytes.
26
//
27
// The state consists of 25 u64 values arranged in a
28
// 5 x 5 array.
29
//
30
// The state is not modified by this method.
31
@[direct_array_access]
32
fn (s State) to_bytes() []u8 {
33
	mut byte_array := []u8{len: 200, cap: 200}
34
	mut index := 0
35

36
	for y in 0 .. 5 {
37
		for x in 0 .. 5 {
38
			unsafe {
39
				$if little_endian {
40
					binary.little_endian_put_u64_at(mut byte_array, s.a[x][y], index)
41
				} $else {
42
					binary.big_endian_put_u64_at(mut byte_array, s.a[x][y], index)
43
				}
44
			}
45
			index += 8
46
		}
47
	}
48

49
	return byte_array
50
}
51

52
// from_bytes sets the state from an array of bytes
53
//
54
// A 1600 bit state fits into 200 bytes.  It is expected
55
// that the input byte array is 200 bytes long.
56
//
57
// All 25 u64 values are set from the input byte array.
58
@[direct_array_access]
59
fn (mut s State) from_bytes(byte_array []u8) {
60
	mut index := 0
61

62
	for y in 0 .. 5 {
63
		for x in 0 .. 5 {
64
			$if little_endian {
65
				s.a[x][y] = binary.little_endian_u64_at(byte_array, index)
66
			} $else {
67
				s.a[x][y] = binary.big_endian_u64_at(byte_array, index)
68
			}
69
			index += 8
70
		}
71
	}
72
}
73

74
// xor_bytes xor's an array of bytes into the state
75
//
76
// This is how new data gets absorbed into the sponge.
77
//
78
// It is expected that the length of the byte array is
79
// the same as the rate.  The rate is how many bytes
80
// can be absorbed at one permutation of the state.
81
//
82
// The rate must be less than the size of the state
83
// in bytes.
84
@[direct_array_access]
85
fn (mut s State) xor_bytes(byte_array []u8, rate int) {
86
	mut index := 0
87

88
	for y in 0 .. 5 {
89
		for x in 0 .. 5 {
90
			$if little_endian {
91
				s.a[x][y] ^= binary.little_endian_u64_at(byte_array, index)
92
			} $else {
93
				s.a[x][y] ^= binary.big_endian_u64_at(byte_array, index)
94
			}
95
			index += 8
96

97
			if index >= rate {
98
				return
99
			}
100
		}
101
	}
102
}
103

104
// kaccak_p_1600_24 performs 24 rounnds on a 1600 bit state.
105
//
106
// The loop is unrolled to get a little better performance.
107
fn (mut s State) kaccak_p_1600_24() {
108
	s.rnd(0)
109
	s.rnd(1)
110
	s.rnd(2)
111
	s.rnd(3)
112
	s.rnd(4)
113
	s.rnd(5)
114
	s.rnd(6)
115
	s.rnd(7)
116
	s.rnd(8)
117
	s.rnd(9)
118
	s.rnd(10)
119
	s.rnd(11)
120
	s.rnd(12)
121
	s.rnd(13)
122
	s.rnd(14)
123
	s.rnd(15)
124
	s.rnd(16)
125
	s.rnd(17)
126
	s.rnd(18)
127
	s.rnd(19)
128
	s.rnd(20)
129
	s.rnd(21)
130
	s.rnd(22)
131
	s.rnd(23)
132
}
133

134
// rnd is a single round of stepping functions.
135
//
136
// The definition of a round is the application of the stepping
137
// functions theta, rho, pi, chi, and iota, in order, on the
138
// state.  The round index also influences the outcome and is
139
// constrained to be 0 <= round_index < 24.
140
@[inline]
141
fn (mut s State) rnd(round_index int) {
142
	s.theta()
143
	s.rho()
144
	s.pi()
145
	s.chi()
146
	s.iota(round_index)
147
}
148

149
// theta is the first step mapping function.  It is defined as:
150
//
151
// 1. For all pairs (x, z) such that 0 <= x < 5 and 0 <= z < w, let
152
//    C[x, z] = A[x, 0, z] xor A[x, 1, z] xor A[x, 2, z] xor A[x, 3, z] xor A[x, 4, z].
153
// 2. For all pairs (x, z) such that 0 <= x < 5 and 0 <= z < w let
154
//    D[x, z] = C[(x-1) mod 5, z] xor C[(x+1) mod 5, (z – 1) mod w].
155
// 3. For all triples (x, y, z) such that 0 <= x < 5, 0 <= y < 5, and 0 <=≤ z < w, let
156
//    A′[x, y, z] = A[x, y, z] xor D[x, z].
157
//
158
// A is the 5 x 5 x w state matrix.  w is the number of bits in the z axis, 64 in our case.
159
//
160
// We can represent a lane from the state matrix as a u64 value and operate
161
// on all the bite in the lane with a single 64-bit operation.  And, since
162
// we represent a lane as a u64 value, we can reduce the state to a 2
163
// dimensional array of u64 values.
164
@[direct_array_access; inline]
165
fn (mut s State) theta() {
166
	// calculate the 5 intermediate C values
167
	mut c := [5]Lane{init: 0}
168
	for x in 0 .. 5 {
169
		for y in 0 .. 5 {
170
			c[x] ^= s.a[x][y]
171
		}
172
	}
173

174
	// calculate the 5 intermediate D values
175
	mut d := [5]Lane{init: 0}
176
	for x in 0 .. 5 {
177
		d[x] = bits.rotate_left_64(c[(x + 1) % 5], 1) ^ c[(x + 4) % 5]
178
	}
179

180
	// add the D values back into the state
181
	for x in 0 .. 5 {
182
		for y in 0 .. 5 {
183
			s.a[x][y] ^= d[x]
184
		}
185
	}
186
}
187

188
// rho_offsets are the amount of rotation to apply to a particular lane
189
// given its position in the state matrix.
190
const rho_offsets = [[int(0), 36, 3, 41, 18], [int(1), 44, 10, 45, 2],
191
	[int(62), 6, 43, 15, 61], [int(28), 55, 25, 21, 56], [int(27), 20, 39, 8, 14]]
192

193
// rho is the second step mapping function.  It is defined as:
194
//
195
// 1. For all z such that 0 <= z < w, let A′ [0, 0, z] = A[0, 0, z].
196
// 2. Let (x, y) = (1, 0).
197
// 3. For t from 0 to 23:
198
//      a. for all z such that 0 <= z < w, let A′[x, y, z] = A[x, y, (z – (t + 1)(t + 2)/2) mod w];
199
//      b. let (x, y) = (y, (2x + 3y) mod 5).
200
//
201
// A is the 5 x 5 x w state matrix.  w is the number of bits in the z axis, 64 in our case.
202
//
203
// Step 1 looks worthless since A' will be overwtitten by step 3a.
204
//
205
// Steps 2 and 3b are defining how the x and y values are initialized and updated
206
// as t goes from 0 to 23.  Notice that the initial value of x, y of 0, 0 is not
207
// calculated and is just zero.  The other 24 values needed are calculated,
208
// making a total of 25, which is the total number of lanes in the state.  By
209
// setting the offset at 0, 0 to 0, that lane does not get rotated.
210
//
211
// The effect of step 3a is to rotate a 64-bit lane by the amount calculated by
212
// (((t + 1) * (t + 2)) / 2) % 64.  In order to save time, these rotation values,
213
// called offsets, can be calculated ahead of time.
214
@[direct_array_access; inline]
215
fn (mut s State) rho() {
216
	for x in 0 .. 5 {
217
		for y in 0 .. 5 {
218
			s.a[x][y] = bits.rotate_left_64(s.a[x][y], rho_offsets[x][y])
219
		}
220
	}
221
}
222

223
// pi is the third step mapping function.  It is defined as:
224
//
225
// 1. For all triples (x, y, z) such that 0 <= x < 5, 0 <= y < 5, and 0 <= z < w, let
226
//    A′[x, y, z]= A[(x + 3y) mod 5, x, z].
227
//
228
// A is the 5 x 5 x w state matrix.  w is the number of bits in the z axis, 64 in our case.
229
//
230
// For this function, we will need to have a temporary version of the state for
231
// holding the rearranged lanes.
232
@[direct_array_access; inline]
233
fn (mut s State) pi() {
234
	mut a_prime := [5][5]Lane{}
235
	for x in 0 .. 5 {
236
		for y in 0 .. 5 {
237
			a_prime[x][y] = s.a[(x + (3 * y)) % 5][x]
238
		}
239
	}
240

241
	// make the temporary state be the returned state
242
	for x in 0 .. 5 {
243
		for y in 0 .. 5 {
244
			s.a[x][y] = a_prime[x][y]
245
		}
246
	}
247
}
248

249
// chi is the fourth step mapping function.  It is defined as:
250
//
251
// 1. For all triples (x, y, z) such that 0 <= x < 5, 0 <= y < 5, and 0 <= z < w, let
252
//    A′ [x, y, z] = A[x, y, z] xor ((A[(x+1) mod 5, y, z] xor 1) & A[(x+2) mod 5, y, z]).
253
//
254
// A is the 5 x 5 x w state matrix.  w is the number of bits in the z axis, 64 in our case.
255
//
256
// The effect of chi is to XOR each bit with a non-linear function of two other bits
257
// in its row.
258
//
259
// For this function, we will need to have a temporary version of the state for
260
// holding the changed lanes.
261
@[direct_array_access; inline]
262
fn (mut s State) chi() {
263
	mut a_prime := [5][5]Lane{}
264
	for x in 0 .. 5 {
265
		for y in 0 .. 5 {
266
			a_prime[x][y] = s.a[x][y] ^ (~(s.a[(x + 1) % 5][y]) & s.a[(x + 2) % 5][y])
267
		}
268
	}
269

270
	// make the temporary state be the returned state
271
	for x in 0 .. 5 {
272
		for y in 0 .. 5 {
273
			s.a[x][y] = a_prime[x][y]
274
		}
275
	}
276
}
277

278
// iota_round_constants are precomputed xor masks for the iota function
279
const iota_round_constants = [u64(0x0000000000000001), 0x0000000000008082, 0x800000000000808a,
280
	0x8000000080008000, 0x000000000000808b, 0x0000000080000001, 0x8000000080008081,
281
	0x8000000000008009, 0x000000000000008a, 0x0000000000000088, 0x0000000080008009,
282
	0x000000008000000a, 0x000000008000808b, 0x800000000000008b, 0x8000000000008089,
283
	0x8000000000008003, 0x8000000000008002, 0x8000000000000080, 0x000000000000800a,
284
	0x800000008000000a, 0x8000000080008081, 0x8000000000008080, 0x0000000080000001,
285
	0x8000000080008008]
286

287
// iota is the fifth step mapping function.  It is defined as:
288
//
289
// 1. For all triples (x, y, z) such that 0 <= x < 5, 0 <= y < 5, and 0 <= z < w, let
290
//    A′[x, y, z] = A[x, y, z].
291
// 2. Let RC = 0**w
292
// 3. For j from 0 to l, let RC[2**j – 1] = rc(j + 7i_r).
293
// 4. For all z such that 0 ≤ z < w, let A′ [0, 0, z] = A′ [0, 0, z] xor RC[z].
294
//
295
// A is the 5 x 5 x w state matrix.  w is the number of bits in the z axis, 64 in our case.
296
//
297
// This is pretty ugly.  Fortunately, all the uglyness can be precomputed so that
298
// all we need to do is xor lane 0, 0 with the appropriate precomputed value.  These
299
// precomputed values are indexed by the round which is being applied.  For sha3,
300
// the number of rounds is 24 so we just need to precompute the 24 valuse needed
301
// to xor with lane 0, 0.
302
@[direct_array_access; inline]
303
fn (mut s State) iota(round_index int) {
304
	s.a[0][0] ^= iota_round_constants[round_index]
305
}
306

307
fn (s State) str() string {
308
	mut output := '\n             y = 0            y = 1            y = 2            y = 3            y = 4\n'
309
	for x in 0 .. 5 {
310
		output += 'x = ${x}: ${s.a[x][0]:016x} ${s.a[x][1]:016x} ${s.a[x][2]:016x} ${s.a[x][3]:016x} ${s.a[x][4]:016x}\n'
311
	}
312

313
	return output
314
}
315