Completed all the crypto challenges by 7:33:08 into the CTF and got a bunch of
first bloods / first 3 solves too. The misc ML challenges were entertaining and
the art gallery aesthetic was fun.
“a shattered padlock laying in a grassy field with a rock wall in the
background in a rustic style”
I tried to save my SSH key, but it seems that some of it has gotten removed!
If there are any data recovery experts out there, hopefully they can recover
my key…if you can, try to connect to my server to reach back to me.
The challenge provides a SSH private key file with some parts of its base64 data
censored with underscores "_". Using the file header, we can identify it as a
RSA private key encoded in the PKCS#1 format.
IPYTHONCOPY IPYTHON?
!wget "https://2022.uiuc.tf/files/6ba91c25ec2929bb9dd73ec46a815b43/key_redacted.pem?token=no-u"-O key_redacted.pem 2>/dev/null
withopen("key_redacted.pem","r")as f:
raw = f.read()print("Redacted key:")print(raw)
We should try to unpack whatever parameters we have remaining after the censor
with some careful handling of the base64 data. One consideration is that the
base64 might have had its padding = characters censored, so we will need to
manually repair this as well. We derive one version of the key key_bytes with
all censored bits set to zero. We also another version of the key key_mask
that sets all provided bits set to 1 to differentiate between data that is known
and data that is censored.
PYTHONCOPY PYTHON?
import base64
key_b64 ="".join(raw.split("\n")[1:-1])
key_bytes = base64.b64decode(
key_b64.replace("_","A")[:-2]+"==")
key_mask = base64.b64decode("".join(["/"if i !="_"else"A"for i in key_b64
])[:-2]+"==")print("Key length:",len(key_bytes))print("Key hex :", key_bytes.hex())print("Key mask :", key_mask.hex())
With some help from reference
documents,
we can make a custom parser for DER encoding. In brief, the binary format is
made of “chunks” with a header and data component:
TEXTCOPY TEXT?
1 byte - Tag / "data type"
1 byte - Short Length
2+ bytes, optional - Extended Length, use if Short Length > 127
[Length] bytes - Raw data
The tag 0x02 means the chunk data should be unpacked as an integer while the
tag 0x30 means the chunk data should be re-parsed as a “Sequence” of DER
struct chunks.
If we try to decode the key data, the output from our custom parser looks very
broken.
Some of the Short Length / Extended Length headers were censored, meaning
the parser does not know where to start and stop unpacking integers. Despite
this, we have recovered n and e of the RSA key successfully. These two
parameters are the first few in the key their lengths were not censored, so they
were correctly parsed.
Generating public/private rsa key pair.
demo_key.pem already exists.
Overwrite (y/n)? Your identification has been saved in demo_key.pem
Your public key has been saved in demo_key.pem.pub
The key fingerprint is:
SHA256:inFQrLVTy/XJR2i1WzReWqX5o5ER0UoLR3ef10CCGzw sy@SYVAPOR
The key's randomart image is:
+---[RSA 4093]----+
| .. . .oB*oB|
| .o . E.o+=XB|
| .o + o B++Bo=|
| ..o o . +o++.|
| . ..S +...|
| + . o .|
| . . . |
| |
| |
+----[SHA256]-----+
Tag: 0x30 Length: 2340
Tag: 0x2 Length: 1
Tag: 0x2 Length: 512
Tag: 0x2 Length: 3
Tag: 0x2 Length: 512
Tag: 0x2 Length: 256
Tag: 0x2 Length: 256
Tag: 0x2 Length: 256
Tag: 0x2 Length: 256
Tag: 0x2 Length: 256
[0,
9622395594545263753511[... 1200 digits ...]6755577479,
65537,
7294503226089045787905[... 1200 digits ...]2918758097,
1322935933887554560075[... 580 digits ...]594486269046053,
7273515933813267674448[... 580 digits ...]23734542192443,
1310804092389371544517[... 580 digits ...]325092090983329,
5031652225327557205188[... 580 digits ...]58325113132715,
9507348386917704126798[... 580 digits ...]15158535783249]
We can modify the DER parser to use these known working chunk tags and data lengths
and use that with the censored key. We manually set one chunk to length 511
since we know that length is valid from earlier.
However, the parser is still a bit broken. One chunk reports an invalid tag of
0x77, but all tags should either be 0x02 if the header was not censored or
0x00 if the header was censored. There also seems to be data left over at the
end after parsing the DER sequence which throws an error unless we add one dummy
chunk at the end.
PYTHONCOPY PYTHON?
fixed_tag_length =[(0x30,2340),(0x02,1),(0x02,512),(0x02,3),(0x02,511),(0x02,256),(0x02,256),(0x02,256),(0x02,256),(0x02,256),# this shouldn't be here(0xff,9999)]defder_unpack_fixed(bytes_stream):global fixed_tag_length
take_pos =0deftake(n_bytes, to_int=True):nonlocal take_pos
res = bytes_stream[take_pos:take_pos + n_bytes]
take_pos += n_bytes
if to_int:
res =int("0"+ res.hex(),16)return res,(take_pos - n_bytes, take_pos)(tag, length), fixed_tag_length = fixed_tag_length[0], fixed_tag_length[1:]
actual_tag, _ = take(1)# tag
take(1)# lengthif length >127:
take(2)# extended lengthprint("Tag:",hex(tag),"Length:", length,"Actual tag:",hex(actual_tag))
res =Noneif tag ==0x30:
res =[]
inner_data, _ = take(length, to_int=False)
inner_pos =0while inner_pos < length:
inner_res, inner_used = der_unpack_fixed(inner_data[inner_pos:])# new recursion
res.append(inner_res)
inner_pos += inner_used
elif tag ==0x02:
res, _ = take(length)return res, take_pos
unpacked_two, _ = der_unpack_fixed(key_bytes)
unpacked_two
OUTPUTCOPY OUTPUT?
Tag: 0x30 Length: 2340 Actual tag: 0x30
Tag: 0x2 Length: 1 Actual tag: 0x2
Tag: 0x2 Length: 512 Actual tag: 0x2
Tag: 0x2 Length: 3 Actual tag: 0x2
Tag: 0x2 Length: 511 Actual tag: 0x2
Tag: 0x2 Length: 256 Actual tag: 0x0
Tag: 0x2 Length: 256 Actual tag: 0x0
Tag: 0x2 Length: 256 Actual tag: 0x77
Tag: 0x2 Length: 256 Actual tag: 0x0
Tag: 0x2 Length: 256 Actual tag: 0x0
Tag: 0xff Length: 9999 Actual tag: 0x0
[0,
7473071059429749799883[... 1200 digits ...]8086142309,
65537,
1109495115862054496740[... 1200 digits ...]268622848,
0,
1980508142803874403456[... 120 digits ...]8400973919,
6082450790802802781530[... 580 digits ...]00046204928,
0,
0,
None]
After inspecting the censored key hex1, we discover that this is because one
of the parameters in censored key has a 1 byte longer field compared to the
known working key. One of the early parameters should have a length of 257
instead of 256. After making this change, we can successfully parse the censored
key.
PYTHONCOPY PYTHON?
fixed_tag_length =[(0x30,2340),(0x02,1),(0x02,512),(0x02,3),(0x02,511),# Change to 257 to align chunks(0x02,257),(0x02,256),(0x02,256),(0x02,256),(0x02,256)]
unpacked_final, _ = der_unpack_fixed(key_bytes)
unpacked_final
OUTPUTCOPY OUTPUT?
Tag: 0x30 Length: 2340 Actual tag: 0x30
Tag: 0x2 Length: 1 Actual tag: 0x2
Tag: 0x2 Length: 512 Actual tag: 0x2
Tag: 0x2 Length: 3 Actual tag: 0x2
Tag: 0x2 Length: 511 Actual tag: 0x2
Tag: 0x2 Length: 257 Actual tag: 0x0
Tag: 0x2 Length: 256 Actual tag: 0x0
Tag: 0x2 Length: 256 Actual tag: 0x2
Tag: 0x2 Length: 256 Actual tag: 0x0
Tag: 0x2 Length: 256 Actual tag: 0x0
[0,
7473071059429749799883[... 1200 digits ...]8086142309,
65537,
1109495115862054496740[... 1200 digits ...]268622848,
0,
5070100845577918472847[... 120 digits ...]190649323383,
1557107402445517512071[... 580 digits ...]90411828461568,
0,
0]
Run the parser once more with the key_mask from earlier so we obtain the
bitmask of uncensored. We can refer to some pyrcyptodome
source
to find the order that the parameters appear in a private key. The next step is
to recover the full key from this partial key leak.
Since n=p∗q we can use p=n⋅q−1mod2128⋅4 to recover
the low 128 nibbles of p. This works since p and q are prime and therefore
all variables involved are coprime to 2128⋅4.
Since we know many bits of dp_high and have a closely associated value
p_low, we can rearrange some equations d=dpmod(p−1) and e⋅d=1mod(p−1)⋅(q−1) to get an equation relating variables dplow,
phigh and k.
de⋅de⋅de⋅dpe⋅dpe⋅(dphigh⋅2129⋅4+dplow)=dpmod(p−1)=1mod(p−1)⋅(q−1)=1modp−1=1modp−1=1+k⋅(p−1)=1+k⋅(phigh∗2128⋅4+plow−1)(1)(2)Change mod of (2)Sub (1)Expand modExpand high/lowwhere0<dplow<2129⋅4,0<phigh<2384⋅4and0<k<e
Since 0<k<e, we can iterate through all possible values of k to look for
integer solutions to the other two variables dplow and
phigh. We use z3 to find possible solutions to the equation and
afterwards check manually if we find a p which divides n. After optionally
speeding up processing with multithreading, around half an hour of
CPU time is needed to get a valid p.
PYTHONCOPY PYTHON?
import multiprocessing
from z3 import*from Crypto.Util.number import isPrime
from tqdm.auto import tqdm
dp_high_offset =2**(129*4)
dp_low_limit =2**(129*4)
p_high_offset =2**(128*4)
p_high_limit =2**(384*4)defsolve_k(k):
dp_low = Int("dp_low")
p_high = Int("p_high")
s = Solver()
s.add(
e *(dp_high * dp_high_offset + dp_low)==1+ k *(p_high * p_high_offset + p_low -1))
s.add(0< dp_low, dp_low < dp_low_limit)
s.add(0< p_high, p_high < p_high_limit)
res = s.check()ifstr(res)=="unsat":returnFalse
model = s.model()
p = model[p_high].as_long()* two_pow_512 + p_low
dp = dp_high * dp_high_offset + model[dp_low].as_long()assert e * dp %(p-1)==1ifnot isPrime(p):returnFalseprint("!!!")print("k:", k)print("p:", p)return p
p =None# jobs = list(range(0, e + 1))# skip to the interesting part for the writeup
jobs =list(range(27500, e +1))with multiprocessing.Pool(4)as p:for res in tqdm(p.imap(solve_k, jobs), total=len(jobs)):if res:
p = res
break
With known p, we can recover q and the rest of the RSA key parameters.
Export the key into a valid PEM file and diff with the redacted key to see that
the original uncensored data has not changed, confirming that the key is good.
PYTHONCOPY PYTHON?
from Crypto.PublicKey import RSA
print(f"{n % p ==0=}")
q = n // p
print(f"{p * q == n =}")
phi =(p-1)*(q-1)
d =pow(e,-1, phi)
rsa_key = RSA.construct((n, e, d, p, q))
rsa_key_bytes = rsa_key.export_key("PEM")withopen("key_solved.pem","wb")as f:
f.write(rsa_key_bytes)
Congratulations! You found my key - if you take a look at it carefully, you'll find the flag - replace slashes in the key with underscores to get your flag...:
uiuctf{hidden_in_plain_sight}
Connection to bro-key-n.chal.uiuc.tf closed.
And just like the server says, the flag is actually visible inside the PEM file
if you look hard enough.
“suspicious machine learning model secretly among us”
Top scientists in Among Us have finally delivered the impossible; A method to
classify the SUS with perfect accuracy. To solve amogus once and for all, they
needed to suss out the sus at scale, and thus created a Neural Network
classifier for crewmate images that achieved 100% accuracy over the
population, which has a ‘sus’ rate of less than 5%.
However, among the us lurked a final sus, who destroyed the back half of the
fully trained model (where the classification head and some convolutional
layers were), and now the sus epidemic looms large again.
With the partial model left over from the fully trained model, figure out;
Who. Is. Sus?
Flag format is uiuctf{n1_n2_n3_...} where n# is the numbers that are sus
sorted in ascending order. Each image has a number in the filename. For
example, if 001.png, 005.png, and 010.png are sus, the flag would be
uiuctf1510
Attachment: sussy.tar.gz
18 solves, 371 points
Challenge sussy.py
PYTHONCOPY PYTHON?
import torch
import torch.nn as nn
import torchvision
import torch.nn.functional as F
import os
from PIL import Image
IMAGE_DIR ='./crewmates/'
MODEL_PATH ='./partial_sus_detector.pt'# load all images into memorydefload_images(path):
images =[]
paths =[]for filename in os.listdir(path):
paths.append(filename)
paths.sort()for filename in paths:
im = Image.open(path + filename)
images.append(im)
transforms = torchvision.transforms.ToTensor()
players =[transforms(image)for image in images]
players = torch.stack(players)return players
# A partial classifierclassPartialModel(nn.Module):def__init__(self, input_channels):super(PartialModel, self).__init__()
self.conv1 = nn.Conv2d(input_channels,32,3, padding=1)
self.conv2 = nn.Conv2d(32,32,3, padding=1)
self.conv3 = nn.Conv2d(32,32,3, padding=1)
self.conv4 = nn.Conv2d(32,64,3, padding=1)
self.pooling = nn.MaxPool2d(2,2)defforward(self, x):
x = F.relu(self.conv1(x))
x = self.pooling(x)
x = F.relu(self.conv2(x))
x = self.pooling(x)
x = F.relu(self.conv3(x))
x = F.relu(self.conv4(x))
x = self.pooling(x)return x
partial_model = PartialModel(3)
partial_model.load_state_dict(torch.load(MODEL_PATH))
partial_model.eval()
crewmates = load_images(IMAGE_DIR)
partial_outputs = partial_model(crewmates)
The challenge provides pretrained model weights, 222 images of testing data and
a sample script to run a machine learning model. However, the model abruptly
ends at a pooling layer and outputs a 64×4×4=1024 wide
embedding output per image instead of classifying “not sus” and “sus”. Given
that the “sus” label is rare with expected less than 222∗0.05≈11
images being “sus”, we can instead run some kind of outlier detection on the
output embeddings.
The first job would be to actually get the partial model outputs. You can
install pytorch on your local machine, but since the model was small I chose to
use a Google Colab IPython kernel since it would be simple to set up.
To find outliers, we need to convert each image’s 1024-dimension output
embedding to a 1-dimension “sus”-ness value; this is called dimensionality
reduction. Some
straightforward ways to do this would be using sklearn’s principal component
analysis
or
isomap
models, both of which are robust enough to lead to the flag. For this writeup,
I use the Isomap model to convert the large input to a 1-dimension value and
visualise this with a histogram plot.
PYTHONCOPY PYTHON?
from sklearn.manifold import Isomap
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt
import numpy as np
partial_outputs_np = partial_outputs.detach().numpy()
partial_outputs_np_flat = partial_outputs_np.reshape((222,64*4*4))
iso = Isomap(n_components=1)
one_dimension_embedding = iso.fit_transform(partial_outputs_np_flat)[:,0]
plt.hist(one_dimension_embedding)
The distribution has two peaks; the smaller peak to the right looks like
outliers and are likely from the “sus” images. We can filter for the images
which had a value of >0.35 and use those to generate the flag.
PYTHONCOPY PYTHON?
sus_labels = np.where(one_dimension_embedding >0.035)[0].tolist()
flag ="uiuctf{"+"_".join(str(i)for i insorted(sus_labels))+"}"print("flag:", flag)
OUTPUTCOPY OUTPUT?
flag: uiuctf{2_31_41_59_65}
We can confirm the flag is correct by submitting it to the CTF platform.
pull off the most daring heist in art history! transfer enough art out of the museum to pull off a successful attack. be careful not to deface the art too badly, or the heist loses all value!
Challenge is broken. Submitting the challenge images back would pass the machine
learning check because it would compare a number label against a text label,
bypassing the entire classification check and giving out flag for free.
However, I think I did an intended solve, so…
PATCHED Challenge app.py
PYTHONCOPY PYTHON?
#the more things change, the more they stay the same ;)#if this looks familiar, it is! welcome back, good luck, have funimport io
import os
import random
import base64
import json
from flask import Flask, jsonify, request, render_template, session
from flask_kvsession import KVSessionExtension
import numpy as np
from sqlalchemy import create_engine, MetaData
from simplekv.db.sql import SQLAlchemyStore
from datetime import timedelta
from werkzeug.utils import secure_filename
from werkzeug.exceptions import HTTPException
from PIL import Image
import imagehash
from torchvision.models import efficientnet_b0
import torchvision.transforms as transforms
import torchvision
import torch.nn as nn
import torch
# Use environment variable if it exists
FLAG = os.environ.get("FLAG","uiuctf{fake_flag}")
MIN_LEVEL =50
SESSION_MINUTES =5
MUST_REPEAT_CAPTCHA =True
HASH_DIFFERENCE =4# how different the imagehash is
app = Flask(__name__)
app.config['SECRET_KEY']= os.urandom(64)# Store local session
engine = create_engine('sqlite:////tmp/sessions.db')
metadata = MetaData(bind=engine)
store = SQLAlchemyStore(engine, metadata,'kvsession_table')
metadata.create_all()
kvsession_extension = KVSessionExtension(store, app)
app.permanent_session_lifetime = timedelta(minutes=SESSION_MINUTES)# ------------------ Model goes here ⬇------------------ #
classes =['plane','car','bird','cat','deer','dog','frog','horse','ship','truck']
device = torch.device("cuda:0"if torch.cuda.is_available()else"cpu")# model = secret_model()# !!! PATCH: I made my own model file trained on 4 epochs of the CIFAR10 train dataset# but we solve the challenge without needing to know this
model = efficientnet_b0(num_classes=len(classes))
model.load_state_dict(torch.load("../models/model.pth", map_location = device))
model = model.to(device)
model.eval()
image_set = torchvision.datasets.CIFAR10(root='./static/images', train=False, download=True)# ------------------ Model goes here ------------------ ## Get a random image and show it to the userdefgen_img():
label =0
curr_image, label = image_set[random.randint(1,len(image_set))]
resize_images = transforms.Compose([transforms.Resize(256),
transforms.CenterCrop(224)])
curr_image = resize_images(curr_image)
buffered = io.BytesIO()
curr_image.save(buffered,format='png')# return base64.b64encode(buffered.getvalue()).decode('utf-8'), label# !!! PATCH: Return a string label insteadreturn base64.b64encode(buffered.getvalue()).decode('utf-8'), classes[label]# Transform image to normalize into model's boundsdeftransform_image(image_bytes):
my_transforms = transforms.Compose([
transforms.ToTensor(),
transforms.Normalize([0.485,0.456,0.406],[0.229,0.224,0.225])])
image = Image.open(io.BytesIO(image_bytes))return my_transforms(image).unsqueeze(0)deftensor_to_image(tensor):
tensor = tensor.detach().squeeze().numpy()
tensor = tensor.transpose(1,2,0)
tensor =(tensor *255).astype(np.uint8)return Image.fromarray(tensor)defimage_to_tensor(img):
tensor = np.array(img).astype(np.float32)/255.0
tensor = tensor.transpose(2,0,1)
tensor = tensor[None,:,:,:]return torch.tensor(tensor, requires_grad=True)defbytes_to_image(img_data):import tempfile
with tempfile.NamedTemporaryFile(suffix='.png')as tmp:
tmp.write(img_data)
tmp.flush()return Image.open(tmp.name)defget_prediction(image_bytes, model, curr_image =None):
inputs = transform_image(image_bytes=image_bytes)
outputs = model(inputs)
preds = torch.argmax(outputs,1)
original = Image.open(io.BytesIO(base64.b64decode(curr_image)))
input_image = Image.open(io.BytesIO(image_bytes))
hash_orig = imagehash.average_hash(original)
hash_input = imagehash.average_hash(input_image)if hash_orig - hash_input < HASH_DIFFERENCE:return classes[preds]else:return"IMAGE WAS TOO DIFFERENT"# Function that takes care of the website's repeated image generation and edge conditions@app.route('/', methods=['GET','POST'])defindex():
response =None
img =None
regen_image = session.get('img')isNoneif session.get('level')isNone:
session['level']=0
session['yolo']=0
session.permanent =Trueif request.method =='POST'and'img'in session:file= request.files['file']
img_bytes =file.read()
image = bytes_to_image(img_bytes)(width, height)= image.size
depth =len(image.getbands())if width !=224or height !=224or depth !=3:
response =f"Invalid image shape. Expecting 224 x 224 with 3 channels, got {width} x {height} with {depth} channels"else:
pred = get_prediction(image_bytes=img_bytes, model = model, curr_image = session['img'])
regen_image =Trueif pred != session['label']and pred !='no':
response ="this {} looks like a {}. must not be from our gallery!".format(session['label'], pred)
session['level']+=1else:
response ="our art!! stop, thief!"
session['yolo']+=1if session['yolo']>3:
session['yolo']=0
session['level']=0
response ="you have to move to escape the consequences of your art crimes. try again!"if session['level']>= MIN_LEVEL:
response = FLAG
elif response isNone:
response ="you've managed to steal %d paintings. maybe one more will be enough!"% session['level']if regen_image ornot MUST_REPEAT_CAPTCHA:
img, label = gen_img()
session['img']= img
session['label']= label
else:
img = session['img']return render_template('index.html', response = response, b64png = img)@app.errorhandler(RuntimeError)deferror_handler(e):return"haha lol something broke"if __name__ =='__main__':
app.run(host='0.0.0.0', port=1337)
We have a web service that prompts players with a blurry “challenge” image and
lets us upload our own “player” images. The task is to submit 50 “player” images
that appear similar to the “challenge” image according to
imagehash.average_hash(), but gives a different prediction when passed through
a machine learning image classifier that is hidden from the player (therefore it
is a “black box”).
We can write some helper functions to interact with the server. We can test that
it works by submitting back the challenge image; it should fail the machine
learning classifier check.
defaverage_hash(image, hash_size=8, mean=numpy.mean):# docstring...if hash_size <2:raise ValueError("Hash size must be greater than or equal to 2")# reduce size and complexity, then covert to grayscale
image = image.convert("L").resize((hash_size, hash_size), Image.ANTIALIAS)# find average pixel value; 'pixels' is an array of the pixel values,# ranging from 0 (black) to 255 (white)
pixels = numpy.asarray(image)
avg = mean(pixels)# create string of bits
diff = pixels > avg
# make a hashreturn ImageHash(diff)
The hash does the following:
Convert the input image to a 8x8 grayscale image
Calculate the average brightness of all pixels
For each pixel, return 1 if brighter or 0 if darker than the average and
return this as the “hash”
The “difference” between two images is the hamming distance between each
image’s “hash” (i.e. the number of 1s/0s that are different)
To generate an image that looks very different (to us and to the machine
learning image classifier) from some original image but has the same image hash,
we can try to directly generate an image from the image hash. We can parse the
image hash as a 8x8 1-bit black/white image, then resize and convert it to the
required dimensions and color channels using nearest neighbour scaling.
This image is guaranteed to produce the same imagehash.average_hash(), but
since it looks like black and white noise the image classifier would
likely give a random prediction which is enough to pass the server’s check.
you've managed to steal 0 paintings. maybe one more will be enough!
Submitting image...
this ship looks like a truck. must not be from our gallery!
We can run this in a loop to get the flag. Progress is reset once we fail 4
checks. If the classified output is indeed random, there is a 90% chance that
the check passes, which adds up to a 20% chance of us reaching 50 “stolen
images” without getting reset.2
We are given two services running scripts that does a AES cipher negotiation
handshake with each other.
After understanding the handshake protocol, MITM the handshake between the kid
and mom services while forcing both of them to use AES-ECB (including an extra
plaintext "finish" which for some reason the mom service does not send).
This turns the kid service into a AES-ECB encryption oracle that returns
encrypt(user_input + flag) and is vulnerable to chosen plaintext attack.
Exploit code
PYTHONCOPY PYTHON?
from pwn import*import string
# Open connection to both services
conn_mom = remote("mom-can-we-have-aes.chal.uiuc.tf",1337)
conn_kid = remote("mom-can-we-have-aes.chal.uiuc.tf",1338)# pow
conn_mom.recvline()
conn_kid.recvline()# cipher
ciphers = conn_kid.recvline().strip()assert ciphers ==b"AES.MODE_CBC, AES.MODE_CTR, AES.MODE_OFB, AES.MODE_EAX, AES.MODE_ECB"
conn_mom.sendline(b"AES.MODE_ECB")# MITM# client random
client_random = conn_kid.recvline().strip()
conn_mom.sendline(client_random)# server cert
server_sig = conn_mom.recvline().strip()
conn_kid.sendline(server_sig)# selected cipher
selected_cipher = conn_mom.recvline().strip()assert selected_cipher ==b"AES.MODE_ECB"
conn_kid.sendline(selected_cipher)# server random
server_random = conn_mom.recvline().strip()
conn_kid.sendline(server_random)# premaster key
premaster = conn_kid.recvline().strip()
conn_mom.sendline(premaster)# confirm cipher
confirm_cipher = conn_kid.recvline().strip()
conn_mom.sendline(confirm_cipher)# enc("finish")
finish_signal = conn_kid.recvline().strip()
conn_mom.sendline(finish_signal)
conn_kid.sendline(b"finish")# done# conn_mom.clean(0.5), conn_kid.clean(0.5)
conn_mom.close()# now its AES-ECB with chosen plaintext attackdefquery_ecb(x):
conn_kid.sendline(x.hex().encode())
res =bytes.fromhex(conn_kid.recvline().strip().decode())return res
pad_char =b"\x00"
known = pad_char *16defchunked(x, bs=16):return[
x[i:i+16]for i inrange(0,len(x),16)]
charset = string.ascii_letters + string.digits + string.punctuation
while known[-1:]!=b"}":print(".", end="", flush=True)
probes =b"".join([(known + s.encode())[-16:]for s in string.ascii_letters + string.digits + string.punctuation
])
pos =len(known)-16
pad_amount =64-1- pos
res = query_ecb(probes + pad_char * pad_amount)
chunked_res = chunked(res)
leak = chunked_res.index(chunked_res[-3])
known += charset[leak].encode()print()print(known[16:])
OUTPUTCOPY OUTPUT?
[x] Opening connection to mom-can-we-have-aes.chal.uiuc.tf on port 1337
[x] Opening connection to mom-can-we-have-aes.chal.uiuc.tf on port 1337: Trying 35.184.164.169
[+] Opening connection to mom-can-we-have-aes.chal.uiuc.tf on port 1337: Done
[x] Opening connection to mom-can-we-have-aes.chal.uiuc.tf on port 1338
[x] Opening connection to mom-can-we-have-aes.chal.uiuc.tf on port 1338: Trying 35.184.164.169
[+] Opening connection to mom-can-we-have-aes.chal.uiuc.tf on port 1338: Done
[*] Closed connection to mom-can-we-have-aes.chal.uiuc.tf port 1337
...........................
b'uiuctf{AES_@_h0m3_b3_l1ke3}'
Server generates some random token t and gives the player 5 queries. For each
query, the player gives a large prime Ni<21024 where (Ni−1) must have
at least one large factor >2512. The servers returns some xi and
outi where outi=xiflag⊕tmodNi.
For each query, we generate some weak Ni where Ni−1 has many small prime
factors p0,p1… and a single large prime factor P. We can solve the
discrete log of outiP with base xiP in ZNi.
Taking the variables to power P constrains the values to a smooth subgroup of
order Πpi, which can be solved quickly using a Pohlig-Hellman attack.
We use sagemath discrete_log to calculate the discrete logs of each query and
then combine the results of the five queries with the Chinese Remainder Theorem.
Exploit code
SAGECOPY SAGE?
from pwn import*defprime_bits(b):return random_prime(2^b,2^(b-1))defgenerate_n(large_prime_bits, small_primes_bits, twiddle_bits):whileTrue:# Large P
P = prime_bits(large_prime_bits)# Many small p
ps =[prime_bits(i)for i in small_primes_bits]
Pps = prod([2]+ ps +[P])for _ inrange(100):# Try multiple final p to get a prime
twiddle_p = prime_bits(twiddle_bits)
try_n =(Pps * twiddle_p +1)if try_n.is_prime():return try_n, P,[2]+ ps +[twiddle_p, P]
r = remote("log.chal.uiuc.tf",1337)
r.recvuntil(b"Here's your token for the session: ")
token =int(r.recvline().strip().decode())print(f"{token=}")print()
crt_as =[]
crt_bs =[]for i inrange(5):
n, P, phi_fac = generate_n(520,[24]*10,24)
phif_str =" ".join([str(i)for i in phi_fac])
r.sendlineafter(b"Give me the prime factors of phi(N): ", phif_str.encode())
r.recvuntil(b"x = ")
x =int(r.recvline().strip().decode())
r.recvuntil(b"out = ")
out =int(r.recvline().strip().decode())# solve dlog
F = Zmod(n)
dlog = discrete_log(F(out)^ P, F(x)^ P)
sub_ord =(F(x)^ P).multiplicative_order()
crt_as.append(dlog)
crt_bs.append(sub_ord)print(f"{n=}")print(f"{x=}")print(f"{out=}")print(f"{dlog=}")print(f"{sub_ord=}")print()# recover flag
flag_xor_token = crt(crt_as, crt_bs)print(f"{flag_xor_token=}")
flag = flag_xor_token ^^ token
print(f"{flag=}")print(bytes.fromhex(hex(int(flag))[2:]))
OUTPUTCOPY OUTPUT?
[x] Opening connection to log.chal.uiuc.tf on port 1337
[x] Opening connection to log.chal.uiuc.tf on port 1337: Trying 34.173.46.25
[+] Opening connection to log.chal.uiuc.tf on port 1337: Done
token=115252043315080069211788772230314084802563899042985991925257357186927446363299309635373613108414589115358266051022252187528388847666857527405160229592646186108033797035085098953200798381099445461872492552834838652566156561617685989075600098851555872052050167773044480799160522843214337051725369058341493731639
n=69635454756751799481415582317476981430621765708074021414358874214845092138094564588686841247519856695969980422111599843270550289916617064173830320861856120197817671039070441497371288159352474016518038351800044447189223419759012813159
x=28302940667249362207703596076255021827770991980563165469733062507004668230889325321072871703941254994716136779722484966080094540108061769069849002976378828851638078671654386026709383862687349223879193789664864617754700299232177573035
out=48107037550886295321718456586517872045047310909276626755118749952460521232376518208249156658168527791626462643846120513150280059933761402734065112503337439667931875279748215099324865636675619768210833122110307522819080316766251348169
dlog=8612051295706839306831523889958944733992081503658072067380812951193173638460
sub_ord=25813918870933342269418063125043767802478258726550619630209528056341236784042
n=45828029433747157675399881769005283518516193497533845156529996240159608192193485862407313997709318053681859748245663132978468137845352937385250515311688842834490319778406740535227383425971558330501723726434281432302905813024459443
x=25646286238606298340161560239154851115147485651837340332627583669429629740496676312974156458858668232289136385430008036397146503967500902346894845051821940392784850095962580427838176068895967528609227725385125025595976772139250912
out=22529718033215420820287757229074227472667246159384175617736111924741652381524131244640543351537345606594148124291624968320882548074859904597126503017212314503339754413503352695885202418972771699966226777540493718049118776505245133
dlog=1496648107171608713805115036809364718263399320834451980923625857412828623
sub_ord=7179416748041412429954008939713230796726916019767891520748090139219511763
n=1023752912938122410991964620427236136282070106815285413887834390415216181047962716537638532301284514528522158632149248113368760709817967591029590768259254524721540829588119419877365099436989223421581704835827373092109911652295768287
x=15490026862734541013199745371862814899564204758034030996344814324820315770080613253133293656729097316907299484206720271214175488917138286641561515133516507315175869469169237174147420334020426158544481837803788053784022491686949833
out=650395057196598545700352250088991602592086591085660354600772913640749886512238503427407306749748299271734135433597158788633165878413277959610699073572163955103373640471244039174079413046416249966154306207138109695979295410130977390
dlog=204679363701310119362029977086463635363182886547493699697741322029033483122
sub_ord=331811046131816017120137974316285406800515048800797656390573370205871750278
n=62205794681819896299758744506255713424509051024295191282665723066317892084372605806891702494811419438401591823027538485994229241817023720776308040173492052972662983042575035588177986681166836147619612040027367167809051476596516619
x=14276117861308164001524425277999951844486905754775258414261803770068575377248154916721308976546421596445087254397519355085069999505335788371011657470764554227793932637416518527170011361100353841945993540838162874145411248947877872
out=45121563106322833847624946083758775393966742894641994399515539172001340591959104571008430658323373399351435710920509465892432283724037287412021526506626845303035769405573840794793747378914467417747884278777700636922431539140980921
dlog=23832521455608546729542248798936120079841565911378336871027973382331234160
sub_ord=25274565380179279578068779314602568324201090111549349508558395752353870971
n=920725946338160142404273122024039708047775811997680754212777306370505555931102385741857139522976137425655711530946337010560216162821271521706044660384774154785090308486621866900599359122243469163232463123725942871835827040272243
x=31113876882981691716417421442307101560974379575525982700886886865075024306685248605187337368290817926652444193278451130058243184271094407686054444597587822770837190171825102147148552644935303072517727213265217304904769483656479
out=517069572339441381177765471578371066995581795965045443828698658989746251833644908553893161482194811347058620378088799134557163614684017777360027413381518556863178975895651512385067754797664769213895801635403527131622792843285305
dlog=265945125210347853690884126510209242660211527277564361222015103925045386
sub_ord=352011957599792857045722514424931866478894442759028506792402521275423986
flag_xor_token=115252043315080069211788772230314084802563899042985991925257357186927446363299309635373613106073445508447780869746654561204091042819896442188622774804714584659925780244729607561956298282654292986976744165731664953095975706803338597485639769903958704751347552825835314241071286691484426565959837161880006607178
flag=2529701069150202415145759245888660935698948454718014822883116354342940915912102610953531198507000362037519603585304850716182610938231315800778127873706339271012829908434694336380279513706795940071841884610930876231805
b'uiuctf{w0w_1_th0ughT_Th4t_discr3te_L0g_w4s_h4rD_f04_s4f3_prim2s!1!_d91ea3cf4a3daaf0604520}'
We are given logs of a diffie hellman key exchange using a circle curve and an
encrypted secret.
Points on the ellipse curve have additive order p−1 which is
smooth,
therefore we can solve the discrete log with the Pohlig-Hellman attack. After
monkeypatching __mul__, __neg__, __sub__, __hash__, parent()(0) and
is_zero() of ClockPoint, we can use sagemath discrete_log with the various
points given in the handout. After solving for Alice’s secret key, complete the
key exchange and decrypt the flag.
Also see a similar challenge The True
ECC from SEETF 2022.
Exploit code
SAGECOPY SAGE?
from hashlib import md5
from Crypto.Cipher import AES
p =62471552838526783778491264313097878073079117790686615043492079411583156507853
Fp = Zmod(p)# copied from ecc.pydefscalar_mult(x, n):
y = ClockPoint(0,1)if n ==0:return y
if n ==1:return x
while n >1:if n %2==0:
x = x + x
n = n //2else:
y = x + y
x = x + x
n =(n-1)//2return x + y
classClockPoint:# copied from ecc.pydef__init__(self,x,y):
x, y = Fp(x), Fp(y)# newassertint(x*x + y*y)==1
self.x = x
self.y = y
def__str__(self):returnf"({self.x},{self.y})"def__eq__(self, other):returnstr(self)==str(other)
__repr__ = __str__
defget_hash(self):return md5(str(self).encode()).digest()def__add__(self, other):
x1,y1 = self.x, self.y
x2,y2 = other.x, other.y
return ClockPoint( x1*y2+y1*x2, y1*y2-x1*x2 )# monkeypatcheddef__mul__(self, other):return scalar_mult(self, other)def__neg__(self):return self *(p-2)def__sub__(self, other):return self +(-other)defparent(self):definner(x):assert x ==0return ClockPoint(Fp(0),Fp(1))return inner
defis_zero(self):return(self.x, self.y)==(0,1)def__hash__(self):returnhash((int(self.x),int(self.y)))
base_point = ClockPoint(34510208759284660042264570994647050969649037508662054358547659196695638877343,4603880836195915415499609181813839155074976164846557299963454168096659979337)
alice_pk = ClockPoint(929134947869102207395031929764558470992898835457519444223855594752208888786,6062966687214232450679564356947266828438789510002221469043877962705671155351)
bob_pk = ClockPoint(49232075403052702050387790782794967611571247026847692455242150234019745608330,46585435492967888378295263037933777203199027198295712697342810710712585850566)
alice_sk = discrete_log(
alice_pk, base_point, p-1,
operation="+")print(f"{alice_sk=}")
shared_key =(bob_pk * alice_sk).get_hash()print(f"{shared_key=}")
enc =b' \xe9\x1aY.+E\xac\x1b\xc41\x1c\xf7\xba}\x80\x11\xa8;%]\x93\x88\x1fu\x87\x91\x88\x87\x88\x9b\x19'
flag = AES.new(shared_key.get_hash(), AES.MODE_ECB).decrypt(enc)print(flag)
Specifically look for the 028201 hex sequence that should appear at the
start of a >128 byte long integer chunk. There is one right after the 0x77
that was wrongly parsed as the tag, so we need to start parsing the chunk
one byte later.↩
Chance of ≥50/53 trials succeeding with an individual probability of
90% is 21.053% using binomial probability.↩
