-
-
[原创] KCTF 2023 第十一题 wp - 98k
-
发表于: 2023-9-27 22:46 10469
-
逆向部分没什么好说的，有个 check 算法，要在 1,000,000,000 到 1<<32 之间找一个数 k ，满足 !check(k) && check(k - 1) ， check 函数大致如下：
程序使用了多线程，总共的 try_count 为 10000 。
直接看这算法完全不懂，于是来找规律。先固定 buf1 和 buf3 数组的值，当输入的 value 比较小的时候 (range(1, 512)) 发现返回值非常稳定，也就是 try_count 为 1 都能直接得到稳定结果，于是使用小 value 调整 buf1 buf3 的取值找规律，部分输出如下：
上面的三次运行结果，是取 value 为 range(1, 256) ， buf3 全为 13 ， buf1 分别为 ① 全 2 ② 全 4 ③ 随机 2 和 4 这三种情况下的输出，输出的格式是返回值在某个值处发生了变化，变为了 True/False ，如第一次的输出含义是在 value = 28 时返回值开始为 True ， value = 51 时返回值开始为 False ，以此类推。这些输出就得到了指定条件下能返回 True/False 的 value 值的区间。并且这个结果是非常稳定的，只需要一次就能得到这个正确的结果。
这三个综合起来就可以看到，第三次返回 False 的 value 区间就是第一次返回 False 的 value 区间与第二次的交集。
如果将 value 的范围改为 range(1, 512) ，设置 buf1 全 2 ， buf3 全 13 ，可以得到如下结果：
可以看到 True/False 的区间长度是二次递增的（相邻 True 区间或者相邻 False 区间的长度差是一个等差数列），总之就是我们可以通过前几个区间值递推到我们想要的区间的 True/False 分布。
所以我们只要找到某组 buf1 和 buf3 的固定取值下 value 在 range(1, 256) 里的 True/False 分布（必须是稳定的），我们就能找到这些取值下 value 在 1,000,000,000 到 1<<32 之间的 True/False 分布，再结合第一条规律，不同 buf1 和 buf3 的取值下得到的返回 False 的取值区间的交就一定包含目标区间，这样就能大大缩小需要暴破的空间。
后面测试发现， buf1 与 buf3 的固定取值存在倍数关系时得到的结果不稳定，所以排除这一部分数据。最后共有 18 组组合，将暴破区间从 3294967296 减少到 87551 。
筛选后得到的区间：
这个空间就可以开始暴了，暴的过程中发现第 2 个区间会有一些误报，而其他都没有，猜测是目标区间就在第二个区间里，区间内其他值离目标值比较近，误报的概率就高了，所以直接写程序暴这个区间内的值：
跑了可能有半小时，输出里找了下很容易看到有一段连续好几百个值，这就是目标区间。当然里面还有一些误报的值， 2 万多个数误报了 20 多个，但是显然这些值是没法重复稳定通过的，只有这个区间里的值能稳定过 !check 。最后回到问题，满足 !check(k) && check(k - 1) 的值就是这个区间里的最小值 1898766093 。
def check(value, try_count):
buf1 = [0] * 10000
buf2 = [0] * 10000
buf3 = [0] * 20000
buf4 = [0] * 20000
for _ in range(try_count):
print(_, end=' \r')
v = [2, 4, 5, 6, 7, 8, 13]
for i in range(10000):
_v = v[rand() % len(v)]
buf1[i] = _v
if i == 0:
buf2[i] = rand() % (_v - 1) + 1
else:
buf2[i] = rand() % _v
for i in range(20000):
buf3[i] = v[rand() % len(v)]
i12 = 0
i34 = 0
tmpv = 0
while i12 < 10000 or tmpv > 0:
if i34 >= 20000:
# assert False, 1
return True
tmpv_bak = tmpv
if i12 >= 10000:
tmpv = tmpv // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
tmpv = buf1[i12] * tmpv + buf2[i12]
if tmpv_bak // buf3[i34] * tmpv >= value:
tmpv = tmpv_bak // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
i12 += 1
i12 = 10000 - 1
i34 -= 1
tmpv = 0
while i34 >= 0 or tmpv > 0:
if i12 < 0:
# assert False, 2
return True
tmpv_bak = tmpv
if i34 < 0:
tmpv = tmpv // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
# assert False, 3
return True
i12 -= 1
else:
tmpv = buf3[i34] * tmpv + buf4[i34]
if tmpv_bak // buf1[i12] * tmpv >= value:
tmpv = tmpv_bak // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
# assert False, 4
return True
i12 -= 1
else:
i34 -= 1
return False
def check(value, try_count):
buf1 = [0] * 10000
buf2 = [0] * 10000
buf3 = [0] * 20000
buf4 = [0] * 20000
for _ in range(try_count):
print(_, end=' \r')
v = [2, 4, 5, 6, 7, 8, 13]
for i in range(10000):
_v = v[rand() % len(v)]
buf1[i] = _v
if i == 0:
buf2[i] = rand() % (_v - 1) + 1
else:
buf2[i] = rand() % _v
for i in range(20000):
buf3[i] = v[rand() % len(v)]
i12 = 0
i34 = 0
tmpv = 0
while i12 < 10000 or tmpv > 0:
if i34 >= 20000:
# assert False, 1
return True
tmpv_bak = tmpv
if i12 >= 10000:
tmpv = tmpv // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
tmpv = buf1[i12] * tmpv + buf2[i12]
if tmpv_bak // buf3[i34] * tmpv >= value:
tmpv = tmpv_bak // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
i12 += 1
i12 = 10000 - 1
i34 -= 1
tmpv = 0
while i34 >= 0 or tmpv > 0:
if i12 < 0:
# assert False, 2
return True
tmpv_bak = tmpv
if i34 < 0:
tmpv = tmpv // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
# assert False, 3
return True
i12 -= 1
else:
tmpv = buf3[i34] * tmpv + buf4[i34]
if tmpv_bak // buf1[i12] * tmpv >= value:
tmpv = tmpv_bak // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
# assert False, 4
return True
i12 -= 1
else:
i34 -= 1
return False
$ python3 ./script.py
[(28, True), (51, False), (107, True), (153, False), 238, True)]
$ python3./script.py
[(54, True), (103, False), (211, True)]
$ python3 ./script.py
[(28, True), (51, False), (54, True), (103, False), (107, True), (153, False), (211, True)]
$ python3 ./script.py
[(28, True), (51, False), (107, True), (153, False), 238, True)]
$ python3./script.py
[(54, True), (103, False), (211, True)]
$ python3 ./script.py
[(28, True), (51, False), (54, True), (103, False), (107, True), (153, False), (211, True)]
[(28, True), (51, False), (107, True), (153, False), 238, True), (307, False), (421, True)]
[(28, True), (51, False), (107, True), (153, False), 238, True), (307, False), (421, True)]
#!/usr/bin/env python3'''seed = 0def rand(): global seed
seed += 1
return seed
'''def rand(): # simulate rand (may be any random function)
pass
def check(value, try_count): # check
pass
def check_1(value, buf1_v, buf3_v):
print(value, end=' \r')
buf1 = [buf1_v] * 10000
buf2 = [rand() % (buf1_v - 1) + 1]
for i in range(1, 10000):
buf2.append(rand() % buf1_v)
buf3 = [buf3_v] * 20000
buf4 = [0] * 20000
i12 = 0
i34 = 0
tmpv = 0
while i12 < 10000 or tmpv > 0:
if i34 >= 20000:
return True
tmpv_bak = tmpv
if i12 >= 10000:
tmpv = tmpv // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
tmpv = buf1[i12] * tmpv + buf2[i12]
if tmpv_bak // buf3[i34] * tmpv >= value:
tmpv = tmpv_bak // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
i12 += 1
i12 = 10000 - 1
i34 -= 1
tmpv = 0
while i34 >= 0 or tmpv > 0:
if i12 < 0:
return True
tmpv_bak = tmpv
if i34 < 0:
tmpv = tmpv // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
return True
i12 -= 1
else:
tmpv = buf3[i34] * tmpv + buf4[i34]
if tmpv_bak // buf1[i12] * tmpv >= value:
tmpv = tmpv_bak // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
return True
i12 -= 1
else:
i34 -= 1
return False
try_count = 150
'''low = 1000000000v_low = check(low, try_count)print(low, v_low)high = 0x100000000v_high = check(high, try_count)print(high, v_high)while low < high: mid = (low + high) // 2
v_mid = check(mid, try_count)
print(mid, v_mid)
if v_mid == v_low:
low = mid + 1
v_low = check(low, try_count)
print(low, v_low)
else:
high = mid - 1
v_high = check(high, try_count)
print(high, v_high)
'''def interval_and(l1, l2):
l = []
i1 = 0
i2 = 0
while i1 < len(l1) and i2 < len(l2):
l1a, l1b = l1[i1]
l2a, l2b = l2[i2]
if l1a >= l2b:
i2 += 1
continue
elif l2a >= l1b:
i1 += 1
elif l1b >= l2b:
l.append((max(l1a, l2a), l2b))
i2 += 1
if l1b == l2b:
i1 += 1
else:
l.append((max(l1a, l2a), l1b))
i1 += 1
return l
def get_f_intervals(t, f, tdiv, fdiv, pub_div):
assert t < f
t = t + tdiv
tdiv += pub_div
assert t > f
while t < 1000000000:
f += fdiv
fdiv += pub_div
t += tdiv
tdiv += pub_div
fl = []
while f < 0x100000000:
fl.append((f, t))
f += fdiv
fdiv += pub_div
t += tdiv
tdiv += pub_div
return fl
def number_count(l):
s = 0
for a, b in l:
s += b - a
return s
'''last_r = Falsea = []for i in range(1, 1024): r = check_1(i, 2, 13)
if last_r != r:
a.append((i, r))
if len(a) >= 8: break
last_r = r
# print(a)
print(a)print(a[2][0] - a[0][0], a[4][0] - a[2][0], a[6][0] - a[4][0])x=a[0][0]y=a[2][0]z=a[4][0]x1=a[1][0]y1=a[3][0]print(x,x1,y-x,y1-x1,(z-y)-(y-x))'''s='''
28 51 79 102 5254 103 157 206 10467 129 196 258 13080 155 235 310 15693 181 274 362 182106 207 313 414 20816 27 43 54 2830 55 85 110 5637 69 106 138 7044 83 127 166 8458 111 169 222 11212 19 31 38 2022 39 61 78 4032 59 91 118 6042 79 121 158 8014 23 37 46 2426 47 73 94 4850 95 145 190 96'''fl = [(1000000000, 0x100000000)]
n = number_count(fl)
for i in s.strip().split('\n'):
if not i.strip(): continue
fl = interval_and(fl, get_f_intervals(*(int(j) for j in i.split(' '))))
last_n = n
n = number_count(fl)
print('{} -> {} (-{}%)'.format(last_n, n, 100 * (last_n - n) / last_n))
for i in fl:
print(i, i[1] - i[0])
#!/usr/bin/env python3'''seed = 0def rand(): global seed
seed += 1
return seed
'''def rand(): # simulate rand (may be any random function)
pass
def check(value, try_count): # check
pass
def check_1(value, buf1_v, buf3_v):
print(value, end=' \r')
buf1 = [buf1_v] * 10000
buf2 = [rand() % (buf1_v - 1) + 1]
for i in range(1, 10000):
buf2.append(rand() % buf1_v)
buf3 = [buf3_v] * 20000
buf4 = [0] * 20000
i12 = 0
i34 = 0
tmpv = 0
while i12 < 10000 or tmpv > 0:
if i34 >= 20000:
return True
tmpv_bak = tmpv
if i12 >= 10000:
tmpv = tmpv // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
tmpv = buf1[i12] * tmpv + buf2[i12]
if tmpv_bak // buf3[i34] * tmpv >= value:
tmpv = tmpv_bak // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
i12 += 1
i12 = 10000 - 1
i34 -= 1
tmpv = 0
while i34 >= 0 or tmpv > 0:
if i12 < 0:
return True
tmpv_bak = tmpv
if i34 < 0:
tmpv = tmpv // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
return True
i12 -= 1
else:
tmpv = buf3[i34] * tmpv + buf4[i34]
if tmpv_bak // buf1[i12] * tmpv >= value:
tmpv = tmpv_bak // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
return True
i12 -= 1
else:
i34 -= 1
return False
try_count = 150
'''low = 1000000000v_low = check(low, try_count)print(low, v_low)high = 0x100000000v_high = check(high, try_count)print(high, v_high)while low < high: mid = (low + high) // 2
v_mid = check(mid, try_count)
print(mid, v_mid)
if v_mid == v_low:
low = mid + 1
v_low = check(low, try_count)
print(low, v_low)
else:
high = mid - 1
v_high = check(high, try_count)
print(high, v_high)
'''def interval_and(l1, l2):
l = []
i1 = 0
i2 = 0
while i1 < len(l1) and i2 < len(l2):
l1a, l1b = l1[i1]
l2a, l2b = l2[i2]
if l1a >= l2b:
i2 += 1
continue
elif l2a >= l1b:
i1 += 1
elif l1b >= l2b:
l.append((max(l1a, l2a), l2b))
i2 += 1
if l1b == l2b:
i1 += 1
else:
l.append((max(l1a, l2a), l1b))
i1 += 1
return l
def get_f_intervals(t, f, tdiv, fdiv, pub_div):
assert t < f
t = t + tdiv
tdiv += pub_div
assert t > f
while t < 1000000000:
f += fdiv
fdiv += pub_div
t += tdiv
tdiv += pub_div
fl = []
while f < 0x100000000:
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
赞赏
|
|
|---|---|
|
|
他的文章
赞赏
雪币:
留言:
