Cracking Android Passwords: The Need for Speed

Impossibly Large Numbers Revisited

In October, 2012 I posted about a article about cracking Android passwords. I spoke primarily on the difficulty in cracking the passwords based on the sheer number of possibilities (a whopping 37,556,971,331,618,802,349,234,821,094,576!)

Don’t believe me? Let’s to a little rehashing: The key space (range of possible ASCII characters) for each position in the password is 94 (upper and lower case letters, digits, and extended characters), or hexadecimal range \x21-\x7F. The password can be a minimum length of 4 and a maximum of 16 characters long.

A little Python 3 math

>>> total = 0
>>> for i in range(4,17):
...     total = total + 94**i
...
>>> print(total)
37556971331618802349234821094576
>>> #python will even put in the commas!
>>> print('{:,}'.format(total))
37,556,971,331,618,802,349,234,821,094,576

And voilà, we have 37.6 trillion-quadrillion possibilities! (Just rolls off the tongue, doesn’t it?) I spoke then that while the CCL Forensics python script was a great tool, python was not the best choice for password cracking because its relatively slow for that purpose. I introduced hashcat, a cross-platform password recovery application, as a better way to do business.

Hashcat-lite: Harness Feline Speed

Hashcat is coded with performance in mind and can use multi-core CPUs and GPUs (Nvidia and AMD) to perform the calculations. The CPU version, hashcat is remarkably faster than the CCL python script, and the GPU verson,oclHashcat-plus leaves the CPU version in the dust!

Using hashcat for cracking Android passwords can be a bit confusing, however, and I hope to deobfuscate the process here.

Spicy Passwords

Android uses a salted password and stores the password as a hash in the /data/system/password.key file. Well, two hashes, actually. A SHA-1 hash is calculated followed by an MD5 hash, and the values are concatenated into a single 72 byte string.

The salt, in this case a randomly generated signed, 64-bit integer, randomizes the hash and makes dictionary and brute force attacks ineffective. The integer is stored in the settings.db located in the /data/data/com.android.providers.settings/databases directory. The integer is converted a hexadecimal string (8 bytes in length) and is appended to the password. The password + salt string is then hashed and stored.

The CrackStation website has an excellent treatise on salted password hashing if you are looking for a more in-depth explanation. The Android salted password formate is not the only salted password hashing method in practice.

Creating Test Data

We can use python to create some salted hashes after the manner of Android. This is useful for testing hashcat or other tools you might use. After all, if you don’t first test, a failed crack attempt leaves you wondering if the tool failed or if you failed to use the tool properly. To create an Android style password hash, we need a 4-16 character length ASCII character

First, let’s pick a password. We’ll keep it fairly short to allow it to be cracked in a reasonable amount of time: "secret". Keeping it lower case allows us to attack it with a 26 character key space—after all, we’re about cracking the password here, not generating secure passwords!

BASH

$ password="secret"
$

Next, we need to generate a random salt integer (we could just make something up here, but we’ll use python to randomly generate a salt to keep the exercise more realistic). The maximum size of a 64-bit integer is 9,223,372,036,854,775,807. It is signed, meaning it can be positive or negative. Yes, mathematicians, that’s the definition of an integer: a positive or negative whole number including zero. But knowing its signed is important for the hexadecimal conversion in Python or other programming languages. To keep the exercise simple, however, we’ll stay in bash and generate a random number (we’re fudging a bit in generating the random number, but it works for our purposes)/

BASH

$ password="secret"
$ salt=$(($RANDOM**4))
$ echo $salt
15606337825758241
$

Note

Extracting the salt from settings.db Recall that in an Android device, the salt would be stored in the /data/data/com.android.providers.settings/databases/settings.db in the "secure" table. The table salt can be obtained as follows: BASH $ sqlite3 settings.db 'SELECT value FROM secure WHERE \ name = "lockscreen.password_salt";' 15606337825758241 $

On the BASH command line, we can convert the salt to a 8-byte hex string with the built-in function printf. The function formats and prints the a string, in this case we’ll be using the salt, according to a format string. Below, we tell print f to convert the string held in the variable $salt to hexadecimal, padding it with leading zeros if necessary until the output string is 16 characters long.

BASH

