『CTF』聊聊一个数字游戏

admin 2022年4月27日08:48:23评论136 views字数 4704阅读15分40秒阅读模式

点击蓝字 关注我们


日期: 2022-04-26
作者: Mr-hello
介绍: nAnB一款算法工程师喜爱的小游戏

0x00 前言

为什么想要研究这个小游戏,当然是CTF比赛中遇到,它夹在一道简单的 pwn 题目中,该题目出现在2022年虎符杯线上赛中,被算法大佬吊打,本场比赛是清华大佬们出的赛题,里面涉及的算法较多,作为一名小菜鸡,我只好赛后分析一下。

『CTF』聊聊一个数字游戏

0x01 游戏原理

说一下这个小游戏的逻辑,本场比赛里面涉及的是猜 4 位数,从 1000 - 9999 如果不限制次数,让谁都可以爆破出来,但是这次比赛是要求在 7 次之内猜解出来,首先程序会生成一个随机 4 位数(真随机数),所以不用考虑伪随机数的情况了,也不可能给你钻空子的。

然后,你每次提交一个随机数,程序都会给你一个 nAnB 的反馈,这个反馈中 nA 代表你猜解的 4 位数其中的 n 位的数值被你猜中,并且位置也同样猜中,nB 代表你猜中了 n 位的数值,但是这 n 位你没有猜中位置。这两个 n 相互独立,什么意思呢,例如:随机数为 4595,你如果提交 3553 那么程序的反馈是 1A1B,如果你提交 5555,程序的反馈是 2A0B,如果随机数为 6666,你提交 6723,程序的反馈是 1A0B

0x02 游戏实现

作为一名逆向选手

我当然选择使用 Python 语言来设计啦

别问为啥不用 CC++

因为 Python 是世界上最好的语言!!

然后我就栽坑了...

这个坑后面再说...

『CTF』聊聊一个数字游戏

设计思路应该是比较清晰的,首先我们应该生成一个 4 位数字,然后记录下来,然后与使用者提交的数字进行比较。但是考虑到比较时需要按位比较,我将生成的随机数的每一位变成了 list 存储,同样使用者提交的 4 位数字相同的办法存储。

后续工作就是如何进行比较,首先判断 nA 的情况,这个点很好解决,因为 nA 代表的是数值和位置同时满足,直接遍历判断是否相等即可找出 n 的数值。

最后确定 nB,因为刚开始的时候想的比较简单,以为只需要判断数值相同,但是下标不同即可满足条件,但是在测试过程中发现,这样在生成的随机数存在相同数字时会出错,而且如果某位先满足了 nA 的条件,即可不参与 nB 的计数。

这里我使用了标记的方法,一旦满足 nA 的条件,我将该位置上的数字进行了替换,后续不进行再次计数,但是这种方法涉及到对存储的 list 中的数据进行更改,而且机会共有 7 次每次开始计算 nAnB 时需要将 list 数据还原成最初的随机数状态,可能大家理所应当的想到,那每次循环的时候设计一个 tmp_list 变量,每次循环开始的时候还原成最原始的数据,每次计算的时候更改 tmp_list 中的数据就行,作者也是这样想的,但是发生了一件出现在我知识盲区里的知识。

看一下如下代码:

a = [1,2,3,4]b = ab[0] = 100print(b)print(a)

上述代码输出的 a 内容应该是什么呢,输出内容发现是 [100,2,3,4],竟然是传地址!原来 Python 在进行 list 类型数据传递时,默认使用浅拷贝模式,浅拷贝会创建新对象,其内容是原对象的引用。当然还有一个深拷贝,就是和浅拷贝相反的一个情况。(作者这里只遇到了 list 类型传递时会出现这种情况,因为深拷贝会额外消耗内存空间, python 语言特性问题)所以想实现只传值的情况,可以使用深拷贝操作。

代码如下:

import copya = [1,2,3,4]b = copy.deepcopy(a)b[0] = 100print(b)print(a)

好了,经过调试,外加从坑里爬出来之后,最终设计出来的简短小游戏代码如下:

# -*- coding: UTF-8 -*-# author: Mr_hello
import randomimport copy
def ansInit():    random.seed()    return list(str(random.randint(1000,9999)))
while True:    final_ans = ansInit()    #print(final_ans)    print('this is a guess number game')    print('you have seven times to guess it')    for i in range(7):        indexA = 0        indexB = 0        temp_ans = copy.deepcopy(final_ans)   # 深拷贝        num = list(input("It's %d time: "%(i + 1)))        while len(num) < 4:            print('please input 1000 <= number <= 9999')            num = list(input("It's %d time: "%(i + 1)))        for j in range(len(temp_ans)):    # 计算nA            if num[j] == temp_ans[j]:                indexA += 1                num[j] = temp_ans[j] = '-'  # 满足nA之后将数据置为'-',不参与后续nB计数。        for k in range(len(temp_ans)):    # 计算nB            for o in range(len(num)):                if temp_ans[k] != '-' and num[o] != '-':                    if k != o and temp_ans[k] == num[o]:                        indexB += 1                        break        print("%dA%dB"%(indexA,indexB))        if indexA == 4 and indexB == 0:            print('you win')            exit()    print('you loss try againn')

0x03 破解算法

这个游戏,被称之为珠玑妙算游戏,看了看网上的大部分解题算法大致分为两步:

