Analyzing The FAT Table For Digital Evidence

A partition is divided into equally sized clusters — small, contiguous blocks of storage. The actual cluster size depends on the FAT variant and the size of the partition, but it usually falls somewhere between 2 KB and 32 KB. A file can span one or many clusters depending on its size, and the FAT file system represents each file as a chain of clusters linked together (forming a singly linked list). Importantly, these clusters are not always stored next to each other physically on disk but are often fragmented throughout the Data Region.  The File Allocation Table (FAT) is a list of entries that map to each cluster on the partition.  It contains cluster status and a pointer to the next cluster in the chain that is allocated to a file.

The FAT Table

The FAT area holds the FAT table(s), and the FAT table entries point to the clusters in the data area. The FAT table is a data structure which stores the information about which clusters are used, free, or possibly unusable In addition to that, it stores information about the chain of clusters that belong to a particular file. The first data cluster in the volume is cluster #2. Multiple copies of the FAT table reside in the FAT area as well, with the exact number given in the boot sector. These are identical, synchronized copies of the FAT. This is only strictly for redundancy purposes. If an error occurs from reading the primary allocated table, the file system will attempt to read from the backup copies.  In FAT32, a user can disable this FAT mirroring feature and dedicate an “active” table, other than the primary table, for the operating system to read from. The first FAT starts after the reserved sectors, the size of which is given in the boot sector. The total size of each FAT is also given in the boot sector, and the second FAT, if it exists, starts in the sector following the end of the first.

A FAT table contains indexed entries for each data block on the disk, indexed by the cluster address. The FAT has one entry per cluster. Different versions of FAT file systems use different file allocation table entry lengths, and this is where they get their name from.  The FAT12 file system uses 12 bits per FAT entry; thus, two entries span 3 bytes. It is consistently little-endian: if those three bytes are considered as one little-endian 24-bit number, the 12 least significant bits represent the first entry (i.e., cluster 0) and the 12 most significant bits the second (i.e., cluster 1). In other words, while the low eight bits of the first cluster in the row are stored in the first byte, the top four bits are stored in the low nibble of the second byte, whereas the low four bits of the subsequent cluster in the row are stored in the high nibble of the second byte and its higher eight bits in the third byte.  The FAT16 file system uses 16 bits per FAT entry; thus, one entry spans two bytes in little-endian byte order. The FAT32 file system uses 32 bits per FAT entry; thus, one entry spans four bytes in little-endian byte order. The high four bits of each entry are reserved for other purposes, cleared during volume format, and should not be changed otherwise. A FAT32 entry, thus, actually uses the low 28-bits to address clusters.

Corresponding to any cluster number, a FAT entry can have certain permissible values given in the table below.  Note that FAT32 uses only 28 bits of the 32 possible bits. The upper 4 bits are usually zero, but are reserved and should be left untouched. In the table below, these are denoted by a question mark.

Table 1: FAT entry cluster values
FAT12	FAT16	FAT32	Description
0x000	0x0000	0x?0000000	Free cluster.
0x001	0x0001	0x?0000001	Reserved value; do not use.
0x002 - 0xFEF	0x0002 - 0xFFEF	0x?0000002 - 0x?FFFFFEF	Cluster is allocated. Value of the entry is the cluster number of the next cluster following this corresponding cluster. MAX is the Maximum Valid Cluster Number
0xFF0 - 0xFF6	0xFFF0 - 0xFFF6	0x?FFFFFF0 - 0x?FFFFFF6	Reserved and must not be used.
0xFF7	0xFFF7	0x?FFFFFF7	Indicates a bad (defective) cluster.
0xFF8 - 0xFFF	0xFFF8 - 0xFFFF	0x?FFFFFF8 - 0x?FFFFFFF	Last cluster in file or End of Cluster chain (EOC) or End of File (EOF).

