Savegames

Revision as of 17:19, 3 January 2018 by Wwylele (talk | contribs) (Nuke outdated content and upload new one. Sorry for removing another nice but outdated image)

This page describes the format and encryption of savegames contained in gamecards, SD and NAND. You can find savegames from various 3DS games on the Games page.

Overview

Savegames are stored in DISA container format (follow this link for the container format description). It forms a file system inside the inner content of the container. In this page only the inner file system format of the content is described.

Unlike SD and NAND savegames, gamecard savegames has additional encryption + wear leveling layer. They are described in the following sections.

Gamecard savegame Encryption

Repeating CTR Fail

On the 3DS savegames are stored much like on the DS, that is on a FLASH chip in the gamecart. On the DS these savegames were stored in plain-text but on the 3DS a layer of encryption was added. This is AES-CTR, as the contents of several savegames exhibit the odd behavior that xor-ing certain parts of the savegame together will result in the plain-text appearing.

The reason this works is because the stream cipher used has a period of 512 bytes. That is to say, it will repeat the same keystream after 512 bytes. The way you encrypt with a stream cipher is you XOR your data with the keystream as it is produced. Unfortunately, if your streamcipher repeats and you are encrypting a known plain-text (in our case, zeros) you are basically giving away your valuable keystream.

So how do you use this to decrypt a savegame on a 3DS? First off, you chunk up the savegame into 512 byte chunks. Then, you bin these chunks by their contents, discarding any that contain only FF. Now look for the most common chunk. This is your keystream. Now XOR the keystream with your original savegame and you should have a fully decrypted savegame. XOR with the keystream again to produce an encrypted savegame.

Savegame keyY

All gamecard and SD savegames are encrypted with AES-CTR. The base CTR for gamecard savegames is all-zero. The gamecard savegame keyslots' keyY(these savegame keyslots use the hardware key-generator) is unique for each region and for each game. The NCSD partition flags determine the method used to generate this keyY. When the save NCSD flags checked by the running NATIVE_FIRM are all-zero, the system will use the repeating CTR, otherwise a proper CTR which never repeats within the image is used.

The AES-CMAC (which uses a hardware key-generator keyslot, as mentioned above) at the the beginning of the savegame must match the calculated CMAC using the DISA/DIFF data, otherwise the savegame is considered corrupted(see below).

When all of the flags checked by the running NATIVE_FIRM are clear, the keyY(original keyY method used with saves where the CTR repeats within the image) is the following:

Offset Size Description
0x0 0x8 First 8-bytes from the plaintext CXI accessdesc signature.
0x8 0x4 u32 CardID0 from gamecard plaintext-mode command 0x90, Process9 reads this with the NTRCARD hw. The actual cmdID used by Process9 is different since Process9 reads it with the gamecard in encrypted-mode.
0xC 0x4 u32 CardID1 from gamecard plaintext-mode command 0xA0, Process9 reads this with the NTRCARD hw. The actual cmdID used by Process9 is different since Process9 reads it with the gamecard in encrypted-mode.

2.0.0-2 Hashed keyY and 2.2.0-4 Savegame Encryption

When certain NCSD partition flags are set, a SHA-256 hash is calculated over the data from the CXI(same data used with the original plain keyY), and the 0x40-bytes read from a gamecard command(this 0x40-byte data is also read by GetRomId, which is the gamecard-uniqueID). The first 0x10-bytes from this hash is used for the keyY. When flag[7] is set, the CTR will never repeat within the save image, unlike the original CTR-method. All games which had the retail NCSD image finalized after the 2.2.0-4 update(and contain 2.2.0-4+ in the System update partition), use this encryption method.

This keyY generation method was implemented with 2.0.0-2 via NCSD partition flag[3], however the proper CTR wasn't implemented for flag[7] until 2.2.0-4. The hashed keyY flag[3] implemented with 2.0.0-2 was likely never used with retail gamecards.

6.0.0-11 Savegame keyY

6.0.0-11 implemented support for generating the savegame keyY with a new method, this method is much more complex than previous keyY methods. This is enabled via new NCSD partition flags, all retail games which have the NCSD image finalized after the 6.0.0-11 release(and 6.0.0-11+ in the system update partition) will have these flags set for using this new method.

