Sup?!
Hey, there! After a bit gap, I’m back with UMD CTF. I played this CTF along with Invaders0x1 team. I only remember few Crypto challenges that I solved because all others were basic stuff.
Crypto
BulbEuler
The challenge provided a sage file and an output file.
# This is the code that was given in bulb.sage
FLAG = open('flag.txt', 'r').read()
flag_bytes = [ord(c) for c in FLAG]
flag_bits = ''.join([f{num:08b} for num in flag_bytes])
p = random_prime(2^256)
G = GF(p, modulus="primitive")
g = G.gen()
m = p-1
print(f'p: {p}')
for bit in flag_bits:
x = G.random_element()
if bit == '1':
y = m-x
else:
y = G.random_element()
print(f'{g^x}, g^y)')
The output file had the p value. It is:
p = 6596997572802685744626960256235787019476434707654191935397530271983648431547
So, I used sage to get the value of 'g'. It was:
g = 2
As the g is prime, we can use Fermat's Little theorem here.
If p is prime, for every integer a:
pow(a, p) = a mod p
and, if p is prime and a is an integer coprime with p:
pow(a, p-1) = 1 mod p
If the bit is 1:
=> y = m - x
=> y + x = m
=> y + x = p - 1
=> g^(y + x) = g^(p - 1)
=> g^y * g^x = g^(p - 1)
=> g^y * g^x = 1 mod p
So, I used this to write the solution.
arr = [# Given g^x, g^y output here]
p = 6596997572802685744626960256235787019476434707654191935397530271983648431547
m = p - 1
flag_bits = ''
for i in range(0, len(arr), 2):
# print(arr[i], arr[i+1])
if (1 == ((arr[i])*(arr[i+1]))% p)):
flag_bits += '1'
else:
flag_bits += '0'
if len(flag_bits) == 8:
print(chr(int(flag_bits, 2)), end = '')
flag_bits = ''
UMDCTF{I_d0nt_th1nk_bulby_!s_th3_n3xt_3ul3r_tbh}
Reduce Thyself
This challenge is similar to the challenge No Padding in picoCTF. This challenge is a netcat based challenge provided with the python file.
import socket
import random
import threading
from _thread import *
from Crypto.Util.number import long_to_bytes as l2b, bytes_to_long as b2l, getPrime, isPrime, inverse
from math import gcd
from binascii import hexlify, unhexlify
HOST = '0.0.0.0' # Standard loopback interface address (localhost)
PORT = 60003 # Port to listen on (non-privileged ports are > 1023)
FLAG = open('flag.txt', 'r').read().strip().encode()
def decrypt(flag_ct, ct, d, n):
pt = 'null'
if isPrime(ct) and ct != flag_ct:
pt = hexlify(l2b(pow(ct, d, n))).decode()
return pt
def gen_params():
while True:
p, q = getPrime(1024), getPrime(1024)
n = p * q
e = 0x10001
phi = (p - 1) * (q - 1)
if gcd(phi, e) == 1:
d = inverse(e, phi)
break
return n,e,d
def threading(conn):
n, e, d = gen_params()
flag_ct = pow(b2l(FLAG), e, n)
print(f"n: {n}\ne: {e}\nd: {d}")
conn.sendall(f"n: {hex(n)}\ne: {hex(e)}\nflag_ct: {hex(flag_ct)}\n\n".encode())
while True:
conn.sendall(b'Gimme ct (hex): ')
try:
ct = int(conn.recv(1024).strip().decode(), 16)
except Exception as e:
conn.sendall(b'invalid ct')
break
pt = decrypt(flag_ct, ct, d, n)
conn.sendall(f'result: {pt}\n\n'.encode())
conn.close()
if __name__ == "__main__":
with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
s.bind((HOST, PORT))
s.listen()
while True:
conn, addr = s.accept()
print(f'new connection: {addr}')
start_new_thread(threading, (conn, ))
s.close()
So, basically it provides N, e and c and gives us a chance to decipher something. But the flag directly cannot be deciphered. This is plain RSA so it the following flaw.
m1^e * m2^e ≡ (m1m2)^e (mod n)
So, m1^e is the ciphered flag and the code above checks for the m2 cipher isPrime() function, so we have to find a prime that satisfies these conditions. Here is the code:
At last we get the cipher that has to be sent.i.e., (m1m2)^e. Then the service decrypts this for us. So we finally end up with m1m2. m1 is the flag, so we simply do m1m2/m2 to get the flag.
from pwn import *
from Crypto.Util.number import long_to_bytes as l2b, bytes_to_long as b2l, getPrime, isPrime, inverse
n = 0x7c60c7769c411fe882a246eae7a0303d45e80f3559e850479e0db7960048b4bb4432163d20a445eaa16bcecb05757915e1efa8965d8bf0e65bdc01fe7ea136e79eeea009a28089d5de0f2046f76c1b5cac0b3013897ba2800db88510a42990a35abe23b57879c4b7c179a1e3001fb204a0c17f764f7257cb96e7825bc472489af4a355c0881815f3b63d53bec1f794ea0603bdf7df8a52a808da2f877e85c71c1c991081d32ce9ac4ab509825d2bdeacd252960da9a981ed0d940b3c5a872cc41face6c34823b45946f9667b8f38d22951fe17350c8049d5ea72a6bf1548127d210ac2330fcb6ed862ab82302fcc4335d19257588910a8beebba5879c8c63d29
e = 0x10001
c = 0x6e1c336f218028b7fc0c7604cb8efbe0a1f2ec2d51efd4b230de4750974deb6d8ed385c27790cb3159c70282ce7f14fd93051929a935d4789078a37ee39168a92605a53d290f8496e142bb95ccb3d82c9ae3300ea6b6b5cf15856529fadeef102ddd09a360e356756a8e7e6f26d1e8a3b811c5c7215307aeadcc3d9959382675e8c2562fafb914e86a5a35a75ec7fe3a1b704a3c7322df7ae8659e816027eddc66a46cd58821bda266e55b22b4b3a118dc90593aaba137fe2bd976a20277d4fb608fec9cfa974d139fab3b16bba5694974c6e160eead05188415188b0f3ca376bef98d060e987ce76b232ffe1fa47350e1a9066b812ef258e05bf7a70a8d6f5a
t = 0
tosend = 0
for i in range(3000):
a = (c*(pow(i,e,n)))%n
if isPrime(a):
t = i
tosend = hex(a)
break
print(t)
print(tosend)
# This is generated output from the service
final = 0x03aafc896d25afdaea1c0f3ee6a719b7d42d357d4c7b60d42009de58007af1610251de366b0222e14afcada4a833d1e38f8acea3c5e39a9ac5fa
final = final//t
print(l2b(final).decode())
UMDCTF{s3lf_r3duc!bility_1s_n0t_ju5t_f0r_DH_97912837923}
Noisy Bits
This challenge had the description saying 'Go lay down', which refers to Golay code. It helped me solve the challenge.
This challenge provided a python code and an output file.
import random
POLY = 0xC75
FLAG_BIN_LENGTH = 360
def encode(cw):
cw = (cw & 0xfff)
c = cw
for i in range(1, 12+1):
if cw & 1 != 0:
cw = cw ^ POLY
cw = cw >> 1
return (cw << 12) | c
flag = open('crypto/Noisy Bits/flag.txt', 'rb').read()
binary_str = bin(int(from_bytes(flag, 'big')))[2:].zfill(FLAG_BIN_LENGTH)
blocks = [ ''.join([binary_str[12*i+j] for j in range(12)]) for i in range(FLAG_BIN_LENGTH // 12)])
print(blocks)
block_nos = [ int(s, 2) for s in blocks ]
print(block_nos)
encoded = [ encode(cw) for cw in block_nos ]
print(encoded)
# flip some bits for fun
for i in range(len(encoded)):
encoded[i] = encoded[i] ^ (1 << random.randint(0,22))
encoded[i] = encoded[i] ^ (1 << random.randint(0,22))
encoded[i] = encoded[i] ^ (1 << random.randint(0,22))
encoded_bin = [ bin(e)[2:].zfill(23) for e in encoded ]
print(' '.join(encoded_bin))
As each bit was flipped three times, I have used hamming distance <= 3 to get the flag. Below is the code:
POLY = 0xC75
codewords = [# Output file]
def golay(cw):
cw = (cw & 0xfff)
c = cw
for i in range(1, 12+1):
if cw & 1 != 0:
cw = cw ^ POLY
cw = cw >> 1
return (cw << 12) | c
def hamming_dist(x, y):
s1 = bin(x)[2:].zfill(23)
s2 = bin(y)[2:].zfill(23)
return sum(c1 != c2 for c1, c2 in zip(s1, s2))
valid_words = {}
for i in range(0, 2**12):
valid_words[golay(i)] = i
flag_binary = ''
for cw in codewords:
for k in valid_words.keys():
if hamming_dist(cw, k) <= 3:
flag_binary += bin(valid_words[k])[2:].zfill(12)
flag = ''
for bit in flag_binary:
if len(flag) == 8:
print(chr(int(flag, 2)), end = '')
flag = ''
flag += bit
UMDCTF{n0i5y_ch4nn3l5_ar3_n0t_@_pr0bleM_4_u}