Android Pin Password Cracking Halloween isnt 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.
| 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.
| 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:
| 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:
| 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,
