Finding Serial Numbers on Locked iPhones

Apple iDevices have their serial number engraved on the back, right? So why the article? Because it's not true of newer devices like the iPhone 5, 5s, and 5c. Also, original cases can be replaced and serial numbers obliterated through unprotected use or deliberate act. Now I have your attention again, I hope.

Getting the Message

I've written in the past about the libimobiledevice library and it's utilities.  One, which is quite handy for gathering device information is ideviceinfo.  It provides information such as the device description (color), device class (iPhone, iPod, iPad), device name, etc.  When the device is unlocked, you can retrieve the serial number, as well.  Basically, you retrieve the contents of the Info.plist.

But ideviceinfo is not so informative with a locked device.  In fact, it won't show you any output unless you use the -s simple option.  While you can obtain some information, such as the description, class, name, UDID (unique identifier), and Mac address, you can't display the serial number.  But never fear, there is a way...

Linux has a system log that tracks systems events, included the plugging and unplugging of devices. The system log can be dumped the the terminal with the dmesg command.  Run by itself, you dump the entire log and it's quite a lot of information to sift through, though in truth what you want will be found at or near the end of the log.  You can shorten the output to the content you need with

$ dmesg syslog

But an even niftier trick is to set up your system to display the log as it is created and watch the output:

$ tail -f /var/log/syslog

This will display the last 10 lines of the system log and the "follow" it until you cancel with ctrl-c. Now you can hotplug your iDevice and watch the data that the system log records about the device. Unfortunately, you will see that it displays the device UDID and not the serial number in the "SerialNumber" field for a locked iDevice.

Recovering the Serial Number

The serial number is recoverable in Recovery Mode, however.  Pressing and holding the hardware power button brings up the software power off slide button.  Power off the device, and then replug it into your Linux box while holding the hardware home button.  The device will boot into recovery mode.  Now check your syslog with either of the two methods discussed above.  Two serial numbers are displayed in the syslog after the product (iPhone, etc) and manufacturer (Apple) are listed.  The first is the UDID, but the second includes several key:value pairs, one of which is the device serial number (key SRNM).  

When you are done collecting the device data revealed in the syslog, reboot it, if required, by pressing and holding the power button approximately 10 seconds until the recovery screen goes blank.  The device will then reboot into the operating system, probably feeling very ashamed of itself for revealing its secrets so readily.

Identifying Owners of Locked Android Devices

Locked Devices are not Always Secure

I was handed a device I’ve never seen before: A Verizon Ellipsis 7" tablet. The device was suspected to be stolen, but it was password locked with no sd card or sim card installed. USB debugging and mass storage mode were disabled, too, checked by plugging the device into a computer while the device was booted into the normal operating system. What to do now?

I’ve learned through much hands-on experience to put a device through a few checks before I give up hope. Is there a bootloader mode? How about recovery? I’ve been surprised to find full access to devices in recovery mode, left wide open by the phone’s distributor. More often I find limited access, and sometimes none.

With a little online research—the forensic community owes a debt of gratitude the the modder community—I found that the way to put the Ellipsis into recovery mode: Press and hold between the up and down volume button while powering the device (pressing up and down at the same time did not work). I plugged the device into my PC again, ran adb devices and observed that the Ellipsis was running the adb daemon in recovery mode! I dropped into the ADB shell and determined I was the shell user, which meant limited privileges.

Getting the lay of the land in Android

$ adb shell
shell@android:/ $ printenv
_=/system/bin/printenv
LD_LIBRARY_PATH=/vendor/lib:/system/lib
HOSTNAME=android
TERM=vt100
PATH=/sbin:/vendor/bin:/system/sbin:/system/bin:/system/xbin
LOOP_MOUNTPOINT=/mnt/obb
ANDROID_DATA=/data
ANDROID_ROOT=/system
SHELL=/system/bin/sh
MKSH=/system/bin/sh
USER=shell
ANDROID_PROPERTY_WORKSPACE=8,49664
EXTERNAL_STORAGE=/storage/sdcard0
RANDOM=17656
SECONDARY_STORAGE=/storage/sdcard1
HOME=/data
ANDROID_BOOTLOGO=1
PS1=$(precmd)$USER@$HOSTNAME:${PWD:-?} $
shell@android:/ $

