Useless free start collision on SHA-3-256

Free-start-keccak.py

import binascii

def ROL64(a, n):
    return ((a >> (64-(n%64))) + (a << (n%64))) % (1 << 64)

def KeccakF1600onLanes(lanes):
     R = 1
     for round in range(24):
          # θ
          C = [lanes[x][0] ^ lanes[x][1] ^ lanes[x][2] ^ lanes[x][3] ^ lanes[x][4] for x in range(5)]
          D = [C[(x+4)%5] ^ ROL64(C[(x+1)%5], 1) for x in range(5)]
          lanes = [[lanes[x][y]^D[x] for y in range(5)] for x in range(5)]
          # ρ and π
          (x, y) = (1, 0)
          current = lanes[x][y]
          for t in range(24):
               (x, y) = (y, (2*x+3*y)%5)
               (current, lanes[x][y]) = (lanes[x][y], ROL64(current, (t+1)*(t+2)//2))
          # χ
          for y in range(5):
               T = [lanes[x][y] for x in range(5)]
               for x in range(5):
                    lanes[x][y] = T[x] ^((~T[(x+1)%5]) & T[(x+2)%5])
          # ι
          for j in range(7):
               R = ((R << 1) ^ ((R >> 7)*0x71)) % 256
               if (R & 2):
                    lanes[0][0] = lanes[0][0] ^ (1 << ((1<<j)-1))
     return lanes

def load64(b):
    return sum((b[i] << (8*i)) for i in range(8))

def store64(a):
    return list((a >> (8*i)) % 256 for i in range(8))

def KeccakF1600(state):
     lanes = [[load64(state[8*(x+5*y):8*(x+5*y)+8]) for y in range(5)] for x in range(5)]
     lanes = KeccakF1600onLanes(lanes)
     state = bytearray(200)
     for x in range(5):
          for y in range(5):
               state[8*(x+5*y):8*(x+5*y)+8] = store64(lanes[x][y])
     return state;

def convert_anoying_bit_to_byte_array(ret, bits):
     for x in range(5):
          for y in range(5):
               val = 0;
               for z in range(8):
                    val += int(bits[(x+5*y)][z*8:(z+1)*8],2) << (8*(7-z))

               ret[8*(x+5*y):8*(x+5*y)+8] = store64(val)
     return ret;

def xor_states(xored, st1, st2):
     for x in range(200):
          xored[x] = st1[x] ^ st2[x]
     return xored

def Keccak(state, rate, capacity, inputBytes, delimitedSuffix, outputByteLen):
     outputBytes = bytearray()
     # state = bytearray([0 for i in range(200)])
     rateInBytes = rate//8
     blockSize = 0
     if (((rate + capacity) != 1600) or ((rate % 8) != 0)):
          return
     inputOffset = 0
     # === Absorb all the input blocks ===
     while(inputOffset < len(inputBytes)):
          print("Before absorption :")
          print(bytes.decode(binascii.hexlify(state)));
          print()
          blockSize = min(len(inputBytes)-inputOffset, rateInBytes)
          for i in range(blockSize):
               state[i] = state[i] ^ inputBytes[i+inputOffset]
          print("After absorption :")
          print(bytes.decode(binascii.hexlify(state)));
          print()
          inputOffset = inputOffset + blockSize
          if (blockSize == rateInBytes):
               state = KeccakF1600(state)
               blockSize = 0
     # === Do the padding and switch to the squeezing phase ===
     state[blockSize] = state[blockSize] ^ delimitedSuffix
     if (((delimitedSuffix & 0x80) != 0) and (blockSize == (rateInBytes-1))):
          state = KeccakF1600(state)
     state[rateInBytes-1] = state[rateInBytes-1] ^ 0x80
     state = KeccakF1600(state)
     # === Squeeze out all the output blocks ===
     while(outputByteLen > 0):
          blockSize = min(outputByteLen, rateInBytes)
          outputBytes = outputBytes + state[0:blockSize]
          outputByteLen = outputByteLen - blockSize
          if (outputByteLen > 0):
               state = KeccakF1600(state)
     return outputBytes

def gen_next_absorb(toxor,toxor2):
     ret = bytearray([0 for i in range(136)])
     for x in range(136):
          ret[x] = toxor[x] ^ toxor2[x]
     return ret

def cut_absorb(toxor):
     ret = bytearray([0 for i in range(136)])
     for x in range(136):
          ret[x] = toxor[x]
     return ret

def cut_capacity(toxor):
     ret = bytearray([0 for i in range(64)])
     for x in range(136,200):
          ret[x-136] = toxor[x]
     return ret

initial_vector_0=[
     '0001100010111010010011010010100010111011000100001110101001001100',
     '1111101100111100001110010110111001100001110101101101101000100001',
     '0110010010111111000111101000000100010010111101011110001011010101',
     '0001111000111111111100011001100001110011100010010111100100000110',
     '1101000001010010011100110101010101001111100100001111111111110011',

     '0110101010110100110110010001100111011000100110001101000110011111',
     '0101110001101010100010000100001101001111111000001101011000000101',
     '1101001100001000101001000000111100011100000111011011010110000010',
     '1111001100100111011011110011000101010100111010000001011100100111',
     '0010101111001100000101011000100100100010010111111000111100101000',

     '0100011010101111010000010011011101110010111001100101000000011101',
     '0010001101111100001010110101000101011100110111010110110011110100',
     '1110101011110000111111000001010011001011100101010100011101101100',
     '1100110001100111011001110001001010000011110001110001101101000011',
     '0000010011101111010111001100000111000101010001111001101010101011',

     '1101011111011011011011110011010011001101011011100101101010000111',
     '0011010101110100101011101010100101010001010011100001111010001001',
     '1011100001001010001000001010110000111010001110101001100101011000',
     '0000100000101101111101001000001011011001000101000001000010010101',
     '0111011010010110100111111111110010011011000110111110000001010101',

     '1010000111011001001101011110110000001001100010010110000000011100',
     '1001001110001111000001000110100001100000110100011101000100100110',
     '1011110010000110001111010011110101111101110001110010100010010001',
     '1110101110011000011000000111010011010111101000110010110011011101',
     '0001111011111100001000110001011101001110110001101110010000101001']


next_block_0=[
     '1100111010000010101001100011001000100110110111001011010111101001',
     '0101110001011011111011101001101011001101001001011000111101111100',
     '1001001101001000101111101111011110010101110011111001001100000001',
     '0101000010111111011000000000110001000111011100110001110110000010',
     '0010001100100011010100011011010000110101111100110010110010010010',

     '0010101001101000110000111111000110011000111000011010011101001011',
     '1110110001111001011100011110100100010001100000010101010101001001',
     '1001011000001110010101100001110011111001001000000000010011000010',
     '1011111001011111000001101011000110110000111110011101001011100011',
     '0001100111010001111110011001010011000111011010110010010000101010',

     '0000101000001111101000101001000110001111000100011111010101110001',
     '0000011101010101001110010000000111011100010001101010101100111010',
     '1010101011000011110001111000111011000010110011110111100011110110',
     '0000111100010100111001110001000000000001110111011110001000000000',
     '0101001100100000011100111001111111001000110111111001010100101000',

     '0010000111101100110101101011010100011111110010000001101000001100',
     '1101001010100000111011000111100100000111011111101100101001111010',
     '0000000000000000000000000000000000000000000000000000000000000000',
     '0000000000000000000000000000000000000000000000000000000000000000',
     '0000000000000000000000000000000000000000000000000000000000000000',

     '0000000000000000000000000000000000000000000000000000000000000000',
     '0000000000000000000000000000000000000000000000000000000000000000',
     '0000000000000000000000000000000000000000000000000000000000000000',
     '0000000000000000000000000000000000000000000000000000000000000000',
     '0000000000000000000000000000000000000000000000000000000000000000']

converted_initial_vector_0 = bytearray([0 for i in range(200)])
converted_next_block_0 = bytearray([0 for i in range(200)])

convert_anoying_bit_to_byte_array(converted_initial_vector_0,initial_vector_0);
convert_anoying_bit_to_byte_array(converted_next_block_0,next_block_0);

# print("vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv")
# print(bytes.decode(binascii.hexlify(cut_absorb(converted_initial_vector_0))));
# print("ccccccccccccccccccccccccccccccccccccccccc")
# print(bytes.decode(binascii.hexlify(cut_capacity(converted_initial_vector_0))));
# print("sssssssssssssssssssssssssssssssssssssssss")

t0 = KeccakF1600(converted_initial_vector_0)
t0_n = KeccakF1600(converted_next_block_0)

convert_anoying_bit_to_byte_array(converted_initial_vector_0,initial_vector_0);
convert_anoying_bit_to_byte_array(converted_next_block_0,next_block_0);

input1 = bytearray([0 for i in range(136)]) + bytearray([0 for i in range(136)])
input2 = cut_absorb(converted_next_block_0) + gen_next_absorb(t0_n,t0)

print("-----------------------------------------")
print("input 1:")
print(bytes.decode(binascii.hexlify(input1)));
print("-----------------------------------------")

clean = bytearray([0 for i in range(200)])

output = Keccak(converted_initial_vector_0,1088,512, input1, 0x06, 256//8)
print("resulting hash :")
print(bytes.decode(binascii.hexlify(output)));
print("#########################################")
print()
print("input 2:")
print(bytes.decode(binascii.hexlify(input2)));
print("-----------------------------------------")
output = Keccak(clean,1088,512, input2, 0x06, 256//8)
print("resulting hash :")
print(bytes.decode(binascii.hexlify(output)));