Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
NSU CRYPTO 2017 - Problem 4 - FNV2 Hash
'''
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)
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.