In a previous blog post we described a method to retrieve an Android pattern lock from the raw flash of a device. However, since version 2.2 (known as “Froyo”) Android has provided the option of a more traditional numeric PIN or alphanumeric password (both are required to be 4 to 16 digits or characters in length) as an alternative security measure.
The very act of writing the last blog got us thinking whether it was possible to use a similar approach to recovering the PINs and passwords.
Our first port of call was to return to the Android source code to confirm how the data was being stored (see listing 1). Both the numeric PIN and alphanumeric passwords were found to be processed by the same methods in the same way, both arriving as a text string containing the PIN or password.
As with the pattern lock the code is sensibly not stored in the plain, instead being hashed before it is stored. The hashed data (both SHA-1 and MD5 hash this time) are stored as an ASCII string in a file named password.key which can be found in the same location on the file system as our old friend gesture.key, in the /data/system folder.
However, unlike the pattern lock, the data is salted before being stored. This makes a dictionary attack unfeasible – but if we can reliably recover the salt it would still be possible to attempt a brute force attack.
/*
* Generate a hash for the given password. To avoid brute force attacks, we use a salted hash.
* Not the most secure, but it is at least a second level of protection. First level is that
* the file is in a location only readable by the system process.
* @param password the gesture pattern.
* @return the hash of the pattern in a byte array.
*/
public byte[] passwordToHash(String password) {
if (password == null) {
return null;
}
String algo = null;
byte[] hashed = null;
try {
byte[] saltedPassword = (password + getSalt()).getBytes();
byte[] sha1 = MessageDigest.getInstance(algo = "SHA-1").digest(saltedPassword);
byte[] md5 = MessageDigest.getInstance(algo = "MD5").digest(saltedPassword);
hashed = (toHex(sha1) + toHex(md5)).getBytes();
} catch (NoSuchAlgorithmException e) {
Log.w(TAG, "Failed to encode string because of missing algorithm: " + algo);
}
return hashed;
Listing 1
Source: com/android/internal/widget/LockPatternUtils.java.
The salt which is added to the data before hashing is a string of the hexadecimal representation of a random 64-bit integer. Necessarily, this number must then be stored, and the source code showed that the Android.Settings.Secure content provider was being used to store the value under the lockscreen.password_salt key.
On the Android file system the backing store for this content provider is found in an SQLite database settings.db in the /data/data/com.android.providers.settings/databases directory (see fig. 1).
Fig 1: Salt as stored in the settings.db SQLite database
Once we knew how these two essential pieces of data were being stored we were able to consider how they might be recovered from a raw flash dump. In the case of the hashes, our approach was similar to the pattern lock. Knowing that:
- The dump was broken into chunks of 2048 bytes (2032 for storing the data, the remaining 16 used for YAFFS2 file system tags)
- The passcword.key file contains two hashes encoded as an ASCII string: an SHA-1 hash (40 hexadecimal digits long) followed by a MD5 hash (32 hexadecimal digits long) which would make the file 72 bytes long in total starting at the top of the chunk
- The hashes only contain the characters 0-9 and A-F
- The remaining 1960 bytes in the data portion of the chunk will be zero bytes
Recovering the salt required a little extra thought. The salt is stored in an SQLite database which, because of the structure of SQLite data, meant that it would be all-but-impossible to predict where in the chunk the data might be stored. Worse still, we couldn’t even be sure of the length of the data as it was stored as a string. However, having a deeper understanding of the SQLite file format allowed us to derive a lightweight and reliable way to recover the salt.
Fig 2: Raw data making up the Salt field in the settings.db database
Figure 2 shows the raw data for the salt record in the settings.db. An SQLite record is made up of two parts, a record header and the record data. The record header is made up of a sequence of values; the first value gives the length of the record header in bytes (including this value), the following values (serial type codes in SQLite parlance) define the data types which follow in the record data.
In our case our serial type codes represent two data types: a null and two strings. The null is unimaginatively represented by the zero-byte highlighted by the red box (if you take a look at Figure 1 you may notice that the first field is displayed as a numeric value 34; this column is defined in the schema as the type INTEGER PRIMARY KEY which means that the value is not actually stored in the record itself, hence being replaced by null. The reasons for this are out of the scope of this blog post, but if you’re particularly interested Alex is more than happy to explain, at length, another time!).
The other two values (highlighted by yellow and green boxes respectively) define strings; in serial type codes a string is represented by a value larger than thirteen, the length of the string can be found by applying the following formula where x is the value of the serial type code:
(x – 13)/2
We can test this by considering the second field: we know that this field will always contain the string: “lockscreen.password_salt” which is 24 characters (and bytes) long. The serial type code associated with this data is the value highlighted with the yellow box: 0x3D which is 61 in decimal. Applying the formula: 61 – 13 gives us 48, divided by 2 gives us 24 which is the length of our string.
The field containing the salt is also a string, but its length can vary depending on the value held. We know from the source code that it is a 64 bit integer being stored which gives us a range of -9223372036854775808 to 9223372036854775808 which, allowing for the negative sign means that the value, stored as a string, takes between 1 and 20 characters. Reversing the formula, the second field’s serial type code must be odd and fall between 15 and 53 (0x0F and 0×35).
Using this information we can create a set of rules which should allow us to search for this record in the raw dump so that we can extract the salt:
- Starting with the record header:
- First field is always null (and therefore a zero byte)
- The next field is always a string of length 24 (serial type code 0x3D)
- The third field is always a string with length 1-20 (odd serial type codes 0x0F-0×35)
- Moving on to the record data:
- The first null field doesn’t feature – it’s implicit in the record header
- The first field to actually appear will always be the string: ”lockscreen.password_salt”
- The next field will be a string of a positive or negative integer.
This allows us to define a regular expression that should reliably capture this record:
\x00\x3d[\x0f\x11\x13\x15\x17\x19\x1b\x1d\x1f\x21\x23\x25\x27\x29\x2b\x2d\x2f\x31\x33\x35]lockscreen.password_salt-?\d{1,19}
Understanding the record structure also means that once we have captured the record we can ensure that we extract the whole salt value; we can simply read the appropriate serial type code and apply the formula to get the length of the salt’s string.
Satisfied that we could reliably extract the data we needed to recover the PINs or passcodes we crafted a couple of Python scripts – one to find and extract the data in the flash dump, and the other to brute force the hashes recovered (using the salt). On our test handset (an Xperia X10i running Android 2.3) we set a number of PINs and passcodes and found that even on a fairly modest workstation (Python’s hashing modules are gratifyingly efficient) PINs of up to 10 digits could be recovered within a few hours.
The passwords obviously have a much larger key-space so took longer, but the attack still seems feasible for shorter passwords and the script can easily be modified to only use Latin characters and digits rather than any other special characters or work from a password dictionary which could expedite the process.
Fig 3: Running the BruteForceAndroidPin script standalone
Once again we are happy to be releasing the scripts so that other practitioners can make use of this method. The scripts can be downloaded here: http://ccl-forensics.com/view_category/8_other-software-and-scripts.html.
Alex Caithness and Arun Prasannan of the R&D team
