首页
社区
课程
招聘
[原创]CTF2017第三题分析
2017-6-11 21:44 3805

[原创]CTF2017第三题分析

Fpc 活跃值
4
2017-6-11 21:44
3805

这个题目设计的不错,感谢题主

坑是smc,一开始不知道!不知道!不知道!坑是三个加号改减号,变量v94 v8c存放位置颠倒。因为存在约束,题目给出的原算法不可行,没有实数解,明知道有坑,不知坑在哪。

题目是VB Pcode,好多年没接触了,因为做题又拣回来,pcode主要是读指令,在虚拟机中打转,变量围绕stack操作,浮点数的存取计算则用到st寄存器。

工具用到看雪主页提供的VB Decompiler Pro用于看算法,ljtt VBParser用于看指令的具体地址,OD用于跟踪。

smc是后来关注到的,一开始改了EIP为1090,后来因为算不出来怀疑自己是不是中招了,恢复原状,结果跟踪时发现代码中有的加法怎么变减法,于是对内存下写断点,才发现有SMC,其中有rdtsc运行时间检查,细节没太关注,通过内存写断点可知,就是异或了上面提到了五处,如果你去跟,会一直在里面打转。OD加载后直接运行就行,在点验证之前设内存断点就可以跟踪了。

Regcode应为16个字母,16进制形式,分为两个dword,设前半部分为L,后半部分为R:

X=0x6606D1F5, A=373414231.36250, B=874402299.931726

初始化代码为:

Private Sub Form_Load() '408040
  'Data Table: 407BB0
  loc_408025: global_76 = CDbl(&H6606D1F5)
  loc_40802E: global_100 = "373414231.362502"
  loc_408038: global_104 = "874402299.931726"
  loc_40803C: Exit Sub
End Sub

约束条件是:

L, R<0x80000000; L>R; X+R>L; L+R>X

用到的公式是

 

loc_4083BE:   If (((L > CDbl(0)) And (R > CDbl(0))) And (L > R)) Then
  
  loc_4083D7:     var_94 = ((L + R) / CDbl(&HF4240))
  loc_4084CA:     var_8C = ((0.5 * ((2 * X^2 * L^2 - R^4 - X^4 + 2 * X^2 * R^2 + 2 * L^2 * R^2 - L ^ 4 ) ^ 0.5)) /  (X  + L  + R ))
  
  loc_40857A:     var_94 = ((X * L  * R) / (((X + L + R) * (X  + L - R ) * (X + R - L ) * ( L + R - X)) ^ 0.5 ))
  
  loc_4085FC:     If CBool(1 And (Format(var_94, "0.000000") = CVar(global_104))) Then
  loc_40860D:       1(0).Enabled = (Format(var_8C, "0.000000") = CVar(global_100))
  loc_408623:       1(0).Enabled = True
  loc_408639:       var_94(&HFF).Visible = var_8C
  loc_408641:     End If
  loc_408643:   End If

其中((2 * X^2 * L^2 - R^4 - X^4 + 2 * X^2 * R^2 + 2 * L^2 * R^2 - L ^ 4 ) ^ 0.5)=((X + L + R) * (X  + L - R ) * (X + R - L ) * ( L + R - X)) ^ 0.5 )   我是查百度来的,公式知识已经忘光了

设上式为DLT,则:

0.5*DLT/(X+L+R)=A ...(1)

X*L*R/DLT=B       ...(2)

约去DLT,将R用L表示

R=(X + L) * 2 * A * B / (L * X - 2 * A * B)

解题思路:

穷举,L作为循环变量,将L R代入1,2式,并以string来验证,1式过了再验2式,结果一致则为答案(实际上1过了,2也就过了)

这里面还可以改进一下,即直接验证浮点数,因为string转换、比较用时还是长

没VB,反出来的代码没法用,试了VBA,根本不行,程序一跑就失去响应,硬着头皮用C代码,主要是对浮点数心里没底,后来才发现不管什么语言,浮点数就是浮点数,相同的公式出的结果是一样的。

最后用到的主要代码:

int main(int argc, char* argv[])
{
	//其中的多余变量是在优化前用到的
	long unsigned double A, B, RT, X, DLT, RB, tmp;
	long unsigned int L, R, RL, RH, LL, LH;
	char sa[32], sb[32];
	char aa[32] = "373414231.362502";
	char bb[32] = "874402299.931726";
	char ch1;
	
	A=373414231.362502;
	B=874402299.931726;
	X=1711722997.0;
	cout<<"input LL"<<endl;
	cin>>LL;
	//1284400000
_next:
	LH=LL+100000000;
	cout<<"start :"<<LL<<"  end:  "<<LH<<endl;
	for(L=LL; L<LH; L++)
	{
		RB=(X + L) * 2 * A * B / (L * X - 2 * A * B);
		R=RB;
			DLT=sqrt(long unsigned double( (X + L + R) * (X  + L - R ) * (X + R - L ) * ( L + R - X)));
			tmp=0.5*DLT/(X+L+R)-A;
			if((tmp<1.0 )&& (tmp>-1.0))
			{
				sprintf(sa, "%13.6f", 0.5*DLT/(X+L+R));
				cout<<sa<<endl;
				if(!strcmp(sa, aa))
				{
					sprintf(sa, "%13.6f", X*R*L/DLT );
					cout<<"GOOD  "<<L<<"   "<<R<<endl;
					cout<<sa<<"     ";
					if(!strcmp(sa, bb))
					{
						continue;
					}
				}
			}
	}
	cout<<"continue ?";
	cin>>ch1;
	if(ch1!='n')
	{
		LL+=100000000;
		goto _next;			//比较丑,就不改do while....
	}
	cout<<"end..."<<endl;
	return 0;
}

编程时的弯路:

开始时对浮点数理解不深,不敢直接用得到的R来直接参与运算,而是在R的左右一定范围内取数,都试一遍,造成运算效率急剧降低,我用的上下限各1/1M,每次验证5M个值,需要10多分钟,加上中间一时疏忽,A值又赋值错误了,前前后后用了有10个小时。比赛完成后,去掉R的上下限,直接用,半分钟内就能出结果 T_T

解这个题费时较长,在坑里呆了一天吧,好在没放弃。收获是对pcode,浮点理解更多一些,知道VB也可以加smc。公式嘛,现在记不住,将来也还会是记不住

PS: 看到用matlab解题的,深感自己学识浅薄,自叹弗如啊



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

收藏
点赞1
打赏
分享
最新回复 (1)
雪    币: 1355
活跃值: (329)
能力值: ( LV13,RANK:920 )
在线值:
发帖
回帖
粉丝
爱琴海 13 2017-6-14 16:05
2
0
文章极好,写出了内心历程,感人呐!
游客
登录 | 注册 方可回帖
返回