This page has been machine-translated from the original page.
We participated in Google CTF 2023 (held from June 24) as 0nePadding and finished in 195th place.
This time we solved one problem each from Rev, Crypto, and Misc.
In the past two years we participated but failed to solve any problems and didn’t even make the scoreboard, so this felt like an opportunity to recognize some growth.
The Crypto problem was also one I couldn’t solve alone — being able to solve it by consulting with team members made me realize that 0nePadding as a team was operating more actively than last year.
I’ll review the unsolved problems later; for now, here’s a summary of just the ones we solved.
Table of Contents
ZERMATT(Rev)
Roblox made lua packing popular, since we’d like to keep hanging out with the cool kids, he’s our take on it.
A very long, obfuscated Lua script file is provided as the challenge binary.
Formatting and displaying the obfuscated script reveals about 3000 lines, with convoluted processing at the top as shown below.
Looking closely, the return value of passing two byte strings to the function v7 is used as a key for Lua’s global environment variable _G.
I used the following script to examine the results of each operation.
local v0 = string.char;
local v1 = string.byte;
local v2 = string.sub;
local v3 = bit32 or bit;
local v4 = v3.bxor;
local v5 = table.concat;
local v6 = table.insert;
local function v7(v24, v25)
local v26 = 0;
local v27;
while true do
if (v26 == 1) then
return v5(v27);
end
if (v26 == 0) then
v27 = {};
for v44 = 1, #v24 do
v6(v27, v0(
v4(v1(v2(v24, v44, v44 + 1)), v1(v2(v25, 1 + ((v44 - 1) % #v25), 1 + ((v44 - 1) % #v25) + 1))) % 256));
end
v26 = 1;
end
end
end
print(v7("\79\15\131\30\40\13\20\203", "\59\96\237\107\69\111\113\185"))
print(v7("\55\2\190\232\63\247", "\68\118\204\129\81\144\122"))
print(v7("\12\180\100\225", "\110\205\16\132\107\85\33\139"))
print(v7("\243\205\101\215\89\95", "\128\185\23\190\55\56\100"))
print(v7("\240\94\174\46","\147\54\207\92\126\115\131"))
print(v7("\109\25\35\60\115\10", "\30\109\81\85\29\109"))
print(v7("\239\234\115", "\156\159\17\52\214\86\190"))
print(v7("\175\186\253\180\178\169", "\220\206\143\221"))
print(v7("\213\149\104\47", "\178\230\29\77\119\184\172"))
print(v7("\235\225\172\3\21\112", "\152\149\222\106\123\23"))
print(v7("\167\216\54", "\213\189\70\150\35"))
print(v7("\28\78\87\120\13", "\104\47\53\20"))
print(v7("\12\172\66\130\29\168", "\111\195\44\225\124\220"))
print(v7("\191\217\68\12\118", "\203\184\38\96\19\203"))
print(v7("\199\55\96\124\83\218", "\174\89\19\25\33"))
print(v7("\6\46\6\90", "\107\79\114\50\46\151\231"))
print(v7("\204\61\163\173\57", "\160\89\198\213\73\234\89\215"))
print(v7("\194\77\101\178\251\203\94", "\165\40\17\212\158"))
print(v7("\53\224\205\5\54\50\228\205\9\49\42\224", "\70\133\185\104\83"))
print(v7("\217\7\68\72\38", "\169\100\37\36\74"))
print(v7("\67\5\139\167\83\20", "\48\96\231\194"))
print(v7("\150\198\74\15\46\18", "\227\168\58\110\77\121\184\207"))
print(v7("\177\122\62\179\69", "\197\27\92\223\32\209\187\17"))
print(v7("\238\13\79\194\248\8", "\155\99\63\163"))
print(v7("\144\141\223\180\128\187\129\144", "\228\226\177\193\237\217"))Running this decodes strings like the following.
It becomes clear that these strings are being passed as arguments to store functions in variables.
Based on these results, restoring the obfuscated script produces the following.
local v8 = _G["tonumber"];
local v9 = _G["string"]["byte"];
local v10 = _G["string"]["char"];
local v11 = _G["string"]["sub"];
local v12 = _G["string"]["gsub"];
local v13 = _G["string"]["rep"];
local v14 = _G["table"]["concat"];
local v15 = _G["table"]["insert"];
local v16 = _G["math"]["ldexp"];
local v17 = _G["getfenv"] or function() return _ENV; end;
local v18 = _G["setmetatable"];
local v19 = _G["pcall"];
local v20 = _G["select"];
local v21 = _G["unpack"] or _G["table"]["unpack"];
local v22 = _G["tonumber"];Here, it appears the Lua global table is being used to store function references in variables.
In my environment using Lua 5.2, the global table had the following definitions.
for n in pairs(_G) do print(n) end
>
pairs
loadstring
package
tostring
load
rawlen
_G
setmetatable
assert
require
error
os
unpack
getmetatable
string
dofile
tonumber
_VERSION
rawequal
collectgarbage
bit32
coroutine
debug
table
io
pcall
type
math
xpcall
next
arg
module
rawget
loadfile
print
ipairs
select
rawsetReference: Programming in Lua : 14
Replacing the variables assigned with functions based on these results makes the code somewhat more readable.
And as we continue analyzing the challenge binary, we can see that a significant amount of unnecessary processing has been added to bulk up the code.
For example, code like the following.
if (v89 == 0) then
local v130 = 0;
while true do
if (v130 == 1) then
v89 = 1; break;
end
if (0 == v130) then
v90 = nil;
if not v87 then
local v166 = 0; local v167;
while true do if (v166 == 0) then
v167 = 0;
while true do if (v167 == 0) then
v87 = v37();
if (v87 == 0) then return ""; end
break;
end
end
break;
end
end
end
v130 = 1;
end
end
endLooking closely, the loop ultimately just defines v87 = v37(); and then exits.
Since this type of structure appears many times throughout the script, removing these operations progressively deobfuscates the code.
After removing enough unnecessary code and tracing the program’s behavior with a debugger, we find code that obtains the correct flag character by character, as shown below.
This gave us the flag.
The animation shown on a correct answer was very stylish.
LEAST COMMON GENOMINATOR?(Crypto)
Someone used this program to send me an encrypted message but I can’t read it! It uses something called an LCG, do you know what it is? I dumped the first six consecutive values generated from it but what do I do with it?!
I’ll write this up since it’s rare for me to solve a Crypto problem.
I read the following script provided as the challenge binary.
It appears the flag is encrypted using a key generated from primes produced by an LCG (Linear Congruential Generator).
from secret import config
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrime
class LCG:
lcg_m = config.m
lcg_c = config.c
lcg_n = config.n
def __init__(self, lcg_s):
self.state = lcg_s
def next(self):
self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n
return self.state
if __name__ == '__main__':
assert 4096 % config.it == 0
assert config.it == 8
assert 4096 % config.bits == 0
assert config.bits == 512
# Find prime value of specified bits a specified amount of times
seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
lcg = LCG(seed)
primes_arr = []
dump = True
items = 0
dump_file = open("dump.txt", "w")
primes_n = 1
while True:
for i in range(config.it):
while True:
prime_candidate = lcg.next()
if dump:
dump_file.write(str(prime_candidate) + '\n')
items += 1
if items == 6:
dump = False
dump_file.close()
if not isPrime(prime_candidate):
continue
elif prime_candidate.bit_length() != config.bits:
continue
else:
primes_n *= prime_candidate
primes_arr.append(prime_candidate)
break
# Check bit length
if primes_n.bit_length() > 4096:
print("bit length", primes_n.bit_length())
primes_arr.clear()
primes_n = 1
continue
else:
break
# Create public key 'n'
n = 1
for j in primes_arr:
n *= j
print("[+] Public Key: ", n)
print("[+] size: ", n.bit_length(), "bits")
# Calculate totient 'Phi(n)'
phi = 1
for k in primes_arr:
phi *= (k - 1)
# Calculate private key 'd'
d = pow(config.e, -1, phi)
# Generate Flag
assert config.flag.startswith(b"CTF{")
assert config.flag.endswith(b"}")
enc_flag = bytes_to_long(config.flag)
assert enc_flag < n
# Encrypt Flag
_enc = pow(enc_flag, config.e, n)
with open ("flag.txt", "wb") as flag_file:
flag_file.write(_enc.to_bytes(n.bit_length(), "little"))
# Export RSA Key
rsa = RSA.construct((n, config.e))
with open ("public.pem", "w") as pub_file:
pub_file.write(rsa.exportKey().decode())LCG (Linear Congruential Generator) produces a sequence of pseudorandom numbers using the recurrence Xn+1 = (m*Xn + c) mod n.
The initial seed value was hardcoded in the challenge script, but the three values m, c, and n are not given.
However, the first 6 generated values are provided as dump.txt.
Since it seemed possible to determine m, c, and n from these values and identify the prime sequence used for key generation, I researched this with my teammates and found the following article.
Reference: Predicting Pseudorandom Numbers Generated by the Linear Congruential Generator - s4tt01237’s diary
It appears that the LCG parameters can be determined from a few initial output values by finding the modulus from the GCD of certain derived values, then solving simultaneous equations based on the modulus.
Using this approach, I was able to determine all three values m, c, and n with the following script.
from Crypto.Util.number import inverse, GCD
from functools import reduce
prime_candidates = [2166771675595184069339107365908377157701164485820981409993925279512199123418374034275465590004848135946671454084220731645099286746251308323653144363063385,
6729272950467625456298454678219613090467254824679318993052294587570153424935267364971827277137521929202783621553421958533761123653824135472378133765236115,
2230396903302352921484704122705539403201050490164649102182798059926343096511158288867301614648471516723052092761312105117735046752506523136197227936190287,
4578847787736143756850823407168519112175260092601476810539830792656568747136604250146858111418705054138266193348169239751046779010474924367072989895377792,
7578332979479086546637469036948482551151240099803812235949997147892871097982293017256475189504447955147399405791875395450814297264039908361472603256921612,
2550420443270381003007873520763042837493244197616666667768397146110589301602119884836605418664463550865399026934848289084292975494312467018767881691302197]
def solve_unknown_increment(states, A, M):
B = (states[1] - A * states[0]) % M
return B
def solve_unknown_multiplier(states, M):
A = (states[2] - states[1]) * inverse((states[1] - states[0]), M)
return A
def solve_unknown_modulus(states):
diffs = [X_1 - X_0 for X_0, X_1 in zip(states, states[1:])]
multiples_of_M = [T_2 * T_0 - T_1 ** 2 for T_0, T_1, T_2, in zip(diffs, diffs[1:], diffs[2:])]
# GCD(GCD(multiples_of_M[0],multiples_of_M[1]), multiples_of_M[2])
M = reduce(GCD, multiples_of_M)
return M
def test_unknown_modulus():
M = solve_unknown_modulus(prime_candidates)
M = solve_unknown_modulus(prime_candidates)
A = solve_unknown_multiplier(prime_candidates, M)
B = solve_unknown_increment(prime_candidates, A, M)
print(M)
print(A)
print(B)
test_unknown_modulus()Now I just need to determine e to generate the private key for flag decryption.
For e, since the RSA public key provided was 2048-bit RSA size, I guessed 65537.
Using the information determined so far, I created the following script and was able to decrypt the flag.
import struct
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes, bytes_to_long, isPrime
class LCG:
lcg_m = -6569199283741144524805092313800498379912765081239722709390321881123001934591054674566684669798886054155292305172680411106681470919005032801138448184653164447435662736622686458913807769346396147888409387744295360132038094168945987371927904880766531430748616858146076625544135687000281908879673294160897281532
lcg_c = 3910539794193409979886870049869456815685040868312878537393070815966881265118275755165613835833103526090552456472867019296386475520134783987251699999776365
lcg_n = 8311271273016946265169120092240227882013893131681882078655426814178920681968884651437107918874328518499850252591810409558783335118823692585959490215446923
def __init__(self, lcg_s):
self.state = lcg_s
def next(self):
self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n
return self.state
if __name__ == '__main__':
it = 8
bits = 512
# Find prime value of specified bits a specified amount of times
seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
lcg = LCG(seed)
primes_arr = []
items = 0
primes_n = 1
while True:
for i in range(it):
while True:
prime_candidate = lcg.next()
if not isPrime(prime_candidate):
continue
elif prime_candidate.bit_length() != bits:
continue
else:
primes_n *= prime_candidate
primes_arr.append(prime_candidate)
break
# Check bit length
if primes_n.bit_length() > 4096:
# print("bit length", primes_n.bit_length())
primes_arr.clear()
primes_n = 1
continue
else:
break
# print(primes_arr)
# print(len(primes_arr))
# Create public key 'n'
n = 1
for j in primes_arr:
n *= j
# Calculate totient 'Phi(n)'
phi = 1
for k in primes_arr:
phi *= (k - 1)
# print("[+] n: ", n)
# print("[+] size: ", n.bit_length(), "bits")
# print("[+] phi: ", phi)
rsa = RSA.construct((n, 65537))
key = rsa.exportKey().decode()
# print(key)
d = pow(65537, -1, phi)
# print("[+] d: ", d)
with open("flag.txt", "rb") as f:
data = f.read()
c = int.from_bytes(data, "little")
# print(c)
# print(c)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)
# enc_flag = b'L\x13\x17\xea\x9e\x10\x13hy\x90kK\xdb? \xd5z7\t\xeb\xf3n\xf1\xd0\xc1\xad\x15\xf8ZN\x9c\xd9\xef\xbcz\xcc\xed\xd9:p\xf0\x1e\x97%T\xdb\xb0\'I\x17\x83mLi6\x1b\xd8 \x93%\xe9\xcd\x0f*\x9e\x1fJ\xb3\xb4\xeahnT\x92\xea<<\x159\xba\xb9vo\xf3\x9b\x8b\xf3\xe93?p\xad`\xd6\xa6T\x85m\x06\xd6\xb1\xd1\x8djQ\xe4\xf3Z\xf5\x10\xd7)G\x91\x13\x1c\xc6O\x0b8;\xed\x89\'\xf42\x92\x03\xa4\x80)y\x10\xdc\x0b;\x03\xf6\xff\x06C~;\xde\xf4\xf9\xd0\xd1\xcc\xfd\x10\x95\x9a\xa9\\\x91X{\xb6M\xe1d\xf4\xf57\xbd\x8a,\x07K\xd7B\x1c\xe5\xd1p=5\x01\x08\xb3\xafA\x00\xad\x90I\x1b\tdt\x9c\x08\xf2\xd2n\xd8%\x1e\xa4H\xb7G\xb5\xc1\tG$h\xa2\xe7z\xcf\xf9\xba\x17}\'&\x05\x1ecF\xc0\x86\xc7\xd9\xd1\r2!\xe1\xa1Z\xabp\xfe\x14C\xd0.+T\x87\x9dP\x17\xfc\xb6\x94\x98\x90q\xe3P\x1fPn\x07\xf1+;\xcc\xd3/\x0f\xde\x0eZL\xa7\xd5\xce\x1dF\x9c#\xdea\xcc,\xbe\xc0O\xb06\xbdi \xf9w\xa1\xac\x97\xfd\x93\x91c\xf5\xee\xd2U\xe32\xd7\xe8\xed\x90\xa4.Q\xca\xdc\x8btF<\xbb\xfe?\xdf\xf4\xfd\xde\xee^\xf3G\x8a\xb8<\xa0\x04U\xfb1>a:\xaf\xfb+\xf3\x10\x15\x9d\x04Md\x9c^\xda\xd3A\x14\x9eV\x05\xfd\xdcC\xa1\xf8\xb4\xf8\\\xb9\x89Bb?\x13\xf1s3\x98i\xb4e\x15\xa6@\xab\xbbR\x80\x1e\xd9\xb4\xd8U\xd6qC\xff\xff\xa7bFN\t\x0f\xa7|\xa1\x80r\xb6\xa5\xa8!\xbc\xe1\x08\xc2t\xe0\xa1\xc2"4%v\x91\xeeKg\x98E\x0e\xa4z\xb5\x01o\x9d\tS\x92\xf3\x1d\x1e\xa3\xe7\xce\xb99s`\x9ao"\xe2Z\xddg\x902\x12\x15\xd6N<\xebH2;\x93\x81`\xa39\x07\xc6\xc0%Wc\xf6\x82\x819\xe0\x99=\xc5\x9a\x95\x9bR\xf4>|@\xe6)\xf1L\x17\n\n\xa4\xac#d\xd9\x13\'\x16\xf9v\x02'
# print(len(enc_flag))
# text = b"myflag"
# enc_flag = bytes_to_long(text)
# _enc = pow(enc_flag, 65537, n)
# with open ("myflag.txt", "wb") as flag_file:
# flag_file.write(_enc.to_bytes(n.bit_length(), "little"))
# with open("myflag.txt", "rb") as f:
# data = f.read()
# number = int.from_bytes(data, "little")
# print(number)
# m = pow(number, d, n)
# flag = long_to_bytes(m)
# print(flag)PAPAPAPA(Misc)
Is this image really just white?
A completely white JPEG like the one below is provided as the challenge binary.
Apparently a flag is hidden somewhere in this image.
As expected, analyzing with common tools does not yield the flag.
Scanning the bytecode also revealed nothing suspicious.
Since images like this often use LSB steganography, I extracted RGB values for all pixels with the following script, but no pixels other than #FFFFFF were found.
from PIL import Image
def get_pixel_rgb(image_path):
img = Image.open(image_path)
pixels = img.load()
width, height = img.size
rgb_values = []
for y in range(height):
for x in range(width):
r, g, b = pixels[x, y]
rgb_values.append((r, g, b))
return rgb_values
image_path = "white.jpg"
rgb_values = get_pixel_rgb(image_path)
for rgb in rgb_values:
for px in rgb:
if px != 255:
print(rgb)I was a bit stuck here, but trying ImageMagick revealed that despite the image size being 512×512, the sampling-factor was 3x1,3x1,3x1.
It appears this image uses chroma subsampling.
./magick identify -verbose white.jpg
>
jpeg:colorspace: 2
jpeg:sampling-factor: 3x1,3x1,3x1JPEG is a compression format that divides an image into small square units and mathematically encodes the color and brightness of each square.
These squares are defined as 8×8 pixels, meaning JPEG dimensions should always be multiples of 8.
JPEG may use a technique called chroma subsampling to reduce image resolution and file size.
Chroma subsampling exploits the fact that human vision is more sensitive to luminance than color.
Specifically, by intentionally reducing color information relative to luminance information, images can be made smaller (lower resolution) while maintaining their visual appearance (image quality).
Chroma subsampling is typically at a 2×2 ratio, but this image was set to 3×1.
When JPEG uses chroma subsampling, the block size becomes the basic 8×8 multiplied by the maximum sampling factor among the image components.
So in this case, the block size is 24×8.
Reference: JPEG - Simple English Wikipedia, the free encyclopedia
Reference: Chroma subsampling - Wikipedia
Reference: Structure of Image Data
Reference: Chroma subsampling in JPG compression
Reference: About JPEG’s YCbCr - awm-Tech
Here I notice that the width of the 512×512 challenge image is not a multiple of 24.
When a chroma-subsampled image’s dimensions are not multiples of the block size, the overflow is treated as padding, and the image size recorded in the SOF segment (which stores the JPEG file type and key parameters) is forced to subtract the padding.
This causes the padding area to disappear from the displayed image.
Incidentally, images hidden in the padding area cannot be recovered simply by enlarging the image in a standard image viewer.
In such cases, we directly overwrite the byte sequence specifying the JPEG image size within the SOF segment.
def modify_sof0_segment(jpeg_path, new_width, new_height):
with open(jpeg_path, "rb") as file:
jpeg_data = bytearray(file.read())
# Search for SOF0 segment position
sof0_marker = b'\xff\xc0'
sof0_start = jpeg_data.find(sof0_marker)
# Find and display SOF0 segment parameter positions
parameter_start = sof0_start + 5
print("Original SOF0 width : {}".format(int.from_bytes(jpeg_data[parameter_start:parameter_start + 2],"big")))
print("Original SOF0 height : {}".format(int.from_bytes(jpeg_data[parameter_start + 2:parameter_start + 4],"big")))
# Convert new width and height to bytes
new_width_bytes = new_width.to_bytes(2, byteorder='big')
new_height_bytes = new_height.to_bytes(2, byteorder='big')
# Replace width and height
jpeg_data[parameter_start:parameter_start + 2] = new_width_bytes
jpeg_data[parameter_start + 2:parameter_start + 4] = new_height_bytes
print("New SOF0 width : {}".format(int.from_bytes(jpeg_data[parameter_start:parameter_start + 2],"big")))
print("New SOF0 height : {}".format(int.from_bytes(jpeg_data[parameter_start + 2:parameter_start + 4],"big")))
# Save the modified JPEG file
modified_jpeg_path = "modified.jpg"
with open(modified_jpeg_path, "wb") as file:
file.write(jpeg_data)
print("==> Saved new JPEG")
# Example usage
jpeg_path = "white.jpg"
new_width = 512
new_height = 528
modify_sof0_segment(jpeg_path, new_width, new_height)Ultimately, creating the solver above and changing the image width to 528 allowed me to retrieve the flag hidden in the padding area.
Summary
It was a great opportunity to feel a sense of growth.
However, the top ranks are still far off, so I’ll keep training.
Since Google CTF’s official writeups are thorough and helpful, I’ll challenge the unsolved problems again.
Reference: google/google-ctf: Google CTF