I’ll See Your FPGA and Raise You a Pencil:
Cracking Hashes on the Back of a Napkin

Executive Summary

Fifty thousand people tried this; five hundred succeeded. Ten wrote about it: five brute-forced it in a higher level language, Alex van Poppelen
Vítězslav Čížek
Zijun Hui
Ichiji001
Tux3 three used z3, Guillaume Vigeant
Grazfather
Laanwj and one broke the algorithm eighteen ways on an FPGA. Aaron Ferrucci Here's how to crack it in five lines of math on the back of a napkin.

Overview

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.

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.

Disassembly

3240 00ff      mov     #0xff00, sr
b012 1000      call    #0x10

Assembly

324000ffb0121000

On this firmware version, there is a dedicated function that does this. The following message is displayed in the interface when the implementation calls this interrupt successfully.

High-Level Analysis

The Hollywood firmware includes the following countermeasures.

1. Jumps into the middle of multi-word instructions to break linear sweep disassemblers.
2. Runtime packing.
3. ASLR for each instruction.
4. The Poor Man's Virtual Machine.
5. A custom hashing algorithm.

Other walkthroughs explain how to circumvent these countermeasures in greater detail. Those wishing for a more complete analysis should consult the one by Grazfather.

Counter-Countermeasures

The problem posed by the code jumping into the middle of multi-word instructions is relatively simple to circumvent with a program like Ghidra or IDA Pro, which are intelligent enough to follow the actual control flow and avoid instruction mangling. This tooling provides little information because it later chokes on the runtime packing.

Breaking The ASLR

The first objective is to break the random number generator so that it always adds zero to the base address. The following debugger macro patches the rand interrupt calls so they always return zero.

let 44c2=430f; let 44c4=4302; let 456e=430f; let 4570=4302

The Poor Man's Virtual Machine

After single-stepping and manually reading a few thousand opcodes, it becomes apparent that there are intermittent calls to address 0xe000. On each call, that address will contain a single unique instruction that will execute before returning. Again, this is after breaking the ASLR by patching out the rand calls. If the rand calls are left unpatched, the implementation will generate a random number, add it to the base address 0xe000, copy one instruction to the resulting randomized address, append a RET instruction, call the gadget, and zero it afterward. This cycle will then repeat. Another author, Guillaume Vigeant, referred to this behavior as a "poor man's virtual machine".

Extracting The Algorithm

The "virtual machine" instructions can be single-stepped by breaking at address 0xe000, continuing, and observing the contents of the PC register with each iteration. The string below prints to the console, one character at a time, with every two steps.

What's the password?

The state of the system is only interesting after it reads untrusted input. Skipping to the gets interrupt call requires unbreaking address 0xe000 and continuing, which causes execution to skip to the prompt for user input. The macro to achieve this, starting from a reset, is as follows.

let 44c2=430f; let 44c4=4302; let 456e=430f; let 4570=4302; c; break e000

Stepping through VM execution from this point onward allows manual extraction of the following algorithm, instruction by instruction.

mov      #0x2600, r5
clr      r6
add      @r5, r4
swpb     r4
xor      @r5+, r6
xor      r4, r6
xor      r6, r4
xor      r4, r6
tst      0x0(r5)
mov      sr, r7
and      #0x2, r7
rra      r7
xor      #0x1, r7
swpb     r7
rra      r7
sxt      r7
swpb     r7
sxt      r7
mov      #0x4b18, r8
and      r7, r8
xor      #-0x1, r7
and      #0x47aa, r7
add      r7, r8
clr      r7
add      @r5, r4
swpb     r4
xor      @r5+, r6
xor      r4, r6
xor      r6, r4
xor      r4, r6
tst      0x0(r5)
mov      sr, r7
and      #0x2, r7
rra      r7
xor      #0x1, r7
swpb     r7
rra      r7
mov      #0x4b18, r8
and      r7, r8
xor      #-0x1, r7
and      #0x47aa, r7
add      r7, r8
clr      r7
cmp      #0xfeb1, r4
mov      sr, r7
clr      r4
cmp      #0x9298, r6
and      sr, r7
clr      r6
rra      r7
xor      #0x1, r7
swpb     r7
rra      r7
rra      r7
rra      r7
rra      r7
bis      r7, sr

Custom Hashing Algorithm

This code is very similar to the bytecode emitted by a JIT compiler—a higher-level abstraction may be generating it on the fly.

Success Condition

