The FAT Filesystem

FAT stands for "File Allocation Table". It's one of the more simple filesystems ever, and is based on concepts closer to the simpler DEC's RT11 filesystem and CP/M rather than the more modern ideas that were used in the Berkeley Fast filesystem.

It was the first filesystem used in Microsoft's DOS operating system, and is still usable in all Windows and Linux operating systems (and indeed, tools exist in virtually every operating system to read and write to basic FAT filesystems.) Devices such as digital cameras, usb memory sticks, and even digital copiers usually use a FAT filesystem for storage.

There have been a large number of versions of the FAT filesytem. The easiest initial breakdown is to recognize the FAT12, FAT16, and FAT32 divisions. Each of these represented a step up in ability to store more data in a FAT filesystem.

Alternative data streams: FAT was never designed to handle alternative data streams, but there have been extensions made that can allow these. This is of significant forensic attention since ADS provide a simple way of obscuring data, (see WFA pp. 312-320 — note that ADSs have been used by the W2K virus and by the Mailbot.AZ rootkit.)

The three parts of the FAT filesystem

All FAT file systems have three divisions:

The "reserved area": in FAT12 and FAT16, this is generally just one sector (usually called the 'boot sector'). In FAT32, it's generally more (see next slide for an example, where the reserved area is 32 sectors, but only three or four of them are used). Typically, a backup "boot sector" and a sector called the FS INFO which caches some statistical information for the partition; there may also be a backup FS INFO sector. Each of these has a magic number of 0xAA55, just like an MBR.
The FAT area: the actual file allocation table area that gives the filesystem its name.
The Data area: as the name suggests, data reside here in "clusters." A cluster is simply a contiguous group of sectors, generally 64 sectors when you are using 512 byte sectors. (Remember, contiguous here refers not to any physical property, but instead sequential LBA numbers.)

A sample FAT 12 dump

Here's a sample dump of an (empty) FAT12 using the Sleuth Kit's fsstat program:

bash$ fsstat -f fat msdos.fat12
FILE SYSTEM INFORMATION
--------------------------------------------
File System Type: FAT12

OEM Name: mkdosfs
Volume ID: 0x3f0947d2
Volume Label (Boot Sector):            
Volume Label (Root Directory):
File System Type Label: FAT12   

Sectors before file system: 0

File System Layout (in sectors)
Total Range: 0 - 49999
* Reserved: 0 - 15
** Boot Sector: 0
* FAT 0: 16 - 31
* FAT 1: 32 - 47
* Data Area: 48 - 49999
** Root Directory: 48 - 79
** Cluster Area: 80 - 49999

METADATA INFORMATION
--------------------------------------------
Range: 2 - 799238
Root Directory: 2

CONTENT INFORMATION
--------------------------------------------
Sector Size: 512
Cluster Size: 8192
Total Cluster Range: 2 - 3121

FAT CONTENTS (in sectors)
--------------------------------------------

A sample FAT16 dump

Here's a sample dump of an (empty) FAT16 using the Sleuth Kit's fsstat program:

bash-4.1$ fsstat -f fat msdos.fat16
FILE SYSTEM INFORMATION
--------------------------------------------
File System Type: FAT16

OEM Name: mkdosfs
Volume ID: 0x4a7c749a
Volume Label (Boot Sector):            
Volume Label (Root Directory):
File System Type Label: FAT16   

Sectors before file system: 0

File System Layout (in sectors)
Total Range: 0 - 49999
* Reserved: 0 - 3
** Boot Sector: 0
* FAT 0: 4 - 55
* FAT 1: 56 - 107
* Data Area: 108 - 49999
** Root Directory: 108 - 139
** Cluster Area: 140 - 49999

METADATA INFORMATION
--------------------------------------------
Range: 2 - 798278
Root Directory: 2

CONTENT INFORMATION
--------------------------------------------
Sector Size: 512
Cluster Size: 2048
Total Cluster Range: 2 - 12466

FAT CONTENTS (in sectors)
--------------------------------------------

A sample FAT32 dump

Here's a sample dump of a (non-empty) FAT32 using the Sleuth Kit's fsstat program:

bash-4.1$ fsstat -f fat /tmp/DFC4-D25D.dat
FILE SYSTEM INFORMATION
--------------------------------------------
File System Type: FAT32

OEM Name: SYSLINUX
Volume ID: 0xdfc4d25d
Volume Label (Boot Sector):            
Volume Label (Root Directory):
File System Type Label: FAT32   
Next Free Sector (FS Info): 4128
Free Sector Count (FS Info): 637528

Sectors before file system: 0

File System Layout (in sectors)
Total Range: 0 - 2097151
Total Range in Image: 0 - 488535
* Reserved: 0 - 31
** Boot Sector: 0
** FS Info Sector: 1
** Backup Boot Sector: 6
* FAT 0: 32 - 2079
* FAT 1: 2080 - 4127
* Data Area: 4128 - 2097151
** Cluster Area: 4128 - 2097151
*** Root Directory: 4128 - 4135

METADATA INFORMATION
--------------------------------------------
Range: 2 - 7750534
Root Directory: 2