The printenv command reveals some other interesting details about the device. For example, I know where the user data is mounted (HOME=/data), where the operating system files are located (ANDROID_ROOT=/system), and where the sdcards are mounted (EXTERNAL_STORAGE=/storage/sdcard0, SECONDARY_STORAGE=/storage/sdcard1). I know the system path, i.e., the location of executable files that can be called from anywhere in the system. I can also see what partitions are mounted:

Mountpoints of Verizon Ellipsis in Recovery Mode

shell@android:/ $ mount
rootfs / rootfs ro,relatime 0 0
tmpfs /dev tmpfs rw,nosuid,relatime,mode=755 0 0
devpts /dev/pts devpts rw,relatime,mode=600 0 0
proc /proc proc rw,relatime 0 0
sysfs /sys sysfs rw,relatime 0 0
none /acct cgroup rw,relatime,cpuacct 0 0
tmpfs /mnt/obb tmpfs rw,relatime,mode=755,gid=1000 0 0
emmc@android /system ext4 ro,noatime,noauto_da_alloc,commit=1,data=ordered 0 0
emmc@usrdata /data ext4 rw,nosuid,nodev,noatime,nodelalloc,noauto_da_alloc,commit=1,data=ordered 0 0
/emmc@cache /cache ext4 rw,nosuid,nodev,noatime,discard,noauto_da_alloc,data=ordered 0 0
/emmc@protect_f /protect_f ext4 rw,nosuid,nodev,noatime,nodelalloc,noauto_da_alloc,commit=1,data=ordered 0 0
/emmc@protect_s /protect_s ext4 rw,nosuid,nodev,noatime,nodelalloc,noauto_da_alloc,commit=1,data=ordered 0 0
/emmc@fat /storage/sdcard0 vfat rw,dirsync,nosuid,nodev,noexec,relatime,uid=1000,gid=1015,fmask=0702,dmask=0702,allow_utime=0020,codepage=cp437,iocharset=iso8859-1,shortname=mixed,utf8,errors=remount-ro 0 0
shell@android:/ $

I see that the /data partition is mounted read/write, but upon exploration, I’ll see there is little I can see or retrieve from there because the shell user does not have sufficient rights. But where can I look to find information about the owner, then? Take a close look at that last entry:

Internal SDCard Mount Point

/emmc@fat /storage/sdcard0 vfat rw,dirsync,nosuid,nodev,noexec,relatime,uid=1000,gid=1015,fmask=0702,dmask=0702,allow_utime=0020,codepage=cp437,iocharset=iso8859-1,shortname=mixed,utf8,errors=remount-ro 0 0
shell@android:/ $ ls -dl storage/sdcard0
d---rwxr-x system   sdcard_rw          1969-12-31 16:00 sdcard0

Members of the sdcard_rw group have read/write/execute privileges in the /storage/sdcard0 directory, and other users can read and execute there. A little more exploration of the root directory, we see that /sdcard is a link to /storage/sdcard0, so we can shortcut our typing a bit.

What remains is figure out who owns this device from the data I can read in the /sdcard mount point. One thing all Androids have in common is that the users register them with Google and create associate the device with a gmail account. I performed a simple search:

Finding the Owner of a Device from SDCard Data

shell@android:/ $ ls -R sdcard/ | grep "\@gmail.com"
...
sdcard//Android/data/com.google.android.apps.books/files/accounts/somebody@gmail.com/volumes/######/res2:
sdcard//Android/data/com.google.android.apps.books/files/accounts/somebody@gmail.com/volumes/######/segments:
...

Note	The email address and path has been altered above to protect privacy. It is offered as an example of what can be expected from such a search.

I found over 230 instances of that email address (modified above for privacy) in the file paths alone, without looking inside any files at all. In fact, I found two accounts. I was able to contact those persons and determine the device was in fact stolen. There are certainly other ways to find user information, and I did in fact find that some of the apps that stored user namest hat corroborated the gmail accounts I found in the file paths.

I’ve known investigators to hear a device description of "Locked with no USB debugging" and declare, "There is nothing that can be done." I hope this quick post demonstrates otherwise. While it is true that some devices are buttoned up pretty tight, I find that the vast majority provide at least some access. Maybe now you’ll be inspired to look a little more closely, too.

---

Last updated 2014-02-19 17:28:28 PST

