[推荐]2019 KCTF 总决赛 | 第二题《南充茶坊》点评及解题思路

2019-12-11 18:51 3290

[推荐]2019 KCTF 总决赛 | 第二题《南充茶坊》点评及解题思路

Editor

2019-12-11 18:51

3290

第二道题《南充茶坊》历时3天，已于5号中午12点关闭攻击通道。共有2548人围观，最终只有4支团队攻破成功。7HxzZ战队率先攻破此题，一共用时约28小时，可见此题难度很大，Acehub战队和大众代表队的readyu攻势迅猛，金左手战队也迎头赶上，与前几位选手相差不大。

1、题目简介

＂鸡米花系统第一级开启＂我一睁眼，只见一片塞外风光，往来行人车马络绎，似是个边疆小镇。起身差点被自己绊倒，才发现竟已换上了缎袍，腰间还有一把折扇（＂唰＂），我成了……古代文人……？＂阁下真是好运气，初次来到就碰上这么个简单关卡。边塞风光可是壮美，只是风沙些许大，阁下不妨先去茶馆避避吧。＂视线扫过四周，我终于看清身后兀然竟立着一座茶馆，风裹着大漠的气息，将门外的旌旗吹得漫卷飞扬，旗上四个大字＂南充茶坊＂。一头雾水，进去探探再说。将将落座，却见一六七岁样貌孩童嬉笑着向我跑来。＂大哥哥，刚才有个仙女姐姐来，让我把谜题交给一个摇扇子的大哥哥，应该就是大哥哥你啦！＂又有仙女儿，又有谜题，甚好甚好。＂不过，大哥哥要陪我玩成语接龙，我才把谜题给你。＂成语接龙……？也行也行，为了拿到仙女姐姐的谜题，哥哥就陪你玩儿会。＂既然在我们家的茶馆，就以'茶'字开头吧。大哥哥先来。＂茶余饭后→后来居上→上善若水→水落石出→出其不意→意气用事→事在人为→为所欲为//众所周知，为所欲为是成语接龙自动机的接受状态，那我换一个事不关己→己所不欲→欲加之罪→罪孽深重→重义轻利→利诱威逼→逼上梁山→山穷水尽→尽力而为→为所欲为//emmmmmm，那我再换一个尽心尽力→力大无穷→穷兵黩武→武偃文修→修身养性→性命攸关→关怀备至→至高无上→上下一心→心猿意马→马首欲东→东遮西掩→掩口卢胡→胡作非为→为所欲为//怎么又回来了，重来重来东门黄犬→犬牙差互→互通有无→无可奈何→何乐不为→为所欲为//……事出有因→因小失大→大智若愚→愚公移山→山穷水尽→尽力而为→为所欲为//……显然，这个小朋友是'有备而来'，没准仙女姐姐正躲在哪里看着我们偷笑呢。怎样才能挽回局面呢……？

攻破此题的战队排名一览：

这道题攻破人数较少，可见出题者设计巧妙，接下来我们一起来看一下这道题的点评和详细解析吧。

2、看雪评委crownless点评

这道题考查的范围较为广泛，需要参赛者对密码学、PE文件结构、python反编译等都有一定程度的理解，题目质量较高。因此，攻破此题的参赛者数量也不多。此外，题目writeup的质量较高，值得一看。

3、出题团队简介

本题出题战队中娅之戒：

4th拜各位大佬！

本次2019KCTF决赛的中娅之戒由4名队员组成：

iiiiiiiiiiii：一个小肥宅，晚上不睡觉，白天起不来

xh1998：国家一级彩蛋制造专家

leafpad：仍旧是萌新

Venessa：深深觉得还是自然科学有意思的密码学方向在读研(小)究(姑)生(娘)

# 我们的征程是吸尘器和云台

# 两只黄鹂鸣翠柳一行白鹭上青天

4、设计思路

加密序列根据用户名的SHA256值确定，使用RSA加密。一共有10组RSA加密。给出了10组公钥：n、e。攻破这些RSA即可。

0x0：n由4个192bit的n拼接而成，e同理。分解每个n即可。

0x1：n存在小因子，分解即可。

0x2：n存在因子p使得p+1不含大素因子。