$ password="secret"
$ salt=$(($RANDOM**4))
$ echo $salt
15606337825758241
$

Now, we generate a hash by concatenating the password and hexadecimal salt into a string and hashing it. We’ll use the MD5 algorithm because it is faster to crack than SHA-1 (recall the password.key file contains both hashes). We pass the -n option to echo to prevent it from appending the output with a line feed as this would change our MD5 hash.

BASH

$ password="secret"
$ salt=$(($RANDOM**4))
$ echo $salt
15606337825758241
$ echo -n $password$salt | md5sum
b6b97079899c5f22d94f27027549cd7d  -

Now we have the salted MD5 hash of the password secret using the salt 15606337825758241!

Note	Extracting the MD5 from password.key We have been generating a salted hash for testing. You’ll need to extract the MD5 from the password.key when working with real data. The following command makes short work of it. BASH $ tail -c32 password.key b6b97079899c5f22d94f27027549cd7d $

Using Hashcat

I’ll be demonstrating the Nvidia version of hashcat. You’ll want to check the help for your version of hashcat, but you’ll find the following demonstration informative.

The basic command for hashcat follows this form: --- hashcat [options] hash [mask] ---

The chief options we are interested in are the hash type (-m) and minimum/maximum password lengths (--pw-min/--pw-max). Reading the help (-h/--help) tells us that for salted MD5 passwords, we us the -m10 option. And since we are using the -m10 option, we need to append the salt to the hash using a colon (:) separator.

Our command and ouput look as follows:

BASH

$ ./cudaHashcat-lite64.bin -m10 --pw-min=4 --pw-max=16 \
b6b97079899c5f22d94f27027549cd7d:15606337825758241
cudaHashcat-lite v0.13 by atom starting...

Password lengths: 4 - 16
Watchdog: Temperature abort trigger set to 90c
Watchdog: Temperature retain trigger set to 80c
Device #1: GeForce 9500 GT, 1023MB, 1375Mhz, 4MCU


b6b97079899c5f22d94f27027549cd7d:15606337825758241:secret

Session.Name...: cudaHashcat-lite
Status.........: Cracked
Hash.Target....: b6b97079899c5f22d94f27027549cd7d:15606337825758241
Hash.Type......: md5($pass.$salt)
Time.Started...: Sat Jan 19 16:49:59 2013 (10 secs)
Time.Estimated.: Sat Jan 19 16:50:39 2013 (26 secs)
Plain.Mask.....: ?1?2?2?2?2?2
Plain.Text.....: ***yd3
Plain.Length...: 6
Progress.......: 1051066368/3748902912 (28.04%)
Speed.GPU.#1...:   102.8M/s
HWMon.GPU.#1...: -1% Util, 45c Temp, 100% Fan

Started: Sat Jan 19 16:49:59 2013
Stopped: Sat Jan 19 16:50:13 2013
$

Wait. Was that 14 seconds? Yes, it was!

Put on a Mask and Speed Your Results

Now, if the password gets very much longer, the exponential increase in the number of password possibilities gets quite large. Hashcat has one more trick up its sleeve (actually, there’s at least one more, but we’ll cover than another time). Hashcat makes use of masks that allow you to narrow the key space. Simply put, you can choose limited character sets to be used in the search, either from a predefined list, or lists your own creation.

The predefined character sets are:

• ?l = abcdefghijklmnopqrstuvwxyz
• ?u = ABCDEFGHIJKLMNOPQRSTUVWXYZ
• ?d = 0123456789
• ?s = !"#$%&'()*+,-./:;<⇒?@[\]^_`{|}~
• ?a = ?l?u?d?s
• ?h = 8 bit characters from 0xc0 - 0xff
• ?D = 8 bit characters from German alphabet
• ?F = 8 bit characters from French alphabet
• ?R = 8 bit characters from Russian alphabet

To limit the password search to passwords containing only lowercase letters, for example, you would pass the command:

$ ./cudaHashcat-lite64.bin -m10 --pw-min=4 --pw-max=16 \
b6b97079899c5f22d94f27027549cd7d:15606337825758241 \
?l?l?l?l?l?l?l?l?l?l?l?l?l?l?l?l

I hope this gets you started using hashcat. It is a very effective tool, and it keeps on improving!

Last updated 2013-01-19 22:11:44 PST