Keystore redesign in Android M

Android M has been announced, and the first preview builds and documentation are now available. The most visible security-related change is, of course, runtime permissions, which impacts almost all applications, and may require significant app redesign in some cases. Permissions are getting more than enough coverage, so this post will look into a less obvious, but still quite significant security change in Android M -- the redesigned keystore (credential storage) and related APIs. (The Android keystore has been somewhat of a recurring topic on this blog, so you might want to check older posts for some perspective.)

New keystore APIs

Android M officially introduces several new keystore features into the framework API, but the underlying work to support them has been going on for quite a while in the AOSP master branch. The most visible new feature is support for generating and using symmetric keys that are protected by the system keystore. Storing symmetric keys has been possible in previous versions too, but required using private (hidden) keystore APIs, and was thus not guaranteed to be portable across versions. Android M introduces a keystore-backed symmetric KeyGenerator, and adds support for the KeyStore.SecretKeyEntry JCA class, which allows storing and retrieving symmetric keys via the standard java.security.KeyStore JCA API. To support this, Android-specific key parameter classes and associated builders have been added to the Android SDK.

Here's how generating and retrieving a 256-bit AES key looks when using the new M APIs:

// key generation
KeyGenParameterSpec.Builder builder = new KeyGenParameterSpec.Builder("key1",
                    KeyProperties.PURPOSE_ENCRYPT | KeyProperties.PURPOSE_DECRYPT);
KeyGenParameterSpec keySpec = builder
                    .setKeySize(256)
                    .setBlockModes("CBC")
                    .setEncryptionPaddings("PKCS7Padding")
                    .setRandomizedEncryptionRequired(true)
                    .setUserAuthenticationRequired(true)
                    .setUserAuthenticationValidityDurationSeconds(5 * 60)
                    .build();
KeyGenerator kg = KeyGenerator.getInstance("AES", "AndroidKeyStore");
kg.init(keySpec);
SecretKey key = kg.generateKey();

// key retrieval
KeyStore ks = KeyStore.getInstance("AndroidKeyStore");
ks.load(null);

KeyStore.SecretKeyEntry entry = (KeyStore.SecretKeyEntry)ks.getEntry("key1", null);
key = entry.getSecretKey();

This is pretty standard JCA code, and is in fact very similar to how asymmetric keys (RSA and ECDSA) are handled in previous Android versions. What is new here is, that there are a lot more parameters you can set when generating (or importing a key). Along with basic properties such as key size and alias, you can now specify the supported key usage (encryption/decryption or signing/verification), block mode, padding, etc. Those properties are stored along with the key, and the system will disallow key usage which doesn't match the key's attributes. This allows insecure key usage patterns (ECB mode, or constant IV for CBC mode, for example) to be explicitly forbidden, as well as constraining certain keys to a particular purpose, which is important in a multi-key cryptosystem or protocol. Key validity period (separate for encryption/signing and decryption/verification) can also be specified.

Another major new feature is requiring use authentication before allowing a particular key to be used, and specifying the authentication validity period. Thus, a key that protects sensitive data, can require user authentication on each use (e.g., decryption), while a different key may require only a single authentication per session (say, every 10 minutes).


The newly introduced key properties are available for both symmetric and asymmetric keys. An interesting detail is that apparently trying to use a key is now the official way (Cf. the Confirm Credential sample and related video) to check whether a user has authenticated within a given time period. This quite a roundabout way to verify user presence, especially if you app doesn't make use of cryptography in the first place. The newly introduced FingerprintManager authentication APIs also make use of cryptographic objects, so this may be part of a larger picture, which we have yet to see.

Keystore and keymaster implementation

On a high level, key generation and storage work the same as in previous versions: the system keystore daemon provides an AIDL interface, which framework classes and system services use to generate and manage keys. The keystore AIDL has gained some new, more generic methods, as well support for a 'fallback' implementation but is mostly unchanged.

