lenerd/VolgaCTF 2018 Quals

## pwn-forbidden.sage
#!/usr/bin/env sage

from struct import pack, unpack
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import (
    Cipher, algorithms, modes
)

# Pwn script for the Forbidden challenge of VolgaCTF 2018 Quals.
# Written by lenerd for Cyclopropenylidene.

# AES-GCM was used to authenticate/encrypt three messages with authenticated
# data using the same key and iv.
# See also Section 3 "A forbidden attack with repeated IV" in
# https://pdfs.semanticscholar.org/473d/4065d08ce6d8d467da4de57b8df664327d8b.pdf


# given messages
m1 = "From: John Doe\nTo: John Doe\nSend 100 BTC"
m2 = "From: VolgaCTF\nTo: VolgaCTF\nSend 0.1 BTC"
m3 = "From: John Doe\nTo: VolgaCTF\nSend ALL BTC"
# given associated data
a1 = "John Doe"
a2 = "VolgaCTF"
a3 = a1
# given ciphertexts
c1 = "1761e540522379aab5ef05eabc98516fa47ae0c586026e9955fd551fe5b6ec37e636d9fd389285f3".decode('hex')
c2 = "1761e540522365aab1e644ed87bb516fa47ae0d9860667d852c6761fe5b6ec37e637c7fc389285f3".decode('hex')
c3 = "1761e540522379aab5ef05eabc98516fa47ae0d9860667d852c6761fe5b6ec37e646a581389285f3".decode('hex')
# given tags
t1 = "0674d6e42069a10f18375fc8876aa04d".decode('hex')
t2 = "cf61b77c044a8fb1566352bd5dd2f69f".decode('hex')


# Some test data, generated with the following key:
# key: 42424242424242424242424242424242
# hash_key: 73446bba4a5a60c9410cf3d8805b910a
#  c1 = "3965387e2d8c715b272fbcc3a9cb1d88d7c7fb101073c4ea5f2693153a406a803f7d845317fca1d1".decode('hex')
#  c2 = "3965387e2d8c6d5b2326fdc492e81d88d7c7fb0c1077cdab581db0153a406a803f7c9a5217fca1d1".decode('hex')
#  c3 = "3965387e2d8c715b272fbcc3a9cb1d88d7c7fb0c1077cdab581db0153a406a803f0df82f17fca1d1".decode('hex')
#  t1 = "c444aa7d870ab39b9d4322a4ae0379cc".decode('hex')
#  t2 = "44cf34f78a7293f144d6c725a6759ed4".decode('hex')
#  t3 = 'f699fefa589d55f24583abc818c87453'.decode('hex')


# Galois field of size 2^128 used in GCM
F.<a> = GF(2^128, name='a', modulus=x^128 + x^7 + x^2 + x + 1)
# Polynomial ring over the GF
R.<X> = PolynomialRing(F)

# convert 16 bytes to a field element
def toGF(s):
    assert len(s) == 16
    return F(list("{:0128b}".format(int(s.encode('hex'), 16))))

# convert a field element to 16 bytes
def fromGF(p):
    bits = list(p.polynomial())
    bits += [0]*(128 - len(bits))

    s = '{:032x}'.format(int(''.join(str(b) for b in bits), 2))
    return s.decode('hex')

# test conversion function
def test():
    s = ('80' + 15*'00').decode('hex')
    p = toGF(s)
    sx = fromGF(p)
    assert s == sx
    x = F.random_element()
    y = toGF(fromGF(x))
    assert x == y

test()


# Xor of bytes
def xor(xs, ys):
    return ''.join(chr(ord(x) ^^ ord(y)) for x, y in zip(xs, ys))

# Increment 128 bit integer given as bytes
def inc128(cnt):
    cnt_a, cnt_b = unpack('>QQ', cnt)
    cnt_b = (cnt_b + 1) & ~int(1 << 64)
    if cnt_b == 0:
        cnt_a = (cnt_a + 1) & ~int(1 << 64)
    return pack('>QQ', cnt_a, cnt_b)

