【参赛经验分享】实现一个世界上最小的程序来输出自身的MD5 388解法分享
原创【参赛经验分享】实现一个世界上最小的程序来输出自身的MD5 388解法分享
原创
王沛文
发布于 2021-08-30 16:12:27
发布于 2021-08-30 16:12:27
文章被收录于专栏：王沛文的专栏
这题整体思路其实大家应该都很明白了。这里主要是列举一些优化点。elf header相关的做的比较挫，求其他大神思路。
FPU优化k计算
普通md5一般使用预计算的K实现，而64个uint32_t就导致了，额外256字节的空间。为了节省这些空间，可以采用intel的浮点指令fsin
核心代码如下
push 32
fild QWORD [rsp] ;push 32 到ST0
push rsi ; push i 到栈上
fld1 ; push 1 进入ST0 这时候ST1是32
fiadd DWORD [rsp] ; ST0=ST0+i
fsin ; ST0=sin(ST0)
fabs ; ST0=abs(ST0)
fscale ; ST0=ST0*2^ST1
fisttp QWORD [rsp] ; pop K[i] to stack节省系统调用
正常思路中需要readlink找到自身文件，然后用open,read来读取文件内容。
这些完全可以省掉，由于进程执行时，已经完全将自身镜像加载到内存地址。因此可以直接从汇编的基址读取内存，即为文件内容。
避免memcpy
正常md5流程中，需要对message进行padding。因此需要按64字节为一块，一块一块拷贝到临时buffer中单独处理。
这里可以通过将program header中的flags设置为可写，并将memsize设置的比filesize大一些，方便直接在内存中原地做padding。
Program Headers:
Type Offset VirtAddr PhysAddr
FileSiz MemSiz Flags Align
LOAD 0x0000000000000000 0x0000000008048000 0x0000000008048000
0x0000000000000184 0x0000000000000204 RWE 203440c766800880hexifier优化
最终输出md5的时候需要做bin2hex，最初写的c语言版本很简单
for(int i=0;i<16;i++) {
hex_output[i*2] = hexmap[(output[i] & 0xf0) >> 4];
hex_output[i*2+1] = hexmap[output[i] & 0xf];
}后来为了汇编优化，改成了一层循环
for(int i=0;i<32;i++) {
hex_output[i] = hexmap[((output[i>>1] >> (i&1?4:0)) & 0xf)];
}但是无论如何都有一个额外16字节的hexmap
这里汇编也改了很多版，最后使用loop + bextr实现了短小精悍的hexifier
loop是非常好用的循环指令，1字节能够替代dec+jnz
lodsb,stosb也是很好用的读取存储指令，1字节能够替代mov+inc
bextr是二进制扩展中用于提取特定几位的指令用于类似于实现 a = (b >> k) & n
hexifer:
push rsp
pop rsi ;input binary
; 正常是需要32的栈 但是两边长短步调不一致可以只压16字节
push rax
push rax
push rsp
pop rdi ;output hex
mov cl, 32
mov bx, 0x404
hexifer_loop:
lodsb ; al = input[i]
bextr eax, eax, ebx
cmp al, 10
jl number
add al, 0x27
number:
add al, 0x30
stosb ; output[i*2] = al
xor bl, 0x4
jpo hexifer_loop_end
dec rsi
hexifer_loop_end:
loop hexifer_loopSSE指令实现MD5轮转
MD5算法中，每轮block计算都需要对state做一个轮转功能
A = D;
D = C;
C = B;
B = f;每个block计算结束之后还有个add操作
state[0] += A;
state[1] += B;
state[2] += C;
state[3] += D;这些可以用sse指令批量完成
pshufd xmm1, xmm1, 10010011b ; rotate xmm1
paddd xmm0, xmm1 ; add inner state to outer state寻址优化
一般寻址计算/jmp类指令的时候，如果偏移大于1字节，就会变成4字节寻址，因此尽量控制偏移在1字节以内。比如常量可以放在靠文件头的位置，寻址的时候指令会小很多。
padding预计算
由于文件大小是合代码强相关，因此padding的计算和处理可以完全在编译期做，没有必要放到运行时。
64n: 64n.asm calc.sh
echo 'PADDINGSIZE equ 64' > padding.asm
echo 'LOOPSIZE equ 1' >> padding.asm
nasm $< -o $@
./calc.sh $@ > padding.asm
nasm $< -o $@
chmod +x $@#! /bin/bash
size=$(stat --printf="%s" $1)
left=$(echo $size%64| bc)
if [ $left -gt 56 ]; then
PADDINGSIZE=$(echo 64-$left+64 | bc)
else
PADDINGSIZE=$(echo 64-$left | bc)
fi
LOOPSIZE=$(echo "($size+$PADDINGSIZE)/64"| bc)
echo "PADDINGSIZE equ $PADDINGSIZE"
echo "LOOPSIZE equ $LOOPSIZE"可以直接在构建完成后，离线算出padding内容长度等信息，然后生成单独的汇编文件。
在代码中include这个额外生成的汇编文件，最后直接赋值就可以了。
%include "padding.asm"
; buffer+rawlen = 0x80
or BYTE [$$ + FILESIZE], 0x80
mov WORD [rax + PADDINGSIZE - 8], FILESIZE * 8其他
使用64位寄存器(rax/r8之类的)的时候指令需要有64bit prefix，因此尽量不要使用64位寄存器，会额外多一个字节
mov rax, 1 > mov eax, 1
使用寄存器寻址的时候使用非64位寄存器，也会额外多一个字节
mov rsp, 1 < mov 1, esp
完整源码
BITS 64
%include "padding.asm"
%define MD5PADDING 128
%define EXTRA MD5PADDING
org 0x08048000
ehdr: ; Elf64_Ehdr
db 0x7F, "ELF" ; e_ident[EI_MAGO]
db 2 ; e_ident[EI_CLASS] 64bits
db 1 ; e_ident[EI_DATA] little endianness
db 1 ; e_ident[EI_VERSION]
; e_ident[EI_OSABI] System V
; e_ident[EI_ABIVERSION] & padding 7
_start2:
movdqu xmm0, [rbp+INITIAL]
push 32
jmp SHORT _start3
dw 2 ; e_type
dw 0x3e ; e_machine
OO equ $-$$
db 0, 1, 5, 0 ; e_version
dq _start ; e_entry
dq phdr - $$ ; e_phoff
_start:
mov ebp, $$ ; use rbp as offset
; preprocess for input buffer
mov eax, $$ + FILESIZE
jmp SHORT _start2
dw ehdrsize ; e_ehsize
dw phdrsize ; e_phentsize
dw 1 ; e_phnum
ROTS equ $-$$
db 7,12,17,22,5,9 ; e_shentsize
; e_shnum
; e_shstrndx
ehdrsize equ $ - ehdr
db 14,20,4,11,16,23,6,10,15,21
M equ $-$$
db 1, 5, 3, 7 ; e_flags
INITIAL equ $-$$
dd 0x67452301;
dd 0xEFCDAB89;
dd 0x98BADCFE;
dd 0x10325476;
FUNS equ $-$$
f0:
xor esi,edx
xchg eax,edx
and esi,edi
xor eax,esi
ret
f1:
xor edi,esi
xchg eax,esi
and edi,edx
xor eax,edi
ret
f2:
xor esi,edx
xchg eax,esi
xor eax,edi
ret
dw 0
f3:
not edx
or edx,edi
xchg eax,edx
xor eax,esi
ret
_start3:
jmp SHORT _start4
phdr: ; Elf64_Phdr
dd 1 ; p_type
dd 7 ; p_flags
dq 0 ; p_offset
dq $$ ; p_vaddr
dq $$ ; p_paddr
dq FILESIZE ; p_filesz
dq FILESIZE+EXTRA ; p_memsz
; p_align
phdrsize equ $ - phdr + 8 ; start的代码没有对齐8字节 这里就直接加8了
_start4:
padding:
; buffer+rawlen = 0x80
or BYTE [rax], 0x80
mov WORD [rax + PADDINGSIZE - 8], FILESIZE * 8
setup_initial:
; r14 blocK
mov r14d, ebp ; input buffer
mov r13b, LOOPSIZE
; xmm0 is outer state
fild QWORD [rsp]
md5_outer_loop:
; xmm1 is inner state
movdqu xmm1, xmm0
md5_inner_process:
xor esi, esi ; ebx as i inner loop i
md5_inner_loop:
; location rsp use more 1 byte than other
push rsp
pop rax
mov ebx, esi
shr ebx, 4 ; ebx = i / 16
push rsi
movdqu [rax], xmm1 ; copy outer state to stack
mov edi, [rax+4] ; eax = fctn(B,C,D)
mov esi, [rax+8]
mov edx, [rax+12]
lea eax, [rbp+FUNS+rbx*8] ; fctn = FUNS[p]
call rax
pop rsi
push rax ; push fctn(B,C,D) to stack
push rsi
fld1
fiadd DWORD [rsp]
fsin
fabs
fscale
fisttp QWORD [rsp] ; push K[i] to stack
movzx eax, BYTE [rbx+rbp+M] ; eax = m = M[p]
mul esi
add al,BYTE [rbx+rbp+OO] ; o = O[p]
and eax,0xf ; al = g = (m*q+o)%16
mov eax,[r14+rax*4]; eax = X[g]
pop rdx ; edx = K[q+16*p]
add eax, edx
pop rdx ; pop fctn(B,C,D) to rdx
add eax, edx
push rsp
pop rdi
; location rsp use more 1 byte than other
add eax, [rdi]; eax = A + fctn(B,C,D) + K[q+16*p] + X[g]
mov edx, esi ; eax = i / 16 * 4
shr dl, 4
shl dl, 2
mov ecx, esi ; ecx = i % 4
and cl, 0x3
add dl, cl
mov cl,[rbp+rdx+ROTS]
rol eax, cl
add eax, [rdi+4] ; f = B + rol (xxx)
mov [rdi], eax ; A = f
movdqu xmm1, [rdi] ; load new value to xmm1
pshufd xmm1, xmm1, 10010011b ; rotate xmm1
inc esi
cmp esi, 64
jl md5_inner_loop
paddd xmm0, xmm1 ; add inner state to outer state
add r14, 64
dec r13
jnz md5_outer_loop
movdqu [rdi], xmm0 ; mov state back to stack for output
hexifer:
push rsp
pop rsi ;input binary
; 正常是需要32的栈 但是两边长短步调不一致可以只压16字节
push rax
push rax
push rsp
pop rdi ;output hex
mov cl, 32
mov bx, 0x404
hexifer_loop:
lodsb ; al = input[i]
bextr eax, eax, ebx
cmp al, 10
jl number
add al, 0x27
number:
add al, 0x30
stosb ; output[i*2] = al
xor bl, 0x4
jpo hexifer_loop_end
dec rsi
hexifer_loop_end:
loop hexifer_loop
write:
mov al, 1
mov edi, eax
push rsp
pop rsi; hex output buffer
mov dl, 32
syscall
exit:
xor edi, edi ; exit arg 1
mov al, 60 ; sys_exit
syscall
FILESIZE equ $ - $$原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