The keymaster HAL and its reference implementation have, however, been completely redesigned. The 'old' keymaster HAL is retained for backward compatibility as version 0.3, while the Android M version has been bumped to 1.0, and offers a completely different interface. The new interface allows for setting fine-grained key properties (also called 'key characteristics' internally), and supports breaking up cryptographic operations that manipulate data of unknown or large size into multiple steps using the familiar begin/update/finish pattern. Key properties are stored as a series of tags along with the key, and form an authorization set when combined. AOSP includes a pure software reference keymaster implementation which implements cryptographic operations using OpenSSL and encrypts key blobs using a provided master key. Let's take a more detailed look at how the software implementations handles key blobs.

Key blobs

Keymaster v1.0 key blobs are wrapped inside keystore blobs, which are in turn stored as files in /data/misc/keystore/user_X, as before (where X is the Android user ID, starting with 0 for the primary user). Keymaster blobs are variable size and employ a tag-length-value (TLV) format internally. They include a version byte, a nonce, encrypted key material, a tag for authenticating the encrypted key, as well as two authorization sets (enforced and unenforced), which contain the key's properties. Key material is encrypted using AES in OCB mode, which automatically authenticates the cipher text and produces an authentication tag upon completion. Each key blob is encrypted with a dedicated key encryption key (KEK), which is derived by hashing a binary tag representing the key's root of trust (hardware or software), concatenated with they key's authorization sets. Finally, the resulting hash value is encrypted with the master key to derive the blob's KEK. The current software implementation deliberately uses a 128-bit AES zero key, and employs a constant, all-zero nonce for all keys. It is expected that the final implementation will either use a hardware-backed master-key, or be completely TEE-based, and thus not directly accessible from Android.

The current format is quite easy to decrypt, and while this will likely change in the final M version, in the mean time you can decrypt keymaster v1.0 blobs using the keystore-decryptor tool. The program also supports key blobs generated by previous Android versions, and will try to parse (but not decrypt) encrypted RSA blobs on Qualcomm devices. Note that the tool may not work on devices that use custom key blob formats or otherwise customize the keystore implementation. keystore-decryptor takes as input the keystore's .masterkey file, the key blob to decrypt, and a PIN/password, which is the same as the device's lockscreen credential. Here's a sample invocation:

$ java -jar ksdecryptor-all.jar .masterkey 10092_USRPKEY_ec_key4 1234
master key: d6c70396df7bfdd8b47913485dc0a885

EC key:
  s: 22c18a15163ad13f3bbeace52c361150 (254)
  params: 1.2.840.10045.3.1.7
  key size: 256
  key algorithm: EC
  authorizations:

Hidden tags:
tag=900002C0 TAG_KM_BYTES bytes: 5357 (2)

Enforced tags:

Unenforced tags:
tag=20000001 TAG_KM_ENUM_REP 00000003
tag=60000191 TAG_KM_DATE 000002DDFEB9EAF0: Sun Nov 24 11:10:25 JST 2069
tag=10000002 TAG_KM_ENUM 00000003
tag=30000003 TAG_KM_INT 00000100
tag=700001F4 TAG_KM_BOOL 1
tag=20000005 TAG_KM_ENUM_REP 00000000
tag=20000006 TAG_KM_ENUM_REP 00000001
tag=700001F7 TAG_KM_BOOL 1
tag=600002BD TAG_KM_DATE FFFFFFFFBD84BAF0: Fri Dec 19 11:10:25 JST 1969
tag=100002BE TAG_KM_ENUM 00000000

Per-key authorization