0x3：n存在因子p使得p-1不含大素因子。

0x4：n的因子p、q过于接近。

0x5：e的阶较小，对密文多次加密即可得到明文。

0x6：私钥d过小。

0x7、0x8：两个n存在公因子。

0x9：https://en.wikipedia.org/wiki/RSA_numbers#RSA-768（更详细的设计思路正在加急更新中，请大家持续关注）

5、解题思路

本题解题思路由Acehub战队的poyoten提供：

试运行

拿到题目，果然如题目描述一样，有两个可执行程序。主程序的图标很眼熟有没有？直接运行，起来一个控制台，控制台的窗口标题似乎出卖了自己，看路径及目录名，应该是RAR自解压格式，用winrar打开程序文件试试，果然如此。取回自解压的两个文件。

初步分析

本来原主程序的图标明显就是pyinstaller打包的默认图标。自解压后的CM.exe文件没有图标了，还带了个aplib.dll动态库文件。大概静态分析了下（感觉时间紧张，先大概看看，找重点），CM.exe实际上就是利用aplib.dll这个压缩引擎做了一个套子。

v3 = fopen("CM.exe","rb");
v4 =calloc(0x28131ui64,1ui64);
fseek(v3,0x8000,0);
fread(v4,1ui64,0x28131ui64, v3);
LODWORD(v3) = aPsafe_get_orig_size(v4);
v5 =calloc((unsigned int)v3,1ui64);
aPsafe_depack(v4,0x28131i64, v5, (unsigned int)v3);

实际的pe文件在偏移0x8000处，压缩长度为0x28131，解压长度为0x42c00。

动态把此pe从内存中dump出来，果然又出现了熟悉的图标。看了下原CM.exe文件偏移0x42c00处，果然上面是00填充，后面就是数据了。把dump出来的0x42c00大小的pe文件覆盖原CM.exe的前0x42c00字节，运行，正常。接着又大概静态看了下新的CM.exe文件，确认是pyinstaller打包的（前面的aplib压缩引擎是新版pyinstaller自带还是后加的就不知道了）。解包

直接拿出pyinstxtractor，准备解包。结果出错了，认不出打包数据。

[*] Processingcm.exe
[*] Error : Unsupported pyinstallerversion or nota pyinstaller archive

始终感觉时间比较紧，没多想直接运行，内存搜索关键字，定位到主脚本的pyc所在，dump出来（前后多dump了点），掐头去尾，加上pyc头反编得到源文件CM.py，发现还需要CMpub和general模块。但是这两个的pyc在内存中没有定位到。最终还是回到pyinstxtractor工具上，看了下源码：

def checkFile(self):
        print('[*] Processing {0}'.format(self.filePath))
        # Check if it is a 2.0 archive
        self.fPtr.seek(self.fileSize -self.PYINST20_COOKIE_SIZE, os.SEEK_SET)
        magicFromFile =self.fPtr.read(len(self.MAGIC))
 
        if magicFromFile ==self.MAGIC:
            self.pyinstVer =20     # pyinstaller 2.0
            print('[*] Pyinstaller version: 2.0')
            return True
 
        # Check for pyinstaller 2.1+ before bailing out
        self.fPtr.seek(self.fileSize -self.PYINST21_COOKIE_SIZE, os.SEEK_SET)
        magicFromFile =self.fPtr.read(len(self.MAGIC))
 
        if magicFromFile ==self.MAGIC:
            print('[*] Pyinstaller version: 2.1+')
            self.pyinstVer =21     # pyinstaller 2.1+
            return True
 
        print('[*] Error : Unsupported pyinstaller version or not a pyinstaller archive')
        return False

在检查文件的magic时出错了，针对新旧版本打包数据，magic相对于文件尾的偏移不一样，于是检查CM.exe的文件尾数据，发现magic是存在且正确的，只不过文件尾多了4字节的数据DEADCODE（hex），所以magic有偏移就有问题了。删除多余字节，用pyinstxtractor再次解包：

py代码反编及分析

主脚本在解包的根目录，文件名为CM，另外两个在PYZ-00.pyz_extracted目录下，文件名分别为CMpub.pyc和general.pyc。CM和内存dump出的一样，需要加16字节的文件头，而另两个pyc文件文件头需要增加4字节。改好后直接反编译成功，代码如下，CMpub.py只有RSA的公钥数据，就不贴了。