Making Sense of the Senseless

SQLite to the Rescue

One of the tasks I’m asked to perform is to geolocate mobile phone calls from Call Detail Reports (CDR). These usually arrive from a carrier as spread sheets: one with details of calls to and from a particular number, and one or more cell tower listings. I’ve tried a variety of ways to process these over time such as BASH scripting and python coding. But by far the easiest and most flexible way to process these records is by importing them into a SQLite database.

The long term difficulty in processing CDRs is that they change over time. It seems that every time I get new records to process, the format has changed which breaks previous code. It takes much more effort to recode a script than it does to write a SQL query on the fly, and I’m certainly no SQL guru. SQLite has enough built in functions to handle nearly any problem you might encounter.

Lets take some Sprint records I recently processed as an example. I was tasked with plotting the locations of the voice calls on a map. There were over 3,600 records for a 12 day period with text message details mixed with voice call details. Only the call details contained references to the tower records, however. Call records included five digit integers that represented the first and last cell towers the mobile phone used during the communication. Text messages contained only zeros in these columns.

The challenge was to retrieve the call records for mapping, ignoring the text messages that did not contain cell tower details. SQLite seemed the easiest way to accomplish this in light of the follow up requirement of looking up each cell tower integer in any one of four associated tower record spread sheets.

Creating the Database

The first step was to create a SQLite database. Fortunately, creating a database is a simple, straight forward process. I performed the work using in the SQLite command line program. However, GUI tools like the excellent SQLite Manager can accomplish the same thing and I recommend them if you are new to SQLite as they can be good teachers.

To create a new database, I simply provided the new database name when I opened the command line program. I called my database cdr.sqlite.

Creating a SQLite database

$ sqlite3 cdr.sqlite
SQLite version 3.7.17 2013-05-20 00:56:22
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite>

Next, I needed a table to hold the call records. I made this something easy to type, so I called it simply cdr. The columns I named for the columns found in the spreadsheet sent by Sprint.

SQLite Create Table Statement for the Call Sprint Detail Report

sqlite> CREATE TABLE "cdr"
   ...> (
   ...> "Calling_NBR" TEXT,
   ...> "Called_NBR" TEXT,
   ...> "Dialed_Digits" TEXT,
   ...> "Type" TEXT,
   ...> "Start_Date" TEXT,
   ...> "End_Date" TEXT,
   ...> "Duration" INTEGER,
   ...> "NEID" INTEGER,
   ...> "Repoll" TEXT,
   ...> "First_Cell" INTEGER,
   ...> "Last_Cell" INTEGER,
   ...> );
sqlite>

Note	In the SQLite command line program, all SQL queries must end in a semi-colon or the interpreter assumes you are adding lines to the statement. If you forget to put the semi-colon at the end of your command, you can enter it on the next line.

To import the CDR data from the spreadsheet, simply export the data without the header row, in text file with comma separated values (CSV). In this case, I called the file "call_records.csv". I had to tell SQLite how the data was delimited (SQLite uses pipes by default), and import the CSV file into the "cdr" table.

Importing the CDR data into the cdr table

sqlite> .separator ","
sqlite> .import call_records.csv cdr

Note	The "dot" commands are special SQLite functions (use .help to view them all) and do not require a semi-colon.

To import the cell tower details, I followed the same process: I created a table I called "towers" using the column headers from the spreadsheet as the column names of the table. Then I exported the cell tower data from each spreadseet to a CSV file and imported the CSVs into the tower table. While I won’t repeat the full process, I will display the table layout (schema) below.

Towers table schema

sqlite> .schema towers
CREATE TABLE "towers" (
    "Cell" INTEGER,
    "Cascade" TEXT,
    "Switch" TEXT,
    "NEID" INTEGER,
    "Repoll" INTEGER,
    "Site_Name" TEXT,
    "Address1" TEXT,
    "Address2" TEXT,
    "City" TEXT,
    "County" TEXT,
    "State" TEXT,
    "Zip" TEXT,
    "Latitude" TEXT,
    "Longitude" TEXT,
    "BTS_Manufacturer" TEXT,
    "Sector" TEXT,
    "Azimuth" TEXT,
    "CDR_Status" TEXT
);
sqlite>

Looking Up Records

