defcon-quals-2020-flag-sharing.py

from pwn import *

# some helper functions
def deco(x):
	return int.from_bytes(x, byteorder='little')

def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
 
def modinv(a, m):
	g, x, y = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m


# manually store a flag with option 3
# Our secret's ID is: ed3d7d
# Your shares are: [(49, 50331216912153726454049654038775423514532430966505096473834160520941526236136940), (45, 54823994255213496500676946730059759818553142106277896291143626823699355636565287), (82, 75444193790958862209466648276089504812875784556625951459151763133500407490834161)]


io = remote('ooo-flag-sharing.challenges.ooo', 5000)

io.recvuntil('Username: ')
io.sendline('kanav')

io.recvuntil('Choice: ')

# step 1: run through a loop in option 2 to determine when you get a singular matrix error
# you will get a the index of the secret stored in the `ed3d7d.1` file
for i in range(3,100):
	print(i)
	io.sendline('2')
	io.recvuntil('Enter the secret\'s ID: ')
	io.sendline('ed3d7d')
	io.recvuntil('Enter your shares of the secret: ')
	io.sendline('[ (0, 0), (1, 0), (2, 0), (%d, 0) ]' % i)
	print(io.recv())
# Result: 47 index in .1 file

# step 2: Run throught a loop in option 4 to determine when you get duplicate shares error
# you will get a the index of the secret stored in the `ed3d7d.2` file
for i in range(2,100):
	if i == 47:
		continue
	print(i)
	io.sendline('4')
	io.recvuntil('Enter the secret\'s ID: ')
	io.sendline('ed3d7d')
	io.recvuntil('Enter your shares of the secret: ')
	io.sendline('[ (0, 0), (1, 0), (%d, 0) ]' % i)
	print(io.recv())
# Result: 8 index in .2 file


# thing to notice: In option 2, line 145
# > shares = user_shares + [ stored_share ]
# if we send 5 shares, then the stored share would be ignored because we only see the first 5 elements of `shares` as seen in line 76
# > subkeys = sorted(keys[:k])

# step 3: Now we know all the indexes
# in option 2, the function `reconstitute_secret` function basically just multiplies the first row of
# inverse of submatrix (i.e. the matrix with only rows of our desired index) modulo P, so to get the 
# elements of first row we simply send 1 and rest 0

indexes = [8, 45, 47, 49, 82]
s1 = '[(8, 1), (45, 0), (47, 0), (49, 0), (82, 0)]'
s2 = '[(8, 0), (45, 1), (47, 0), (49, 0), (82, 0)]'
s3 = '[(8, 0), (45, 0), (47, 1), (49, 0), (82, 0)]'
s4 = '[(8, 0), (45, 0), (47, 0), (49, 1), (82, 0)]'
s5 = '[(8, 0), (45, 0), (47, 0), (49, 0), (82, 1)]'


io.sendline('2')
io.recvuntil('Enter the secret\'s ID: ')
io.sendline('ed3d7d')
io.recvuntil('Enter your shares of the secret: ')
io.sendline(s1)
print(io.recv())

io.sendline('2')
io.recvuntil('Enter the secret\'s ID: ')
io.sendline('ed3d7d')
io.recvuntil('Enter your shares of the secret: ')
io.sendline(s2)
print(io.recv())

io.sendline('2')
io.recvuntil('Enter the secret\'s ID: ')
io.sendline('ed3d7d')
io.recvuntil('Enter your shares of the secret: ')
io.sendline(s3)
print(io.recv())

io.sendline('2')
io.recvuntil('Enter the secret\'s ID: ')
io.sendline('ed3d7d')
io.recvuntil('Enter your shares of the secret: ')
io.sendline(s4)
print(io.recv())

io.sendline('2')
io.recvuntil('Enter the secret\'s ID: ')
io.sendline('ed3d7d')
io.recvuntil('Enter your shares of the secret: ')
io.sendline(s5)
print(io.recv())

# Result: we get the following elements of first row
b1 = b'/nW\xde\xae\xf6#3\x93:6\xcc\xe3\n\xc0\n\x918\xc9G\xf6\\\x04\x89\x84\xf4\xc1\xf7\xd3\x16\xd5\n'
b2 = b'\xd4O\xfc\xdc\n\xe4\xba9YlF_\xcf\xcc\xf8\xd73?YJ\x99\xbbR\x17m\xbe\xf55\xd3X89'
b3 = b'\x16.\xfcl\xf6\xa0a\xfb\xff\x8d\xf1kp\xc0\xef8\xe9\xa4LBDj\xf9\xe90S.f\xd3\xc9\x05\xc2'
b4 = b'\x81E\x8fw\x0f\xb2\xe9\x1e<Y\xa2{\xac\xb0d\x84\x1a\xb0\x12\x0f\xc1}\xd8X\x9a\xaa\x96\xc3%\xaaD\xb8'
b5 = b'\x99E(`\xd1*76R\xf5\xb4B\x18\xfcS\x03\xbbp\xc9\xac\xf4\n\xb2\xe4\xd8 =\x98V\x04\xcfj'

