Wednesday, October 31, 2012

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

Note 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

Note 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

Note 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

Note 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

Note 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

Note 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

Note 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

Note 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.