Binary Modification: Part 2

Image of binary digits with a 0 begin corrected to a 1.

If you haven’t yet, read Part 1 here!

Welcome back! We will be picking up from Part 1 after having inspected the binary’s headers and symbol table. In particular, we found the location of our .text segment along with the address of main and our target compute_hash function. With this information, we can move forward attempting to modify a single bit of the mystery binary to print the “success” flag.

Binary Dump

We found that inspecting the binary with readelf will only get us so far. We need to use another tool to disassemble the RISC-V code in a format we can read. For that, we can use the GNU tools objdump.

>$ riscv64-unknown-elf-objdump
Usage: riscv64-unknown-elf-objdump <option(s)> <file(s)>
 Display information from object <file(s)>.
 At least one of the following switches must be given:
  -a, --archive-headers    Display archive header information
  ...
  -x, --all-headers        Display the contents of all headers
  -d, --disassemble        Display assembler contents of executable sections
  -D, --disassemble-all    Display assembler contents of all sections
      --disassemble=<sym>  Display assembler contents from <sym>
  ...

There are a variety of options. objdump -x, for example, will display the contents of our section headers in a similar (but slightly different) format of readelf. objdump -D is what we’re after as it will display the assembly of all the sections, something that readelf could not do! For our purposes, we only need to examine the .text segment (our assembly code) so objdump -d will do just fine. Let’s save the output to the file mystery.asm.

Upon inspecting mystery.asm, we can see the disassembled .text section:

>$ riscv64-unknown-elf-objdump -d mystery > mystery.asm
>$ cat mystery.asm

mystery:     file format elf64-littleriscv

Disassembly of section .text:

0000000000010120 <exit>:
   10120:	1141       	addi	sp,sp,-16
   [...]

000000000001014e <_start>:
   1014e:	0000c197   	auipc	gp,0xc
   10152:	da218193  	addi	gp,gp,-606 # 1bef0 <__global_pointer$>
   10156:	23818513   	addi	a0,gp,568 # 1c128 <__malloc_max_mem>
   [...]
   10188:	4601      	li	a2,0
   1018a:	04e000ef   	jal	101d8 <main>
   1018e:	bf49       	j	10120 <exit>

As we talked about earlier, we find our _start label at address 0x1014e which aligns with the listed entry point in the ELF header! Although I omitted much of _start for brevity, we can generally see that _start_ sets up the environment and eventually calls main before jumping to the exit label.

If we scroll futher, we find our main function! Here is the entire version (annotated for those who are rusty in assembly):

00000000000101d8 <main>:
   /* Store saved registers to stack */
   101d8:	1101       	addi	sp,sp,-32
   101da:	ec06       	sd	ra,24(sp)
   101dc:	e822       	sd	s0,16(sp)
   101de:	1000       	addi	s0,sp,32

   /* malloc() call with 1000 bytes */
   101e0:	3e800513   	li	a0,1000
   101e4:	0d0000ef   	jal	102b4 <malloc>
   101e8:	87aa       	mv	a5,a0
   101ea:	fef43423   	sd	a5,-24(s0)
   101ee:	fe843783   	ld	a5,-24(s0)

   /* branch instruction? Interesting... */
   101f2:	e38d       	bnez	a5,10214 <main+0x3c>
   101f4:	deadc7b7   	lui	a5,0xdeadc
   101f8:	eef78513   	addi	a0,a5,-273 # ffffffffdeadbeef 
   101fc:	028000ef   	jal	10224 <compute_hash>
   10200:	87aa       	mv	a5,a0
   10202:	85be       	mv	a1,a5

   /* printf("Success! Hash is %d") */
   10204:	67e9       	lui	a5,0x1a
   10206:	cf878513   	addi	a0,a5,-776 # 19cf8 <__clzdi2+0x32>
   1020a:	763000ef   	jal	1116c <printf>
   1020e:	4501       	li	a0,0
   10210:	f11ff0ef   	jal	10120 <exit>

   /* printf("Nothing to see here...")             */
   /* Note the call to puts() instead of printf()  */
   10214:	67e9       	lui	a5,0x1a
   10216:	d4078513   	addi	a0,a5,-704 # 19d40 <__clzdi2+0x7a
   1021a:	004010ef   	jal	1121e <puts>
   1021e:	557d       	li	a0,-1
   10220:	f01ff0ef   	jal	10120 <exit>
