I was at BSides Canberra this year for the CTF! I was part of Sober Ostrich, who came first, although my main contributions to the team were getting people merch from gatcha challenges and also completing game challenges.
I didn’t get this challenge when I was competing because I was locked out, but after the CTF I locked in and also worked with bpaul to get this challenge done!!
challenge
Welcome to the 6-out-of-7 Oblivious Transfer service!
nc c.sk8.dog 11202
Author: Neobeo
#!/usr/bin/env python3
import os
from math import prod
from secrets import randbelow
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
FLAG = os.getenvb(b'FLAG', b'skbdg{????????????????????????????????????????????????????????????}')
assert len(FLAG) == 67
print(r'''
╭─────────────────────────────────────────────────────────────────╮
│ │
│ ___ ▄▄ _ _ _ │
│ / _ \ ▄█▀ | (_)_ _(_) ___ _ _ ___ │
│ | | | |████▄| | \ \ / / |/ _ \| | | / __| │
│ | |_| |██ ██| | |\ V /| | (_) | |_| \__ \ │
│ \___/ ▀███▀|_|_| \_/ |_|\___/ \__,_|___/ │
│ out of __ │
│ ▄█▀▀██_ __ __ _ _ __ ___ / _| ___ _ __ │
│ ▄█▀ '__/ _` | '_ \/ __| |_ / _ \ '__| │
│ ▄█▀| | | (_| | | | \__ \ _| __/ | │
│ ▄█▀ |_| \__,_|_| |_|___/_| \___|_| │
│ ▀ │
│ │
│ Welcome to the 6-out-of-7 Oblivious Transfer service! │
╰─────────────────────────────────────────────────────────────────╯
''')
# Split the flag into seven shares -- having all seven gives you the flag!
shares = [os.urandom(67) for _ in range(6)]
shares.append(bytes(a^b^c^d^e^f^z for a,b,c,d,e,f,z in zip(*shares,FLAG)))
# Discrete log prime subgroup
p = 2**1279 - 1
q = 581211581_67_345470_67_67_3490730717101265_67
g = pow(67, p//q, p)
assert g != 1 and pow(g, q, p) == 1
# Server-side secret
x = randbelow(q)
h = pow(g, x, p)
print(f'{h = }')
# 6-out-of-7 Oblivious Transfer protocol:
# To receive all shares except i, choose random a[j] and set y[j] = g^a[j] for j != i.
# Then choose y[i] so their product is h. You can decrypt six shares by using h^a[j].
ys = list(map(int, input('Enter ys: ').split(',')))
assert len(ys) == 7 and prod(ys) % p == h, "Invalid ys"
print('Here are the seven encrypted shares:')
for y, share in zip(ys, shares):
shared_secret = pow(y, x, p)
key = shared_secret.to_bytes(160)[-32:]
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(share, 16))
print(ct.hex())
the main idea
The main vulnerability in this protocol is where the user is asked to give values for y:
# 6-out-of-7 Oblivious Transfer protocol:
# To receive all shares except i, choose random a[j] and set y[j] = g^a[j] for j != i.
# Then choose y[i] so their product is h. You can decrypt six shares by using h^a[j].
ys = list(map(int, input('Enter ys: ').split(',')))
assert len(ys) == 7 and prod(ys) % p == h, "Invalid ys"
There is no check for whether the y values are in the subgroup generated by g - which means that they can be a small order! Any subgroup will have an order that divides p-1, and some small factors of this prime are:
(p-1).factor(limit=10000000000)
2 * 3^3 * 7 * 19 * 73 * 1279 * 5113 * 17467 * 66457 * 102241 * 228479 *
48544121 * 56409643 * 212885833 * 1920360089161039537725943743682642488875[...]
The information you’re given in terms of encrypted shares once you provide valid y values is pretty limited - which means I couldn’t do an attack to recover x using one smooth generator (which was my first idea).
However, you are given some information in the decryption stage:
for y, share in zip(ys, shares):
shared_secret = pow(y, x, p)
key = shared_secret.to_bytes(160)[-32:]
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(share, 16))
print(ct.hex())
If you choose a value of y with a small order, you can then iterate over every value of x up until the order of y. When you get to the value of x mod y’s order, the ciphertext will unpad correctly and be 67 bytes long. Repeat this 6 times with coprime orders for ys, and then you eventually get to something where you can find the original value of x using the Chinese Remainder Theorem :)
solution & optimizations
The original list of orders for y we had was:
ords = [factors[11], factors[10]*factors[4], factors[9]*factors[3], factors[8]*factors[5], factors[7], factors[6]*factors[2]*factors[1]*factors[0]]
ords.sort()
print(ords)
[17467, 1932714, 1942579, 16678967, 48544121, 84998503]
However when iterating over all of these it ends up being 154,114,351 AES decrypts at a maximum. When asking bpaul how they figured out these numbers, they replied:
…OK so that was not the best way to group orders
Ultimately I came up with:
factors = [2, 3**3, 7, 19, 73, 1279, 5113, 17467, 66457, 102241, 228479, 48544121, 56409643, 212885833]
sfact = factors[1:12]
sfact[0] = sfact[0] // 3 # extra 3 not needed
sfact.sort()
ords = []
l = len(sfact) - 1
s_minus_last = sfact[:-1]
for i in range(len(s_minus_last) // 2):
ords.append(s_minus_last[i] * s_minus_last[-(i+1)])
ords.append(sfact[-1])
ords.sort()
This ended up being only 60,140,944 AES decrypts, which is a lot smaller :) still very slow though
After finding these orders, you can find a generator for a subgroup of a given order using an algorithm in this paper:
def find_generator(q, p):
while True:
h = randbelow(p)
power = (p-1) // q
assert (p-1) % power == 0
if pow(h, power, p) != 1:
return pow(h, power, p)
And then you can use this to generate values of y, and a seventh value that makes it so that they all multiply to h.
ys = [find_generator(s, p) for s in ords]
ys.append((pow(product(ys), -1, p) * h) % p)
After this, it’s time for 60 million AES decrypts
enc_shares = []
for _ in range(7):
enc_shares.append(bytes.fromhex(serv.recvline()))
xs = []
for i in range(6):
y = ys[i]
ct = enc_shares[i]
for x in range(ords[i]):
shared_secret = pow(y, x, p)
key = shared_secret.to_bytes(160)[-32:]
try:
share = unpad(AES.new(key, AES.MODE_ECB).decrypt(ct), 16)
if len(share) != 67:
continue
xs.append(x)
break
except ValueError:
continue
x = crt(xs, ords)
And then use this to decrypt all shares normally :)
flag = []
for y, share in zip(ys, enc_shares):
shared_secret = pow(y, x, p)
key = shared_secret.to_bytes(160)[-32:]
pt = unpad(AES.new(key, AES.MODE_ECB).decrypt(share), 16)
flag.append(pt)
print(xor(flag[0], flag[1], flag[2], flag[3], flag[4], flag[5], flag[6]))
The full solve script can be found here - I left out some steps in regards to connecting to the server, declaring static values, imports, etc. in this writeup.
more optimizations???
When we posted our working solution to the CTF discord, we learned that it was very un-optimal - apparently the author’s solution only uses about 500k AES decrypts. I don’t think there’s any way to use our approach and reduce the number of decrypts by 120 times…
I shall maybe update this post when the author writeup is out with a link and hopefully an explanation about what we missed :)
afterword
I was talking with one of my teammates after the CTF, and he said that he didn’t think he would have been able to get as many challenges done if he didn’t have another teammate there to bounce ideas off of.
I am used to being the only one on a team that does crypto challenges (“hey berri please do crypto for us thx”) and so I am unsure if I would have been able to solve this challenge in the main competition, and it was very refreshing to have someone to work on a challenge with!
Thank you to bpaul for pointing out that a decryption oracle was possible, and also thank you skateboarding dog for the CTF and also just being awesome in general :)