STARCTF2022

2022-05-17

参加了*ctf的个人认证，太懒了一直没写blog，这里记录当时答的题顺便复现正赛题目。

Grey(misc)

签到题，flag第一部分用stegsolve在Alpha plane3通道看到，第二部分则是在图片的hex数据段最后，第三部分则需要把图片改高一点（crc爆破宽高）再用stegsolve查看。

连起来就是*CTF{Catch_m3_1F_y0u_cAn}

oh-my-grafana(web)

百度搜索 grafana cve 找到Grafana8.x 任意文件读取；github上面找到一个poc：https://github.com/rnsss/CVE-2021-43798-poc 脚本克隆到本地。

尝试直接打，发现没能成功，貌似是因为文件内容太大poc接受不了那么多数据。于是直接用bp发包来打，在grafana.ini中有用户名和密码。登入之后发现Explore可以执行sql语句，先查询得到表名：

1 2	select 11,group_concat(table_name)from information_schema.tables select 11,22,(select group_concat(table_name) from information_schema.tables where table_schema=database()

最后查表得到flag。

babyRSA(crypto)

比赛的时候找到一道类似的题目。但发现不太一样，那题数据特殊，p和q刚好bit-inverse，可以列方程解，这题并不能用相同的方法。

how to do it? 观察会发现，即使p和q之间没有比特相反那么强的关系，异或的关系也不弱(因为我们知道message)。那么可以通过遍历p和q每一位的值，通过异或关系排除一些情况，得到真实的p和q：

1.当p第i位取1的时候，q对应位一定为m_i^1

2.当p第i位取0的时候，q对应位一定为m_i

3.每一轮取值以后都进行现有低位的乘法并把积与n的对应低位比较，若相等，则符合

4.1024轮以后得到p，q的真实值

5.这样的算法大大减少了遍历的可能性，时间复杂度可以接受

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from Crypto.Util.number import *
import sys
sys.setrecursionlimit(2048) # 限制递归深度限制防止崩溃
c=0x45875b297ed0fcddbdd85c9c889bd3d6653dd1f1cbe50279935d398bce4ca87157cc1c14c3a44e81266308158d823570d8656edaba84131a33087ba3a62cb7b755f8d92afb6035b8ca1fba457e2b9fed0b83ceaeb87717f8833d46dd49814d3ca0a4030584aa5d203b4d8572385cba79cee7ba24bd4b4633e9578bbeac3a98febc0ec615e645a26f12cbce54c73e30af85cfd6f95014ba669ab6ac8377d527ed31d7c54cebf928f0bc073d04a99ef21f194fc59e34d5127d31014f8c5c304446de80ef72e187b57247208438c7a405a12cde573f1413105f61c6108a19ce652efbbdf1396c4fda121ea764ee782bcf420decfdfcbff473be2cad6ec0c78eabc4
n=0x8b5ad91687dde91ef2b06cbe059c43a1523c809f57cd3b868d7f9cb2b8af2ed66b0ceaedbc0f86abb9ca8bc6b4b5ba2a4cd8528a420db8ec2a0cb0d32528959b72575a58a76a47100ed7aa8cf61df4e587c9cf3d914115c0e7feee4c2f993e39962ea31d25e9dd9627bdc14c7526db0e1d2851e68974ad1101794808e187877f2d3e536f764b624312af1d841c7dcbe74c48cc10ccd9659ab968d9e566f222807ebb9e2b9325e2d9af987c9452d2c61c921efcc799378b9cfc524317ecb7e20fa9e37868a0f2670c6022780ea97b156551b86c6bea85d3ea71e34a13935ef120a1d96d88a7aad5501f5cd6467b4f6fdddd15d326aaa35ea17d7e409f9f864f5d

message='''For the win win win!
For the win win win!
信じててね 大丈夫
あくあ色に染めるよ
キミと歩くこの未来を'''
m=bytes_to_long(bytes(message,encoding="utf-8"))
p=0
q=0
# 遍历每一位
def backtrace(i,pi,qi):
    # 满足p位数为1024时，递归退出
    global p,q
    if i==1024:
        if n%pi==0:
            p=pi
            q=qi
            print(p,q)
        return 
    pt=pi+(1<<i)
    qt=qi+((m&(1<<i))^^(1<<i))
    if (pt*qt)%(1<<(i+1))==n%(1<<(i+1)):
        backtrace(i+1,pt,qt)
    pt=pi
    qt=qi+(m&(1<<i))
    if (pt*qt)%(1<<(i+1))==n%(1<<(i+1)):
        backtrace(i+1,pt,qt)

var('x,y')
for p0,q0 in solve_mod(x*y==n,2048): # 模2就得到1位，mod2048则得到前11位
    backtrace(10,int(p0),int(q0))
    if p!=0:
    	break
e=65537
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
flag=long_to_bytes(int(m)).decode()
print(flag)

# *CTF{Ship_of_the_new_era_seats_no_man_of_the_past}

ezRSA(crypto)

思路：对N开方得到p的高位，异或关系得到p中间几位，coppersmith得到p的低位。

q的比特如图所示：

所以对n开方是可以获得p和q的最高124位。

爆破中间位数之前先将p的低900位全设置为1，q的低900位全设置为0，因为p和q的中间bit是相反的。

这里类似于均值不等式，p和q差距越大，乘积越小，所以初始的时候是最小的。所以从高位开始，每次把p的某一位变为0，q的对应位变为1，p和q的乘积是在变大，只要还小于n，就该继续异或赋值变换。而由于现在的低300位p全为1q全为0，不是准确值，经过爆破以后p和q中间部分比特的尾端部分（大概450-300位这一段，具体是多少可以在p高位攻击的时候多次尝试）也是不准确的，因此在最后进行p高位攻击的时候，x比特应该取450左右。 p和q中间有一部分比特值固定不受低300位影响，因为低300位最多只能影响到n的300+1024位，n的某一部分高位和pq的低300位无关。这部分由p和q的高位决定，所以是固定值。

最后p已知高位攻击解rsa即可。

from Crypto.Util.number import *
n=0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
c=0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1

p = (1<<900)-(1<<300)
q = 1<<300-1
PR.<x> = PolynomialRing(Zmod(n))
pm=int(sqrt(n))>>900 # p的高位 124位
p = (1<<900)-1
q = 1<<300-1
p+=pm*(1<<900) # 低位补0再加上(1<<900)-1，现在低位全是1
q+=pm*(1<<900) 
#in the rest place, '1' either belong to p or q
for i in range(899, 301, -1):
    cur = 1<<i
    if (p^^cur) * (q^^cur) < n: 
        p ^^= cur
        q ^^= cur
        
f=x+p # 已知p高位攻击
roots=f.small_roots(X=2**450,beta=0.4) 
p=p+roots[0]
q=n//int(p)
fn=(p-1)*(q-1)
d=pow(65537,-1,fn)
print(long_to_bytes(pow(c,d,n)))
# *CTF{St.Diana_pls_take_me_with_you!}