Password storage in Android M

While Android has received a number of security enhancements in the last few releases, the lockscreen (also know as the keyguard) and password storage have remained virtually unchanged since the 2.x days, save for adding multi-user support. Android M is finally changing this with official support for fingerprint authentication. While the code related to biometric support is currently unavailable, some of the new code responsible for password storage and user authentication is partially available in AOSP's master branch. Examining the runtime behaviour and files used by the current Android M preview reveals that some password storage changes have already been deployed. This post will briefly review how password storage has been implemented in pre-M Android versions, and then introduce the changes brought about by Android M.

Keyguard unlock methods

Stock Android provides three keyguard unlock methods: pattern, PIN and password (Face Unlock has been rebranded to 'Trusted face' and moved to the proprietary Smart Lock extension, part of Google Play Services). The pattern unlock is the original Android unlock method, while PIN and password (which are essentially equivalent under the hood) were added in version 2.2. The following sections will discuss how credentials are registered, stored and verified for the pattern and PIN/password unlock methods.

Pattern unlock

Android's pattern unlock is entered by joining at least four points on a 3×3 matrix (some custom ROMs allow a bigger matrix). Each point can be used only once (crossed points are disregarded) and the maximum number of points is nine. The pattern is internally converted to a byte sequence, with each point represented by its index, where 0 is top left and 8 is bottom right. Thus the pattern is similar to a PIN with a minimum of four and maximum of nine digits which uses only nine distinct digits (0 to 8). However, because points cannot be repeated, the number of variations in an unlock pattern is considerably lower compared to those of a nine-digit PIN. As pattern unlock is the original and initially sole unlock method supported by Android, a fair amount of research has been done about it's (in)security. It has been shown that patterns can be guessed quite reliably using the so called smudge attack, and that the total number of possible combinations is less than 400 thousand, with only 1624 combinations for 4-dot (the default) patterns.

Android stores an unsalted SHA-1 hash of the unlock pattern in /data/system/gesture.key or /data/system/users/<user ID>/gesture.key on multi-user devices. It may look like this for the 'Z' pattern shown in the screenshot above.

$ od -tx1 gesture.key
0000000 6a 06 2b 9b 34 52 e3 66 40 71 81 a1 bf 92 ea 73
0000020 e9 ed 4c 48

Because the hash is unsalted, it is easy to precompute the hashes of all possible combinations and recover the original pattern instantaneously. As the number of combinations is fairly small, no special indexing or file format optimizations are required for the hash table, and the grep and xxd commands are all you need to recover the pattern once you have the gesture.key file.

$ grep `xxd -p gesture.key` pattern_hashes.txt
00010204060708, 6a062b9b3452e366407181a1bf92ea73e9ed4c48

PIN/password unlock

The PIN/password unlock method also relies on a stored hash of the user's credential, however it also uses a 64-bit random, per-user salt. The salt is stored in the locksettings.db SQLite database, along with other settings related to the lockscreen. The password hash is kept in the /data/system/password.key file, which contains a concatenation of the password's SHA-1 and MD5 hash values. The file's contents may look like this:

$ cat password.key && echo
2E704465DB8C3CBFF085D8A5135A6F3CA32D5A2CA4A628AE48E22443250C30A3E1449BD0

Note that the hashes are not nested, but their values are simply concatenated, so if you were to bruteforce the password, you only need to attack the weaker hash -- MD5. Another helpful fact is that in order to enable password auditing, Android stores details about the current PIN/password's format in the device_policies.xml file, which might look like this:

<policies setup-complete="true">
...
<active-password length="6" letters="0" lowercase="0" nonletter="6" 
                 numeric="6" quality="196608" symbols="0" uppercase="0">
</active-password>
</policies>

If you were able to obtain the password.key file, chances are that you would also have the device_policies.xml file. This file gives you enough information to narrow down the search space considerably when recovering the password by specifying a mask or password rules. For example, we can easily recover the following 6-digit pin using John the Ripper (JtR) in about a second by specifying the ?d?d?d?d?d?d mask and using the 'dynamic' MD5 hash format (hashcat has a dedicated Android PIN hash mode), as shown below . An 8-character (?l?l?l?l?l?l?l?l), lower case only password takes a couple of hours on the same hardware.

