Flag: Tornado! Hurricane!

File Format Reversing - EverQuest II VPK

Tuesday, September 6 2005 17:30.58 CDT
Author: daeken # Views: 64411 Printer Friendly ...

 Introduction

In this article I will cover the basics of reverse-engineering binary file formats, starting with the simple archive format used in the popular game EverQuest II known as VPK. This is the first of many articles I'll be writing on the subject as time goes on. You can find VPK files in any EverQuest II installation, and any will do for the purposes of this article. For the purposes of this article, I will assume the reader has knowledge of programming in C. The architecture being used is x86, and thus, everything is unsigned and little-endian. The tools you will need to follow along with this article are a decent hex editor (I recommend "HexEditor" for Mac OS X) and a copy of Python.

 Diving In

For this article I targeted the file boat_06p_tutorial01.vpk. If you choose to target another file, please note that there may be differences between what you see in the article and what you come across in the file.

The main thing you must understand when working with file formats is the way data is typically stored. The most basic C data-type that you will find in a binary file is a char. A char is stored as a single byte, a short is stored as two bytes, a long or a float is stored as 4 bytes. Since we're dealing with little-endian files, the bytes will be stored in the reverse order to what they would normally be. For instance, given the number 9, if you wanted to store it as a long in little-endian, it would be represented as 4 bytes with the values 0x09, 0x00, 0x00, and 0x00, in that order. Aside from integers, you will often find arrays. Typically these are stored as an integer representing the length of the array and then that many elements. The elements of an array could be anything from a char to a string to a complex data structure, so it can be difficult to figure out where arrays are and how to read their elements.

To start reverse-engineering a file format, you will want to choose at least one sample file. It is often a good idea to pick a number of sample files to be able to look at the similarities and differences between them, but it is not absolutely necessary in most cases. Once you have picked your sample file, you'll need to examine it within a hex editor.