CONTENT INFORMATION
--------------------------------------------
Sector Size: 512
Cluster Size: 4096
Total Cluster Range: 2 - 261629

FAT CONTENTS (in sectors)
--------------------------------------------
4128-4135 (8) -> EOF
4136-11527 (7392) -> EOF
11528-27823 (16296) -> EOF
27824-27831 (8) -> EOF
27832-27839 (8) -> EOF
27840-27847 (8) -> EOF
27848-27855 (8) -> EOF
27856-27863 (8) -> EOF
27864-27871 (8) -> EOF
27872-28351 (480) -> EOF
28352-28359 (8) -> EOF
28360-44655 (16296) -> EOF
44656-44703 (48) -> EOF
44704-44711 (8) -> EOF
44712-45039 (328) -> EOF
45040-45943 (904) -> EOF
45944-46079 (136) -> EOF
46080-46399 (320) -> EOF
46400-53791 (7392) -> EOF
53792-53831 (40) -> EOF
53832-53887 (56) -> EOF
53888-53903 (16) -> EOF
53904-1432815 (1378912) -> EOF
1432816-1432823 (8) -> EOF
1432824-1449119 (16296) -> EOF
1449120-1449167 (48) -> EOF
1449168-1449175 (8) -> EOF
1449176-1449503 (328) -> EOF
1449504-1450407 (904) -> EOF
1450408-1450727 (320) -> EOF
1450728-1458119 (7392) -> EOF
1458120-1458127 (8) -> EOF
1458128-1458191 (64) -> EOF
1458200-1458319 (120) -> EOF
1458328-1458335 (8) -> EOF
1458336-1458343 (8) -> EOF
1458344-1458351 (8) -> EOF
1458352-1458775 (424) -> EOF
1458776-1458815 (40) -> EOF
1458840-1458863 (24) -> EOF
1458864-1459455 (592) -> EOF
1459456-1459471 (16) -> EOF
1459472-1459607 (136) -> EOF
1459608-1459631 (24) -> EOF
1459632-1459639 (8) -> EOF
1459640-1459663 (24) -> EOF

The "Boot Sector"

Each FAT filesystem can contain boot code; if it does, the first three bytes will contain an actual JMP instruction to the boot code.

Here's a detailed breakdown for a filesystem found on a typical FLASH drive: here

From the Wikipedia (here), the layout of the first 36 bytes of the boot sector for all versions of FAT:

Byte Offset Length (bytes) Description

0x00 3 Jump instruction. This instruction will be executed and will skip past the rest of the (non-executable) header if the partition is booted from. See Volume Boot Record. If the jump is two-byte near jmp it is followed by a NOP instruction.

0x03 8 OEM Name (padded with spaces 0x20). This value determines in which system disk was formatted. MS-DOS checks this field to determine which other parts of the boot record can be relied on.^[28]^[29] Common values are IBM 3.3 (with two spaces between the "IBM" and the "3.3"), MSDOS5.0, MSWIN4.1 and mkdosfs.

0x0b 2 Bytes per sector. A common value is 512, especially for file systems on IDE (or compatible) disks. The BIOS Parameter Block starts here.

0x0d 1 Sectors per cluster. Allowed values are powers of two from 1 to 128. However, the value must not be such that the number of bytes per cluster becomes greater than 32 KB.

0x0e 2 Reserved sector count. The number of sectors before the first FAT in the file system image. Should be 1 for FAT12/FAT16. Usually 32 for FAT32.

0x10 1 Number of file allocation tables. Almost always 2.

0x11 2 Maximum number of root directory entries. Only used on FAT12 and FAT16, where the root directory is handled specially. Should be 0 for FAT32. This value should always be such that the root directory ends on a sector boundary (i.e. such that its size becomes a multiple of the sector size). 224 is typical for floppy disks.

0x13 2 Total sectors (if zero, use 4 byte value at offset 0x20)

0x15 1 Media descriptor^[30]

0xF0 3.5" Double Sided, 80 tracks per side, 18 or 36 sectors per track (1.44MB or 2.88MB). 5.25" Double Sided, 80 tracks per side, 15 sectors per track (1.2MB). Used also for other media types.

0xF8 Fixed disk (i.e. Hard disk).^[31]

0xF9 3.5" Double sided, 80 tracks per side, 9 sectors per track (720K). 5.25" Double sided, 80 tracks per side, 15 sectors per track (1.2MB)

0xFA 5.25" Single sided, 80 tracks per side, 8 sectors per track (320K)

0xFB 3.5" Double sided, 80 tracks per side, 8 sectors per track (640K)

0xFC 5.25" Single sided, 40 tracks per side, 9 sectors per track (180K)

0xFD 5.25" Double sided, 40 tracks per side, 9 sectors per track (360K). Also used for 8".

0xFE 5.25" Single sided, 40 tracks per side, 8 sectors per track (160K). Also used for 8".

0xFF 5.25" Double sided, 40 tracks per side, 8 sectors per track (320K)

Same value of media descriptor should be repeated as first byte of each copy of FAT. Certain operating systems (MSX-DOS version 1.0) ignore boot sector parameters altogether and use media descriptor value from the first byte of FAT to determine file system parameters.