The following checks occur near the end of the algorithm.

cmp      #0xfeb1, r4
mov      sr, r7
clr      r4
cmp      #0x9298, r6
and      sr, r7
clr      r6

These instructions set the contents of R7 based on the boolean result of the CMP instructions. After some massaging, this value is XORed with SR.

rra      r7
xor      #0x1, r7
swpb     r7
rra      r7
rra      r7
rra      r7
rra      r7
bis      r7, sr

For context, some bits in SR are hardware control flags. See Figure 3-6 in this document.

If the previous comparisons fail, the code sets the "CPU OFF" bit in SR via a convoluted series of bitwise operations, halting the processor. If they succeed, that bit remains unset, and the firmware calls the unlock interrupt. The extracted algorithm comes from an execution trace, which does not include the unlock interrupt call because that instruction only executes when the password is valid. The goal is simple: craft an input such that registers R4 and R6 contain 0xfeb1 and 0x9298, respectively.

Control Flow

This algorithm iterates over the supplied password, one 16-bit word at a time, to calculate a four-byte hash. The diagram below depicts the relevant sections of the algorithm. Only operations that affect the contents of R4 and R6 are relevant. The diagram omits the rest of the instructions for brevity.

┌─────────┐ ┌────────────────────┐        
│ INITIAL │ │mov      #0x2600, r5│        
│ SETUP   │ │clr      r6         │        
└─────────┘ └────────────────────┘        
                                          
┌─────────┐ ┌────────────────────┐◄──────┐
│         │ │add      @r5, r4    │       │
│         │ │swpb     r4         │       │
│HASHING  │ │xor      @r5+, r6   │       │
│ALGORITHM│ │xor      r4, r6     │ "JNZ" │
│         │ │xor      r6, r4     │       │
│         │ │xor      r4, r6     │       │
│         │ │tst      0x0(r5)    │       │
└─────────┘ └────────────────────┴───────┘
                                          
┌─────────┐ ┌────────────────────┐        
│         │ │cmp      #0xfeb1, r4│        
│         │ │mov      sr, r7     │        
│         │ │clr      r4         │        
│         │ │cmp      #0x9298, r6│        
│         │ │and      sr, r7     │        
│ CHECK   │ │clr      r6         │        
│ OUTPUT  │ │rra      r7         │        
│ VALID   │ │xor      #0x1, r7   │        
│         │ │swpb     r7         │        
│         │ │rra      r7         │        
│         │ │rra      r7         │        
│         │ │rra      r7         │        
│         │ │rra      r7         │        
│         │ │bis      r7, sr     │        
└─────────┘ └────────────────────┘        

Constraints

The algorithm breaks out of the loop when the current word is null. It is possible to have null bytes in the password, but null words are prohibited.

Understanding The Algorithm

Consider the highlighted section below.

┌─────────┐ ┌────────────────────┐◄──────┐
│         │ │add      @r5, r4    │       │
│         │ │swpb     r4         │       │
│HASHING  │ │xor      @r5+, r6   │       │
│ALGORITHM│ │xor      r4, r6     │ "JNZ" │
│         │ │xor      r6, r4     │       │
│         │ │xor      r4, r6     │       │
│         │ │tst      0x0(r5)    │       │
└─────────┘ └────────────────────┴───────┘

As other writeups have observed, this effectively swaps the contents of R4 and R6. The x86 platform typically implements such an operation with a single XCHG instruction. While the following assembly is not valid for the MSP430 ISA, the visual tweak makes the algorithm simpler to understand.

┌─────────┐ ┌────────────────────┐◄──────┐
│         │ │add      @r5, r4    │       │
│HASHING  │ │swpb     r4         │       │
│ALGORITHM│ │xor      @r5+, r6   │ "JNZ" │
│         │ │xchg     r4, r6     │       │
│         │ │tst      0x0(r5)    │       │
└─────────┘ └────────────────────┴───────┘

Test Input

Consider what happens with the following test password. Note that all inputs are hex strings.

11223344

Algorithm Behavior

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├──┬──┤      ├──┬──┤  
       │00│00│      │00│00│  
       └──┴──┘      └──┴──┘  
                             
                             
                             
                             
                             
┌──────┬──┬──┬──┬──┬──┬──┐   
│INPUT │11│22│33│44│00│00│   
└──────┴──┴──┴──┴──┴──┴──┘   
        ▲                    
        │                    
       ┌┴───┐                
       │ R5 │                
       └────┘                
                             