A SHA-256 hash is calculated over the same data used with the above hashed keyY method, after hashing the above data the following data is hashed: the CXI programID, and the ExeFS:/.code hash from the decrypted ExeFS header. An AES-CMAC (the keyslot used for this uses the hardware key-scrambler) is then calculated over this hash, the output CMAC is used for the savegame keyY.

The keyY used for calculating this AES-CMAC is initialized while NATIVE_FIRM is loading, this keyY is generated via the RSA engine. The RSA slot used here is slot0(key-data for slot0 is initialized by bootrom), this RSA slot0 key-data is overwritten during system boot. This RSA slot0 key-data gets overwritten with the RSA key-data used for verifying RSA signatures, every time Process9 verifies any RSA signatures except for NCCH accessdesc signatures. Starting with 7.0.0-13 this key-init function used at boot is also used to initialize a separate keyslot used for the new NCCH encryption method.

This Process9 key-init function first checks if a certain 0x10-byte block in the 0x01FF8000 region is all-zero. When all-zero it immediately returns, otherwise it clears that block then continues to do the key generation. This is likely for supporting launching a v6.0+ NATIVE_FIRM under this FIRM.

Gamecard wear leveling

The 3DS employs a wear leveling scheme on the savegame FLASH chips(only used for CARD1 gamecards). This is done through the usage of blockmaps and a journal. The blockmap is located at offset 0 of the flash chip, and is immediately followed by the journal. The initial state is dictated by the blockmap, and the journal is then applied to that.

First, there are 8 bytes whose purposes are currently unknown. Then comes the actual blockmap. The blockmap structure is simple:

struct header_entry {
        uint8_t phys_sec; // when bit7 is set, block has checksums, otherwise checksums are all zero
        uint8_t alloc_cnt;
        uint8_t chksums[8];
} __attribute__((__packed__));

There's one entry per sector, counting from physical sector 1 (sector 0 contains the blockmap/journal).

The 2 bytes that follow the blockmap are the CRC16 (with starting value 0xFFFF (like modbus)) of the first 8 bytes and the blockmap.

Then comes the journal. The journal structure is as follows:

struct sector_entry {
        uint8_t virt_sec;       // Mapped to sector
        uint8_t prev_virt_sec;  // Physical sector previously mapped to
        uint8_t phys_sec;       // Mapped from sector
        uint8_t prev_phys_sec;  // Virtual sector previously mapped to
        uint8_t phys_realloc_cnt;       // Amount of times physical sector has been remapped
        uint8_t virt_realloc_cnt;       // Amount of times virtual sector has been remapped
        uint8_t chksums[8];
} __attribute__((__packed__));

struct long_sector_entry{
        struct sector_entry sector;
        struct sector_entry dupe;
        uint32_t magic;
}__attribute__((__packed__));

With magic being a constant 0x080d6ce0.

The checksums in the blockmap/journal entries work as follows:

  • each byte is the checksum of an encrypted 0x200 bytes large block
  • to calculate the checksum, a CRC16 of the block (with starting value 0xFFFF) is calculated, and the two bytes of the CRC16 are XORed together to produce the 8bit checksum

Components and partitions

A savegame, after unwrapping the DISA container, consists of the following components:

  • SAVE header
  • directory hash table
  • file hash table
  • file allocation table
  • directory entry table
  • file entry table
  • data region

A DISA container can have one or two partitions, and correspondingly a savegame has two possible layouts. The layout is determined by the parameter duplicate data passed in FS:FormatSaveData or FS:CreateSystemSaveData.

Layout for duplicate data = true

The DISA container only has one partition which is always configured as external IVFC level 4 disabled (see DISA format for details). All components are stored in this partition as

  • SAVE header at the beginning
  • directory hash table
  • file hash table
  • file allocation table
  • data region
    • directory entry table is allocated inside data region
    • file entry table as well
    • all file data is also allocated here

In this layout, all data is duplicated by DISA's DPFS tree, which is what the parameter duplicate data implies.

Layout for duplicate data = false

The DISA container has two partitions. Partition A is always configured as external IVFC level 4 disabled, and partition B is configured as it enabled. Components are stored among the two partitions as

  • Partition A
    • SAVE header at the beginning.
    • directory hash table
    • file hash table
    • file allocation table
    • directory entry table
    • file entry table
  • Partition B
    • used as data region entirely, and only has file data allocated.