# step 4: to get the prime, check which of the following bs have the maximum value. 
# here, we have b3 (MSB in little endian is the last byte)
# so if we send '[(8, 0), (45, 0), (47, 2), (49, 0), (82, 0)]', the value will exceed the prime
# so to get prime, get value at '[(8, 0), (45, 0), (47, 2), (49, 0), (82, 0)]' and calculate
# 2*b3 - x where x is the value we get to get the prime
P = 95820804521871446624646154398560990164494336030962272285033480112778980081147

# step 5: if we send 4 secrets with value 0, except the secret stored in .1 i.e index 47
# we will get (b3 * share3) % P, from which we can easily get share3
s1 = '[(8, 0), (45, 0), (49, 0), (82, 0)]'
io.sendline('2')
io.recvuntil('Enter the secret\'s ID: ')
io.sendline('ed3d7d')
io.recvuntil('Enter your shares of the secret: ')
io.sendline(s1)
print(io.recv())

# Result: we get this secret
secret = b'\x82\x00\x92="\xc4\xe2\xc9\xd8\xd4\x03\x9fQ\xc0=Wn\x13%\xacJ\xe0h\x06\x04\xb7bn\x16]\x9d='
# adn the secret in .1 file is recovered
print((deco(secret) * modinv(deco(b3), P)) % P)
# (47, 70676385020498942306941471535414863555431695699450572706657373483340873503300)

# share[0] is unknown so -1
shares = [-1, 54823994255213496500676946730059759818553142106277896291143626823699355636565287, 70676385020498942306941471535414863555431695699450572706657373483340873503300, 50331216912153726454049654038775423514532430966505096473834160520941526236136940, 75444193790958862209466648276089504812875784556625951459151763133500407490834161]
print(len(shares))

# some sanity checks to be sure we did it alright
# should print 5
s1 = '[(8, %d), (45, %d), (47, %d), (49, %d), (82, %d)]' % (modinv(deco(b1), P), modinv(deco(b2), P), modinv(deco(b3), P), modinv(deco(b4), P), modinv(deco(b5), P))
io.sendline('2')
io.recvuntil('Enter the secret\'s ID: ')
io.sendline('ed3d7d')
io.recvuntil('Enter your shares of the secret: ')
io.sendline(s1)
print(io.recv())

# step 6: notice how the code uses `strip(b"\x00")` to remove the leading or trailing 0x00
# and option 4 checks if the result just starts with `OOO{`
# and as we are in little endian, 'OOO{' is the LSB bytes
# if we see flag as a number, it would look like 0x..........7b4f4f4f.
# so if we minus the last 4 bytes with `OOO{` (0x7b4f4f4f), the resultant flag would look like 0x..........00000000.
# now if we add 0xXX4f4f4f where `XX = (- i + ord('{'))` and `i` is the thing we would loop for, the flag will look 
# like 0x........YY4f4f4f00
# when i is the actual value of the byte before `OOO{`, our flag would be 0x........7b4f4f4f00, this ends with `OOO{`
# hence we will be reported "Congrats! You have decoded our secret. We must have trusted you!"

# now how do you subtract/add stuff to the flag value?
# first we calculate `x` which is the effective value so that
# resultant share at `[(49, 50331216912153726454049654038775423514532430966505096473834160520941526236136940), (45, 54823994255213496500676946730059759818553142106277896291143626823699355636565287), (82, 75444193790958862209466648276089504812875784556625951459151763133500407490834161)]` 
# = resultant share at '[(45, x), (49, 0), (82, 0) ]' just to keep things simple
# you can try to send '[(45, x), (49, 0), (82, 0) ]' in option 4 to check if you get "Congrats! You have decoded our secret. We must have trusted you!"

x = (deco(b2) * shares[1] + deco(b4) * shares[3] + deco(b5) * shares[4]) % P
x = (x * modinv(deco(b2), P)) % P


# now to add a number y to the resultant flag value, we add modinv(deco(b2), P) * y, i.e we send
y = 1
s1 = '[(45, %d), (49, 0), (82, 0) ]' % (x + modinv(deco(b2), P) * y)

# why do we do so? because if flag = b2 * x + constant
# b2 * (x + modinv(deco(b2), P) * y) + constant = b2 * x + constant + b2 * modinv(deco(b2), P) * y
# i.e flag + y

# finally we run our main loop
flag = b"OOO{"
def zeros(n):
	return bytes([ 0 for _ in range(n)])

while True:
	j = x + modinv(deco(b2), P) * (P - deco(flag) + deco( b"OOO" + zeros(len(flag) - 3) ))
	for i in [ ord(i) for i in ('_' + '}' + string.printable) ]:
		print(i, ",", end='')
		j = x + modinv(deco(b2), P) * (P - deco(flag) + deco( zeros(len(flag) - 3) + b"OOO" + bytes([ (-i + ord('{')) % 256 ]))  )
		io.sendline('4')
		io.recvuntil('Enter the secret\'s ID: ')
		io.sendline('ed3d7d')
		io.recvuntil('Enter your shares of the secret: ')
		io.sendline('[(45, %d), (49, 0), (82, 0) ]' % j)
		o = io.recv()
		if o.startswith(b"Congrats!"):
			flag = flag + bytes([i])
			break
	print()
	print(flag)

# final flag
flag = b"OOO{ooo_c4nt_ke3p_secr3ts!}"