DiceCTF 2021 Writeups
DiceCTF 2021 Writeups
Garbled
challenge implements a small garbled circuit using three AND gates and ciphertext of flag encrypted using a key derived from the four inputs to the circuit which will make the end result(output) 1 is given. player has to find that inputs using the circuit garbled tables given along with challenge source.
circuit = {
"inputs" : [1, 2, 3, 4],
"outputs" : [7],
"gates" : [
{"id" : 5, "type" : "AND", "in" : [1, 2]},
{"id" : 6, "type" : "AND", "in" : [3, 4]},
{"id" : 7, "type" : "AND", "in" : [5, 6]}
]
}
I would suggest you to look at the wikipedia page regarding the garbled circuits for better understanding [link] as I will only explain concepts required to understand the solution.
key operation in garbled circuit is garbling. during garbling each wire or line in the boolean circuit is assigned with two random values called labels.each label corresponds to the two possible values of that line (0 or 1). using the notation from wikipedia, consider a simple AND gate, there are 3 wires (2 inputs and 1 output).
| Truth Table | Labeled Truth Table | ||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
Xa0, Xb0,… are the so called labels.
Using the Labeled Truth Table(this is just my naming), Garbled Table is calculated. Garbled table consists of ciphertexts as entries.this ciphertexts are the encrypted value of the output label using the input labels as keys.the order of the rows is shuffled.
| Garbled Table |
|---|
| \(Enc_{Xa0, Xb0}(Xc0)\) |
| \(Enc_{Xa0, Xb1}(Xc0)\) |
| \(Enc_{Xa1, Xb0}(Xc0)\) |
| \(Enc_{Xa1, Xb1}(Xc1)\) |
we were given the garbled tables for the three gates used in the challenge circuit and an extra value(ciphertext of plaintext 0 encrypted using the corresponding keys) is given for each entry in the garbled table.
g_tables = {5: [(5737111, 2983937),
(15406556, 16284948),
(14172222, 14132908),
(4000971, 16383744)],
6: [(8204186, 1546264),
(229766, 3208405),
(9550202, 13483954),
(13257058, 5195482)],
7: [(1658768, 11512735),
(1023507, 9621913),
(7805976, 1206540),
(2769364, 9224729)]}
reformulating the information, let \(key_{a0}, key_{a1}, key_{b0}, key_{b1}\) be the labels corresponding to the input lines of a gate. each entry in the g_table of a gate are ciphertexts encrypted using the four combinations of the above keys. i.e \((key_{a0}, key_{b0}), (key_{a0}, key_{b1}), (key_{a1}, key_{b0}), (key_{a1}, key_{b1})\) not necessarily in the same order. we also have a plaintext-ciphertext pair(encrypted value of 0) for each of the four key pairs.
The part of the encryption algorithm used in the challenge is
def encrypt(data, key1, key2):
encrypted = encrypt_data(data, key1)
encrypted = encrypt_data(encrypted, key2)
return encrypted
def decrypt(data, key1, key2):
decrypted = decrypt_data(data, key2)
decrypted = decrypt_data(decrypted, key1)
return decrypted
notice that given data(output label) is encrypted using keys separately i.e \(ct = Enc(Enc(m, key1), key2)\) instead of combining the two keys into one key and then encrypting. This kind of encryption instances are vulnerable to meet-in-the-middle attack.
To understand the attack, assume that key1 and key2 are each of size k bits. Given a plaintext-ciphertext pair, we could compute the ciphertexts of known plaintext using all possible values of key1 and build a lookup table using them.
After building the lookup table, we can bruteforce the value of key2 by decrypting the ciphertext of the known plaintext-ciphertext pair and checking if the resulting intermediate value is in the lookup table.
using this approach, number of operations are reduced from \(2^{2k}\) to \(2^{k+1}\).
In our challenge, every label is of size 24 bits or less. we have a known plaintext-ciphertext pair and using above approach, number of operations would be \(2^{25}\) only if we want to bruteforce key1 and key2.
The problem with this is that there can be many(approx \(2^{24}\)) possible key pairs for a given plaintext-ciphertext pair. The reason is that the size of key space is \(2^{24}*2^{24} = 2^{48}\) where as the message-ciphertext space is just \(2^{24}\).
In order to reduce the possible key pairs, we have to use the other information and structure of the g_table to find correct key pairs.
Let \(Cli, Czi\) be the ciphertexts in the ith(i = 0, 1, 2, 3) row of g_table and \(Enc(pt, keyj)\ and\ Dec(ct, keyj)\) be the sub encryption and decryption routines used in the challenge. \((key_{a0}, key_{b0}), (key_{a0}, key_{b1}), (key_{a1}, key_{b0}), (key_{a1}, key_{b1})\) are the key pairs.
One of the efficient ways would be
- build a dictionary(D0) consisting of \(Enc(0, keyj)\) as dict-keys and corresponding \(keyj\) as value.
- Similarly, build dictionaries(D1, D2, D3) for each \(Czi\), i = 1, 2, 3 consisting of \(Dec(Czi, keyj)\) as dict-keys and corresponding \(keyj\) as values.
- for each possible \(kj\) of \(key_{b0}\)
- if \(kj == key_{b0}\) then \(Dec(Cz0, kj)\) should be in D0 and \(key_{a0} \in D1[Dec(Cz0, kj)]\)
- \(key_{b0}\) is used as \(key2\) for another entry. therefore one of \(Dec(Czi, kj), i = 1, 2, 3\) should be in D0 and \(key_{a1} \in D1[Dec(Czi, kj)]\)
- \(key2\) for the remaining two entries is the same value \(key_{b1}\) and \(key1\) is \(key_{a0}\) and \(key_{a1}\) for each.so, \(Enc(0, key_{a0}), Enc(0, key_{a1})\) should be in the corresponding dictionaries built in step 2 and \(key_{b2}\) can be recovered.
- there will be very few possible keys which could statisfy above three conditions. to further constrain the values, decrypt all \(Cli\)(output labels) using keys and verify that there are only two distinct values and are with frequency 3 and 1 as AND gate have (3 0’s and 1 1’s).
my ugly but working code implementing above solution
from block_cipher import encrypt_data, decrypt_data, encrypt, decrypt
from public_data import g_tables
from collections import Counter
import itertools
import ast
import hashlib
import json
key1_lookup = {}
for key1 in range(2**24):
encrypted = encrypt_data(0, key1)
if encrypted in key1_lookup:
key1_lookup[encrypted].append(key1)
else:
key1_lookup[encrypted] = [key1]
print("key1 lookup table created")
def gen_key2_lookup(cts):
lookups = (dict(), dict(), dict())
for key2 in range(2**24):
for ind, ct in enumerate(cts):
encrypted = decrypt_data(ct, key2)
d = lookups[ind]
if encrypted in d:
d[encrypted].append(key2)
else:
d[encrypted] = [key2]
return lookups
def verify_keys(g_tables, keya_0, keya_1, keyb_0, keyb_1, order):
iters = itertools.product(keya_0, keya_1, keyb_0, keyb_1)
new_keys = []
for key00, key01, key10, key11 in iters:
t = []
t.append((key00, key10))
t.append((key00, key11))
t.append((key01, key10))
t.append((key01, key11))
res = []
vals = []
for ind, j in enumerate(order):
res.append(decrypt(g_tables[j][0], t[ind][0], t[ind][1]))
vals.append(decrypt(g_tables[j][1], t[ind][0], t[ind][1]))
if list(set(vals)) != [0]:
print("Messed Up(Again!), are you drunk?!!!", vals)
if 3 not in Counter(res).values():
continue
new_keys.append((key00, key01, key10, key11))
return new_keys
inputs = []
# for gate in (5, 6):
gate = int(input("gate: "))
gi_tables = g_tables[gate]
validations = [i for _, i in gi_tables]
key2_lookups = gen_key2_lookup(validations[1:])
print("key2 lookups created")
keys = []
for key2_0 in range(2**24):
if key2_0 % 2**16 == 0:
print("key2_0 = {}".format(hex(key2_0)[2:]))
print("nvals = {}".format(len(keys)))
validation = validations[0]
encrypted = decrypt_data(validation, key2_0)
if encrypted not in key1_lookup:
continue
poss_key1_0 = key1_lookup[encrypted]
c1 = encrypted
for ind in range(1, 4):
validation = validations[ind]
encrypted = decrypt_data(validation, key2_0)
if encrypted in key1_lookup:
c2 = encrypted
poss_key1_1 = key1_lookup[encrypted]
rem_ind = [i for i in range(1, 4) if i != ind]
if c1 in key2_lookups[rem_ind[0] - 1] \
and c2 in key2_lookups[rem_ind[1] - 1]:
i1 = rem_ind[0]
i2 = rem_ind[1]
elif c2 in key2_lookups[rem_ind[0] - 1] \
and c1 in key2_lookups[rem_ind[1] - 1]:
i2 = rem_ind[0]
i1 = rem_ind[1]
else:
continue
poss_key2_1_1 = key2_lookups[i1 - 1][c1]
poss_key2_1_2 = key2_lookups[i2 - 1][c2]
poss_key2_1 = set(poss_key2_1_1).intersection(set(poss_key2_1_2))
if len(poss_key2_1) > 0:
poss_key2_1 = list(poss_key2_1)
order = [0, i1, ind, i2]
new_keys = verify_keys(gi_tables, poss_key1_0, poss_key1_1, [key2_0], poss_key2_1, order)
print("len(new_keys) =", len(new_keys))
print(new_keys)
keys.extend(new_keys)
break
assert len(keys) == 1
inputs.append(keys[0][:2])
inputs.append(keys[0][2:])
print("gate {} inputs = {}".format(gate, inputs))
"""
gate 5 inputs = [(11693387, 12215201), (188483, 11338704)]
gate 6 inputs = [(7371799, 9872293), (5588127, 2815776)]
"""
import hashlib
import itertools
def xor(A, B):
return bytes(a ^ b for a, b in zip(A, B))
inputs = [(11693387, 12215201), (188483, 11338704), (7371799, 9872293), (5588127, 2815776)]
for i, j, k, l in itertools.product(*inputs):
msg = "{}:{}:{}:{}".format(i, j, k, l)
msg = msg.encode('ascii')
m = hashlib.sha512()
m.update(msg)
m.digest()
xor_flag = b'\x90),u\x1b\x1dE:\xa8q\x91}&\xc7\x90\xbb\xce]\xf5\x17\x89\xd7\xfa\x07\x86\x83\xfa\x9b^\xcb\xd77\x00W\xca\xceXD7'
flag = xor(m.digest(), xor_flag)
if flag.startswith(b'dice'):
print(flag.decode())
"""
dice{N0w_YoUr3_Th1nkIn6_Wi7H_pR0t0c015}
"""
Benaloh
from Crypto.Random.random import randrange
from Crypto.Util.number import getPrime, GCD
r = 17
def keygen():
while True:
p = getPrime(1024)
a, b = divmod(p-1, r)
if b == 0 and GCD(r, a) == 1:
break
while True:
q = getPrime(1024)
if GCD(r, q-1) == 1:
break
n = p*q
phi = (p-1)*(q-1)//r
y = 1
while True:
y = randrange(n)
x = pow(y, phi, n)
if x != 1:
break
log = {pow(x, i, n): i for i in range(r)}
return (n, y), (n, phi, log)
def encrypt(data, pk):
n, y = pk
u = randrange(n)
a = randrange(n)
c = randrange(n)
for m in data.hex():
yield pow(y, int(m, 16), n) * pow(u, r, n) % n
u = (a*u + c) % n
def decrypt(data, sk):
n, phi, log = sk
return bytes.fromhex(''.join(f'{log[pow(z, phi, n)]:x}' for z in data))
if __name__ == '__main__':
from local import flag
pk, sk = keygen()
print(pk)
for z in encrypt(flag, pk):
print(z)
challenge implements the Benaloh Cryptosystem[link] with r = 17. nonces used in the encryption are generated using a Linear congruential generator(LCG). Modulus(n) used in the encryption is used for the LCG also.flag ciphertext(encrypted with Benaloh cryptosystem) is given.None of the parameters of LCG other than modulus are given.
refer to wikipedia page about Benaloh Cryptosystem to understand how and why decryption works.coming to the encryption, a random number \(y\) is generated with a certain property necessary to succesfully decrypt.
The entire message is encoded such that each part of the encoded string can be mapped to a number less than \(r = 17\).
In this challenge, flag is hex-encoded and each hex digit(\(mi\)) is encrypted using benaloh cryptosystem
where \(u\) is the random nonce.
we are given \(y, n\) and 34 ciphertexts where random nonce for \(i\)th ciphertext is \(i\)th term of LCG.
Let \(X_{i}\) be ith term of LCG, \(X_{0}\) is the seed and \(X_{i+1} = a* X_{i} + c\ mod\ n\).
using the flag format “dice{“, we can calculate \((X_{i})^{r} = ct_{i} * (y^{-1})^{mi}\) for \(i \in [0, 9]\)
As the flag is hex-encoded, \(mi \in [0, 16)\). so, we can derive 16 possible values for \((X_{i})^r\).
Now, I want to explain how I approached(might be boring) the challenge at this stage. Eliminating the unsolvable
- can we factor the modulus using known \((X_{i})^{r}\)? nah, never. with respect to \(n\), \((X_{i})^{r}\) are just random powers cause even though \(X_{i}\) are related that relation doesn’t depend on the factors of \(n\).
- can we find \((X_{k})^{r}\) using \((X_{i})^{r}, i < k\)? no. considering the smallest case given \((X_{0})^r\),finding \((X_{1})^r = (a* X_{0} + c)^r\), this is analogous to finding \((a* m + c)^e\) given \(m^e\) in RSA which shouldn’t be possible. given \(f1(x)^r, f2(x)^r, ...\), we can compute \(h(x)^r\) if we can write \(h(x)\) as a product of \(fi(x)\) or their inverses.
possible ways
- can we find \(X_{0}, a, c\) given \((X_{i})^{r}, 0 <= i < k\)? may be. given just \((X_{0})^r\), it shouldn’t be possible cause it’s same as RSA decryption.given \((X_{0})^r, (X_{1})^r\), if we know \(a\) and \(c\) then it could be solved using franklin-reiter-related-message-attack. so, using more relations(\((X_{i})^r\)) it might be possible to solve.
- can we decide correctly given a value \(z\) and \((X_{i})^r \ 0 < i < k\) whether \(z == (X_{i+1})^r\)? it should be.why? cause this was the only remaining idea :).
Note that I haven’t been completely honest while explaining my approach. I don’t follow a specific approach while solving a challenge, I just brainstrom by myself and checkout the ideas. most of them turn out to be absurd.
tbh, I didn’t thought of finding \(X_{0}, a, c\) at first, I tried to find a way to check whether given \(z\) is equal to \((X_{i+1})^r\) as I know resultant of two polynomials is zero if both the polynomials have a common root. It took me some time to realise that we could use gcd along with resultants to calculate the root itself.
coming back to the challenge. given any two successive terms of an LCG, we can construct polynomials as follows
\(f1(x = X_{i}) == 0,\ f2(x = X_{i}, y = c/a, w = a) == 0\)
if \(ti = Res_{x}(f1, f2)\) then \(ti(y = c/a, w = a) == 0\). where \(Res_{x}(f1, f2)\) is the Resultant of polynomials \(f1,\ f2\).
using other known \(X_{i}^r\), we could calculate other \(ti\) with root \((c/a, a)\). with the help of Resultant, polynomial gcd we could eliminate one more variable and find the root of a single variable, using same approach we could find all the roots \(X_{0}, a, c\).
But, the problem is that after the calculation of \(Res_{x}(f1, f2)\) resulting polynomial in \(y, w\) has total degree greater than 500 making it hard to calculate the subsequent resultants.
As I have mentioned above, we don’t need to find the values of \(X_{0}, a, b\).
if we can tell whether given \(z\) is equal to \((X_{i+1})^r\) then we can decrypt the message as we only have 16 possible values for \((X_{i+1})^r\) each corresponding to the message.
It is reasonable to assume that checking whether a system of polynomials have a common root should be faster then finding the root itself.
we can check if a system of polynomials have a common root using groebner basis and that is the solution for the challenge.
construct 2 or 3 polynomials as above such that they all have common root \((y = c/a, w = a)\) and calculate \(ti\) using each possible value for \(X_{i+1}\) and check whether the system of polynomials along with \(ti\) is consistent or not.
import ast
import sys
def get_resultant(f1, f2, rr, varia=None):
q1 = f1.change_ring(rr)
q2 = f2.change_ring(rr)
if varia:
r1 = q1.resultant(q2, varia)
else:
r1 = q1.resultant(q2)
return r1
def conv_bivar(f, yr, wr):
monomials = f.monomials()
nf = yr - yr
x, y, w = f.parent().gens()
for mono in monomials:
xd, yd, wd = mono.degrees()
if xd != 0:
print("xd is not zero but", xd)
if mono == 1:
coeff = int(f.constant_coefficient())
else:
coeff = int(f.coefficient({x: xd, y: yd, w: wd}))
nf += int(coeff)*(yr**yd)*(wr**wd)
return nf
def are_inconsistent(pols):
gt = ideal(*pols).groebner_basis()
if len(gt) == 1 and gt[0] == 1:
return True
return False
def possible_zi(ct, yinv):
d = {}
for i in range(16):
d[i] = power_mod(yinv, i, n)*ct % n
return d
def to_file(t, name):
with open(name, "w") as f:
f.write(str(t))
def from_file(name):
with open(name) as f:
return eval(f.read())
with open("out.txt", "r") as f:
d = ast.literal_eval(f.read().strip().replace("\n", ","))
pk, cts = d[0], d[1:]
n, yp = pk
p_id = None
if len(sys.argv) == 2:
p_id = int(sys.argv[1])
r = 17
yinv = inverse_mod(yp, n)
even_positions = [6, 7, 4, 5, 3]
odd_positions = list(range(16))
known_flag = b"dice{".hex() + "67723a6f626e6572215f21" + "}"
ind = len(known_flag) - 1
PRxy.<x, y, w> = PolynomialRing(Zmod(n))
PRx.<wn> = PolynomialRing(Zmod(n))
PRyw.<yr, wr> = PolynomialRing(Zmod(n))
PRZZ.<xz, yz, wz> = PolynomialRing(Zmod(n))
PRQQ.<yq, wq> = PolynomialRing(Zmod(n))
# zi = [power_mod(yinv, int(i, 16), n)*cts[j] for j, i in enumerate(b"dice{".hex())]
# z0, z1, z2, z3, z4, z5 = zi[:6]
# f1 = x^r - z0
# f2 = w^r*(x + y)^r - z1
# g1 = x^r - z2
# g2 = w^r*(x + y)^r - z3
# h1 = x^r - z4
# h2 = w^r*(x + y)^r - z5
# r1 = get_resultant(f1, f2, PRZZ)
# t1 = conv_bivar(r1, yr, wr)
# r2 = get_resultant(g1, g2, PRZZ)
# t2 = conv_bivar(r2, yr, wr)
# r3 = get_resultant(h1, h2, PRZZ)
# t3 = conv_bivar(r3, yr, wr)
t1 = from_file("t1")
t2 = from_file("t2")
t3 = from_file("t3")
zj = power_mod(yinv, int(known_flag[-1], 16), n)*cts[ind] % n
for i in range(1):
ind = ind + 1
print("ind =", ind)
zis = possible_zi(cts[ind], yinv)
if ind % 2 == 0:
positions = even_positions
if p_id is not None:
if p_id != 3:
positions = [even_positions[p_id]]
else:
positions = even_positions[p_id:]
else:
positions = odd_positions
if p_id is not None:
positions = odd_positions[p_id*4: p_id*4 + 4]
tmp = {}
for val in positions:
tmp[val] = zis[val]
zis = tmp
for char in zis:
print("\ntrying char =", hex(char))
zi = zis[char]
f1 = x^r - zj
f2 = w^r*(x + y)^r - zi
print("computing resultant")
ri = get_resultant(f1, f2, PRZZ)
print("resultant calculated")
ti = conv_bivar(ri, yr, wr)
if not are_inconsistent((t1, t2, ti)):
print("not inconsistent")
known_flag += hex(char)[2:]
print("-"*25)
print("known_flag =", known_flag)
print("-"*25)
zj = zi
print('\a\a\a\a\a\a')
break
"""
flag :: dice{gr:obner!_!}
references:
resultant calculation -> http://mslc.ctf.su/wp/confidence-ctf-2015-rsa1-crypto-400/
"""
This implementation is quite slow and it is not the complete script.