Hackersgame 2019 的一些失败尝试及复现

概述

在之前比赛时尝试的基础上，参考官方题解进行复现

（√）天书残篇

Try

三种字符，统计结果:

1
2
3

20 00100000 : 2100
09 00001001 : 1353
0a 00001010 : 646

各种尝试无果（因为以为是密码学的题，方向完全错了）
没想到跟去年一样，又是一种语言

Solution

使用在线反编译器，单步调试分析
首先把Please input your flag:push入栈，然后读取输入
随便输入一个值，进行一系列操作后打印I think your flag is incorrect!
该字符在label_6入栈，所以回溯即可找到判断代码

label_4:
push 2
add
push 127
sub
jz label_5
jmp label_6

127-2=125, 对应flag的最后一个字符}，dump出ascii码，加2后转换，最后倒序即可

（√）无限猴子定理

Try

发现有一些字符不会被随机到

1 2	nolist = [3114, 6563, 10012, 13461, 16910, 20359, 23808, 27257, 30706, 34155, 37604, 41053, 44502, 47951, 51400, 54849, 58298, 61747, 65196, 65531, 65532, 65533, 65534] "+a+8tGa0edrn++eLArC"

各种拼接，提交无果
没想到是直接传入进行取值 = =

Solution

修改代码为

1	i = iter(random_iter(3114))

输出flag{Generat0r+A+8ad+LC}
根据条件：

flag 一定代表一串有意义的英文单词序列，但本题完全不需要任何程度的基于机器的自然语言识别。
和本次比赛的其他 flag 类似，本题的对应 flag 中可能有英文字母被替换混淆。
flag 代表的第一个英文单词既不会是名词，也不会是形容词。

所以为
flag{A+8ad+LC+Generat0r}
PS: 个人拼接出了一个A+CLear+Garden+80t
感觉还挺正常的，不过含义跟题目无关 = =

（√）失落的圣物

Try

分析完kvm执行流程之后，由于当时没有安装虚拟环境，就暂时搁置了
没有直接使用IDA分析系统镜像，不然应该能做出来

Solution

run_long_mode中把系统镜像复制到内存中，然后进行装载
在此处下断可以分析binary_guest64_img_start（按C强制转换为函数）
首先加载了一些数据，再调用sub_5569F1E0215B函数进行解密，观察得知算法是XXTEA算法（根据常数0x9E3779B9 0x61C88647以及6 + 52 / n）
dump出数据解密即可

（X）宇宙终极问题

Try

没搜到分解整数的网页，GG

Solution

Everything

分解成平方和
 分解成立方和

（X）不同寻常的Python考试

Try

基本考察python的内建函数和各种数据类型之间的转换，
对python不是很熟，一半都没做出来….
可在github搜索wtf moments in python参考

Solution

to be added…

（X）无法利用的漏洞

Try

IDA打开，发现存在后门函数，所以关键是要调整EIP到这里

unsigned __int64 sub_96B()
{
  char buf; // [rsp+0h] [rbp-10h]
  char v2; // [rsp+7h] [rbp-9h]
  unsigned __int64 v3; // [rsp+8h] [rbp-8h]

  v3 = __readfsqword(0x28u);
  puts("that's impossible!");
  read(0, &buf, 7uLL);
  v2 = 0;
  system(&buf);
  return __readfsqword(0x28u) ^ v3;
}

checksec查询，发现保护全开，所以不能简单栈溢出，需要用到一些高级操作，第一次做pwn，没时间研究了

Solution

to be added…

（X）驴啃计算器

Try

可以使用meet in middle算法进行搜索，没写代码实现

Solution

to be added…

（X）十次方根

Try

「只要你的输入 n 代入后满足约束条件，flag 就是你的。」

