OT is secure
I hope you will not break it
Don’t be malicious
This challenge provides you with incomplete client code for an Oblivious Transfer (OT) protocol. In Oblivious Transfer there is a “sender” and a “receiver”, the sender won’t know what data was sent to the receiver, and the receiver will only learn the information it requested. See this Wikipedia article for more information.
The challenge server will tell you that the flag has been split into 2 shares and that you must XOR them together to get the flag. However, getting both shares in a single session is impossible if we play “honestly”.
The challenge name is “semihonest” which suggests that the OT protocol implemented has an assumption that at least one party is acting “honestly”. Well, we can just be a little less than honest and get the flag. In particular, the client code provided only calculates 1 key that it knows the secret to and another that is just random. In oblivious transfer the sender doesn’t know which share the client requested so it looks like the server would have to send back 2 valid shares in this case.
I first tried sending the same key twice, but the server checks for that. Drats, its never that easy… So we need to just call our public key and shared key generator again, and save a second key. I stopped caring about the “choice bit” because it doesn’t matter in the end if we can decrypt both shares the server sends back. So all that remains is filling in the missing client code and then computing the XOR of the 2 shares we decrypt.
def gen_key(g, p, B):
"""
Choose random a \in [1, p-2]
find A: g ^ a mod p
find KA: B ^ a mod p
output: A, KA
"""
a = get_rand(p)
A = pow(g, a, p)
KA = pow(B, a, p)
return A, KA
def otp_decrypt(key, p, ctext):
"""
output: ctext * key^-1 mod p
Hint: You will need to compute modular inverse
"""
return (ctext * get_inv_mul(key, p)) % p
# Get modular multiplicative inverse
def get_inv_mul(e, n):
gcd, x, _ = xgcd(e, n)
if gcd != 1:
raise Exception('Modular inverse does not exist')
return x % n
# Extended Euclidean Algorithm
# Ref: https://anh.cs.luc.edu/331/notes/xgcd.pdf
def xgcd(a, b):
x0, x1 = 1, 0
y0, y1 = 0, 1
while b:
q = a // b
x1, x0 = x0 - q*x1, x1
y1, y0 = y0 - q*y1, y1
a, b = b, a % b
return a, x0, y0
And for the actual “semihonest” part of the challenge this was my run_client function (comments intact to line up):
# Generate our D-H public key and shared key
pkey1, ka_key1 = gen_key(generator, modulus, server_pkey)
pkey2, ka_key2 = gen_key(generator, modulus, server_pkey)
# The server will encrypt each plaintext with our keys
keys[0] = pkey1
shared_key[0] = ka_key1
keys[1] = pkey2 #get_rand(modulus)
shared_key[1] = ka_key2
formatted_keys = ','.join(str(key) for key in keys).encode()
# Send keys to server
s.send(formatted_keys)
# Receive both ciphertexts from server encrypted with respective keys
ctexts = receive_ints(s)
# Decrypt the one ciphertext we can decrypt (as determined earlier by choice_bit)
ptext = otp_decrypt(shared_key[0], modulus, ctexts[0])
ptext2 = otp_decrypt(shared_key[1], modulus, ctexts[1])
print("Decrypted text:")
pbytes = to_bytes(ptext)
print(pbytes)
print("Decrypted text:")
pbytes2 = to_bytes(ptext2)
print(pbytes2)
print("".join([chr(x^y) for x,y in zip(pbytes, pbytes2)]))
return 0