Android Pin/Password Cracking: Halloween isn't the Only Scary Thing in October

CCL Forensics did the mobile forensics world a great service when it released several python scripts for cracking Android gesture, pin, and password locks. I have mostly encountered gesture locks in my examinations, and I have successfully cracked them each time with CCL’s Tools. But recently, I had a chance to take a look at the pin/password cracking tool.

A colleague contacted me and said he’d been running the CCL BruteForceAndroidPin.py tool for more than two weeks but had not cracked a password. I was pretty naive when I thought, "That’s ridiculous, you must be doing something wrong," but I’m glad I had the thought none the less. I’m glad because the thought made me investigate. And the investigation led to some pretty surprising facts and an improvement in the brute force attack.

---

What’s In an Android Password?

First, let’s look at what an Android password can look like: * 4-16 Characters long * 94 possible characters per space: Uppercase and lowercase letters, digits, and punctuation (known as keyspace) * Spaces are not allowed * Alphanumeric passwords MUST have at least one letter * The password is salted with a random integer and stored in a text file as a concatenated SHA-1 and MD5 value while the salt is stored in a SQLite Database.

So, how many password possibilites are there in a 4-16 character length password where each place value can be anyone of 94 characters? I mean, what exactly are we asking our cpu’s to do here? The table below provides the answer.

Table 1. Android Password Possibilities

Length	Number of Possibilities
4	78,074,896
5	7,339,040,224
6	689,869,781,056
7	64,847,759,419,264
8	6,095,689,385,410,816
9	572,994,802,228,616,704
10	53,861,511,409,489,970,176
11	5,062,982,072,492,057,196,544
12	475,920,314,814,253,376,475,136
13	44,736,509,592,539,817,388,662,784
14	4,205,231,901,698,742,834,534,301,696
15	395,291,798,759,681,826,446,224,359,424
16	37,157,429,083,410,091,685,945,089,785,856

The figures in each row in the table are independent of the other rows

Yes, the chart above totals over 37.5 trillion quadrillion possibilities! And totaling the columns—which is the true effect of searching all 4-16 length password combinations, by the way—is a whopping 3.7557e+31!

It can be difficult to understand what large numbers mean. So, lets assume a worst case scenario: a password of length of 16 characters. Since we can’t know the password length from examining the hash values, we have to start our attack at a length of 4. Now, Assuming we have a reasonably good processor, we can make about 200,000 password attempts a second with the CCL brute force script. That means it will take us about 1.87784856658094e+26 seconds to complete the task. There are 86400 seconds in a day, and 365 days in a year (yes, I know you knew that one). So, that’s a mere: 5,954,618,742,329,212,000 years! Let me try to say that in English, "That’s 5.9 quintilian years!"

"Alright," you say, "I understand that I’ve no hope of cracking a password of 16 characters in length. But, how long of a password can I reasonably expect to crack with this script?" Not too many, I’m afraid. Let’s continue to assume 94 characters are possible per place value, and we can generate and test passwords at a rate of 200,000 per second.

Table 2. Time to Complete, 200K/sec

Length	Number of Possibilities	Time to complete
4	7.80749e+07	6 minutes
5	7.33904e+09	10 hours
6	6.8987e+11	39 days
7	6.48478e+13	1 decades
8	6.09569e+15	96 decades
9	5.72995e+17	90 millennia
10	5.38615e+19	8,539 millennia
11	5.06298e+21	802,730 millennia
12	4.7592e+23	75,456,670 millennia
13	4.47365e+25	7,092,927,066 millennia
14	4.20523e+27	666,735,144,231 millennia
15	3.95292e+29	62,673,103,557,788 millennia
16	3.71574e+31	5,891,271,734,432,093 millennia

The figures in each row in the table are independent of the other rows

The stats above don’t really offer much hope if the password has a length of seven or more. But, since this is simple math, it becomes readily apparent how to speed our results: reduce the keyspace, or speed the number of calculations per second. Better yet, do both!

==Reducing the Keyspace

The CCL brute force tool, as written, includes 95 ASCII characters. One of these, the space character, is illegal in Android passwords, so, we can edit the CHAR_LIST variable a the start of the code to 94 characters. But if we consider what characters are visible on the default android keyboard at the lock screen, we see that there are 26 lowercase letters and 5 characters of punctuation accessible with a single, regular key press. Human nature suggests that most passwords would be composed of these keys alone, and since words are easiest to remember, probably the 26 lowercase letters would suffice.

So, what happens if we reduce the CHAR_LIST variable to just lower case letters, thus reducing our keyspace to 26, but are still calculating at a rate of 200K/sec? Let’s take a look:

