About a week ago, there has been a little addition to the 3dbrew wiki page about 3DS cartridges (carts) that outlines the technical details of how the 3DS cartridge controller and a 3DS cartridge talk to each other. I would like to take this opportunity to also include the 3DS itself in the conversation to illuminate which part of which device performs which step. I will then proceed to outline where I think the corresponding design decisions originate. Finally, I will conclude with some concrete ideas for improvement.

But first, we need to talk about parallel universes

This protocol makes no sense unless you have a basic overview of the 3DS AES engine.

The 3DS AES engine can load 128-bit AES keys in two ways:

1. Using key-derivation from a keyX and keyY (officially called KeyId and KeySeed, respectively).
2. Directly specifying a full AES key.

The key derivation from a keyX and keyY works as follows:

AES key = (((keyX ROL 2) XOR keyY) + C1) ROR 41, where ROL is left rotation on a 128-bit word and ROR is right rotation on a 128-bit word. The constant C1 is stored in the AES hardware but black-box analysis of the key derivation function with a pair of known keyX and keyY led to the discovery of the constant (0x1ff9…). This also implies keyX and keyY are always 128-bit values.

The idea is that any software never directly stores a critical key but rather that the keys are derived on the fly by the hardware with the non-obfuscated key only being known to Nintendo.

The protocol

At the factory, three pieces of information are generated:

1. The ID1. The cartridge ID1 contains a bit whether this is a 3DS cartridge, the specific 3DS cart type (security type 1 or 2 and EEPROM present or not), the size of the cartridge itself and the maker code (who manufactured this cartridge).
2. The ID2. The cartridge ID2 determines the key used later in the protocol.
3. The unique ID. This is 16 bytes, which supposedly can get verified in some manner later, plus 48 bytes of padding.
4. The title key. This is static for all instances of a cartridge.

The unique ID is interesting in that apparently it can be verified by Nintendo online services. Knowing Nintendo, they generally shy away from using homebrewed cryptographic algorithms. No asymmetric signature is 16 bytes in length. This suggests some kind of symmetric-key construction (HMAC? They also use CMAC elsewhere to “brand” system files with a console-unique key) though it remains unclear what specifically would be the input to this since only the unique ID is unique to each cartridge.

Who	Step	Details
Console	Boot-up	Set the keyX.
Console	Initialization	Causes the cart to initialize itself in DS(i) cart mode
Cart	Initialization	Sends 0x2000 bytes of dummy data
Console	Signal 3DS mode	Causes the cart to be ready to change to 3DS mode
Console	ID1	Causes the cart to send the ID1
Cart	ID1	Sends the ID1
Console	ID2	Causes the cart to send the ID2
Cart	ID2	Sends the ID2
Console	Upgrade	Signal switch to 3DS mode
Console	Initial data	Requests the initial data
Cart	Initial data	Sends the initial data, which contains: (1) keyY, (2) encrypted title key, (3) MAC, (4) nonce
Console	Initial data	Load the keyY into the AES engine, causing it to derive the key
Cart	Key generation	Perform the same steps as the console and cart controller below until the end of the key generation step
Console	Key generation	Decrypt the title key using AES-CCM
Console	Key generation	Send the decrypted title key to the cart controller
Cart controller	Key generation	Split the title key into two halves: left and right
Cart controller	Key generation	Initialize a context for the SNOW 2.0 stream cipher. The 128-bit title key. The 128-bit IV is a 128-bit static value depending on the gamecard ID2
Cart controller	Key generation	Call the SNOW 2.0 stream cipher 32 times to obtain and discard 1024 bits (32 words) of output
Cart controller	Key generation	Initialize a context for the RC4 stream cipher. The 256-bit key consists of a 128-bit static value depending on the gamecard ID2 followed by four outputs of the SNOW 2.0 stream
Cart controller	Key generation	Call the RC4 stream cipher 256 times to obtain and discard 2048 bits (256 bytes) of output
Console	Rekey	Pull 8 bytes of random data from the cryptographically secure random number generator
Console	Rekey	Send the 8 bytes to the cart and controller
Cart	Rekey	Perform the same steps as the console and cart controller below until the end of the rekey step
Cart controller	Rekey	Initialize a new context for the SNOW 2.0 stream cipher. The 128-bit key consists of the left half of the title key followed by the 8 random bytes. The 128-bit IV is the same 128-bit static value depending on the gamecard ID2 as before
Cart controller	Rekey	Call the SNOW 2.0 stream cipher 32 times to obtain and discard 1024 bits (32 words) of output
Cart controller	Rekey	Initialize a context for the RC4 stream cipher. The 256-bit key consists of a 128-bit static value depending on the gamecard ID2 followed by four outputs of the SNOW 2.0 stream
Cart controller	Rekey	Call the RC4 stream cipher 256 times to obtain and discard 2048 bits (256 bytes) of output

At this point, both sides have arrived at the same key and will talk over one shared RC4 state to each other. The 3DS console itself cannot obtain these keys because only the cart and cart controller have the keys that are chosen according to the ID2. Responses include a CRC-32, which is also encrypted.

In summary:

