Pacman (security vulnerability)

Pacman[a] is a side-channel vulnerability in certain ARM CPUs that was made public by Massachusetts Institute of Technology security researchers on June 10, 2021. It affects the pointer authentication (PAC) mechanism in many ARMv8.3 chips, including Apple's M1 CPU.[1] Pacman creates an 'oracle' that lets an attacker guess a pointer's PAC signature without crashing the program if the guess is wrong. PAC signatures are typically less than 16 bits wide, so an attacker can use the oracle to guess the signature in 216 tries or fewer. It is unfixable without hardware changes because it is caused by the inherent design of CPU caches and branch predictors.

Pacman
Logo for Pacman exploit
Date discoveredPublicly disclosed June 10, 2022; 2 years ago (2022-06-10)
Date patchedUnable to be patched
Affected hardwareApple M1 processors
Websitepacmanattack.com

Impact and response

edit

Pacman alone is not an exploitable vulnerability. PAC is a 'last line of defense'[2] that detects when software running on the CPU is being exploited by a memory corruption attack and reacts by crashing the software before the attacker completes their exploit. Apple stated that they did not believe the vulnerability posed a serious threat to users because it requires specific conditions to be exploited.[3]

Background

edit

Pacman is similar to Spectre, abusing two key CPU optimizations to create a PAC oracle: branch prediction and memory caching.[4]

PAC (Pointer Authentication Codes)

edit

PAC is a security feature in ARMv8.3-based computer processors that mitigates against return-oriented programming by adding a cryptographic signature to the upper bits of pointers. Compilers emit PAC 'sign' instructions before storing pointers to memory, and 'verify' instructions after loading pointers from memory. If an attacker tampers with the pointer, the signature becomes invalid and the program crashes when the pointer is next accessed.[5] PAC signatures are not cryptographically secure because they need to be small enough to fit into the unused upper bits of pointers. Therefore, if an attacker can reliably test whether a guessed signature is correct without crashing the program, they can brute-force the correct signature.[6]

Branch prediction

edit

Modern CPUs employ branch prediction to reduce the number of pipeline stalls caused by conditional branches. Branch prediction uses heuristics to guess the direction of a conditional branch and begin executing the predicted path – while the condition is still being evaluated. Instructions executed during this period are 'speculative', and the CPU holds their results in the re-order buffer (ROB) without writing them back to memory. Once the CPU finishes evaluating the condition and determines that its initial prediction was correct, it 'retires' the instructions in the ROB by writing their changes back to memory and propagating any exceptions produced. If the speculation was incorrect, the CPU flushes the ROB and resumes execution at the correct location.[7]

Memory caching

edit
 
A simplified schematic of a set-associative cache

CPU caches accelerate memory accesses by caching frequently accessed memory on the CPU die. This lowers the cost of memory accesses from hundreds of cycles to fewer than 10, by reducing the amount of time spent communicating with the physically separate northbridge and RAM chip. When an uncached address is loaded, the CPU immediately stashes the loaded data into the cache, evicting another entry if the cache is full. These changes are not held in the ROB because the presence or absence of an address in the cache is considered 'unobservable', so stashes and evictions that occur during speculative execution persist after the ROB has been flushed, even if that path was not ultimately taken.[8]

Mechanism

edit

Principle

edit

Pacman tricks the CPU into checking the validity of a guessed PAC signature within a mispredicted branch so that exceptions produced by potentially incorrect guesses are discarded during the ROB flush.[9] If the guess was incorrect, the exception thrown during speculative execution forces the CPU to stall, preventing further instructions from being speculatively executed. A Pacman gadget is a sequence of instructions of the following form:

if (condition):
    ptr = verify(attacker_tamperable_pointer)
    load(ptr)

Sequences of this form are common and can be found in most compiled programs supporting PAC.[10] When the CPU mispredicts the condition, it begins speculatively executing the PAC verification instruction. If the attacker's guess was correct, the verification instruction succeeds and the CPU proceeds to load the address from memory; if the guess was incorrect, the verification instruction throws an exception. This exception is held in the ROB and then discarded once the CPU finds the condition to be false. The attacker then uses a hardware side-channel to determine whether the load instruction was executed, therefore determining whether their guessed signature was correct.[11]

Attack

edit

Ravichandran et al. demonstrate that the cache-based Prime and Probe technique can be used to determine whether the load instruction executed.[11] The attacker determines if the load instruction in a Pacman gadget was executed by filling the cache with data, calling the gadget, and checking the latency of accessing the previously loaded addresses. If one of the addresses takes longer than before, it was evicted by the gadget and the attacker knows that their guess was correct. The attacker may then use this forged pointer elsewhere in the program to hijack it.

1. Train

edit