Table 3. Time to Complete, keyspace = 26, 200k/sec

Length	Number of Possibilities	Time to complete
4	456976	2 seconds
5	1.18814e+07	59 seconds
6	3.08916e+08	25 minutes
7	8.03181e+09	11 hours
8	2.08827e+11	12 days
9	5.4295e+12	314 days
10	1.41167e+14	2 decades
11	3.67034e+15	58 decades
12	9.5429e+16	15 millennia
13	2.48115e+18	393 millennia
14	6.451e+19	102,278 millennia
15	1.67726e+21	265,927 millennia
16	4.36087e+22	6,914,120 millennia

The figures in each row in the table are independent of the other rows

Hey, now we’re cooking! Unless the password is 9 or more characters, we have some hope of cracking it. And since most Android devices are smart phones, users are probably not creating ultra-long passwords because they want quick access to their devices.

This modification to the CCL script might be sufficient for most attacks. And, we can improve the script by making different keyspaces selectable through options, such as -l for lower case, -u for upper case, -d for digits, and -s for special characters (punctuation, etc.). In fact, I went to the effort to do just that, but before you get too excited and ask me to send the modified tool to you, please read on.

Obviously, a keyspace of only lowercase letters will fail to crack a password that includes any characters not included that keyspace, and you won’t know definitively if it does or does not for 6.9 billion years! We need to do more than just reduce the keyspace, we need to increase the calculation rate, too!

---

Increasing the Calculation Rate

I hope you realize from the previous section that an intelligent approach to the keyspace can significantly improve your search times… to a point. But if we are going to make real progress on password cracking, we are going to need to thank CCL Forensics mightily for their contribution, but politely move on to other tools. Python simply isn’t the best platform for this type of process.

On the other hand, OCL is apparently an excellent language for this type of processing, and the specialized Graphical Processing Unit is more adept and this kind of calculation than the more generally capable CPU. And it just so happens that the hashcat tool uses both.

CPU Version

Hashcat comes in several flavors. The original hashcat is coded to use the cpu for password cracking, and unlike the CCL tool, can use multiple cores. As and example of what the OCL programming language and multi-core processing can do for you, I achieved 25 million/sec on my core i5 processor with hashcat compared to 200k/sec with python script. Let’s see what that does for our processing times, and couple that with the lower-case letters keyspace we used previously:

Table 4. Time to Complete, keyspace=26, 25M/sec

Length	Number of Possibilities	Time to complete
4	456976	0 seconds
5	1.18814e+07	0 seconds
6	3.08916e+08	12 seconds
7	8.03181e+09	5 minutes
8	2.08827e+11	2 hours
9	5.4295e+12	2 days
10	1.41167e+14	65 days
11	3.67034e+15	4 years
12	9.5429e+16	12 decades
13	2.48115e+18	3 millennia
14	6.451e+19	81 millennia
15	1.67726e+21	2,127 millennia
16	4.36087e+22	55,312 millennia

The figures in each row in the table are independent of the other rows

Wow! Cracking passwords of 9 characters just became reasonable (recall that initially, 6 character-length password took us about 40 days). With a little luck, we’ll be examining the device’s contents in a fairly short time. And we didn’t spend a dime to improve our systems, we just found a tool that is more adept at the task.

GPU Version

But, I mentioned GPU, right? Hashcat has two other versions, called oclHashcat-plus and ocl-Hashcat-lite, both of which are coded to run on Nvidia and ATI GPUs (currently, you must select the right tool for the processor type, but a future version is planned with multi-processor support). Because the GPU is better suited for this type of calculation, the GPU versions of hashcat are preferred.

As it turns out, I have an inexpensive but supported NVidia GeForce 9500 graphics card. I spent $50 on it about three years ago. This is not a high-end card by any stretch (1023MB, 1375Mhz). This is a good place to mention that while NVidia graphics cards are generally thought to perform better rendering 3D graphics, the ATI cards are better for password cracking.

I used the cudaHashcat-lite version of the tool. CUDA refers to NVidia’s parallel processing platform. I achieved a significant performance increase over my quad-core Intel processor, reaching 35 million calculations/sec. This had a significant effect on my cracking times:

Table 5. Time to Complete, keyspace=26, 35M/sec

Length	Number of Possibilities	Time to complete
4	456976	0 seconds
5	1.18814e+07	0 seconds
6	3.08916e+08	8 seconds
7	8.03181e+09	3 minutes
8	2.08827e+11	1 hours
9	5.4295e+12	1 days
10	1.41167e+14	46 days
11	3.67034e+15	3 years
12	9.5429e+16	8 decades
13	2.48115e+18	2 millennia
14	6.451e+19	58 millennia
15	1.67726e+21	1,519 millennia
16	4.36087e+22	39,509 millennia