┌──┐   ┌────────────────────┐
│PC├─► │add      @r5, r4    │
└──┘   │swpb     r4         │
       │xor      @r5+, r6   │
       │xchg     r4, r6     │
       │tst      0x0(r5)    │
       └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├──┬──┤      ├──┬──┤  
       │22│11│      │00│00│  
       └──┴──┘      └──┴──┘  
       ▲     ▲               
       │     │               
       │ ADD │               
       │     │               
       │     │               
┌──────┼──┬──┼──┬──┬──┬──┐   
│INPUT │11│22│33│44│00│00│   
└──────┴──┴──┴──┴──┴──┴──┘   
        ▲                    
        │                    
       ┌┴───┐                
       │ R5 │                
       └────┘                
                             
       ┌────────────────────┐
┌──┐   │add      @r5, r4    │
│PC├─► │swpb     r4         │
└──┘   │xor      @r5+, r6   │
       │xchg     r4, r6     │
       │tst      0x0(r5)    │
       └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├──┬──┤      ├──┬──┤  
       │11│22│      │00│00│  
       └──┴──┘      └──┴──┘  
                             
        ◄────                
        SWPB                 
        ────►                
                             
┌──────┬──┬──┬──┬──┬──┬──┐   
│INPUT │11│22│33│44│00│00│   
└──────┴──┴──┴──┴──┴──┴──┘   
        ▲                    
        │                    
       ┌┴───┐                
       │ R5 │                
       └────┘                
                             
       ┌────────────────────┐
       │add      @r5, r4    │
┌──┐   │swpb     r4         │
│PC├─► │xor      @r5+, r6   │
└──┘   │xchg     r4, r6     │
       │tst      0x0(r5)    │
       └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├──┬──┤      ├──┬──┤  
       │11│22│      │22│11│  
       └──┴──┘      └──┴──┘  
                    ▲     ▲  
       ┌────────────┘     │  
       │       XOR        │  
       │     ┌────────────┘  
       │     │               
┌──────┼──┬──┼──┬──┬──┬──┐   
│INPUT │11│22│33│44│00│00│   
└──────┴──┴──┴──┴──┴──┴──┘   
              ▲              
              │              
             ┌┴───┐          
             │ R5 │          
             └────┘          
                             
       ┌────────────────────┐
       │add      @r5, r4    │
       │swpb     r4         │
┌──┐   │xor      @r5+, r6   │
│PC├─► │xchg     r4, r6     │
└──┘   │tst      0x0(r5)    │
       └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├─────┤◄─────┼─────┤  
       │22 11│ XCHG │11 22│  
       └─────┴─────►└─────┘  
                             
                             
                             
                             
                             
┌──────┬──┬──┬──┬──┬──┬──┐   
│INPUT │11│22│33│44│00│00│   
└──────┴──┴──┴──┴──┴──┴──┘   
              ▲              
              │              
             ┌┴───┐          
             │ R5 │          
             └────┘          
                             
       ┌────────────────────┐
       │add      @r5, r4    │
       │swpb     r4         │
       │xor      @r5+, r6   │
┌──┐   │xchg     r4, r6     │
│PC├─► │tst      0x0(r5)    │
└──┘   └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├──┬──┤      ├──┬──┤  
       │22│11│      │11│22│  
       └──┴──┘      └──┴──┘  
                             
                             
                             
                             
                             
┌──────┬──┬──┬──┬──┐         
│INPUT │33│44│00│00│         
└──────┴──┴──┴──┴──┘         
        ▲                    
        │                    
       ┌┴───┐                
       │ R5 │                
       └────┘                
                             
┌──┐   ┌────────────────────┐
│PC├─► │add      @r5, r4    │
└──┘   │swpb     r4         │
       │xor      @r5+, r6   │
       │xchg     r4, r6     │
       │tst      0x0(r5)    │
       └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├──┬──┤      ├──┬──┤  
       │66│44│      │11│22│  
       └──┴──┘      └──┴──┘  
       ▲     ▲               
       │     │               
       │ ADD │               
       │     │               
       │     │               
┌──────┼──┬──┼──┬──┐         
│INPUT │33│44│00│00│         
└──────┴──┴──┴──┴──┘         
        ▲                    
        │                    
       ┌┴───┐                
       │ R5 │                
       └────┘                
                             
       ┌────────────────────┐
