2019看雪CTF总决赛第二题--南充茶坊WP
2019-12-08 14:36:03 Author: bbs.pediy.com(查看原文) 阅读量:185 收藏

试运行

拿到题目,果然如题目描述一样,有两个可执行程序。主程序的图标很眼熟有没有?
直接运行,起来一个控制台,控制台的窗口标题似乎出卖了自己,看路径及目录名,应该是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.pycgeneral.pycCM和内存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到作者的意图,预期的解题方法应该也不是这样,花费了大量的时间和算力,队友帮我了很多。

[公告]安全测试和项目外包请将项目需求发到看雪企服平台:https://qifu.kanxue.com


文章来源: https://bbs.pediy.com/thread-256221.htm
如有侵权请联系:admin#unsafe.sh