Now it was time to lookup the call records in the tower tables to find that latitude and longitude of the tower used to initiate the call an place the mobile device in time and space. I expected it to be straight forward: take the 5-digit tower number from the first_call field of the cdr table, match it to the cell field in the towers table, and return the map coordinates. Easy peasy, right? The SQL equivalent of show me the latitude and longitude of the tower where the CDR first_cell integer matches the Tower cell integer.

First attempt to match call tower numbers to tower coordinates

sqlite> select latitude, longitude from towers, cdr where first_cell = cell;
sqlite> # Ruh roh, raggy, no matches!
sqlite> select first_cell from cdr where first_cell != 0 limit 5;
40385
10962
10962
20962
30392
sqlite> select cell, latitude, longitude from towers;
<redacted>
385|34.046944|-118.448056
385|34.046944|-118.448056
385|34.046944|-118.448056
392|34.063806|-118.30366
392|34.063806|-118.30366
392|34.063806|-118.30366
962|37.657222|-122.094653
962|37.657222|-122.094653
962|37.657222|-122.094653
385|37.838333|-122.298611
385|37.838333|-122.298611
392|37.693|-122.0939
392|37.693|-122.0939
392|37.693|-122.0939
385|37.403633|-121.89436
385|37.403633|-121.89436
385|37.403633|-121.89436
<redacted>
sqlite>

Whoa, the cdr first_cell and towers cell values do not jibe! And, as we can see, there is more than one entry in the tower table for each cell designator. Take cell 385 for example: there are three distinct groupings of tower 385 with three different map coordinates for each group. It turns out that cell towers are grouped by the switch they are part of, recorded in the CDR and tower records as the NEID. The appropriate cell tower record can be further reconciled by the sector number, or side of the tower from which the call originated. The first_cell value is actually a concatenation of the sector and the tower number. How did I figure all this out? The answer came from reading the documentation (RTFM) that came with the records and some analysis of the spreadsheets.

I’ll demonstrate below the values that make a tower record unique and that must be considered when matching call records to tower details. I’ll focus on tower 385

Values that make the tower records unique.

sqlite> .headers on
sqlite> .mode columns
sqlite> select cell, sector, neid, azimuth, latitude, longitude from towers
   ...> where cell = 385;
Cell        Sector      NEID        Azimuth     Latitude    Longitude
----------  ----------  ----------  ----------  ----------  -----------
385         1           65          60          34.046944   -118.448056
385         2           65          200         34.046944   -118.448056
385         3           65          290         34.046944   -118.448056
385         1           512         55          37.838333   -122.298611
385         2           512         155         37.838333   -122.298611
385         1           95          0           37.403633   -121.89436
385         2           95          110         37.403633   -121.89436
385         3           95          190         37.403633   -121.89436
sqlite>

Now it is easy to see that the three different groupings of tower 385 are a result of that tower designator being used in three different switches, or NEIDs. Further, each tower can be resolved to a sector, which corresponds to a unique asimuth or direction the cell tower antenna points.

SQLite Substrings

The remaining problem in querying this data is the configuration of the first_cell value in the call details. Recall that it is the sector concatentated to the tower number. I needed a way to take the first digit from the integer and assign it to a sector value, and use the remaining four digits as the tower designator. Fortunately, SQLite has a built-in substring function to make this easy.

substr(X,Y,Z), substr(X,Y)

The substr(X,Y,Z) function returns a substring of input string X that begins with the Y-th character and which is Z characters long. If Z is omitted then substr(X,Y) returns all characters through the end of the string X beginning with the Y-th. The left-most character of X is number 1. If Y is negative then the first character of the substring is found by counting from the right rather than the left. If Z is negative then the abs(Z) characters preceding the Y-th character are returned. If X is a string then characters indices refer to actual UTF-8 characters. If X is a BLOB then the indices refer to bytes.

http://www.sqlite.org/lang_corefunc.html
— SQLite

From the SQLite documentation, we see that the substr function takes 2-3 arguments and returns a substring of the of the input string based according to those documents. To return the sector, I needed to take the first digit from the first_cell string in this manner: substr(first_cell, 1, 1). To return the tower identification, I needed to skip the first digit and return the rest of the string thusly: substr(first_cell, 2).

Note	I did not need to specify the third argument in the second substr() expression because I wanted the entirety of the string past the first digit.

