I have been trying to write my own implementation of Keccak-256 cryptographic hash function in Java. I have been using Keccak specifications summary and their Implementation Guide for reference. I want to test my implementation using a zero length input. According to this online tool. The zero length input should have a hash of: C5D2460186F7233C927E7DB2DCC703C0E500B653CA82273B7BFAD8045D85A470 but my hash is something else.
My code is located here on Github.
My thoughts are that I must have done something wrong on the padding of the message(that is all that gets hashed) or something on byte order in my conversion of byte[] to longs and back, or the absorbing/squeezing phase. In my implementation I only need keccak-f[1600] which means there is only 64bits in each lane and that each block is 1088 bits or 136 bytes. I chose to use a five-by-five 2D array of longs to represent the state in my code.
Using a zero byte message means that there should only be one block of 136 bytes which should be all just padding. According to this post since keccak uses little-endian my padding should be in this order of bytes:
byte[] p = new byte[136];
p[7] = (byte) 0x01;
p[135] = (byte) 0x80;
I have looked at someone else's implementation but I can't seem to find out where my error is.
This is the sponge function:
public byte[] keccak(byte[] Mbytes, int r, int c) { // r should be 1088 and c should be 512 for Keccack-256
// Padding
byte[] paddedMessage = concatBytes(Mbytes, pad(r, Mbytes.length));
System.out.println("Padded Message size: " + paddedMessage.length);
// Initialize State
A = new long[5][5];
// Break up message into blocks r bits or 136 bytes
byte[] block = new byte[136];
int n = paddedMessage.length / block.length; // number of blocks
System.out.println("Blocks: " + n);
for (int i = 0; i < n; i++) { // For each block
//set block values
for (int j = 0; j < block.length; j++) {
block[j] = paddedMessage[i * block.length + j];
}
printBlock(block);
// Fill state
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
int index = x + 5 * y;
if (index < r/w) {
long value = decodeLELong(block, index * 8);
System.out.println(value + " index: " + index);
A[x][y] = A[x][y] ^ value;
A = keccakF1600(A);
}
}
}
}
byte[] output = new byte[0]; // Size should be 256 bits/Z
int bytesFilled = 0;
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
int index = x+5*y;
if (index < r/w) {
if (bytesFilled < 136) {
// Take out a long from state and concat it to output.
output = concatBytes(output, encodeLELong(A[x][y]));
bytesFilled += 8;
A = keccakF1600(A);
}
}
if (bytesFilled == 32) {
//System.out.println("Finished Hash");
return output;
}
}
}
return output;
}
This is my pad function:
private byte[] pad(int x, int m) { // x/size should be 1088 or 136 bytes
byte[] p = null;
int q = 136 - (m % 136); // number of padding bytes
//System.out.println("Pad q: " + q + " m: " + m);
if(q == 136) { // Whole block is padding
p = new byte[136];
p[7] = (byte) 0x01;
p[135] = (byte) 0x80;
}
else { // Ignore for now
p = new byte[q];
p[0] = 1;
}
return p;
}
And this is my code for the keccak permutation:
public long[][] keccakF1600(long[][] A) { // KECCAK-f where b = 1600
for (int i = 0; i < 24; i++) { // 24 Rounds
A = Round1600(A, RC[i]);
}
return A;
}
private long[][] Round1600(long[][] A, long rc) {
// θ Step
long[] C = new long[5];
for (int x = 0; x < 5; x++) {
C[x] = A[x][0] ^ A[x][1]^ A[x][2] ^ A[x][3] ^ A[x][4];
}
long[] D = new long[5];
for (int x = 0; x < 5; x++) {
D[x] = C[(x + 4) % 5] ^ Long.rotateLeft(C[(x + 1) % 5], 1);
}
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
A[x][y] = A[x][y] ^ D[x];
}
}
// ρ and π steps
long[][] B = new long[5][5];
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
B[y][(2 * x + 3 * y) % 5] = Long.rotateLeft(A[x][y], rot_offset(x,y));
}
}
// χ step
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
A[x][y] = B[x][y] ^ ((~B[(x+1) % 5][y]) & B[(x+2) % 5][y]);
}
}
// ι step
A[0][0] = A[0][0] ^ rc;
return A;
}
private int rot_offset(int x, int y) {
switch (x){
case 0:
switch (y) {
case 0:
return 0;
case 1:
return 36;
case 2:
return 3;
case 3:
return 41;
case 4:
return 18;
}
case 1:
switch (y) {
case 0:
return 1;
case 1:
return 44;
case 2:
return 10;
case 3:
return 45;
case 4:
return 2;
}
case 2:
switch (y) {
case 0:
return 62;
case 1:
return 6;
case 2:
return 43;
case 3:
return 15;
case 4:
return 61;
}
case 3:
switch (y) {
case 0:
return 28;
case 1:
return 55;
case 2:
return 25;
case 3:
return 21;
case 4:
return 56;
}
case 4:
switch (y) {
case 0:
return 27;
case 1:
return 20;
case 2:
return 39;
case 3:
return 8;
case 4:
return 14;
}
}
System.out.println("Should not Happen!");
return -1; // Should not happen!
}
And finally the helper metheods to convert byte[] to long and back:
public static long decodeLELong(byte[] buf, int off)
{
return (buf[off + 0] & 0xFFL)
| ((buf[off + 1] & 0xFFL) << 8)
| ((buf[off + 2] & 0xFFL) << 16)
| ((buf[off + 3] & 0xFFL) << 24)
| ((buf[off + 4] & 0xFFL) << 32)
| ((buf[off + 5] & 0xFFL) << 40)
| ((buf[off + 6] & 0xFFL) << 48)
| ((buf[off + 7] & 0xFFL) << 56);
}
public static byte[] encodeLELong(long val)
{
byte[] buf = new byte[8];
buf[0] = (byte)val;
buf[1] = (byte)(val >>> 8);
buf[2] = (byte)(val >>> 16);
buf[3] = (byte)(val >>> 24);
buf[4] = (byte)(val >>> 32);
buf[5] = (byte)(val >>> 40);
buf[6] = (byte)(val >>> 48);
buf[7] = (byte)(val >>> 56);
return buf;
}
Last helper method for concatBytes:
public static byte[] concatBytes(byte[] in1, byte[] in2) {
byte[] output = new byte[in1.length + in2.length];
for (int i = 0; i < in1.length; i++) {
output[i] = in1[i];
}
for (int i = 0; i < in2.length; i++) {
output[i + in1.length] = in2[i];
}
return output;
}