In this layout, all file system metadata is duplicated by partition A DPFS tree, but file data is not as partition B has external IVFC level 4.

SAVE Header

The SAVE header defines the rest components of the savegame. All "offsets" in the table are relative to the beginning of SAVE image, while all "starting block index" are relative to the beginning of data region.

Offset Length Description
0x00 4 Magic "SAVE"
0x04 4 Magic 0x40000
0x08 8 File system Information offset (0x20)
0x10 8 Image size in blocks
0x18 4 Image block size
0x1C 4 Padding
Below is File system Information
0x20 4 Unknown:thinking:
0x24 4 Data region block size
0x28 8 Directory hash table offset
0x30 4 Directory hash table bucket count
0x34 4 Padding
0x38 8 File hash table offset
0x40 4 File hash table bucket count
0x44 4 Padding
0x48 8 File allocation table offset
0x50 4 File allocation table entry count
0x54 4 Padding
0x58 8 Data region offset (if no partition B)
0x60 4 Data region block count (= File allocation table entry count)
0x64 4 Padding
0x68 8 If partition B exists: directory entry table offset;
otherwise: u32 directory entry table starting block index + u32 directory entry table block count
0x70 4 Maximum directory count
0x74 4 Padding
0x78 8 If partition B exists: file entry table offset;
otherwise: u32 file entry table starting block index + u32 file entry table block count
0x80 4 Maximum file count
0x84 4 Padding
  • The file/directory bucket count & maximum count are specified by the parameters of FS:FormatSaveData or FS:CreateSystemSaveData.
  • When partition B doesn't exist, directory & file entry tables are allocated in the data region, and while be marked allocated in file allocation table as if they are two normal files. However, only continuous allocation has been observed, so directly reading block_count * block_size bytes from data_region + starting_block_index * block_size should be safe. See the section #File Allocation Table below for more information.

Directory Entry Table

The directory entry table is an array of the entry type shown below. It describes the directory hierarchy of the file system.

Offset Length Description
0x00 4 Parent directory index. 0 for root
0x04 16 ASCII directory name in. All zero for root
0x14 4 Next sibling directory index. 0 if this is the last one
0x18 4 First subdirectory index. 0 if not exists
0x1C 4 First file index in file entry table. 0 for empty directory
0x20 4 Padding / zero?
0x24 4 Index of the next directory in the same hash table bucket. 0 if this is the last one

There are also some dummy entries in the array:

Offset Length Description
0x00 4 Current Total entry count
0x04 4 Maximum entry count = maximum directory count + 2
0x08 28 Padding / All zero
0x24 4 Index of the next dummy entry. 0 if this is the last one

The 0-th entry of the array is always a dummy entry, which functions as the head of the dummy entry linked list. The 1-st entry of the array is always the root. Therefore maximum entry count is two more than maximum directory count. Dummy entries are left there when deleting directories, and reserved for future use.

File Entry Table

The file entry table is an array of the entry type shown below. It contains information for each file.

Offset Length Description
0x00 4 Parent directory index in directory entry table
0x04 16 ASCII file name
0x14 4 Next sibling file index. 0 if this is the last one
0x18 4 Padding
0x1C 4 First block index in data region. 0x80000000 if the file is just created and has no data.
0x20 8 File Size
0x28 4 Padding?
0x2C 4 Index of the next file in the same hash table bucket. 0 if this is the last one

Like directory entry table, file entry table also has some dummy entries:

Offset Length Description
0x00 4 Current total entry count
0x04 4 Maximum entry count = maximum file count + 1
0x08 36 Padding / All zero
0x2C 4 Index of the next dummy entry. 0 if this is the last one

The 0-th entry of the array is always a dummy entry, which functions as the head of the dummy entry linked list. Therefore maximum entry count is one more than maximum file count. Dummy entries are left there when deleting files, and reserved for future use.

Directory Hash Table & File Hash Table

This is a u32 array of size = bucket count, each of which is an index to the directory / file entry table. The directory / file name is hashed and its entry index is put to the corresponding bucket. If there is already a directory/file entry in the bucket, then it appends to the linked list formed by Index of the next directory/file in the same hash table bucket field in the directory/file entry table. i.e. this is a hash table using separate chaining with linked lists

