各位爱挑战爱学习的coder们,大家千呼万唤的解题思路来啦!(原赛题传送门:腾讯极客挑战赛丨全世界最最最小的程序,等你来battle!)
在x86-64赛道的首破纪录奖励公布后,“阿鹏”同学仅用4天即打破纪录,最终以291字节的成绩,摘得首破纪录奖以及赛道冠军。下面由他带来x86-64赛道的解题思路分享,也欢迎小伙伴们在文末留言,分享自己的解题报告链接。
原理
可以从两个方面来解这道题:
-
md5碰撞
直接碰撞输出定值,显然不可行
利用hashclash工具碰撞每一个bit
-
计算本程序的md5值
md5碰撞
碰撞的方法参考这几篇文章:
能否构造一个含有自己哈希或MD5等的文件(https://www.zhihu.com/question/411191287)、 collisions(https://github.com/corkami/collisions)
碰撞工具:hashclash(https://github.com/cr-marcstevens/hashclash)
目前并没有办法给定一个md5值,生成对应的消息,所以我们不能像编写一个helloworld一样直接输出一个定植,然后在结尾附加字节使得文件的md5值和输出一致。
王小云院士的差分攻击算法可以构造出两个不同的消息具有一样的md5值,并且有hashclash这样的开源工具可以利用。但通过这种方法每128字节才可以碰撞1个bit。我们需要编写程序读取每个128字节中的那一个bit,连起来转换成md5输出,这样数据加代码会使得程序会非常巨大。一开始我对碰撞比较好奇,所以仍然完成了这种方法
计算程序md5值
题目中给的示例即为这种方法。为了结果尽可能小,我们需要从优化算法,定制elf头两方面进行
定制elf头
既然要让程序足够小,就不能用gcc编译了。我们编写汇编代码,直接用nasm编译。nasm的好处在于可以直接生成二进制文件,方便我们定制elf文件头。定制过程中需要大量翻阅elf文件格式的定义,可以在linux教程(https://linux.die.net/man/5/elf)中找到。
elf头很简单,分为三个部分,elf header, program header和section header。其中section header是可选的,可以不要。我们只需要关注运行时的segment即可,于是只需要一个elf header和一个program header。
接下来分析elf header 和program header中的每一个字段,对于没用的字段可以像里面填充代码,以尽可能的节省空间
elf header
elf头包含了elf程序整体的一些信息。经过大量的测试,不可随意修改的字段包括
-
file_identification: magic nuber,固定为’x7fELF’
-
ei_class: 64位程序
-
ei_data: LSB字节序
-
e_type: 可执行文件
-
e_machine: x86_64
-
e_entry: 入口点
-
e_phoff: program header的文件偏移
-
e_ehsize: elf头大小,固定为0x40
-
e_phentsize: program header的大小,固定为0x38
-
e_phnum: program header数量,只有1个
-
e_shnum: section header数量,没有
剩余字段都是可以填任意值的。由于没有section,e_shentsize(section header大小)这个字段也可以填为0。
program header
程序头描述了segment的属性。我们只需要1个segment即可。不可随意修改的字段包括
-
p_type: LOAD,这个segment需要load进内存。
-
p_flags: 7 这个segment需要可读可写可执行。这个字段由32位整形存储。经过测试只需要最低三个bit为1即可,其余bit可以随意(更进一步测试,对于内存权限而言,只要可执行必定可读,所以只需要执行和写对应的bit为1即可,如果需要非常极限的利用可以考虑这一点),因此p_flags的第一个字节的低3bit需要为1.
-
p_offset: 该segment与文件中的偏移。整个文件我们都要load进内存计算,因此偏移为0
-
p_vaddr: load到的虚拟地址位置,填入程序的基地址。这里只需要合法,低12bit需要为0,基地址不能特别大。在我本地测试下来任何小于0x7ffff0000000,低12bit为0的地址都可以作为基地址
-
p_filesz: load的大小,填写文件大小(实际测试下来这个字段填写filesize-0x1000范围内都可以,但是不是很容易利用上,所以没考虑在内)
-
p_memsz的高4byte: 这个字段描述内存大小,测试下来只有低4字节可以随意填写,第5字节在题目的环境上只能填0-f,而我本地的环境小于0x7ffffff00000左右都不影响运行。为了适用性更广我们只考虑使用它的低4字节
剩余部分都是可以填任意内容的了
接下来我们分析一下elf header末尾的字段和program header开头的字段,考虑重叠两部分。由于p_type必须要为dd 1,只有e_phnum这里开始可以重叠。刚好e_shnum填写7并不影响,于是program header的偏移地址就为0x38
总体算下来,我们一共有10+4+12+3+8+4字节可以填写任意字节。如果填代码的话,需要用jmp将他们连起来。分析一下10 和4这两个block,他们中间间隔了4个字节。我们可以吧这四个字节当作一条汇编指令的data部分(例如mov eax, 0的字节码为b8 00 00 00 00),这样省去了使用jmp连接两个block,又节省了一个字节。
同理,4和12这两个block中间间隔了dq entry
和dq 38h
一共8个字节。如果entry_addr
只占4字节,高4字节为0,那么可以把b8
和这四字节连起来变成mov eax, entry
。00 00
对应的汇编代码为add [rax], al
,38 00
为cmp [rax], al
,此时rax指向entry_addr
,是个合法指针,这两句add 和cmp可以顺利运行。add [rax], al
看起来会修改rax指向的内容(入口点),但实际测试起来竟然没有!这也就使得我们可以使用这个trick
这里是一份重叠后的代码,大部分可随意填写的字段都被填入了nop(base addr并没有填入代码,不然还可以多至少4字节)最后用系统调用退出
BITS 64
org 0x10000
base:
db 0x7f, "ELF" ; e_ident
db 2 ; ei_class ELFCLASS64
db 1 ; ei_data ELFDAA2LSB
start0: ; any 10 bytes
db 090h, 090h, 090h, 090h, ; nop
db 090h, 090h, 090h, 090h, ; nop
db 090h
db 0b8h ; mov eax, 0x3e0002
dw 2 ; e_type ET_EXEC
dw 3Eh ; e_machine EM_X86_64
start1: ; any 4 bytes
nop
nop
nop
db 0b8h ; mov eax, entry
dq start0 ; e_entry
dq 38h ; e_phoff
start2: ; any 12 bytes
db 090h, 090h, 090h, 090h, 090h, ; nop
db 090h, 090h, 090h, 090h, 090h, ; nop
jmp start3
dw 40h ; e_ehsize
dw 38h ; e_phentsize
dw 1 ; e_phnum
dw 0 ; e_shentsize
db 0x7
start3: ; any 3 bytes
nop
jmp start4
dq 0 ; p_offset
dq $$ ; p_vaddr
start4: ; any 8 bytes
nop
nop
nop
nop
nop
nop
jmp start5
dq filesize ; p_filesz
start5: ; any 4 bytes
nop
nop
jmp start
db 0,0,0,0
start:
mov rax, 60
mov rdi, 42
syscall
filesize equ $-$$
你可以使用这条命令汇编运行这段代码:
nasm ./test_elf.asm && chmod +x ./test_elf && ./test_elf || echo $?
将会回显exit的参数42。
也可以使用ida进行调试,将会看到运行到db 0
而不会报错:
这样我们一共有10+4+12+3+8+4个字节可以任意填写,base addr中有32-12=20
bit可以拿来爆破(为了使指针正常赋值,我们的基地址需要小于uint32的范围)
减去jmp和重叠的mov指令,可以被填写为代码的字节数为9+3+10+6+2字节
在向elf头填代码的时候也比较玄学,由于可以填写的空间是固定的,代码的顺序也是有要求的,所以不一定所有的地方都能填上代码,剩余的部分可以拿来爆破
优化md5算法
接下来我们考虑优化md5算法。
首先我在GitHub上找到了一份比较好的md5源码md5.c(https://gist.github.com/creationix/4710780),它没有内联任何代码,没有展开循环,代码本身比较小,我们基于它编写我们的代码。我们用gcc编译后,照着写一遍汇编,代码的体积很轻松的来到五百多字节。接下来我们需要用汇编完整重写一遍。
md5循环优化
md5使用了md结构,类似分组密码,讲消息padding到512bit,padding时先补一个1bit,然后补若干个0bit到448,最后64bit填写原消息的bit数。
接下来对每一个512bit的block计算4个int值,加到iv上(iv初始值固定)。总体为2层循环。
优化的思路为把iv放到最后一个block,这样前面block的内容是确定的,他们算出来的结果也是确定的,把这个结果作为iv,计算最后一个block的hash,这样可以省去一层循环。
这样的弊端在于程序的大小存在瓶颈。如果程序大小使得iv值刚好穿越最后一个block时,即一部分iv在上一个block,我们是没办法利用的,此时需要补充到刚好极限的大小。程序大小需要在[k*64+0x10:k*64+0x37]
这个范围(最小值为iv刚好为多出去的0x10个字节,最后一个block都是iv,最大值为刚好加上0x80的padding字节,8字节的size字节后正好为512bit),也就是如果我们的程序长度为336这样的5*64+16
的大小时,下一步就要减去0x10+8+1=25字节才是有意义的,这也就是为什么会卡在400,336这些瓶颈。
rbox
md5有一个rbox(rotate box),简单观察一下发现有16字节。但并不能找到一条从i到r[i]的简洁的公式,所以还是要打表,只是从64字节的表变成16字节的表,具体为r[i/16][i%4]
kbox
kbox打表太占空间了。我找了一些md5资料,kbox生成的算法为:
k[i] = (uint32_t)(floor(fabs(sin(i+1)*0x100000000)));
我们可以先生成k表,计算时打表,也可以计算md5时计算k表的值。我这里选择了后一种方法,感觉要比打表小一点。
计算浮点数我们使用x87 fpu指令,80×87的教程参考80×87 Instruction Set (x87 – Pentium)(https://www2.math.uni-wuppertal.de/~fpf/Uebungen/GdR-SS02/opcode_f.html)
fsin计算sin值,乘以0x100000000的操作可以用push 0x4f800000和fmul dword[rsp],fabs指令计算绝对值。最后floor的地方,这份资料里需要用fldcw设置fpu的控制字,然后再fistp保证为floor。后面参考了另一份资料FISTTP — Store Integer with Truncation(https://www.felixcloutier.com/x86/fisttp),fisttp在将浮点数转为整形时就是floor转换,从而不必再设置控制字
计算k表:
inc ii ; eax
push iiq ; rax
fild dword [rsp]
fsin
push 0x4f800000
fmul dword [rsp]
fabs
fisttp qword [rsp]
pop ffq ; rsi
输出结果
输出需要将一个字节的低4bit和高4bit分离然后tohex。我们使用div bl
(bl值为0x10),它将ax寄存器除以0x10,余数(低4bit)放到ah, 商(高4bit)放到al,根据范围加上不同的值转ascii。操作完al后eax右移,ah(低4bit)就去到了al,此时根据指针奇偶性,还需跳转到内层循环的开头操作一遍低4bit。然后用loop指令完成外层的0x10次循环
最后用系统调用write(1, buf, 32)输出结果,exit(0)退出。(我一开始以为结尾的回车是必要的,所以还构造了一个0x0a字节,输出33字节)
编写汇编代码
接下来对照c源代码编写我们的汇编代码。编写时需要代码尽量小,原则上时利用尽量短的代码,用到的一些trick:
-
取数据/存数据考虑使用lodsb/lodsw/lodsd,stosb/stosw/stosd这类短的指令
-
mov可以考虑换成xchg,当xchg的一个寄存器为eax时xchg的长度为1字节
-
一般情况下指针寄存器用64为寄存器更短(形如mov eax, [rax]),直接使用的寄存器用32位寄存器更短(形如mov eax, ebx)。由于我们的内存空间在uint32范围内,所以用64位寄存器或32位寄存器效果来说一样
-
分配寄存器的时候,频率最高的寄存器用eax,也就是下标寄存器用eax。我最开始用ecx存放下标,调整一下使用eax后发现少了1个字节
-
md5的switch内尽可能复用代码。md5算法分为4个switch,根据i的值进行不同操作。先写了一份基础代码后,发现一些指令在不同分支内都用到了,那就可以提取出来放在开头执行。对于两个不同分支的也可以服用,只要最终结果等价就行。(这里的优化是比较难的,需要考虑每条指令的关系,尽可能的复用)
-
尽可能利用已有的东西。刚load完的程序,所有寄存器出了rip和rsp都设置为0,rsp指向的内容是固定的,argc, argv,envp等,堆栈平衡时可以把这些数据取出来利用:
比如我的代码用到了argc的这个1,省去了后面一次1的赋值;最终的md5字符串被写到了argv[0]里,一句pop rdi就获取了一个指针;argv[1]是空指针,刚好可以在最后退出的时候给rdi,省去了xor edi, edi
这句清零(题目需要返回值为0)
为了方便调试,我另外制作了一份debug版本的汇编源文件,没有重叠任何elf头。可以直接使用gdb进行调试,入口点位于0x10078。
debug版本的汇编代码如下:
我们还需要额外编写一个程序计算输出的前n-1个block的结果,讲这个结果放到iv里。
BITS 64
org 0x10000
base:
db 0x7f, "ELF" ; e_ident
db 2 ; ei_class ELFCLASS64
db 1 ; ei_data ELFDAA2LSB
db 1 ; ei_version EV_CURRENT
db 0 ; ei_osabi ELFOSABI_NONE
db 0 ; ei_abiversion 0
dd 0
db 0,0,0
dw 2 ; e_type ET_EXEC
dw 3Eh ; e_machine EM_X86_64
dd 1 ; e_version EV_CURRENT
dq start ; e_entry
dq 40h ; e_phoff
dq 0
dd 0 ; e_flags
dw 40h ; e_ehsize
dw 38h ; e_phentsize
dw 1 ; e_phnum
dw 0 ; e_shentsize
dw 0 ; e_shnum
dw 0 ; e_shstrndx
program header
dd 1 ; p_type PT_LOAD
dd 7 ; p_flags PF_X | PF_W | PF_R
dq 0 ; p_offset
mul_val: dq 0x10000 ; p_vaddr
dq 0x10000 ; p_paddr
dq filesize ; p_filesz
dq 0xffffffff ; p_memsz upto 0xffffffff
dq 1000h ; p_align
padding_size_off equ padding_size - padding_byte
data_off equ data - padding_byte
r_off equ r - padding_byte
start:
v0 edx
v1 ebx
v2 ebp
v3 edi
v0q rdx
v1q rbx
v2q rbp
v3q rdi
idxs r13
ii eax
iiq rax
iib al
gg ecx
ggq rcx
ff esi
ffq rsi
mov esi, padding_byte - 0x10
push rsi
lodsd
xchg eax, v0
lodsd
xchg eax, v1
lodsd
xchg eax, v2
lodsd
xchg eax, v3
mov byte [rsi], 0x80
mov word [rsi + padding_size_off], filesize * 8
lea idxs, [rsi + r_off]
loop1_start:
switch1_0:
mov ff, v2
cmp iib, 0xF
ja short switch1_10
xor ff, v3
and ff, v1
mov gg, ii
jmp short switch1_end4
switch1_10:
xor ff, v1
cmp iib, 1Fh
ja short switch1_20
and ff, v3
lea gg, [iiq + iiq*4+1]
jmp short switch1_end3
switch1_20:
lea gg, [iiq + iiq*2+5]
switch1_end4:
xor ff, v3
cmp iib, 2Fh
jbe short switch1_end2
switch1_30:
imul gg, ii, 7
mov ff, v3
not ff
or ff, v1
switch1_end3:
xor ff, v2
switch1_end2:
and gg, 0Fh
add v0, dword [idxs + ggq * 4 + data-r] ; w[g]
add v0, ff ; f
inc ii
push iiq
fild dword [rsp]
fsin
push 0x4f800000
fmul dword [rsp]
fabs
fisttp qword [rsp]
pop ffq
add v0, ff
dec ii
mov ff, ii
shr ff, 4
and iib, 3
add iiq, idxs
xchg ii, v3 ; switch eax, ecx
mov cl, byte [v3q + ffq * 4] ; cl is v3b
rol v0, cl
add v0, v1
xchg ii, v0
xchg ii, v1
xchg ii, v2
xchg ii, v3 ; switch back
pop iiq
cmp iib, 40h
jnz short loop1_start
loop1_end:
pop rsi
add [rsi], v0
add [rsi+4], v1
add [rsi+8], v2
add [rsi+12], v3
rax = 0x40
rdi < 0x10
rsi = buffer
ecx, edx, ebx, ebp filled
pop rdx ; rdx = 1
mov cl, 0x10
mov bl, cl
pop rdi ; argv[0]
push rdi ; save
loop_start:
lodsb
div bl
loc:
add al, 30h
cmp al, 3ah
jl else
add al, 39
else:
stosb
shr eax, 8
test edi, edx
jnz loc
loop loop_start
pop rsi
mov edi, edx ; edi = 1
xchg eax, edx ; eax = 1
mov dl, 32
syscall
mov al, 60
pop rdi
syscall
r:
db 7, 0Ch, 11h, 16h
db 5, 9, 0Eh, 14h
db 4, 0Bh, 10h, 17h
db 6, 0Ah, 0Fh, 15h
iv: dd 0x6369ccc1, 0x495eb568, 0xd15445da, 0xaea958a3
padding_byte:
filesize equ $-$$
align_addr equ $ + (64 - filesize % 64)
data equ align_addr - 64
padding_size equ align_addr-8
爆破一个iv为0
经过很长时间的优化,程序的大小来到了297字节,此时已经找不到什么优化的办法了。看到和最终的结果272之差6个字节了,可以开始考虑爆破了。我们可以假设最后一个iv的值为0,这样直接用初始化的0字节,省去4字节。
最终输出的时候我是用指针的奇偶性来判断内层循环的。如果假设hash值的每个字节的低4bit都不全为0,那可以用shr eax, 8的结果(不为0则跳转,完成输出的内层循环,第二次shr后eax为0,不跳转),这里的概率为(15/16)**16,为百分之35左右
此时头中有3个任意字节没办法放代码,加上baseaddr的20bit,一共48bit拿来爆破,超过了需要的32bit的空间,理论上时可行的。编写好最终的结果后,编写爆破程序开始爆破。在我的笔记本版的i9上花了不到1个小时爆破出了8个结果(其中第8个才中了百分之35的概率,脸黑。。。)
最终的代码如下:
v0 edx
v1 ebx
v2 ebp
v3 edi
v0q rdx
v1q rbx
v2q rbp
v3q rdi
idxs r13
ii eax
iiq rax
iib al
gg ecx
ggq rcx
ff esi
ffq rsi
padding_size_off equ padding_size - padding_byte
data_off equ data - padding_byte
r_off equ r - padding_byte
9 4 12 3 8 5
5+4+1 10
3+1 4
1+3+6+2 12
4+2+2 8
1+2+2 5
BITS 64
org 0xa0a60000
base:
db 0x7f, "ELF" ; e_ident
db 2 ; ei_class ELFCLASS64
db 1 ; ei_data ELFDAA2LSB
start0: ; 10 bytes
mov esi, padding_byte - 0xC ; 5
push rsi ; 1
lodsd ; 1
xchg eax, v0 ; 1
lodsd ; 1
db 0bbh ; mov ebx,imm32 ; 1
dw 2 ; e_type ET_EXEC
dw 3Eh ; e_machine EM_X86_64
start1: ; 4 bytes
xchg eax, v1 ; 1
lodsd ; 1
xchg eax, v2 ; 1
db 0b8h ; mov eax ; 1
jmp start3
dq start0 ; e_entry
dq 38h ; e_phoff
start2: ; 12 bytes
mov byte [rsi], 0x80 ; 3
mov word [rsi + padding_size_off], filesize * 8 ; 6
xchg eax, ecx ; 1
jmp start4 ; 2
dw 40h ; e_ehsize
dw 38h ; e_phentsize
dw 1 ; e_phnum
dw 0 ; e_shentsize
db 0x7
start3: ; 3 bytes
db 0xf6, 0xdc, 0 ; any 3 bytes
dq 0 ; p_offset
dq $$ ; p_vaddr
start4: ; 8 bytes
lea idxs, [rsi+r_off] ; 4
loop1_start:
mov ff, v2 ; 2
jmp start5 ; 2
dq filesize ; p_filesz
5 bytes
start5:
cmp iib, 0xF ; 2
jmp start ; 2
db 0,0,0,0
start:
loop1_start:
switch1_0:
mov ff, v2
cmp iib, 0xF
ja short switch1_10
xor ff, v3
and ff, v1
mov gg, ii
jmp short switch1_end4
switch1_10:
xor ff, v1
cmp iib, 1Fh
ja short switch1_20
and ff, v3
lea gg, [iiq + iiq*4+1]
jmp short switch1_end3
switch1_20:
lea gg, [iiq + iiq*2+5]
switch1_end4:
xor ff, v3
jmp short switch1_end2
cmp iib, 2Fh
jbe short switch1_end2
switch1_30:
imul gg, ii, 7
mov ff, v3
not ff
or ff, v1
switch1_end3:
xor ff, v2
switch1_end2:
and gg, 0Fh
add v0, dword [idxs + ggq * 4 + data-r] ; w[g]
add v0, ff ; f
inc ii
push iiq
fild dword [rsp]
fsin
push 0x4f800000
fmul dword [rsp]
fabs
fisttp qword [rsp]
pop ffq
add v0, ff
dec ii
mov ff, ii
shr ff, 4
and iib, 3
add iiq, idxs
xchg ii, v3 ; switch eax, ecx
mov cl, byte [v3q + ffq * 4] ; cl is v3b
rol v0, cl
add v0, v1
xchg ii, v0
xchg ii, v1
xchg ii, v2
xchg ii, v3 ; switch back
pop iiq
cmp iib, 40h
jnz short loop1_start
loop1_end:
pop rsi
add [rsi], v0
add [rsi+4], v1
add [rsi+8], v2
mov [rsi+12], v3
rax = 0x40
rdi < 0x10
rsi = buffer
ecx, edx, ebx, ebp filled
pop rdx ; rdx = 1
mov rcx, 0x10
push 0x10
pop rcx
mov cl, 0x10
mov bl, 0x10
mov bl, cl
pop rdi ; argv[0]
push rdi
loop_start:
lodsb
div bl
loc:
add al, 30h
cmp al, 3ah
jl else
add al, 39
else:
stosb
shr eax, 8
test edi, edx
jnz loc
loop loop_start
pop rsi
mov edi, edx ; edi = 1
xchg eax, edx ; eax = 1
mov dl, 32
syscall
mov al, 60
pop rdi
syscall
r:
db 7, 0Ch, 11h, 16h
db 5, 9, 0Eh, 14h
db 4, 0Bh, 10h, 17h
db 6, 0Ah, 0Fh, 15h
iv: dd 0xc718942d, 0x27848216, 0x26f99fc3,
padding_byte:
filesize equ $-$$
align_addr equ $ + (64 - filesize % 64)
data equ align_addr - 64
padding_size equ align_addr-8
最终的输出:
echo # 编译运行,最后在echo一个回车 nasm ./zero_res.asm && chmod +x ./zero_res && ./zero_res &&
96935fafb893d3325b244bfe2ca98908
# 这个程序用来计算目标文件n-1个block后的结果,并输出完整程序的md5值 ./md5 ./zero_res
0xc718942d, 0x27848216, 0x26f99fc3, 0x00000000
96935fafb893d3325b244bfe2ca98908
再分享一篇 x86-64赛道选手TODD在极客群内分享的解题思路(点击阅读),期待更多思路碰撞的火花
原文始发于微信公众号(我在鹅厂做安全):腾讯极客挑战赛丨从“碰撞”到“爆破”,42次尝试终破纪录