顶级极客技术挑战赛，你敢来挑战吗？| 大神登峰造极
大家好，我是極客君，去年鵝廠內(nèi)部極客圈舉辦了第二次極客大賽，題目如下：
"實(shí)現(xiàn)一個(gè)世界上最小的程序來(lái)輸出自身的MD5"
作為極客圈一員的我也參加了比賽，比賽競(jìng)爭(zhēng)很激烈，為了爭(zhēng)奪一個(gè)字節(jié)的優(yōu)勢(shì)，大家都拿出自己的絕活，比賽重新刷新了我對(duì)匯編的認(rèn)知和對(duì)程序運(yùn)行原理理解，昨天分享一個(gè)典型的樸素解法：
最小MD5挑戰(zhàn)賽，你敢來(lái)戰(zhàn)嗎？
但這篇"菜鳥(niǎo)"樸素解法,已經(jīng)讓有些人看得不知所云，其實(shí)要完全理解其中一些技巧，可能需要實(shí)際操作一下，計(jì)算機(jī)實(shí)踐很重要，看不懂也可以做個(gè)吃瓜群眾，長(zhǎng)長(zhǎng)見(jiàn)識(shí)也可以。
上篇文章說(shuō)過(guò)點(diǎn)贊在看超過(guò)20，今天就放出大神解法，我相信此法一出，評(píng)論區(qū)會(huì)一片驚呼：
A：天啊，這個(gè)男人不得了，他做到了最短！
B：神仙打架
C :??膜拜第一名大佬，各種技巧溜得飛起，學(xué)習(xí)了
? ? ?
D :? 跪著看完了，厲害！
E? :??降維打擊
...
文章稍微有點(diǎn)長(zhǎng)，不想慢慢看完，可以直接拉到底，接下來(lái)該你上場(chǎng)表演了。
開(kāi)闊眼界的大神解法
299字節(jié)打印自身的MD5，NO.1（冠軍）
用 nasm 寫(xiě)匯編，手動(dòng)構(gòu)造 ELF 格式文件。ELF 文件分為三部分：
[A] [B] [C]其中 A 的長(zhǎng)度為 64 的倍數(shù)，B+C 的長(zhǎng)度 <= 55。
A+B 包括：ELF 文件頭、計(jì)算 MD5 一個(gè) block 的代碼、輸出 16 進(jìn)制的代碼。盡可能壓縮這部分代碼的大小。
C 是對(duì) A 計(jì)算 MD5（不加 padding）的中間結(jié)果，13 字節(jié)。（為什么是 13 不是 16？因?yàn)樽擦?3 個(gè)字節(jié)，詳見(jiàn)下文。）
思路
大的方向無(wú)非就這些：
撞：理想情況下，我們的程序就簡(jiǎn)單執(zhí)行一條輸出指令，撞出一個(gè)滿足?MD5(print(md5_string)) == md5_string?的?md5_string。
利用外部能力：調(diào)用外部程序，或者利用 Linux 內(nèi)核中的 MD5 實(shí)現(xiàn)。
算：程序讀取自身，計(jì)算 MD5 并輸出。
如果考慮撞，MD5 有 128 位，2 的 128 次方據(jù)說(shuō)已經(jīng)超過(guò)了宇宙中基本粒子的數(shù)量，窮舉顯然是不行的，只能用密碼學(xué)的方法構(gòu)造。鑒于本文作者的密碼學(xué)知識(shí)接近于 0，就不賣(mài)弄了，不過(guò)據(jù)群里的同學(xué)說(shuō)這樣構(gòu)造出來(lái)的文件會(huì)很大，并不適合本次比賽。
而利用外部能力的路已經(jīng)被堵死，不允許 fork，也不允許使用 socket，此路不通。
看來(lái)可行的方法就是算，成了一個(gè)純工程優(yōu)化問(wèn)題。這一塊正好本文作者有點(diǎn)經(jīng)驗(yàn)，研究生方向是編譯器，做的題目是 code size reduction。
MD5 算法
第一想法是去抄開(kāi)源代碼，我一開(kāi)始抄了 Linux kernel 里的 MD5 實(shí)現(xiàn)，但后來(lái)發(fā)現(xiàn)并不適合本次比賽。開(kāi)源的 MD5 實(shí)現(xiàn)為了性能大都做了人工循環(huán)展開(kāi)和常量預(yù)計(jì)算，會(huì)把代碼撐得很大。不如直接照著 MD5 算法的偽碼來(lái)寫(xiě)，維基百科上面的偽代碼寫(xiě)得夠清晰，就它了。
簡(jiǎn)單描述：
需要先對(duì)原始數(shù)據(jù)做 padding，將它的長(zhǎng)度變成 64 字節(jié)的整數(shù)倍，MD5 算法在 64 字節(jié)長(zhǎng)的 block 上進(jìn)行。
具體 padding 方法：在原始數(shù)據(jù)后增加一字節(jié) 0x80，然后再增加若干個(gè) 0，直到總長(zhǎng)度為 64 的倍數(shù)，并且最后至少留出 8 個(gè)字節(jié)的位置，用于填寫(xiě) little endian 編碼的原始數(shù)據(jù)總長(zhǎng)度（按位計(jì)，即字節(jié)數(shù)乘以 8）。
Padding 完成后，對(duì)每個(gè) 64 字節(jié) block 進(jìn)行計(jì)算，block 的計(jì)算方法參考下一節(jié)的代碼。每一輪計(jì)算結(jié)束后更新 16 字節(jié)的 MD5 狀態(tài)，最后一輪計(jì)算完成后，將狀態(tài)用 16 進(jìn)制打印出來(lái)。
C++ 實(shí)現(xiàn)
以下是一個(gè) C++ 寫(xiě)的完整實(shí)現(xiàn)，在不太損失可讀性的前提下用較簡(jiǎn)短的寫(xiě)法，不考慮性能：
#include <cmath> #include <cstdio> #include <cstring> #include <memory>using namespace std;static const uint8_t SHIFT[] = {7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21};// 注：為了省事，下面代碼假設(shè)了 CPU 是 little endian static void compute_md5(void* result, const void* orig_data, size_t orig_size) {uint32_t* hash = reinterpret_cast<uint32_t*>(result);hash[0] = 0x67452301;hash[1] = 0xefcdab89;hash[2] = 0x98badcfe;hash[3] = 0x10325476;// 計(jì)算padding后的總長(zhǎng)度size_t padded_size;if (orig_size % 64 > 55) {padded_size = orig_size / 64 * 64 + 128;} else {padded_size = orig_size / 64 * 64 + 64;}// 增加paddingstd::unique_ptr<char[]> padded_data(new char[padded_size]);memset(padded_data.get(), 0, padded_size);memcpy(padded_data.get(), orig_data, orig_size);padded_data[orig_size] = 0x80;*(uint64_t*)(padded_data.get() + padded_size - 8) = orig_size * 8;// 開(kāi)始計(jì)算for (const uint32_t* data = (const uint32_t*)padded_data.get();padded_size >= 64; data += 16, padded_size -= 64) {uint32_t a = hash[0];uint32_t b = hash[1];uint32_t c = hash[2];uint32_t d = hash[3];for (int i = 0; i < 64; ++i) {uint32_t f, g;if (i < 16) {f = ((c ^ d) & b) ^ d; // 等價(jià)于 (b & c) | ((~b) & d);g = i;} else if (i < 32) {f = ((b ^ c) & d) ^ c; // (d & b) | ((~d) & c);g = 5*i + 1;} else if (i < 48) {f = b ^ c ^ d;g = 3*i + 5;} else {f = c ^ (b | (~d));g = 7*i;}uint32_t K = static_cast<uint32_t>(fabs(sin(i + 1)) * 4294967296.0);f += a + K + data[g % 16];int shift_val = SHIFT[(i / 16) * 4 + (i % 4)];f = (f << shift_val) | (f >> (32 - shift_val));a = d;d = c;c = b;b += f;}hash[0] += a;hash[1] += b;hash[2] += c;hash[3] += d;} }int main(int argc, char** argv) {FILE* fp = fopen(argv[0], "rb");if (fp == nullptr) {perror("Failed to open file");return 1;}char buffer[65536];size_t len = fread(buffer, 1, sizeof(buffer), fp);fclose(fp);unsigned char result[16];compute_md5(result, buffer, len);for (int i = 0; i < 16; ++i) {printf("%02x", result[i]);}putchar('\n');return 0; }這個(gè)版本用?g++ -Os?編譯出來(lái)，strip 一下，不做其他處理，大約 14 KB。
用匯編改寫(xiě)
接下來(lái)的任務(wù)就是想辦法用匯編重寫(xiě)這個(gè) 14 KB 的程序，將代碼壓縮到最小。
手動(dòng)構(gòu)造 ELF
手動(dòng)構(gòu)造 ELF 網(wǎng)上能找到不少例子，例如：Smallest executable program (x86-64)。它使用 nasm 構(gòu)造了一個(gè)最小的 64 位 ELF，先照著它搭個(gè)架子。
這個(gè)例子提供了兩個(gè)思路：(1) ELF 頭部有很多不重要的字段，可以用來(lái)放代碼或數(shù)據(jù) (2) ehdr 的最后 8 個(gè)字節(jié)和 phdr 的最前面 8 個(gè)字節(jié)可以重合。
借助 nasm 可以很容易地將 file size 硬編碼到代碼里。還有?%define、%if?等也可以幫助我們省很多事。
手動(dòng)構(gòu)造 ELF 以后，也不再需要再去讀文件，加載到內(nèi)存里的地址完全受我們控制了，直接去讀。
系統(tǒng)調(diào)用
沒(méi)有 C 庫(kù)以后，系統(tǒng)調(diào)用需要自己寫(xiě)。x86-64 有 syscall 指令，發(fā)起系統(tǒng)調(diào)用很方便。
入?yún)?#xff1a;
eax = 系統(tǒng)調(diào)用號(hào)，可以在?/usr/include/asm/unistd_64.h?文件中找到
rdi, rsi, rdx, r10, r8, r9 分別為第 1 至 6 個(gè)參數(shù)
出參：
rax = 返回值（如果失敗，返回 -errno）
rcx, r11 被破壞（它們分別被 syscall 指令用來(lái)保存返回地址和 rflags）
其他寄存器的值保留
假設(shè)棧頂 32 字節(jié)是計(jì)算好的 MD5 字符串，輸出的系統(tǒng)調(diào)用：
0: b8 01 00 00 00 mov eax,0x1 ; write 系統(tǒng)調(diào)用5: bf 01 00 00 00 mov edi,0x1 ; 標(biāo)準(zhǔn)輸出a: 48 89 e6 mov rsi,rsp ; 指針d: ba 20 00 00 00 mov edx,0x20 ; 長(zhǎng)度 32 字節(jié)12: 0f 05 syscall匯編代碼優(yōu)化
預(yù)先計(jì)算 MD5 中間狀態(tài)
將 ELF 文件分為三部分：[A] [B] [C]
其中 A 的長(zhǎng)度為 64 的倍數(shù)，B+C 的長(zhǎng)度 <= 55。
A+B 包括：ELF 文件頭、計(jì)算 MD5 一個(gè) block 的代碼、輸出 16 進(jìn)制的代碼。
C 是對(duì) A 計(jì)算 MD5（不加 padding）的中間結(jié)果，16 字節(jié)，由輔助腳本計(jì)算并填入。（后面會(huì)把 C 變成 13 字節(jié)，見(jiàn)下文。）
這樣可以省掉外層循環(huán)，匯編只用計(jì)算最后 64 位字節(jié)。
避免 copy
默認(rèn) text 段是不可寫(xiě)的，可以修改 p_flags，從 5 (可讀可執(zhí)行) 寫(xiě)為 7 (可讀寫(xiě)可執(zhí)行)，同時(shí)把 p_memsz 改大一些。這樣 padding 就可以直接加在后面，不需要再拷貝到棧上。
分支之間共用指令
注意最內(nèi)層的那一串 if-else：有兩個(gè)分支都用到?b^c，還有兩個(gè)分支計(jì)算?f?的最后一步是?^c，還兩個(gè)分支計(jì)算?f?的最后一步是?^d。這里代碼都可以共用，不僅可以省掉幾個(gè)字節(jié)，更重要的是，分支代碼碼變得更短以后，更容易塞到文件頭里面。
指令選擇
盡量選用早期 x86 就有的指令，一般編碼會(huì)比較短。很多不常用的指令，只因?yàn)樯迷?#xff0c;占了好坑，都只要一兩個(gè)字節(jié)。
例如：lodsb?只要一個(gè)字節(jié)，而?mov al,[rsi]; inc rsi?要好幾個(gè)。
又如，loop addr?指令大致相當(dāng)于?dec ecx; jnz addr，也少了好幾個(gè)字節(jié)。沒(méi)有哪個(gè)現(xiàn)代編譯器會(huì)主動(dòng)生成這個(gè)指令，實(shí)際上 Intel 也不建議用，較新的 CPU 里沒(méi)有為這個(gè)指令做優(yōu)化，性能偏低。但對(duì)本題卻相當(dāng)合適。
拿不準(zhǔn)的時(shí)候多試幾次，用 objdump 看哪個(gè)短。
寄存器的選擇
優(yōu)先使用從 32 位時(shí)代沿襲下來(lái)的 8 個(gè)寄存器 (rax, rbx, rcx, rdx, rsi, rdi, rbp, rsp)，避免使用 r8-r15。對(duì)于很多指令，使用 r8-r15 會(huì)多占一個(gè)字節(jié)。例如：
0: 41 83 e0 01 and r8d,0x14: 83 e0 01 and eax,0x1用最短的代碼賦值小常量給寄存器
對(duì) 0 值，對(duì)寄存器異或自身：xor eax, eax。這個(gè)很常見(jiàn)，減少代碼體積，也不損失性能，Intel 也推薦這樣寫(xiě)。
對(duì)于非 0 值，下面的寫(xiě)法就損失性能了，但對(duì)本題有用。
將常量 1 賦給 ebx，最自然的寫(xiě)法 5 個(gè)字節(jié)：
0: bb 01 00 00 00 mov ebx,0x1這樣寫(xiě)只要 4 個(gè)字節(jié)（如果知道 ebx 的高位已經(jīng)是 0，則只需后一指令，2 個(gè)字節(jié)）：
0: 31 db xor ebx,ebx 2: b3 01 mov bl,0x1這樣寫(xiě)只要 3 個(gè)字節(jié)：
0: 6a 01 push 0x1 2: 5b pop rbx32 位 or 64 位寄存器
x86-64 有一個(gè)特性，目標(biāo)操作數(shù)是 32 位寄存器時(shí)，會(huì)同時(shí)清空對(duì)應(yīng) 64 位寄存器的高 32 位。所以?xor eax, eax?與?xor rax, rax?等價(jià)；mov eax, 1?也與?mov rax, 1?等價(jià)。使用 32 位寄存器常常可以省一個(gè)字節(jié)（r8-r15 除外）：
0: 31 c0 xor eax,eax 2: 48 31 c0 xor rax,rax但注意，在作為地址時(shí)，情況相反，64 位少一個(gè)字節(jié)：
0: 67 8d 43 08 lea eax,[ebx+0x8] 4: 8d 43 08 lea eax,[rbx+0x8]進(jìn)程初始狀態(tài)
網(wǎng)上說(shuō) Linux 進(jìn)程啟動(dòng)時(shí)，除了 RCX 以外，其他寄存器的值都不確定。但實(shí)測(cè)拿到的都是 0，所以省略對(duì)寄存器清 0 的操作。
（有的資料說(shuō)其他寄存器會(huì)繼承?execve?之前的值，懶得去驗(yàn)證，不過(guò)對(duì)此存疑。如果操作系統(tǒng)不清 0，這會(huì)是一個(gè)安全漏洞，父進(jìn)程可能無(wú)意中漏泄信息給子進(jìn)程。）
使用 16 位地址
ELF 的常見(jiàn)初始虛擬地址是諸如 0x8048000 這樣的值，把它改成 0x1000，這樣兩個(gè)字節(jié)可以放下地址。
不能比 0x1000 更小了，因?yàn)?0x1000 == 4096 是一個(gè)頁(yè)面的大小，在最前面至少要留一個(gè)頁(yè)面，否則 NULL 會(huì)成為有效指針。
棧優(yōu)化
棧涉及到內(nèi)存操作，比用寄存器慢。然而 push、pop 作為元老級(jí)的 8086 指令，編碼超級(jí)短，前 8 個(gè)寄存器的 push、pop 只要一個(gè)字節(jié)。
0: 50 push rax 1: 5b pop rbx 2: 48 89 c3 mov rbx,rax在這個(gè)例子里，出棧再入棧竟然比 mov 少一個(gè)字節(jié)！
浮點(diǎn)運(yùn)算
現(xiàn)在 Intel 推薦用 SSE/AVX 來(lái)做浮點(diǎn)運(yùn)算，但對(duì)本題還是 x87 香，計(jì)算 sin、取絕對(duì)值都是一條指令的事情（兩個(gè)字節(jié)）。
x87 寄存器是棧式的，寫(xiě)復(fù)雜的算式比較麻煩。好在本題的式子并不復(fù)雜，下面幾行代碼就可以計(jì)算出?(fabs(sin(i + 1)) * 4294967296.0)，其中?[rbx-0x14]?指向一個(gè)預(yù)存了?4294967296.0?的地址。
10d4: 50 push rax ; i+1 入棧10d5: db 04 24 fild DWORD PTR [rsp] ; 轉(zhuǎn)成浮點(diǎn)數(shù)，放到st010d8: d9 fe fsin ; sin10da: d9 e1 fabs ; abs10dc: d8 4b ec fmul DWORD PTR [rbx-0x14] ; 乘以 429496729610df: dd 0c 24 fisttp QWORD PTR [rsp] ; 轉(zhuǎn)成整數(shù)，寫(xiě)到棧頂10e2: 5a pop rdx ; 出棧，讀到結(jié)果pext 指令
C++ 代碼里有一處?(i / 16) * 4 + (i % 4)，很適合用 pext 指令來(lái)實(shí)現(xiàn)。pext 是一條 BMI 2 指令，可以簡(jiǎn)便地從源操作數(shù)里抽一些不連續(xù)的位出來(lái)。
假設(shè)?i?放在 eax，那么用?pext ecx, eax, bit_mask?(bit_mask = 0b00110011) 就可以從?i?里面提取出第 0、1、4、5 位，正好就是?(i / 16) * 4 + (i % 4)?的值。
使用 near 跳轉(zhuǎn)
jmp、jcc 都有 8 位偏移和 32 位偏移兩個(gè)版本。32 位太浪費(fèi)，盡量調(diào)整代碼塊的位置，讓所有跳轉(zhuǎn)都變成 8 位（跳轉(zhuǎn)范圍在 -128 至 127 字節(jié)之間）。實(shí)在避免不了的，用兩條短 jmp 中轉(zhuǎn)一下都能節(jié)省一個(gè)字節(jié)。
尋址優(yōu)化
x86-64 提供了相對(duì) rip 的尋址，為位置無(wú)關(guān)代碼（PIC）提供了很大便利。又由于它比絕對(duì)尋址短，所以編譯器通常在非 PIC 代碼中也會(huì)使用它。
但遺憾的是，它始終使用 32 位偏移量，太浪費(fèi)。可以考慮固定使用一個(gè)寄存器保存一個(gè)地址，后面的尋址都相對(duì)它進(jìn)行，并設(shè)法將偏移保持在 8 位的范圍內(nèi)（-128 至 127）。
對(duì)比以下三條指令的長(zhǎng)度：
0: 8b 43 02 mov eax,DWORD PTR [rbx+0x2] 3: 8b 05 02 00 00 00 mov eax,DWORD PTR [rip+0x2] 9: 8b 04 25 02 00 00 00 mov eax,DWORD PTR [0x2]調(diào)用函數(shù)
call 指令沒(méi)有 8 位偏移的版本，32 位偏移很浪費(fèi)。先將函數(shù)地址裝到一個(gè)寄存器，再 call 這個(gè)寄存器，只要兩個(gè)字節(jié)：
0: ff d3 call rbx最后撞三個(gè)字節(jié)
寫(xiě)完代碼以后，發(fā)現(xiàn) ELF 頭部還剩兩個(gè)可以自由修改的字節(jié)。代碼里還有一些等效的指令，例如，當(dāng)已知 eax 和 ecx 的值相等時(shí)，下面四條指令等價(jià)：
lea ecx, [rax+rax*4+1] lea ecx, [rax+rcx*4+1] lea ecx, [rcx+rax*4+1] lea ecx, [rcx+rcx*4+1]又如，在判斷循環(huán)條件時(shí)，下面代碼里的?jb?可以替換為?jne：
inc eax cmp al, 64 jb _loop_md5于是，通過(guò)給 nasm 增加參數(shù)?-Dalternative=...，并在代碼里使用?%if alternative = ...?來(lái)選擇使用哪一種等價(jià)的寫(xiě)法。
再寫(xiě)一個(gè)額外的程序來(lái)遍歷頭部?jī)蓚€(gè)字節(jié)的值，以及代碼中這些有?alternative?的地方的指令選擇，使得計(jì)算出的 MD5 的中間結(jié)果的最后三個(gè)字節(jié)是?0x80 0x00 0x00，即與 MD5 padding 的前三個(gè)字節(jié)相同，這樣就可以從文件內(nèi)容中省去這三個(gè)字節(jié)。
代碼
完整代碼：
bits 64; 定義“變量”對(duì)應(yīng)的寄存器; R_ 表示 64 位，r_ 表示對(duì)應(yīng)的 32 位，_w 表示低 16 位， _l 表示低 8 位%define r_base ebx ; 始終指向$$+offs%define R_base rbx%define r_base_w bx;%define r_a r8d ; a,b,c,d 在內(nèi)層循環(huán)中保存MD5狀態(tài);%define R_a r8 ; r_a 現(xiàn)在不占用寄存器了，移到棧頂 [rsp]%define r_b edi%define R_b rdi%define r_c ebp%define R_c rbp%define r_d edx%define R_d rdx%define r_i eax ; 內(nèi)層循環(huán)下標(biāo)%define R_i rax%define r_i_l al%define r_f esi ; 內(nèi)層循環(huán)中的變量 F; ecx用作臨時(shí)變量; 一般是使用 0x8048000，故意改成一個(gè)很小的數(shù)，以便兩個(gè)字節(jié)可以放下地址 %define base 0x1000org base ehdr: ; Elf64_Ehdrdb 0x7F, "ELF", 2, 1, 1, 0 ; e_ident; times 8 db 0; 這個(gè)代碼塊正好8字節(jié)，放這里 _16_to_32:; if (16 <= i && i < 32) {; g = 5*i + 1;; f = ((b ^ c) & d) ^ c; // (d & b) | ((~d) & c);; }%if alternative = 1 ; alternative用于控制生成多種等效的代碼，fill.py會(huì)對(duì)它們進(jìn)行遍歷，; 找到使MD5中間結(jié)果最后幾個(gè)字節(jié)恰好等于 0x80 0x00 0x00 的組合lea ecx, [R_i+R_i*4+1]%elif alternative = 2lea ecx, [R_i+rcx*4+1]%elif alternative = 3lea ecx, [rcx+R_i*4+1]%elselea ecx, [rcx+rcx*4+1]%endifand r_f, r_djmp _reuse_code ; _16_to_32 與 _32_to_48 最后一條指令相同，jmp過(guò)去省兩個(gè)字節(jié) times 8 - ($ - _16_to_32) db 0; enddw 2 ; e_typedw 62 ; e_machine;dd 1 ; e_version (modifiable) _0x1p32 dd 4294967296.0 ; pow(2.0, 32)dq _start ; e_entrydq phdr - $$ ; e_phoff;dq 0 ; e_shoff (modifiable);dd 0 ; e_flags (modifiable);dw ehdrsize ; e_ehsize (modifiable); 14個(gè)可以修改的字節(jié)，放一個(gè)函數(shù)在此(13字節(jié)); 將al低4位轉(zhuǎn)為1位16進(jìn)制 _make_hex:and eax, 15cmp al, 10jb .lt10add al, 'a' - '0' - 10 .lt10:add al, '0'stosbret; 剩一個(gè)字節(jié)，放pext的mask%if alternative = 1 _pext_mask db 0b00110011%elif alternative = 2 _pext_mask db 0b01110011%elif alternative = 3 _pext_mask db 0b10110011%else _pext_mask db 0b11110011%endif times 14-($-_make_hex) db 0dw phdrsize ; e_phentsize;; overlap the last 8 bytes of ehdr with phdr phdr: ; Elf64_Phdrdd 1 ; p_type = 1; e_phnum (word, 1); e_shentsize (word, modifiable)db 7 ; p_flags=7 (readable, writable, executable)db 0 ; 這個(gè)字節(jié)留給fill.py修改 (p_flags只要最低1字節(jié)對(duì)即可，高位隨便改) _context_ptr dw base + (_context - $$) ; e_shnum (word, modifiable); e_shstrndx (word, modifiable)ehdrsize equ $ - ehdrdq 0 ; p_offsetdq $$ ; p_vaddr;;dq $$ ; p_paddr (modifiable) _0_to_16: ; 這個(gè)代碼塊正好8字節(jié)，放這里; if (i < 16) {; g = i;; f = ((c ^ d) & b) ^ d; // (b & c) | ((~b) & d);; }mov r_f, r_cxor r_f, r_dand r_f, r_bjmp _reuse_code_2 ; _0_to_16 與 _48_to_64 最后一條指令相同，jmp過(guò)去省兩個(gè)字節(jié) times 8-($-_0_to_16) db 0dq filesize ; p_filesz;dq filesize+512 ; p_memsz; 挪用p_memsz用于存一些其他數(shù)據(jù)，只要這里填的值至少比f(wàn)ilesize大一些，但又不要過(guò)于; 巨大以免運(yùn)行錯(cuò)誤 _16_to_32_relay: jmp short _16_to_32 ; 中轉(zhuǎn)向_16_to_32的跳轉(zhuǎn)，便得兩處跳轉(zhuǎn)都使用8位偏移量 _compute_start_ptr dd ($$ + filesize - filesize % 64) times (8 - ($ - _16_to_32_relay)) db 0;dq 0x1000 ; p_align;; p_align是phdr的最后8個(gè)字節(jié)，對(duì)靜態(tài)鏈接的代碼沒(méi)什么用，省去 phdrsize equ $ + 8 - phdr_shift db 7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21%assign start_of_code base + ($ - $$) %warning code: start_of_code_48_to_64:; if (i >= 48) {; g = 7*i;; f = c ^ (b | (~d));; }%if alternative = 1imul ecx, r_i, 7%elseimul ecx, 7%endifmov r_f, r_dnot r_for r_f, r_b _reuse_code:xor r_f, r_cjmp _join; R_base 偏移 offs 字節(jié)，指向 _make_hex offs equ _make_hex - $$; 程序入口 _start:mov r_base_w, base + offs ; mov r_base, $$ + offs; 文檔說(shuō)進(jìn)程啟動(dòng)時(shí)rdi的值未定，但實(shí)測(cè)至少tlinux2; 保證了它是0mov esi, [R_base - offs - $$ + _context_ptr]; 本來(lái)這里應(yīng)該用movzx讀2個(gè)字節(jié)的，但正好后面2個(gè)字節(jié)也是0，就用mov省一個(gè)字節(jié)push rsi; MD5 paddingmov byte [rsi + _end - _context], 0x80mov word [rsi + _end - _context + paddingsize - 8], filesize*8; uint32_t a = hash[0];; uint32_t b = hash[1];; uint32_t c = hash[2];; uint32_t d = hash[3];push qword [rsi]mov r_b, [rsi + 4]mov r_c, [rsi + 8]mov r_d, [rsi + 12]; for (int i = 0; i < 64; ++i) {; xor r_i, r_i ; 文檔說(shuō)啟動(dòng)時(shí)rax的值未定，實(shí)測(cè)至少tlinux2上進(jìn)程啟動(dòng)時(shí)eax=0 _loop_md5:; 有兩個(gè)分支用到 b^c，在分支前先算出來(lái)放到f，省兩個(gè)字節(jié)mov r_f, r_b ; f = b ^ cxor r_f, r_cmov ecx, r_i ; g = icmp r_i_l, 16jb _0_to_16cmp r_i_l, 32jb _16_to_32_relaycmp r_i_l, 48jae _48_to_64_32_to_48:; if (32 <= i && i < 48) {; g = 3*i + 5;; f = b ^ c ^ d;; }%if alternative = 1lea ecx, [R_i+R_i*2+5]%elif alternative = 2lea ecx, [R_i+rcx*2+5]%elif alternative = 3lea ecx, [rcx+R_i*2+5]%elselea ecx, [rcx+rcx*2+5]%endif _reuse_code_2:xor r_f, r_d_join:; f += a; a = d;; (d := garbage)xchg r_d, [rsp]add r_f, r_d; f += in[g % 16];and ecx, 15mov r_d, [R_base - offs - $$ + _compute_start_ptr]add r_f, [R_d + rcx*4]; int shift_val = _shift[(i / 16) * 4 + (i % 4)];pext ecx, r_i, [R_base-offs-$$+_pext_mask] ; _pext_mask的高24位不是0，不過(guò)不影響，因?yàn)閞_i高位全是0mov cl, [R_base-offs-$$+_shift+rcx] ; [_shift + rcx]; K[i] := floor(2^32 × abs (sin(i + 1)))inc r_ipush R_ifild dword [rsp]fsinfabsfmul dword [R_base-offs-$$+_0x1p32] ; * 2^32fisttp qword [rsp]; f += K[i]pop R_d ; 把r_d當(dāng)作臨時(shí)寄存器用一下，pop出來(lái)的是剛才fisttp寫(xiě)入[rsp]的值，即K[i]add r_f, r_d; f = (f << shift_val) | (f >> (32 - shift_val));rol r_f, cl; d = c;; c = b;; b += f;mov r_d, r_cmov r_c, r_badd r_b, r_f; }cmp r_i_l, 64%if alternative = 1jb _loop_md5%elsejne _loop_md5%endif; hash[0] += a;; hash[1] += b;; hash[2] += c;; hash[3] += d;pop rax ; Apop rsi ; _contextadd [rsi], eaxadd [rsi+4], r_badd [rsi+8], r_cadd [rsi+12], r_d; PRINT HEX;xor ecx, ecx ; 從前面循環(huán)里出來(lái)，ecx高位還是0mov cl, 16 ; mov ecx, 16lea edi, [rsi+16].loop_print_hex:mov al, [rsi]shr eax, 4call R_base ; call _make_hexlodsbcall R_base ; call _make_hexloop .loop_print_hex;rsi is already buffer of hex stringmov al, 1 ; mov eax, 1 (write) (eax高位已經(jīng)是0)mov edi, eax ; mov edi, 1 (1 = stdout)%if alternative = 1lea edx, [rax+31] ; mov edx, 32; 用lea比mov短一點(diǎn)%elselea edx, [rdi+31]%endifsyscall; 返回后eax=32; EXIT%if alternative = 1mov al, 231 ; exit_group (eax高位已經(jīng)是0)%elif alternative = 2add al, 231-32 ; 同上%elif alternative = 3sub al, 32-231 ; 同上%elif alternative = 4mov al, 60 ; exit (eax高位已經(jīng)是0)%elif alternative = 5add al, 60-32 ; 同上%elsesub al, 32-60 ; 同上%endifxor edi, edisyscall%if ($ - $$) % 64 > 64 - 13 - 9 %assign wasted_padding 64 - ($ - $$) % 64 %warning Wasted padding bytes: wasted_paddingalign 64 %endif; _context 的初始內(nèi)容由 fill.py 填入 _context: times 13 db 0 ; 最后三個(gè)字節(jié)由fill.py保證正好是0x80 0x00 0x00 (和MD5的padding一致)_end:filesize equ $ - $$ main_loops equ (filesize + 9 + 63) / 64 ; MD5算法循環(huán)次數(shù) paddingsize equ 64 * main_loops - filesize ; 原始數(shù)據(jù)后需要附加的字節(jié)數(shù)%assign filesize filesize %warning File size: filesize光憑這個(gè) asm 還不夠，還要配合碰撞的腳本才能編譯出來(lái)正確的二進(jìn)制：
README.md：解題描述
build.ninja：編譯腳本
main.asm: 主程序
fill.py: 用于碰撞 3 個(gè)字節(jié)的腳本
fill_helper.cpp: fill.py 的輔助代碼（用 C++ 加速）
md5.out: 最終的 299 字節(jié)可執(zhí)行文件
cpp_reference.cpp：C++ 參考實(shí)現(xiàn)
最終文件?md5.out?。從源碼編譯需要先安裝 Python 3、ninja、nasm，然后運(yùn)行 ninja 命令，等 10~20 分鐘（取決于機(jī)器性能），就能得到 md5.out。
感興趣的小伙伴，可以在公眾號(hào)回復(fù)“md5”獲取完整實(shí)現(xiàn)。
大神解法，我是跪著看完了，歡迎小伙伴在留言區(qū)打上666，膜拜一下大佬，
如果文章給你長(zhǎng)見(jiàn)識(shí)了，那就一鍵三連繼續(xù)支持，點(diǎn)贊和在看超過(guò)30，我就放另辟蹊徑的野路子解法：
絕對(duì)讓你感嘆腦洞如此之大，讓人望其項(xiàng)背。
推薦閱讀
最小MD5挑戰(zhàn)賽，你敢來(lái)戰(zhàn)嗎？
頂級(jí)C程序員之路
一個(gè)奇葩的網(wǎng)絡(luò)問(wèn)題
C++模版的本質(zhì)
總結(jié)
以上是生活随笔為你收集整理的顶级极客技术挑战赛，你敢来挑战吗？| 大神登峰造极的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 顶级C程序员之路
- 下一篇： 一篇漫画，看懂云计算！