$ cat lockscreen.txt
user:$dynamic_1$A4A628AE48E22443250C30A3E1449BD0$327d5ce3f570d2eb

$ ./john --mask=?d?d?d?d?d?d lockscreen.txt
Loaded 1 password hash (dynamic_1 [md5($p.$s) (joomla) 128/128 AVX 480x4x3])
Will run 8 OpenMP threads
Press 'q' or Ctrl-C to abort, almost any other key for status
456987           (user)
1g 0:00:00:00 DONE  6.250g/s 4953Kp/s 4953Kc/s 4953KC/s 234687..575297

Android's lockscreen password can be easily reset by simply deleting the gesture.key and password.key files, so you might be wondering what is the point in trying to bruteforce it. As discussed in previous posts, the lockscreen password is used to derive keys that protect the keystore (if not hardware-backed), VPN profile passwords, backups, as well as the disk encryption key, so it might be valuable if trying to extract data from any of these services. And of course, the chance that a particular user is using the same pattern, PIN or password on all of their devices is quite high.

Gatekeeper password storage

We briefly introduced Android M's gatekeeper daemon in the keystore redesign post in relation to per-key authorization tokens. It turns out the gatekeeper does much more than that and is also responsible for registering (called 'enrolling') and verifying user passwords. Enrolling turns a plaintext password into a so called 'password handle', which is an opaque, implementation-dependent byte string. The password handle can then be stored on disk and used to check whether a user-supplied password matches the currently registered handle. While the gatekeeper HAL does not specify the format of password handles, the default software implementation uses the following format:

typedef uint64_t secure_id_t;
typedef uint64_t salt_t;

static const uint8_t HANDLE_VERSION = 2;
struct __attribute__ ((__packed__)) password_handle_t {
    // fields included in signature
    uint8_t version;
    secure_id_t user_id;
    uint64_t flags;

    // fields not included in signature
    salt_t salt;
    uint8_t signature[32];

    bool hardware_backed;
};

Here secure_id_t is randomly generated, 64-bit secure user ID, which is persisted in the /data/misc/gatekeeper directory in a file named after the user's Android user ID (*not* Linux UID; 0 for the primary user). The signature format is left to the implementation, but AOSP's commit log reveals that it is most probably scrypt for the current default implementation. Other gatekeeper implementations might opt to use a hardware-protected symmetric or asymmetric key to produce a 'real' signature (or HMAC).

Neither the HAL, nor the currently available AOSP source code specifies where password handles are to be stored, but looking through the /data/system directory reveals the following files, one of which happens to be the same size as the password_handle_t structure. This implies that it likely contains a serialized password_handle_t instance.

# ls -l /data/system/*key
-rw------- system   system         57 2015-06-24 10:24 gatekeeper.gesture.key
-rw------- system   system          0 2015-06-24 10:24 gatekeeper.password.key

That's quite a few assumptions though, so time to verify them by parsing the gatekeeper.gesture.key file and checking if the signature field matches the scrypt value of our lockscreen pattern (00010204060708 in binary representation). We can do so with the following Python code:

$ cat m-pass-hash.py
...
N = 16384;
r = 8;
p = 1;

f = open('gatekeeper.gesture.key', 'rb')
blob = f.read()

s = struct.Struct('<'+'17s 8s 32s')
(meta, salt, signature) = s.unpack_from(blob)
password = binascii.unhexlify('00010204060708');
to_hash = meta
to_hash += password
hash = scrypt.hash(to_hash, salt, N, r, p)

print 'signature  %s' % signature.encode('hex')
print 'Hash:      %s' % hash[0:32].encode('hex')
print 'Equal:     %s' % (hash[0:32] == signature)

$./m-pass-hash.py
signature: 3d1a20985dec4bd937e5040aadb465fc75542c71f617ad090ca1c0f96950a4b8
Hash:      3d1a20985dec4bd937e5040aadb465fc75542c71f617ad090ca1c0f96950a4b8
Equal: True

The program output above leads us to believe that the 'signature' stored in the password handle file is indeed the scrypt value of the blob's version, the 64-bit secure user ID, and the blob's flags field, concatenated with the plaintext pattern value. The scrypt hash value is calculated using the stored 64-bit salt and the scrypt parameters N=16384, r=8, p=1. Password handles for PINs or passwords are calculated in the same way, using the PIN/password string value as input.

