Hash Trees

Instead of having directory entries in an unsorted order, a hash tree can be used to sort some of the entries. Each block in the directory corresponds to a node in the tree. The non-leaf nodes have data structures that point to the next layer. In a smaller directory, there are two layers, and the first block is the only node at the top layer.

To show which blocks correspond to the nodes in the next layer, there are node descriptor data structures. Before the node descriptors is a header data structure, and it starts following the '..' directory entry. The node descriptor header has the fields given in Table 15.25.

Table 15.25. Data structure for the hash tree node descriptor header.

Byte Range







Hash version



Length of this structure



Levels of leaves





Following the header is a list of node descriptors that identifies what hash values are in each block. Each entry in the list has the data structure given in Table 15.26.

Table 15.26. Data structure for the hash tree node descriptor entries.

Byte Range



0 3

Minimum hash value in node


4 7

Block address


Each entry contains the smallest hash value and the directory block of the node. The first node descriptor does not need a minimum because it should be 0. Therefore, those four bytes are used for another purpose. They store the current number of node descriptors and the maximum number of node descriptors that can fit in the block. Therefore, the first node descriptor has the fields given in Table 15.27.

Table 15.27. Data structure for the first node descriptor entry.

Byte Range




Maximum number of node descriptors



Current number of node descriptors



Block address of first node


The remainder of the block after the last node descriptor typically contains data from previous directory entries.

Here we see the contents of the first block in a large directory using a hash index:

# icat -f linux-ext3 ext3-3.dd 16

0000000: 1000 0000 0c00 0100 2e00 0000 0200 0000 ................

0000016: f403 0200 2e2e 0000 0000 0000 0208 0000 ................

0000032: 7c00 0400 0100 0000 3295 6541 0400 0000 |.......2.eA....

0000048: 88d5 fa92 0200 0000 86e7 50be 0300 0000 ..........P.....

0000064: 3738 3930 2e31 3233 3400 0000 1200 0000 7890.1234.......

In this output, bytes 0 to 9 are for the '.' directory entry, and bytes 12 to 23 are for the '..' entry. Notice that the record length field of the '..' entry in bytes 16 to 17 is 1,012 bytes (0x03f4). That points to the end of the 1,024-byte block.

The hash index header starts at byte 24, and the first four bytes are unused. Byte 28 shows us that hash version 2 is being used, and byte 29 shows us that the structure is eight bytes long. The first node descriptor is in bytes 32 to 39. Bytes 32 to 33 show that it can have 124 (0x7c) descriptors in the block, but bytes 34 to 35 show that only 4 are used. Bytes 36 to 39 show that block 1 of the directory contains the first node.

The second node descriptor starts in byte 40. We see that this node contains files with a file name hash greater than 0x41659532, and the names are located in block 4 of the directory. To find the upper bound of the hashes in this node, we look at the entry for the next node, which starts in byte 48, and see that its hash value is 0x92fad588. The entry for the fourth node starts in byte 63.

Part I: Foundations

Digital Investigation Foundations

Computer Foundations

Hard Disk Data Acquisition

Part II: Volume Analysis

Volume Analysis

PC-based Partitions

Server-based Partitions

Multiple Disk Volumes

Part III: File System Analysis

File System Analysis

FAT Concepts and Analysis

FAT Data Structures

NTFS Concepts

NTFS Analysis

NTFS Data Structures

Ext2 and Ext3 Concepts and Analysis

Ext2 and Ext3 Data Structures

UFS1 and UFS2 Concepts and Analysis

UFS1 and UFS2 Data Structures




show all menu

File System Forensic Analysis
File System Forensic Analysis
ISBN: 0321268172
EAN: 2147483647
Year: 2006
Pages: 184
Authors: Brian Carrier
Similar book on Amazon

Flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net