Contents:
I recently was tasked with the following assignment for a uni course
colltatz function is not constant time.cmov and is constant time.I've never done this before. These are my notes on how to patch the binary. I'll only use simple tools here (objdump, xxd, vim).
The file command tells us that the binary is a position-independent ELF binary:
base: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=d50f39f88c70eded4b8bd8b733a363d128cd508a, for GNU/Linux 3.2.0, with debug_info, not stripped
When you run the binary you see:
collatz(1): 4
collatz(2): 1
...
collatz(48): 24
collatz(49): 148
Alright, nothing special so far.
Disassemble the binary to see what has to be fixed: objdump -D -Mintel collatz
0000000000004000 <collatz>:
4000: f3 0f 1e fa endbr64
4004: 55 push rbp
4005: 48 89 e5 mov rbp,rsp
4008: 89 7d fc mov DWORD PTR [rbp-0x4],edi
400b: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
400e: 83 e0 01 and eax,0x1
4011: 85 c0 test eax,eax
4013: 75 0e jne 4023 <collatz+0x23>
4015: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
4018: 89 c2 mov edx,eax
401a: c1 ea 1f shr edx,0x1f
401d: 01 d0 add eax,edx
401f: d1 f8 sar eax,1
4021: eb 0c jmp 402f <collatz+0x2f>
4023: 8b 55 fc mov edx,DWORD PTR [rbp-0x4]
4026: 89 d0 mov eax,edx
4028: 01 c0 add eax,eax
402a: 01 d0 add eax,edx
402c: 83 c0 01 add eax,0x1
402f: 5d pop rbp
4030: c3 ret
The simplified reverse engineered C code should look similar to:
int collatz(int n) {
if (n & 1) // odd?
return 3 * n + 1;
return n / 2; // weird implementation: ((n >> 0xf1) + n) >> 1
}
The code isn't constant-time due to the if-else case. To make it constant-time, we should always compute 3*n+1 and n/2, and then use cmov to make a constant-time selection of the correct result. The adjusted assembly looks as follows (ignore the offsets):
0000000000004000 <collatz>:
4000: f3 0f 1e fa endbr64
4004: 55 push rbp
4005: 48 89 e5 mov rbp,rsp
4008: 89 7d fc mov DWORD PTR [rbp-0x4],edi
; store result for even case in EBX
400b: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
;>>>>> these can be removed to shrink binary size
;4018: 89 c2 mov edx,eax
;401a: c1 ea 1f shr edx,0x1f
;401d: 01 d0 add eax,edx
;<<<<<
401f: d1 f8 sar eax,1
89 C3 mov ebx,eax
; store result for odd case in ECX
4023: 8b 55 fc mov edx,DWORD PTR [rbp-0x4]
4026: 89 d0 mov eax,edx
4028: 01 c0 add eax,eax
402a: 01 d0 add eax,edx
402c: 83 c0 01 add eax,0x1
89 C1 mov ecx,eax
; select the correct case via CMOV
400b: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
400e: 83 e0 01 and eax,0x1
4011: 85 c0 test eax,eax
0F 44 C3 cmovz eax,ebx // even
0F 45 C1 cmovnz eax,ecx // odd
; return
402f: 5d pop rbp
4030: c3 ret
; pad up to original size
90 nop
If you don't know the opcodes for instructions that aren't already inside the binary (e.g. cmov eax,ebx in this example), you can check e.g. this reference. Or you run the assembly through an assembler.
Next, create a hexdump of the original binary:
xxd collatz > collatz.hex
You should see the opcodes that are also shown in the objdump of the original collatz binary (e.g. f30f1efa is opcode of endbr64 instruction at the start of collatz):
...
00004000: f30f 1efa 5548 89e5 897d fc8b 45fc 83e0 ....UH...}..E...
00004010: 0185 c075 0e8b 45fc 89c2 c1ea 1f01 d0d1 ...u..E.........
00004020: f8eb 0c8b 55fc 89d0 01c0 01d0 83c0 015d ....U..........]
00004030: c300 0000 f30f 1efa 4883 ec08 4883 c408 ........H...H...
00004040: c300 0000 0000 0000 0000 0000 0000 0000 ................
...
The collatz function ends in the 4th line after c3 (opcode for ret). We have to make sure that we don't change something after that byte. In other words, you can only replace bytes but you shouldn't add more or remove them, as that would likely result in the corruption of the binary1.
My strategy here was to make the binary smaller than the original by removing the instructions surrounded by ;>>>>> <<<<< above. To my knowledge, these instructions don't change the result.
If the patched binary is smaller than the original, you can simply add 0x90 bytes as padding, which is the opcode for the x86 NOP instruction. I had to add one NOP.
To patch the binary, we just edit the middle section of this hexdump with vim or any other editor, to match the instruction opcodes of the updated assembly code. The patched hexdump looks as follows (ignore the ASCII representation):
...
00004000: f30f 1efa 5548 89e5 897d fc8b 45fc d1f8 ....UH...}..E...
00004010: 89c3 8b55 fc89 d001 c001 d083 c001 89c1 ...u..E.........
00004020: 8b45 fc83 e001 85c0 0f44 c30f 45c1 5dc3 ....U..........]
00004030: 9000 0000 f30f 1efa 4883 ec08 4883 c408 ........H...H...
00004040: c300 0000 0000 0000 0000 0000 0000 0000 ................
...
Save the modified hexdump. Then produce the patched binary from it:
xxd -r collatz.hex patched_collatz
Running objdump -D -Mintel patched_collatz should match the updated assembly (note that cmov(n)z and cmov(n)e are equivalent):
0000000000004000 <collatz>:
4000: f3 0f 1e fa endbr64
4004: 55 push rbp
4005: 48 89 e5 mov rbp,rsp
4008: 89 7d fc mov DWORD PTR [rbp-0x4],edi
400b: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
400e: d1 f8 sar eax,1
4010: 89 c3 mov ebx,eax
4012: 8b 55 fc mov edx,DWORD PTR [rbp-0x4]
4015: 89 d0 mov eax,edx
4017: 01 c0 add eax,eax
4019: 01 d0 add eax,edx
401b: 83 c0 01 add eax,0x1
401e: 89 c1 mov ecx,eax
4020: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
4023: 83 e0 01 and eax,0x1
4026: 85 c0 test eax,eax
4028: 0f 44 c3 cmove eax,ebx
402b: 0f 45 c1 cmovne eax,ecx
402e: 5d pop rbp
402f: c3 ret
4030: 90 nop
The original and patched binary should now produce the same output.
You probably can change other bytes too but then you have to adjust other parts of the ELF as well. I haven't tested that but it'd probably be tedious to do this by hand. I suppose that reverse engineering frameworks provide such a functionality. ↩