The attacker calls the Pacman gadget many times with condition = true. The branch predictor is now trained to guess that the condition is true on subsequent calls. During this period, attacker_tamperable_pointer is its original value with a valid PAC signature.

2. Prime

edit

The attacker fills the L1 cache by loading from addresses they control. The contents of these memory locations does not matter – the attacker just needs to be able to precisely measure their access latency.[12]

Initial L1 cache
Set 0
Address Value
... ...
... ...
... ...
...
Set 0x1FFF
Address Value
... ...
... ...
... ...
Primed L1 cache
Set 0
Address Value
0xab30000 AAAAAAAAA
0x1230000 AAAAAAAAA
0x1920000 AAAAAAAAA
...
Set 0x1FFF
Address Value
0x2001FFF AAAAAAAAA
0x6a21FFF AAAAAAAAA
0x09b1FFF AAAAAAAAA

3. Evict

edit

The attacker overwrites attacker_tamperable_pointer with their target pointer and guess for the target pointer's PAC signature. They then call the Pacman gadget with condition = false, causing the branch to be mispredicted. The branch predictor will speculatively execute the contents of the if statement, before eventually flushing the pipeline and rolling back.[13]

During this speculative execution, two things can occur:

  1. The speculative execution proceeds to the load() instruction. This means that the verify() instruction did not fault, implying the guessed signature was correct. The load() instruction will then load the target pointer into cache, evicting an address in the attacker's eviction set.
  2. Speculative execution faults on the verify instruction, preventing execution of the load(). This implies the guessed signature was wrong. Since this was speculatively executed within a mispredicted branch, the fault is not propagated to the program.
L1 Cache after running gadget if guess was correct
Set 0
Address Value
0xab30000 AAAAAAAAA
0x1230000 AAAAAAAAA
0x1920000 AAAAAAAAA
...
Set 0x1FFF
Address Value
pacman address my data
0x6a21FFF AAAAAAAAA
0x09b1FFF AAAAAAAAA
L1 Cache after running gadget if guess was wrong
Set 0
Address Value
0xab30000 AAAAAAAAA
0x1230000 AAAAAAAAA
0x1920000 AAAAAAAAA
...
Set 0x1FFF
Address Value
0x2001FFF AAAAAAAAA
0x6a21FFF AAAAAAAAA
0x09b1FFF AAAAAAAAA

4. Probe

edit

The attacker measures the access time for each element in their eviction set. If one of the elements was evicted (i.e., the access is slow) then the guess was correct. If none of the elements were evicted (i.e., all accesses are fast) then the guess was wrong. This process can be repeated with different guesses until the correct signature is found.[11]

Notes

edit
  1. ^ Stylized PACMAN.

References

edit
  • "PACMAN security vulnerability". developer.arm.com. Archived from the original on 2023-11-16.
  • "Pointer Authentication on ARMv8.3" (PDF). qualcomm.com.
  • Heinrich, Joe (1996). MIPS R10000 Microprocessor User's Manual (2.0 ed.). MIPS Technologies.
  • Page, Carly (2022-06-10). "MIT researchers uncover 'unpatchable' flaw in Apple M1 chips". TechCrunch.
  • Tomasulo, R. M. (January 1967). "An Efficient Algorithm for Exploiting Multiple Arithmetic Units". IBM Journal of Research and Development. 11 (1): 25–33. doi:10.1147/rd.111.0025. ISSN 0018-8646.
  • Ravichandran, Joseph; Na, Weon Taek; Lang, Jay; Yan, Mengjia (July 2023). "PACMAN: Attacking ARM Pointer Authentication With Speculative Execution". IEEE Micro. 43 (4): 11–18. doi:10.1109/MM.2023.3273189. hdl:1721.1/146470. ISSN 0272-1732.
  • Ravichandran, Joseph; Na, Weon Taek; Lang, Jay; Yan, Mengjia (18 June 2022). PACMAN: attacking ARM pointer authentication with speculative execution. Annual International Symposium on Computer Architecture. ACM. pp. 685–698. doi:10.1145/3470496.3527429. hdl:1721.1/146470. ISBN 978-1-4503-8610-4.
  • Liu, Fangfei; Yarom, Yuval; Ge, Qian; Heiser, Gernot; Lee, Ruby B. (May 2015). Last-Level Cache Side-Channel Attacks are Practical. IEEE Symposium on Security and Privacy. IEEE. pp. 605–622. doi:10.1109/SP.2015.43. ISBN 978-1-4673-6949-7.
  • Lee, Smith (January 1984). "Branch Prediction Strategies and Branch Target Buffer Design". Computer. 17 (1): 6–22. doi:10.1109/MC.1984.1658927. ISSN 0018-9162.

See also

edit
edit