Cryptoverse CTF 2023 WriteUps
發表於
This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .
This time, I solved a few problems in the nyahello team, mainly including some relatively difficult problems in crypto.
Crypto
LFSR Explorer
from Crypto.Util.number import *
from secret import flag
assert flag.startswith("cvctf{")
assert flag.endswith("}")
flag = flag[6:-1].encode()
assert len(flag) == 8
def explore(state, mask):
curr = (state << 1) & 0xffffffff
i = state & mask & 0xffffffff
last = 0
while i != 0:
last ^= (i & 1)
i >>= 1
curr ^= last
return (curr, last)
states = [bytes_to_long(flag[4:]), bytes_to_long(flag[:4])]
mask = 0b10000100010010001000100000010101
output = []
for i in range(8):
tmp = 0
for j in range(8):
(states[i // 4], out) = explore(states[i // 4], mask)
tmp = (tmp << 1) ^ out
output.append(tmp)
with open("output.txt", "wb") as f:
f.write(bytes(output))There are two LFSRs, just reverse them directly.
with open("output.txt", "rb") as f:
ct = f.read()
def rev(state, mask):
curr = state >> 1
b = state & 1
state >>= 1
while mask:
if mask & 1:
b ^= state & 1
state >>= 1
mask >>= 1
return curr | (b << 31)
mask = 0b10000100010010001000100000010101
s0 = int.from_bytes(ct[:4], "big")
s1 = int.from_bytes(ct[4:], "big")
for _ in range(32):
s0 = rev(s0, mask)
s1 = rev(s1, mask)
print(s1.to_bytes(4, "big") + s0.to_bytes(4, "big"))
# cvctf{G@@d_j0b}Knapsack vs. Backpack
from Crypto.Util.number import *
from math import gcd
from secret import flag
import random
NBITS = 32
print("=== Knapsack vs. Backpack ===")
class Knapsack:
def __init__(self, nbits):
W, P = [], []
for _ in range(nbits):
W.append(random.randint(1, 10))
P.append(random.randint(1, 100))
self.W, self.P = W, P
def fill(self, nbits):
r = getRandomNBitInteger(nbits)
pt = [int(i) for i in bin(r)[2:].zfill(nbits)]
self.A = sum([x * y for x, y in zip(pt, self.W)])
self.B = sum([x * y for x, y in zip(pt, self.P)])
try:
for _ in range(10):
challenge1 = Knapsack(NBITS*4)
challenge1.fill(NBITS*4)
print(challenge1.W)
print(challenge1.P)
print(f"Knapsack Capacity: {challenge1.A}")
inp = list(map(int, input("Items: ").strip().split()))
for i in inp:
if i < 0 or i >= len(challenge1.W):
print("Nope.")
exit(1)
if len(inp) != len(set(inp)):
print("Nope.")
exit(1)
weight = sum([challenge1.W[i] for i in inp])
profit = sum([challenge1.P[i] for i in inp])
if weight <= challenge1.A and profit >= challenge1.B:
print("Correct!")
else:
print("Nope.")
exit(1)
except:
exit(1)
print(flag[:len(flag)//2])
class Backpack:
def __init__(self, nbits):
r = [42]
for _ in range(nbits - 1):
r.append(random.randint(2*r[-1], 4*r[-1]))
B = random.randint(3*r[-1] + 1, 4*r[-1])
A = random.randint(2*r[-1] + 1, B - 1)
while gcd(A, B) != 1:
A = random.randint(2*r[-1] + 1, B - 1)
self.M = [A * _ % B for _ in r]
def fill(self, inp):
return sum([x * y for x, y in zip(inp, self.M)])
try:
for _ in range(10):
challenge2 = Backpack(NBITS)
r = getRandomNBitInteger(NBITS)
pt = [int(i) for i in bin(r)[2:].zfill(NBITS)]
ct = challenge2.fill(pt)
print(challenge2.M)
print(f"In your Knapsack: {ct}")
inp = int(input("Secret: ").strip())
if inp == r:
print("Correct!")
else:
print("Nope.")
exit(1)
except:
exit(1)
print(flag[len(flag)//2:])The first half is a 0/1 knapsack, let copilot write it directly. The second half is a Merkle-Hellman knapsack, directly use LLL to solve the subset sum for the answer.
from sage.all import *
from pwn import process, remote
import ast
def solve_01_knapsack(W, P, A):
# thanks copilot!
# W: weight of items
# P: profit of items
# A: capacity of knapsack
n = len(W)
# dp[i][j]: maximum profit of items 0..i with capacity j
dp = [[0 for _ in range(A + 1)] for _ in range(n)]
for i in range(n):
for j in range(A + 1):
if j >= W[i]:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + P[i])
else:
dp[i][j] = dp[i - 1][j]
# reconstruct solution
i, j = n - 1, A
items = []
while i >= 0 and j >= 0:
if i == 0:
if dp[i][j] == P[i]:
items.append(i)
break
if dp[i][j] != dp[i - 1][j]:
items.append(i)
j -= W[i]
i -= 1
return items
def solve_ssp(w, t):
L = block_matrix([[matrix(w).T, ZZ(1), ZZ(0)], [matrix([-t]), ZZ(0), ZZ(1)]])
for row in L.LLL():
if row[-1] != 0:
if row[-1] < 0:
row = -row
if all([0 <= x and x <= 1 for x in row[1:-1]]):
if vector(row[1:-1]) * vector(w) == t:
return row[1:-1]
# io = process(["python", "challenge.py"])
io = remote("67.205.179.135", 7272)
io.recvline()
for _ in range(10):
W = ast.literal_eval(io.recvlineS().strip())
P = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"Knapsack Capacity: ")
A = int(io.recvlineS().strip())
items = solve_01_knapsack(W, P, A)
io.sendline(" ".join(map(str, items)).encode())
io.recvline()
flag1 = io.recvlineS().strip()
for _ in range(10):
W = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"In your Knapsack: ")
t = int(io.recvlineS().strip())
sol = solve_ssp(W, t)
secret = int("".join(map(str, sol)), 2)
io.sendline(str(secret).encode())
io.recvline()
flag2 = io.recvlineS().strip()
print(flag1 + flag2)
# cvctf{knap5ack_0/1_15_for_the_noob5_BUT_backp@ck_M3rkl3_h3llm4n_15_for_the_pro5}Fractional Flag
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from secret import flag
assert len(flag) == 99
assert flag.startswith(b"cvctf{") and flag.endswith(b"}")
class MyRSA:
def __init__(self, n = 2, nbits = 512):
self.p = getPrime(nbits)
self.q = getPrime(nbits)
self.N = self.p * self.q
self.d = getPrime(nbits//2 - 1)
self.my_phi = self.gen_phi(n)
self.e = inverse(self.d, self.my_phi)
def gen_phi(self, n):
return sum([self.p**i for i in range(n)]) * sum([self.q**i for i in range(n)])
def encrypt(self, m):
print("I am not going to encrypt anything...")
return m
def get_public(self):
print(f"N = {self.N}")
print(f"e = {self.e}\n")
def get_private(self):
# print(f"d = {self.d}")
return self.d
NPARTS = 3
fractions = [bytes_to_long(flag[len(flag)//NPARTS*i:len(flag)//NPARTS*(i+1)]) for i in range(NPARTS)]
print("[+] Here are my public keys:")
ns = [2, 3, 6]
rsas = [MyRSA(n) for n in ns]
private_exponents = [rsa.get_private() for rsa in rsas]
for rsa in rsas:
rsa.get_public()
print("[+] Here are my flag fractions:")
for i in range(NPARTS):
f = sum(fractions[j] * private_exponents[i]**(NPARTS-1-j) for j in range(NPARTS))
print(f"[!] Fraction {i+1}: {f}")There are three types of RSA public keys, for , there is , where .
For , .
For , .
So we can get the approximate relationship .
Using , we get , where , because is not large, we can use a method similar to the Wiener attack to solve for .
So using to approximate , we can solve for , and after interpolation, the answer will come out.
from sage.all import *
from Crypto.Util.number import isPrime, long_to_bytes
pubs = [
(
2,
97612005002255328088089410975523983681740354800179039894937915732930244664586629120094932234362725524185511994009850035922533559839893979074939037832668549750255468381192887812469917667115839541015495242839376266431038121426628287675447989631207259597586333251571969522037989427555616133183042678577218636039,
76116130167787561359953887266200869082448529331107937460219287530308978477708991999616543343406382355689250048669403437942401267295685636067522489421767819007148067769751457394505797110602169754511939818788483430730012575308299189299157812591392734160576417069436538119185074252625496946207312639052459476691,
),
(
3,
82898492840033848499679066573599199466262845944574446435099699953454086638324386416129279494828609729766998439132172194894188387716844097335523066318666261933348513791114624155336437054163128912934864480178839237943154511986161169068625070999701692457965233641625122455113801192492673037347038351956273261209,
4209437149177720414392052396995336370571472638739290885909782621676928212352728218779571626530884770305850882606520062302514835362331092897621059096111410844919671863579044484955054277159466422627065939698416080746679841734383574957303171143150437215717944527004524163060734647488552780385109395365103554265493136383680197786179491825415327877829363932241445886199163804911851983235568877189260370900147226881457732043676609664875472514523869518158935427849891304397052900751093562294098001282747462255107311383605819243052786444806092296448159814920695343700003324553167747140120222023780385726663202175975632841101,
),
(
6,
74994178474501705271671940639744064973727732038326591115828216310018498822567967944888584927591599150655580137956560356301728244890598527629795727836492659456865084635190916504902969902122979161893704294891200235692036639700141954229504462610034653592940594511895628524050995435988759181763969824436031245313,
1489343297993123282242703585767862889532966168614466114229659752495521741344828171911376172581419167249138037648594483979411817592040147160238477726426615905245322859547191851844862266610905034585090032979459885344332508376146458008432418485138745167332564668471655885462387844870978937353124271354756749987557641173034038037138552554286596191926276854019397533360181392329678995160770713221738607291949604788483647158238145885370267789175042383720834228546234687195524802723091258548142868749009819341250311783811669486498714774091479332840123020791916467567722826634424992913028930995948675696110790085249624326162007313472329046629836566951986389110657545671708876118803228632059850860536273457909861781873059134865932188230401277356396602494704882757454481213539839098539947582560234411030973307998825870210215033177749651750411682404527804606701340350999128273688467096980925538961234964285918052638858734125375270072587641505250814286217419987349217586276836222849825473745401814287955844160842207855608228330415022147681694596413651097936005515497301045029721788331269208281455180641244748905469345705931987679143863830321305138722585532495234826613572876602582994268211475793765951624522296606385747914811802020368502982841323574845193182348705392733364068634167943152196883988138300398486795444947317920558342244022638552596544997423504070874736567161433560622253197613565603458736833008516912312579020461040855359316882678726669756450813443842584222951463074601799430267187315529031340358497011459213690622999701314023178557960651,
),
]
ds = []
for n, N, e in pubs:
cf = continued_fraction(ZZ(e) / ZZ(N ** (n - 1)))
for c in cf.convergents():
d = c.denominator()
if d.bit_length() == 255 and isPrime(d):
print(d)
ds.append(d)
break
fs = [
12885959655953139374785717692048211268233398655222955130228721746869891559409080848367142483157517829612928194235174347299097615553919212787225377729454255371358309685093996459461793296183459238094074717707949401000365552082820354011,
23144924364202496361036242964551729244108242071387074122924446048219898057065538815277890013860024253422666710259842325295228086904295846675276536535237894072110755426259617054492417613772645109337095876879440959135444974146373938103,
10216090816848970230135050433869173852319169856151418349231810820430643701522230150158652915588855848669985626642166987135416343716291162149831827545892183798838168834007800941773301995075510960084628367588300016798178754792796044603,
]
ms = map(int, QQ['x'].lagrange_polynomial(zip(ds, fs)))
print(b"".join([long_to_bytes(m) for m in ms][::-1]))
# cvctf{th15_fam1Ly_0f_RSA-like_crypt0syst3m_c4n_b3_4tt4ck3d_wh3n_E_15_cL053_t0_N^(n-1)_4nd_d<N^0.25}PicoChip 1
from itertools import groupby
from Crypto.Util.number import *
from enum import Enum
from base64 import b64encode
from secret import flag
import plotly.express as px
import random
class State(Enum):
# PicoChip power states for hardware simulation.
FALLBACK = 0x0
SUCCESS = 0x1
ERROR = 0x2
class PicoChip:
def __init__(self, k: int, N: int, t: int):
self.states = []
self.k = k
self.N = N
self.t = t
self.r = self.gen_op()
def rec(self, s: State):
self.states.append(s)
def gen_op(self) -> list:
rs = []
i = 3
while len(rs) < self.N:
if isPrime(i):
self.rec(State.SUCCESS)
rs.append(i)
i += 2
return rs
def gen_secure_prime(self) -> int:
# More secure than getPrime() as indicated from my latest paper.
while True:
v0 = random.randint(2**(self.k-1), 2**self.k)
v = v0 + 1 - v0 % 2
while True:
is_prime = True
i = 0
while i < self.N:
if v % self.r[i] == 0:
v = v + 2
self.rec(State.FALLBACK)
break
i += 1
self.rec(State.SUCCESS)
if i == self.N:
for m in range(1, self.t+1):
if not miller_rabin(v):
is_prime = False
v = v + 2
self.rec(State.FALLBACK)
break
self.rec(State.SUCCESS)
if is_prime:
return v
def plot(self):
# For transparency, I will show you the internals of PicoChip.
power_states(self.states)
def power_states(states: list):
if State.ERROR in states:
raise Exception("PicoChip is broken!")
power = []
for k, g in groupby(states):
if k != State.FALLBACK:
power.append(sum(1 for _ in g))
else:
power.extend([0 for _ in g])
gx, gy = [], []
for i in range(len(power)):
gx.append(i)
gy.append(power[i])
gx.append(i + 1)
gy.append(power[i])
fig = px.line(x=gx, y=gy, title="PicoChip Power States")
fig.write_html("power_states.html")
def miller_rabin(n: int) -> bool:
if n <= 1 or n == 4:
return False
if n <= 3:
return True
d = n - 1
while d % 2 == 0:
d //= 2
a = 2 + random.randint(1, n - 4)
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
while d != n-1:
x = (x * x) % n
d *= 2
if x == 1:
return False
if x == n - 1:
return True
return False
if __name__ == "__main__":
pico = PicoChip(36, 60, 1)
p = pico.gen_secure_prime()
q = pico.gen_secure_prime()
assert p != q and isPrime(p) and isPrime(q)
assert flag.startswith(b"cvctf{") and flag.endswith(b"}")
flag = flag[6:-1]
N = p * q
e = 0x10001
m = bytes_to_long(flag)
ct = pow(m, e, N)
print("[+] PicoChip Encryption Parameters:")
# print(f"N = {N}")
print(f"e = {e}")
print(f"ct = {ct}")
pico.plot()
print("[+] PicoChip Power States saved.")This problem has a prime generator that leaks side channel information. By tracing back the power from the HTML it generates, and then tracing back the states from power, we can determine some information about mod some small primes, and then use CRT to recover it.
Recovering follows the same concept.
from sage.all import crt, lcm, reduce
from Crypto.Util.number import *
# fmt: off
pico_r = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283]
# fmt: on
def solve_eqs(eqs):
if len(eqs) < 2:
return 0, 0
ms = [-k for k, _ in eqs]
ps = [p for _, p in eqs]
L = reduce(lcm, ps)
res = crt(ms, ps)
return L, res
def solve(st, N, t):
eqs = []
k = 0
idx = 0
while idx < len(st):
for i, s in enumerate(st[idx : idx + N]):
idx += 1
if s == 0:
eqs.append((k, pico_r[i]))
# assert (vp + k) % pico.r[i] == 0
k += 2
break
else:
L, cur_vv = solve_eqs(eqs)
print(f"{L = }")
print(f"{cur_vv = }")
for s in st[idx : idx + t]:
idx += 1
if s == 0:
k += 2
break
if isPrime(cur_vv + k):
print("FOUND1", cur_vv + k)
return cur_vv + k, st[idx:]
if L and (2**37 // L) < 10000:
for u in range(2**37 // L):
if isPrime(cur_vv + k + u * L):
print("FOUND2", cur_vv + k + u * L)
return cur_vv + k + u * L, st[idx:]
# fmt: off
gy = [66,66,0,0,10,10,0,0,0,0,1,1,0,0,60,60,0,0,0,0,2,2,0,0,3,3,0,0,0,0,17,17,0,0,60,60,0,0,0,0,12,12,0,0,1,1,0,0,0,0,4,4,0,0,41,41,0,0,0,0,1,1,0,0,6,6,0,0,0,0,65,65,0,0,0,0,2,2,0,0,1,1,0,0,0,0,3,3,0,0,48,48,0,0,0,0,1,1,0,0,2,2,0,0,0,0,29,29,0,0,28,28,0,0,0,0,60,60,0,0,5,5,0,0,0,0,16,16,0,0,1,1,0,0,0,0,25,25,0,0,61,61]
# fmt: on
power = gy[::2]
st = sum([[0] if v == 0 else [1] * v for v in power], [])
print(st)
st = st[60:]
p, stt = solve(st, 60, 1)
print(stt)
q, _ = solve(stt, 60, 1)
e = 65537
ct = 3059648962482294740345
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(ct, d, p * q)
print(int(m).to_bytes(100, "big").strip(b"\x00"))
# cvctf{p1C@-_}PicoChip 2
from Crypto.Util.number import *
from enum import Enum
from base64 import b64encode
from secret import flag
import random
import csv
class State(Enum):
# PicoChip power states for hardware simulation.
FALLBACK = 0x0
SUCCESS = 0x1
ERROR = 0x2
class PicoChip:
def __init__(self, k: int, N: int, t: int):
self.states = []
self.k = k
self.N = N
self.t = t
self.r = self.gen_op()
def rec(self, s: State):
self.states.append(s)
def gen_op(self) -> list:
rs = []
i = 3
while len(rs) < self.N:
if isPrime(i):
self.rec(State.SUCCESS)
rs.append(i)
i += 2
return rs
def gen_secure_prime(self) -> int:
# More secure than getPrime() as indicated from my latest paper.
while True:
v0 = random.randint(2**(self.k-1), 2**self.k)
v = v0 + 1 - v0 % 2
while True:
is_prime = True
i = 0
while i < self.N:
if v % self.r[i] == 0:
v = v + 2
self.rec(State.FALLBACK)
break
i += 1
self.rec(State.SUCCESS)
if i == self.N:
for m in range(1, self.t+1):
if not miller_rabin(v):
is_prime = False
v = v + 2
self.rec(State.FALLBACK)
break
self.rec(State.SUCCESS)
if is_prime:
return v
def save(self):
# For transparency, I will show you the internals of PicoChip.
power_states(self.states)
def power_states(states: list):
if State.ERROR in states:
raise Exception("PicoChip is broken!")
states = [s.value for s in states]
fields = ['Time', 'Signal']
rows = [[i, s] for i, s in enumerate(states)]
with open('power_states.csv', 'w') as f:
write = csv.writer(f)
write.writerow(fields)
write.writerows(rows)
def miller_rabin(n: int) -> bool:
if n <= 1 or n == 4:
return False
if n <= 3:
return True
d = n - 1
while d % 2 == 0:
d //= 2
a = 2 + random.randint(1, n - 4)
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
while d != n-1:
x = (x * x) % n
d *= 2
if x == 1:
return False
if x == n - 1:
return True
return False
if __name__ == "__main__":
pico = PicoChip(512, 100, 10)
p = pico.gen_secure_prime()
q = pico.gen_secure_prime()
assert p != q and isPrime(p) and isPrime(q)
assert flag.startswith(b"cvctf{") and flag.endswith(b"}")
flag = flag[6:-1]
N = p * q
e = 0x10001
m = bytes_to_long(flag)
ct = pow(m, e, N)
print("[+] PicoChip Encryption Parameters:")
print(f"N = {N}")
print(f"e = {e}")
print(f"ct = {ct}")
pico.save()
print("[+] PicoChip Power States saved.")Almost the same as before, but this time is known and both and are 512 bits, so we use the same method to recover and then use Coppersmith or similar methods.
I found that I can get and , where and . However, there are still a few issues to handle:
- 256 bits is a bit tight for Coppersmith.
- My method cannot determine which part of the power trace is and which part is , so the parameters sent into CRT need to be correct, and we need to find a way to handle errors.
- Similarly, I cannot be sure about .
The main point is to notice that are products of small primes, so after taking , we can use small_roots to solve to get .
Next, since are not 1, there is some additional information that can be used. After some calculations, using CRT, we can find the value of or modulo , which is about 340 bits.
Finally, for the error part, I decomposed and randomly removed a few primes, then used Coppersmith to solve until a solution was found.
from Crypto.Util.number import *
from tqdm import tqdm
import random
from lbc_toolkit import small_roots
N = 130242563655857624894400945577596726349342500250110028576899185041437457270571385988775800707021082684571500938230335838572343683077030043170929464612371476956037213483889197399888953059037490955052374761877827022364642118001281744384383425614733953384975007872647643383223846078326219496054222658506664194809
e = 65537
ct = 105907761990378066226415220707780642346253492128869807523331608442629667283774856771483475721417798409391047173653877895381454531056957845466445503946203117753779878926970882151071816334395199925843076844258607834225532144320120475312185170491128333893223806872578843356036259570319998389877610989110147615590
# get this with `get_mod.py`
Lq = 110771048542294008655567252323407263021635384906342218910220956868946703113415
qmLq = 46507139167438726023448101260439823591848326066022505845258905249241953906242
Lp = 1487051625896473568251626796657514782188841738792655155038905673165
pmLp = 72663085590708489175312897469020819802613550944383864132672454215
L = gcd(Lq, Lp)
qL = qmLq % L
pL = pmLp % L
# qmLq, pmLq is not actually q (mod Lq) and p (mod Lp)
# instead, it is the initial output of `v0 = random.randint(2**(self.k-1), 2**self.k); v = v0 + 1 - v0 % 2`
# I am not sure the `k` value found in `get_mod.py` is correct
# so just test it with coppermsith
x, y = Zmod(L)["x,y"].gens()
f = (qL + x) * (pL + y) - N
x, y = small_roots(f, (2**10, 2**10))[0]
qmLq += x
pmLp += y
# unfortunately, neither Lp and Lq are big enough to apply coppersmith here
# but we can use the fact that n=pq to get more bits of q (mod Lq/gcd(Lq,Lp)) and p (mod Lp/gcd(Lq,Lp))
L2 = Lp // L
qmL2 = N / pmLp % L2
L3 = Lq // L
pmL3 = N / qmLq % L3
LL = Lq * L2
qmLL = crt([qmLq, qmL2], [Lq, L2])
pmLL = crt([pmLp, pmL3], [Lp, L3])
assert qmLL * pmLL % LL == N % LL
# let's coppersmith
x = Zmod(N)["x"].gen()
for _ in range(100):
ps = [p for p, _ in factor(LL)]
# we are not sure it is always correct
# try remove some primes and apply coppersmith until it works
pps = set(ps) - set(random.sample(ps, 8))
Lsub = prod(pps)
print("trying", Lsub, Lsub.bit_length())
qmLsub = qmLL % Lsub
f = (qmLsub + x * Lsub).monic()
rs = f.small_roots(X=2 ** (512 - Lsub.bit_length()), beta=0.49, epsilon=0.1)
if rs:
sol = rs[0]
print("yay", sol)
break
q = ZZ(qmLsub + sol * Lsub)
p = ZZ(N // q)
assert p * q == N
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(ct, d, N)
print(long_to_bytes(m))
# cvctf{jU57_4_s1MpL3_s1d3_ch4nn3L_ch1p@_@}Misc
OJail
An OCaml jail (?), connect and directly Sys.command "sh";; to get a shell.
*Minecraft's Deadly Dilemma
Couldn't solve this problem during the competition
from io import BytesIO
from PIL import Image
import base64
import numpy as np
def load_image(img: str):
with open(img, 'rb') as f:
img = Image.open(f)
img = img.convert('L')
return np.asarray(img)
def load_image_b64(img: str):
img = Image.open(BytesIO(base64.b64decode(img)))
img = img.convert('L')
return np.asarray(img)
def distance(x, y):
return np.linalg.norm(x - y)
def is_close(inp, x):
if inp.shape != x.shape:
return False
return np.sqrt(np.sum(np.abs(inp - x))) < 474
if __name__ == '__main__':
sword = load_image("./sword.png")
pickaxe = load_image("./pickaxe.png")
try:
test = load_image_b64(input().strip())
if is_close(test, pickaxe) and distance(test, pickaxe) > distance(test, sword):
from secret import flag
print(flag)
else:
print("Nope!")
except:
exit(0)In short, there are two 64x64 images pickaxe and sword, and we need to find an image such that L2Norm(img - pickaxe) > L2Norm(img - sword) and sqrt(L1Norm(img - pickaxe)) < 474.
My approach was to use PyTorch with backpropagation to find it, and the loss part was adjusted randomly until it worked.
from io import BytesIO
from PIL import Image
import base64
import numpy as np
import torch
def load_image(img: str):
with open(img, "rb") as f:
img = Image.open(f)
img = img.convert("L")
return np.asarray(img)
def load_image_b64(img: str):
img = Image.open(BytesIO(base64.b64decode(img)))
img = img.convert("L")
return np.asarray(img)
def distance(x, y):
return np.linalg.norm(x - y)
def is_close(inp, x):
if inp.shape != x.shape:
return False
return np.sqrt(np.sum(np.abs(inp - x))) < 474
sword = load_image("./sword.png")
pickaxe = load_image("./pickaxe.png")
sword_tensor = torch.tensor(sword).float()
pickaxe_tensor = torch.tensor(pickaxe).float()
x = torch.nn.Parameter(torch.rand((1, 1, 64, 64)), requires_grad=True)
optim = torch.optim.SGD([x], lr=3e-1)
def loss_fn(x):
dist = torch.sqrt(torch.sum(torch.abs(x - pickaxe_tensor)))
cond2 = torch.norm(x - pickaxe_tensor) - torch.norm(x - sword_tensor)
total_loss = dist - cond2 * 2
return total_loss, dist, -cond2 * 2
i = 0
while True:
optim.zero_grad()
loss, a, b = loss_fn(torch.clamp(x, 0, 254))
if i % 1000 == 0:
print(i, loss, a, b)
if a < 474 and b < 0:
xxx = torch.clamp(x, 0, 254).detach().numpy().reshape(64, 64).round()
img = Image.fromarray(xxx)
img = img.convert("L")
img.save("result.png")
yyy = load_image("result.png")
c1 = is_close(yyy, pickaxe)
c2 = distance(yyy, pickaxe) > distance(yyy, sword)
print(
c1,
c2,
distance(yyy, pickaxe),
distance(yyy, sword),
np.sqrt(np.sum(np.abs(yyy - pickaxe))),
np.sqrt(np.sum(np.abs(xxx - pickaxe))),
)
if c1 and c2:
break
loss.backward()
optim.step()
i += 1
with open("result.png", "rb") as f:
print(base64.b64encode(f.read()))
"""
iVBORw0KGgoAAAANSUhEUgAAAEAAAABACAAAAACPAi4CAAAGzUlEQVR4nI1W2ZbbuA4EwV27lzi5//9zSXfbkrVR3O/DTJJu2Z0JHiFWsQACdUQYiZTq/nzNhyjejjNQqjZUmzQzcs+5czXhMNez9CwtF+MEncRallcSNAs2YYBUy/Hrm2gkXLtBkbgFzox5VbSK+jA3Ik9sI1ek0kTIrEESKkhDXTHGmSDky7aiF0nrFwH1cHg73riQ/dcwVES8tmEqAkb/zbLXLoQYaFBZix7aKWextPSOLKmgV1bETRBIx5ECT7Gv4iRMEOeXEhTpi8rLqxwYMAsf40IkIQoXmYkMkUmyBbXqtODxtZBkiYQ3fap7ZROpaL7D5fuOQKkRM/FCuYJJi+kaYK0nVuutkHxivKY/WgbZAWZG5gvdCwBuKNZrAZlRWM4m1FmLKZNtY2ufkmR0OvQynXnddv0UJ032BDFFIrPyhjUpJrnYb+GtYZs93NHWca0nAE35QKBQ+Xp++QeE6TdBqzwrcypNwa/oaDx9BzlKIZDZJhHw9JTo1Ld5QTaL+V/QOzwUI8Vox/RtsadYTcX67Wsl7OSTT6O3XzcaFtiUlSlOgm97/QDg8kxq30z1lGOXLKOeX4/U+8qshGgvDLTk5mW7OReewAGK1qD0o4zoJN1Kxv2olz7baSTeCZateIkHWiyUyad40NeRiMwRPW7UXQKhMYheaRNEYYXrTzPLxdyZxNz0lACLhqgNSjoeCbmr6XLVxdvhWtCZ+ZPP2sT6hRT5ORgA4BhmpNU3U+h+HcVyuTJBRH9JWpHKFEUf6pVx+qx7/wbbBOlWru548LefyQb0vHwd7CU5i9xGzodfitOeAAURrvWZZDA/k19GFclGGOWLr+n8h/sB5GnARqetcrr4lVwslRxKamw62hv73TB8JKjmhmWjBAm338kVbtCUS8ESc7SWv4Xv9QMASM+80g9rDkYha6bGDp8BAeCcM+a5Qqnpdt9/PKpiArN82L49zy1S79VEsKJ2faCvDaRual8+Zj+8AktQoEPSio3hdYe/zAHFenD9Z+gTiC1PNJOOTcCBvReICQB4uWb3EfyhBBNEtNVSCcMO2eTxodYvKRT73Pto+lRHoVZncKGB5IceTNv6AfRhBk7leYQNJLGlRwIsk+7t9x0P4/qxEACAs6vupYtr6S0i+2L18n4OPsf/+jSVizNdQQUEJfAGb/D4jJ9pAACA9m4bug4q2DYnpihJ5fgfuJ93J4BSkMjjpF2G4ZDjSo7jYbYJ0p+Kfx9HmslIHDARfeLHhDe+aPa+wp3efagbzSEUAFCkixxfWSl6Ldyzo08UVaGOLCwNzkgCh9V6jjU/e/VX4gFA+8BIT2cWWKxSrSvNcA5vj3P0WQ0zg6lrzQEap310hpcFzng2T8CPNXxl/2t1SsXEa288sEmFeAsBy4HUz9u1i6mebS4J1cSNAVqpqSD14Bg2o3xwpGfReQL3Kogb1pgJiwbIVkuOxiTCAfCDZz5I0gx77vNZR4TkDbUzAuhiySOKouEPr/g4Eweg34nMScRS1dVGupuGqFxRoFlvOzw+UVAsrCqpD1HQUieWqi2Wmxo493gwhFfnwzv/3LsPAACmclXzYrKzlg0pi6CQhJKQgtB64S7+s0740RU+bgeTsUux1+DKzV3uDQGyKieZNlyrrdyVnh47kQy8QAOZtdk1DmHjV5Z4Rt9sceA/9po/2aWxzTzF84x4m8e6WOGVMFLtTf15IAAAy1LRsUA7nx1mvgFlTX66ip+xFODv1BN2WMXEecyGSLr+nZP8Kun81mVitK8s9ZCwZn9C7cEAwAcg9yAmdfc+jTOy+BcM7zXWQvcEIE4bzLm6MEPLv6rgVywHwx3lwR6oJT4RAL5bxk/c9WcZLJzy7WSgst6JwFG2e0P6j56KU+TtPfCX7LmSHMu0/4v9D3vxkb1KUm0CSD0hxduDoyYAQHz2TwUAAOXg0ygDb+Yu+DhicT/8+cZ9THKCNoxyLF+ycAKTpo+H/lBFp5t0hnzCKDt0UrCmbx/O8E9ZvtDvaq5urDQxO7IwMuHw0ETIn/k8wLrKkm11RhsPgWUSGSvdwySaoPnajsrF1lql8wCHbU5lXll77ap7N02JKrk2Y/eDANr6bU9w5MGS2S+kGQMu/T3QFI6gkcO1RkMTXJRbbsGZHwIiaQxHp6XN2cpJgzlmmKptKxCjvqcus5fa1ldo0KTjNXTDKQ8FOhUjrIJYFOhQmI5uOEuI5yqxtZ/ryfGgLF4FGYd4tt1QojJSQzyPBU1is4g5UlRUVw1ulsRxUah8oOsgk6J+U7zRiRFNWFATIaMoOqiW8UcTkngZWFnElICJscEp/B98MNFTPsG0qAAAAABJRU5ErkJggg==
"""
# cvctf{chatGPT_isn't_wrong_but_u_n33d_more_s@mples}