腾讯极客挑战赛丨从“碰撞”到“爆破”,42次尝试终破纪录

渗透技巧 3年前 (2020) admin
556 0 0

各位爱挑战爱学习的coder们,大家千呼万唤的解题思路来啦!(原赛题传送门:腾讯极客挑战赛丨全世界最最最小的程序,等你来battle!

 

x86-64赛道的首破纪录奖励公布后,“阿鹏”同学仅用4天即打破纪录,最终以291字节的成绩,摘得首破纪录奖以及赛道冠军。下面由他带来x86-64赛道的解题思路分享,也欢迎小伙伴们在文末留言,分享自己的解题报告链接。


原理

可以从两个方面来解这道题:

  1. md5碰撞

    直接碰撞输出定值,显然不可行

    利用hashclash工具碰撞每一个bit

  2. 计算本程序的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 entrydq 38h一共8个字节。如果entry_addr只占4字节,高4字节为0,那么可以把b8和这四字节连起来变成mov eax, entry00 00对应的汇编代码为add [rax], al38 00cmp [rax], al,此时rax指向entry_addr,是个合法指针,这两句add 和cmp可以顺利运行。add [rax], al看起来会修改rax指向的内容(入口点),但实际测试起来竟然没有!这也就使得我们可以使用这个trick

这里是一份重叠后的代码,大部分可随意填写的字段都被填入了nop(base addr并没有填入代码,不然还可以多至少4字节)最后用系统调用退出

BITS 64                org     0x10000base:                db      0x7f, "ELF"     ; e_ident                db      2               ; ei_class          ELFCLASS64                db      1               ; ei_data           ELFDAA2LSBstart0:         ; 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_64start1:         ; any 4 bytes                nop                nop                nop                db      0b8h            ; mov eax, entry                dq      start0          ; e_entry                dq      38h             ; e_phoffstart2:         ; 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      0x7start3:         ; any 3 bytes                nop                jmp     start4                dq      0               ; p_offset                dq      $$              ; p_vaddrstart4:         ; any 8 bytes                    nop                nop                nop                nop                nop                nop                jmp     start5                 dq      filesize        ; p_fileszstart5:         ; any 4 bytes                nop                     nop                     jmp     start                 db      0,0,0,0start:                mov     rax, 60                mov     rdi, 42                syscallfilesize        equ $-$$

你可以使用这条命令汇编运行这段代码:

nasm ./test_elf.asm && chmod +x ./test_elf && ./test_elf || echo $?

将会回显exit的参数42。

也可以使用ida进行调试,将会看到运行到db 0而不会报错:

腾讯极客挑战赛丨从“碰撞”到“爆破”,42次尝试终破纪录

这样我们一共有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生成的算法为:

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等,堆栈平衡时可以把这些数据取出来利用:

腾讯极客挑战赛丨从“碰撞”到“爆破”,42次尝试终破纪录

比如我的代码用到了argc的这个1,省去了后面一次1的赋值;最终的md5字符串被写到了argv[0]里,一句pop rdi就获取了一个指针;argv[1]是空指针,刚好可以在最后退出的时候给rdi,省去了xor edi, edi这句清零(题目需要返回值为0)

腾讯极客挑战赛丨从“碰撞”到“爆破”,42次尝试终破纪录

为了方便调试,我另外制作了一份debug版本的汇编源文件,没有重叠任何elf头。可以直接使用gdb进行调试,入口点位于0x10078。

debug版本的汇编代码如下:

我们还需要额外编写一个程序计算输出的前n-1个block的结果,讲这个结果放到iv里。

BITS 64                org     0x10000base:                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_offsetmul_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_bytedata_off equ data - padding_byter_off equ r - padding_bytestart:%define v0 edx%define v1 ebx%define v2 ebp%define v3 edi
%define v0q rdx%define v1q rbx%define v2q rbp%define v3q rdi
%define idxs r13
%define ii eax%define iiq rax%define iib al
%define gg ecx%define ggq rcx%define ff esi%define 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_end4switch1_10: xor ff, v1 cmp iib, 1Fh ja short switch1_20 and ff, v3 lea gg, [iiq + iiq*4+1] jmp short switch1_end3switch1_20: lea gg, [iiq + iiq*2+5]switch1_end4: xor ff, v3 cmp iib, 2Fh jbe short switch1_end2switch1_30: imul gg, ii, 7 mov ff, v3 not ff or ff, v1switch1_end3: xor ff, v2switch1_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_startloop1_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 ; saveloop_start: lodsb div blloc: add al, 30h cmp al, 3ah jl else add al, 39else: 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 syscallr: db 7, 0Ch, 11h, 16h db 5, 9, 0Eh, 14h db 4, 0Bh, 10h, 17h db 6, 0Ah, 0Fh, 15hiv: dd 0x6369ccc1, 0x495eb568, 0xd15445da, 0xaea958a3 padding_byte:filesize equ $-$$align_addr equ $ + (64 - filesize % 64)data equ align_addr - 64padding_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的概率,脸黑。。。)

最终的代码如下:


%define v0 edx%define v1 ebx%define v2 ebp%define v3 edi
%define v0q rdx%define v1q rbx%define v2q rbp%define v3q rdi
%define idxs r13
%define ii eax%define iiq rax%define iib al
%define gg ecx%define ggq rcx%define ff esi%define ffq rsi
padding_size_off equ padding_size - padding_bytedata_off equ data - padding_byter_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 0xa0a60000base: db 0x7f, "ELF" ; e_ident db 2 ; ei_class ELFCLASS64 db 1 ; ei_data ELFDAA2LSBstart0: ; 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_64start1: ; 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_phoffstart2: ; 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 0x7start3: ; 3 bytes db 0xf6, 0xdc, 0 ; any 3 bytes dq 0 ; p_offset dq $$ ; p_vaddr
start4: ; 8 bytes lea idxs, [rsi+r_off] ; 4loop1_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, v1switch1_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 blloc: add al, 30h cmp al, 3ah jl else add al, 39else: 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 syscallr: 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 - 64padding_size equ align_addr-8

最终的输出:

$ nasm ./zero_res.asm && chmod +x ./zero_res && ./zero_res && echo # 编译运行,最后在echo一个回车96935fafb893d3325b244bfe2ca98908$ ./md5 ./zero_res # 这个程序用来计算目标文件n-1个block后的结果,并输出完整程序的md5值0xc718942d, 0x27848216, 0x26f99fc3, 0x0000000096935fafb893d3325b244bfe2ca98908


再分享一篇 x86-64赛道选手TODD在极客群内分享的解题思路(点击阅读),期待更多思路碰撞的火花腾讯极客挑战赛丨从“碰撞”到“爆破”,42次尝试终破纪录

原文始发于微信公众号(我在鹅厂做安全):腾讯极客挑战赛丨从“碰撞”到“爆破”,42次尝试终破纪录

版权声明:admin 发表于 2020年12月9日 下午4:32。
转载请注明:腾讯极客挑战赛丨从“碰撞”到“爆破”,42次尝试终破纪录 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...