The hash function takes the parent index and the name as key. The function is equivalent to

uint32_t GetBucket(
    char name[16], // takes all 16 bytes including trailing zeros
    uint32_t parent_dir_index,
    uint32_t bucket_count
) {
    uint32_t hash = parent_dir_index ^ 0x091A2B3C;
    for (int i = 0; i < 4; ++i) {
        hash = (hash >> 1) | (hash << 31);
        hash ^= (uint32_t)name[i * 4]
        hash ^= (uint32_t)name[i * 4 + 1] << 8
        hash ^= (uint32_t)name[i * 4 + 2] << 16
        hash ^= (uint32_t)name[i * 4 + 3] << 24
    }
    return hash % bucket_count;
}

File Allocation Table

The file allocation table is an array of a 8-byte entry shown below. The array size is actually one larger than the size recorded in the SAVE header. Each entry corresponds to a block in the data region (the block size is defined in SAVE header). However, the 0th entry corresponds to nothing, so the corresponding block index is off by one. e.g. entry 31 in this table corresponds to block 30 in the data region.

Offset Length Description
0x00 4 bit[0:30]: Index U; bit[31]: Flag U
0x04 4 bit[0:30]: Index V; bit[31]: Flag V

Entries in this table forms several chains, representing how blocks in the data region should be linked together. However, unlike normal FAT systems, which uses chains of entries, 3DS savegames use chain of nodes. Each node spans one or multiple entries.

One node spanning n entries starting from FAT[k] is in the following format:

FAT[k + 0]:
    Index_U = index of the first entry of the previous node. 0 if this is the first node.
    Index_V = index of the first entry of the next node. 0 if this is the last node.
    Flag_U set if this is the first node.
    Flag_V set if this node has multiple entries.

FAT[k + 1]:
    Index_U = k (the first entry index of this node)
    Index_V = k + n - 1 (the last entry index of this node)
    Flag_U always set
    Flag_V always clear

FAT[k + 2] ~ FAT[k + n - 2]:
    All these entries are uninitialized

FAT[k + n - 1]:
    Index_U = k
    Index_V = k + n - 1
    Flag_U always set
    Flag_V always clear
    (Same values as FAT[k + 1])
  • Note: all indices above are entry indices (block index + 1)

All free blocks that are not allocated to any files also form a node chain in the allocation table. The head index of this "free chain" is recorded in FAT[0].Index_V. Other fields of FAT[0] are all zero

Initialization

When a save FLASH contains all xFFFF blocks it's assumed uninitialized by the game cartridges and it initializes default data in place, without prompting the user. The 0xFFFFFFFF blocks are uninitialized data. When creating a non-gamecard savegame and other images/files, it's initially all 0xFFFFFFFF until it's formatted where some of the blocks are overwritten with encrypted data.

I got a new game SplinterCell3D-Pal and I downloaded the save and it was 128KB of 0xFF, except the first 0x10 bytes which were the letter 'Z' (uppercase) --Elisherer 22:41, 15 October 2011 (CEST)

Fun Facts

If you have facts that you found out by looking at the binary files please share them here:

  • From one save to another the game backups the last files that were in the partition and the entire image header in "random" locations.. --Elisherer 22:41, 15 October 2011 (CEST)

Tools

  • 3dsfuse supports reading and modifying savegames. In the mounted FUSE filesystem, the /output.sav is the raw FLASH save-image. When the save was modified, a separate tool to update the CMAC must be used with /clean.sav, prior to writing output.sav to a gamecard.
  • 3DSExplorer supports reading of savegames, it doesn't support reading the new encrypted savegames and maybe in the future it will support modifying (some of the modyfing code is already implemented).
  • wwylele's 3ds-save-tool supports extracting files from savegames and extdata. It properly reconstructs data from the DPFS tree and extracts files in directories hierarchy. It also contains a newer documentation of the save format but unfinished yet.
    • I will migrate the documentation here when I get time. Anyone is also welcome to do this before I do it. --Wwylele (talk) 13:18, 18 November 2017 (CET)
  • 3dsfuse-ex similar to 3dsfuse, but supports savegame inner FS, proper DPFS handling, and automatic CMAC update. Still WIP.

Japanese