Some thoughts about FAT Filesystem
Some information raised during preparation of GCFA exam
FAT, or File Allocation Table, is a file system that is designed to keep track of allocation status of clusters on a hard drive.
Originally designed in 1977 for use on floppy disks with Microsoft Disk BASIC interpreter, FAT was soon adapted and used almost universally on hard disks throughout the DOS and Windows 9x eras for two decades.
As disk drives evolved, the capabilities of the file system have been extended accordingly, resulting in three major file system variants: FAT12, FAT16 and FAT32.
Structure
The File Allocation Table (FAT) file system is a simple file system originally designed for small disks and simple folder structures.
The FAT file system is named for its method of organization, the file allocation table, which resides at the beginning of the volume. To protect the volume, two copies of the table are kept, in case one becomes damaged.
In addition, the file allocation tables and the root folder must be stored in a fixed location so that the files needed to start the system can be correctly located.
Boot Record
When a computer is powered on, a POST (power-on self test) is performed, and control is then transferred to the Master boot record (MBR).
The MBR is present no matter what file system is in use, and contains information about how the storage device is logically partitioned. When using a FAT file system, the MBR hands off control of the computer to the Boot Record, which is the first sector on the partition.
The Boot Record, which occupies a reserved area on the partition, contains executable code, in addition to information such as an OEM identifier, number of FATs, media descriptor (type of storage device), and information about the operating system to be booted.
Once the Boot Record code executes, control is handed off to the operating system installed on that partition.
FATs
The primary task of the File Allocation Tables is to keep track of the allocation status of clusters, or logical groupings of sectors, on the disk drive.
There are four different possible FAT entries: allocated (along with the address of the next cluster associated with the file), unallocated, end of file, and bad sector.
In order to provide redundancy in case of data corruption, two FATs, FAT1 and FAT2, are stored in the file system.
FAT2 is a typically a duplicate of FAT1. However, FAT mirroring can be disabled on a FAT32 drive, thus enabling any of the FATs to become the Primary FAT. This possibly leaves FAT1 empty, which can be deceiving.
Root Directory
The Root Directory, sometimes referred to as the Root Folder, contains an entry for each file and directory stored in the file system.
This information includes the file name, starting cluster number, and file size. This information is changed whenever a file is created or subsequently modified.
Root directory has a fixed size of 512 entries on a hard disk and the size on a floppy disk depends. With FAT32 it can be stored anywhere within the partition, although in previous versions it is always located immediately following the FAT region.
Data Area
The Boot Record, FATs, and Root Directory are collectively referred to as the System Area.
The remaining space on the logical drive is called the Data Area, which is where files are actually stored. It should be noted that when a file is deleted by the operating system, the data stored in the Data Area remains intact until it is overwritten.
Clusters
In order for FAT to manage files with satisfactory efficiency, it groups sectors into larger blocks referred to as clusters.
A cluster is the smallest unit of disk space that can be allocated to a file, which is why clusters are often called allocation units.
Each cluster can be used by one and only one resident file. Only the “data area” is divided into clusters, the rest of the partition is simply sectors. Cluster size is determined by the size of the disk volume and every file must be allocated an even number of clusters.
Cluster sizing has a significant impact on performance and disk utilization. Larger cluster sizes result in more wasted space because files are less likely to fill up an even number of clusters.
The size of one cluster is specified in the Boot Record and can range from a single sector (512 bytes) to 128 sectors (65536 bytes). The sectors in a cluster are continuous, therefore each cluster is a continuous block of space on the disk. Note that only one file can be allocated to a cluster.
Therefore, if a 1KB file is placed within a 32KB cluster there are 31KB of wasted space. The formula for determining clusters in a partition is (# of Sectors in Partition) — (# of Sectors per Fat * 2) — (# of Reserved Sectors) ) / (# of Sectors per Cluster).
Wasted Sectors
Wasted Sectors (a.k.a. partition slack) are a result of the number of data sectors not being evenly distributed by the cluster size. It’s made up of unused bytes left at the end of a file.
Also, if the partition as declared in the partition table is larger than what is claimed in the Boot Record the volume can be said to have wasted sectors. Small files on a hard drive are the reason for wasted space and the bigger the hard drive the more wasted space there is.
FAT Entry Values
FAT12
- 00x000 (Free Cluster)
- 0x001 (Reserved Cluster)
- 0x002–0xFEF (Used cluster; value points to next cluster)
- 0xFF0–0xFF6 (Reserved values)
- 0xFF7 (Bad cluster)
- 0xFF8–0xFFF (Last cluster in file)
FAT16
- 0x0000 (Free Cluster)
- 0x0001 (Reserved Cluster)
- 0x0002–0xFFEF (Used cluster; value points to next cluster)
- 0xFFF0–0xFFF6 (Reserved values)
- 0xFFF7 (Bad cluster)
- 0xFFF8–0xFFFF (Last cluster in file)
FAT32
- 0x?0000000 (Free Cluster)
- 0x?0000001 (Reserved Cluster)
- 0x?0000002–0x?FFFFFEF (Used cluster; value points to next cluster)
- 0x?FFFFFF0–0x?FFFFFF6 (Reserved values)
- 0x?FFFFFF7 (Bad cluster)
- 0x?FFFFFF8–0x?FFFFFFF (Last cluster in file)
Note: FAT32 uses only 28 of 32 possible bits, the upper 4 bits should be left alone.
Typically, these bits are zero, and are represented above by a question mark (?).
Versions
There are three variants of FAT in existence: FAT12, FAT16, and FAT32.
FAT12
- FAT12 is the oldest type of FAT that uses a 12 bit file allocation table entry.
- FAT12 can hold a max of 4,084 clusters (which is 212 clusters minus a few values that are reserved for values used in the FAT).
- It is used for floppy disks and hard drive partitions that are smaller than 16 MB.
- All 1.44 MB 3.5" floppy disks are formatted using FAT12.
- Cluster size that is used is between 0.5 KB to 4 KB.
FAT16
- It is called FAT16 because all entries are 16 bit.
- FAT16 can hold a max of 65,524 addressable units
- It is used for small and moderate sized hard disk volumes.
FAT32
FAT32 is the enhanced version of the FAT system implemented beginning with Windows 95 OSR2, Windows 98, and Windows Me. Features include:
- Drives of up to 2 terabytes are supported (Windows 2000 only supports up to 32 gigabytes)
- Since FAT32 uses smaller clusters (of 4 kilobytes each), it uses hard drive space more efficiently. This is a 10 to 15 percent improvement over FAT or FAT16.
- The limitations of FAT or FAT 16 on the number of root folder entries have been eliminated. In FAT32, the root folder is an ordinary cluster chain, and can be located anywhere on the drive.
- File allocation mirroring can be disabled in FAT32. This allows a different copy of the file allocation table then the default to be active.
Limitations with Windows 2000 & Windows XP
- Clusters cannot be 64KB or larger.
- Cannot decrease cluster size that will result in the the FAT being larger than 16 MB minus 64KB in size.
- Cannot contain fewer than 65,527 clusters.
- Maximum of 32KB per cluster.
- Windows XP: The Windows XP installation program will not allow a user to format a drive of more than 32GB using the FAT32 file system. Using the installation program, the only way to format a disk greater than 32GB in size is to use NTFS. A disk larger than 32GB in size can be formatted with FAT32 for use with Windows XP if the system is booted from a Windows 98 or Windows ME startup disk, and formatted using the tool that will be on the disk.
exFAT (sometimes incorrectly called FAT64)
exFAT (also known as Extended File Allocation Table or exFAT) is Microsoft’s latest version of FAT and works with Windows Embedded CE 6.0, Windows XP/Server 2003 (with a KB patch), Vista/Server 2008 SP 1 & Later, and Windows 7.
Features include:
- Largest file size is 264 bytes (16 exabytes) vs. FAT32’s maximum file size of 4GB.
- Has transaction support using Transaction-Safe Extended FAT File System (TexFAT). (Not released yet in Desktop/Server OS)
- Speeds up storage allocation processes by using free space bitmaps.
- Support UTC timestamps (Vista/Server 2008 SP1 does not support UTC, UTC support came out with SP2)
- Maximum Cluster size of 32MB (Fat32 is 32KB)
- Sector sizes from 512 bytes to 4096 bytes in size
- Maximum FAT supportable volume size of 128PB
- Maximum Subdirectory size of 256MB which can support up to over 2 million files in a singlr subdirectory
- Uses a Bitmap for cluster allocation
- Supports File Permissions (Not released yet in Desktop/Server OS)
- Has been selected as the exclusive file system of the SDXC memory card by the SD Association
Although Microsoft has published some information on exFAT, there are more technical specifications available from third parties.
FAT Filesystem in forensics analysis
Disk Unit Addressing
FAT saves file content in clusters. A cluster is a grouping of consecutive sectors (512-bytes each). When a file is described by the directory entries and File Allocation Table, the cluster numbers are used as addresses. The problem, is that cluster 0 is not at the beginning of the partition. Cluster 0 is in the Data Area, which is after the super block and File Allocation Tables and can be hundreds of sectors into the partition. This creates a problem because if The Sleuth Kit were to use clusters as the addressable units, then there would be no way to identify the non-”data area” sectors.
This problem was solved by making the sector as the addressable unit, instead of the cluster. When a file is described (using istat for example), the sector addresses are given. In the output of fsstat, the File Allocation Table contents are displayed in sectors and when using blkls -l, the sector status is given.
This actually makes manual data recovery easier because one can use ‘dd’ to carve out data using the sector addresses. If clusters were given, the user would have to translate the Data Area address to sectors before carving out data.
Metadata Addressing
FAT describes its files in a directory entry structure, which is contained in the sectors allocated by the parent directory.
The directory entry structures have a fixed size of 32-bytes, not addressed, and can exist anywhere in the partition.
The Sleuth Kit needs some form of Metadata Address for each file, so this became a problem. Also, the root directory does not have a directory entry. In other words, there is no descriptive information for the root directory.
The solution to this problem was to use the same method that is used in many UNIX implementations. Each sector in the data area is treated as though it could be full of directory entries.
As each sector is 512-bytes and each directory entry is 32-bytes, each sector could contain 16 entries.
To keep things similar to UNIX, the root directory is given the value of 2. The first 32-bytes of the first sector in the data area are addressed as 3, the second 32-bytes of the sector are 4 etc.
The Sleuth Kit will scan through the sectors and identify which ones actually contain directory entries.
This method will produce large gaps of addresses between used address values.
Notes on Timezones
FAT does not store the file times in the delta format that UNIX does.
Instead of saving the difference in time from GMT, FAT simply saves the raw hour, minute, and second values.
The Sleuth Kit stores all times in the UNIX GMT offset format and will translate the FAT time to the UNIX offset. This uses the current timezone value when identify the GMT offset.
If the tool displays the time in a nice ASCII format, the same timezone will be used to translate the offset value into a date. Therefore, you can use any timezone value and the time will not change (just the timezone name). On the other hand, if you use a tool such as ils or fls -m, which display the time in the offset format, then it will have the offset of the current timezone or the one specified with ‘-z’. Therefore, ensure that the same ‘-z’ argument is used with mactime to display the correct time in the timeline.
General Notes on Time
Each file in FAT can store up to three times (last accessed, written, and created).
- Last written time is the only ‘required’ time and is accurate to a second.
- Create time is optional and is accurate to the tenth of a second (Note that I have seen several system directories in Windows that have a create time of 0).
- Last access time is also optional and is only accurate to the day (so the times are 00:00:00 in The Sleuth Kit).
Sentinel Timestamps
- January 1, 0001 — The value 0 as a CLR System.DateTime.
- January 1, 1601 — The value 0 as a Win32 FILETIME.
- December 29/30, 1899 — The value -1 or 0 as an OLE automation date.
- December 13, 1901 — The value 0x80000000 as a time_t.
- December 31, 1969, January 1, 1970 — The value -1 or 0 as a time_t.
- January 1, 1980 — The beginning of the DOS date/time era. (Unlikely to be encountered since 0 is not a valid DOS date/time value.)
- January 19, 2038 — The value 0x7FFFFFFF as a time_t.
- February 7, 2106 — The value 0xFFFFFFFF as a time_t.
- September 14, 30828 — The value 0x7FFFFFFF`FFFFFFFF as a FILETIME.
All of these special values have one thing in common: If you see them, it’s probably a bug.
Typically, they will arise when somebody fails to do proper error checking and ends up treating an error code as if it were a valid return value. (The special values 0, -1, and 0xFFFFFFFF are often used as error codes.)
Data Recovery
Recovering directory entries from FAT filesystems as part of recovering deleted data can be accomplished by looking for entries that begin with a sigma 0xe5.
When a file or directory is deleted under a FAT filesystem, the first character of its name is changed to sigma.
The remainder of the directory entry information remains intact.
The pointers are also changed to zero for each cluster used by the file. Recovery tools look at the FAT to find the entry for the file.
The location of the starting cluster will still be in the directory file. It is not deleted or modified. The tool will go straight to that cluster and try to recover the file using the file size to determine the number of clusters to recover.
Other tools will go to the starting cluster and recover the next “X” number of clusters needed for the specific file size. However, this tool is not ideal.
An ideal tool will locate “X” number of available clusters. Since files are most often fragmented, this will be a more precise way to recover the file.
An issue arises when two files in the same row of clusters are deleted. If the clusters are not in sequential order, the tool will automatically receive “X” number of clusters. However, because the file was fragmented, it’s most likely that all the clusters obtained will not all contain data for that file. If these two deleted files are in the same row of clusters, it is highly unlikely the file can be recovered.
File Slack
File slack is data that starts from the end of the file written and continues to the end of the sectors designated to the file.
There are two types of file slack, RAM slack and Residual slack.
- RAM slack — starts from the end of the file and goes to the end of that sector.
- Residual slack — starts at the next sector and goes to the end of the cluster allocated for the file.
File slack is a helpful tool when analyzing a hard drive because the old data that is not overwritten by the new file is still in tact.
References