- ASCWQ 2022
- Crypto
- Rsa In The Wild
- OSP
- Misc
- Weird FS
- corCTF 2022
- Crypto
- tadpole
- luckyguess
- exchanged
- hidE
- Forensics
- whack-a-frog
周末找了两个国外的比赛，做了几个题。 ASCWQ 2022
（这个比赛的源码忘保存了。。。现在想写博客发现官网把challenges关了，只能随便写点思路QAQ
Crypto Rsa In The Wild审查源码可以知道调用密钥生成函数时使用的p是固定的，对于每个接入的用户，系统会单独生成一个q，然后计算n进行RSA。因此求用户key的最大公因数就可以拿到p。
四个人key的gcd等于1，猜测分组了，遍历发现第一个人和第三个人使用一组p，第二个人和第四个人使用另一组p。
将四个人的key分解掉，分别求解即可。
import json
from math import gcd
from libnum import invmod
with open('output.json', 'r') as f:
info = json.load(f)
k = []
c = []
APT = ['John', 'Sara', 'Y4mm1', 'Gary']
for i in range(4):
k.append(info[i][APT[i]]['key'])
c.append(info[i][APT[i]]['msg'])
e = 0x10001
p1 = gcd(k[0],k[2])
p2 = gcd(k[1],k[3])
q1 = k[0] // p1
q2 = k[1] // p2
q3 = k[2] // p1
q4 = k[3] // p2
d1 = invmod(e,(p1-1)*(q1-1))
d2 = invmod(e,(p2-1)*(q2-1))
d3 = invmod(e,(p1-1)*(q3-1))
d4 = invmod(e,(p2-1)*(q4-1))
m1 = n2s(int(pow(c[0],d1,k[0])))
m2 = n2s(int(pow(c[1],d2,k[1])))
m3 = n2s(int(pow(c[2],d3,k[2])))
m4 = n2s(int(pow(c[3],d4,k[3])))
print(m1)
print(m2)
print(m3)
print(m4)
# b'x0cXx08x0bxc4)xcdxcdx8fxb3x94x11xc4x9bxa4eCx93x12xe5[x15uxae5xbbxe2&xca!xf5xf2xa3KM'
# b"x17xfe&x9c.\exb6x91xdc7xcfxf0UAx10(x915}4x05x1dxf23x17x0cox1dxa5xccOtx89x98x12xe4x06xaaxc2Bxbe#v9xa5[mx96x91xfexefx1f{xf3xd8x06x9cx05x18zWx01xda(xac3x8fxa1x02x92Fx96xe0xf9x8c+xb0xb2x9bex0e1x97xd6xec%xf8x16xf6xf0xb3Yxcbxebxc4xc8xa4Yx0bWyxffxc4IDw\xa7x9bxf5Pxb4xd9xdaMxcaxb4x9bx8ax95'rx08xa9xe1n%"
OSP
一次一密，生成了一个与flag等长的字节流secret，对flag中的每个字符做如下处理（十六进制值）：
flag[i] = flag[i] * p + secret[i]
其中p和secret均未知，但是我们知道flag格式肯定是"ASCWQ{XXX}"，而且字节流串每个字节最大的值是0xff，完全可以爆破。因此我们尝试先把p爆出来。
A的ascii是65，S的ascii是83，本身是互素的，只需要爆破256*256即可：
with open('output.txt', 'r') as f:
c = f.read().splitlines()
for i in range(256):
mul1 = c[0] - i
for j in range(256):
mul2 = c[1] - j
if gcd(mul1,mul2) > 1:
print(gcd(mul1,mul2))
结果有个很明显的大素数就是p。
这样我们就可以爆破所有字符：
for i in range(len(c)):
for j in range(256):
if (c[i] - j) % p == 0:
print(chr((c[i] - j) // p),end='')
# ASCWG{Wh47_1f_17's_N07_@_Pr1M3!-f0ffa3657e}
Misc
Weird FS
给了一个img镜像，但是用Linux尝试挂载时会报/dev/loop0的经典错误，估计是数据块识别错误。
先看看里面藏没藏东西，binwalk一下发现里面有个Flag.zip。分离出来发现有密码。strings看一下时间戳，没找到密钥。猜测压缩包是个弱口令加密，用Kit爆一下得到口令：juelma。解压就可以拿到flag了。
ASCWG{M4C_4N6_1$_Co0l}
corCTF 2022
Crypto的几个跟LCG有关的题还不错。
Crypto tadpolef ( 31337 ) ≡ a × 31337 + b ( m o d p ) f ( f ( 31337 ) ) ≡ a × f ( 31337 ) + b ( m o d p ) ⇒ g = g c d ( f ( 31337 ) − ( a × 31337 + b ) , f ( f ( 31337 ) ) − ( a × f ( 31337 ) + b ) ) = k p i f i s P r i m e ( g ) ⇒ g = p f(31337) equiv a times 31337 + b space (mod space p) \ f(f(31337)) equiv a times f(31337) + b space (mod space p) \ Rightarrow g = gcd(f(31337)-(a times 31337 + b),f(f(31337))-(a times f(31337) + b)) =kp \ if space isPrime(g) Rightarrow g = p f(31337)≡a×31337+b (mod p)f(f(31337))≡a×f(31337)+b (mod p)⇒g=gcd(f(31337)−(a×31337+b),f(f(31337))−(a×f(31337)+b))=kpif isPrime(g)⇒g=p
from Crypto.Util.number import *
from math import gcd
from libnum import n2s
a = 7904681699700731398014734140051852539595806699214201704996640156917030632322659247608208994194840235514587046537148300460058962186080655943804500265088604049870276334033409850015651340974377752209566343260236095126079946537115705967909011471361527517536608234561184232228641232031445095605905800675590040729
b = 16276123569406561065481657801212560821090379741833362117064628294630146690975007397274564762071994252430611109538448562330994891595998956302505598671868738461167036849263008183930906881997588494441620076078667417828837239330797541019054284027314592321358909551790371565447129285494856611848340083448507929914
f = 52926479498929750044944450970022719277159248911867759992013481774911823190312079157541825423250020665153531167070545276398175787563829542933394906173782217836783565154742242903537987641141610732290449825336292689379131350316072955262065808081711030055841841406454441280215520187695501682433223390854051207100
ff = 65547980822717919074991147621216627925232640728803041128894527143789172030203362875900831296779973655308791371486165705460914922484808659375299900737148358509883361622225046840011907835671004704947767016613458301891561318029714351016012481309583866288472491239769813776978841785764693181622804797533665463949
g = gcd(ff - (a * f + b),f - (a * 31337 + b))
if isPrime(g):
print(n2s(g))
# b'corctf{1n_m4th3m4t1c5,_th3_3ucl1d14n_4lg0r1thm_1s_4n_3ff1c13nt_m3th0d_f0r_c0mput1ng_th3_GCD_0f_tw0_1nt3g3rs} <- this is flag adm'
luckyguess
p已知，LCG内置参数a、b未知。用户可以输入LCG的初始值x，x被放入生成器转r轮后输出，要求用户给出输出值，r未知。
求解方程
a
x
+
b
≡
x
(
m
o
d
p
)
ax+b equiv x space(mod space p)
ax+b≡x (mod p)，提交x，此时无论r为多少，LCG中始终只有一个值。
from pwn import *
import re
from libnum import invmod
p = remote("be.ax", 31800)
prime = 2**521 - 1
s = str(p.recv())
a,b = int(re.findall(r'd+',s)[0]),int(re.findall(r'd+',s)[1])
print(a,b)
payload = (invmod(a-1,prime)*(-b)) % prime
print(payload)
p.sendline(str(payload).encode())
print(p.recv())
p.sendline(str(payload).encode())
print(p.recv())
# corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}
exchanged
考点其实很基础，不过很好的解释了为什么plainLCG不能用来设计密钥交换算法。
LCG的p和内置参数a、b已知。定义：
f
(
s
)
≡
a
×
s
+
b
(
m
o
d
p
)
f
n
(
s
)
≡
f
(
f
(
f
(
.
.
.
f
(
f
(
s
)
)
.
.
.
)
)
)
⏟
n
次
(
m
o
d
p
)
f(s) equiv a times s+b space (mod space p) \ f^n(s) equiv underbrace{f(f(f(...f(f(s))...)))}_{n次} space (mod space p)
f(s)≡a×s+b (mod p)fn(s)≡n次
f(f(f(...f(f(s))...))) (mod p)
假设A与B要利用这个基础的LCG，共享密钥，二者商定一个基础的公共值s，满足s小于p即可。
此时A生成一个小于p的随机数
a
p
r
i
v
a_{priv}
apriv作为私钥，计算公钥
P
K
A
=
f
a
p
r
i
v
(
s
)
PK_A=f^{a_{priv}}(s)
PKA=fapriv(s)；B生成一个小于p的随机数
b
p
r
i
v
b_{priv}
bpriv作为私钥，计算公钥
P
K
B
=
f
b
p
r
i
v
(
s
)
PK_B=f^{b_{priv}}(s)
PKB=fbpriv(s)。A和B把公钥
P
K
A
PK_A
PKA和
P
K
B
PK_B
PKB公开至共享信道，随后A计算
f
a
p
r
i
v
(
P
K
B
)
f^{a_{priv}}(PK_B)
fapriv(PKB)，B计算
f
b
p
r
i
v
(
P
K
A
)
f^{b_{priv}}(PK_A)
fbpriv(PKA)，由于定义
f
f
f函数满足性质：
f
a
(
f
b
(
s
)
)
=
f
a
+
b
(
s
)
f^a(f^b(s))=f^{a+b}(s)
fa(fb(s))=fa+b(s)
故有：
f
a
p
r
i
v
(
P
K
B
)
=
f
a
p
r
i
v
(
f
b
p
r
i
v
(
s
)
)
=
f
a
p
r
i
v
+
b
p
r
i
v
(
s
)
=
f
b
p
r
i
v
(
P
K
A
)
f^{a_{priv}}(PK_B)=f^{a_{priv}}(f^{b_{priv}}(s))=f^{a_{priv}+b_{priv}}(s)=f^{b_{priv}}(PK_A)
fapriv(PKB)=fapriv(fbpriv(s))=fapriv+bpriv(s)=fbpriv(PKA)
此时二者完成密钥共享，
K
=
f
a
p
r
i
v
+
b
p
r
i
v
(
s
)
K=f^{a_{priv}+b_{priv}}(s)
K=fapriv+bpriv(s)。
由于
a
p
r
i
v
a_{priv}
apriv和
b
p
r
i
v
b_{priv}
bpriv都非常大，因此在CTF环境下无法采取暴力破解的手段计算二者的私钥，但是可以发现这个过程存在一个最大的问题：LCG采用的线性算法具有同构性。
f
n
(
s
)
≡
f
(
f
(
f
(
.
.
.
f
(
f
(
s
)
)
.
.
.
)
)
)
⏟
n
次
(
m
o
d
p
)
≡
a
(
.
.
.
a
(
a
(
a
s
+
b
)
+
b
)
+
b
.
.
.
)
+
b
(
m
o
d
p
)
≡
a
n
s
+
(
a
n
−
1
+
a
n
−
2
+
.
.
.
+
1
)
b
(
m
o
d
p
)
≡
a
′
s
+
b
′
(
m
o
d
p
)
f^n(s) equiv underbrace{f(f(f(...f(f(s))...)))}_{n次} space (mod space p) \ equiv a(...a(a(as+b)+b)+b...)+b space (mod space p)\ equiv a^ns +(a^{n-1}+a^{n-2}+...+1)b space (mod space p) \ equiv a's+b' space (mod space p)
fn(s)≡n次
f(f(f(...f(f(s))...))) (mod p)≡a(...a(a(as+b)+b)+b...)+b (mod p)≡ans+(an−1+an−2+...+1)b (mod p)≡a′s+b′ (mod p)
可以发现，迭代n次
f
f
f函数得到的结果仍可以写成
a
′
s
+
b
′
a's+b'
a′s+b′的形式，如果我们定义一个内置参数为
a
′
a'
a′、
b
′
b'
b′的LCG，及其相关的计算函数
f
′
f'
f′，则有：
f
′
(
s
)
≡
a
′
×
s
+
b
′
(
m
o
d
p
)
f
n
(
s
)
≡
f
′
(
s
)
(
m
o
d
p
)
f'(s) equiv a' times s+b' space (mod space p) \ f^n(s) equiv f'(s) space (mod space p)
f′(s)≡a′×s+b′ (mod p)fn(s)≡f′(s) (mod p)
其中
a
′
=
a
n
a'=a^n
a′=an，
b
′
=
(
a
n
−
1
+
a
n
−
2
+
.
.
.
+
1
)
b
=
(
a
−
1
)
−
1
(
a
n
−
1
)
b
b'=(a^{n-1}+a^{n-2}+...+1)b=(a-1)^{-1}(a^n-1)b
b′=(an−1+an−2+...+1)b=(a−1)−1(an−1)b。
从以上推导回到LCG密钥交换问题，可以发现：
f
a
p
r
i
v
(
s
)
≡
a
a
p
r
i
v
×
s
+
(
a
−
1
)
−
1
(
a
a
p
r
i
v
−
1
)
b
(
m
o
d
p
)
⇒
(
a
−
1
)
f
a
p
r
i
v
(
s
)
≡
(
a
−
1
)
×
a
a
p
r
i
v
×
s
+
(
a
a
p
r
i
v
−
1
)
b
(
m
o
d
p
)
⇒
[
(
a
−
1
)
s
+
b
]
×
a
a
p
r
i
v
≡
(
a
−
1
)
f
a
p
r
i
v
(
s
)
+
b
(
m
o
d
p
)
⇒
a
a
p
r
i
v
≡
[
(
a
−
1
)
s
+
b
]
−
1
[
(
a
−
1
)
f
a
p
r
i
v
(
s
)
+
b
]
(
m
o
d
p
)
f^{a_{priv}}(s) equiv a^{a_{priv}} times s + (a-1)^{-1}(a^{a_{priv}}-1)bspace (mod space p) \ Rightarrow (a-1)f^{a_{priv}}(s)equiv (a-1) times a^{a_{priv}} times s +(a^{a_{priv}}-1)bspace (mod space p) \ Rightarrow [(a-1)s+b] times a^{a_{priv}}equiv (a-1)f^{a_{priv}}(s)+bspace (mod space p) \ Rightarrow a^{a_{priv}}equiv[(a-1)s+b]^{-1}[(a-1)f^{a_{priv}}(s)+b]space (mod space p)
fapriv(s)≡aapriv×s+(a−1)−1(aapriv−1)b (mod p)⇒(a−1)fapriv(s)≡(a−1)×aapriv×s+(aapriv−1)b (mod p)⇒[(a−1)s+b]×aapriv≡(a−1)fapriv(s)+b (mod p)⇒aapriv≡[(a−1)s+b]−1[(a−1)fapriv(s)+b] (mod p)
同理可知：
a
b
p
r
i
v
≡
[
(
a
−
1
)
s
+
b
]
−
1
[
(
a
−
1
)
f
b
p
r
i
v
(
s
)
+
b
]
(
m
o
d
p
)
a^{b_{priv}}equiv[(a-1)s+b]^{-1}[(a-1)f^{b_{priv}}(s)+b]space (mod space p)
abpriv≡[(a−1)s+b]−1[(a−1)fbpriv(s)+b] (mod p)
此时可以破解共享密钥：
K
=
f
a
p
r
i
v
(
P
K
B
)
=
f
a
p
r
i
v
(
f
b
p
r
i
v
(
s
)
)
=
a
a
p
r
i
v
×
f
b
p
r
i
v
(
s
)
+
(
a
−
1
)
−
1
(
a
a
p
r
i
v
−
1
)
b
K=f^{a_{priv}}(PK_B)=f^{a_{priv}}(f^{b_{priv}}(s)) \ =a^{a_{priv}} times f^{b_{priv}}(s) + (a-1)^{-1}(a^{a_{priv}}-1)b
K=fapriv(PKB)=fapriv(fbpriv(s))=aapriv×fbpriv(s)+(a−1)−1(aapriv−1)b
或者：
K
=
f
b
p
r
i
v
(
P
K
A
)
=
f
b
p
r
i
v
(
f
a
p
r
i
v
(
s
)
)
=
a
b
p
r
i
v
×
f
a
p
r
i
v
(
s
)
+
(
a
−
1
)
−
1
(
a
b
p
r
i
v
−
1
)
b
K=f^{b_{priv}}(PK_A)=f^{b_{priv}}(f^{a_{priv}}(s)) \ =a^{b_{priv}} times f^{a_{priv}}(s) + (a-1)^{-1}(a^{b_{priv}}-1)b
K=fbpriv(PKA)=fbpriv(fapriv(s))=abpriv×fapriv(s)+(a−1)−1(abpriv−1)b
题中给出了p、a、b、s和
f
a
p
r
i
v
(
s
)
f^{a_{priv}}(s)
fapriv(s)、
f
b
p
r
i
v
(
s
)
f^{b_{priv}}(s)
fbpriv(s)，求解共享密钥。共享密钥被用作AES-CBC中的key加密flag，解密一下即可。
p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
a = 118090659823726532118457015460393501353551257181901234830868805299366725758012165845638977878322282762929021570278435511082796994178870962500440332899721398426189888618654464380851733007647761349698218193871563040337609238025971961729401986114391957513108804134147523112841191971447906617102015540889276702905
b = 57950149871006152434673020146375196555892205626959676251724410016184935825712508121123309360222777559827093965468965268147720027647842492655071706063669328135127202250040935414836416360350924218462798003878266563205893267635176851677889275076622582116735064397099811275094311855310291134721254402338711815917
def f(s):
return (a * s + b) % p
def mult(s, n):
for _ in range(n):
s = f(s)
return s
s = 35701581351111604654913348867007078339402691770410368133625030427202791057766853103510974089592411344065769957370802617378495161837442670157827768677411871042401500071366317439681461271483880858007469502453361706001973441902698612564888892738986839322028935932565866492285930239231621460094395437739108335763
A = 27055699502555282613679205402426727304359886337822675232856463708560598772666004663660052528328692282077165590259495090388216629240053397041429587052611133163886938471164829537589711598253115270161090086180001501227164925199272064309777701514693535680247097233110602308486009083412543129797852747444605837628
B = 132178320037112737009726468367471898242195923568158234871773607005424001152694338993978703689030147215843125095282272730052868843423659165019475476788785426513627877574198334376818205173785102362137159225281640301442638067549414775820844039938433118586793458501467811405967773962568614238426424346683176754273
m = (invmod((a-1) * s + b, p) * (B * (a-1) + b)) % p
k = (invmod((a-1) * s + b, p) * (A * (a-1) + b)) % p
shared1 = (m * A + invmod(a-1, p) * (m-1) * b) % p
shared2 = (k * B + invmod(a-1, p) * (k-1) * b) % p
assert shared1 == shared2
shared = 86382471144674987516192390676739968790606018844855369676663312319897424264589519056860582366433954661923689613455950996957073708730586503567240461427068073600946731416068482076340126294642483394238838801798961052802865121895198819944744990914204503217602305639165324158861726404756338767093146109002421799336
key = sha256(long_to_bytes(shared)).digest()[:16]
c = long_to_bytes(0x482eae28750eaba12f4f76091b099b01fdb64212f66caa6f366934c3b9929bad37997b3f9d071ce3c74d3e36acb26d6efc9caa2508ed023828583a236400d64e)
iv = long_to_bytes(0xe0364f9f55fc27fc46f3ab1dc9db48fa)
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
print(cipher.decrypt(c))
# b'corctf{th1s_lcg_3xch4ng3_1s_4_l1ttl3_1ns3cur3_f0r_n0w}nnnnnnnnnn'
hidE
这个题比赛时没搞出来。等大佬wp。。。
def encrypt(msg):
e = random.randint(1, n)
while math.gcd(e, phi) != 1:
e = random.randint(1, n)
pt = bytes_to_long(msg)
ct = pow(pt, e, n)
return binascii.hexlify(long_to_bytes(ct)).decode()
通过加密源码可以发现每次调用encrypt函数加密的时候都会新生成一个e，相当于e不可知。远程允许用户拿到加密的flag或者提请内容进行加密。
明显e不能直接解出来（离散对数难度）。
回顾代码发现系统设置了random的种子数：
random.seed(int(time.time()))
这句代码是在加密模块以外的。因此推测可以攻击系统时间，泄露seed后自行构造random.randint，这样便可以预言e。申请得到两个加密的flag然后共模就行。
然而获取系统时间失败了。。。telnetlib也不行。寄。
先贴上一个脚本，以后再看：
from pwn import *
import re
import random
from math import log,floor
from Crypto.Util.number import isPrime
def bit_to_list(t, n):
s = [0 for i in range(n)]
i = -1
while t != 0:
s[i] = t % 2
t >>= 1
i -= 1
return s
def fast_power(a, b, p):
if b == 0:
return 1
n = 1
if b != 0:
blist = bit_to_list(b,floor(log(b,2)+1))
n = 1
for i in range(len(blist)-1,-1,-1):
if blist[i] == 1:
n = ((a % p) * (n % p)) % p
a = ((a % p) ** 2) % p
return n
def euclidean_extended(e1, e2):
a1 = 0
a2 = 1
b1 = 1
b2 = 0
while e1 != 0 and e2 != 0:
if e1 < 0:
e1 = -e1
a1 = -a1
b1 = -b1
if e2 < 0:
e2 = -e2
a2 = -a2
b2 = -b2
if e1 >= e2:
s = e1 // e2
e1 = e1 - e2 * s
a1 = a1 - a2 * s
b1 = b1 - b2 * s
else:
s = e2 // e1
e2 = e2 - e1 * s
a2 = a2 - a1 * s
b2 = b2 - b1 * s
if e1 != 0:
e1 += e2
b1 += b2
a1 += a2
return b1,a1,e1
else:
e2 += e1
b2 += b1
a2 += a1
return b2,a2,e2
p = remote("be.ax", 31124)
random.seed(int(time.time()))
N = int(re.findall(r'd+',str(p.recv()))[0])
e1 = random.randint(1, N)
while not isPrime(e1):
e1 = random.randint(1, N)
e2 = random.randint(1, N)
while not isPrime(e1):
e2 = random.randint(1, N)
p.sendline('1'.encode())
s1 = str(p.recv())
c1 = ""
flag = 0
for i in s1:
if flag == 1:
c1 += i
if i == ':':
flag = 1
if i == 'n':
flag = 0
c1 = int('0x'+c1[1:-88],16)
p.sendline('1'.encode())
s2 = str(p.recv())
c2 = ""
flag = 0
for i in s2:
if flag == 1:
c2 += i
if i == ':':
flag = 1
if i == 'n':
flag = 0
c2 = int('0x'+c2[1:-88],16)
a1,b1,g = euclidean_extended(e1,e2)
if a1 < 0:
c1,b,g = euclidean_extended(c1,N)
a1 = -a1
if b1 < 0:
c2,b,g = euclidean_extended(c2,N)
b1 = -b1
m = fast_power(fast_power(c1,a1,N)*fast_power(c2,b1,N),1,N)
print(m)
更新：一个很神奇的做法
远程提供了功能，用户可以提交任意消息进行加密。直接提交0x02，利用2的幂次泄露e，获取多组执行CommonMod。
よっちんのブログ corCTF 2022 Writeup
HTML流量导出，发现文件夹下所有的文件名格式统一：
anticheat%3fx=8&y=14&event=mousemove
典型的鼠标流量，脚本遍历文件名提取坐标绘图：
import os
import re
from PIL import Image
filePath = 'D:\out\'
k = os.listdir(filePath)
point = []
for i in k:
point.append([int(j) for j in re.findall(r'd+', i)])
res = Image.new('RGB', (520, 68), 255)
k = 0
for i in range(520):
for j in range(68):
flag = 0
for m in point:
if i == m[1] and j == m[2]:
res.putpixel((i,j), (0,0,0))
k += 1
flag = 1
break
if flag == 0:
res.putpixel((i,j), (255,255,255))
res.save('out.png')
res.show()
# corctf{LILYXOX}