# CTR mode encryption
def ctr(ecb, cnt, plaintext):
    nblocks = ceil(len(plaintext) / 16)
    keystream = ''
    for i in range(nblocks):
        keystream += ecb.update(cnt)
        cnt = inc128(cnt)
    return xor(plaintext, keystream)

# GHash
def ghash(h, blocks):
    h = toGF(h)
    res = F(0)
    for b in blocks:
        res += toGF(b)
        res *= h
    return fromGF(res)

# Pad and split bytes into 16B blocks
def split_blocks(data):
    data += '\x00'*(16 - (len(data) % 16))
    assert len(data) % 16 == 0
    return [data[16*i:16*(i+1)] for i in range(len(data) // 16)]

# GCM encryption
def gcm_encrypt(key, iv, plaintext, assoc_data):
    ecb = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend()).encryptor()
    h = ecb.update('\x00'*16)
    j0 = ghash(h, [iv, '\x00'*8 + pack('>Q', 128)])
    ciphertext = ctr(ecb, inc128(j0), plaintext)
    assoc_blocks = split_blocks(assoc_data)
    ciphertext_blocks = split_blocks(ciphertext)
    lens = pack('>QQ', len(assoc_data)*8, len(ciphertext)*8)
    s = ghash(h, assoc_blocks + ciphertext_blocks + [lens])
    tag = xor(ecb.update(j0), s)
    return ciphertext, tag

# Some testing of the above GCM implementation. Ignore this.
# =======================================================
#  key = "\x42"*16
#  iv = "9313225df88406e555909c5aff5269aa".decode('hex')
#  M1 = m1
#  C1, T1 = gcm_encrypt(key, iv, M1, a1)
#  M2 = m2
#  C2, T2 = gcm_encrypt(key, iv, M2, a2)
#  print("key {}".format(key.encode('hex')))
#  print("iv  {}".format(iv.encode('hex')))
#  print("M1  {}".format(M1.encode('hex')))
#  print("C1  {}".format(C1.encode('hex')))
#  print("T1  {}".format(T1.encode('hex')))
#  print("M2  {}".format(M2.encode('hex')))
#  print("C2  {}".format(C2.encode('hex')))
#  print("T2  {}".format(T2.encode('hex')))
#
#  ecb = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend()).encryptor()
#  c11, c12, c13 = map(toGF, split_blocks(c1))
#  c21, c22, c23 = map(toGF, split_blocks(c2))
#  a11 = map(toGF, split_blocks(a1))[0]
#  a21 = map(toGF, split_blocks(a2))[0]
#  lens = toGF(pack('>QQ', len(a1)*8, len(c1)*8))
#  h = toGF(ecb.update('\x00'*16))
#
#  s1 = ((((((a11 * h) + c11) * h + c12) * h + c13) * h + lens) * h) #+ e
#  print("s1  {}".format(fromGF(s1).encode('hex')))
#  s2 = ((((((a21 * h) + c21) * h + c22) * h + c23) * h + lens) * h) #+ e
#  print("s2  {}".format(fromGF(s2).encode('hex')))
#
#  j0 = ghash(fromGF(h), [iv, '\x00'*8 + pack('>Q', 128)])
#  e = toGF(ecb.update(j0))
#
#  #  t1 = s1 + e
#  #  t2 = s2 + e
#  #  print("t1  {}".format(fromGF(t1).encode('hex')))
#  #  print("t2  {}".format(fromGF(t2).encode('hex')))
# =======================================================


# Convert blocks of associated data, ciphertext, lengths, tags to field
# elements.
c11, c12, c13 = map(toGF, split_blocks(c1))
c21, c22, c23 = map(toGF, split_blocks(c2))
a11 = map(toGF, split_blocks(a1))[0]
a21 = map(toGF, split_blocks(a2))[0]
lens = toGF(pack('>QQ', len(a1)*8, len(c1)*8))
t1 = toGF(t1)
t2 = toGF(t2)


# Authentication with GCM:
# 128 bit strings are interpreted as elements of GF(2^128).
# Let h = E_k(00..0) be the authentication key, l the encoding of the lengths
# of the associated data and the plaintext as two 64 bit blocks.
# Authentication tag is computed the following way:
# s = GHash(h, [a11, c11, c12, c13])
#   = (((((a11 * h) + c11) * h + c12) * h + c13) * h + l) * h
#   = a_11 * h^5 + c11 * h^4 + c12 * h^3 + c13 * h^2 + l * h
# tag = s + E_k(GHash(h, [iv, 0^64 || len(iv)]))

# The tags for the first two messages yield the following equations.
#   t1 = a_11 * h^5 + c11 * h^4 + c12 * h^3 + c13 * h^2 + l * h
#   t2 = a_21 * h^5 + c21 * h^4 + c22 * h^3 + c23 * h^2 + l * h
# Hence, we can construct the following polynomial that has root h.
p = (a11 + a21) * X^5 + (c11 + c21) * X^4 + (c12 + c22) * X^3 + (c13 + c23) * X^2 + (t1 + t2)

# In our case the p has two roots.
auth_key_candidates = [r for r, _ in p.roots()]
assert len(auth_key_candidates) > 0

# Find the difference between messages 1 and 3
diff = xor(m1, m3)
d1, d2, d3 = map(toGF, split_blocks(diff))

# We use the recovered authentication key to compute a valid auth tag for the
# message 3.
for h in auth_key_candidates:
    dx = d1 * h^4 + d2 * h^3 + d3 * h^2
    t3 = t1 + dx
    print('possible flag:  VolgaCTF{{{}}}'.format(fromGF(t3).encode('hex')))


# VolgaCTF{b084b54cb9d114c6912926f4ec42dbcf}

## pwn-nonsense.sage
#!/usr/bin/env sage

import hashlib

# Pwn script for the Nonsense challenge of VolgaCTF 2018 Quals.
# Written by lenerd for Cyclopropenylidene.

# DSA was used with a linear congruential generator as RNG
# See also https://cseweb.ucsd.edu/~mihir/papers/dss-lcg.pdf
#

# DSA involves the following computations (k nonce, x secret key):
#   r = (g^k mod p) mod q
#   s = k^-1 * (H(M) + x * r) mod q
# Since an LCG with parameters a, b, m is used, consecutive ks are related:
#   k2 = a * k1 + b  (mod m)

# We get (more than) two signatures ((r1, s1), (r2, s2)). Therefore, we can
# construct the following system of linear equations with unknowns k1, k2, x:
#   s1 * k1           - x * r1 = H(m1)  (mod q)
#             s2 * k2 - x * r2 = H(m2)  (mod q)
#   -a * k1      + k2          = b      (mod m)

# Since m = q, this is easy to solve (see e.g. Section 3.1 of mentioned paper).


# DSA Parameters
g = 88125476599184486094790650278890368754888757655708027167453919435240304366395317529470831972495061725782138055221217302201589783769854366885231779596493602609634987052252863192229681106120745605931395095346012008056087730365567429009621913663891364224332141824100071928803984724198563312854816667719924760795
y = 18433140630820275907539488836516835408779542939919052226997023049612786224410259583219376467254099629677919271852380455772458762645735404211432242965871926570632297310903219184400775850110990886397212284518923292433738871549404880989194321082225561448101852260505727288411231941413212099434438610673556403084
p = 89884656743115795425395461605176038709311877189759878663122975144592708970495081723016152663257074178905267744494172937616748015651504839967430700901664125135185879852143653824715409554960402343311756382635207838848036159350785779959423221882215217326708017212309285537596191495074550701770862125817284985959
q = 1118817215266473099401489299835945027713635248219

# Finite field modulo q
F = GF(q)

# LCG Parameters
a = 3437776292996777467976657547577967657547
b = 828669865469592426262363475477574643634
m = 1118817215266473099401489299835945027713635248219

assert q == m

# Given message/signature pairs
m1, r1, s1 = ('VolgaCTF{nKpV/dmkBeQ0n9Mz0g9eGQ==}', 1030409245884476193717141088285092765299686864672, 830067187231135666416948244755306407163838542785)
m2, #!/usr/bin/env sage

import hashlib

# Pwn script for the Nonsense challenge of VolgaCTF 2018 Quals.
# Written by lenerd for Cyclopropenylidene.

# DSA was used with a linear congruential generator as RNG
# See also https://cseweb.ucsd.edu/~mihir/papers/dss-lcg.pdf
#

# DSA involves the following computations (k nonce, x secret key):
#   r = (g^k mod p) mod q
#   s = k^-1 * (H(M) + x * r) mod q
# Since an LCG with parameters a, b, m is used, consecutive ks are related:
#   k2 = a * k1 + b  (mod m)

# We get (more than) two signatures ((r1, s1), (r2, s2)). Therefore, we can
# construct the following system of linear equations with unknowns k1, k2, x:
#   s1 * k1           - x * r1 = H(m1)  (mod q)
#             s2 * k2 - x * r2 = H(m2)  (mod q)
#   -a * k1      + k2          = b      (mod m)

# Since m = q, this is easy to solve (see e.g. Section 3.1 of mentioned paper).


# DSA Parameters
g = 88125476599184486094790650278890368754888757655708027167453919435240304366395317529470831972495061725782138055221217302201589783769854366885231779596493602609634987052252863192229681106120745605931395095346012008056087730365567429009621913663891364224332141824100071928803984724198563312854816667719924760795
y = 18433140630820275907539488836516835408779542939919052226997023049612786224410259583219376467254099629677919271852380455772458762645735404211432242965871926570632297310903219184400775850110990886397212284518923292433738871549404880989194321082225561448101852260505727288411231941413212099434438610673556403084
p = 89884656743115795425395461605176038709311877189759878663122975144592708970495081723016152663257074178905267744494172937616748015651504839967430700901664125135185879852143653824715409554960402343311756382635207838848036159350785779959423221882215217326708017212309285537596191495074550701770862125817284985959
q = 1118817215266473099401489299835945027713635248219

# Finite field modulo q
F = GF(q)

# LCG Parameters
a = 3437776292996777467976657547577967657547
b = 828669865469592426262363475477574643634
m = 1118817215266473099401489299835945027713635248219

assert q == m

# Given message/signature pairs
m1, r1, s1 = ('VolgaCTF{nKpV/dmkBeQ0n9Mz0g9eGQ==}', 1030409245884476193717141088285092765299686864672, 830067187231135666416948244755306407163838542785)
m2, r2, s2 = ('VolgaCTF{KtetaQ4YT8PhTL3O4vsfDg==}', 403903893160663712713225718481237860747338118174, 803753330562964683180744246754284061126230157465)
h1 = int(hashlib.md5(m1).hexdigest(), 16)
h2 = int(hashlib.md5(m2).hexdigest(), 16)


M = Matrix(F, [
    [s1,  0, -r1],
    [ 0, s2, -r2],
    [-a,  1,   0],
])
v = vector(F, [h1, h2, b])

sol = M.solve_right(v)

k1, k2, x = sol


print("recovered secet key: x = 0x{:x}".format(int(x)))r2, s2 = ('VolgaCTF{KtetaQ4YT8PhTL3O4vsfDg==}', 403903893160663712713225718481237860747338118174, 803753330562964683180744246754284061126230157465)
h1 = int(hashlib.md5(m1).hexdigest(), 16)
h2 = int(hashlib.md5(m2).hexdigest(), 16)


M = Matrix(F, [
    [s1,  0, -r1],
    [ 0, s2, -r2],
    [-a,  1,   0],
])
v = vector(F, [h1, h2, b])

sol = M.solve_right(v)

k1, k2, x = sol


print("recovered secet key: x = 0x{:x}".format(int(x)))

## VolgaCTF 2018 Quals
Scripts solving two crypto challenges from VolgaCTF 2018 Quals
	#!/usr/bin/env sage

	from struct import pack, unpack
	from cryptography.hazmat.backends import default_backend
	from cryptography.hazmat.primitives.ciphers import (
	Cipher, algorithms, modes
	)

	# Pwn script for the Forbidden challenge of VolgaCTF 2018 Quals.
	# Written by lenerd for Cyclopropenylidene.

	# AES-GCM was used to authenticate/encrypt three messages with authenticated
	# data using the same key and iv.
	# See also Section 3 "A forbidden attack with repeated IV" in
	# https://pdfs.semanticscholar.org/473d/4065d08ce6d8d467da4de57b8df664327d8b.pdf


	# given messages
	m1 = "From: John Doe\nTo: John Doe\nSend 100 BTC"
	m2 = "From: VolgaCTF\nTo: VolgaCTF\nSend 0.1 BTC"
	m3 = "From: John Doe\nTo: VolgaCTF\nSend ALL BTC"
	# given associated data
	a1 = "John Doe"
	a2 = "VolgaCTF"
	a3 = a1
	# given ciphertexts
	c1 = "1761e540522379aab5ef05eabc98516fa47ae0c586026e9955fd551fe5b6ec37e636d9fd389285f3".decode('hex')
	c2 = "1761e540522365aab1e644ed87bb516fa47ae0d9860667d852c6761fe5b6ec37e637c7fc389285f3".decode('hex')
	c3 = "1761e540522379aab5ef05eabc98516fa47ae0d9860667d852c6761fe5b6ec37e646a581389285f3".decode('hex')
	# given tags
	t1 = "0674d6e42069a10f18375fc8876aa04d".decode('hex')
	t2 = "cf61b77c044a8fb1566352bd5dd2f69f".decode('hex')


	# Some test data, generated with the following key:
	# key: 42424242424242424242424242424242
	# hash_key: 73446bba4a5a60c9410cf3d8805b910a
	# c1 = "3965387e2d8c715b272fbcc3a9cb1d88d7c7fb101073c4ea5f2693153a406a803f7d845317fca1d1".decode('hex')
	# c2 = "3965387e2d8c6d5b2326fdc492e81d88d7c7fb0c1077cdab581db0153a406a803f7c9a5217fca1d1".decode('hex')
	# c3 = "3965387e2d8c715b272fbcc3a9cb1d88d7c7fb0c1077cdab581db0153a406a803f0df82f17fca1d1".decode('hex')
	# t1 = "c444aa7d870ab39b9d4322a4ae0379cc".decode('hex')
	# t2 = "44cf34f78a7293f144d6c725a6759ed4".decode('hex')
	# t3 = 'f699fefa589d55f24583abc818c87453'.decode('hex')


	# Galois field of size 2^128 used in GCM
	F.<a> = GF(2^128, name='a', modulus=x^128 + x^7 + x^2 + x + 1)
	# Polynomial ring over the GF
	R.<X> = PolynomialRing(F)

	# convert 16 bytes to a field element
	def toGF(s):
	assert len(s) == 16
	return F(list("{:0128b}".format(int(s.encode('hex'), 16))))

	# convert a field element to 16 bytes
	def fromGF(p):
	bits = list(p.polynomial())
	bits += [0]*(128 - len(bits))

	s = '{:032x}'.format(int(''.join(str(b) for b in bits), 2))
	return s.decode('hex')

	# test conversion function
	def test():
	s = ('80' + 15*'00').decode('hex')
	p = toGF(s)
	sx = fromGF(p)
	assert s == sx
	x = F.random_element()
	y = toGF(fromGF(x))
	assert x == y

	test()


	# Xor of bytes
	def xor(xs, ys):
	return ''.join(chr(ord(x) ^^ ord(y)) for x, y in zip(xs, ys))

	# Increment 128 bit integer given as bytes
	def inc128(cnt):
	cnt_a, cnt_b = unpack('>QQ', cnt)
	cnt_b = (cnt_b + 1) & ~int(1 << 64)
	if cnt_b == 0:
	cnt_a = (cnt_a + 1) & ~int(1 << 64)
	return pack('>QQ', cnt_a, cnt_b)

	# CTR mode encryption
	def ctr(ecb, cnt, plaintext):
	nblocks = ceil(len(plaintext) / 16)
	keystream = ''
	for i in range(nblocks):
	keystream += ecb.update(cnt)
	cnt = inc128(cnt)
	return xor(plaintext, keystream)

	# GHash
	def ghash(h, blocks):
	h = toGF(h)
	res = F(0)
	for b in blocks:
	res += toGF(b)
	res *= h
	return fromGF(res)

	# Pad and split bytes into 16B blocks
	def split_blocks(data):
	data += '\x00'*(16 - (len(data) % 16))
	assert len(data) % 16 == 0
	return [data[16i:16(i+1)] for i in range(len(data) // 16)]

	# GCM encryption
	def gcm_encrypt(key, iv, plaintext, assoc_data):
	ecb = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend()).encryptor()
	h = ecb.update('\x00'*16)
	j0 = ghash(h, [iv, '\x00'*8 + pack('>Q', 128)])
	ciphertext = ctr(ecb, inc128(j0), plaintext)
	assoc_blocks = split_blocks(assoc_data)
	ciphertext_blocks = split_blocks(ciphertext)
	lens = pack('>QQ', len(assoc_data)8, len(ciphertext)8)
	s = ghash(h, assoc_blocks + ciphertext_blocks + [lens])
	tag = xor(ecb.update(j0), s)
	return ciphertext, tag

	# Some testing of the above GCM implementation. Ignore this.
	# =======================================================
	# key = "\x42"*16
	# iv = "9313225df88406e555909c5aff5269aa".decode('hex')
	# M1 = m1
	# C1, T1 = gcm_encrypt(key, iv, M1, a1)
	# M2 = m2
	# C2, T2 = gcm_encrypt(key, iv, M2, a2)
	# print("key {}".format(key.encode('hex')))
	# print("iv {}".format(iv.encode('hex')))
	# print("M1 {}".format(M1.encode('hex')))
	# print("C1 {}".format(C1.encode('hex')))
	# print("T1 {}".format(T1.encode('hex')))
	# print("M2 {}".format(M2.encode('hex')))
	# print("C2 {}".format(C2.encode('hex')))
	# print("T2 {}".format(T2.encode('hex')))
	#
	# ecb = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend()).encryptor()
	# c11, c12, c13 = map(toGF, split_blocks(c1))
	# c21, c22, c23 = map(toGF, split_blocks(c2))
	# a11 = map(toGF, split_blocks(a1))[0]
	# a21 = map(toGF, split_blocks(a2))[0]
	# lens = toGF(pack('>QQ', len(a1)8, len(c1)8))
	# h = toGF(ecb.update('\x00'*16))
	#
	# s1 = ((((((a11 * h) + c11) * h + c12) * h + c13) * h + lens) * h) #+ e
	# print("s1 {}".format(fromGF(s1).encode('hex')))
	# s2 = ((((((a21 * h) + c21) * h + c22) * h + c23) * h + lens) * h) #+ e
	# print("s2 {}".format(fromGF(s2).encode('hex')))
	#
	# j0 = ghash(fromGF(h), [iv, '\x00'*8 + pack('>Q', 128)])
	# e = toGF(ecb.update(j0))
	#
	# # t1 = s1 + e
	# # t2 = s2 + e
	# # print("t1 {}".format(fromGF(t1).encode('hex')))
	# # print("t2 {}".format(fromGF(t2).encode('hex')))
	# =======================================================


	# Convert blocks of associated data, ciphertext, lengths, tags to field
	# elements.
	c11, c12, c13 = map(toGF, split_blocks(c1))
	c21, c22, c23 = map(toGF, split_blocks(c2))
	a11 = map(toGF, split_blocks(a1))[0]
	a21 = map(toGF, split_blocks(a2))[0]
	lens = toGF(pack('>QQ', len(a1)8, len(c1)8))
	t1 = toGF(t1)
	t2 = toGF(t2)


	# Authentication with GCM:
	# 128 bit strings are interpreted as elements of GF(2^128).
	# Let h = E_k(00..0) be the authentication key, l the encoding of the lengths
	# of the associated data and the plaintext as two 64 bit blocks.
	# Authentication tag is computed the following way:
	# s = GHash(h, [a11, c11, c12, c13])
	# = (((((a11 * h) + c11) * h + c12) * h + c13) * h + l) * h
	# = a_11 * h^5 + c11 * h^4 + c12 * h^3 + c13 * h^2 + l * h
	# tag = s + E_k(GHash(h, [iv, 0^64 \|\| len(iv)]))

	# The tags for the first two messages yield the following equations.
	# t1 = a_11 * h^5 + c11 * h^4 + c12 * h^3 + c13 * h^2 + l * h
	# t2 = a_21 * h^5 + c21 * h^4 + c22 * h^3 + c23 * h^2 + l * h
	# Hence, we can construct the following polynomial that has root h.
	p = (a11 + a21) * X^5 + (c11 + c21) * X^4 + (c12 + c22) * X^3 + (c13 + c23) * X^2 + (t1 + t2)

	# In our case the p has two roots.
	auth_key_candidates = [r for r, _ in p.roots()]
	assert len(auth_key_candidates) > 0

	# Find the difference between messages 1 and 3
	diff = xor(m1, m3)
	d1, d2, d3 = map(toGF, split_blocks(diff))

	# We use the recovered authentication key to compute a valid auth tag for the
	# message 3.
	for h in auth_key_candidates:
	dx = d1 * h^4 + d2 * h^3 + d3 * h^2
	t3 = t1 + dx
	print('possible flag: VolgaCTF{{{}}}'.format(fromGF(t3).encode('hex')))


	# VolgaCTF{b084b54cb9d114c6912926f4ec42dbcf}
	#!/usr/bin/env sage

	import hashlib

	# Pwn script for the Nonsense challenge of VolgaCTF 2018 Quals.
	# Written by lenerd for Cyclopropenylidene.

	# DSA was used with a linear congruential generator as RNG
	# See also https://cseweb.ucsd.edu/~mihir/papers/dss-lcg.pdf
	#

	# DSA involves the following computations (k nonce, x secret key):
	# r = (g^k mod p) mod q
	# s = k^-1 * (H(M) + x * r) mod q
	# Since an LCG with parameters a, b, m is used, consecutive ks are related:
	# k2 = a * k1 + b (mod m)

	# We get (more than) two signatures ((r1, s1), (r2, s2)). Therefore, we can
	# construct the following system of linear equations with unknowns k1, k2, x:
	# s1 * k1 - x * r1 = H(m1) (mod q)
	# s2 * k2 - x * r2 = H(m2) (mod q)
	# -a * k1 + k2 = b (mod m)

	# Since m = q, this is easy to solve (see e.g. Section 3.1 of mentioned paper).


	# DSA Parameters
	g = 88125476599184486094790650278890368754888757655708027167453919435240304366395317529470831972495061725782138055221217302201589783769854366885231779596493602609634987052252863192229681106120745605931395095346012008056087730365567429009621913663891364224332141824100071928803984724198563312854816667719924760795
	y = 18433140630820275907539488836516835408779542939919052226997023049612786224410259583219376467254099629677919271852380455772458762645735404211432242965871926570632297310903219184400775850110990886397212284518923292433738871549404880989194321082225561448101852260505727288411231941413212099434438610673556403084
	p = 89884656743115795425395461605176038709311877189759878663122975144592708970495081723016152663257074178905267744494172937616748015651504839967430700901664125135185879852143653824715409554960402343311756382635207838848036159350785779959423221882215217326708017212309285537596191495074550701770862125817284985959
	q = 1118817215266473099401489299835945027713635248219

	# Finite field modulo q
	F = GF(q)

	# LCG Parameters
	a = 3437776292996777467976657547577967657547
	b = 828669865469592426262363475477574643634
	m = 1118817215266473099401489299835945027713635248219

	assert q == m

	# Given message/signature pairs
	m1, r1, s1 = ('VolgaCTF{nKpV/dmkBeQ0n9Mz0g9eGQ==}', 1030409245884476193717141088285092765299686864672, 830067187231135666416948244755306407163838542785)
	m2, #!/usr/bin/env sage

	import hashlib

	# Pwn script for the Nonsense challenge of VolgaCTF 2018 Quals.
	# Written by lenerd for Cyclopropenylidene.

	# DSA was used with a linear congruential generator as RNG
	# See also https://cseweb.ucsd.edu/~mihir/papers/dss-lcg.pdf
	#

	# DSA involves the following computations (k nonce, x secret key):
	# r = (g^k mod p) mod q
	# s = k^-1 * (H(M) + x * r) mod q
	# Since an LCG with parameters a, b, m is used, consecutive ks are related:
	# k2 = a * k1 + b (mod m)

	# We get (more than) two signatures ((r1, s1), (r2, s2)). Therefore, we can
	# construct the following system of linear equations with unknowns k1, k2, x:
	# s1 * k1 - x * r1 = H(m1) (mod q)
	# s2 * k2 - x * r2 = H(m2) (mod q)
	# -a * k1 + k2 = b (mod m)

	# Since m = q, this is easy to solve (see e.g. Section 3.1 of mentioned paper).


	# DSA Parameters
	g = 88125476599184486094790650278890368754888757655708027167453919435240304366395317529470831972495061725782138055221217302201589783769854366885231779596493602609634987052252863192229681106120745605931395095346012008056087730365567429009621913663891364224332141824100071928803984724198563312854816667719924760795
	y = 18433140630820275907539488836516835408779542939919052226997023049612786224410259583219376467254099629677919271852380455772458762645735404211432242965871926570632297310903219184400775850110990886397212284518923292433738871549404880989194321082225561448101852260505727288411231941413212099434438610673556403084
	p = 89884656743115795425395461605176038709311877189759878663122975144592708970495081723016152663257074178905267744494172937616748015651504839967430700901664125135185879852143653824715409554960402343311756382635207838848036159350785779959423221882215217326708017212309285537596191495074550701770862125817284985959
	q = 1118817215266473099401489299835945027713635248219

	# Finite field modulo q
	F = GF(q)

	# LCG Parameters
	a = 3437776292996777467976657547577967657547
	b = 828669865469592426262363475477574643634
	m = 1118817215266473099401489299835945027713635248219

	assert q == m

	# Given message/signature pairs
	m1, r1, s1 = ('VolgaCTF{nKpV/dmkBeQ0n9Mz0g9eGQ==}', 1030409245884476193717141088285092765299686864672, 830067187231135666416948244755306407163838542785)
	m2, r2, s2 = ('VolgaCTF{KtetaQ4YT8PhTL3O4vsfDg==}', 403903893160663712713225718481237860747338118174, 803753330562964683180744246754284061126230157465)
	h1 = int(hashlib.md5(m1).hexdigest(), 16)
	h2 = int(hashlib.md5(m2).hexdigest(), 16)


	M = Matrix(F, [
	[s1, 0, -r1],
	[ 0, s2, -r2],
	[-a, 1, 0],
	])
	v = vector(F, [h1, h2, b])

	sol = M.solve_right(v)

	k1, k2, x = sol


	print("recovered secet key: x = 0x{:x}".format(int(x)))r2, s2 = ('VolgaCTF{KtetaQ4YT8PhTL3O4vsfDg==}', 403903893160663712713225718481237860747338118174, 803753330562964683180744246754284061126230157465)
	h1 = int(hashlib.md5(m1).hexdigest(), 16)
	h2 = int(hashlib.md5(m2).hexdigest(), 16)


	M = Matrix(F, [
	[s1, 0, -r1],
	[ 0, s2, -r2],
	[-a, 1, 0],
	])
	v = vector(F, [h1, h2, b])

	sol = M.solve_right(v)

	k1, k2, x = sol


	print("recovered secet key: x = 0x{:x}".format(int(x)))