┌──┐   │add      @r5, r4    │
│PC├─► │swpb     r4         │
└──┘   │xor      @r5+, r6   │
       │xchg     r4, r6     │
       │tst      0x0(r5)    │
       └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├──┬──┤      ├──┬──┤  
       │44│66│      │11│22│  
       └──┴──┘      └──┴──┘  
                             
        ◄────                
        SWPB                 
        ────►                
                             
┌──────┬──┬──┬──┬──┐         
│INPUT │33│44│00│00│         
└──────┴──┴──┴──┴──┘         
        ▲                    
        │                    
       ┌┴───┐                
       │ R5 │                
       └────┘                
                             
       ┌────────────────────┐
       │add      @r5, r4    │
┌──┐   │swpb     r4         │
│PC├─► │xor      @r5+, r6   │
└──┘   │xchg     r4, r6     │
       │tst      0x0(r5)    │
       └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├──┬──┤      ├──┬──┤  
       │44│66│      │55│11│  
       └──┴──┘      └──┴──┘  
                    ▲     ▲  
       ┌────────────┘     │  
       │       XOR        │  
       │     ┌────────────┘  
       │     │               
┌──────┼──┬──┼──┬──┐         
│INPUT │33│44│00│00│         
└──────┴──┴──┴──┴──┘         
              ▲              
              │              
             ┌┴───┐          
             │ R5 │          
             └────┘          
                             
       ┌────────────────────┐
       │add      @r5, r4    │
       │swpb     r4         │
┌──┐   │xor      @r5+, r6   │
│PC├─► │xchg     r4, r6     │
└──┘   │tst      0x0(r5)    │
       └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├─────┤◄─────┼─────┤  
       │55 11│ XCHG │44 66│  
       └─────┴─────►└─────┘  
                             
                             
                             
                             
                             
┌──────┬──┬──┬──┬──┐         
│INPUT │33│44│00│00│         
└──────┴──┴──┴──┴──┘         
              ▲              
              │              
             ┌┴───┐          
             │ R5 │          
             └────┘          
                             
       ┌────────────────────┐
       │add      @r5, r4    │
       │swpb     r4         │
       │xor      @r5+, r6   │
┌──┐   │xchg     r4, r6     │
│PC├─► │tst      0x0(r5)    │
└──┘   └────────────────────┘

       ┌─────┐      ┌─────┐  
       │ R4  │      │ R6  │  
       ├──┬──┤      ├──┬──┤  
       │55│11│      │44│66│  
       └──┴──┘      └──┴──┘  
                             
                             
                             
                             
                             
┌──────┬──┬──┐               
│INPUT │00│00│               
└──────┴──┴──┘               
        ▲                    
        │                    
       ┌┴───┐                
       │ R5 │                
       └────┘                
                             
       ┌────────────────────┐
       │add      @r5, r4    │
       │swpb     r4         │
       │xor      @r5+, r6   │
       │xchg     r4, r6     │
       │tst      0x0(r5)    │
       └────────────────────┘

• 01
• 02
• 03
• 04
• 05
• 06
• 07
• 08
• 09
• 10
• 11

Brute-Forcing Hollywood in a Custom Computing Machine

Most people with working exploits reimplement the algorithm in a higher-level language and brute-force the password (although some choose to use z3). Then, there is this individual.

I concluded that I don't know the required math for solving this sort of puzzle. [...] Adding to my shame at not being able to simply solve for the password with math: the brute-force search for 5-byte passwords takes about 12 hours to run on my pretty-modern laptop. Then I thought of a way to salvage my dignity: I know how to design digital logic; I have access to programmable logic hardware; why not build a custom computing machine to find the passwords?
— Aaron Ferrucci

This FPGA implementation can brute-force all possible five-byte preimages in the time it takes to make coffee. Congratulations to Mr. Ferrucci for becoming a gold medalist in the resume-padding Olympics.

$ cloc hollywood_fpga_hash/
      29 text files.
      28 unique files.                              
       6 files ignored.

github.com/AlDanial/cloc v 1.86  T=0.03 s (754.2 files/s, 232788.2 lines/s)
---------------------------------------------------------------------
Language              files         blank       comment          code
---------------------------------------------------------------------
XML                       3             0             0          5094
Tcl/Tk                    5           108           302           744
Verilog-SystemVerilog     7            74            18           372
C                         2            39             7           288
Markdown                  1            28             0           188
Stata                     2             0             0            82
make                      2             9             0            37
Mathematica               1             3             0            12
Bourne Shell              1             0             1             2
---------------------------------------------------------------------
SUM:                     24           261           328          6819
---------------------------------------------------------------------