第一步:首先尝试 1234 ,根据该数字得到的反馈,对所有 1000 ~ 9999 的数字进行 nAnB 的判断,取出所有满足与得到的反馈相同的数字集合,将不符合的反馈进行踢除。
第二步:从第一步得到的数字集合中取一个数字,进行尝试得到反馈,然后再次进入针对于第一步数字集合的 nAnB 判断,再次踢除不符合的数字,并且一直重复第二步。

PS: 为什么首先尝试 1234呢,因为在不知道任何反馈的情况下,选取 0 ~ 9 中不重复的 4 位数字组合,这样可以最大化得到数字信息。如果你问为什么不选 5678 那你就是在抬杠!

『CTF』聊聊一个数字游戏

破解代码部分实现如下:

def compare(num,temp):    A = 0    B = 0    for j in range(len(temp)):        if num[j] == temp[j]:            A += 1            num[j] = temp[j] = '-'    for k in range(len(temp)):        for o in range(len(num)):            if temp[k] != '-' and num[o] != '-':                if k != o and temp[k] == num[o]:                    B += 1                    break    return A, B
def delnum(num,indexA,indexB):    global maps    number = 0    for temp in maps:         if temp != 0:            A,B = compare(copy.deepcopy(num),copy.deepcopy(list(str(temp))))            if A == indexA and B == indexB:                pass            else:                maps[maps.index(temp)] = 0def suggestnum(num,i,indexA,indexB):    global maps    delnum(num,indexA,indexB)    for i in maps:        if i != 0:            return list(str(i))

这种算法实现的时候提取的数字,是从剩余数字集合中取第一个,利用该种算法经过大量尝试,发现可以实现的平均猜解次数为 6 ~ 7 次。尝试 400 次破解平均次数为 6.6325 ,下图是我尝试 200 次算出的平均次数。

『CTF』聊聊一个数字游戏

由此可见,上述算法已经可以做到平均 7 次之内将数字猜解出,但是这种算法情况有相当一部分概率会出现大于 7 次的现象,所以我又进行了一次改进。

既然在第二步中,我们是按照数字集合的第一位进行取,那么我们在第一步拿到数字集合之后,选取数字集合里面的每一位进行对比,记录每一位被排除的数字个数,优先选取排除个数最多的那个数字作为下一次尝试的数,这样是不是可以实现平均更少次数猜解出来呢。

实现代码如下:

def compare(num,temp):    A = 0    B = 0    for j in range(len(temp)):        if num[j] == temp[j]:            A += 1            num[j] = temp[j] = '-'    for k in range(len(temp)):        for o in range(len(num)):            if temp[k] != '-' and num[o] != '-':                if k != o and temp[k] == num[o]:                    B += 1                    break    return A, B
def delnum(num,indexA,indexB):    global maps    number = 0    value = 0    for temp in maps:         if temp != 0:            A,B = compare(copy.deepcopy(num),copy.deepcopy(list(str(temp))))            if A == indexA and B == indexB:                pass            else:                number += 1    return number
def maps_move(num,indexA,indexB):    global maps    temp_maps = copy.deepcopy(maps)    for temp in temp_maps:        A, B = compare(copy.deepcopy(num),copy.deepcopy(list(str(temp))))        if A == indexA and B == indexB:            pass        else:            maps.remove(temp)
def suggestnum(num,indexA,indexB):    global maps    renum = 0    delnumMax = 0    del_num = 0    print('Del num ' + str(delnum(num,indexA,indexB)))    maps_move(num,indexA,indexB)    for i in maps:        count = delnum(list(str(i)),indexA,indexB)        if delnumMax == 0 or delnumMax < count:            delnumMax = count            del_num = i    return list(str(del_num))

这里因为涉及到两个 for 循环效率变慢,但是我将第一次猜测更改为 1234 第二次尝试更改为 5678 之后效率相对变快,而且测试 500 次后统计出来的平均次数变为 5.896 次。但是在 500 次中仍然存在 16 次大于 7 次才成功猜解出来。也就是说失败率大约为 3.2%

『CTF』聊聊一个数字游戏

0x04 结语

我毕竟不是玩算法的大佬,我也不懂什么是信息摘要算法,或许上文我用到了该算法,但是我也不知道,咱也不懂啊,我只是知道网上有说可以实现稳定 6 次之内得到所有正确答案,但是我目前实现不了。而且我最后设计出来的解题算法,失败率仍然在 3.2% 左右,惭愧,学习去了。

『CTF』聊聊一个数字游戏

免责声明:本文仅供安全研究与讨论之用,严禁用于非法用途,违者后果自负。

『CTF』聊聊一个数字游戏

宸极实验室隶属山东九州信泰信息科技股份有限公司,致力于网络安全对抗技术研究,是山东省发改委认定的“网络安全对抗关键技术山东省工程实验室”。团队成员专注于 Web 安全、移动安全、红蓝对抗等领域,善于利用黑客视角发现和解决网络安全问题。

团队自成立以来,圆满完成了多次国家级、省部级重要网络安全保障和攻防演习活动,并积极参加各类网络安全竞赛,屡获殊荣。

对信息安全感兴趣的小伙伴欢迎加入宸极实验室,关注公众号,回复『招聘』,获取联系方式。

原文始发于微信公众号(宸极实验室):『CTF』聊聊一个数字游戏

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年4月27日08:48:23
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   『CTF』聊聊一个数字游戏http://cn-sec.com/archives/948754.html

发表评论

匿名网友 填写信息