Finally, I needed to include the NEID from the call detail records to ensure I’ve looked up the correct tower. Putting it all together, we can see how to created the values we need from the call records to find the matching tower details. I’ve added a second query to demonstrate, using the ltrim() function to strip the leading zeros from the cell column.

Using the SQLite substr() function

sqlite> select substr(first_cell, 1, 1) as sector,
   ...> substr(first_cell, 2) as cell, neid
   ...> from cdr where first_cell != 0 limit 5;
sector      cell        NEID
----------  ----------  ----------
4           0385        95
1           0962        169
1           0962        169
2           0962        169
3           0392        512
sqlite> select substr(first_cell, 1, 1) as sector,
   ...> ltrim(substr(first_cell, 2), 0) as cell, neid
   ...> from cdr where first_cell != 0 limit 5;
sector      cell        NEID
----------  ----------  ----------
4           385         95
1           962         169
1           962         169
2           962         169
3           392         512
sqlite>

Putting it All Together

As usual, the explanation is more step intensive that the actual work. The whole process can be done in one query, but I wanted to break it down so that it would be easier to recognize the elements of the query. To make it more legible, I’ll write it across several lines.

Matching the CDR call record to the correct tower details

sqlite> select start_date as Date, calling_nbr as Number, latitude, longitude
   ...> from cdr, towers
   ...> where substr(first_cell, 1, 1) = towers.sector and
   ...> ltrim(substr(first_cell, 2), 0) = cell and
   ...> cdr.neid = towers.neid limit 5;
Date                 Number      Latitude    Longitude
-------------------  ----------  ----------  -----------
2012-12-10 07:36:39  ##########  37.657222   -122.094653
2012-12-10 08:24:21  ##########  37.657222   -122.094653
2012-12-10 08:26:09  ##########  37.657222   -122.094653
2012-12-10 09:59:40  ##########  37.693      -122.0939
2012-12-10 10:00:26  ##########  37.705128   -122.047417
sqlite>

This can be converted to a CSV file suitable for mapping through a website like gpsvisualizer.com[GPS Visualizer] or a program like GPSBabel. First, I change the output mode to CSV and I change the columns names to comply with the mapping software’s requirements, printing a sample to ensure I have the format I am seeking. Then I output the data to a file for import to the mapping program.

Exporting the data for mapping

sqlite> .mode csv
sqlite> select start_date as name, calling_nbr as desc, latitude, longitude
   ...> from cdr, towers
   ...> where substr(first_cell, 1, 1) = towers.sector and
   ...> ltrim(substr(first_cell, 2),0) = cell and
   ...> cdr.neid = towers.neid limit 5;
name,desc,Latitude,Longitude
"2012-12-10 07:36:39",##########,37.657222,-122.094653
"2012-12-10 08:24:21",##########,37.657222,-122.094653
"2012-12-10 08:26:09",##########,37.657222,-122.094653
"2012-12-10 09:59:40",##########,37.693,-122.0939
"2012-12-10 10:00:26",##########,37.705128,-122.047417
sqlite> .output call_map.csv
sqlite> select start_date as name, calling_nbr as desc, latitude, longitude
   ...> from cdr, towers
   ...> where substr(first_cell, 1, 1) = towers.sector and
   ...> ltrim(substr(first_cell, 2),0) = cell and
   ...> cdr.neid = towers.neid;
sqlite>

So, in its simplest form, you can see this is not necessarily a difficult process. It can be distilled into three basic steps:

1. Review the records and determine the relationships between them

2. Import the data into a SQLite database

3. Query the database for the output needed

Though there is commercial mapping software available, the software I’ve seen either lacks flexibility to deal with differences in records or in output. Further they usually require configuration that can take as long or longer than importing the data into SQLite and writing the specific query you need for your investigation. If you have the software and a happy with it, use it. If you find it is lacking the flexibility you need, consider doing the work by hand. You’ll be better for it!

Note