As discussed in the 'New keystore APIs' section, the setUserAuthenticationRequired() method of the key parameter builder allows you to require that the user authenticates before they are authorized to use a certain key (not unlike iOS's Keychain). While this is not a new concept (system-wide credentials in Android 4.x require access to be granted per-key), the interesting part is how it is implemented in Android M. The system keystore service now holds an authentication token table, and a key operation is only authorized if the table contains a matching token. Tokens include an HMAC and thus can provide a strong guarantee that a user has actually authenticated at a given time, using a particular authentication method.

Authentication tokens are now part of Android's HAL, and currently support two authentication methods: password and fingerprint. Here's how tokens are  defined:

typedef enum {
    HW_AUTH_NONE = 0,
    HW_AUTH_PASSWORD = 1 << 0,
    HW_AUTH_FINGERPRINT = 1 << 1,
    HW_AUTH_ANY = UINT32_MAX,
} hw_authenticator_type_t;

typedef struct __attribute__((__packed__)) {
    uint8_t version;  // Current version is 0
    uint64_t challenge;
    uint64_t user_id;             // secure user ID, not Android user ID
    uint64_t authenticator_id;    // secure authenticator ID
    uint32_t authenticator_type;  // hw_authenticator_type_t, in network order
    uint64_t timestamp;           // in network order
    uint8_t hmac[32];
} hw_auth_token_t;

Tokens are generated by a newly introduced system component, called the gatekeeper. The gatekeeper issues a token after it verifies the user-entered password against a previously enrolled one. Unfortunately, the current AOSP master branch does not include the actual code that creates these tokens, but there is a base class which shows how a typical gatekeeper might be implemented: it computes an HMAC over the all fields of the hw_auth_token_t structure up to hmac using a dedicated key, and stores it in the hmac field. The serialized hw_auth_token_t structure then serves as an authentication token, and can be passed to other components that need to verify if the user is authenticated. Management of the token generation key is implementation-dependent, but it is expected that it is securely stored, and inaccessible to other system applications. In the final gatekeeper implementation the HMAC key will likely be backed by hardware, and the gatekeeper module could execute entirely within the TEE, and thus be inaccessible to Android. The low-level gatekeeper interface is part of Android M's HAL and is defined in hardware/gatekeeper.h.

As can be expected, the current Android M builds do indeed include a gatekeeper binary, which is declared as follows in init.rc:

...
service gatekeeperd /system/bin/gatekeeperd /data/misc/gatekeeper
    class main
    user system
...

While the framework code that makes use of the gatekeepr daemon is not yet available, it is expected that the Android M keyguard (lockscreen) implementation interacts with the gatekeeper in order to obtain a token upon user authentication, and passes it to the system's keystore service via its addAuthToken() method. The fingerprint authentication module (possibly an alternative keyguard implementation) likely works in the same way, but compares fingerprint scans against a previously enrolled fingerprint template instead of passwords.

Summary

Android M includes a redesigned keystore implementation which allows for fine-grained key usage control, and supports per-key authorization. The new keystore supports both symmetric and asymmetric keys, which are stored on disk as key blobs. Key blobs include encrypted key material, as well as a set of key tags, forming an authorization set. Key material is encrypted with a per-blob KEK, derived from the key's properties and a common master key. The final keystore implementation is expected to use a hardware-backed master key, and run entirely within the confines of the TEE. 

Android M also includes a new system component, called the gatekeeper, which can issue signed tokens to attest that a particular user has authenticated at a particular time. The gatekeeper has been integrated with the current PIN, pattern or password-based lockscreen, and is expected to integrate with fingerprint-based authentication in the final Android M version on supported devices. 

Comments

stevemorrow001 said…
Hi Nikolay,

First, thanks for the great posts on Android security. They are an invaluable resource for anyone developing security-conscious apps.

I have a question regarding the security of the Android keystore/keychain on all recent versions of the OS.

As your posts have laid out, access to keys in the keystore are defined on a per-app basis such that each app can only access its own keys. This is essentially governed by the app UID (and, as of 4.3, the user id).

On your post describing the ICS keychain, you stated, "What this means in practice is that the Android key store is pretty secure for a software solution: even if you had access to a rooted device and managed to extract the key blobs, you would still need the keystore password to derive the master key."

As of Jelly Bean (and now through Android M), support for hardware-backed devices has been provided, such that even on a rooted device, the key material should not be exposed (i.e., the security of the keystore is essentially defined by the security of the TE).

These are direct attacks on the keychain, though. Suppose I have a device with app X installed and key K generated by app X. Suppose that the device is rooted. What prevents me from installing malicious app Y, granting it root access, and having app Y impersonate app X (i.e., run under the same UID) such that app Y can now access key K directly? This would seem to preclude any direct attack on the keystore, and instead use the OS permissions system directly to access any key in the keystore.
Nikolay Elenkov said…
Not much, really. If you can impersonate other apps (including system apps), you've successfully circumvented Android's security model. If SELinux is in enforcing mode (4.4+), simply getting UID 0 would probably not be enough to impersonate apps. That said, if you have physical access and can get root (unlocked bootloader, etc.), chances are you can also disable SELinux.
Arne Riiber said…
Thanks for great sharing of Android Security internals! A small question related to example 1 above, generating and retrieving a 256-bit AES key:

On a hardware-backed key storage device, can a symmetric key be extracted using the getEncoded() method of the Key - so that another part may use the secret key for encrypting/decrypting information to the device - or is the key not exportable - so that encrypt/decrypt can be preformed on the device only?

Best regards

Arne
Holla said…
Hi Nikolay! With a kernel exploit it would still be possible to impersonate apps, or?
Pavel Lašta said…
I think there are number of ways to get the key if you have root access. But the most important is that you can't (or it's hard) to get key from the hardware backed storage. Example of attacks could be to hook Java or C using substrate or xposed framework, also to modify kernel. There always be a moment then the key will be in memory. But it will be always hard to copy this key somewhere into other device. Nikolay, am I right?
Nikolay Elenkov said…
TrustZone guarantees that you cannot access secure memory from Android. Unless you find a vulnerability in the TEE implementation, you cannot access the key, even though it is in physical memory at some point. Modifying the kernel doesn't help either, because the TEE is a separate OS.
Pavel Lašta said…
This comment has been removed by the author.
Pavel Lašta said…
Nikolay, you're right. I wrote my post without investigating too much. This looks like a great stuff. Quick question - I found few articles about generating key in hw keystore, but can you actually put something into it e.g private key. There's a method setEntry. Another question: then keystore gets wiped? I saw some people complaining that after changing lock from passcode to pincode causes keystore to get wiped. Thanks
Sarbyn said…
My app made for android 4.4.x with the standard KeyStore (with an RSA keypair) had a strange behaviour with Android M.
I found that on Android M it is possible to change the keyguard type and also is possible to disable it even if a keystore is setted up. If the user disable it, my keystore is deleted without any warning (a popup for the user, but no warning to my application) and then my app become completely useless......
This is normal? Google changes the KeyStore and Keyguard behaviour? Why? This is very dangerous because if an user removes the keyguard it will also delete all the data in keystores (for example, also VPN credentials?).
Nikolay Elenkov said…
This comment has been removed by the author.
Nikolay Elenkov said…
This appears to be by design. It wasn't clearly documented before but now it is, see https://developer.android.com/training/articles/keystore.html

