各位爱挑战爱学习的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字节）最后用系统调用退出
代码语言：javascript复制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 $-$$你可以使用这条命令汇编运行这段代码：
代码语言：javascript复制nasm ./test_elf.asm && chmod x ./test_elf && ./test_elf || echo $?也可以使用ida进行调试，将会看到运行到db 0而不会报错：
这样我们一共有10 4 12 3 8 4个字节可以任意填写，base addr中有32-12=20bit可以拿来爆破（为了使指针正常赋值，我们的基地址需要小于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生成的算法为：
代码语言：javascript复制k[i] = (uint32_t)(floor(fabs(sin(i 1)*0x100000000)));我们可以先生成k表，计算时打表，也可以计算md5时计算k表的值。我这里选择了后一种方法，感觉要比打表小一点。
计算浮点数我们使用x87 fpu指令，80x87的教程参考80x87 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表：
代码语言：javascript复制 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里。
代码语言：javascript复制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:
�fine v0 edx
�fine v1 ebx
�fine v2 ebp
�fine v3 edi
�fine v0q rdx
�fine v1q rbx
�fine v2q rbp
�fine v3q rdi
�fine idxs r13
�fine ii eax
�fine iiq rax
�fine iib al
�fine gg ecx
�fine ggq rcx
�fine ff esi
�fine 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的概率，脸黑。。。）
最终的代码如下：
代码语言：javascript复制
�fine v0 edx
�fine v1 ebx
�fine v2 ebp
�fine v3 edi
�fine v0q rdx
�fine v1q rbx
�fine v2q rbp
�fine v3q rdi
�fine idxs r13
�fine ii eax
�fine iiq rax
�fine iib al
�fine gg ecx
�fine ggq rcx
�fine ff esi
�fine 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最终的输出：
代码语言：javascript复制$ nasm ./zero_res.asm && chmod x ./zero_res && ./zero_res && echo # 编译运行，最后在echo一个回车
96935fafb893d3325b244bfe2ca98908
$ ./md5 ./zero_res # 这个程序用来计算目标文件n-1个block后的结果，并输出完整程序的md5值
0xc718942d, 0x27848216, 0x26f99fc3, 0x00000000
96935fafb893d3325b244bfe2ca98908再分享一篇 x86-64赛道选手TODD在极客群内分享的解题思路（点击阅读），期待更多思路碰撞的火花