x = 130095999494467643631574289251374479743427759332282644620931023932981730612064829262332840253969261363881910701276769455728130421459878658660627330362688856751252524519341435317968272275310598639991033512763704530123231772642623291899534454658707761230166809620539187116816778418242273580873637781313957589597
y = 116513882455567447431772208851676203256471727099349255694179213039239989833646726805040167642952589899809273716764673737423792812107737304956679717082391151505476360762847773608327055926832394948293052633869637754201186227370594688119795413400655007893009882742908697688490841023621108562593724732469462968731
z = 88688615046438957657148589794574470139777919686383514327296565433247300792803913489977671293854830459385807133302995575774658605472491904258624914486448276269854207404533062581134557448023142028865220726281791025833570337140263511960407206818858439353134327592503945131371190285416230131136007578355799517986306208039490339159501009668785839201465041101739825050371023956782364610889969860432267781626941824596468923354157981771773589236462813563647577651117020694251283103175874783965004467136515096081442018965974870665038880840823708377340101510978112755669470752689525778937276250835072011344062132449232775717960070624563850487919381138228636278647776184490240264110748648486121139328569423969642059474027527737521891542567351630545570488901368570734520954996585774666946913854038917494322793749823245652065062604226133920469926888309742466030087045251385865707151307850662127591419171619721200858496299127088429333831383287417361021420824398501423875648199373623572614151830871182111045650469239575676312393555191890749537174702485617397506191658938798937462708198240714491454507874141432982611857838173469612147092460359775924447976521509874765598726655964369735759375793871985156532139719500175158914354647101621378769238233
if __name__ == "__main__":
    n = int(input())
    if 0 < n < z and n ** 10 % (x * y * y * y) == z:
        flag = bytes.fromhex(hex(n)[2:]).decode()
        if flag.startswith("flag"):
            print("Flag:", flag[:32])
            exit()
    print("Wrong!")

可以得出约束条件:

0 < n < z
pow(n,10,(x*y*y*y)) == z
flag = bytes.fromhex(hex(n)[2:]).decode()#每一位字符都是可打印的,即0x20-0x7f
flag.startswith("flag") # 即转化成十六进制以666c6167开头

尝试使用z3约束器求解，跑不出结果，于是继续分析
注意到x和y都是309位的数字，猜测是使用random_prime函数生成的，使用sympy进行素性测试，发现确实是素数，于是想到rsa算法

加密明文m：c = pow(m, e, N)，得到的c即为密文
解密密文c：m = pow(c, d, N)，得到的m即为明文

已知约束pow(n,10,(x*y*y*y)) == z，也就是

1	e=10, N=(x * y * y * y), c = z

所以需要把d求出来，才能解密出flag
参考rsa中d的生成算法：

计算φ = (p-1) * (q-1) 即N的欧拉函数，然后选择一个e (1<e<φ)，且e和φ互质
取e的模反数为d，计算方法: d=e^-1 mod (p-1)(q-1)

本题已知e=10，所以关键在于求出φ
根据欧拉函数定义，计算出$φ(n)=(p-1) *(q-1)*q * q$

205777062822855196204557259074204338863038877637508486991101948465308135853880119111298068410289942295119552877315995448483302052425384602998841067955989953532845673085938551734361886384957239104845083274605794116053692298274075954846274045387790432296780713156217096516442834594918827862540823117379119661764619290734086685907363261513580137663874870284095783503058795808164041247072364419239866222057499427540588679887524968959272826964100134564431765857617785871632054905292345277712079341783082012212706688061094998296147702680236639550101982604019253080207087085614227084574908094202693850747452248476172169172988025295138860040086705252643613747942616761475965636304045008301477874434092164471640329043047768806832761725356175958693573828929796609421973244181058162273249948507989984964176737160126969440713901163378524487913052802448828878557913452548831503041309225019783292421104846983044294553488830895031906282691942377484591183173552068835852478319307261641554425552804754002477048056545092966316064552607875541020758891571430248441211430296946142454465137812875546208385522654977654027563707207023062358869162899849260716308794744184245547839510008610288699881144289526736391055307563993152525081699163811563126251241880

使用gmpy2寻找逆元，提示逆元不存在
尝试暴力搜索，没得到结果，GG
(没注意到是因为phi和e不互素)

Solution

中国剩余定理是啥 = =

（X）2077 海底捞针

Try

no try, too hard for me

Solution

to be added…

（X）大整数分解锦标赛

Try

分析sympy的源码，发现调用的是random库来实现的随机，继续往下分析
最终跟踪到Python源码的_randommodule.c
随机数生成采用mt19937算法，而Python默认是获取系统的随机值，所以需要对状态进行恢复
可以通过不断调用Help函数来生成比特，然后就卡这了

Solution

to be added…

（X）Flag 红包

Try

设计一个AI来对抗它，没写代码实现
结果直接左右互搏？！

Solution

to be added…