NSU CRYPTO 2017 - Problem 4 - FNV2 Hash

1_collision_2nd_preimage.py

'''
Explanation at
https://drive.google.com/open?id=1gDRoulcbWfh-T6KBLwvV8g_xb7dT3Erx
'''

from sage.all import *

mod = 2**128
h0 = 144066263297769815596495629667062367629
g = 2**88 + 315

K = 2**128
B = K**2 # big enough

if 1: # short collision
    N = 17           # number of bytes
    base = [128] * N # close to this value
    '''
    [128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128]
    ASCII: '\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80'
    0xfa3824bfb69587b859aa5b77536cd63fL

    [192, 123, 55, 93, 181, 109, 138, 206, 172, 80, 67, 129, 208, 102, 150, 56, 159]
    ASCII: '\xc0{7]\xb5m\x8a\xce\xacPC\x81\xd0f\x968\x9f'
    0xfa3824bfb69587b859aa5b77536cd63fL
    '''

else: # readable (second preimage)
    base = map(ord, "~~~~ NSU CRYPTO IS FUN! ~~~~")
    N = len(base)
    '''
    [126, 126, 126, 126, 32, 78, 83, 85, 32, 67, 82, 89, 80, 84, 79, 32, 73, 83, 32, 70, 85, 78, 33, 32, 126, 126, 126, 126]
    ASCII: '~~~~ NSU CRYPTO IS FUN! ~~~~'
    0x8e10c895b91c6cba80b57a5e555b7f6L

    [130, 133, 123, 131, 39, 76, 87, 83, 30, 68, 82, 78, 73, 86, 75, 23, 83, 81, 39, 63, 72, 87, 42, 28, 121, 128, 124, 122]
    ASCII: "\x82\x85{\x83'LWS\x1eDRNIVK\x17SQ'?HW*\x1cy\x80|z"
    0x8e10c895b91c6cba80b57a5e555b7f6L
    '''

htarget = 0

m = matrix(ZZ, N + 1, N + 2)
for i in xrange(N):
    ge = pow(g, N-i, mod)
    m[i,0] = ge
    m[i,1+i] = 1
m[N,0] = mod

for i in xrange(N+1):
    m[i,0] *= K

ml = m.LLL()

sol = ml.rows()[0]
print "Sol:", sol
if sol[0] != 0:
    print "Zero not reached, increase K"
    quit()

if not base:
    base = [BASE] * N
msg = []
for i in xrange(N):
    msg.append(base[i] + sol[1+i])
    if not (0 <= msg[-1] <= 255):
        print "Need more bytes!"
        quit()


def FNV2(msg):
    h = h0
    for xi in msg:
        h = (h + xi) * g % mod
    return int(h)


print base
print "ASCII:", `"".join(map(chr, base))`
print hex(FNV2(base)), FNV2(base)
print
print msg
print "ASCII:", `"".join(map(chr, msg))`
print hex(FNV2(msg)), FNV2(base)

2_preimage.py

from sage.all import *

TARGET_HASH = 2**128 - 1 # tcfmeeqplmmiolhnpohkljhocslnygdn
TARGET_HASH = 0          # orshtmfbpjpnpekkqromurkhvnqpjlst
TARGET_HASH = 77777777777777777777777777777777777777 # pclumkounkpqunoqhgjmjplwotkuqhik

mod = 2**128
h0 = 144066263297769815596495629667062367629
g = 2**88 + 315

N = 32     # number of bytes
K = 2**128
B = K**2   # big enough
BASE = ord("a") + 13  # close to this value

htarget = (-TARGET_HASH + h0 * pow(g, N, mod)) % mod

m = matrix(ZZ, N + 2, N + 2)
for i in xrange(N):
    ge = pow(g, N-i, mod)
    htarget = (htarget + ge * BASE) % mod
    m[i,0] = ge
    m[i,1+i] = 1

m[N,0] = htarget
m[N,1+N] = B
m[N+1,0] = mod
for i in xrange(N+2):
    m[i,0] *= K

ml = m.LLL()

sol = ml.rows()[-1]
print "Sol:", sol
if sol[0] != 0:
    print "Zero not reached, increase K"
    quit()
if sol[-1] != B:
    print "B is not big enough, increase"
    quit()

base = []
msg = []
testsum = 0
for i in xrange(N):
    base.append(BASE)
    msg.append(BASE + sol[1+i])
    if not (0 <= msg[-1] <= 255):
        print "Need more bytes!"
        quit()

def FNV2(msg):
    h = h0
    for xi in msg:
        h = (h + xi) * g % mod
    return h

print msg
print "ASCII:", `"".join(map(chr, msg))`
print hex(FNV2(msg)), FNV2(msg)