The figures in each row in the table are independent of the other rows

We cut our 9 character length processing time in half and put 10 characters in reach. That’s not bad for an low end graphics card, and it was substantially less expensive than the quad-core processor I purchased at the same time.

---

Fine Tuning the Attack

Other than getting a better graphics cards or more of them (yes, hashcat can make parallel use of up to 128 GPUs!), you might think we’re done with this topic. But I had one more idea that I thought worth checking. The password.key file contains two abutting hash values, a 40 byte SHA-1 hash and a 32 byte MD5 hash. The CCL brute force attack is on the SHA-1 value, but what if we targeted the MD5 value? It can’t make that much difference, right?

Wrong! It makes a three-fold difference for the better! Utilizing the MD5 hash and settings.db salt value, I achieved 107 million calculations/sec with the same GPU as before! (Yes, I know that was three exclamations in a row, but darn it, it deserves three exclamations! Ok, that’s four…) The effect on our calculation times is dramatic:

Table 6. Time to Complete, keyspace=26, 107M/sec

Length	Number of Possibilities	Time to complete
4	456976	0 seconds
5	1.18814e+07	0 seconds
6	3.08916e+08	2 seconds
7	8.03181e+09	1 minutes
8	2.08827e+11	32 minutes
9	5.4295e+12	14 hours
10	1.41167e+14	15 days
11	3.67034e+15	1 years
12	9.5429e+16	2 decades
13	2.48115e+18	73 decades
14	6.451e+19	19 millennia
15	1.67726e+21	497 millennia
16	4.36087e+22	12,923 millennia

The figures in each row in the table are independent of the other rows

We’re cracking 8 character passwords in half and hour! What if we bought one of those fancy $400 ATI 4790 cards that they brag about on the hashcat forums, you know, the ones that calculate at a rate of 9 billion a second?

Table 7. Time to Complete, keyspace=26, 9B/sec

Length	Number of Possibilities	Time to complete
4	456976	0 seconds
5	1.18814e+07	0 seconds
6	3.08916e+08	0 seconds
7	8.03181e+09	0 seconds
8	2.08827e+11	23 seconds
9	5.4295e+12	10 minutes
10	1.41167e+14	4 hours
11	3.67034e+15	4 days
12	9.5429e+16	122 days
13	2.48115e+18	8 years
14	6.451e+19	22 decades
15	1.67726e+21	5 millennia
16	4.36087e+22	153 millennia

The figures in each row in the table are independent of the other rows

And what of those (apparently wealthy) guys who are stringing 8 of those cards together and getting speeds of 72 billion calculations/sec?

Table 8. Time to Complete, keyspace=26, 72B/sec

Length	Number of Possibilities	Time to complete
4	456976	0 seconds
5	1.18814e+07	0 seconds
6	3.08916e+08	0 seconds
7	8.03181e+09	0 seconds
8	2.08827e+11	2 seconds
9	5.4295e+12	1 minutes
10	1.41167e+14	32 minutes
11	3.67034e+15	14 hours
12	9.5429e+16	15 days
13	2.48115e+18	1 years
14	6.451e+19	2 decades
15	1.67726e+21	73 decades
16	4.36087e+22	19 millennia

The figures in each row in the table are independent of the other rows

And what if we’re a three-letter agency that could maximize hashcat with 128 GPUs? …Alright, alright, I’ll stop. But I actually posted those last two tables for a reason. Notice that 8 high-end cards only put one more password level within realistic reach. Most of us, if properly motivated and only modestly funded, could manage one of those cards and achieve impressive results. But do the math before you drop nearly $4000 on graphics cards, and consider waiting for the next version of hashcat to put your collection of older cards to work for you.

---

A HashCat Tip

You won’t find a lot of helpful documentation on using hashcat, unless you already understand cryptography and cryptographic principals, that is. In order to use the salt with hashcat, you need to convert it from an integer to hexadecimal notation. In python3, this can be accomplished as follows:

>>> import binascii, struct >>> binascii.hexlify(struct.pack('>q', salt )) #where 'salt' is an integer

There is quite a bit more to know about hashcat, including password masks and keyspace definitions, but I’ll cover that in a future post. If you decide to give hashcat a whirl before I blog any further, make sure you test on known data: I had to roll back a version to get cudaHashcat-lite and cudaHashcat-plus to work properly.