-
-
[原创]看雪 2022·KCTF 秋季赛 > 第二题 盗贼作乱 by 心学
-
2022-11-19 00:31 13299
-
准备工具:
1、IDA77
2、WinDBG Preview【可以不用】
3、Python
一、分析程序结构
1、直接运行程序,了解程序反馈
1 2 3 4 5 6 7 | C:\Users\surface> "C:\Users\surface\OneDrive\Crack\CTF\看雪 2022·KCTF 秋季赛\02\cm2022\cm2022.exe" Input : 0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef Error. C:\Users\surface> "C:\Users\surface\OneDrive\Crack\CTF\看雪 2022·KCTF 秋季赛\02\cm2022\cm2022.exe" Input : 11111111111111 Error. C:\Users\surface> |
结论:输入错误的序列号,直接返回 Error
提示:先打开CMD窗口,然后将文件拖入窗口运行。
2、IDA反编译程序,浏览整体架构
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | int __cdecl main( int argc, const char * * argv, const char * * envp) { int v3; / / edi int v4; / / eax int v6; / / esi int v7; / / eax char inputSN; / / [esp + 8h ] [ebp - 40h ] BYREF char v10[ 60 ]; / / [esp + 9h ] [ebp - 3Fh ] BYREF __int16 v11; / / [esp + 45h ] [ebp - 3h ] char v12; / / [esp + 47h ] [ebp - 1h ] inputSN = 0 ; memset(v10, 0 , sizeof(v10)); v11 = 0 ; v12 = 0 ; sub_40284A(( int )aInput); gets(&inputSN); v3 = - 1 ; v4 = 0 ; if ( !inputSN ) goto LABEL_20; do { if ( v4 > = 0x40 ) break ; if ( v10[v4 - 1 ] = = '-' ) v3 = v4; } while ( v10[v4 + + ] ); if ( v3 > 0 && (v6 = v4 - v3, v4 - v3 > 0 ) && sub_4014D0(dword_40A940, &inputSN, v3, Base62) > 0 / / '-' 前半部分 && sub_4014D0(dword_40A964, &v10[v3], v6 - 1 , Base62) > 0 / / '-' 后半部分 && (sub_4014D0( dword_40A9D0, aIrtzloz6iub, strlen(aIrtzloz6iub), Base62), / / 处理固定字符 sub_401630( dword_40A9FC, 0 ), / / 初始化 为 0 sub_401630( dword_40AA20, 0 ), / / 初始化 为 0 cmp (dword_40A940, dword_40A964) < 0 ) / / 前半部分 < 后半部分 && cmp (dword_40A940, dword_40A9D0) < 0 / / 前半部分 < 内置 8 && cmp (dword_40A964, dword_40A9D0) < 0 ) / / 后半部分 < 内置 8 { v7 = 0 ; while ( 1 ) { dword_40A9F4 = v7 + 1 ; / / 处理的标志位? sub_401730(dword_40A9FC, dword_40A9FC, dword_40A940); / / 累加 sub_401730(dword_40AA20, dword_40AA20, dword_40A964); / / 累加 sub_4021A0(dword_40A9FC, dword_40A9FC, dword_40A9D0); / / 取余 sub_4021A0(dword_40AA20, dword_40AA20, dword_40A9D0); / / 取余 sub_401630(dword_40A988, 1 ); / / 初始化 为 1 ,此处会重新赋值 sub_401820(dword_40A988, dword_40A9FC, dword_40A988); / / 减 1 if ( ! cmp (dword_40A988, dword_40A940) ) / / 判断两个数要相等才行。相等返回 0 ,大于返回 1 ,小于返回 - 1 { + + dword_40A9F8; sub_401CF0(dword_40A988, dword_40A988, dword_40A940); / / 乘法? } sub_401630(dword_40A9AC, 1 ); sub_401730(dword_40A9AC, dword_40AA20, dword_40A9AC); / / 加 1 if ( ! cmp (dword_40A9AC, dword_40A964) ) { + + dword_40A9F8; sub_401F30(dword_40A9AC, dword_40A9D0, dword_40A964); / / 除法? } if ( dword_40A9F8 = = 0xA ) / / 需要命中 10 次(只要使其等于 10 即可)才行 break ; v7 = dword_40A9F4; if ( dword_40A9F4 > = 0x200000 ) goto LABEL_20; } sub_40284A(( int )aSuccess); return 0 ; } else { LABEL_20: sub_40284A(( int )aError); return 0 ; } } 程序分为四大块: 一是:获取用户输入 二是:IF条件判断,需满足 三是: while 循环,一大堆计算 四是:输出结果 ### 3、全局查看结构,锁定成功失败 |
在IDA里,反编译之后,程序的主函数main结构比较简单,Text或Graph视图都可以清晰的看到 Error 和 Success 信息,能快速定位到程序运行失败或成功的关键判断之处。
1 2 3 4 5 6 7 8 9 | sub_40284A(( int )aSuccess); return 0 ; } else { LABEL_20: sub_40284A(( int )aError); return 0 ; } |
从后往前推:
如果要运行到 sub_40284A((int)aSuccess),则必须保证 dword_40A9F8 == 0xA;【作者埋了一个坑】,此时想当然认为 循环要进行十遍(错了)。
关注:全局变量 dword_40A9F8
二、找出约束条件
1、静态代码走查,记录约束条件
1 2 3 4 5 6 7 8 9 | do { if ( v4 > = 0x40 ) break ; if ( v10[v4 - 1 ] = = '-' ) v3 = v4; } while ( v10[v4 + + ] ); if ( v3 > 0 |
约束条件1:序列号长度小于等于 0x40
约束条件2:序列号内存在一个 '-' 字符。v3 记录 '-' 的位置
1 2 | sub_4014D0(dword_40A940, &inputSN, v3, Base62) > 0 sub_4014D0(dword_40A964, &v10[v3], v6 - 1 , Base62) > 0 |
约束条件3:序列号部分转换满足要求(2处)
1 | (sub_4014D0(dword_40A9D0,aIrtzloz6iub,strlen(aIrtzloz6iub),Base62) |
约束条件4:内置字符串转换满足要求
1 2 3 | cmp (dword_40A940, dword_40A964) < 0 && cmp (dword_40A940, dword_40A9D0) < 0 && cmp (dword_40A964, dword_40A9D0) < 0 |
约束条件5:序列号(2处)及内置字符串相互比较要满足要求
1 | if ( dword_40A9F8 = = 0xA ) |
约束条件6:dword_40A9F8 == 0xA
总结一下:有6个约束条件,在不深入到子函数细节的情况下进行分析。
约束条件1:序列号长度小于等于 0x40
约束条件2:序列号内存在一个 '-' 字符。v3 记录 '-' 的位置
约束条件3:序列号部分转换满足要求(2处)
约束条件4:内置字符串转换满足要求
约束条件5:序列号(2处)及内置字符串相互比较要满足要求
约束条件6:dword_40A9F8 == 0xA
2、数据驱动调试,猜测函数功能
我们遇到了很多函数,目前,还不清楚每个函数的细节,但是对于大佬老说,此时已经猜测是利用高进制进行大整数的运算。接下来我主要从经验值较低的角度来分析函数功能,主要方法是通过参数及变量(内存区域)的变化,来猜测或推测函数的大概功能。
2.1 sub_4014D0
1 2 3 | sub_4014D0(dword_40A940, &inputSN, v3, Base62) sub_4014D0(dword_40A964, &v10[v3], v6 - 1 , Base62) sub_4014D0(dword_40A9D0,aIrtzloz6iub,strlen(aIrtzloz6iub),Base62) |
输入四个参数,返回结果要大于0
输入的参数:最后一个参数是固定的内置字符串,即Base62;第二个参数是字符串,有的是用户输入的字符串、程序内置字符串;第三个参数是整数;第一个参数是一个全局变量。
现在猜测这个函数应该只对第一个参数全局变量做修改。
现在开始数据驱动测试,我们构造序列号:
IDA调试:
SN:0123456789abcdef-0123456789abcdef
结果:
1 2 3 | .data: 0040A940 dword_40A940 dd 0Ch , 2C7BD6CEh , 0B7B6B582h , 677E02E5h , 0 , 0 , 0 , 0 , 0 .data: 0040A964 dword_40A964 dd 0Ch , 2C7BD6CEh , 0B7B6B582h , 677E02E5h , 0 , 0 , 0 , 0 , 0 .data: 0040A9D0 dword_40A9D0 dd 8 , 89E80000h , 8AC72304h , 0 |
0040A940 和 0040A964 结果一样,这与我们输入的序列号相关,初步判断是用 - 进行了分割,然后分别进行计算。
0040A9D0 与 内置字符串相关 'IRtzloZ6iuB'
但是 这些全局变量值与输入的字符串有什么关联,直接看代码是一种方式,但是通过数据测试也可以才出来。用最小的值依次判断。
SN:0-0
程序非正常退出
在sub_4014D0内return 0 直接返回0,不满足条件,退出了。全局变量没有值,这个子函数不支持0数据转换
SN:1-1
1 2 | .data: 0040A940 dword_40A940 dd 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 .data: 0040A964 dword_40A964 dd 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 |
那看来输入1,返回1
SN:11-12
1 2 | .data: 0040A940 dword_40A940 dd 1 , 3Fh , 0 , 0 , 0 , 0 , 0 , 0 , 0 .data: 0040A964 dword_40A964 dd 1 , 7Dh , 0 , 0 , 0 , 0 , 0 , 0 , 0 |
0x3F = 63 对应 11
0x7D = 125 对应 12
我们与62进制来对照,11(62进制) = 63;21(62进制) = 125
初步猜测该函数是 62进制 的字符串序列与整数的转换,不过字符串是倒序存放的。可以进一步分析
1 | .data: 0040A9D0 dword_40A9D0 dd 8 , 89E80000h , 8AC72304h , 0 |
'IRtzloZ6iuB' ==》8, 89E80000h, 8AC72304h
第一个 DWORD = 8 是后面的字节序列长度。可以猜测出来。
2.2 sub_401630
1 2 | sub_401630(dword_40A9FC, 0 ) sub_401630(dword_40AA20, 0 ) |
可以跟踪函数的运行前后,两个全局变量的变化,基本可以判断这是一个赋值操作,用0来给全局变量赋值,类似于初始化。
2.3 sub_401690
1 | sub_401690(resultA * a1, resultA * a2) |
用上面的方法,可以判断出这是一个比较方法,其返回值有1、0、-1 分别表示大于、等于、小于
我在这儿构造了一个结构resultA,它是大整数计算的结构,第一个DWORD是大整数的字节长度,之后就是大整数的字节序列。我们可以通过前述的0040A940进行分析,当我们给定更大的值,就可以得出上述结构构造。
2.4 sub_401730
1 | signed int __cdecl sub_401730(resultA * dest, resultA * a2, resultA * source) |
用上面方法分析,这是一个 加法运算
dest = a2 + source
2.5 sub_4021A0
1 | int __cdecl sub_4021A0(resultA * a1, resultA * a2, resultA * baseNum) |
这是取模运算,最后一个参数都是固定的,dword_40A9D0 ,存储的是内置字符串的62进制值。
2.6 sub_401630
1 | sub_401630(dword_40A988, 1 ) |
这是 赋值操作,给第一个参数赋第二个参数值,即赋值1
2.7 sub_401820
1 2 | signed int __cdecl sub_401820(resultA * dest, resultA * a2, resultA * source) sub_401820(dword_40A988, dword_40A9FC, dword_40A988) |
这是 减法操作,实际上 减去了1 (dword_40A988)
dword_40A988 = dword_40A9FC - dword_40A988
2.8 sub_401CF0
1 | sub_401CF0(dword_40A988, dword_40A988, dword_40A940); |
它的运算比较复杂,如果用参数前后对照,会发现它是一个 乘法运算
dword_40A988 = dword_40A988 * dword_40A940
dword_40A988 在每次循环后都会置初始值1,其不会对其他造成干扰
dword_40A940 是固定值。貌似这个乘法用处不大。
2.9 sub_401F30
1 | sub_401F30(dword_40A9AC, dword_40A9D0, dword_40A964); |
这是除法运算
dword_40A9AC = dword_40A9D0 / dword_40A964
dword_40A9AC 在每次循环后都会置初始值1,其不会对其他造成干扰
dword_40A9D0 、dword_40A964 是固定值。
这个除法貌似没法用。它没有对我们关注的全局变量进行修改【实际有坑】
3、深入挖掘代码,寻找隐藏细节
经过上面分析,基本上对逻辑计算有了一定理解,
dword_40A940:序列号前半部分值 partA
dword_40A964:序列号后半部分值 partB
dword_40A9D0:内置字符串值 interValue
条件判断:
partA < partB
partA < interValue
partB < interValue
经过if条件判断之后,开始while循环处理
dword_40A9F8:记录两个 cmp 相等的次数【坑,还有其他地方对其影响】,满足10即可
dword_40A9F4:记录当前循环的次数 cnt
1 2 3 4 | dword_40A9FC = dword_40A940 * dword_40A9F4 = partA * cnt mod(interValue) dword_40AA20 = dword_40A964 * dword_40A9F4 = partB * cnt mod(interValue) dword_40A988 = 1 dword_40A988 = dword_40A9FC - dword_40A988 = dword_40A9FC - 1 |
cmp(dword_40A988, dword_40A940)
比较相等即成功给 dword_40A9F8 加 1
数学表达式就是
1 | partA * cnt mod(interValue) - 1 = = partA |
一个数乘以一个倍数,减去 1 然后等于自身
这是第一处判断。。。。。。
dword_40A9AC = 1
dword_40A9AC = dword_40AA20 + dword_40A9AC = dword_40AA20 +1
cmp(dword_40A9AC, dword_40A964)
比较相等即成功给 dword_40A9F8 加 1
数学表达式就是
1 | partB * cnt mod(interValue) + 1 = = partB |
一个数乘以一个倍数,加上 1 然后等于自身
这是第二处判断。。。。。。
然后这些需要经过 10次 才能满足要求【坑】,
这种情况可能吗?cnt 有上限 0x200000; interValue模数已知,要求 partA 和 partB,直觉不可能,如果具有一定的数论知识,联想到 模N求逆,只能有一个结果。
模N 求A 的 逆元B =》 A × B == 1 mod(N),只有在A或B与N互质的情况下才存在,如果 不互质,那么就不可能存在逆元 B。存在的情况下也只有一个结果。
那么,问题如何解决了?这需要更进一步查看、深究代码。
重点关注cmp比较之后的代码,也就是上面分析出来的乘法和除法函数,为什么?一是此段代码执行比较少,应优先判断去排查;二是循环体的外侧代码功能性强,运算的结果都有一定的影响,影响的全局变量值目的性强,且未发现对其他的全局变量进行更改。
关键隐藏之处1
乘法:
1 2 3 4 5 6 7 8 9 10 11 12 13 | int __cdecl sub_401CF0(resultA * a1, resultA * a2, resultA * a3) sub_401630(dword_40A988, 4 ); sub_4023A0(dword_40A9AC, dword_40A988, 3 ); if ( dword_40A9F8 > 0 && * (_DWORD * )&dword_40A9D0[ 0 ].value[(unsigned __int8)dword_40A9AC[ 0 ].value[ 0 ]] = = (unsigned __int8)dword_40A9AC[ 0 ].value[ 0 ] ) { sub_401730(dword_40A988, dword_40A988, dword_40A9AC); v13 = sub_402360(dword_40A988, dword_40A9F4); dword_40A9D0[ 0 ].value[(unsigned __int8)dword_40A988[ 0 ].value[ 0 ]] + = 4 ; sub_4023A0(dword_40A988, dword_40A988, v13); sub_401820(dword_40A9AC, dword_40A988, dword_40A9AC); } return v7; |
1 2 3 4 5 | sub_401630(dword_40A988, 4 ) = = >dword_40A988 = 4 sub_4023A0(dword_40A9AC, dword_40A988, 3 ) = = > dword_40A9AC = 4 * 2 ^ 3 = 32 dword_40A9AC[ 0 ].value[ 0 ] 是第一个字节,即上面的赋值 32 dword_40A9D0[ 0 ].value[(unsigned __int8)dword_40A9AC[ 0 ].value[ 0 ]] = = > dword_40A9D0[ 0 ].value[ 32 ] |
if语句的两个判断:
dword_40A9F8 > 0 显然无问题 4
dword_40A9D0[0].value[32] == 32
这里要满足32,才执行里面的语句,此处分析两个问题:
1、怎么满足条件?
2、满足条件后,执行了啥?有什么用?
第一个问题,进一步查看全局变量的位置
dword_40A9D0[0].value[32] ==>
dword_40A9D0 + 4 + 32 = dword_40A9F4
+4 是略过了第一个双字(字节序列长度)
我们发现,这种操作之后,实际内存位置是 dword_40A9F4
它是什么,我们回看main里面的while循环,他是循环累计次数,即进行到了第几次循环,也就说,我们得循环到第32次(从1开始计数)才能进入,此时要够在序列号,使其满足前述的5个约束条件,特别是两个 cmp 运算,即满足while里的cmp运算。
一个数乘以一个倍数,减去 1 然后等于自身
第二个问题,满足条件了,执行了啥?
1 2 | sub_401730(dword_40A988, dword_40A988, dword_40A9AC); dword_40A9D0[ 0 ].value[(unsigned __int8)dword_40A988[ 0 ].value[ 0 ]] + = 4 ; |
dword_40A988 = dword_40A988 + dword_40A9AC = 4+32 = 36
dword_40A988[0].value[0]] = 36
dword_40A9D0[0].value[(unsigned __int8)dword_40A988[0].value[0]] = dword_40A9D0[0].value[4]==>
dword_40A9D0 + 4 + 36 = dword_40A9F8
这是 关键的全局变量,它等于0xA才能输出success。
除法方法类似。这两个方法是关键的隐藏之处。
梳理一下思路:
序列号的前后两个部分:
1、执行到32次,满足判断条件,此时 dword_40A9F8 各计入1次
partA × 32 mod(interValue) - 1 == partA
partB × 32 mod(interValue) + 1 == partB
2、进入乘法或除法方法后,dword_40A9F8 各累加4
此时,就可以满足 dword_40A9F8 == 10 == 0xA
三、整理破解思路
1、列出步骤
1.1 构造一个62进制的解码及编码方法
1.2 求出序列号的前后两部分
1.3 输出序列号
2、优化方案
主要是对 求出序列号的前后两部分 进行优化
1 2 3 | interValue = 0x8AC7230489E80000 = 10000000000000000000 = 10 ^ 19 partA × 32 mod( 10 ^ 19 ) - 1 = = partA partB × 32 mod( 10 ^ 19 ) + 1 = = partB |
可以通过循环,逐个从1开始计算,找到结果。
有一种快速方法,可以利用求模N的逆来快速得到结果。
1 2 | partA * 31 = 1 mod( 10 ^ 19 ) partB * ( - 31 ) = 1 mod( 10 ^ 19 ) |
可以利用pow方法求出
1 2 | partA = pow ( 31 , - 1 , 10 * * 19 ) partB = pow ( - 31 , - 1 , 10 * * 19 ) |
四、编写程序脚本
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | ''' 题目:看雪 2022·KCTF 秋季赛 > 第二题 盗贼作乱 链接:https://ctf.pediy.com/game-season_fight-217.htm 作者:htg 心学 时间:2022-11-18 ''' BASE62 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" interValue = 'IRtzloZ6iuB' #模 ##62进制字符串转整数:字符串倒序存放 def Str2Int(text): base = len (BASE62) num = 0 for i in text[:: - 1 ]: num = num * base + BASE62.index(i) return num ##整数转62进制字符串:字符串倒序存放 def Int2Str(value): base = len (BASE62) resultStr = "" while value > 0 : tmp = value % base value = value / / base resultStr = resultStr + BASE62[tmp] if resultStr = = "": resultStr = 0 return resultStr returnNum = Str2Int(interValue) print ( "测试:Str2Int('IRtzloZ6iuB') = {0}\t0x{0:X}" . format (returnNum)) ''' 10**19 == 10000000000000000000 == 0x8AC7230489E80000 N = 0x8AC7230489E80000 = 10**19 【数论知识点】模N求逆运算 求解 X 32 * X - 1 = X mod N ===》 31 * X = 1 mod N ===》X 为 31 相对于 模N 的逆。 这个容易想起模逆运算。 X * Y = 1 mod N 代表 X 和 Y 相对于模 N 互逆。当然 X,Y 相对于 模N 互质。 所以可以直接用 pow(31,-1,10**19) 来求 31 的 逆 相对于模10**19 求解 Y 32 * Y + 1 = Y mod N ===》 31 * Y = -1 mod N ===》-31 * Y = 1 mod N ==》Y 为 -31 相对于 模N 的逆。 所以可以直接用 pow(-31,-1,10**19) 来求 31 的 逆 相对于模10**19 ''' partA = pow ( 31 , - 1 , 10 * * 19 ) partB = pow ( - 31 , - 1 , 10 * * 19 ) print ( "(partA,partB) = ({},{})" . format (partA,partB)) print ( "(partA,partB) = ({0},{1})\nSN = {0}-{1}" . format (Int2Str(partA),Int2Str(partB))) |