master
1const std = @import("std");
2const builtin = @import("builtin");
3const assert = std.debug.assert;
4const math = std.math;
5const mem = std.mem;
6const native_endian = builtin.cpu.arch.endian();
7const mode = @import("builtin").mode;
8
9/// The Keccak-f permutation.
10pub fn KeccakF(comptime f: u11) type {
11 comptime assert(f >= 200 and f <= 1600 and f % 200 == 0); // invalid bit size
12 const T = std.meta.Int(.unsigned, f / 25);
13 const Block = [25]T;
14
15 const PI = [_]u5{
16 10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24, 4, 15, 23, 19, 13, 12, 2, 20, 14, 22, 9, 6, 1,
17 };
18
19 return struct {
20 const Self = @This();
21
22 /// Number of bytes in the state.
23 pub const block_bytes = f / 8;
24
25 /// Maximum number of rounds for the given f parameter.
26 pub const max_rounds = 12 + 2 * math.log2(f / 25);
27
28 // Round constants
29 const RC = rc: {
30 const RC64 = [_]u64{
31 0x0000000000000001, 0x0000000000008082, 0x800000000000808a, 0x8000000080008000,
32 0x000000000000808b, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009,
33 0x000000000000008a, 0x0000000000000088, 0x0000000080008009, 0x000000008000000a,
34 0x000000008000808b, 0x800000000000008b, 0x8000000000008089, 0x8000000000008003,
35 0x8000000000008002, 0x8000000000000080, 0x000000000000800a, 0x800000008000000a,
36 0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008,
37 };
38 var rc: [max_rounds]T = undefined;
39 for (&rc, RC64[0..max_rounds]) |*t, c| t.* = @as(T, @truncate(c));
40 break :rc rc;
41 };
42
43 st: Block = [_]T{0} ** 25,
44
45 /// Initialize the state from a slice of bytes.
46 pub fn init(bytes: [block_bytes]u8) Self {
47 var self: Self = undefined;
48 inline for (&self.st, 0..) |*r, i| {
49 r.* = mem.readInt(T, bytes[@sizeOf(T) * i ..][0..@sizeOf(T)], .little);
50 }
51 return self;
52 }
53
54 /// A representation of the state as bytes. The byte order is architecture-dependent.
55 pub fn asBytes(self: *Self) *[block_bytes]u8 {
56 return mem.asBytes(&self.st);
57 }
58
59 /// Byte-swap the entire state if the architecture doesn't match the required endianness.
60 pub fn endianSwap(self: *Self) void {
61 for (&self.st) |*w| {
62 w.* = mem.littleToNative(T, w.*);
63 }
64 }
65
66 /// Set bytes starting at the beginning of the state.
67 pub fn setBytes(self: *Self, bytes: []const u8) void {
68 var i: usize = 0;
69 while (i + @sizeOf(T) <= bytes.len) : (i += @sizeOf(T)) {
70 self.st[i / @sizeOf(T)] = mem.readInt(T, bytes[i..][0..@sizeOf(T)], .little);
71 }
72 if (i < bytes.len) {
73 var padded = [_]u8{0} ** @sizeOf(T);
74 @memcpy(padded[0 .. bytes.len - i], bytes[i..]);
75 self.st[i / @sizeOf(T)] = mem.readInt(T, padded[0..], .little);
76 }
77 }
78
79 /// XOR a byte into the state at a given offset.
80 pub fn addByte(self: *Self, byte: u8, offset: usize) void {
81 const z = @sizeOf(T) * @as(math.Log2Int(T), @truncate(offset % @sizeOf(T)));
82 self.st[offset / @sizeOf(T)] ^= @as(T, byte) << z;
83 }
84
85 /// XOR bytes into the beginning of the state.
86 pub fn addBytes(self: *Self, bytes: []const u8) void {
87 var i: usize = 0;
88 while (i + @sizeOf(T) <= bytes.len) : (i += @sizeOf(T)) {
89 self.st[i / @sizeOf(T)] ^= mem.readInt(T, bytes[i..][0..@sizeOf(T)], .little);
90 }
91 if (i < bytes.len) {
92 var padded = [_]u8{0} ** @sizeOf(T);
93 @memcpy(padded[0 .. bytes.len - i], bytes[i..]);
94 self.st[i / @sizeOf(T)] ^= mem.readInt(T, padded[0..], .little);
95 }
96 }
97
98 /// Extract the first bytes of the state.
99 pub fn extractBytes(self: *Self, out: []u8) void {
100 var i: usize = 0;
101 while (i + @sizeOf(T) <= out.len) : (i += @sizeOf(T)) {
102 mem.writeInt(T, out[i..][0..@sizeOf(T)], self.st[i / @sizeOf(T)], .little);
103 }
104 if (i < out.len) {
105 var padded = [_]u8{0} ** @sizeOf(T);
106 mem.writeInt(T, padded[0..], self.st[i / @sizeOf(T)], .little);
107 @memcpy(out[i..], padded[0 .. out.len - i]);
108 }
109 }
110
111 /// XOR the first bytes of the state into a slice of bytes.
112 pub fn xorBytes(self: *Self, out: []u8, in: []const u8) void {
113 assert(out.len == in.len);
114
115 var i: usize = 0;
116 while (i + @sizeOf(T) <= in.len) : (i += @sizeOf(T)) {
117 const x = mem.readInt(T, in[i..][0..@sizeOf(T)], native_endian) ^ mem.nativeToLittle(T, self.st[i / @sizeOf(T)]);
118 mem.writeInt(T, out[i..][0..@sizeOf(T)], x, native_endian);
119 }
120 if (i < in.len) {
121 var padded = [_]u8{0} ** @sizeOf(T);
122 @memcpy(padded[0 .. in.len - i], in[i..]);
123 const x = mem.readInt(T, &padded, native_endian) ^ mem.nativeToLittle(T, self.st[i / @sizeOf(T)]);
124 mem.writeInt(T, &padded, x, native_endian);
125 @memcpy(out[i..], padded[0 .. in.len - i]);
126 }
127 }
128
129 /// Set the words storing the bytes of a given range to zero.
130 pub fn clear(self: *Self, from: usize, to: usize) void {
131 @memset(self.st[from / @sizeOf(T) .. (to + @sizeOf(T) - 1) / @sizeOf(T)], 0);
132 }
133
134 /// Clear the entire state, disabling compiler optimizations.
135 pub fn secureZero(self: *Self) void {
136 std.crypto.secureZero(T, &self.st);
137 }
138
139 inline fn round(self: *Self, rc: T) void {
140 const st = &self.st;
141
142 // theta
143 var t = [_]T{0} ** 5;
144 inline for (0..5) |i| {
145 inline for (0..5) |j| {
146 t[i] ^= st[j * 5 + i];
147 }
148 }
149 inline for (0..5) |i| {
150 inline for (0..5) |j| {
151 st[j * 5 + i] ^= t[(i + 4) % 5] ^ math.rotl(T, t[(i + 1) % 5], 1);
152 }
153 }
154
155 // rho+pi
156 var last = st[1];
157 comptime var rotc = 0;
158 inline for (0..24) |i| {
159 const x = PI[i];
160 const tmp = st[x];
161 rotc = (rotc + i + 1) % @bitSizeOf(T);
162 st[x] = math.rotl(T, last, rotc);
163 last = tmp;
164 }
165 inline for (0..5) |i| {
166 inline for (0..5) |j| {
167 t[j] = st[i * 5 + j];
168 }
169 inline for (0..5) |j| {
170 st[i * 5 + j] = t[j] ^ (~t[(j + 1) % 5] & t[(j + 2) % 5]);
171 }
172 }
173
174 // iota
175 st[0] ^= rc;
176 }
177
178 /// Apply a (possibly) reduced-round permutation to the state.
179 pub fn permuteR(self: *Self, comptime rounds: u5) void {
180 var i = RC.len - rounds;
181 while (i < RC.len - RC.len % 3) : (i += 3) {
182 self.round(RC[i]);
183 self.round(RC[i + 1]);
184 self.round(RC[i + 2]);
185 }
186 while (i < RC.len) : (i += 1) {
187 self.round(RC[i]);
188 }
189 }
190
191 /// Apply a full-round permutation to the state.
192 pub fn permute(self: *Self) void {
193 self.permuteR(max_rounds);
194 }
195 };
196}
197
198/// A generic Keccak-P state.
199pub fn State(comptime f: u11, comptime capacity: u11, comptime rounds: u5) type {
200 comptime assert(f >= 200 and f <= 1600 and f % 200 == 0); // invalid state size
201 comptime assert(capacity < f and capacity % 8 == 0); // invalid capacity size
202
203 // In debug mode, track transitions to prevent insecure ones.
204 const Op = enum { uninitialized, initialized, updated, absorb, squeeze };
205 const TransitionTracker = if (mode == .Debug) struct {
206 op: Op = .uninitialized,
207
208 fn to(tracker: *@This(), next_op: Op) void {
209 switch (next_op) {
210 .updated => {
211 switch (tracker.op) {
212 .uninitialized => @panic("cannot permute before initializing"),
213 else => {},
214 }
215 },
216 .absorb => {
217 switch (tracker.op) {
218 .squeeze => @panic("cannot absorb right after squeezing"),
219 else => {},
220 }
221 },
222 .squeeze => {
223 switch (tracker.op) {
224 .uninitialized => @panic("cannot squeeze before initializing"),
225 .initialized => @panic("cannot squeeze right after initializing"),
226 .absorb => @panic("cannot squeeze right after absorbing"),
227 else => {},
228 }
229 },
230 .uninitialized => @panic("cannot transition to uninitialized"),
231 .initialized => {},
232 }
233 tracker.op = next_op;
234 }
235 } else struct {
236 // No-op in non-debug modes.
237 inline fn to(tracker: *@This(), next_op: Op) void {
238 _ = tracker; // no-op
239 _ = next_op; // no-op
240 }
241 };
242
243 return struct {
244 const Self = @This();
245
246 /// The block length, or rate, in bytes.
247 pub const rate = KeccakF(f).block_bytes - capacity / 8;
248 /// Keccak does not have any options.
249 pub const Options = struct {};
250
251 /// The input delimiter.
252 delim: u8,
253
254 offset: usize = 0,
255 buf: [rate]u8 = undefined,
256
257 st: KeccakF(f) = .{},
258
259 transition: TransitionTracker = .{},
260
261 /// Absorb a slice of bytes into the sponge.
262 pub fn absorb(self: *Self, bytes: []const u8) void {
263 self.transition.to(.absorb);
264 var i: usize = 0;
265 if (self.offset > 0) {
266 const left = @min(rate - self.offset, bytes.len);
267 @memcpy(self.buf[self.offset..][0..left], bytes[0..left]);
268 self.offset += left;
269 if (left == bytes.len) return;
270 if (self.offset == rate) {
271 self.st.addBytes(self.buf[0..]);
272 self.st.permuteR(rounds);
273 self.offset = 0;
274 }
275 i = left;
276 }
277 while (i + rate < bytes.len) : (i += rate) {
278 self.st.addBytes(bytes[i..][0..rate]);
279 self.st.permuteR(rounds);
280 }
281 const left = bytes.len - i;
282 if (left > 0) {
283 @memcpy(self.buf[0..left], bytes[i..][0..left]);
284 }
285 self.offset = left;
286 }
287
288 /// Initialize the state from a slice of bytes.
289 pub fn init(bytes: [f / 8]u8, delim: u8) Self {
290 var st = Self{ .st = KeccakF(f).init(bytes), .delim = delim };
291 st.transition.to(.initialized);
292 return st;
293 }
294
295 /// Permute the state
296 pub fn permute(self: *Self) void {
297 if (mode == .Debug) {
298 if (self.transition.op == .absorb and self.offset > 0) {
299 @panic("cannot permute with pending input - call fillBlock() or pad() instead");
300 }
301 }
302 self.transition.to(.updated);
303 self.st.permuteR(rounds);
304 self.offset = 0;
305 }
306
307 /// Align the input to the rate boundary and permute.
308 pub fn fillBlock(self: *Self) void {
309 self.transition.to(.absorb);
310 self.st.addBytes(self.buf[0..self.offset]);
311 self.st.permuteR(rounds);
312 self.offset = 0;
313 self.transition.to(.updated);
314 }
315
316 /// Mark the end of the input.
317 pub fn pad(self: *Self) void {
318 self.transition.to(.absorb);
319 self.st.addBytes(self.buf[0..self.offset]);
320 if (self.offset == rate) {
321 self.st.permuteR(rounds);
322 self.offset = 0;
323 }
324 self.st.addByte(self.delim, self.offset);
325 self.st.addByte(0x80, rate - 1);
326 self.st.permuteR(rounds);
327 self.offset = 0;
328 self.transition.to(.updated);
329 }
330
331 /// Squeeze a slice of bytes from the sponge.
332 /// The function can be called multiple times.
333 pub fn squeeze(self: *Self, out: []u8) void {
334 self.transition.to(.squeeze);
335 var i: usize = 0;
336 if (self.offset == rate) {
337 self.st.permuteR(rounds);
338 } else if (self.offset > 0) {
339 @branchHint(.unlikely);
340 var buf: [rate]u8 = undefined;
341 self.st.extractBytes(buf[0..]);
342 const left = @min(rate - self.offset, out.len);
343 @memcpy(out[0..left], buf[self.offset..][0..left]);
344 self.offset += left;
345 if (left == out.len) return;
346 if (self.offset == rate) {
347 self.offset = 0;
348 self.st.permuteR(rounds);
349 }
350 i = left;
351 }
352 while (i + rate < out.len) : (i += rate) {
353 self.st.extractBytes(out[i..][0..rate]);
354 self.st.permuteR(rounds);
355 }
356 const left = out.len - i;
357 if (left > 0) {
358 self.st.extractBytes(out[i..][0..left]);
359 }
360 self.offset = left;
361 }
362 };
363}
364
365test "Keccak-f800" {
366 var st: KeccakF(800) = .{
367 .st = .{
368 0xE531D45D, 0xF404C6FB, 0x23A0BF99, 0xF1F8452F, 0x51FFD042, 0xE539F578, 0xF00B80A7,
369 0xAF973664, 0xBF5AF34C, 0x227A2424, 0x88172715, 0x9F685884, 0xB15CD054, 0x1BF4FC0E,
370 0x6166FA91, 0x1A9E599A, 0xA3970A1F, 0xAB659687, 0xAFAB8D68, 0xE74B1015, 0x34001A98,
371 0x4119EFF3, 0x930A0E76, 0x87B28070, 0x11EFE996,
372 },
373 };
374 st.permute();
375 const expected: [25]u32 = .{
376 0x75BF2D0D, 0x9B610E89, 0xC826AF40, 0x64CD84AB, 0xF905BDD6, 0xBC832835, 0x5F8001B9,
377 0x15662CCE, 0x8E38C95E, 0x701FE543, 0x1B544380, 0x89ACDEFF, 0x51EDB5DE, 0x0E9702D9,
378 0x6C19AA16, 0xA2913EEE, 0x60754E9A, 0x9819063C, 0xF4709254, 0xD09F9084, 0x772DA259,
379 0x1DB35DF7, 0x5AA60162, 0x358825D5, 0xB3783BAB,
380 };
381 try std.testing.expectEqualSlices(u32, &st.st, &expected);
382}
383
384test "squeeze" {
385 var st = State(800, 256, 22).init([_]u8{0x80} ** 100, 0x01);
386
387 var out0: [15]u8 = undefined;
388 var out1: [out0.len]u8 = undefined;
389 st.permute();
390 var st0 = st;
391 st0.squeeze(out0[0..]);
392 var st1 = st;
393 st1.squeeze(out1[0 .. out1.len / 2]);
394 st1.squeeze(out1[out1.len / 2 ..]);
395 try std.testing.expectEqualSlices(u8, &out0, &out1);
396
397 var out2: [100]u8 = undefined;
398 var out3: [out2.len]u8 = undefined;
399 var st2 = st;
400 st2.squeeze(out2[0..]);
401 var st3 = st;
402 st3.squeeze(out3[0 .. out2.len / 2]);
403 st3.squeeze(out3[out2.len / 2 ..]);
404 try std.testing.expectEqualSlices(u8, &out2, &out3);
405}