A good first step is to think about how you would store the data if you were designing the file format. In my example, the VPK archive format, my first thought was that the architects would probably store the data in a compressed format. I immediately drew this conclusion due to the fact that I could not see any plain-text data, telling me that the file could be compressed and/or even encrypted. In most cases, developers will not waste time writing their own compression algorithm. What I will usually do is come up with a list of compression methods that are commonly used, royalty-free (nobody likes to spend money when they don't have to) and easy to implement. Since I am using Python, I decided to try zlib first. zlib is a compression library used in many applications as it is easy to work with and fairly efficient.

 Locating Compressed Data

Since we don't know where the compressed data is in the file, it was necessary to write code that would search through the file for anything that can be decompressed with zlib. I start by reading the file into a string. From there, I attempt to decompress data from each byte to the end of the file, which will tell us where the start of a decompressed block is. I wrote the following snippet of code to accomplish this task:

import zlib, sys

def main(args):
    f = file(args[0], 'rb').read()
    size = len(f)

    i = 0
    while i < size:
        try:
            de = zlib.decompress(f[i:])
        except zlib.error:
            i += 1
            continue

        print 'Found a compressed block starting at', i

        i += 1

if __name__=='__main__':
    sys.exit(main(sys.argv[1:]))

And the output:

    Found a compressed block starting at 4
    Found a compressed block starting at 1370
    Found a compressed block starting at 51781
    Found a compressed block starting at 51905
    Found a compressed block starting at 52283
    Found a compressed block starting at 52401

This code takes a filename to search as an argument and will return the location of any zlib-compressed blocks. Immediately when I run this I see many compressed blocks, so it is confirmed that they are using zlib. Now, just having the location of the compressed block doesn't tell you a whole lot. You also need to know the size of the data. To accomplish this I wrote code that upon discovery of a compressed block, will loop through all the data from that point on, looking for the first point where the decompressed data matches the length of the decompressed data from the beginning of the block to the end of the file. This is not fool-proof, but should work well enough. The code is as follows:

import zlib, sys

try:

    import psyco
    psyco.full()
except ImportError:
    pass


def main(args):
    f = file(args[0], 'rb').read()
    size = len(f)

    i = 0
    slen = 0
    while i < size:
        try:
            slen = len(zlib.decompress(f[i:]))
        except zlib.error:
            print i
            i += 1
            continue

        start = i
        while i < size:
            try:
                slen2 = len(zlib.decompress(f[start:i]))
            except zlib.error:
                i += 1
                continue

            if slen == slen2:
                break

            i += 1

        print 'Found:', start, i - start

if __name__=='__main__':
    sys.exit(main(sys.argv[1:]))

Output:

    Found: 4 1362
    Found: 1370 50407
    Found: 51781 120
    Found: 51905 374
    Found: 52283 114
    Found: 52401 145

When I run this code, it gives me some interesting results. It seems that the first compressed block starts 4 bytes into the file and that there are 4 bytes between each compressed block. Looking at the 4 bytes before each block, it seems to be a long integer representing the length of the compressed block. We now have enough information to decompress the data and make use of it. In the following code I make use of the struct module of Python to decode the long.

import zlib, struct, sys

try:
    import psyco
    psyco.full()
except ImportError:
    pass

def main(args):
    fp = file(args[0], 'rb')

    i = 1

    while True:
        data = fp.read(4)
        if len(data) != 4:
            break

        length = struct.unpack('<L', data)[0]
        file('block_%i.dat' % i, 'wb').write(zlib.decompress(fp.read(length)))
        i += 1

if __name__=='__main__':
    sys.exit(main(sys.argv[1:]))

This code will write all of the compressed blocks to files in the current directory called block_#.dat.

Looking at the first block, it appears to start off with a small header, followed by the filename for the block, followed by the data of the file. This matches all of the blocks until the last. It seems to be the filename list used to pull out arbitrary blocks. This seems like a good place to work on next.

Just looking at it with my hex editor, I see 20 bytes, then the first filename, then 12 bytes followed by the second filename, followed by 12 bytes, etc until the end of the block. In the case of the filename block I'm working with, the entire thing is 487 bytes and there are 5 filenames. Since the data before the first filename is 20 bytes and the data before the rest is only 12, this says there's probably an 8-byte header on the actual filename block.

Looking at the first 8 bytes, I see what seems to be 2 long integers. Selecting the first, my hex editor tells me it has a value of 487, which is the total size of the block. Selecting the second, my hex editor tells me it has a value of 5, which is the number of filenames in the block. Fantastic.

Now looking at the first filename and 12-byte header, I notice the filename is 85 bytes long and since it has no null-termination, the length should be stored in the header somewhere. Checking the value of the 4 bytes immediately before the filename gives me 85, so we have our length. But what are the other 8 bytes? The first 4 bytes seem to be a long integer with a value of 0, and the second 4 bytes seem to be a long integer with the value 1362 (0x0552 hex). This is not immediately obvious as to what it does, so I look at the next file's header. Yet again the filename length is the last 4 bytes of the header. Looking again at the 2 unknown longs, in this case the first is 1366 and the second is 50407. If you look at the difference between the second long in the first filename header and the first long in the second filename header, they differ by 4 bytes. Earlier we found that the header on compressed blocks is 4 bytes, and seeing that the first filename header's first long is 0, it seems likely that these integers represent the starting position and length of the compressed blocks. Looking back at the output of the earlier script, it's confirmed. We now know the filename block format.

Now we have to look at the previous blocks. Looking at the first one, I see an 8-byte header followed by the filename. In this case, the filename is 85 bytes long and the file is 2276 bytes long. Looking at the header, I see two long integers. One with a value of 86 and one with a value of 2182. The first looks suspiciously like the length of the filename, but it's 1 byte too long. This is because the filename is null-terminated. When you count the ending null, the filename is 86 bytes, which makes the first integer of the header the filename length. The second is relatively close to the length of the file, but what could be causing this difference? The header, including the filename and null terminator, is 94 bytes long. Subtracting this from the total file length gives 2182, the value of the second long integer.

 Putting It All Together

The file consists of a number of blocks, which are each a long integer followed by a zlib-compressed block of data of the size the integer indicates.

Each block is its own file, with the exception of the last which is a filename block.

The filename block consists of an 8-byte header, made up of a long representing the length of the whole filename block and a long representing the number of files. After this header are the filenames, each with a 12-byte header consisting of a long that represents the beginning of the file's block, a long that represents the length of this block, and a long that represents the length of the filename, followed by the (non-null-terminated) filename itself.

The other blocks consist of an 8-byte header consisting of a long storing the length of the filename (null-terminated) and a long representing the length of the data in the block, followed by the filename and then the data.

So when I write my code, now that everything is figured out, I end up with this:

import zlib, struct, os, sys

try:
    import psyco
    psyco.full()
except ImportError:
    pass

def main(args):
    fp = file(args[0], 'rb')
    data = fp.read(4)

    while len(data) == 4:
        l = struct.unpack('<L', data)[0]
        data2 = fp.read(l)
        data = fp.read(4)

        if len(data) != 4:
            try:
                filenameblock = zlib.decompress(data2)
            except ImportError:
                filenameblock = data2

    fnblocksize, fncount = struct.unpack('<LL', filenameblock[:8])

    filenameblock = filenameblock[8:]

    try:
        os.mkdir(args[1])
    except OSError:
        pass

    for i in range(fncount):
        block_start, block_len, fnlen = struct.unpack('<LLL', filenameblock[:12])
        filename = filenameblock[12:12 + fnlen]

        paths = filename.split('/')[:-1]
        path = args[1]

        for dir in paths:
            path += '/' + dir

            try:
                os.mkdir(path)
            except OSError:
                pass

        print filename
        f = file(args[1] + '/' + filename, 'w')
        fp.seek(block_start + 4)
        d = fp.read(block_len)

        try:
            d = zlib.decompress(d)
        except zlib.error:
            pass

        f.write(d[12 + len(filename):])
        f.close()
        filenameblock = filenameblock[12 + fnlen:]

if __name__=='__main__':
    sys.exit(main(sys.argv[1:]))

 Conclusion

And there we have it. To run this script, use `python <script.py> <filename.vpk> <directory to output to>`.

Hopefully you've found this article useful. I hope to cover more advanced file formats in the future, as well as network protocols.

If you have any questions or comments, please let me know.

Happy Hacking,

Cody Brocious.

Article Comments Write Comment / View Complete Comments

    Username Comment Excerpt Date
wedikes It is interesting article and what about RE any... Thursday, November 7 2013 02:46.26 CST
  Donner2011 This was precisely the answers I��d been search... Wednesday, December 21 2011 04:08.22 CST
klondikemarlen Would the following code do the same thing with... Thursday, September 30 2010 20:12.57 CDT
drew Someone mentioned to me that the 010 editor was... Friday, January 20 2006 08:54.49 CST
drew The ability to highlight a chunk of bytes and q... Thursday, October 13 2005 03:47.55 CDT
rfreeman Two I have used extensively: 1) The CopyAs f... Wednesday, October 12 2005 17:42.19 CDT
  luis Hi hoglund. Personally my favorite feature of H... Monday, October 10 2005 22:51.38 CDT
