SHA512 Is Not a DSA: Using Partial Hash Collisions To Own a Custom Bootloader
Abstract
This page is a walkthrough for Churchill, the fourth in a recent series of reverse engineering challenges from the embedded systems division at NCC Group.
Executive Summary
The load address is signed, and the secure boot implementation has changed. Again, the goal is to circumvent the signature check to achieve arbitrary code execution.
Overview
First Working Exploit: 0804 UTC, March 10th, 2023Blockchain Timestamp: 0934 UTC, March 10th, 2023
Pastebin Timestamp: pastebin.com/rMbS7Jgp
Cryptographic Proof of Existence: solution.txt solution.txt.ots
Solve Count At Time Of Writing: Unknown A backend bug breaks the solve counters for Cold Lake and Churchill.
Solves Per month: Unknown
Reading Time: 12 minutes
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.
Background
The following is a walkthrough for the fourth in the new series of Microcorruption challenges. The original CTF-turned-wargame was developed a decade ago by Matasano and centered around a deliberately vulnerable smart lock. The goal for each challenge was simple: write a software exploit to trigger an unlock.
NCC Group later acquired Matasano. They continued maintaining the wargame and added half a dozen new challenges on October 28th, 2022, of which this is one.
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. On earlier challenges in the series, there is a dedicated function called unlock_door that does this.
Executing the following shellcode 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 the interrupt is called successfully.
High-Level Analysis
Sample Payload
The debug payload is only one segment, and the load address is read big-endian. The example payload is below.
800000063041c26436953f8f3cadf1442fc218b185051ab6c20853a45f093fc32adf31529d05a5ec3e96a9e41ed9ad1b14dcbdb98e50e37a7ddc3d595b867807ed1605f2070e
Sample Output
Running the firmware with the example debug payload will produce the following output at the console.
Welcome to the secure program loader.
Please enter debug payload.
Signature valid, executing payload
Please enter debug payload.
The debug payload is successfully loaded to address 0x8000 and executes successfully.
Static Analysis
Even without understanding the exact workings, something is immediately interesting: there is now a call to the sha512 function.
Examining the flow control graph for the main provides more context for why this call exists.
The sha512 function call is in conditional block 0x44c0. It is reasonable to assume that the sha512 function computes a SHA512 checksum. After this call, two values that are exactly 64 bytes long—most likely two checksums—are compared using the memcmp function.
What seems to be a boolean return value is then checked in conditional block 44fa.
If the comparison passes, the code reaches the conditional block at address 0x4508, which executes the payload.
This snippet suggests there is an alternate path for exploitation. It is reasonable to assume that the ed25519 implementation probably has not changed, so this new SHA512 verification mechanism presents the most likely target. The objective is to craft a payload such that execution reaches the conditional block where the register indirect call occurs (at address 0x451c).
Discerning details of control flow requires correlating conditional blocks with status messages.
Status Messages
| String Address | String | Address of Conditional Block Containing Referencing Code |
|---|---|---|
| 4686 | "Welcome to the secure program loader." | 443e |
| 46ac | "Please enter debug payload." | 444a |
| 46c8 | "Load address outside allowed range of 0x8000-0xF000" | 448a |
| 46fc | "Invalid payload length" | 44a0 |
| 4713 | "Invalid signature type" | 44f0 |
| 472a | "Incorrect signature, continuing" | 44fe |
| 474a | "Signature valid, executing payload" | 4508 |
The "Invalid signature type" status message, in particular, is worth noting because it was not present in the previous firmware versions.
Dynamic Analysis
The first step is to break at address 0x44c0, provide the example debug payload as input, and see if execution reaches the conditional block of interest. While the signature verification check passes, the program skips the block. The next question is how it parses the payload to determine which branch to take.
The payload format is very similar to the one from St. John's. The signature section is 64 bytes long, suggesting it could be either a SHA512 checksum or an ed25519 signature.
800000063041c26436953f8f3cadf1442fc218b185051ab6c20853a45f093fc32adf31529d05a5ec3e96a9e41ed9ad1b14dcbdb98e50e37a7ddc3d595b867807ed1605f2070e
Aside from the signature changing (presumably because the developers rotated the leaked private key), the payload format is identical to the one from St. John's.
Load address
800000063041c26436953f8f3cadf1442fc218b185051ab6c20853a45f093fc32adf31529d05a5ec3e96a9e41ed9ad1b14dcbdb98e50e37a7ddc3d595b867807ed1605f2070e
Size
800000063041c26436953f8f3cadf1442fc218b185051ab6c20853a45f093fc32adf31529d05a5ec3e96a9e41ed9ad1b14dcbdb98e50e37a7ddc3d595b867807ed1605f2070e
Code
800000063041c26436953f8f3cadf1442fc218b185051ab6c20853a45f093fc32adf31529d05a5ec3e96a9e41ed9ad1b14dcbdb98e50e37a7ddc3d595b867807ed1605f2070e
Unknown Byte
There is once again an unknown byte before the size field.
800000063041c26436953f8f3cadf1442fc218b185051ab6c20853a45f093fc32adf31529d05a5ec3e96a9e41ed9ad1b14dcbdb98e50e37a7ddc3d595b867807ed1605f2070e
The rest of the payload is well understood. The load address, size, executable code section, and signature probably work similarly to the St. John's equivalents. The unknown byte is the only possible field in the payload that does not have a previously documented purpose.
The implementation reads the payload to address 0x2420 in the following conditional block.
The unknown byte is at address 0x2422. The XREFs to that location are as follows.
The code at address 0x4478 is in the same conditional block that calls getsn to read in the payload.
The unknown byte preceding the size field, by process of elimination, must control which branch is taken (SHA512 or ed25519 verification). This field probably contains the signature type referenced by the "Invalid signature type" status message.
Debug Payload Format
| Load Address | Signature Type | Size | Executable code | Signature |
|---|---|---|---|---|
8000 |
00 |
06 |
3041 (RET) |
c26436953f8f3cadf... |
Crafting Test Payloads
The first step is to see what happens when setting the signature type field to an arbitrary value. The payload below sets it to 0xFF.
8000ff063041c26436953f8f3cadf1442fc218b185051ab6c20853a45f093fc32adf31529d05a5ec3e96a9e41ed9ad1b14dcbdb98e50e37a7ddc3d595b867807ed1605f2070eAs expected, this prints the following text to the I/O console:
Welcome to the secure program loader.
Please enter debug payload.
Invalid signature type
Please enter debug payload.
The next question is how to make execution reach the call to sha512. Like the example payload, this one fails to hit the conditional block at address 0x44c0. The conditional block that branches to address 0x44c0 is below.
The signature type field was loaded into R9 previously. Setting the signature type field to a value of 0x01 should cause this conditional check to pass.
800001063041c26436953f8f3cadf1442fc218b185051ab6c20853a45f093fc32adf31529d05a5ec3e96a9e41ed9ad1b14dcbdb98e50e37a7ddc3d595b867807ed1605f2070eThe above payload (after breaking at address 0x44c0) results in execution reaching the conditional block containing the call to sha512.
Continuing execution prints the following messages to the console.
Welcome to the secure program loader.
Please enter debug payload.
Incorrect signature, continuing
Please enter debug payload.
The next goal is to determine how to make it branch to the register indirect call that executes the debug payload.
SHA512 Calling Convention
The next goal is to understand the parameters passed to the sha512 function.
The register state at this point in execution is as follows.
pc 44c8 sp 43c0 sr 0003 cg 0000
r04 0000 r05 5a08 r06 0000 r07 0000
r08 2426 r09 0001 r10 0006 r11 8000
r12 4400 r13 43c0 r14 0006 r15 2420
Proceeding from the assumption that the implementation is similar to St. John's, R14 seems to contain the value from the payload size field. The value in R15 is a pointer to the payload. Register R13 contains a pointer to the stack, which is most likely where the firmware writes the SHA512 hex digest of the payload after it is calculated (i.e., it is a pointer to the location to store the return value).
| Register | Description | Type |
|---|---|---|
| r13 | Return Value | int * |
| r14 | Size | int |
| r15 | Data | char * |
┌───────────────────────────────────────────────┐
│ DATA SECTION │
├───────┬───────────────────────────────────────┤
│ADDRESS│ DATA │
├───────┼───────────────────────────────────────┤
│ 2400 │a09a e3e8 3008 5a01 6964 1e1e 2211 8b45│
├───────┼───────────────────────────────────────┤
│ 2410 │7f9a 95e7 a133 643c b578 fb0c 2594 0c4f│
├───────┼───────────────────────────────────────┤ ┌───┬───────┐
│ 2420 │8000 0106 3041 c264 3695 3f8f 3cad f144│◄─┤R15│MESSAGE│
├───────┼───────────────────────────────────────┤ └───┴───────┘
│ 2430 │2fc2 18b1 8505 1ab6 c208 53a4 5f09 3fc3│
├───────┼───────────────────────────────────────┤
│ 2440 │2adf 3152 9d05 a5ec 3e96 a9e4 1ed9 ad1b│
├───────┼───────────────────────────────────────┤
│ 2450 │14dc bdb9 8e50 e37a 7ddc 3d59 5b86 7807│
├───────┼───────────────────────────────────────┤
│ 2460 │ed16 05f2 070e 0000 0000 0000 0000 0000│
├───────┼───────────────────────────────────────┤
│ 2470 │0000 0000 0000 0000 0000 0000 0000 0000│
└───────┴───────────────────────────────────────┘
┌───────────────────────────────────────────────┐
│ STACK │
├───────┬───────────────────────────────────────┤
│ADDRESS│ DATA │
├───────┼───────────────────────────────────────┤
│ 43b0 │3e45 3e45 0200 b645 0200 2024 ff03 bc44│
├───────┼───────────────────────────────────────┤ ┌───┬───────────────┐
│ 43c0 │c264 3695 3f8f 3cad f144 2fc2 18b1 8505│◄─┤R13│CHECKSUM BUFFER│
├───────┼───────────────────────────────────────┤ └───┴───────────────┘
│ 43d0 │1ab6 c208 53a4 5f09 3fc3 2adf 3152 9d05│
├───────┼───────────────────────────────────────┤ ┌───┬────────────┐
│ 43e0 │a5ec 3e96 a9e4 1ed9 ad1b 14dc bdb9 8e50│ │R14│MESSAGE SIZE│
├───────┼───────────────────────────────────────┤ ├───┴────────────┤
│ 43f0 │e37a 7ddc 3d59 5b86 7807 ed16 05f2 070e│ │ 0006 │
└───────┴───────────────────────────────────────┘ └────────────────┘
Checksum Verification
After the call to sha512, the stack is as follows.
┌───────────────────────────────────────────────┐
│ STACK │
├───────┬───────────────────────────────────────┤
│ADDRESS│ DATA │
├───────┼───────────────────────────────────────┤ ┌───┬───────────────┐
│ 43c0 │c264 3695 3f8f 3cad f144 2fc2 18b1 8505│◄─┤R13│CHECKSUM BUFFER│
├───────┼───────────────────────────────────────┤ └───┴───────────────┘
│ 43d0 │1ab6 c208 53a4 5f09 3fc3 2adf 3152 9d05│
├───────┼───────────────────────────────────────┤
│ 43e0 │a5ec 3e96 a9e4 1ed9 ad1b 14dc bdb9 8e50│
├───────┼───────────────────────────────────────┤
│ 43f0 │e37a 7ddc 3d59 5b86 7807 ed16 05f2 070e│
└───────┴───────────────────┬───────────────────┘
│
▼ CALL
┌──────┐
│sha512│
└──┬───┘
│
▼ RETURN
┌───────┬───────────────────────────────────────┐ ┌───┬───────────────┐
│ 43c0 │7d11 c6bf ae64 2cbc 36a5 cd74 7b74 4427│◄─┤R13│CHECKSUM BUFFER│
├───────┼───────────────────────────────────────┤ └───┴───────────────┘
│ 43d0 │a085 2f4e 89ca 1b9f c3b2 2a85 c249 5612│
├───────┼───────────────────────────────────────┤
│ 43e0 │bae7 5246 3042 19d3 f394 8882 b9ea 51e4│
├───────┼───────────────────────────────────────┤
│ 43f0 │59c2 1904 5b42 29d0 e345 ca70 6324 2391│
└───────┴───────────────────────────────────────┘
This data is the SHA512 checksum of the first six bytes in the payload. Confirming that the checksum is correct can be accomplished using the following Python code.
python3
>>> import binascii
>>> import hashlib
>>> payload = binascii.unhexlify("800001063041")
>>> binascii.hexlify(hashlib.sha512(payload).digest())
b'7d11c6bfae642cbc36a5cd747b744427a0852f4e89ca1b9fc3b22a85c2495612bae75246304219d3f3948882b9ea51e459c219045b4229d0e345ca7063242391'
Following this is the call to memcmp.
The register state at this point in execution is as follows.
pc 44d4 sp 43c0 sr 0000 cg 0000
r04 0000 r05 5a08 r06 0000 r07 0000
r08 2426 r09 0001 r10 0006 r11 8000
r12 4400 r13 0040 r14 2426 r15 43c0
The conjectured calling convention for memcmp is straightforward.
| Register | Description | Type |
|---|---|---|
| r13 | Size | int |
| r14 | Memory Area 1 | char * |
| r15 | Memory Area 2 | char * |
The register R14 points to the signature field for the current payload. R15 points to the stack buffer containing the SHA512SUM calculated for the non-signature part of the payload (during the call to sha512 at 0x44c8).
┌───────────────────────────────────────────────┐
│ DATA SECTION │
├───────┬───────────────────────────────────────┤
│ADDRESS│ DATA │
├───────┼───────────────────────────────────────┤
│ 2400 │a09a e3e8 3008 5a01 6964 1e1e 2211 8b45│
├───────┼───────────────────────────────────────┤
│ 2410 │7f9a 95e7 a133 643c b578 fb0c 2594 0c4f│
├───────┼───────────────────────────────────────┤ ┌───┬──────┐
│ 2420 │8000 0106 3041 c264 3695 3f8f 3cad f144│◄─┤R14│AREA 1│
├───────┼───────────────────────────────────────┤ └───┴──────┘
│ 2430 │2fc2 18b1 8505 1ab6 c208 53a4 5f09 3fc3│
├───────┼───────────────────────────────────────┤
│ 2440 │2adf 3152 9d05 a5ec 3e96 a9e4 1ed9 ad1b│
├───────┼───────────────────────────────────────┤
│ 2450 │14dc bdb9 8e50 e37a 7ddc 3d59 5b86 7807│
├───────┼───────────────────────────────────────┤
│ 2460 │ed16 05f2 070e 0000 0000 0000 0000 0000│
└───────┴───────────────────┬───────────────────┘
│
┌─────────────────────────────┘
│
│ ┌───────┬───────────────────────────────────────┐ ┌───┬──────┐
│ │ 43c0 │7d11 c6bf ae64 2cbc 36a5 cd74 7b74 4427│◄─┤R15│AREA 2│
│ ├───────┼───────────────────────────────────────┤ └───┴──────┘
│ │ 43d0 │a085 2f4e 89ca 1b9f c3b2 2a85 c249 5612│
│ ├───────┼───────────────────────────────────────┤ ┌───┬────┐
│ │ 43e0 │bae7 5246 3042 19d3 f394 8882 b9ea 51e4│ │R13│SIZE│
│ ├───────┼───────────────────────────────────────┤ ├───┴────┤
│ │ 43f0 │59c2 1904 5b42 29d0 e345 ca70 6324 2391│ │ 0040 │
│ └───────┴───────────────────┬───────────────────┘ └────────┘
│ │
│ ▼
│ ┌──────┐
└─────────────────────────►│memcmp│
└──────┘
The implementation compares these two arrays of bytes. The below conditional block checks the resulting return value.
If this conditional check passes, the program jumps to conditional block 0x4508, and the payload executes.
SHA512 Is Not A DSA
The above behavior constitutes a logical vulnerability that essentially boils down to security through obscurity. The algorithm verifies that the data has not been corrupted by calculating the checksum of the data and comparing it to the checksum in the payload signature field, but it has no way of verifying that the payload comes from a trusted party. Hashing is incorrectly used instead of signing. The "Incorrect signature type" message is misleading: the implementation does not toggle between two digital signature algorithms (DSAs) because SHA512 is not a DSA.
Exploitation
Developing a working attack is conceptually simple. First, create a valid load address, set the signature type to 0x01, reuse the portable shellcode, and set the size field appropriately. Concatenate all of this data into a single byte string, then calculate the SHA512 checksum of that byte string in Python and append it to the end of the payload.
Payload
| Load Address | Signature Type | Size (Bytes) | Executable code | Checksum |
|---|---|---|---|---|
8000 |
01 |
0c |
3240 00ff b012 1000 |
80a0ca7614b65324... |
Reusing the SHA512 Python code to calculate the checksum yields the following result.
>>> import binascii
>>> import hashlib
>>> payload = binascii.unhexlify("8000010c324000ffb0121000")
>>> binascii.hexlify(hashlib.sha512(payload).digest())
b'80a0ca7614b653247b207a739e8a5445bfc34f755d4bd0bd413ec5f65a748fe04f9488f7e10700b5bfb57f41ba56f2a314a0f9545b74d08764af7a5c0cfc40ec'
Final Payload
8000010c324000ffb012100080a0ca7614b653247b207a739e8a5445bfc34f755d4bd0bd413ec5f65a748fe04f9488f7e10700b5bfb57f41ba56f2a314a0f9545b74d08764af7a5c0cfc40ecResult
When provided as an input, the console prints the following.
Welcome to the secure program loader.
Please enter debug payload.
Incorrect signature, continuing
Please enter debug payload.
Execution does not reach the debug payload at address 0x8000.
Debugging
The error is unusual, as this should be a relatively straightforward operation. The checksum provided in the payload matches the one calculated by the firmware, which is verifiable by inspecting the stack just after the return from sha512.
43c0: 80a0 ca76 14b6 5324 7b20 7a73 9e8a 5445
43d0: bfc3 4f75 5d4b d0bd 413e c5f6 5a74 8fe0
43e0: 4f94 88f7 e107 00b5 bfb5 7f41 ba56 f2a3
43f0: 14a0 f954 5b74 d087 64af 7a5c 0cfc 40ec
The next likely place to check is the conditional jump after the memcmp call that determines whether the checksums match.
This behavior is an implementation bug. Generally speaking, functions like strcmp or memcmp return zero if there is a complete match between the two compared variables. In this case, the main function incorrectly interprets a memcmp call with return code 0x1 as valid when that means there is a single-bit difference in the compared strings.
Constructing a string that returns a value of 0x1 after the memcmp call requires understanding how these functions generally work. From the Linux man page for memcmp:
NAME
memcmp - compare memory areas
SYNOPSIS
#include
int memcmp(const void *s1, const void *s2, size_t n);
DESCRIPTION
The memcmp() function compares the first n bytes (each in‐
terpreted as unsigned char) of the memory areas s1 and s2.
RETURN VALUE
The memcmp() function returns an integer less than, equal
to, or greater than zero if the first n bytes of s1 is
found, respectively, to be less than, to match, or be
greater than the first n bytes of s2.
For a nonzero return value, the sign is determined by the
sign of the difference between the first pair of bytes
(interpreted as unsigned char) that differ in s1 and s2.
If n is zero, the return value is zero.
Arbitrary Code Execution
It is possible to force the memcmp function to return 0x1 by adding or subtracting one bit from any given byte in the checksum. Any byte after the first difference will not affect the return value, which means it is possible to trick the conditional check into passing by fiddling with the two least significant bits of the last byte in the payload. Because it is not superficially obvious which string is s1 or s2, it is necessary to produce two modified payloads: the first will have 0x1 added to the last byte, and the second will have 0x1 subtracted from it. For reference, here is the end of the original:
...14a0f9545b74d08764af7a5c0cfc40ecThe above snippet highlights the last byte (0xEC). Changing that byte to 0xED or 0xEB results in the following payloads.
...14a0f9545b74d08764af7a5c0cfc40ed...14a0f9545b74d08764af7a5c0cfc40ebThe first will fail with an "incorrect signature" status message, while the second will result in arbitrary code execution.
Welcome to the secure program loader.
Please enter debug payload.
Signature valid, executing payload
Final Payload
8000010c324000ffb012100080a0ca7614b653247b207a739e8a5445bfc34f755d4bd0bd413ec5f65a748fe04f9488f7e10700b5bfb57f41ba56f2a314a0f9545b74d08764af7a5c0cfc40ebDoor Unlocked
The CPU completed in 22073 cycles.Alternate Approaches
There is no restriction dictating that the last byte specifically must be modified. Recall that memcmp returns the difference for the first pair of mismatched bytes, which means that it is possible to have a checksum in the signature section of the payload that is only a single byte. For example, the following payload results in arbitrary code execution.
8000010c324000ffb01210007fThis behavior is uninteresting in isolation, but it becomes critically important when attempting to circumvent one of the likely fixes discussed below.
Remediation
The core issue is that neither SHA512 nor any other cryptographic checksum is safe to treat as equivalent to a digital signature. The current implementation prevents accidental corruption of the payload during transmission, but it does not guarantee that malicious parties cannot tamper with it. While there are two potential fixes, only the first should be considered under ideal circumstances (the second is a suboptimal design).
1. Use a real DSA.
SHA512 is not a DSA. The best solution would be to revert to the Cold Lake firmware and implement the fixes suggested in the remediation section of that write-up.
2. Whitelist hardcoded payload checksums.
It is possible for checksum comparison to provide an equivalent level of security to a digital signature: the firmware could have a whitelist of hashes for debug payloads that it will accept. This solution comes with the caveat that it is impossible to update the whitelist without needing a firmware update for every device in the field.
Even with a hardcoded hash whitelist, it is possible to craft a payload such that the first byte of the payload checksum is 0x1 off from the first byte of the whitelisted checksum. Such an exploit requires appending a few extra random bytes to the end of the shellcode. Suppose, for example, that there is a whitelisted SHA512 checksum that begins with the byte 0xFE. The payload to generate the collision is as follows:
| Load Address | Signature Type | Size (Bytes) | Executable code | Collision Bytes | Checksum |
|---|---|---|---|---|---|
8000 |
01 |
0e |
3240 00ff b012 1000 |
???? |
ff |
The collision bytes should be brute-forced until the checksum for the payload begins with 0xFF, at which point it will pass the conditional check and result in arbitrary code execution—even with a whitelist.
Thus, a proper patch requires including a hardcoded whitelist of approved payload hashes and fixing the check at 0x44fa to execute arbitrary code only if the memcmp return value is zero. Otherwise, it is possible to generate partial SHA512 collisions that will cause the check to pass.