I'm implementing SHA-3 following the official FIPS-202 document in Verilog. My state is represented by a one-dimensional register and I use a macro function to calculate the corresponding state index from the (x,y,z) coordinates in the document:
A[x, y, z] = S [W(5y + x) + z], W = 64 (p. 9)
I'm strictly following the guide on page 11 and came up with this:
// Macros for transforming dimensions
`define sub_1(x) (x == 0 ? 4 : x - 1)
`define add_1(x) (x == 4 ? 0 : x + 1)
`define sub_1_W(x) (x == 0 ? (W - 1) : x - 1)
`define s(x,y,z) ((W * ((5 * y) + x)) + z)
`define s_xz(x,z) ((W * x) + z)
// Wires
wire [0:(1600 - 1)] absorbed_data, after_theta;
wire [0:((5 * 64) - 1)] C, D;
genvar x, z;
for(x = 0; x < 5; x = x + 1) begin
for(z = (W - 1); z >= 0; z = z - 1) begin
// Step 1
assign C[`s_xz(x,z)] = absorbed_data[`s(x,0,z)] ^ absorbed_data[`s(x,1,z)] ^ absorbed_data[`s(x,2,z)] ^ absorbed_data[`s(x,3,z)] ^ absorbed_data[`s(x,4,z)];
// Step 2
assign D[`s_xz(x,z)] = C[`s_xz(`sub_1(x),z)] ^ C[`s_xz(`add_1(x),`sub_1_W(z)];
end
end
genvar x, y, z;
generate
for(x = 0; x < 5; x = x + 1) begin
for(y = 0; y < 5; y = y + 1) begin
for(z = 0; z < W; z = z + 1) begin
// Step 3
assign after_theta[`s(x,y,z)] = absorbed_data[`s(x,y,z)] ^ D[`s_xz(x,z)];
end
end
end
endgenerate
The issue I'm currently facing seems to be in the Theta function. For example for SHA-224 and an empty message should yield the intermediate results and the final output as shown in this document.
Strangely, I get the same absorbed_data (06 00 ... 00 80) but different values for C and D:
C
as is: 06 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 80 | 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00
to be: 00 00 00 00 00 00 00 06 | 00 00 00 00 00 00 00 00 | 80 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00
D
as is: 00 00 00 00 00 00 00 00 | 06 00 00 00 00 00 01 00 | 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 80 | 0c 00 00 00 00 00 00 00
to be: 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 07 | 00 00 00 00 00 00 00 00 | 80 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 0c
Firstly, for C the bit order seems to be different but not on the bit-level but on the byte-level (as 06 stays 06).
Secondly, for D I get 06 00 .. 01 00 whereas the correct result should be 00 .. 00 07. This is never possible for my implementation as, according to FIPS-202, the bit at z can only be shifted by one position ( (z - 1) mod w).
In the to-be case D will yield the correct result because 06 ^ (80 << 1) = 07.
In conclusion, I would say that my implementation behaves as one can expect from the definition in FIPS-202, correct?
Any idea what I'm doing wrong here?
Thanks in advance!
I think I found the solution. It is described in appendix of FIPS 202 B.1 (starting on page 26). A hint on this topic is given on page 25:
The convention for interpreting hexadecimal strings as bit strings for the inputs and outputs of the SHA-3 examples is different from the convention for other functions on the examples page. The conversion functions between hexadecimal strings and SHA-3 bit strings are specified in Sec. B.1. For byte-aligned messages, the hexadecimal forms of the padding for the SHA-3 functions are described in Sec. B.2.
There is a good explanation on how to circumvent this issue on cryptologie.net.