The first cluster of the Data Region is cluster #2. That leaves the first two entries of the FAT unused. In the first byte (8 bits) of the first entry, a copy of the BIOS Parameter Block at offset 0x15 (the media descriptor) is stored. The remaining 8 bits (if FAT16) or 20 bits (if Fat32) of this entry are set to 1. In the second entry the end-of-cluster-chain marker is stored. The high order two bits of the second entry are sometimes, in the case of FAT16 and FAT32, used for dirty volume management: high-order bit if set to 1 indicates the last shutdown was clean, otherwise abnormal; the next highest bit if set to 1 indicates that during the previous mount, no disk I/O errors were detected, else there were. Because the first two FAT entries store special values, there is no cluster 0 or 1. The first addressable cluster is cluster 2, which is the reason why BPB value at offsets 0x2C-0x2F of the FAT32 boot sector which indicates the root directory cluster number cannot be less than 2, and is usually 2. The entries, however, are addressed starting with 0, and each entry corresponds to the cluster with the same address.

Figure 1: The relation between FAT entries and clusters

As shown in Figure 1 above, cluster addresses start with 2, whereas the FAT entry numbers start with 0 (zero). Each FAT table entry points to the cluster whose address is equal to the FAT entry number in the data area. For example, FAT entry 2 corresponds to cluster 2. A hex dump of a FAT32 FAT table is interpreted as shown in Figure 2 below.  

Figure 2: Hex dump of a FAT32 FAT table

In most file systems, clusters are the smallest unit of disk space allocated to files and directories. On hard disks, however, a sector is the lowest-level unit the disk hardware can directly address. Because of this, any given disk location can be identified either by its sector number or by its cluster (block) number. Sector numbering is relative to the start of the filesystem/partition, while cluster numbering in FAT file systems is relative to the start of the data area. In FAT, the data area is divided into clusters, and cluster numbering begins at cluster 2. Therefore, to locate the corresponding sector S on disk for a given cluster number C, a conversion is required as follows.

S = (C - 2) * (number of sectors per cluster) + (sector address of cluster 2)

To perform the reverse operation—converting a sector address S back into a cluster address C—the following formula is applied:

C = ((S - sector address of cluster 2) / (number of sectors per cluster)) + 2

However, before using the above formulas for conversion, it is essential to determine which version of the FAT file system you are dealing with: FAT32, or FAT12/16. From the FAT variant, you can determine the location of Cluster 2 accordingly. In FAT12 and FAT16, the root directory is stored immediately after the FAT region, so Cluster 2 comes right after the root directory. In contrast, FAT32 places the root directory within the data area itself, so Cluster 2 starts immediately after the FAT region—at the very first sector of the data area, as shown in the Figure below.

Figure 3: Location of Cluster #2 in the three FAT variants

Determination Of Sector Address Of Cluster 2 In FAT12/16

The general LBA formula for the first sector of a cluster (C), called FirstDataSector in a FAT 12/16 volume, is given as:

FirstDataSector = (number of reserved sector) + ((number of FATs) * (number of sectors occupied by one FAT)) + RootDirSectors

where RootDirSectors is determined by the following formula:

RootDirSectors = ceil(((maximum number of 32-byte entries in the root directory) * 32) / bytes per sector) //The result is typically an integer if the disk is formatted correctly

The Sector address S of a given cluster number (C) is then determined by the following formula.

S = FirstDataSector + ((C - 2) * Sectors per cluster)

The sector address of Cluster #2 in a FAT12/16 volume can be calculated by substituting C with 2 in the above formula. Thus, the Sector address of Cluster #2 = FirstDataSector.

Determination Of Sector Address Of Cluster 2 In FAT32

FAT32 places the root directory within the data area itself, so Cluster 2 starts immediately after the FAT region—at the very first sector of the data area. Therefore, the general LBA formula for the first sector of a cluster (C), called FirstDataSector in a FAT32 volume, is given as:

FirstDataSector = (number of reserved sector) + ((number of FATs) * (number of sectors occupied by one FAT))

The Sector address S of a given cluster number (C) is then determined by the following formula.

S = FirstDataSector + ((C - 2) * Sectors per cluster)