In the interest of full disclosure, the results demonstrated here are over simplified. For the real casework, I interpreted the call direction with a case statement to select the called number or calling number as appropriate. The result was a Google Earth map with waypoints named for the date and time of the call. Clicking the waypoint showed call details, e.g., (To: ()-## for 37 secs, azimuth 270).

---

Last updated 2014-02-17 13:34:39 PST

iPhone: Recovering from Recovery

I was attempting to brute force an iPhone 4 passcode for data recovery. The phone was in poor condition and had undergone modifications: the home button had been replaced as well as the back cover, maybe more. I could not reliably get the phone into recovery mode, possibly the result of a faulty home button, so i used libimobiledevice’s ideviceenterrecovery command.

It worked wonderfully. Maybe too wonderfully. I eventually achieved DFU mode (the home button was probably the culprit in making this normally simple process quite difficult), executed my exploit, and obtained the passcode and data. My goal was to unlock the phone and pass it off to another investigator. But, when I rebooted the phone after DFU mode I found it was in recovery again!

I tried a variety of things, from trying to rest with FirmwareUmbrella (formerly TinyUmbrella) to disassembling the phone and disconnecting the battery, but nothing worked. Then a colleague (thanks, Perry) suggested iRecovery.

What is libirecovery?

libirecovery is a cross-platform library which implements communication to iBoot/iBSS found on Apple’s iOS devices via USB. A command-line utility is also provided.

https://github.com/libimobiledevice/libirecovery
— libirecovery

libirecovery can be compiled in Linux. I found I had to install the libreadline-dev package in my Ubuntu install, but you may find you have to do more depending on the packages you already have installed. Building requires you to execute the autogen.sh followed by make and then make install. I had to also run ldconfig to register the library since this was not done automatically.

The command line utility is the irecovery tool. It is used as follows:

iRecovery - iDevice Recovery Utility
Usage: irecovery [args]
        -i <ecid>       Target specific device by its hexadecimal ECID
        -v              Start irecovery in verbose mode.
        -c <cmd>        Send command to client.
        -f <file>       Send file to client.
        -k [payload]    Send usb exploit to client.
        -h              Show this help.
        -r              Reset client.
        -s              Start interactive shell.
        -e <script>     Executes recovery shell script.

On first blush, it might seem that the solution to my problem was the command irecovery -r to reset the device. But that is not so. Instead, I needed to enter the shell, change and environment variable, and reboot.

iRecovery Shell

$ sudo irecovery -s
> setenv auto-boot true
> saveenv
> reboot

Important

Running the command as root was required or the program failed with a segmentation fault.

The device rebooted into the normal operating system and I was able to unlock it with the passcode I had recovered. If you find yourself in a recovery loop, I hope this post will help you, uh, recover from it!

---

Last updated 2013-09-18 17:03:04 PDT

Recovering Data from Deleted SQLite Records: Redux

Rising from the Ashes

I’ve received many, many inquiries about recovering deleted records from SQLite databases ever since I posted an article about my first attempt to recover deleted data. Well, the hypothesis of checking the difference between the original database and a vacuumed copy seemed sound at the time and did in fact yield dropped record data, but it also included data from allocated records. The main thing I learned was that I had much to learn about the SQLite database file format.

Since that time, I’ve run into more and more SQLite databases, and the issue of recovering dropped records has become paramount. I have learned how to do so, and I’ll share some of the secrets with you now. But first, you need to know a little about SQLite databases…

This article is not a treatise on the SQLite file format. The best resource for that is located at SQLite.org. I hope to put the salient points here so you can understand the complexity of the task of recovering dropped records from SQLite databases.

SQLite Main Database Header

The first 100 bytes of a SQLite database define and describe the database. The key value to record recovery is the page size, a 16-bit (two-bytes) big-endian integer at byte offset 16. SQLite databases are divided into pages, usually matching the underlying file system block size. Each page has a single use, and those containing the records that are the interest of forensic examiners is the table b-tree leaf page, which I’ll refer to as the TLP. The TLP is distinguished from other page types by its first byte, \x0d or integer 13.

Thus, we can find the TLPs with the knowledge of the database page size we obtain from the database header and check the first byte of each page for \x0d. In python, that might look like:

Python 3: Finding table b-tree leaf pages

from struct import unpack

with open('some.db', 'rb') as f:
    data = f.read()

pageSize = unpack('>h', data[16:18])[0]

pageList = []

for offset in range(0, len(data), pageSize):
    if data[offset] == 13;
        pageList.append(offset)

Note	The code above prints the offset of TLPs. Make sure you are using Python 3 if you want to try this for yourself.

Table B-Tree Leaf Pages

The TLPs hold the records, and consequently, the dropped (deleted) records data when they occur. Each page has an 8-byte header, broken down as follows:

Table 1. Table b-tree leaf page header

Offset	Size	Value
0	1	Page byte \x0d (int 13)
1	2	Byte offset to first freeblock
3	2	Number of cells
5	2	Offset to first cell
7	1	Number of freebytes

The header introduces some terms that need explaining. A freeblock is unallocated space in the page below one or more allocated records. It is created by the dropping of a record from the table. It has a four-byte header: the first two bytes are a 16-bit big-endian integer pointing to the next freeblock (zero means its the last freeblock), and the second two bytes are a 16-bit big-endian integer representing the size of the freeblock, including the header.

Cells are the structures that hold the records. The are made up of a payload length, key, and payload. The length and key, also known as the rowid, are variable length integers. What are those? I’m glad you asked:

Variable-length Integers

A variable-length integer or "varint" is a static Huffman encoding of 64-bit twos-complement integers that uses less space for small positive values. A varint is between 1 and 9 bytes in length. The varint consists of either zero or more byte which have the high-order bit set followed by a single byte with the high-order bit clear, or nine bytes, whichever is shorter. The lower seven bits of each of the first eight bytes and all 8 bits of the ninth byte are used to reconstruct the 64-bit twos-complement integer. Varints are big-endian: bits taken from the earlier byte of the varint are the more significant and bits taken from the later bytes.

http://www.sqlite.org/fileformat2.html
— SQLite.org

I won’t go into varints any further in this post, because I will not be discussing cell decoding in this post. Suffice it to say that with the payload length, we can define the payload, which itself is made up of a header and columns. The header is a list of varints, the first describing the header length, and the remainder decribing the column data and types. The page header contains number of cells and the offset to the first cell on the page.

The last value in the header, freebytes, describes the number of fragmented bytes on the page. Fragmented bytes are byte groupings of three or less that cannot be reallocated to a new cell (which takes a minimum of four bytes).

Immediately following the page header is a cell pointer array. It is made up of 16-bit big endian integers equal in length to the number of cells on the page. Thus, if there are 10 cells on the page, the array is 20 bytes long (10 2-btye groupings).

Page Unallocated Space

There are three types of unallocated space in a TLP. Freeblocks and freebytes we’ve discussed, and the third is the space between the end of the cell array and the first cell on the page referred to in the SQLite documentation as simply "unallocated". Freeblocks and unallocated can contain recoverable record data, while freebytes are too small for interpretation. Thus, knowing the first freeblock (defined in the page header), the length of the cell array (interpreted from the number of cells defined in the page header) and the offset to the first cell (yep, you guessed it, defined in the page header), we can recover all the unallocated space in the page for analysis.

Python 3: Finding table b-tree leaf page unallocated space

for offset in pageList:
    page = data[offset: offset + pageSize]

    pageHeader = unpack('>bhhhb', page[:8])
    pageByte, fbOffset, cellQty, cellOffset, freebytes = pageHeader

    # get unallocated
    start = 8 + cellQty * 2
    end = cellOffset-start
    unalloc = page[start:end]
    print(offset, unalloc, sep=',')

    # get freeblocks, if any
    if fbOffset > 0:
        while fbOffset != 0:
            start, size = unpack('>hh', page[fbOffset: fbOffset + 4])
            freeblock = page[fbOffset: fbOffset + size]
            print(offset, freeblock, sep = ',')
            fbOffset = start

With the lines from the two code boxes, we have coaxed the unallocated data from the "some.db" SQLite database. We have printed the offset of each unallocated block and the contents (in python bytes format) to stdout. With just a little manipulation, we can turn this into a script a reuseable program, and the content can be grepped for strings. At bare minimum, we now have a way to determine if there is deleted content in the database related to our investigation, e.g., we could grep the output of the Android mmssms.db for a phone number to see if there are deleted records. Searching against the whole database would not be valuable because we cannot separate the allocated from the unallocated content!

Now, this obviously does not reconstruct the records for us, but recovering the unallocated data is a good start. In future posts I will describe how to reconstruct allocated records with an eye towards reconstructing unallocated records.

---

Last updated 2013-09-13 00:14:30 PDT