[0CTF/TCTF 2019] babysponge

All you need is only this article. Since the capicity(=48) is not that big, collision can easily found.

 

My desktop requires 5-7 hrs to hashing 16 millions of plain, which is not enough until competition ends, so our team uses expansive instances in AWS. (about 5$ per hour 8ㅅ8) I heard that using Pypy is almost 4 to 10 times faster than Py. So rather than py, it might be better to use Pypy.

from hashlib import sha256
import random,sys,string
#import CompactFIPS202


# -*- coding: utf-8 -*-
# Implementation by Gilles Van Assche, hereby denoted as "the implementer".
#
# For more information, feedback or questions, please refer to our website:
# https://keccak.team/
#
# To the extent possible under law, the implementer has waived all copyright
# and related or neighboring rights to the source code in this file.
# http://creativecommons.org/publicdomain/zero/1.0/

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

#(1552, 48, bytearray(msg), 0x06, 32)
#rateInBytes = 194
def Keccak(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)):
        blockSize = min(len(inputBytes)-inputOffset, rateInBytes)
        for i in range(blockSize):
            state[i] = state[i] ^ inputBytes[i+inputOffset]
        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


#(1592, 8, bytearray(msg), 0x06, 32)
#rateInBytes = 199
def Keccak_vuln(rate, capacity, inputBytes, delimitedSuffix, outputByteLen,capacityonly):
    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)):
        blockSize = min(len(inputBytes)-inputOffset, rateInBytes)
        for i in range(blockSize):
            state[i] = state[i] ^ inputBytes[i+inputOffset]
        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))):
    #    print("not here")
    #    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)
    if capacityonly: return state[rateInBytes:]
    return state

def SHAKE128(inputBytes, outputByteLen):
    return Keccak(1344, 256, inputBytes, 0x1F, outputByteLen)

def SHAKE256(inputBytes, outputByteLen):
    return Keccak(1088, 512, inputBytes, 0x1F, outputByteLen)

def SHA3_224(inputBytes):
    return Keccak(1152, 448, inputBytes, 0x06, 224//8)

def SHA3_256(inputBytes):
    return Keccak(1088, 512, inputBytes, 0x06, 256//8)

def SHA3_384(inputBytes):
    return Keccak(832, 768, inputBytes, 0x06, 384//8)

def SHA3_512(inputBytes):
    return Keccak(576, 1024, inputBytes, 0x06, 512//8)


def dohash(msg):
  return bytes(Keccak(1552, 48, bytearray(msg), 0x06, 32))


def dohash_vuln(msg,capacityonly): # 200byte state자체를 반환
  return bytearray(Keccak_vuln(1552, 48, bytearray(msg), 0x06, 32,capacityonly))



t = bytearray(194)
for i in range(12,194):
  t[i] = random.randint(0,255)
D = dict()
t1 = bytearray()
t2 = bytearray()
cnt = 0
print("begin. Speed : 100000 plain per 100~150s")
print("To test 2**24 plain, requires 5-7 hours... :( ")
while True:
  t[0] += 1
  cnt += 1
  if cnt % 100000 == 0:
    print(cnt//100000)
  for i in range(6):
    if t[i] == 0x100:
      t[i]=0
      t[i+1]+=1
    else:
      break
  capacity = bytes(dohash_vuln(bytearray(t),1))
  if capacity in D:
    print("**** COLLISION CANDIDATE DETECTED ****")
    state = dohash_vuln(bytearray(t),0)
    #print(D[capacity])
    #print(state[:6])
    tmp = D[capacity]
    t1 = t[:]
    for i in range(6):
      t1[i] = tmp & 0xff
      tmp >>= 8
    t2 = t[:]
    print("t1 : ", t1.hex())
    print("t2 : ", t2.hex())
    break
  D[capacity] = cnt

state1 = dohash_vuln(t1,0)
bitrate1 = state1[:-6]
state2 = dohash_vuln(t2,0)
bitrate2 = state2[:-6]
xor = bytearray(194)
for i in range(194):
  xor[i] = bitrate1[i]^bitrate2[i]

col1 = t1+bytearray(194)
col2 = t2+xor
ret1 = dohash(col1)
ret2 = dohash(col2)
if ret1==ret2: # ret1,ret2 is hash result 
  print("GOOD JOB!! COLLISION OCCURED")
else:
  print("NONO...")
  exit(0)
print(ret1.hex())
print(ret2.hex())
print()
print("plain1\n"+col1.hex())
print("plain2\n"+col2.hex())