Original C Code
One-Bit Challenge main.c | Last updated: Apr 21, 2025
printf optimization

Notice how the compiler replaced the second call to printf with a call to puts. printf has additional overhead needed to replace the format specifiers with their arguments on the stack. GCC sees that we are printing a static string and optimized our code by substituting puts for printf!

For our purposes, the following lines are the most important for us:

00000000000101d8 <main>:
   ...
   /* malloc result stored in a5 */
   101f2:	e38d       	bnez	a5,10214 <main+0x3c>
   101f4:	deadc7b7   	lui	a5,0xdeadc
   101f8:	eef78513   	addi	a0,a5,-273 # ffffffffdeadbeef 
   101fc:	028000ef   	jal	10224 <compute_hash>
   ...
   10210:	f11ff0ef   	jal	10120 <exit>

   ...
   /* printf("Nothing to see here...") */
   10214:	67e9       	lui	a5,0x1a
   10216:	d4078513   	addi	a0,a5,-704 # 19d40 <__clzdi2+0x7a>
   1021a:	004010ef   	jal	1121e <puts>
   1021e:	557d       	li	a0,-1
   10220:	f01ff0ef   	jal	10120 <exit>

The key is the branch instruction bnez (“branch if not equal to zero”) which will jump to the new address if our register a5 is not equal to zero. This new address is the instruction at 0x10214 which is the start of our printf("Nothing to see here") block. If the bnez condition evalutes to false (a5 == 0), the program will not branch and will continue to the compute_hash function and terminate early at exit. This is exactly what we need! Branching skips the execution of compute_hash.

Remember that our original goal is to the print the “success” line which involves jumping to compute_hash. If we can modify the binary so that the branch is not taken, then we will accomplish our goal.

The Plan

There are various single-bit modifications we can make to the binary to beat the challenge. Some ideas (please try to implement them!) are below:

  • Change a5 in bnez to a register we know will equal zero.
    • a5 is encoded as 0b01111, so the registers with a Hamming distance of 1 will be t6, s7, t2, a1, and a4. Note that some (possibly all) of the registers may be nonzero by the time of the bnez instruction.
  • Change program entry point from 0x101d8 to 0x101f8 which is two instructions after bnez.
    • This will certainly not work without heavy modification as the _start bootstrapping will be skipped, but it would be a fun exercise to attempt.
  • Make malloc fail and which puts NULL into a5
    • One idea for causing malloc to fail is by passing in a value that is too large. This may be done by replacing li a0, 1000 with an immediate value of 1000 | (1 << X) where X is large enough to be encoded in a single addi instruction (li is a pseudoinstruction for an (optional, not currently present) lui followed by addi to form the immediate). I am not sure this can be accomplished by modifying a single bit, but please try and let me know!
  • Negate the branch condition by converting bnez a5 to beq a5 (“branch if equal to zero”)
    • This will be our approach!

Because this project originally came from a student while teaching instruction formats, we will focus on changing bnez to a bne instruction. Let’s do it!

Inserting Instructions

If we know the address of compute_hash, why can we not just insert an unconditional jump instruction to jump straight to our printf of compute_hash?

We can but changing fully replacing an existing an instruction would likely require modifying 2-4 bytes (can be done but likely not with a single-bit change. Please try though!). Inserting a jump instruction is possible, but dangerous and must be done with care.

The reason why we can’t just insert random instructions into assembly is because compilers make use of Position-Independent Code (PIC). This means that branch and jump instructions use offsets relative to the current instruction (called “PC-relative addressing”). If we start inserting / removing instructions, those branch/jump offsets point to the wrong instructions and the rest code will not work!

Binary Modification

Still working on the writeup! Will update soon :)