#CM.py
from CMpubimport pub_n_list, pub_e_list
from generalimport valid_serial, valid_username, get_enc_seq, enc0
from Crypto.Util.numberimport bytes_to_long
from osimport system
 
def check(serial, seq):
    now = serial
    for jin range(len(seq)):
        i = seq[j]
        n = pub_n_list[i]
        e = pub_e_list[i]
        if now > pub_n_list[i]:
            return False
        if i >0:
            now = pow(now, e, n)
        else:
            now = enc0(now, e, n)
            if 0 == now:
                return False
 
    return now
 
 
def main():
    username0 = input('Please input Username:\t')
    serial0 = input('Please input Serial:\t')
    try:
        valid_serial(serial0)
        valid_username(username0)
    except:
        print('\nInvalid Input\n')
        return
    else:
        serial = int(serial0,16)
        username = username0.encode('utf-8')
        seq = get_enc_seq(username)
        username = bytes_to_long(username)
        check_value = check(serial, seq)
        if check_value == username:
            print('\nCorrect!\n')
        else:
            print('\nOops! The encrypted Serial is not "' + username0 +'".\n')
        system('pause')
 
 
if __name__ =='__main__':
    main()

#general.py
from hashlibimport sha256
 
def valid_serial(serial):
    assert type(serial) == str
    assert len(serial) >0
    if not '0' != serial[0]:
        assert 1 == len(serial)
        for cin serial:
            if not ord('0') <= ord(c) <= ord('9'):
                if not ord('A') <= ord(c) <= ord('F'):
                    raise AssertionError
 
        return serial
 
 
def valid_username(username):
    assert type(username) == str
    assert len(username) >0
    for cin username:
        assert ord(c) >0
 
    return username
 
 
def get_enc_seq(username):
    h = sha256()
    h.update(username)
    hash_value = int(h.hexdigest(),16)
    T =9
    S =10
    stat = [0] * (T +1)
    seq = [0]
    n = hash_value
    while n >0:
        if S * T > len(seq):
            now = n % T +1
            if stat[now] < S:
                seq.append(now)
                stat[now] +=1
            n //= T
 
    return seq
 
 
def enc0(m, e, n):
    nbit =192
    T = (n.bit_length() -1) // nbit +1
    ans =0
    for iin range(T -1,-1,-1):
 
        def xxx(x, t):
            return x >> t * nbit & (1 << nbit) -1
 
        now_n = xxx(n, i)
        now_e = xxx(e, i)
        now_m = xxx(m, i)
        if now_m >= now_n:
            return 0
        ans = (ans << nbit) + pow(now_m, now_e, now_n)
 
    return ans

校验流程为：

检查用户名及序列号格式
用户名编码成0开头的其余皆为1-9的数字序列
通过数字序列和序列号计算对应的用户名
利用计算出的用户名校验输入用户名

从以上步骤可以看出，关键在第3步，第2步的编码无需关心。第3步中的计算全是rsa加密，如果求出私钥，那整个过程就可逆，可由预期用户名求出对应的序列号。0-9的数字序列决定了rsa的密钥选取和rsa加密过程。0-9分别对应一组公钥，除此，在计算方法上，0对应的是大数按192bits分组（m,e,n都拆成192bits）进行rsa加密，1-9对应的是正常的rsa加密。9层计算

看了下n全是768bits，e也都比较大。768bits以现在的算力是可以分解的，但是时间上可能有点长何况去了第0组，还有1-9组。首先想到上factordb上试试，然而当天数据库维护。于上是yafu，秒出1、2组（相对而言）：

然后就跑不动了。开始找各种分解攻击方法。分解列表如下：特殊分解算法：