hoglund What is your favorite feature of HexWorkshop? Monday, October 10 2005 01:12.42 CDT
  0xebfe So basically, generically speaking, you looked ... Tuesday, September 6 2005 19:57.01 CDT
drew For file format RE, my favorite hex editor is H... Tuesday, September 6 2005 18:45.26 CDT

There are 31,310 total registered users.


Recently Created Topics
[help] Unpacking VMP...
Mar/12
Reverse Engineering ...
Jul/06
hi!
Jul/01
let 'IDAPython' impo...
Sep/24
set 'IDAPython' as t...
Sep/24
GuessType return une...
Sep/20
About retrieving the...
Sep/07
How to find specific...
Aug/15
How to get data depe...
Jul/07
Identify RVA data in...
May/06


Recent Forum Posts
Finding the procedur...
rolEYder
Question about debbu...
rolEYder
Identify RVA data in...
sohlow
let 'IDAPython' impo...
sohlow
How to find specific...
hackgreti
Problem with ollydbg
sh3dow
How can I write olly...
sh3dow
New LoadMAP plugin v...
mefisto...
Intel pin in loaded ...
djnemo
OOP_RE tool available?
Bl4ckm4n


Recent Blog Entries
halsten
Mar/14
Breaking IonCUBE VM

oleavr
Oct/24
Anatomy of a code tracer

hasherezade
Sep/24
IAT Patcher - new tool for ...

oleavr
Aug/27
CryptoShark: code tracer ba...

oleavr
Jun/25
Build a debugger in 5 minutes

More ...


Recent Blog Comments
nieo on:
Mar/22
IAT Patcher - new tool for ...

djnemo on:
Nov/17
Kernel debugger vs user mod...

acel on:
Nov/14
Kernel debugger vs user mod...

pedram on:
Dec/21
frida.github.io: scriptable...

capadleman on:
Jun/19
Using NtCreateThreadEx for ...

More ...


Imagery
SoySauce Blueprint
Jun 6, 2008

[+] expand

View Gallery (11) / Submit