2019看雪CTF总决赛第二题--南充茶坊WP

试运行

拿到题目，果然如题目描述一样，有两个可执行程序。主程序的图标很眼熟有没有？
直接运行，起来一个控制台，控制台的窗口标题似乎出卖了自己，看路径及目录名，应该是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，准备解包。结果出错了，认不出打包数据。

[*] Processing cm.exe
[*] Error : Unsupported pyinstaller version or not a 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 CMpub import pub_n_list, pub_e_list
from general import valid_serial, valid_username, get_enc_seq, enc0
from Crypto.Util.number import bytes_to_long
from os import system

def check(serial, seq):
    now = serial
    for j in 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 hashlib import sha256

def valid_serial(serial):
    assert type(serial) == str
    assert len(serial) > 0
    if not '0' != serial[0]:
        assert 1 == len(serial)
        for c in 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 c in 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 i in 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

校验流程为：

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

从以上步骤可以看出，关键在第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 idx1 in l[:-1]:
    tmp = l.index(idx1)
    for idx2 in 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 idx in [3,4,5,6,9]:
    n = pub_n_list[idx]
    n1,flag= iroot(n,2)
    for i in 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 idx in [3,5]:
    c = 1234
    c = pow(c,pub_e_list[idx],pub_n_list[idx])
    for i in 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 j in 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 i in 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

似乎用户名计算出来的数字序列中5比较多，计算稍需要点时间：

虽然最后做出来了，但似乎没有完全get到作者的意图，预期的解题方法应该也不是这样，花费了大量的时间和算力，队友帮我了很多。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课