I'll see your custom computing machine and raise you a napkin sketch.

Owning this system does not require brute-forcing, SAT solvers, or FPGAs. That said, one must not begrudge those honor-bound to reimplement homebrew hashing algorithms in 372 lines of SystemVerilog to avoid obligatory seppuku (as required in the blood oath taken by all computer engineering graduates). Here is how to break the algorithm with a preimage attack in five lines of math. Why do this? Because yours truly does not like writing C. Cue the music.

Debugger Macros

The following debugger macros were helpful throughout the process of developing this technique.

#define vm-reset reset; unbreak e000
#define vm-init let 44c2=430f; let 44c4=4302; let 456e=430f; let 4570=4302; c; break e000
#define vm-init-hash c; c; c
#define vm-iter-hash c; c; c; c; c; c; c; c; c; c; c; c; c; c; c; c; c; c; c; c; c; c 

vm-reset
vm-init

vm-init-hash

vm-iter-hash

• Debugger Macros

Assumptions

All values are 16-bit integers. Let the ordered pair $\left(R_4,R_6\right)$ represent the target image. Let $H$ be a hash function, and let

$H\left(x\right)=\left(R_4,R_6\right)$

If $R_4=\mathrm{0xFEB1}$ and $R_6=\mathrm{0x9298}$, solve for $x$.

Second Preimage Attack

Instead of a preimage attack, suppose the goal was to perform a second preimage attack. That process requires finding some value $r$ with the following characteristics.

$2r\equiv 0mod{2}^{16}$
$r\ne 0$

The only 16-bit value that satisfies these constraints is 0x8000. For any arbitrary value $a$,

$H(a||a)=H(a||r||r||r||r||a)$

By way of example, the following two inputs produce the same hash.

Input #1:

ffff ffff

Input #2:

ffff 0080 0080 0080 0080 ffff

Preimage Attack

Let $f$ be a function that reverses the endianness of a 16-bit number. Let the operator $||$ represent a 16-bit little-endian integer concatenation. E.g., $(3||7)$ is "0300 0700". Given any arbitrary image $\left(R_4,R_6\right)$ on a hypothetical version of the implementation where null words are allowed,

$i_1=R_4\oplus \mathrm{0xFFFF}$
$i_2=\mathrm{0xFFFF}$
$i_3=\frac{f\left(f\right(R_6)-i_1)\oplus \mathrm{0xFFFF}}{2}$
$H(i_3||0||0||0||i_3||i_2||i_1)=(R_4\pm 1,R_6\pm 1)$

Raw Payload

b45d 0000 0000 0000 b45d ffff 4e01

On the real implementation, given $R_4=\mathrm{0xFEB1}$ and $R_6=\mathrm{0x9298}$,

$H(i_3-1||1||1||1||r\oplus 1||r||r||r||i_3+1||i_2||i_1)=\left(R_4,R_6\right)$

Raw Payload

b35d 0100 0100 0100 0180 0080 0080 0080 b55d ffff 4e01

Result

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 9979491 cycles.

Alternate Approach

The above attack is a curated version meant to be easier to understand. The original version, as implemented in July 2020, only relied on the first three equations. An earlier revision of this page claimed that breaking the algorithm "does not require math". After digging up and reviewing some four-year-old notes, it is fairer to say that it does not require much math.

$i_1=R_4\oplus \mathrm{0xFFFF}$
$i_2=\mathrm{0xFFFF}$
$i_3=\frac{f\left(f\right(R_6)-i_1)\oplus \mathrm{0xFFFF}}{2}$

The original solution involved a degree of tinkering and intuition, so it is not straightforward to formally describe The most succinct summary is "knock a few bits off the first word and plug in low values for the next dozen until it works". the process of going from the simpler theoretical implementation,

$H(i_3||0||0||0||i_{\mathrm{<mark>3</mark>}}||i_{\mathrm{<mark>2</mark>}}||i_{\mathrm{<mark>1</mark>}})=(R_4\pm 1,R_6\pm 1)$

to the practical implementation. Click here for another episode where yours truly attempts to become the Tiger Woods of code golf.

b252 0100 0100 0100 0005 0100 0001 0100 0004 0001 0100 0700 b55d ffff 4e01