1. At the 3DS factory,
   1. the keyX is written into the boot ROM,
   2. the AES key derivation constant is made part of the AES hardware,
   3. the SNOW 2.0 and RC4 key constants are made part of the cartridge controller hardware.
2. At the cart factory, the keyY, (encrypted) title key, ID1, ID2 and unique ID are written to the cart.
3. When the cartridge is inserted, the 3DS decrypts the title key using the keyX (boot ROM), keyY (cart) via the AES hardware (hardware key derivation constant).
4. The cart controller uses a SNOW 2.0 stream cipher, whose only purpose is to act as a key derivation function for RC4, to generate an RC4 key. Both keys involve constants stored in the cartridge controller hardware.
5. The cart controller uses RC4 for encryption.
6. The cart does the same.

Assumed motivations

The motivation for encryption in the first place is obvious: Nintendo does not want their assets and code to be obtained.

Ciphers. The encryption uses SNOW 2.0 and RC4. SNOW 2.0 is an uncommon cipher, only notable for being standardized by ISO. It claims to be software-oriented but is implemented strictly in hardware on the 3DS. Similarly, RC4 is software-oriented. This suggests that this protocol may initially have been meant to be implemented in software. It was considered weak even at the time the 3DS was designed around 2009/2010. This is the reason why some outputs are discarded from both the stream ciphers: Avoiding weak initial streams. Furthermore, Nintendo is notoriously afraid of leaving classic, NIST-approved cryptography. This strongly suggests that this protocol was not designed in-house. The use of a stream cipher per se seems a natural choice for a protocol in which both sides share a state, messages are of variable length and no authentication of the message is needed (or is implied by the correct encryption of a CRC value). AES-CCM is also a fairly unusual choice but avoids the need for GHASH/POLYVAL in hardware compared to AES-GCM, which would have been the primary alternative at the time.

Secrets. The scheme excels at splitting secrets across multiple components such that breaking one does not break the others. This part is illustrative of a good mesh design and laudable in its execution. The cartridge must either have a full copy of the AES hardware and the keyX/keyY key derivation algorithm to use the initial data to decrypt the title key or an unencrypted copy of the title key. It would be fairly unnatural to have a full implementation of AES and then two separate ciphers, which suggests that there is an unencrypted copy of the title key on the cart that the cart hardware can use for the SNOW 2.0 and RC4 key derivation. This is corroborated by the observation that a corresponding region is not readable on retail cartridges.

Concrete improvements

There are four issues that stand out: the prelude, cipher choice, message authentication and rekeying.

Prelude. The prelude (initial key negotiation and ID1/ID2) are in plaintext and unauthenticated. It would be beneficial if the cart and cart controller had a pre-shared key as a first line of defense.

Message authentication. While there is an encrypted CRC-32, it will likely not provide meaningful resistance against modifications to the stream. This is likely a holdover from thinking about hardware (bit flips) instead of thinking about cryptography (authentication).

Cipher choice. Both SNOW 2.0 and RC4 are software-oriented. An ideal implementation would prefer hardware-oriented ciphers for this. Interest in stream ciphers has been waning and the eSTREAM winners for the hardware profile make use of only 80-bit keys. This is considered strong enough, but Nintendo exhibits a strong preference towards 128-bit keys.

Rekeying. The 3DS console alone dictates the randomness used for rekeying. Assume an attacker realizes that a stream cipher is used. Assume further the attacker compromises the 3DS firmware to the point that they can force the 3DS to send the same rekey value. The attacker can then save the transcript of a communication, force the 3DS to send the same rekey value and request different pages: An attacker observes (convo1 = plain1 XOR keystream). They reset the conversation, forces the same rekey value and observe (convo2 = plain2 XOR keystream). Because XOR is commutative, this lets them observe the XOR of plain1 and plain2. Since they can control the pages used, if at least one of the pages returned is all-zero decrypted (which they can observe on the 3DS firmware), they obtain the raw keystream and can decrypt the whole cart by repeatedly resetting and doing page-wise requests.

The protocol-level issues of the prelude and rekeying can be solved by instantiating a Noise protocol framework pattern; finding an appropriate pattern is straightforward thanks to tools like the Noise Explorer. The downside is that these protocols assume the wide availability of elliptic curve Diffie–Hellman primitives. In a pure hardware implementation, elliptic curves may well be even more of a nightmare than in software. It may be necessary to substitute custom key derivation, albeit this is not recommended.

The message authentication can be solved using authentication tags instead of a CRC. Assuming a performant, hardware-oriented implementation of AES, AES-OCB could be used as the primary method of communication with one authentication tag per packet.

Finally, the AES key derivation function is just plain bad. It was possible to determine the constant just given a pair of keyX/keyY and the resulting key. NIST peddles a solution to this, NIST SP 800-56C, involving AES-CMAC. NIST SP 800-56C which was not yet released at the time the 3DS was designed and released. The AES key derivation function is particularly baffling because it should be an obvious idea to involve AES engine in the key derivation.

Edit:
A demo of this is now available at: https://git.winter-software.com/forbiddentempura/cartcrypto
- Mia