2023 DiceCTF
I participated in DiceCTF 2023 this weekend.
Huge applause to our team, everyone who participated, and respect to challenge authors.
I solved the following 4 crypto challenges. Took way too much time dealing with ‘BBBB’ considering I got the hang of it at the first place already.
Provably Secure & Provably Secure 2
I solved normal ‘Provably Secure’ with the solution for ‘Probvably Secure 2’. First I didn’t even know the difference for those 2 challenges, but then later realized that normal one has no filtering at all, due to coding miss, so you can just directly decrypt the message.
I will just write solution for ‘Provably Secure 2’ at this point.
server.py
#!/usr/local/bin/python
# Normally you have unlimited encryption and decryption query requests in the IND-CCA2 game.
# For performance reasons, my definition of unlimited is 8 lol
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes
from secrets import randbits
from os import urandom
from Crypto.Util.strxor import strxor
def encrypt(pk0, pk1, msg):
r = urandom(16)
r_prime = strxor(r, msg)
ct0 = pk0.encrypt(r, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(), label=None))
ct1 = pk1.encrypt(r_prime, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(), label=None))
return ct0.hex() + ct1.hex()
def decrypt(key0, key1, ct):
ct0 = ct[:256]
ct1 = ct[256:]
r0 = key0.decrypt(ct0, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(), label=None))
r1 = key1.decrypt(ct1, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(), label=None))
return strxor(r0, r1)
if __name__ == '__main__':
print("""Actions:
0) Solve
1) Query Encryption
2) Query Decryption
""")
for experiment in range(1, 129):
print("Experiment {}/128".format(experiment))
key0 = rsa.generate_private_key(public_exponent=65537, key_size=2048)
key1 = rsa.generate_private_key(public_exponent=65537, key_size=2048)
pk0 = key0.public_key()
pk1 = key1.public_key()
print("pk0 =", pk0.public_numbers().n)
print("pk1 =", pk1.public_numbers().n)
m_bit = randbits(1)
seen_ct = set()
en_count = 0
de_count = 0
while True:
choice = int(input("Action: "))
if choice == 0:
guess = int(input("m_bit guess: "))
if (guess == m_bit):
print("Correct!")
break
else:
print("Wrong!")
exit(0)
elif choice == 1:
en_count += 1
if (en_count > 8):
print("You've run out of encryptions!")
exit(0)
m0 = bytes.fromhex(input("m0 (16 byte hexstring): ").strip())
m1 = bytes.fromhex(input("m1 (16 byte hexstring): ").strip())
if len(m0) != 16 or len(m1) != 16:
print("Must be 16 bytes!")
exit(0)
msg = m0 if m_bit == 0 else m1
ct = encrypt(pk0, pk1, msg)
seen_ct.add(ct)
print(ct)
elif choice == 2:
de_count += 1
if (de_count > 8):
print("You've run out of decryptions!")
exit(0)
in_ct = bytes.fromhex(input("ct (512 byte hexstring): ").strip())
if len(in_ct) != 512:
print("Must be 512 bytes!")
exit(0)
if in_ct.hex() in seen_ct:
print("Cannot query decryption on seen ciphertext!")
exit(0)
print(decrypt(key0, key1, in_ct).hex())
with open('flag.txt', 'r') as f:
print("Flag: " + f.read().strip())
We can assume there is nothing we can do with OAEP’s vulnerability, since it already includes sha256 hash.
But the decrypting system decrypts 2 blocks individually, and the filtering system just checks if the 2 blocks are the exact same.
So I thought, we encrypt 2 times, and decrypt with first encryption’s front block, and second encryption’s back block.
When I optimized my theory, it looked like this.
First we have to encrypt the message 3 times(I saw another solutions using just 2 though).
e1 = [enc0(r1), enc1(r1 ^ msg)]
e2 = [enc0(r2), enc1(r2 ^ msg)]
e3 = [enc0(r3), enc1(r3 ^ msg)]
Then we decrypt these three messages.
dec([enc0(r1), enc1(r2 ^ msg)]) = r1^r2^msg
dec([enc0(r2), enc1(r3 ^ msg)]) = r2^r3^msg
dec([enc0(r3), enc1(r1 ^ msg)]) = r3^r1^msg
If we xor all three of them, we can easily get the message.
Here is my final ex code.
ex.sage
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes
from secrets import randbits
from os import urandom
from Crypto.Util.strxor import strxor
from pwn import *
io = remote("mc.ax", 31497)
for _ in range(128):
print(f"step {_}")
io.recvuntil("pk0 = ")
n0 = int(io.recvline())
io.recvuntil("pk1 = ")
n1 = int(io.recvline())
enc_0 = []
enc_1 = []
for i in range(3):
io.sendlineafter("Action: ", "1")
io.sendlineafter("m0 (16 byte hexstring): ", "00" * 16)
io.sendlineafter("m1 (16 byte hexstring): ", "11" * 16)
enc = bytes.fromhex(io.recvline().decode()[:-1])
assert len(enc) == 512
enc_0.append(enc[:256])
enc_1.append(enc[256:])
msg = b"\x00" * 16
for i in range(3):
io.sendlineafter("Action: ", "2")
send = enc_0[i] + enc_1[(i + 1) % 3]
io.sendlineafter("ct (512 byte hexstring): ", bytes.hex(send))
dec = bytes.fromhex(io.recvline().decode()[:-1])
assert len(dec) == 16
msg = xor(msg, dec)
io.sendlineafter("Action: ", "0")
if msg == b"\x00" * 16:
io.sendlineafter("m_bit guess: ", "0")
else:
io.sendlineafter("m_bit guess: ", "1")
io.interactive()
Flag
PV: dice{yeah_I_lost_like_10_points_on_that_proof_lmao}
PV2: dice{my_professor_would_not_be_proud_of_me}
rSabin
challenge.py
import asyncio
import traceback
from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from nth_root import nth_root, chinese_remainder # not provided
class Server:
def __init__(self):
e = 17
nbits = 512
p = getPrime(nbits)
q = getPrime(nbits)
N = p * q
self.p = p
self.q = q
self.N = N
self.e = e
def encrypt(self, m):
assert 0 <= m < self.N
c = pow(m, self.e, self.N)
return int(c)
def decrypt(self, c):
assert 0 <= c < self.N
mp = int(nth_root(c, self.p, self.e))
mq = int(nth_root(c, self.q, self.e))
m = chinese_remainder([mp, mq], [self.p, self.q])
return int(m)
def encrypt_flag(self):
with open("flag.txt", "rb") as f:
flag = f.read()
key = RSA.construct((self.N, self.e))
cipher = PKCS1_OAEP.new(key)
c = cipher.encrypt(flag)
c = bytes_to_long(c)
return c
async def handle(a):
S = Server()
while True:
cmd = (await a.input("Enter your option (EDF) > ")).strip()
if cmd == "E":
m = int(await a.input("Enter your integer to encrypt > "))
c = S.encrypt(m)
await a.print(str(c) + '\n')
elif cmd == "D":
c = int(await a.input("Enter your integer to decrypt > "))
m = S.decrypt(c)
await a.print(str(m) + '\n')
elif cmd == "F":
c = S.encrypt_flag()
await a.print(str(c) + '\n')
return
class Handler:
def __init__(self, reader, writer):
self.reader = reader
self.writer = writer
async def print(self, data):
self.writer.write(str(data).encode())
await self.writer.drain()
async def input(self, prompt):
await self.print(prompt)
return (await self.reader.readline()).decode()
async def __aenter__(self):
return self
async def __aexit__(self, exc_t, exc_v, exc_tb):
self.writer.close()
await self.writer.wait_closed()
if exc_v is not None and not isinstance(exc_v, asyncio.TimeoutError):
traceback.print_exception(exc_v)
return True
async def main():
async def callback(*args):
async with Handler(*args) as a:
await asyncio.wait_for(handle(a), 20)
server = await asyncio.start_server(callback, '0.0.0.0', 5000)
print('listening')
async with server:
await server.serve_forever()
if __name__ == "__main__":
asyncio.run(main())
I second blooded this challenge, thanks to some luck I had.
I was unsure how does nth_root function works, and I tried decrypting 1 multiple times for no reason.
1’s 17th root should be always 1, right, but I found sometimes it is not in low probability.
I observed why it isn’t 1, and found out it is happening when p-1 or q-1 is multiple of e value which is 17.
Let’s assume p-1 is not multiple of 17, and q-1 is multiple of 17(Without Loss Of Generality).
The decryption finds 17th root depending on p, q individually. So we can say 17th root of p is calculated correctly.
After that we can see it calculates with CRT. So we can say
dec % p == 1
This means dec - 1 is multiple of p, and if we find the value of n, we can get p’s value with GCD.
Getting value of n is easy enough.
Since both p and q’s bit_length is 512, n’s bit_length should be around 1024, so when we encrypt 2^61, it should become 2^(61*17) = 2^1037.
2^1037 - enc(2^61) should be multiple of n, if we factor out the small multiple, we can get n’s value.
Then we can finally get p and q’s value.
This is the code for collecting the values. I found n with factorDB, it is not heavy factoring at all.
from pwn import *
while 1:
io = remote("mc.ax", 31370)
io.sendlineafter("Enter your option (EDF) > ", "D")
io.sendlineafter("Enter your integer to decrypt > ", str(1))
d = int(io.recvline())
print(d)
if d > 1:
break
io.close()
io.sendlineafter("Enter your option (EDF) > ", "E")
io.sendlineafter("Enter your integer to encrypt > ", str(2^61))
enc = int(io.recvline())
nmul = 2^(61 * 17) - enc
io.sendlineafter("Enter your option (EDF) > ", "F")
f = int(io.recvline())
print(nmul)
print(d)
print(f)
As like all challenges when gcd(phi(n), e) > 0, we have to check 17 possibilities.
The disturbing step is the PKCS1_OAEP actually haha.
After the CTF ended, I saw some people looked up for implementation for PKCS1_OAEP to decrypt manually.
For me, I generated another q value (which $17 \nmid q - 1$ this time), and created another private RSA key, and made another cipher.
And cipher.decrypt() does all the job LOL. Quite neat right?
Here is my final ex code.
ex.sage
from Crypto.Util.number import *
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
nmul = 1472652434159470912717652477249629435288838642660072237733135353261210431116228248553975980211706774692931634311512685185865487901002152566198037716990062525940495276211736076829793428052109414039635475636893136335117172740673736934738697615380782000387169557073669482414190802882921184771103976730603474027568571
d = 65218508357739351094678168808378222795836228873250917356076923974796498850037416350961686574551446156400306841574623055670195469503308577533679327001450403240311853731706027507515671967316704795205347956069238908679689738539924987372657739504485607577702302069253226736628602308321255282725166442485680199585
f = 57816931865503984306516063152772233676118644798781873004195645287848832866141173472948992881001736064199811245895734601275395784423478282808860723558495979180040578988171301802518739535134189606472385840733816329925894907511746442431778101397560140643668504642635172995797036111267892860084796849795540372499
n = 71756197152437309979908028906574547351207846935636711871224253435716534186825914756808262934839291267988677791332294751540490566730115117974859314768311773422038458130474885583481626860210954248386467652725875180778500840065961941954816431095881791180001440192645786795994289474390741352195291951985746432177
p = gcd(d - 1, n)
q = n // p
assert isPrime(p) and isPrime(q) and p * q == n
e = 17
# q - 1 is multiple of 17
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi // e)
X = pow(f, d, n)
k = 2
L = pow(k, phi // e, n)
ms = []
for i in range(e):
Li = pow(L, i, n)
m = X*Li % n
if pow(m, e, n) == f:
ms.append(m)
q = getPrime(512)
while (q - 1) % 17 == 0:
q = getPrime(512)
cs = []
newn = p * q
newd = pow(17, -1, (p - 1) * (q - 1))
for m in ms:
cs.append(long_to_bytes(pow(m, e, newn)))
key = RSA.construct((int(newn), int(e), int(newd)))
cipher = PKCS1_OAEP.new(key)
for c in cs:
try:
print(cipher.decrypt(c))
except:
pass
Flag
dice{rabin-williams-cryptosystem-in-disguise-3038e78caa07}
BBBB
bbbb.py
#!/usr/local/bin/python
from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from math import gcd
from os import urandom
def generate_key(rng, seed):
e = rng(seed)
while True:
for _ in range(randint(10,100)):
e = rng(e)
p = getPrime(1024)
q = getPrime(1024)
phi = (p-1)*(q-1)
if gcd(e, phi) == 1:
break
n = p*q
return (n, e)
def generate_params():
p = getPrime(1024)
b = randint(0, p-1)
return (p,b)
def main():
p,b = generate_params()
print("[+] The parameters of RNG:")
print(f"{b=}")
print(f"{p=}")
a = int(input("[+] Inject b[a]ckdoor!!: "))
rng = lambda x: (a*x + b) % p
keys = []
seeds = []
for i in range(5):
seed = int(input("[+] Please input seed: "))
seed %= p
if seed in seeds:
print("[!] Same seeds are not allowed!!")
exit()
seeds.append(seed)
n, e = generate_key(rng, seed)
if e <= 10:
print("[!] `e` is so small!!")
exit()
keys.append((n,e))
FLAG = open("flag.txt", "rb").read()
assert len(FLAG) < 50
FLAG = FLAG + urandom(4)
for n,e in keys:
r = urandom(16)
flag = bytes_to_long(FLAG + r)
c = pow(flag, e, n)
r = r.hex()
print("[+] Public Key:")
print(f"{n=}")
print(f"{e=}")
print(f"{r=}")
print("[+] Cipher Text:", c)
if __name__ == "__main__":
main()
The challenge was based on BBB on SECCON CTF 2022. https://ctftime.org/task/23982
Original challenge was to set all the e’s values to 11, and perform hastad’s attack.
On this one, we can’t perform hastad’s attack since all the plaintexts are different due to added urandom(16).
But this was not the main point of the challenge, it could be easily solved with coppersmith after generating small polynomials. (But it took long time for me because I am not too fond with coppersmith… ㅠㅅㅠ)
Anyways, the main point of this chall was to make small e values to make coppersmith work. I thought of making LCG into a loop in the first place.
Setting value a can do a huge job here.
LCG works like:
$seed → a*seed + b → a^2*seed + b*(a + 1) → a^3*seed + b*(a^2 + a + 1) → ….$ and so on.
We can see if a is root of (a + 1 = 0), we can generate a loop with 2 elements, if a is root of (a^2 + a + 1 = 0), we can generate a loop with 3.
I did with 3 because I was too much focusing on making e into exact 11.
Let’s say we found a root for (a^2 + a + 1 = 0), and the elements in loop-11 is (11, A, B).
The seeds we should send is obviously 11, A, B. Since no same seeds are allowed, the maximum 11s we can get is 3 in this case.
When the challenge gives us e, it can be any value between (11, A, B), so it is not very wise to rely on 1/27 probability.
But when A, B is an even number, gcd with phi value never can be 1, so it is always filtered leaving 11 alone.
That was how I made 3 datas with e=11.(I threw away the other large 2)
Gladly, coppersmith worked with just 3 of it.
Here is my final ex code.
ex.sage
import cypari2
from Crypto.Util.number import *
pari = cypari2.Pari()
pari.allocatemem(1024*1024*1024)
n1 = 27954...9433
r1 = bytes_to_long(bytes.fromhex('54107efb65283d816bb7986bf684f101'))
enc1 = 17168...6062
n2 = 20353...9779
r2 = bytes_to_long(bytes.fromhex('67a7ba893badda86ccca15b70ada1c81'))
enc2 = 13271...9198
n3 = 13197...3569
r3 = bytes_to_long(bytes.fromhex('f8f10bc4c2601ff2f92bf52f4b79cdba'))
enc3 = 44466...9519
crtcoef = [(n2*n3, pow(n2*n3, -1, n1)), (n1*n3, pow(n1*n3, -1, n2)), (n1*n2, pow(n1*n2, -1, n3))]
x = pari('x')
f = 0
f += crtcoef[0][0] * crtcoef[0][1] * ((x*(2**(8*16))+r1)**11 - enc1)
f += crtcoef[1][0] * crtcoef[1][1] * ((x*(2**(8*16))+r2)**11 - enc2)
f += crtcoef[2][0] * crtcoef[2][1] * ((x*(2**(8*16))+r3)**11 - enc3)
sol = pari.zncoppersmith(f, N=n1*n2*n3, X=2**((49+4)*8), B=n1*n2*n3)
print(long_to_bytes(int(sol[0])))
Flag
dice{r3s0rt_t0_LCG_4ft3r_f41l1ng_t0_m4k3_ch4ll}
[+]
Another easy solution is, as I mentioned, we can just create loop of 2 with a = -1.
When we think about it, the loop is made with these 2 elements: (seed, b - seed)
If b is an odd number with 50% probability, when we send a seed which is odd number, b - seed is always even, so it gets filtered.
With this way, if we send 5 seeds: (11, b - 11, 13, b - 13, 15)
We can get 5 datas with e = (11, 11, 13, 13, 15).
Coppersmith works for this method too. Probably even more accurate.