Also this for some more details/investigation: https://doridori.github.io/android-security-the%20forgetful-keystore/
Unknown said…
Hi Nikolay,

Thanks for great sharing, I have a problem and described here http://stackoverflow.com/questions/35342372/how-to-generate-key-using-keygenerator-for-fingerprint-api-in-android

Can you guide me how to proceed further?
Regards,
Gulfam
Lukas said…
Do you know if Gatekeeper is used to protect the full-disk encryption key as well? According to Google's doc, the TEE is used for FDE key derivation, but it is unclear from their description if on-device brute force attempts are possible or not.
Lukas said…
I think I've found the answer myself: http://androidxref.com/6.0.1_r10/xref/system/vold/cryptfs.c#215

If I understand it correctly, this means that the TEE is currently only used to prevent off-device parallelized brute-force attacks, but on-device brute forcing is only limited by the speed of the keymaster hardware implementation.
Nikolay Elenkov said…
I haven't tested with latest code, but yes, you are right. You can also dump the encryption key if you can modify the kernel. See this post for some details about an alternative implementation: http://nelenkov.blogspot.com/2015/05/hardware-accelerated-disk-encryption-in.html
Nikolay Elenkov said…
It is however rate-limited, and will wipe after 10 or 20 unsuccessful tries.
Lukas said…
Thanks, very interesting! Where is that retry limit enforced? I couldn't find any reference in the cryptfs.c implementation or the keystore/keymaster docs. Is this something that can be used from Keystore userspace clients as well?
Nikolay Elenkov said…
The crypto footer only stores the number of tries. The wipe logic is in the CryptKeeper app, which is what you see when you enter the FED PIN/password on boot.
Unknown said…
I have a problem using my sd card as internal storage but I had to reinstall the rom now I get that I have to fomatear , but I have important files will be some way to recover or lost forever

Popular posts from this blog

Password storage in Android M

Decrypting Android M adopted storage

Unpacking Android backups