TL; DR：我们仅用十个小时就对一个完全未知的CPU架构编写的程序进行了反向工程，而该程序在CPU上没有任何文档（没有仿真器，没有ISA，没有所有内容）。 从本文中，您将了解我们是如何做到的...
上周末，CMU PPP团队和我参加了Dragon Sector Teaser CTF 2019团队，以放松并摆脱
CHI 2020艰难的最后期限。 Dragon Sector是一支受人尊敬的波兰团队，有着有趣的
CTF的历史，因此我想知道他们的库存。
解决了“ ummmfpu”这一任务，其中包括对Micromega uM-FPU浮点协处理器的字节码进行反向工程后，我决定参加一场竞赛以解决CPU Adventure问题，当时该问题尚未被任何团队解决（因此我们是唯一完成任务的人。
这是CPU Adventure任务的描述：
我60年代的祖父从事计算机的开发。 我把东西整理好放在他的阁楼上，我发现了一辆奇怪的汽车。 机器旁边是一堆打着“龙族冒险游戏”的打孔卡。 一段时间后，我设法将它连接到现代设备，但是游戏太复杂了，如果不作弊，我将无法结束游戏。 你能帮我吗？ 随函附上机器中使用的打孔卡的副本。 据称，该机器具有4个通用寄存器，1吉字节的数据存储器和32吉字节的命令存储器。 要玩游戏，请按以下方式连接到服务器： socat tcp4-connect:cpuadventure.hackable.software:1234 fd:0,rawer提示：该机器的处理器是唯一的，请勿尝试在其上搜索Google信息。
game.bin
连接到服务器后，我们收到以下信息：
THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.
SELECT AN OPTION:
- GO (N)ORTH
- GO (E)AST
- (T)ALK TO VALIS
- (D)RINK
- SHOW (I)NVENTORY
YOUR CHOICE:
太好了 这是一款老式的冒险游戏。 玩了一段时间之后，我们意识到如果我们取悦他，您可以与敌人战斗并从这个瓦利斯的角色中获得旗帜：
YOUR CHOICE: T
YOU ENTER THE TAVERN AND APPROACH VALIS.
- HEY, I WAS WONDERING IF YOU COULD HELP ME FIND THE FLAG?
- THE FLAG? MAYBE, BUT FIRST, I NEED A REDBULL.
- I... I DON'T HAVE A REDBULL.
- WELL THEN, MAKE YOURSELF USEFUL AND FIND ONE.
THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.
SELECT AN OPTION:
- GO (N)ORTH
- GO (E)AST
- (T)ALK TO VALIS
- (D)RINK
- SHOW (I)NVENTORY
YOUR CHOICE:
第一步
我玩了很长时间没有意识到，很可能对
game.bin文件进行反向工程更为重要。 我在十六进制编辑器中打开了它，期望看到二进制值。 当我看到这个时，想像一下我的惊讶：
110011111101000000111100110010001110000011001101000000000000110010011101010000001101001111100001111111001100111000000011 ...
从字面上看，这
是一个二进制文件-一个不包含ASCII字符1和0的文本文件。我们知道这很可能是处理器的机器代码，但除了具有4个寄存器，1 KB数据存储器和32个字节外千字节的指令存储器，
对此一无所知 。 因此，我们的首要任务是确定该二进制文件的单位大小（例如，它具有8位尺寸吗？或者，就像某些
古老的体系结构一样，它具有12位或18位尺寸？）
为了找出未知文件的大小，我使用了一个古老的技巧-调整文本框的大小，直到换行符的长度与对齐一致。 此方法非常适用于多种XOR加密文本，未知（未压缩）文件格式以及来自未知CPU的代码：
更改文本框的大小通过此快速检查，我发现此文件的单位大小应为20的除数（对齐窗口的宽度）。 为了找出确切的大小，我迅速编写了一个脚本，寻找长的重复行（假设任何代码都具有重复的定型序列）。 最长的重复行是以下425位块，分别位于43625和44510：
10000011111110000001010100011111110100000101100010111000001001000101000100001000100001010001011000101000000001111111111100010000011110010100100001010100111100000110000010100000101000101000011110001111001101111001010100001010000111110100001010000110010011011110011111000000111011101000000001100000110000111101011010111011000100100010100000111000100011100011000000000101010101100010111000001010000001101010010000000011000001100
由于重复之间的距离为885，我们得出的结论是尺寸应为5位，即 未知的CPU必须具有5位字节。 进步！
我们搜索了5位的打孔卡编码，并迅速确定了
使用Baudot码的旧编码。 实际上-当我们使用在线解码器解码某些片段时，我们得到了可读的文本！
⇩DRAGON⇩HERE⇧；⇧⇧⇩SHE⇩出现⇩要⇩保护⇩某些⇩OF⇩A⇩BOTTLE⇧；＆。＆。＆⇩␀THERE⇩IS⇩A⇩B
LSB Baudot ITA增强的425位代码
然后，我们尝试使用Bodo代码对整个文件进行解码，但是在大约前2万位中，我们出现了垃圾，之后便有了一个可读性强的文本。 这使我们很清楚，文件的第一部分属于“代码”部分，其后是“数据”部分，其中包含常数行。 我们假设机器可能将Bodo代码用于I / O，因此也将常数行以Bodo编码存储在内存中。 为了使代码段更具可读性，我决定使用base-32编码（类似于十六进制编码）对其进行编码，但使用字母0-9a-v对其进行扩展。 这是game.bin文件的样子，第一部分由base-32编码，第二部分由Bodo解码（完整文件发布在此处：
game.b32 ）：
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf1sf24p5f3r9c11qad0f0sf1df26p5f39c21qad0f05f1ff26p5f39c41qad0f08f1df26p5f39c81qad0f0hf1ef26p5f3r1c00qaq15c20qcl0f01f1of27p5f3p3g3psf35c10qal0f02f1nf27p5f3p3g3psf3rf0hf1nf27p5f3f05f16f27p5f3rf84f95101311fl0f510f84907qa40b518447qa40b514f84f95k9m0k9m0k9m0907qa40b511447qa40b512ruougf10f20g0i9g0i910931b320u2u1u0ro9f0o9f0ojh0o9f0o9f0o9f0olj0o9f0o9f0o9f0o9f0o9f0o9f0o9f0o9k1onp0o9f0o9f0o9f0o9f0onf0ot82odi0o9f0o9f0o9f0o9f0o9f0o9f0o9f0olg0o9f0f0gf1df24p5f3r9c11qa835548755
[...]
93e9n59ka8fo87r85g8ui8ml8ed87b9h89u291u82333333333456789abcdb01234567892)%c3BOTTLE OF SOPLICA PIGWOWAENEMY HEALTH:
YOU ATTACK
YOU APPROACH REDFORD.
YOU ENTER THE TAVERN AND APPROACH VALIS.
[...]
为简单起见，我在下面将五位单元称为“字节”。 在团队之间，我们为他们想出了其他名字-我称它们为粗磨，而Zak-骇客。
未知的处理器架构逆向工程
现在我们开始讨论最困难的部分-逆向工程4000字节的代码，这些代码在完全未知的唯一CPU架构上运行。 从代码中可以明显看出，这应该是一组
可变长度的指令，因为不可能在其中找到明显的稳定重复模式。 我花了几个小时，后来我的团队成员Zachary Wade（@ zwad3）开始帮助我。 首先，我开始寻找重复的代码段，建议它们经常使用少量的指令。 我开始将代码分成更短的重复序列，以便于分析。 我想说这是一个严格的过程，但实际上，主要使用了以下模糊算法：
- 我们仔细检查代码，寻找是否经常重复某些代码
- 执行搜索和替换过程，在此重复项旁边插入新行
- 探索所得分割线之间的异同。
- 重复此过程约一个小时...
例如，我发现的模式之一是“ 0f0.f”，其中“。” 表示未知字符。 我打破了这种模式的字符串，并得到了以下内容：
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf
1sf24p5f3r9c11qad0f0sf
1df26p5f39c21qad0f05f
1ff26p5f39c41qad0f08f
1df26p5f39c81qad0f0hf
1ef26p5f3r1c00qaq15c20qcl0f01f
1of27p5f3p3g3psf35c10qal0f02f
非常有帮助！ 在第二和第三行中，我们看到有“ ... p5f3r9c ...”和“ ... p5f39c ...”，这向我们暗示“ r”是一个单字节操作码，即“ ... 5f3”是一个操作码的结尾，而“ 9c ..”是另一个的开始。 在最后两行中，我们看到“ p5f3r1c ...”，这意味着“ 1c ..”是另一个操作码，而“ p3 ...”也是另一个操作码。
我继续以相似的方式一遍又一遍地拆分指令，使用相似块的相似点和不同点来查找可能的指令。 最后，我得到了这样的东西：
pv83
pi70
pk00
p7a0
qfgv
pjg3
f0k
f13
f28
p5f3
pv10
pk40
pn60
f0s
f1s
f24
p5f3
r
9c11
qad0
f0s
f1d
f26
p5f3
9c21
qad0
f05
f1f
我假设“ p”和“ q”是带有三个操作数字节的指令，“ f0”，“ f1”和“ f2”是带有一个操作数的指令，而“ 9c”是带有两个操作数的指令。 但是，我不知道每个指示是什么。
因此，我转到我突出显示的所有“ p”指令的目录，发现当前带有“ p”的最常见指令是“ p5f3”。 此外，从发生的地方看，我发现它始终以“ f0”，“ f1”和“ f2”指令开头。 查看所有操作数“ f0”，“ f1”和“ f2”，我注意到操作数f2始终在4-8范围内。 记住CPU有32 kb的程序存储器用于寻址，需要15位，因此我假设“ f0”，“ f1”和“ f2”将某些地址加载为f2作为高字节。 当我将其中一些地址连接在一起时，我发现它们都完全指向数据部分中常数行的开头。 我发现了
print功能！ 紧随其后的是，“ p5f3”实际上是某种用于打印行或调用的指令。 如果考虑到三字节操作数，则很可能是“调用”。 再次，通过查看“ p”指令，我意识到操作数的三个字节以
直接顺序（little-endian）指示地址，也就是说，操作数的最后一个字节是地址的最高字节。
这是一个巨大的突破！ 我们已经确定了第一条指令。 看到“ f0”和“ f1”在其他地方使用后，我假设它们不是加载地址，而是四个具有直接寻址的5位常量的寄存器（例如，f0加载寄存器0）之一。 这对于p5f3是合乎逻辑的-它为3f5函数（“ print_string”）加载了三个寄存器参数。
我开始编写一个可识别“打印”惯用法（f0x，f1x，f2x，p5f3）的反汇编程序，将打印行的替换内容放入反汇编代码中。 由于程序中的行数很多，因此反汇编的代码很快变得非常易读，并且更容易找出功能块的位置（完整的反汇编的代码位于）：
0: call 38v
4: call 7i
8: call k
c: call a7
g: q vgf
k: call 3gj
o: print 83k # 'SELECT AN OPTION\x0e:\r\n\r\n\x0f\x00'
15: call 1v
19: call 4k
1d: call 6n
1h: print 4ss # '\r\nYOUR CHOICE\x0e: \x0f\x00'
1u: ret
1v: unk 9
20: unk c
21: unk 1
22: unk 1
23: q 0da
27: print 6ds # '\x0e- \x0fGO \x0e(\x0fS\x0e)\x0fOUTH\r\n\x00'
2k: unk 9
2l: unk c
2m: unk 2
2n: unk 1
2o: q 0da
2s: print 6f5 # '\x0e- \x0fGO \x0e(\x0fN\x0e)\x0fORTH\r\n\x00'
39: unk 9
3a: unk c
3b: unk 4
3c: unk 1
3d: q 0da
3h: print 6d8 # '\x0e- \x0fGO \x0e(\x0fE\x0e)\x0fAST\r\n\x00'
3u: unk 9
3v: unk c
40: unk 8
41: unk 1
42: q 0da
46: print 6eh # '\x0e- \x0fGO \x0e(\x0fW\x0e)\x0fEST\r\n\x00'
4j: ret
从这个小代码片段中，我设法弄清了几个方面：“ q0”指令应指示一些条件分支（因为它被用来跳过函数1v中不必要的打印方向），而指令“ 9c11”，“ 9c21”，“ 9c41”，“ “ 9c81”应指示某种AND指令-他们检查设置的位以查看是否允许这些方向（这些指令中使用“ 1”，“ 2”，“ 4”和“ 8”清楚地表明了这一点）。
在接下来的两个小时中，我和Zachary Wade（@ zwad3）整理了各种说明，从而完善和完善了有关它们在做什么的假设。 拥有许多可读的打印语句使我们的工作更加轻松。 我们决定让我们每个人单独编写自己的反汇编程序，以便我们可以按照自己的进度检查说明并分享我们的发现。
代码逆向工程
几个小时后，我开始在拆卸方面取得很大进展。 在检查了适用于用户清单的代码（更具体地说，“ drink”功能以及与之相关的每个处理程序）之后，我们找到了用于从内存中进行保存和加载的指令（不要忘记CPU拥有1 kb的数据内存）。 然后，我们发现一些算术/逻辑（ALU）指令使用内存操作数（例如，“ 9c41”表示“以数据地址1处的值与值4执行与”）。 据此，我们能够在数据存储器中重新创建变量，例如，在[0]中，NPC标识符存储在当前位置，在[6,7]中，存储玩家的当前健康状况（[6]中的低5位，[7中的最早的5位） ]）。 在这个阶段，我从逆向工程指令切换到注释反汇编的代码，并对程序本身进行逆向工程。 以下是我对5位值的有趣表示法：
_start:
call init
L4:
call check_moves
call print_menu
call handle_command
br 4
print_menu:
call print_itemname
print 83k # 'SELECT AN OPTION\x0e:\r\n\r\n\x0f\x00'
call print_moves
call print_npcmenu
call print_itemmenu
print 4ss # '\r\nYOUR CHOICE\x0e: \x0f\x00'
ret
print_moves:
and 0y1, [1]
brz 2k
print 6ds # '\x0e- \x0fGO \x0e(\x0fS\x0e)\x0fOUTH\r\n\x00'
2k: and 0y2, [1]
brz 39
print 6f5 # '\x0e- \x0fGO \x0e(\x0fN\x0e)\x0fORTH\r\n\x00'
39: and 0y4, [1]
brz 3u
print 6d8 # '\x0e- \x0fGO \x0e(\x0fE\x0e)\x0fAST\r\n\x00'
3u: and 0y8, [1]
brz 4j
print 6eh # '\x0e- \x0fGO \x0e(\x0fW\x0e)\x0fEST\r\n\x00'
4j: ret
print_npcmenu:
add 0y0, [0]
brz 6m
sub 0y2, [0]
br<c> 5p
print 7o1 # '\x0e- (\x0fT\x0e)\x0fALK TO \x00'
call print_npcname
call print_crlf
5p: sub 0y1, [0]
brz 6m
print 7n2 # '\x0e- (\x0fF\x0e)\x0fIGHT \x00'
call print_npcname
call print_crlf
6m: ret
print_itemmenu:
print 7nh # '\x0e- (\x0fD\x0e)\x0fRINK\r\n\x00'
print 765 # '\x0e- \x0fSHOW \x0e(\x0fI\x0e)\x0fNVENTORY\r\n\x00'
ret
例如，我们仍然有许多未知的操作码，尽管我们发现“ qa”是零（Branch-on-zero，brz）上的条件分支，但我们无法理解“ qc”是什么（上面表示为br <c>）。 但这足以开始理解程序的逻辑。
实际上，该游戏允许玩家在8×8的地图上移动，随机放置NPC（龙，红牛和人类）。 您可以与任何NPC战斗（即使缺少相应的菜单项，也可以与Valis战斗）。 在战斗中，您可以攻击敌人，造成随机数量的伤害或未命中，之后敌人攻击玩家，也导致随机数量的伤害或未命中。 您还可以选择一个盾牌锁，这样敌人就可以在不造成伤害的情况下错过或击中盾牌。 最后，您可以通过将生命值提高到1000来作弊，但是在这种情况下，隐藏变量（“被欺骗”，地址10）设置为1。如果玩家成功杀死了敌人，则有一个物体从他身上掉下来，通常是一瓶酒精（显然，此游戏不适合儿童）。
玩家必须从中获得旗帜的主要NPC瓦里斯（Valis）具有一个状态机，在该状态机中，玩家要求玩家提供几件物品-一堆红牛饮料（击败红牛敌人时显然会获得），各种混合饮料（例如杜松子酒和补品-要获得它们，您需要击败蓝龙和灰龙，然后混合掉从它们掉落的物体）和配电盘，如果您在游戏中击败另一个NPC人（Redford）或帮助他，则可以获得配电盘。 如果您满足了所有这些长期要求，他将为您提供标志，但前提是变量“被骗”不等于1。也就是说，我们的任务是在不被骗的情况下赢得比赛。 由于我们只有100 HP的生命，就像所有敌人一样，通过通常的通道就不可能击败所有敌人（要获得击败20个对手所需要的所有必要东西）。 必须以某种方式修改RNG，以便敌人始终会错过。
随机数是由类似于某种PRNG（地址37a）的函数生成的，但是它使用的唯一指令在其他任何地方都没有使用，因此我们无法对其进行反向工程。 但是，我们注意到它从内存中的三个地址（[11]，[12]和[13]）加载其状态向量，即其完整状态仅占用15位。 这意味着RNG的周期必须短-长度不超过2 ^ 15 = 32768。
当我们（未成功）尝试撤消RNG实施时，Jay Bosamia（@ jay_f0xtr0t）和Matthew Savage（@thebluepichu）实施了一个利用。 通过简单地连续发送“屏蔽”命令100,000次，我们就可以得到与RNG输出的位相对应的一系列敌人“命中”和“未命中”。 我们确保此序列以32767为周期重复。因此，我们得以集结主要功用-与我们遇到的第一个敌人战斗时，我们关闭了盾牌40次，以重新创建击中和未击中的序列，以较大的周期性序列搜索此序列，然后找出什么时候要盾牌，什么时候要进攻，这样敌人总是会错过。 然后，我们以
谋杀流氓的方式浏览了整个地图，杀死了所有人并收集了他们的战利品。 最后，我们回到瓦利斯（Valis），礼貌地要求我们提供国旗，我们收到了：
DrgnS{m4kin9-v4lis-happy-w1th-n4t1ve-b4ud0t-cpu}
！ 确实是一次真正的冒险。 我仍然不能完全相信，我们是在不到10小时的时间内从二进制字符串和处理器上完全没有文档的工作变成了两个几乎完整的反汇编程序和干净的反汇编代码！ 所有代码都可以在GitHub上找到：
我的反汇编程序 ，
Zachary的反汇编程序 ，
我的原始反汇编代码 ，带
注释的反汇编代码 ，
Matt的Exploit客户端 。