How does forensic software detect deleted files

There are any number of different ways it can be done. In large part, the easiest way is following the link pointers to each of the chunks, but that isn't the only way by any means. (The MFT isn't the only source of those links in many file systems as well.)

At a lower level, it can identify all the chunks and try to match some of them up on content if the files have an internal structure that allows one chunk to be matched to another. That won't work for all files though if the pointers are removed, since some don't have much of a pattern to them, but it will work with enough that it's still a major concern, especially since unless your drive is highly fragmented, even a large file probably isn't more than a few dozen large pieces.

Basically, there are a ton of different ways you can try piecing stuff together based on either the physical structure of the drive (contiguous blocks are generally preferred if available), file system features (such as forward and reverse block links) or file structure features, which vary from file to file.

Short of total destruction, there are any number of possible ways to recover the file. In some cases, simply removing the pointers may be enough, but a truly determined analysis can likely still put the jigsaw together by looking for fragments that make sense together, particularly if they are looking for something in particular.

A forensic tool such as FTK imager, is essentially a binary data reader and interpreter. Oversimplified, it reads each value and shows you both the hexidecimal (or decimal) absolute value and/or the interpreted value (such as text). Google for more examples and explanations of how FTK imager works.

Notice that a forensic toolkit is merely a tool. Most provide some level of processing to help you determine if what you are seeing is what you want to see.

Something that may help is to understand how file systems work. Here is a well put together book (I know it's old, but it's still relevant). Here is also a brief overview of the NTFS.

Edit: Example Exercise

So here is a super quick and fun way for you to see how all this works. First, I recommend you read through the aforementioned book but regardless you can follow these steps:

1. Get some form of media to store a file on (I recommend a small 256mb sd card or the like).
2. Reformat the media (in windows unselect the 'quick format option' and make sure it is formatting in NTFS).
3. Open the media and create a simple text file with a short name and put your email address in it.
4. Save the file and check to see if everything looks normal.
5. Open up the media and just delete the file.
6. Open FTK Imager, choose 'add evidence item' and select your media.
7. Now, just look for your email address.
8. Experiment and learn till your heart's content!

This simple exercise demonstrates how easy it is to find a deleted file (even without it's MFT). I love doing this with my students because you can learn so much by just varying this exercise and if you combine it with a textbook, bam!

In NTFS, all of the metadata is stored in the MFT. This includes names, dates, parent folder, etc. the occupied clusters are also stored in there in a structure called data runs. The clusters storing the file data hold only file data and there is no linked list that holds info about the next or previous cluster.

When a file is deleted (assuming a skip of the recycle bin), there is a single bit in the MFT record that gets turned off. The rest of that record stays in place exactly how it was otherwise. The metadata from a deleted file does not get wiped out until a new file needs to occupy that record slot with its metadata.

The MFT is a contiguous block of clusters with records in the size of 1024 bytes. NTFS uses the first unallocated record (from the top) when it creates a new file.

Forensic tools need only start at the top of the MFT and treat each block of 1024 bytes as a record. If the deleted/allocated bit is on, then it is an allocated file. If it is off, then the file has been deleted.

There was mention in another comment of wiping MFT unallocated space, and this is one way of trying to hide metadata. This involves writing over the records in the MFT that have been marked as deleted.

If that metadata is gone, it makes file recovery more difficult, but not impossible.