The sector address of Cluster #2 in a FAT32 volume can be calculated by substituting C with 2 in the above formula. Thus, the Sector address of Cluster #2 = FirstDataSector.

Sector address of Cluster 2 = (number of reserved sectors) + ((number of FATs) * (number of sectors occupied by one FAT))

All values discussed thus far must be taken from the BIOS Parameter Block of the FAT volume. In addition, disk space can be accessed by using a byte offset, which is the distance in bytes relative to the beginning of a partition or file system. Given a byte offset B into a partition or file system, we can obtain the corresponding sector address S of the disk space as follows: 

S = floor(B/512)  //where floor() is the floor function

We can use the Sleuth Kit utilities to investigate details of a FAT table as seen below.

Figure 4: Truncated output of the sleuth kit fsstat command

To examine the FAT structure of our sample image, we view sector 6316, which is the first sector following the reserved area.

Figure 5: Sample FAT32 FAT table showing a file stored in several clusters

This output is from a FAT32 file system, so each entry is 4 bytes (two columns) in length. The file occupies nine clusters in the file system (clusters 3, 4, 5, 6, 7, 8, 9, 10, and 11). The nine clusters of interest are underlined. To determine the file content, the starting cluster is first identified as cluster 3 from the Directory Entry. The entry for cluster 3 in the FAT table is then consulted. The value at this location is 0x04. This means that the next cluster in the chain is Cluster 4. Consulting this position in the FAT shows that the next cluster in the file’s content is 5. This continues until we reach cluster 11. When the entry for cluster 11 is examined, the end-of-file marker (0x0FFFFFFF) is discovered. This signifies the end of the FAT chain. Therefore, the cluster chain looks like the following (remember that each FAT entry has 32 bits or 4 bytes in a FAT32). 

• FAT entry 3 contains “0x00000004”, which means the next occupied cluster is cluster 4.
• FAT entry 4 contains “0x00000005”, which means the next occupied cluster is cluster 5.
• FAT entry 5 contains “0x00000006”, which means the next occupied cluster is cluster 6. 
• FAT entry 6 contains “0x00000007”, which means the next occupied cluster is cluster 7.
• FAT entry 7 contains “0x00000008”, which means the next occupied cluster is cluster 8.
• FAT entry 8 contains “0x00000009”, which means the next occupied cluster is cluster 9.
• FAT entry 9 contains “0x0000000a”, which means the next occupied cluster is cluster 10.
• FAT entry 10 contains “0x0000000b”, which means the next occupied cluster is cluster 11.

until FAT entry 11, where cluster 11 is the last cluster allocated to readme.txt. Therefore, FAT entry 11 contains a special flag of the end of file, “0x0fffffff”, which means cluster 11 is the last cluster allocated to the file.  It is worth noting that in this exercise, we only consider a scenario where a file is stored in a hard disk contiguously and without fragmentation. In other words, the list of used clusters will progress linearly, and clusters 3, 4, 5, 6, 7, 8, 9, 10, and 11 (a total of 9 clusters) are occupied by the file.

This also shows how file fragmentation is handled in FAT file systems. The fact that directory entries store only the starting cluster requires the FAT table to be consulted in every case to determine the subsequent clusters in the chain. Hence, in the FAT file system, there is no difference in how contiguous and fragmented files are examined. In every case, the starting cluster is identified in the directory entry, and the FAT chain is then extracted from the FAT table.

Finally, suppose we have the following output from the fsstat tool in TSK. Also, suppose that we wish to convert a hypothetical sector address 18025 to a cluster number. How do we achieve this?

From the above output of the fsstat tool, we know sectors per cluster = 1024/ 512 = 2. Further, since we are dealing with a FAT32 file system, we know the sector address of Cluster 2 is the first sector of the data area, i.e., sector 8192. Therefore, we have:

C = ((S - sector address of cluster 2) / (number of sectors per cluster)) + 2

= ((18025 - 8192) / 2)  + 2.

= 4918.5. Finally, we apply the floor number function to the result.

= 4918.

Hence, we have the cluster number 4918.