Cracking Android PINs and passwords

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 0x35).

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-0x35)
  • 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

Advertisements

47 thoughts on “Cracking Android PINs and passwords

  1. Sorry, I have a problem when running your BruteForce script to crack a password (alpha, alphanumeric). Running the script to crack a pin, it works very well! But only with alpha or alphanumeric I have problems. The script returns Passcode: None . I hope you can help me or solve the problem.

    Jaap

  2. Hi Jaap,

    Firstly, does the script report that it has found hashes and salts? We’ve had issues with a limited number of devices (The Samsung Galaxy Tab springs to mind) where we can’t return any viable hits (possibly a non-standard lockscreen is in use).

    If you are finding hashes and salts, I would also check that all of the characters likely to be involved in the password are present in the CHAR_LIST variable on line 40 of the BruteForceAndroidPin.py script, currently there are only Latin characters without diacritics so if the user was likely to have included characters outside that range then I would amend the string.

    Hope that helps, drop us a line if you need any extra assistance.,
    Alex

  3. Hi Alex,

    After some tries I worked out that the script use the code_generater instead of password_generator, so the result is none because it’s not a number. When I force to use password_generator in the if statement in def main() than it works! So I think that the script makes the wrong decision in choosing between the code_generator and the password_generator, in the if statement in def main(). Finally the result is none: the result from code_generater before. I have no other declaration. I hope you understand me.

    It’s really a great script, thanks!

    Jaap

  4. Ah, I assumed you were using the “RecoverAndoirdPin” script (which calls the functions in BruteForceAndroidPin), my apologies.

    If you’re using the BruteForceAndroidPin script directly to crack Alpha Numeric Passwords you need to run it as:

    BruteForceAndroidPin.py t

    The “t” at the end switches that script into alpha-numeric mode (which I now realise isn’t documented in the usage information; I’ll have that updated).

    Thanks for your support!

  5. Hi Alex,

    Thanks for your brilliant work.

    I run the script ‘RecoverAndroidPin’ but the ‘Hash’ field does not populate.. The ‘salt’ does, therefore there is no argument to run for the ‘BruteForceAndroidPin’.. Device is the HTC Ace or HTC Desire HD.

    Any suggestions..?

    Paolo

  6. Hi Paolo, how did you acquire the image that you’re running the script across? Also, would it be possible to see the output from the script as it might help us diagnose the issue.

    • Hi Alex,

      The image is from a current working phone (was using this to test before anything else). Since the HTC is rooted and has 4EXT Recovery installed, i used this to make a backup/image of the ‘Data’ partition which contains all the .db files. This then makes a ‘data.tar’ file as it’s backup.
      I then extracted, and used winhex to make an image file sector by sector and called it data.img.
      Is it possible that this process is not compatible with the script..? The output is quite long, would you like me to post it here or email it to you perhaps..?
      Thanks..

      • Hi Paolo,

        The script is configured to take into consideration the in-band metadata which is present when you do a straight read of (most) flash chips on Android devices, the way you have acquired the device I suspect you won’t have this metadata. It’s easy to reconfigure the script:

        If you open the script in an editor and find the lines that read:
        CHUNK_SIZE = 2032
        SKIP_SIZE = 16

        and change them so that they read:
        CHUNK_SIZE = 2048
        SKIP_SIZE = 0

        and try the script again – that may well fix the problem. You don’t need to run the Brute Force script separately – the “RecoverAndroidPin” script will do it automatically.

        Alternatively, as you’ve already got the contents of the data partition logically you could simply go and get the hash from the file noted in the post: “data/system/password.key”.

        I hope that helps, let me know how you get on.

        Alex

      • Hi Alex,

        Once again thanks for your assistance. I tried the modified script but that still hasn’t worked. It pretty much repeats the same results. Salt found but hash remains empty. I’m working today on getting a sector by sector image of the entire phones internal memory straight to one file using the UFED. I’ll try once again once it’s finished with both versions of the script to note any changes.

        I also previously found the password.key hash and placed it manually with the BruteForce script, it was running for 2.5days on a decent PC still running but this morning it crashed so had to reboot (thank windows). I’m assuming the length of the current password (13 alphanumeric) is probably to exaggerated for a test run ;).

        Just to make sure the command i issued was :
        RecoverAndroidPin.py -t p Data.img
        and also
        RecoverAndroidPin.py Data.img

        This is correct.?

        Paolo

      • Paolo,

        It sounds like the way you acquired the data messes with the sector alignment then; that’s probably why the search fails.

        13 character alphanumeric is probably a bit much for the script to feasibly do to be honest – Python isn’t compiled so it’s comparatively slow, you could be waiting a long time! I did start to look at offloading some of the processing to GPU (there’s some Python Cuda bindings) or rewriting in another language (turns out C#’s built in hashing algos are SLOW) but other projects had to take priority.

        As we mentioned in the post, we might at some point in the future modify the script to work with a dictionary which would run a lot faster.

        And the command-line syntax looks fine.

        Cheers,

        Alex

      • Alex, I think your def right.. I’ll check once the UFED image has complete it will give a more definitive answer.

        As for the 13 char. Yes i think maybe a few weeks/months will do it. Although the rig i have setup was made mainly for decryption purposes.. with 24GB Triple ch RAM and a HD 7970 GPU -offloading to GPU / accelerating would be a brilliant addition to the script. I’d def. love to see that at some stage.

        Paolo

      • Alex,
        Your script worked flawlessly on an image taken from a Sony Ericsson Xperia x10i – taken using JTAG (RIFF Box). 😉 extracted the 4 digit pin in under 5 seconds.

        Paolo

      • Alex,

        A question.. Have you.. or is there a piece of software or script etc made to decode the .BIN dump from a RIFF box for Android devices..?

        I tried several known methods but nothing has really worked.

        Thanks

        Paolo

    • Decode as in view the file system?

      I know that Revskills have just added YAFFS2 decoding functionality to their new version, although I haven’t had a chance to try it: http://psas.revskills.de/

      If you’re looking to pull records from databases from the raw dump out own tool Epilog has been shown to be very effective: http://www.ccl-forensics.com/epilog Here’s a link to a video where we recover SMS (live and deleted) from a raw dump taken with RIFF box: http://www.youtube.com/watch?v=B_zuysSHx-0&list=UU7ClwfasiS0G03TRDSJltUA&index=6&feature=plcp

  7. Hi,

    I’m currently trying to find out how password hashing is done on a Samsung Galaxy SII.

    Samsung has modified the passwordToHash() function, the resulting password.key file is just 40 bytes instead of 72 as on stock Android.

    It is not just the SHA-1 of password+salt, they have probably added some proprietary stuff.

    Do you have any more information about this?

    • Gerd,

      Thanks for getting in touch. I don’t have any information on that right now, but I’ll see if I can get hold of the source code and work out what they’ve done.

      Is the device in question running Gingerbread? ICS?

      Alex

      • The device is running ICS. But I guess they didn’t change the algo between Gingerbread and ICS because updating works without reentering the password. That would be hard with a hash…

        BTW, I need this for fixing the inconvenient device encryption. You have to use the same password for encrypting the device and on the lock screen. I’m writing a script to change to password for the lock screen and combine that with instant shutoff on unlock failure. Already works on a HTC I borrowed, but my Samsung needs some extra care 😦

      • Gerd, doesn’t look like it’s in their open source downloads. If you have root on the device you could use ADB to pull the relevant compiled code (I’d start looking in system/framework) and use dexdump to decompile it and work out what’s going on.

        If they’ve just altered the standard code it’ll be in “framework.jar” just taken a look at the decompiled code and it’s fairly readable (although I’ve spent hours wading through decompiled dalvik op codes so I might be biased!).

        If you’ve not used dexdump before I’d suggest using it with the “-d” “-f” and “-l plain” switches and pipe it into a text file. Let me know if you need any help.

  8. Hi Alex,

    thanks for your help. I’ve already searched the stuff Samsung released myself and did not find anything. I thought maybe you have some “special sources” to tap onto.

    I haven’t done any dalvik decompiling yet but I guess now is the right time to try it. Thanks for offering help with that, will contact you if I’m stuck.

    Gerd

    • No worries, I’d like to know the answer too!

      If you’re happy “thinking like a programmer” and keep a notepad handy it’s easy enough to read the dumped dex files, if you’ve done any Android App coding in the past, even a “hello world” app it’s worth starting with that so you can get an idea what method calls, stored variables, etc look like. Everything else is just an extension of some fairly simple ideas.

      This is a link to the official documentation which can be helpful if you come across a less friendly named opcode.
      http://developer.android.com/reference/dalvik/bytecode/Opcodes.html

      Good luck!

      • Got it, this a python-equivalent of what Samsung is doing:

        	def saltToHex(self,saltlong):
        		blob=struct.pack(">q",saltlong)
        		longagain=struct.unpack(">Q",blob)[0]
        		hexstr=hex(longagain)
        		hexstr=hexstr.lstrip("0x")
        		hexstr=hexstr.rstrip("L")
        		return hexstr.lower()
        		
        	def hashPinSamsung(self,pin,salt):
        		salted=str(pin)+self.saltToHex(salt)
        		hashbuf=str()
        		i=0
        		while i < 1024:
        			hashbuf=hashlib.sha1(hashbuf+str(i)+salted).digest()
        			i=i+1
        		return binascii.hexlify(hashbuf).upper()	
        

        (now lets hope your wordpress doesn’t screw up the formatting)

        What I expected was that they are adding something like “SamsungSecret” to the string to hash – but it seems that they actually thought about making brute-forcing a magnitude slower. Nice.

      • Hi Gerd

        Nice work with the Samsung “secret hash”.
        May I ask how did you get the code ?

        thx a lot

    • Hi yof,

      just see below – I decoded the framework.odex file from the samsung firmware and analyzed it. Then I wrote the python code and tested it agains some real world examples.

    • Gerd,

      Great, that’s really useful thanks!

      That does make cracking it a lot slower doesn’t it? Time for me to look at the Python Cuda bindings again I think…

      Where did you find the information about their implementation? Did you go down the decompiling route?

      • The time consuming function in this is the hash, and they are executing it 1024 times instead of just 1. So you’d need to rent more computing power at Amazon or go the Cuda route to get it done in time.

        Yes, I found out what they are doing by decompiling.

      • Yeah, we might need something with a little more grunt – and python might not be the appropriate language for that job…

        Was the code in the location I suggested?

      • Sorry, I don’t know where Samsung uses this and where not. I have a Galaxy SII (GT-9100, EU model) and it uses it. That’s why I wanted to find out more about it.

        What models do you have and where do they use it? Maybe we can collect a list of devices here.

      • A samsung GSII (EU model) (use it) and a GalaxyTab P1000 (don’t use it) and i tried with a GalaxyS (don’t use it)

  9. Pingback: Chrome Session and Tabs Files (and the puzzle of the pickle) | Digital Investigation

  10. Yesterday I finished a pinlocked Motorola MB200 reference a homicide case. I just wanted to pass on some info about this phone that I found to be different from others. The carrier for this phone is T-Mobile and the OS is Android 1.6.1 Cupcake. The phone was released in 2009. After I obtained an image of the phone using the Medusa Box, I tried the CCL scripts and Cellebrite’s PA to find the pin but had no luck. I didn’t even get a hit for lockdown.password_salt or password.key. I was left with having to do a little research and asking around as to why this was happening. While looking at the raw image, I did find a keyword hit for pinlock.key. A closer look revealed what looked like a SHA1 value 2118 bytes prior to the start of the keyword. I tried that value with the CCL script and it worked. The pin lock was not salted as in the newer versions. I’m sure this is already known, but I wanted to put it out there for the newer JTAGers as myself.

  11. Hello

    I have a sony ericsson walkman live with android 2.3. unfortunately I’m not due to my forgetfulness (forgot pin) on the phone.

    thanks to their scripts I could find password. what for prerequisites i need for start the script?

    I can only connect the phone via usb. this is sufficient?

    Thank you for any help.

    friendly greetings

    ben

  12. I have the hash and the salt and am trying to run the bruteforceandroidpin.py with the hash and salt. I am getting the passcode: none message. then i tried adding the t after bruteforceandroidpin.py but am getting the message BruteForceAndroidPin.py . What am I doing wrong? This is the first time I have used it by just adding the hash and salt manually. thanks.

    • Ray,

      When entering the hash and salt manually you also need to set the max length eg:
      BruteForceAndroidPin.py 8

      It may be that the PIN is longer than you’re currently specifying? The maximum is 16 (although that’ll take a while to run).

  13. Dear All,
    Greetings from a non techie, I have a Motorla ME863 (Droid3) It is the chinese version as it was purchased in China (08/12) while on travels ( I am UK based) I have forgotten the phone lock pin code..(1,500 attempts) and have had no luck trying to figure out how to unlock the code. The phone I used to take a lot of pics and images as I write articled for magazines and would love to be able to unlock the phone. The usb connection was set to charge only (not sync) on the phone so I dont know if usb connect will work (you can tell I have no tech ability lol) If anyone can help me with this problem my gratitude would be huge.
    Many thanks in advance
    JD

    • Julian,
      Probably the easiest thing for you to do here is to use the “Forgot PIN” button which appears after you’ve gotten the code wrong a few times. You can then enter your Google credentials and reset it that way. This technique and another possible solution is detailed here: http://droidlessons.com/how-to-reset-your-android-lock-screen-password/

      If the photos are more pressing then it might be worth checking that there isn’t a microSD card installed in the phone as they may saved to there rather than the internal memory.

      Hope that helps.

      • I had found that as a poss solution, but as chinese based phones block, google, facebook and gmail that is a no go. 😦
        At the forget pin option it only seems to offer factory reset

  14. Just wanted to let you know, My daughter changed her pin and promptly forgot it after school was out. After 3 days I ran across this, and 15 minutes later it was unlocked (Samsung Galaxy S). Simply used adb to pull everything.

    command prompt lines

    ADB.exe shell
    sqlite3 /data/data/com.android.providers.settings/databases/setting.db
    .tables “just to make sure the table secure was there and accessible”
    select * from secure;
    “marked and copied the data from ‘lockscreen.password_salt”
    .quit

    now I pulled the password.key file

    ADB.exe pull /data/data/com.android.providers.settings/databases/password.key
    exit

    then opened password.key in hex editor copied everything (not in hex),

    then started your brute force method

    python C:\BruteForceAndroidPin.py

    2 minutes later there was her airheaded code. My daughter thanks you so much for saving her pictures and videos.

  15. Hello there! This article couldn’t be written much better! Reading through this article reminds me of my previous roommate! He constantly kept talking about this. I’ll send this information to him.
    Fairly certain he’s going to have a great read. Many thanks for sharing!

  16. Pingback: Sécurité des terminaux Android | SCRT Sec Team blog

  17. Hi,
    I’m not really a programmer so please bear with me.
    I have a samsung galaxy SII and I’m trying to retrieve the lock pin that I put in the other day then forgot.
    I have rooted but it appears usb debugging is not enabled and I can’t work out how to remotely turn it on (if it’s possible), so the adb method won’t work.
    My pin is short so I assume it won’t take long to crack once I get the correct process running.
    The files I got when I dumped using CWM are:
    boot.img
    cache.ext4.tar
    data.ext4.tar
    nandroid.md5
    recovery.img
    system.ext4.tar
    I’ve installed python and tried running recoverandroidpin.py on all of the above files, only one returns a salt.
    I’m lost. Do I have to edit the recoverandroidpin.py file to be specific to the galaxy s2 (as per one of the previous posts)?

    Cheers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s