With this new hashing scheme patterns and passwords are treated in the same way, and thus patterns are no longer easier to bruteforce. That said, with the help of the device_policies.xml file which gives us the length of the pattern and a pre-computed pattern table, one can drastically reduce the number of patterns to try, as most users are likely to use 4-6 step patterns (about 35,000 total combinations) .

Because Androd M's password hashing scheme doesn't directly use the plaintext password when calculating the scrypt value, optimized password recovery tools such as hashcat or JtR cannot be used directly to evaluate bruteforce cost. It is however fairly easy to build our own tool in order to check how a simple PIN holds against a brute force attack, assuming both the device_policies.xml and gatekeeper.password.key files have been obtained. As can be seen below, a simple Python script that tries all PINs from 0000 to 9999 in order takes about 10 minutes, when run on the same hardware as our previous JtR example (a 6-digit PIN would take about 17 hours with the same program). Compare this to less than a second for bruteforcing a 6-digit PIN for Android 5.1 (and earlier), and it is pretty obvious that the new hashing scheme Android M introduces greatly improves password storage security, even for simple PINs. Of course, as we mentioned earlier, the gatekeeper daemon is part of Android's HAL, so vendors are free to employ even more (or less...) secure gatekeeper implementations.

$ time ./m-pass-hash.py gatekeeper.password.key 4
Trying 0000...
Trying 0001...
Trying 0002...

...
Trying 9997...
Trying 9998...
Trying 9999...
Found PIN: 9999

real    9m46.118s
user    9m6.804s
sys     0m39.107s

Framework API

Android M is still in preview, so framework APIs are hardly stable, but we'll show the gatekeeper's AIDL interface for completeness. In the current preview release it is called IGateKeeperService and look likes this:

interface android.service.gatekeeper.IGateKeeperService {

    void clearSecureUserId(int uid);

    byte[] enroll(int uid, byte[] currentPasswordHandle, 
                  byte[] currentPassword, byte[] desiredPassword);

    long getSecureUserId(int uid);

    boolean verify(int uid, byte[] enrolledPasswordHandle, byte[] providedPassword);

    byte[] verifyChallenge(int uid, long challenge, 
                           byte[] enrolledPasswordHandle, byte[] providedPassword);
}

As you can see, the interface provides methods for generating/getting and clearing the secure user ID for a particular user, as well as the enroll(), verify() and verifyChallenge() methods whose parameters closely match the lower level HAL interface. To verify that there is a live service that implements this interface, we can try to call the getSecureUserId() method using the service command line utility like so:

$ service call android.service.gatekeeper.IGateKeeperService 4 i32 0
Result: Parcel(00000000 ee555c25 ea679e08  '....%\U...g.')

This returns a Binder Parcel with the primary user's (user ID 0) secure user ID, which matches the value stored in /data/misc/gatekeeper/0 shown below (stored in network byte order).

# od -tx1 /data/misc/gatekeeper/0
37777776644 25 5c 55 ee 08 9e 67 ea
37777776644

The actual storage of password hashes (handles) is carried out by the LockSettingsService (interface ILockSettings), as in previous versions. The service has been extended to support the new gatekeeper password handle format, as well as to migrate legacy hashes to the new format. It is easy to verify this by calling the checkPassword(String password, int userId) method which returns true if the password matches:

# service call lock_settings 11 s16 1234 i32 0
Result: Parcel(00000000 00000000   '........')
# service call lock_settings 11 s16 9999 i32 0
Result: Parcel(00000000 00000001   '........')

Summary

Android M introduces a new system service -- gatekeeper, which is responsible for converting plain text passwords to opaque binary blobs (called password handles) which can be safely stored on disk. The gatekeeper is part of Android's HAL, so it can be modified to take advantage of the device's native security features, such as secure storage or TEE, without modifying the core platform. The default implementation shipped with the current Android M preview release uses scrypt to hash unlock patterns, PINs or passwords, and provides much better protection against bruteforceing than the previously used single-round MD5 and SHA-1 hashes.