(audience applause)
- Some things can't be unseen.
So look, probably there's a lot of people in the room
who think of me as this kind of crazy guy
who spends a lot of time looking at the internals of
UNIX file systems in a hex editor.
Yeah, well this presentation is going to do
nothing to correct that opinion,
so this is actually based on some ideas that I had
when I had been doing my Linux forensics casework,
and sometimes you deal with investigations
where bad things happen to your file system.
You're dealing with a damaged file system
and I wanted to talk about a couple of different cases.
One is one that I actually experienced where
our suspects became aware that, you know,
we were about to seize their systems,
and so they did the, "Cheese it, the cops."
Let's remove the file system
and try and get rid of all of the evidence.
The other one can happen accidentally, right,
you know, you're gonna zero that drive for your next case.
Oh, did I mean to type sda?
No, no I didn't, I just overwrote
at least part of my primary hard drive,
but you also see people doing this for exfoliation, I mean,
you know, either overwriting the drive,
or putting a new virgin operating system
on top of the nefarious stuff, so these are all cases where
you've got either the remnants of a removed file system
or fragments of a preexisting file system,
but things are messed up,
and things are messed up in a particular way.
In both of these scenarios,
the situation you're dealing with is basically
all the metadata is gone, right, so what ain't you got?
You ain't got metadata, and you know,
and that actually covers a lot of territory so first up,
all the inode information right,
so when I delete something in UNIX file system,
the inode associated with the file or directory
that I deleted is mostly zeroed out,
so all of the block pointer information
or all of the extent information gets zeroed out.
You lose that mapping to where
the content of the file used to live on disk, right?
If somebody overwrites the file system,
the inodes in the beginning of each block group
get overwritten, so you lose all of that inode metadata.
You don't know where the files
used to live on the disk anymore.
Ext, at least through ext3 forward
is a journaling file system, so you think, oh, okay,
well I'm gonna, you know, go look at the journal.
Problem is, you know, if I just
rm minus rf the entire file system,
so many journal transactions happen during that event
that you basically overrun the journal, I mean,
you overwrite the old stuff, so the journal doesn't give you
a very large window of what happened to that file system,
so you can't really use the journal to reconstruct things.
If the file system is damaged,
you may have even lost the inode for the journal,
so you don't even know where the journal lives on disk,
so you have to go groveling around through unallocated
to try and find and reconstruct the journal blocks
which are spread all over the place.
And the other thing is,
and it turns out that in my research,
the last one is actually the most difficult one for me.
The block and inode allocation maps
that sit up at the beginning of the block group
also get overwritten, so you're going through,
you know, trying to recover blocks
from the remaining disk space,
but you don't know which ones of those blocks
are actually allocated and part of the file system,
or which represent old data, and that,
as it turns out, it turns out to be a hassle,
so all of this metadata is completely gone,
but I still wanted to say, okay so,
what can I do as far as file system recovery,
even in a scenario where I basically
have no metadata that I can work with,
so what do you have left?
So what you have left is at least some of
the actual data blocks that used to be in the file system,
and in those data blocks,
you've got directory content, right?
So UNIX file systems, basically,
directories are nothing more than
sequential lists of entries, and those entries,
all they do is they map file names
and directory names to inode numbers, right,
so here's a example.
This is a partial directory.
So let's say this is my home directory.
If you look at the internals of
that directory file for home/hal,
what you see is the sequential list of entries
and they're not even in alphabetical order.
They're basically in the order in which
the objects were created in the directory, right?
So every directory starts with
the dot and dot-dot links that, you know,
the dot link points to the directory itself,
the dot-dot link points to the parent, but then,
you've just got, you know, a bunch of entries,
so inode number 127153 is the directory.
The file type is also stored in the directory file,
called Downloads, you know,
and then there's my desktop directory
and my dot profile file, and so on.
Just bang, bang, bang, one after the other
in this directory file.
Okay now, you know, if the file system is whole
and fully connected, you know,
okay, that's my home/hal directory,
but if I'm just groveling around in a damaged file system
and I find this block of directory entries,
I don't actually know the name of that directory.
I know there's a block that has, you know,
downloads, desktop, dot profile, and dot ssh directories,
so it's probably some user's home directory,
but I don't particularly know which user it is.
Okay, so that's part of the problem.
You're running around through this damaged file system
and you keep finding these directories,
but how do you reconnect them back into
the original contiguous file system?
Well look, okay, so this is, you know,
this was, at least at one point, the home/hal directory,
so somewhere else on the disk,
I'm gonna find a block of data
which was the slash home directory, right?
So if I look at that block of data,
there's an entry in there for hal, right,
you know, there used to be a home/hal directory.
So this is where the intelligence starts coming in.
All right, so think about it, right.
So home/hal has a dot link that points to itself,
and that dot link tells us that
the original inode associated with
this directory was 127151, right?
I don't know the name of the directory,
but I know what inode used to be associated with it,
but if I look at its parent, the old home directory now,
there should be an entry, right?
So there's an entry that, you know,
corresponds to that 127151, right,
that actually tells me the name
associated with that inode, right?
So if can find the parent, I can match up the inode numbers
and go, oh, cool, you know, 127151 is hal,
so that's how you can get to a file name,
you know, by tying the inodes together,
so you have to find the parent
and then, use the dot linkage to figure that out.
But you also have the dot-dot link, so you know,
by way of confirmation, right,
I know that in the original home/hal directory,
there's a dot-dot link that points back to its parent,
so it's inode number 18350, right?
So the dot link in the parent
should be the same inode number, right?
So, 18350 should be the inode associated with
the dot link in the corresponding parent directory,
so you can use that for confirmation, right,
as you're going through and you're finding
all of these directory blocks
floating around in the file system,
you can use these linkages to tie everything back together,
and ultimately, you know, if you find enough of this,
you can begin reconstructing the original file system,
even without any of the metadata, I mean,
we're just like brute force, you know,
raw parsing the directory files, but it kind of works.
So, great, but how do I even locate these directory files.
I mean, in a connected file system, it's easy,
because the inodes are there
and you can find the directory file content,
but with the metadata gone,
how do I even begin identifying these directory blocks
in order to begin parsing them?
The answer is, if you think about it,
there's actually a signature
associated with directory files, right,
so we can actually use this signature
to carve for the directory blocks,
and to understand that signature,
you have to look a little bit more closely at exactly
how these UNIX directory entries are structured.
Okay, so the first thing that you need to understand is
that UNIX directory files must begin
with a dot and dot-dot link, so they always have
those two entries right at the front of the block.
So you're thinking, well, if I could characterize
what those entries look like,
I should be able to create a signature,
and that's exactly right, so a directory entry
is actually, it's a variable length record.
The first four bytes are always the inode number,
you know, whatever inode number that happens to be,
and then, the next two bytes
are the total length of the directory entry,
including the inode field and the entry length field.
It's worth noting that directory entries
in UNIX file systems are four byte aligned,
so you know, in the case of the dot link,
I could actually fit that directory entry into nine bytes,
but because everything has to be four byte aligned,
the dot link is always 12 bytes long,
so it's rounded up to the next four byte quantity.
Okay, so you've got the entry length,
and then, the actual length of the file name,
which in the case of the dot link is just one character,
right, so that's, you know, one byte long.
Then you have a byte which is
the file type, the file type code.
Two is the code for subdirectories,
and then, you actually have the file name.
Now in the case of the dot link,
there's three extra bytes in the directory entry,
so we round up to a four byte quantity,
and those are just null filled.
So once you put all that together,
I mean, you can see it on the slide,
there's actually a very nice signature
for that initial dot entry.
There's, you know, gonna be four bytes
of whatever the inode is, but after that four byte offset,
it's always gonna be a 12 byte directory entry length,
so it's little envian, so zero C zero zero, and then,
the length of the file name is always gonna be one,
and then the type is always gonna be two
because it's always a directory, and then,
the file name itself field
is always gonna be two E, and then nulls.
So that's a nice, you know, eight byte signature,
offset four bytes from the beginning of the block,
and it's very easy to pull out the initial directory block
using that signature, so that what you do.
You basically just run through the blocks
looking for that signature.
And you can begin finding these and parsing them.
Okay, so great, so we have this idea
that if we find these directory blocks
and parse through them, we can, you know,
maybe reconstruct the file system
by using these inode linkages.
Nothing is ever that easy though, right?
Typically, UNIX directories tend to be small.
90 or more percent of the directories
in your UNIX file system are only gonna be
a single block long, and so, that's great, I mean,
we can locate the blocks using the signature we saw
on the previous slide and we're good to go, but you know,
five to 10 percent of the directories
in your UNIX file system are gonna be large enough
that they need to go across multiple blocks.
Unfortunately, typically, directory files
that are more than a single block tend to be fragmented,
and the reason for that is
the way UNIX file systems tend to do block allocation,
so the way this works in UNIX file systems is
blocks are grouped together into these block groups
that are scattered throughout the disk.
When you create a new subdirectory,
it goes into the least used block group, basically,
and then, as you add files in that subdirectory,
the file system driver tends to allocate the files
in the same block group with its directory,
so the problem is, you know,
you start off with a small directory
and you keep adding files and keep adding files,
and the directory grows to a point where
the directory file needs to gwom a second block onto it.
By the time that happens, all of the blocks
near the original directory block
have been allocated to files, and so,
you almost always will fragment
the second block of the directory file,
so the problem for us reconstructing the file system is
okay, I can find the original block of the directory
by using the dot link signature,
but what happens if it's a big directory?
I don't know where the rest of that directory file is,
so that was an issue.
The other thing that you have in active file systems is
you know, things get deleted,
and so there's some interesting detail around
parsing deleted directory entries,
which we'll talk about in a little bit.
There's also this problem where there's just churn, right,
so you know, a file or directory is created
in a temp directory, for example, and then it gets deleted,
and then its inode gets reallocated to some other file,
but there may be copies of the old data floating around,
and as I discovered when I started
doing this in real file systems, there's actually like
a lot of copies of the same directory data,
because you end up finding copies of the directory block
in journal entries, and you know, it's just, it's nuts,
it's actually quite a lot of conflicting
and redundant information that you have to somehow
navigate through to try and build an idea
of what the original file system was,
so I want to talk a little bit about
some of the points on this slide,
and describe a bit of the pain that I went through
when I was trying to deal with this.
All right, so let's first talk about
deleted directory entries and
how those work in UNIX file systems.
Okay, so we start with a simple directory.
It's got five files in it plus the dot and dot-dot links.
By the way, quiz time, there's an RMO in it
for the first person who can tell me
what the file names are in this directory.
Okay, so while you're working on that.
So here we've got a simple directory, right,
so we got five files, bang, bang, bang, bang, bang,
plus the dot and dot-dot link.
One thing to notice here,
check out the entry length field,
which is the second column, on that last entry.
You see it's a big number?
Remember, it's little envian, so it's 0FB4.
Okay, so for those of you who don't want to
pull out your trusty calculator,
I'll do the Math for you.
That number corresponds to 4020.
If you do the Math on this,
there's 76 bytes of directory entries preceding that entry.
And so, the way this works in ext files systems,
the last entry is always block aligned,
so however much space is left in the block,
that's what the length of the last entry is, okay.
Directory entries are not allowed to cross block boundaries.
So anyway, just a little note there.
Okay now, let's see what happens to this directory
if I basically rm minus rf that directory.
Now, if I rm minus rf that directory,
the inode that used to point to this directory
is zeroed out, but the block that was that directory file
is still there on disk and you can take a look at it,
and what you see just at the surface,
take a look at the entry length for the dot-dot field.
You'll notice that it's another big number,
so what happens when I rm minus rf a directory is
all of the files get unlinked from that directory,
so just before the directory itself is unlinked,
it's an empty directory, okay,
and so that's what you see there.
The entry length for that dot-dot link is actually 4084.
Basically, the 12 bytes of the dot entry,
and then, everything else in the block.
But if you look past that dot-dot entry,
you can still see the original directory entries
for the files that used to be in that directory.
They're basically now in the slack space of the directory,
the unallocated space of that directory,
but you can go parse them out.
They haven't moved.
The data is still there.
The inode numbers and the file names are still there,
so you can parse them out,
and this is the way deletion works in UNIX directory files.
When you delete a file somewhere in the directory,
the previous entry grows to basically
consume the old deleted directory entry.
But the old directory entry is still there
and can be parsed out if you go looking for it,
so one of the things that you need to do
when you're groveling through these UNIX directory files
is if you've got a bunch of slack space
at the end of a directory entry,
go look at that and see if it's a parsable directory entry.
You know it has to be four byte aligned, right,
so you can write some parsing code
to go find the deleted directory entries,
because, you know, in this case,
the deleted directory entries are interesting.
They tell me the file names
that were in that directory originally.
Anybody got the file names yet?
Come on.
- [Man In Audience] See to a dot at the end.
- Correct, good call.
Good catch, okay, so,
all right, so great, so now we've got,
you know, deleted directory entries that we care about,
and we need to parse for those.
Now, the other thing is this, you know,
thing I talked about with inode churn, right,
you're gonna find a lot of conflicting information
when you go through a UNIX file system.
You're gonna find a bunch of blocks
that all talk about the same inode number,
and they may tell you that that inode number
is associated with different file names.
So you go parsing through the blocks in your file system,
your damaged file system, and you find 12 blocks
that say, you know, inode number 390936 is
tmp/systemd, some random GUID that has NJU in it,
and then, you find another 10 blocks that say,
that same inode number, 390936,
is tmp/systemd, some other GUID that starts qYK something.
So the question is which information is correct?
Which do you believe?
If you're trying to reconstruct the file system,
which one is it?
Okay, so since I can't really see people,
we'll do this by applause.
How many people think it's the first one,
the 12 blocks that say it's systemd NJU blah, blah, blah,
so applaud if you think that's the one.
Wow, okay.
Okay, that guy.
All right, so how many of you think it's the second one,
it's the 10 blocks that say qYK?
Wow, nobody is willing to put their
money where their mouth is on this one.
Okay, so there was more people that said
it was the second one.
Huh, guess what?
It's neither one.
The file had actually been
completely unallocated from the original file system.
What you're finding is old residual data that
actually isn't even relevant to the original file system.
Ha, welcome to my world.
Okay, so this gives you an idea of
some of the complications that arise trying to reconstruct
this information into a meaningful file system.
So I spent a bunch of time beating my head around this,
and trying to come up with little puristic methods
and things like that, and I've got a tool now
that I think is about 95, 98% effective
at rebuilding the original file system
just from the basic data blocks,
and I checked that in to a new Git Hub repo
this morning before I came down,
and with apologies to David Kovar,
I call the tool, Analyze EXT.
Some of you may have used David's Analyze MFT tool,
and I'm sure I'll get a complaining email from him
from stealing his idea, so anyways,
so there's an Analyze EXT tool that you can use
that will try and reconstruct a file system layout
purely based on data block information
that it finds in your image.
It also can just dump out raw information
about what it finds in these directory blocks,
and it dumps it out in a tab delimited format
so that you can like load it into a spreadsheet
and process the data that way.
(dramatic music)