How to pass "test free data recovery software" (part 1)

Earlier, my colleague Viktor-Flash conducted a test of free data recovery programs ( first and second parts). He considered two problems that are often found on flash drives with the FAT32 file system. Despite the damage, some programs managed to recover data well. I will try to talk about exactly how the methods work, allowing to return the data and to the extent possible.

The article turned out great, so I broke it into pieces. In the first part I will talk about the FAT32 device and how to recover the data in the first test (where everything was erased before the FAT tables).

How to get to the file in FAT32

I'll start with a superficial description of how data is stored inside FAT32, good, its structure is quite simple in comparison with other FS. Suppose there is a file "\ documents \ Secret.doc" on the flash drive. Let's figure out what path the file system driver goes to read the data in this document.


')
When we connect a USB flash drive to a computer, the OS first checks its 0th sector. It is almost always recorded Master Boot Record (MBR) , it lists the ranges of sectors that are occupied by partitions. On flash drives, the partition is almost always one, it usually begins (but not always) in sector 63 or 2048 and takes up almost all the available space.

The MBR contains a byte label that indicates the type of partition. In FAT32, this is 0x0B or 0x0C. Next, you need to read the first sector of the partition in which the BootFAT32 should be located. From it we can learn a lot of useful information:

• cluster size (block with which the FS operates);
• the number, size and location of FAT tables (usually 1 or 2, I’ll tell you further about their purpose);
• the beginning of the clustering area - the area that is divided into clusters and which is available for recording user data;
• a cluster with the root directory, also known as Root (often the 2nd cluster) *.

* Note: in FAT32, the clustering area is numbered from the 2nd cluster, i.e. Root is often located at the very beginning of this area.



Each folder in FAT corresponds to a list structure, which is called FAT Folder (or FAT directory). This is a list of subdirectories and files that a particular directory contains. Each element of the list contains: name, size for the file, dates of creation, deletion, modification, attributes and starting cluster (the beginning of the file or the location of the corresponding FAT Folder structure for the subdirectory).

An important point, which we then use. Any FAT directory, except the root, begins with 2 standard elements. These are descriptors of the self. " and parent '..'. And already further descriptors of all other subdirectories and files. Those. we can check the current cluster number (the start cluster is '.'), and we can also go up one level in the hierarchy (go to the '..' directory).



So, we found and parsed the root directory, found an entry in it about the subdirectory named "documents". Moved to the specified cluster to find out the contents of the documents folder, dismantled the corresponding FAT Folder. They found a descriptor for the file "Secret.doc" from which, among other things, we learned the first cluster of the file and the file size.

If all files were continuous, then this would already be enough to read the file data. But for fragmented files, you still need to build the location. The FAT table is just needed in order to put the file related clusters in the correct order. If “TopSecrect.doc” starts in cluster No. 100, then in the 100th cell of the table it will be indicated which cluster to take next, i.e. where the second file cluster is located. And so on through the chain. At the end of the cluster chain will be an end marker. Free clusters are also marked with a special value of 0 (remember that there is no 0th cluster?), The FAT table also serves to track the free / used space in the partition.

(picture from technet.microsoft.com )

Now that we are more or less familiar with the FAT32 device, we can speculate on how to treat it.

Test one: no boot'ov

The first test was that everything was erased before the start of the FAT tables. This means that we have lost BootFAT32 and its copy (if it was). And along with them, and a bunch of useful information. But is it difficult to restore it? It turns out that simple.

I'll start with the FAT tables. We do not know exactly where to look for them, but we know what they are. Fortunately, the tables have a recognizable and verifiable structure. The search is based on the following observations:

• FAT table has a characteristic beginning (remember the 0th and 1st “mythical” clusters?) - often 0xF8FFFF0FFFFFFFFF
• cells in the FAT table (4-byte unsigned integers) can contain either overhead values ​​or limited by the size of the partition;
• in addition, the entire FAT table should not have the same values ​​(except service ones);
• for many cells in the table, it can be argued that cell N contains the value N + 1, that is, after cluster N comes cluster N + 1. This is a purely heuristic observation. It is valid because the FS driver still tries to place data continuously.

Thus, we can find a table or FAT tables and even determine their size (at least the size of a significant part). Immediately after the last table, the root directory is often found and, at the same time, the beginning of the clustering area. You can test this assumption, but there is a more universal way.

Remember that all FAT directories, except the root, start with 2 standard entries? So, these records allow you to find them very well among all the other data. If we find only 2 directories, we get 2 pairs of values: (LBA1, ClusterNo1), (LBA2, ClusterNo2) . And this is a school problem for proportions, from which we immediately find the cluster size

ClusterSize = (LBA1-LBA2)/(ClusterNo1-ClusterNo2) 

and the beginning of the clustering area (remember the “eaten” clusters 0 and 1)

 ClusterizationStart = LBA1 – (ClusterNo1-2)*ClusterSize 

It remains to find Root. In any directory there is an entry about the parent directory '..'. If we go up the hierarchy, we will quickly get to Root (which we learn, for example, by the absence of the '.' And '..' records).

Conclusion on the first test

We had to try a little, but we found all that is needed for full data recovery: FAT tables, the beginning of the clustering area, cluster size, Root position. It can be argued that for such damage there is a technique that allows in most cases to return 100% of the data (get the same file system as before), lost forever still can be found ... The “minority” of cases is when it was not possible to find even a couple of FAT Folders or there were problems finding FAT tables. However, such situations are rather rare.

PS

The format for storing data in FAT32 is described in the document: Microsoft Extensible Firmware Initiative FAT32 File System Specification
A less detailed description on technet: FAT File System

Continuation of this article