试除法(Trial division)
轮式因子分解法(Wheel factorization)
Pollard's rho算法(Pollard's rho algorithm)
代数群因子分解算法(Algebraic-group factorisation algorithms)，包括：
Pollard's p-1算法(Pollard'sp−1 algorithm)
Williams' p+1算法(Williams'p+1 algorithm)
Lenstra椭圆曲线因子分解法(Lenstra elliptic curve factorization)
费尔马因子分解法(Fermat's factorization method)
欧拉因子分解法(Euler's factorization method)
特殊数域筛选法(Special number field sieve, SNFS)

一般用途算法：

Dixon's算法(Dixon's algorithm)
连分数因子分解法(Continued fraction factorization, CFRAC)
二次筛选法(Quadratic sieve)
自然筛选法(Rational sieve)
普通数域筛选法(General number field sieve, GNFS)
二次剩余因子分解法(Shanks' square forms factorization, SQUFOF)

除此之外，还有些攻击手段，如：

Wiener’s attack
模数公约数

等。上面所说的大部分方法在yafu、msieve、ggnfs中都用到了，这三个中似乎也有些交叉。一边软件跑，一边手动写脚本试，看着答案在不同方法中一点一点出现，感觉是不是作者是考察rsa攻击的各知识点，只是有些是用软件跑出来的，不知道考察的是什么。第7、8组n存在公约数。大概代码如下：

def de_cofactor():
  l = [3,4,5,6,7,8,9]
  for idx1in l[:-1]:
    tmp = l.index(idx1)
    for idx2in l[tmp+1:]:
      n1 = pub_n_list[idx1]
      n2 = pub_n_list[idx2]
      fa = gcd(n1,n2)
      if fa !=1:
        print('{}-{}:{}'.format(idx1,idx2,fa))
        break

第4组在Fermat's factorization method中出了，后来在研究各种工具过程中发现此方法在yafu中就有集成（针对第4组n真正是秒出），大概代码如下，出了第4组我就停了，计算时间太长：

def de_fmt():
  for idxin [3,4,5,6,9]:
    n = pub_n_list[idx]
    n1,flag= iroot(n,2)
    for iin range(1,100000000):#4：30766579
      d = (n1+i)**2 - n
      d1,d1_flag = iroot(d,2)
      if d1_flag:
        print('{}:{} * {}'.format(idx,n1+i-d1,n1+i+d1))
        break

第二天在factordb上查到第9组分解结果（这是作者传上去的？）。Yafu出了第6组。后面就不见动静了。一边用软件重复跑，一边在研究其它的攻击手段。想到题目一再地说到成语接龙的自动机，抱着试一试的想法，跑了如下代码出了第5组，不能分解n，得不到d，但是能反解，想到了以前的一个题。。。：


def de_nenc():
  for idxin [3,5]:
    c =1234
    c = pow(c,pub_e_list[idx],pub_n_list[idx])
    for iin range(1,3000):#5：972
      c = pow(c,pub_e_list[idx],pub_n_list[idx])
      if c ==1234:
        print(idx,i)
        break

第3组通过P+1方法跑出来了：

最后的9层结果是：

--------------------------------1 yafu
3012613441
408348887278831461892610983390456945715612189153595698014201723503582993177671598068402822885301113712860820610804438839912419021850712894809826330539771179969086301239790288951959814006579380835620367785931463468740342519
--------------------------------2 yafu
33432251606513919330224622231317366537583494828490610118526091564149071313914670507018535045422242143860852944567717
36796059015915981995743432427927902530578158826788662547913509800095517347118062478922356654842254755916234587213077
--------------------------------3 msieve
35649202521608097930406469243867007880953508969230221480710213863570107942900924156757677983779306674419762868555881
34508357350889186927005771176009938286558270433215942821530479444470024241863567490529149148811494601012847563892119
--------------------------------4 root
35073848198058968264749790689745197012385911613318747771531468291963621262770461817935405298684967674641247961569207
35073848198058968264749790689745197012385911613318747864444430571453140176920442860760331340059929469925220710756489
--------------------------------5 mutli enc 927
 
--------------------------------6 yafu
26153324138194530872309557862464074525306735281010877795840958405693838446634362256045094682633541743845611502925341
47037312003475104493787837223043052957997925611039410248119470723357078273788416725476266555402464778755414193496517
--------------------------------7 gcd with 8
31550999035553713541658090861648847436644679578302163888858659624252927748982782365539915958668921514993162014394013
38990070212574870147996976234485159783294770114760127229326637585796111190341078784636949590143174262955343019982189
--------------------------------8 gcd with 7
31550999035553713541658090861648847436644679578302163888858659624252927748982782365539915958668921514993162014394013
38990721481148651230245403302870059427845712033679000902896256935166030973974325392836914596772977488693063112507763
 
--------------------------------9 factordb
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

计算序列号

基本全出来了，序列号就好计算了，直接在原代码的基础上改了，有点乱，把有改动的部分贴出来。

d_list = [0,
      1229061379053482744823152709690434888605435342198642793057361495153090878523561729157374272032362247153476832905266577597936263875922635915871109425948662301015976854125739243408750974498511602088546684816889116185016023460221241669,
      777757116197429014363243483536399809327489478672765799132008796613164652485176625704586327714092043960999487185568710834915265226900792279774759093092549483626423808502139519027474793822444064402879491357824424416255246538629615833,
      823517544270505260875748293850542665969704501523967290816451493771583601768953397655610971102989198539746963950912153425409736040224095605717482218948794082459357645210952999432155985335398508720958815348576453854403675948095665769,
      201419093613711761798540120588879041236840801068737686325195769604622639638393093247553615834885873886104026065263583851481439063609372020322699902282368593094548575688163522138303256348801329176798576662806247524508598547117027909,
      0,
      922636550562204599680939922372659456090989853033213781402035071733018496656291847983487357218691366381484789513851952285401356211108779700672241308549478980097499945532484886375918716118514969665502334756552044884230174523807259329,
      627567627354326605515830278366021138159090868181225778581524414114680017539982571880336309158282300554534438008003322761037932916796881232969829716072515736525821134512405811777096389132413642826921797756179543381108933388795804769,
      87763698610259057934268676955169084425464093902524300758830437447338976666426976224860384022223934601405128988601223084334832120115000652985202766336425151725676233383146800117094745887838499800523801384784235875984207816521259103,
      476133969086427941368462698171675198835788633664060460402567958612344234273279077792246479357026462298849835811290909092037603283477920353500979549470973082158764663458247740861805650589884280458476962517272738918503674157481390819]
 
 
def main(): 
    username0 = input('Please input Username:\t')
# serial0 = input('Please input Serial:\t')
    try:
# valid_serial(serial0)
        valid_username(username0)
    except:
        print('\nInvalid Input\n')
        return
    else:
# serial = int(serial0, 16)
        username = username0.encode('utf-8')
        seq = get_enc_seq(username)
        username = bytes_to_long(username)
        serial = gen_code(username,seq)
        check_value = check(serial, seq)
        if check_value == username:
            print('\nCorrect!\n')
            print('Username:'+username0)
            print('Serial:'+long_to_bytes(serial).hex().upper())
        else:
            print('\nOops! The encrypted Serial is not "' + username0 +'".\n')
        system('pause')
 
 
def gen_code(name,seq):
    now = name
    for jin range(len(seq)-1,-1,-1):
        i = seq[j]
        n = pub_n_list[i]
        d = d_list[i]
        e = pub_e_list[i]
        if now > pub_n_list[i]:
            return False
        if i ==5:
            for _in range(972):
                now = pow(now, e, n)
        elif i >0:
            now = pow(now, d, n)
        else:
            now = dec0(now, e, n)
    return now
 
def dec0(m, e, n):
    nbit =192
    T = (n.bit_length() -1) // nbit +1
    ans =0
    now_d = [3278088227273880484685188900446423165326324359156241482897,
              5595268830569065289149075246423557309146176813871482913465,
              5168422726700129702446055556002687483861807983023239862033,
              935387432279493795970516178982877288303534264234974679937,
              ]
    now_n = [6277052177355867862708971469565390229110991711310599757597,
              6277031389885428580574088212602983156224270664268963309877,
              6277087998938792861042405062580257456598525084583043892593,
              4973828634074084070222279013150769733596223651485114564273,
              ]
    for iin range(T -1,-1,-1):
        def xxx(x, t):
            return x >> t * nbit & (1 << nbit) -1
        now_m = xxx(m, i)
        tmp = pow(now_m, now_d[i], now_n[i])
        ans = (ans << nbit) + tmp
    return ans