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.