spp_key_deriv.md

Physical Store Private Key Derivation

Background

As described in the TSforge blogpost, the AES key needed to decrypt the physical store's contents is encrypted using an RSA whitebox located in a component known as the blackbox/secure processor (spsys.sys on Windows Vista/7, part of sppsvc.exe on Windows 8+). Luckily, with a debugger and a basic understanding of the math behind RSA, the private key of this whitebox can be easily extracted, allowing exploits like ZeroCID to be carried out on an unmodified system.

SpModExpPrv

In the symbols for spsys.sys in Windows 8 build 7850, the whitebox is named SpModExpPrv. This function only implements plain RSA decryption with a constant private key, and other code is used to implement operations such as padding and RSA encryption.

SpModExpPrv is effectively constructed like a large virtualized ALU with multiple 1024-bit registers. This ALU is driven by a series of bytecode instructions known as "ExecCodes", which govern both the obfuscation and modular exponentiation algorithm. The ExecCodes instructions are interpreted by a function known as __Execute.

There are only two ExecCodes instructions, with each taking 3 operands. The first, MMCopy indexes1, indexes2, shufSeq, shuffles the values of the virtual registers using a sequence of bitwise XORs and value swaps determined by the values of indexes1, indexes2, and shufSeq. indexes1 and indexes2 select a set of registers to be shuffled, and shufSeq selects the sequence of XORs and swaps used to shuffle them.

The second instruction, ModMul factor1, factor2, product, performs a modular multiplication of registers factor1 and factor2, with the product stored in the product register. The modular multiplication is carried out by the function BenalohModMul, whose implementation can be found in a file called rsa32.lib in the Windows XP source code.

Aside from these instructions, SpModExpPrv will perform a register shuffling similar to MMCopy between calls to __Execute. It also intermittently uses another modular multiplication routine between __Execute calls, known as mpModMultiply, to prevent the whitebox from being cracked solely by hooking BenalohModMul.

Implementation Rationale

To understand how SpModExpPrv can be attacked, we will first consider how it uses modular multiplications to implement the RSA cipher.

Recall that plain RSA decryption is done by raising the ciphertext $c$ to the power of the private key $k$, modulo the key modulus $n$, to obtain the plaintext $m$. This can be written as $m = c^k \pmod {n}$. A modular exponentiation is primarily computed using a sequence of several modular multiplications, so theoretically, observing this sequence of multiplications could expose the private key.

For example, let's consider a naive implementation of modular exponentiation. To do this, we recall that $m = c^k \pmod {n}$ can be written as

$$ m = \overbrace{c \cdot c \cdot \ldots \cdot c}^{k \text{ times}} \pmod {n}$$

Writing this as code gives:

# Computes m = c^k (mod n) naively
def modexp_naive(c, k, n):
    m = 1
    for i in range(k):
        m = (m * c) % n
    
    return m

While this algorithm is the easiest to implement, it is also the slowest method, since the number of multiplications is equal to the private key. For the very large private keys used in real-world applications of RSA, the number of multiplications used makes this algorithm unusable. Additionally, an attacker can easily recover the private key from this algorithm by counting the number of modular multiplications. Luckily, with a technique known as addition-chain exponentiation both of these issues can be addressed.

To see how this works, we will consider a small example with $k = 31$ and arbitrary $c$ and $n$. Along with these values, we will use the intermediate variables $r_0$ through $r_7$.

$$ r_0 = c \bmod n = c^1 \bmod n$$

$$ r_1 = \left(r_0 \cdot r_0 \right) \bmod n = \left(c^1 \cdot c^1 \right) \bmod n = c^2 \bmod n$$

$$ r_2 = \left(r_1 \cdot r_0 \right) \bmod n = \left(c^2 \cdot c^1 \right) \bmod n = c^3 \bmod n$$

$$ r_3 = \left(r_2 \cdot r_2 \right) \bmod n = \left(c^3 \cdot c^3 \right) \bmod n = c^6 \bmod n$$

$$ r_4 = \left(r_3 \cdot r_3 \right) \bmod n = \left(c^6 \cdot c^6 \right) \bmod n = c^{12} \bmod n$$

$$ r_5 = \left(r_4 \cdot r_4 \right) \bmod n = \left(c^{12} \cdot c^{12} \right) \bmod n = c^{24} \bmod n$$

$$ r_6 = \left(r_5 \cdot r_3 \right) \bmod n = \left(c^{24} \cdot c^6 \right) \bmod n = c^{30} \bmod n$$

$$ r_7 = \left(r_6 \cdot r_0 \right) \bmod n = \left(c^{30} \cdot c^1 \right) \bmod n = c^{31} \bmod n$$

$$ m = r_7 $$

As shown, this computation method only uses 7 modular multiplications, which is much faster than the 31 multiplications used by the naive method. Additionally, this method uses several instances of modular squaring, which can be more efficiently computed than general modular multiplication.

SpModExpPrv implements this exponentiation algorithm, using its registers to store the intermediate values:

# Computes m = c^k (mod n) with SpModExpPrv's method
def modexp_spmodexpprv(c, n):
    registers[0] = c
    registers[1] = (registers[0] * registers[0]) % n
    registers[2] = (registers[1] * registers[0]) % n
    registers[3] = (registers[1] * registers[2]) % n
    # Skipping several more multiplications
    registers[123123...654] = (registers[321232...987] * registers[654567...111]) % n
    m = registers[123123...654]
    return m

Aside from being a faster exponentiation method, this algorithm also affords similar security benefits to the Montgomery ladder algorithm. More crucially, this algorithm encodes the value of the private key $k$ within the sequence of multiplications, preventing simple extraction of this value via code inspection.

Whitebox Attack

With the structure of SpModExpPrv understood, we can develop a very simple attack against this whitebox, using a debugger to inspect the factors and products of each modular multiplication.

To do this, we note that all of the intermediate values must be powers of the ciphertext $c$. Therefore, an attacker can create a table matching each intermediate value to its exponent. With each multiplication, the attacker can add the exponents of the factors to get the exponent of the product, then store the product and its exponent in the table. The final intermediate value, which holds the value of $m$, can then be looked up in this table to retrieve its exponent, which is the private key $k$.

To see how this works, we will use the prior example of addition-chain exponentiation, with $c = 234$ and $n = 97$:

Intermediate Value	Exponent
234	1

We observe the computation $(234 \cdot 234) \bmod 97 = 48$, so we store $48$ in the table with an exponent of $1+1=2$.

Intermediate Value	Exponent
234	1
48	2

We observe the computation $(48 \cdot 234) \bmod 97 = 77$, so we store $77$ in the table with an exponent of $2+1=3$.

Intermediate Value	Exponent
234	1
48	2
77	3

We observe the computation $(77 \cdot 77) \bmod 97 = 12$, so we store $12$ in the table with an exponent of $3+3=6$.

Intermediate Value	Exponent
234	1
48	2
77	3
12	6

Repeating this process several times, the result is this table:

Intermediate Value	Exponent
234	1
48	2
77	3
12	6
47	12
75	24
27	30
13	31

Upon observing the value $13$ being copied as the output of the exponentiation, the attacker can look up $13$ in this table to obtain the exponent $31$, which is the value of the private key $k$ given earlier.

This attack renders the shuffling done by the MMCopy instruction irrelevant, as the values of the factors and product in each multiplication can be directly obtained by debugging BenalohModMul and mpModMultiply.