K3RN3L CTF 2021 WriteUps
這個 CTF 我是只有在有空的時候才去解點 Crypto 題目的，因為有不少有趣的題目所以還是紀錄一下。這次用的隊伍名是 peko，31 名。
Pryby
from Crypto.Util.number import bytes_to_long
def f(n):
q=[True]*(n + 1)
r=2
while r**2<=n:
if q[r]:
for i in range(r**2,n+1,r):q[i] = False
r += 1
return [p for p in range(2,n+1) if q[p]]
class G:
def __init__(self, f):
self.f = f
self.state = 1
def move(self):
q=1
for p in self.f:
if self.state%p!=0:
self.state=self.state*p//q
return
q*=p
flag = open('flag.txt','r').read().strip().encode()
flag=bytes_to_long(flag)
gen = G(f(pow(10,6)))
for _ in range(flag):gen.move()
print('enc =',gen.state)
# enc = 31101348141812078335833805605789286074261282187811930228543150731391596197753398457711668323158766354340973336627910072170464704090430596544129356812212375629361633100544710283538309695623654512578122336072914796577236081667423970014267246553110800667267853616970529812738203125516169205531952973978205310可以看出它是拿質數作為 binary 表示，所以就分解開然後恢復 bits 得到 flag:
fs = [
a
for a, b in factor(
31101348141812078335833805605789286074261282187811930228543150731391596197753398457711668323158766354340973336627910072170464704090430596544129356812212375629361633100544710283538309695623654512578122336072914796577236081667423970014267246553110800667267853616970529812738203125516169205531952973978205310
)
]
ps = list(primes(1500))
print(int(sum([1 << ps.index(x) for x in fs])).to_bytes(100, "big"))Pascal RSA
triangle =[[1]]
flag = open('flag.txt','rb').read()
from Crypto.Util.number import getPrime,bytes_to_long
from math import gcd
p = getPrime(20)
while len(triangle[-1]) <= p:
r = [1]
for i in range(len(triangle[-1]) - 1):
r.append(triangle[-1][i] + triangle[-1][i+1])
r.append(1)
triangle.append(r)
code = ''
for x in triangle[-1]:
code+=str(x%2)
d = int(code,2)
while True:
P = getPrime(512)
Q = getPrime(512)
if gcd(d, (P-1)*(Q-1)) == 1:
N = P*Q
e = pow(d,-1,(P-1)*(Q-1))
break
enc = pow(bytes_to_long(flag), e, N)
file = open('challenge.txt','w')
file.write(f'p = {p}\nenc = {enc}\nN = {N}')這題 RSA 的 是使用一個帕斯卡三角形的第 層模 2 之後的 binary representation 所得到的，查一下相關資訊可以找到 Sierpiński’s triangle，而它轉換為數字的數列在 OEIS 上也有: A001317
所以用它裡面給的通項公式求出 之後就有 flag 了:
# https://oeis.org/A001317
p = 751921
d = 1
for _ in range(p):
d ^= 2 * d
c = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
n = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447
m = pow(c, d, n)
print(m.to_bytes(128, "big"))Poly Expo go BRRRRR
#!/usr/bin/env sage
#
# Polymero
#
from Crypto.Util.number import getPrime
with open('flag.txt','rb') as f:
FLAG = f.read()
f.close()
n = getPrime(512) * getPrime(512)
e = 0x10001
P.<x> = PolynomialRing(GF(2))
N = sum([int(j)*x**i for i,j in enumerate('{:0{bl}b}'.format(n,bl=n.bit_length()))])
Q.<x> = P.quotient(N)
def encrypt(msg):
if type(msg) == bytes:
msg = int.from_bytes(msg,'big')
msg = sum([int(j)*x**i for i,j in enumerate('{:0{bl}b}'.format(msg,bl=n.bit_length()-1))])
cip = Q(msg)**e
cip = int(''.join([str(i) for i in list(cip)]),2)
return cip
c = encrypt(FLAG)
print('n =',n)
print('e =',e)
print('c =',c)
assert solve()
#
# n = 119688104315557021890936576297322528053073582644938225605833562855944546643311189725353580415278613605803528999976536949698525581164157480218289586687945087549976509446759942778609918817975151644563678567137671925049937536315926169828583738712154203276012477308556625213229949900385215601055758028238785190211
# e = 65537
#
# c = 59180475538014020769986137847579404920412136380976726613826924727288568855214946199702335444771145318394201684142700441287649150098774979773106915707593238156979003572684188994666984941867671144226245449471326607224512384706414018555885923177955268177207582929765645093722741174664225408159262482249199006862
#這題看起來像是 RSA，只是 被轉換到 的一個多項式 ，之後的運算都在 下運算。flag 本身也是轉換到那個 ring 之下的多項式之後開 次方加密後再轉回數字。
可以發現 本身是可以分解的，所以要找個方法求出它的 order 後拿到 解密即可。查一下資料可以在這邊找到公式。
對於 底下 degree 的 irreducible polynomial 來說
然後還有對於任意多項式都有
有兩個關係之後就足夠計算出 ，之後再求 即可解密。
n = 119688104315557021890936576297322528053073582644938225605833562855944546643311189725353580415278613605803528999976536949698525581164157480218289586687945087549976509446759942778609918817975151644563678567137671925049937536315926169828583738712154203276012477308556625213229949900385215601055758028238785190211
e = 65537
c = 59180475538014020769986137847579404920412136380976726613826924727288568855214946199702335444771145318394201684142700441287649150098774979773106915707593238156979003572684188994666984941867671144226245449471326607224512384706414018555885923177955268177207582929765645093722741174664225408159262482249199006862
P.<x> = PolynomialRing(GF(2))
N = sum(
[
int(j) * x ** i
for i, j in enumerate("{:0{bl}b}".format(n, bl=int(n).bit_length()))
]
)
Q.<x> = P.quotient(N)
# https://pointloma.whdl.org/sites/default/files/Freed-RSA%20Encryption%20Using%20Polynomial%20Rings-HP.pdf
# 4.5
# For a irreducible polynomial f(x) over F_p
# phi(f(x)^n)=p^((deg f(x))*n)-p^((deg(f(x)))*(n-1))
# phi(f(x)*g(x))=phi(f(x))*phi(g(x)) holds too
phi = product(
[2 ** (poly.degree() * n) - 2 ** (poly.degree() * (n - 1)) for poly, n in N.factor()]
)
d = inverse_mod(e, phi)
c = sum(int(a) * x ^ i for i, a in enumerate(bin(c)[2:]))
m = c ^ d
print(int("".join([str(i) for i in list(m)]), 2).to_bytes(100, "big"))1-800-758-6237
#!/usr/bin/env python3
#
# Polymero
#
# Imports
from Crypto.Cipher import AES
import os, time, random
# Local imports
with open('flag.txt', 'rb') as f:
FLAG = f.read()
f.close()
def leak(drip):
rinds = sorted(random.sample(range(len(drip)+1), 16))
for i in range(len(rinds)):
ind = rinds[i] + i*len(b'*drip*')
drip = drip[:ind] + b'*drip*' + drip[ind:]
aes = AES.new(key=server_key, mode=AES.MODE_CTR, nonce=b'NEEDaPLUMBER')
return aes.encrypt(drip).hex()
server_key = os.urandom(16)
while True:
print(leak(FLAG))
time.sleep(1)很明顯的是 AES-CTR nonce reuse，代表所有的 message 都是 xor 某個相同的 key stream 加密的。首先可以先存個大概 100 筆 ciphertext 下來比較好處理。
leak 函數就是在你的 flag 的一些任意 index 插入 *drip* 這個字串，所以明文中肯定也有許多的 *drip* 出現。
所以先假設說其中至少有一筆 ciphertext 的明文是 flag{ 開頭，由此可以還原出 key stream 的前面五個 bytes。(會有多個 candidates)
之後對於剩下的部分就利用 *drip 後面一定是 * 和 *dri 後面是 p 這兩個去一個一個把剩下的 key stream 還原即可。
from itertools import combinations
import string
def xor(a, b):
return bytes(x ^ y for x, y in zip(a, b))
data = []
with open("output.txt") as f:
for line in f:
data.append(bytes.fromhex(line))
good = set(map(ord, string.ascii_letters + string.digits + " {}_*:!"))
kss = set()
flag = b"flag{"
dt = {}
for a, b in combinations(data, r=2):
tmp = xor(xor(a, b), flag)
if all(x in good for x in tmp) and xor(a, flag) == xor(b, flag):
kss.add(xor(a, flag))
for k in kss:
for _ in range(200):
for i, ct in enumerate(data):
pt = xor(k, ct)
r = pt.replace(b"*drip*", b"")
if pt.endswith(b"*drip"):
k = xor(pt + b"*", ct)
break
if pt.endswith(b"*dri"):
k = xor(pt + b"p", ct)
break
else:
break
if not all(x in good for x in r):
break
print(r)
# flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}Poly-Proof
#!/usr/bin/env python3
#
# Polymero
#
# Imports
import os
# Local imports
with open('flag.txt','rb') as f:
FLAG = f.read()
f.close()
HDR = r"""|
| ________ ________ ___ ___ ___ ________ ________ ________ ________ ________
| |\ __ \|\ __ \|\ \ |\ \ / /| |\ __ \|\ __ \|\ __ \|\ __ \|\ _____\
| \ \ \|\ \ \ \|\ \ \ \ \ \ \/ / / \ \ \|\ \ \ \|\ \ \ \|\ \ \ \|\ \ \ \__/
| \ \ ____\ \ \\\ \ \ \ \ \ / / \ \ ____\ \ _ _\ \ \\\ \ \ \\\ \ \ __\
| \ \ \___|\ \ \\\ \ \ \____ \/ / / \ \ \___|\ \ \\ \\ \ \\\ \ \ \\\ \ \ \_|
| \ \__\ \ \_______\ \_______\__/ / / \ \__\ \ \__\\ _\\ \_______\ \_______\ \__\
| \|__| \|_______|\|_______|\___/ / \|__| \|__|\|__|\|_______|\|_______|\|__|
| \|___|/
|"""
class Server:
def __init__(self, difficulty):
self.difficulty = difficulty
self.coefficients = None
self.limit = 8
self.i = 0
self.set_up()
def _eval_poly(self, x):
return sum([ self.coefficients[i] * x**i for i in range(len(self.coefficients)) ])
def _prod(self, intlst):
ret = 1
for i in intlst:
ret *= i
return ret
def set_up(self, verbose=False):
print(HDR)
print("| To prove to you that I own the flag, I used it to make a polynomial. Challenge me all you want!")
noise = [ self._prod(list(os.urandom(self.difficulty))) for i in range(len(FLAG)) ]
self.coefficients = [ noise[i] * FLAG[i] for i in range(len(FLAG)) ]
def accept_challenge(self):
print("|\n| Name your challenge (as ASCII string):")
try:
user_input = int.from_bytes(str(input("| >> ")).encode(),'big')
except ValueError:
print("|\n| ERROR - That ain't working... s m h ")
return
if user_input == 0:
print("|\n| ERROR - You clearly don't know what ZERO-KNOWLEDGE means eh?")
return
if user_input <= 0:
print("|\n| ERROR - Your clever tricks will not work here, understood?")
return
print("|\n| Here's my commitment: {}".format(self._eval_poly(user_input)))
self.i += 1
def run(self):
while self.i < self.limit:
try:
self.accept_challenge()
except:
break
if self.i >= self.limit:
print("|\n| Are you trying to steal my polynomial or something?")
print("| I think I have proven enough to you...")
print("|\n|\n| ~ See you back in polynomial time! o/ \n|")
S = Server(15)
S.run()這題會先把 flag 的每個字元乘上一些 noise 得到多項式係數 。然後你可以輸入 去得到 ，重複 8 次。
第一個目標是要還原出多項式係數，一個最簡單的做法就是取 ，然後把 以 進位表示出來就能拿到 。
不過我當時卻沒想到這個，反而用了一個複雜很多的作法:
取一個夠大的常數 之後做 LLL 可以找到一個短向量 獲得多項式的係數。
取得多項式係數後也沒辦法直接拿到 flag，但是因為 ，其中的 和 分別是 noise 和 flag。所以就拿多組的 之後取 gcd 就有機會拿到 。
不過實際上只能拿到 的倍數，非常難以得到真正的 ，所以這邊需要利用 flag 本身可能的字元範圍去猜可能的 ，之後再 guess flag 是什麼東西。因為 flag 本身是 leetspeak 所以有點難猜…
from pwn import remote, process
import string
import random
def get_pair(io):
r = "".join(random.sample(string.ascii_letters, 16)).encode()
io.sendlineafter(b"| >> ", r)
r = int.from_bytes(r, "big")
io.recvuntil(b"commitment: ")
fr = int(io.recvlineS().strip())
return r, fr
def get_params():
io = remote("ctf.k3rn3l4rmy.com", 2232)
pairs = [get_pair(io) for _ in range(8)]
io.close()
rs, frs = zip(*pairs)
return rs, frs
def solve_coefs(rs, frs, n):
assert len(rs) == 8
M = matrix([[r ^ i for i in range(n)] for r in rs]).T
M = M.augment(matrix.identity(n))
M = matrix([-fr for fr in frs] + [0] * n).stack(M)
M[:, :8] *= 2 ^ 128
for row in M.LLL():
if all(x == 0 for x in row[:8]):
return row[8:]
def find_possible(x):
flagchrs = ("{_}" + string.ascii_lowercase + string.digits).encode()
return [y for y in flagchrs if x % y == 0]
n = 101 # flag length
# flag = [0] * n
# fmt: off
flag = [408, 648, 776, 206, 984, 872, 416, 484, 1176, 204, 1520, 792, 968, 396, 432, 204, 380, 968, 192, 234, 2736, 190, 460, 408, 1584, 456, 204, 232, 920, 380, 104, 220, 800, 190, 920, 52, 220, 196, 464, 588, 488, 408, 1140, 484, 96, 234, 1368, 760, 196, 220, 448, 936, 464, 920, 190, 96, 5472, 2280, 832, 832, 460, 380, 464, 832, 196, 460, 380, 448, 2496, 1320, 800, 204, 436, 196, 396, 760, 880, 192, 928, 760, 464, 208, 936, 412, 416, 464, 190, 968, 192, 936, 380, 208, 440, 242, 1392, 2496, 294, 880, 2472, 500, 240]
# fmt: on
while True:
rs, frs = get_params()
noiseflag = solve_coefs(rs, frs, n)
for i in range(n):
flag[i] = gcd(flag[i], noiseflag[i])
print(flag)
fflag = [
"".join(map(chr, p)) if len((p := find_possible(x))) <= 5 else x for x in flag
]
print(fflag)
if all(0 <= x < 256 for x in flag):
print(bytes(flag))
break
# by guessing leetspeak...
# flag{m4yb3_cycl3_y0ur_s3cr3ts_4nd_s4n1t1z3_y0ur_1nputs_0r_h4s_th1s_p4nd3m1c_n0t_t4ught_y0u_4nyth1ng}Non-Square Freedom 1
#!/usr/bin/env python3
#
# Polymero
#
# Imports
from Crypto.Util.number import getPrime
import os
# Local imports
with open('flag.txt','rb') as f:
FLAG = f.read()
f.close()
# Key gen
P = getPrime(512//8)
Q = getPrime(256)
R = getPrime(256)
N = P**8 * Q * R
E = 0x10001
def pad_easy(m):
m <<= (512//8)
m += (-(m % (P**2)) % P)
return m
# Pad FLAG
M = pad_easy(int.from_bytes(FLAG,'big'))
print('M < N :',M < N)
print('M < P**8 :',M < (P**8))
print('M < Q*R :',M < (Q*R))
# Encrypt FLAG
C = pow(M,E,N)
print('\nn =',N)
print('e =',E)
print('c =',C)
# Hint
F = P**7 * (P-1) * (Q-1) * (R-1)
D = inverse(E,F)
print('\nD(C) =',pow(C,D,N))
#----------------------------------------------------
# Output
#----------------------------------------------------
# M < N : True
# M < P**8 : True
# M < Q*R : True
#
# n = 68410735253478047532669195609897926895002715632943461448660159313126496660033080937734557748701577020593482441014012783126085444004682764336220752851098517881202476417639649807333810261708210761333918442034275018088771547499619393557995773550772279857842207065696251926349053195423917250334982174308578108707
# e = 65537
# c = 4776006201999857533937746330553026200220638488579394063956998522022062232921285860886801454955588545654394710104334517021340109545003304904641820637316671869512340501549190724859489875329025743780939742424765825407663239591228764211985406490810832049380427145964590612241379808722737688823830921988891019862
#
# D(C) = 58324527381741086207181449678831242444903897671571344216578285287377618832939516678686212825798172668450906644065483369735063383237979049248667084304630968896854046853486000780081390375682767386163384705607552367796490630893227401487357088304270489873369870382871693215188248166759293149916320915248800905458
#一個奇怪的 RSA，令 D(C) 為 之後可以知道 ，但是 。
可以從 padding 函數觀察到 ，所以從 會拿到 ，之後可以拿到 。把 模 之後就很神奇的得到的我們要的 。
其實我也不太清楚這題究竟是怎麼回事…。詳細的解釋可以看作者的 WriteUp。
Tick Tock
#!/usr/bin/env python3
#
# Polymero
#
# Imports
from Crypto.Util.number import getPrime, isPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from random import randint
from hashlib import sha256
# Local imports
with open('flag.txt','rb') as f:
FLAG = f.read()
f.close()
assert len(FLAG) % 8 == 0
# Helper functions
def legendre_symbol(a, p):
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
def modular_sqrt(a, p):
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return p
elif p % 4 == 3:
return pow(a, (p + 1) // 4, p)
s = p - 1
e = 0
while s % 2 == 0:
s //= 2
e += 1
n = 2
while legendre_symbol(n, p) != -1:
n += 1
x = pow(a, (s + 1) // 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e
while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = pow(t, 2, p)
if m == 0:
return x
gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
# TickTock class
class TickTock:
def __init__(self, x, y, P):
self.x = x
self.y = y
self.P = P
assert self.is_on_curve()
def __repr__(self):
return '({}, {}) over {}'.format(self.x, self.y, self.P)
def __eq__(self, other):
return self.x == other.x and self.y == other.y and self.P == other.P
def is_on_curve(self):
return (self.x*self.x + self.y*self.y) % self.P == 1
def add(self, other):
assert self.P == other.P
x3 = (self.x * other.y + self.y * other.x) % self.P
y3 = (self.y * other.y - self.x * other.x) % self.P
return self.__class__(x3, y3, self.P)
def mult(self, k):
ret = self.__class__(0, 1, self.P)
base = self.__class__(self.x, self.y, self.P)
while k:
if k & 1:
ret = ret.add(base)
base = base.add(base)
k >>= 1
return ret
def lift_x(x, P, ybit=0):
y = modular_sqrt((1 - x*x) % P, P)
if ybit:
y = (-y) % P
return TickTock(x, y, P)
def domain_gen(bits):
while True:
q = getPrime(bits)
if isPrime(4*q + 1):
P = 4*q + 1
break
while True:
i = randint(2, P)
try:
G = lift_x(i, P)
G = G.mult(4)
break
except: continue
return P, G
def key_gen():
sk = randint(2, P-1)
pk = G.mult(sk)
return sk, pk
def key_derivation(point):
dig1 = sha256(b'x::' + str(point).encode()).digest()
dig2 = sha256(b'y::' + str(point).encode()).digest()
return sha256(dig1 + dig2 + b'::key_derivation').digest()
# Challenge
flagbits = [FLAG[i:i+len(FLAG)//8] for i in range(0,len(FLAG),len(FLAG)//8)]
for i in range(8):
print('# Exchange {}:'.format(i+1))
P, G = domain_gen(48)
print('\nP =', P)
print('G = ({}, {})'.format(G.x, G.y))
alice_sk, alice_pk = key_gen()
bobby_sk, bobby_pk = key_gen()
assert alice_pk.mult(bobby_sk) == bobby_pk.mult(alice_sk)
print('\nA_pk = ({}, {})'.format(alice_pk.x, alice_pk.y))
print('B_pk = ({}, {})'.format(bobby_pk.x, bobby_pk.y))
key = key_derivation(alice_pk.mult(bobby_sk))
cip = AES.new(key=key, mode=AES.MODE_CBC)
enc = cip.iv + cip.encrypt(pad(flagbits[i], 16))
print('\nflagbit_{} = "{}"'.format(i+1, enc.hex()))
print('\n\n\n')這題有個在一個特殊 group 上的 diffie hellman，需要解開上面的 DLP 才能拿到 key 去解密 flag。
此題因為是在 writeup submission 的範圍中，大概 11/17 的時候我才能公開這題的解法。
*MathyOracle
比賽中沒解，後來看到解法覺得值得解
print('Find my number N, and I will give you the flag.')
def f(N,k):
while min(N,k)>0:
if k>N: N,k = k,N
N%=k
return max(N,k)
import random
N = random.getrandbits(512)
for i in range(600):
print(f"Try #{i+1}: ")
k = input(f'Enter k: ')
l = input(f'Enter l: ')
try:
k= int(k)
assert 0<k<pow(10,500)
l= int(l)
assert 0<l<pow(10,500)
except:
print('Invalid input. Exiting...')
quit()
print(f'f(N+l,k) = {f(int(N+l),k)}\n')
guess = input('What is N?')
if str(N)==guess:
print(open('flag.txt').read().strip())
else:
print('Wrong answer. The number was '+str(N))簡單來說有個 ，然後你可以指定任意 讓它計算 ，目標要在 600 次的 query 內把 還原才行。
如果可以 的話那麼一次就能取得 ，因為 。
這題的題目介紹有說 My friend told me I need LSB to solve this, but I don’t do drugs! Can you solve it for me instead?，關鍵在於 LSB 的部份。
的時候可以知道 的 parity，也就是能拿到 的 LSB。有 LSB 的時候可以透過改 把 的已知部分都清成 ，然後 就能取得第二個 bit，這樣以此類推即可。
只是這個方法會遇到的問題是 ，不過只要把方法稍微小改一下即可。假設目前已知 的底下 個 bits ，目前想知道的是第 bits，那取 的話 的第 就會被 flip。
假設原本第 個 bits 是 ，那麼 的 lowest bits 都會是 0，反之只有 bits 是 0。所以取 時如果 就代表 bit 是 1，反之為 0。
from pwn import process
io = process(["python", "main.py"])
def get(k, l):
io.sendlineafter(b"k: ", str(k).encode())
io.sendlineafter(b"l: ", str(l).encode())
io.recvuntil(b"= ")
return int(io.recvlineS().strip())
n = 0
for i in range(600):
l = (1 << i) - n
k = 1 << (i + 1)
if get(k, l) == k:
n += 1 << i
print(n)
io.sendlineafter(b"N?", str(n).encode())
print(io.recvlineS())另解
這個是在 Discord 中看到的不同作法，取 ，然後對於 到 都計算 。如果 可以被某個質數 整除的話就知道 ，蒐集到很多的等式之後 CRT 求出答案。