0x16 2 Sectors per File Allocation Table for FAT12/FAT16

0x18 2 Sectors per track (Only useful on disks with geometry. [1])

0x1a 2 Number of heads (Only useful on disks with geometry. [2])

0x1c 4 Count of hidden sectors preceding the partition that contains this FAT volume. This field should always be zero on media that are not partitioned.

0x20 4 Total sectors (if greater than 65535; otherwise, see offset 0x13)

Slack

Since FAT filesystems are replete with areas of unused data, the term "slack" (or "slack space") has been used as a general reference word for them.

Sources of slack space:

Volume slack — it's entirely possible that a FAT filesystem does not even go to the end of the partition. The space from the end of the filesystem to the end of the partition is called "volume slack."
Data area slack — even in the data area, it is possible that the clusters do not actually go to the end of the data area.
File slack — a file uses entire clusters even if it doesn't fill that space, so there could easily be leftover space in both the last used block in the cluster and, of course, all of the unused blocks in the cluster. This space has come to be called "file slack".

FAT

The heart of the FAT filesystem is the eponymous FAT (file allocation table.) There are usually two copies of the FAT, located together right after the reserved area.

The FAT consists of consecutive entries, each entry referencing a single cluster. (See next slide.) (Yes, the mapping from FAT entries to clusters is bijective, or one-to-one and onto.) The size of entry is indicated by the FAT type: FAT12 has 12 bit entries; FAT16 has 16 bit entries; and FAT32 has 32 bit entries.

If the value of the entry is zero, then the corresponding cluster is not allocated to a file. The marking for damaged clusters is 0xff7 for FAT12, 0xfff7 for FAT16, and 0x0ffffff7 for FAT32. This is very relevant for forensics since it is ordinary practice for commercial tools to actually mark clusters as damaged and still use that space, and malware can do the same.

The other two legitimate values for a FAT entry are (1) the next cluster in a file or (2) an EOF marker, meaning that this the last cluster associated with a file.

The allocation policy governs how you identify and use free space; for WIN98 and XP, it is a simple "first available".

Clusters and data

As remarked above, a given cluster is simply a continguous group of blocks.

Each cluster has a number associated with it; the first cluster is 2 (there is no 0 or 1 cluster.) Clusters are are in sequential order on a partition:

Cluster 2

Cluster 4

Cluster 5

Cluster 6

Cluster 7

...

In FAT12 and FAT16, the data area begins with a "root directory". The first cluster is right after this root directory area.

In FAT32, the first cluster is at the beginning of the data area.

As described above, the FAT entries describe how a file maps to the actual clusters used to store the file.

Directories

A directory in a FAT filesystem is a special type of file, and if it requires more than one cluster, the FAT entries for the directory use the same cluster-chaining that ordinary files use.

The most important attribute of directories are of course the actual entries.

Each ordinary directory entry is 32 bytes in size. It contains the file name, attributes, size, starting cluster, and dates and times associated with the file.

The first two entries in a non-root directory are fixed at "." and "..".

If the filename begins with the character "0xe5", then the entry has been deallocated. Most programs that "delete" files actually simply change the first character of the filename to 0xe5, and thus recovery of such "deleted" files is often (but not always!) simple.

In addition to ordinary entries, there is also a special type of file entry called the "long file name" entry.

Structure of a basic directory entry

	0 --> first character of file in ASCII; if this is 0x0 or 0xe5, then it is
              not allocated
        1-10 --> more characters of filename in ASCII
        11 --> file attributes
                  0x01 --> read only
                  0x02 --> hidden
                  0x04 --> system file
                  0x08 --> volume label
                  0x0f --> long file name (note this is an OR of above!)
                  0x10 --> directory
                  0x20 --> archive
                  0x40 --> reserved
                  0x80 --> reserved
          12 --> reserved
          13 --> created time (tenths of second)
          14-15 --> create time (hours, minutes, seconds)
          16-17 --> create day
          18-19 --> accessed day
          20-21 --> high 2 bytes of first cluster address
          22-23 --> written time (hours, minutes, seconds)
          24-25 --> written day
          26-27 --> low 2 bytes of first cluster address
          28-31 --> size of file (0 for directories)

Structure of a long filename (LFN) entry

The LFNs occur in reverse order; thus the first entry will have the last characters of a filename. They come before the basic directory entry that they reference. Unused character space are indicated by 0xff, and if there is room, the LFN should be null terminated.

        0 --> Sequence number (starts with 1 for the first LFN entry for a given file); this
              is ORed with 0x40
        1-10 --> Filename characters 1-5 (either UTF-16 (2000/XP/Vista/Windows7) or older OSes use the
                 largely identical UCS-2 standard), thus two bytes per character (well, except when it might be four,
                 but those are reserved for dead languages)
        11 --> attributes, must be equal to 0x0f
        12 --> reserved
        13 --> checksum (computed from short filename, must be same for each LFN entry for the shortname)
        14-25 --> filename characters 6-11 in UTF-16/UCS-2
        26-27 --> reserved
        28-31 --> two more filename characters in UTF-16/UCS-2