Gadget Performance

In a perfect world, a working Public Key Infrastructure (PKI) takes care of issuing, distributing and revoking certificates as necessary. All that a system needs to verify the identities of previously unknown machines and users are a few trust anchor certificates. In practice, though, there are number of issues. Those have been known for some time, but the recent breaches in top-level CAs have shown that the problems and their consequences are far from theoretical. Probably the biggest PKI issue is that revocation of root certificates is not really supported. Most OSes and browsers come with a pre-configured set of trusted CA certificates (dozens of them!) and when a CA certificate is compromised there are two main ways to handle it: 1. tell users to remove it from the trust store; or, 2. issue an emergency update that removes the affected certificate. Expecting users to handle this is obviously unrealistic, so that leaves the second option. Windows modifies OS trust anchors by distributing patches via Windows Update, and browser vendors simply release a new patch version. However, even if an update removes a CA certificate from the system trust store, a user can still install it again, especially when presented with a 'do this, or you can't access this site' ultimatum. To make sure removed trust anchors are not brought back, the hashes of their public keys are added to a blacklist and the OS/browser rejects them even if they are in the user trust store. This approach effectively revokes CA certificates (within the scope of the OS/browser, of course) and takes care of PKI's inability to handle compromised trust anchors. However, it's not exactly ideal: even an emergency update takes some time to prepare, and even after it is out some users won't update right away, no matter how often they are being nagged about it. CA compromises are relatively rare and widely publicized though, so it seems to work OK in practice (for now, at least).

While CA breaches are fairly uncommon, end entity (EE) key compromise occurs much more often. Whether due to a server breach, stolen laptop or a lost smart card, it happens daily. Fortunately, modern PKI systems have been designed with this in mind -- CAs can revoke certificates and publish revocation information in the form of CRLs, or provide online revocation status using OCSP. Unfortunately, this doesn't really work in the real world. Revocation checking generally requires network access to a machine different from the one we are trying to connect to, and as such has a fairly high failure rate. To mitigate this most browsers do their best to fetch fresh revocation information, but if this fails for some reason, they simply ignore the error (soft-fail), or at best show some visual indication that revocation information is not available. To solve this Google Chrome has opted to disable online revocation checks altogether, and now uses its online update mechanism to proactively push revocation information to browsers, without requiring an application update or restart. Thus Chrome can have an up-to-date local cache of revocation information which makes certificate validation both faster and more reliable. This is yet another blacklist (Chrome calls it a 'CRL set'), this time based on information published by each CA. The browser vendor effectively managing revocation data on the user's behalf is quite novel, and not everyone thinks it's a good idea, but it has worked well so far.

In Android versions prior to 4.0 (Ice Cream Sandwich, ICS), the system trust store was a single Bouncy Castle key store file. Modifying it without root permissions was impossible and the OS didn't have a supported way to amend it. That meant that adding new trust anchors or removing compromised ones required an OS update. Since, unlike regular desktop OSes, updates are generally handled by carriers and not the OS vendor, they are usually few and far between. What's more, if a device doesn't sell well, it may never get an official update. In practice this means that there are thousands of devices that still trust compromised CAs, or don't trust newer CAs that have issued hundreds of web site certificates. ICS changed this by making the system trust store mutable and adding an UI, as well as an SDK API, that allows for adding and removing trust anchors. This didn't quite solve PKI's number one problem though -- aside from the user manually disabling a comprised trust anchor, an OS update was still required to blacklist a CA certificate. Additionally, Android does not perform online revocation checks when validating certificate chains, so there was no way to detect compromised end entity certificates, even if they have been revoked.

This finally leads us to the topic of the article -- Android 4.1 (Jelly Bean, JB) has taken steps to allow for online update of system trust anchors and revocation information by introducing certificate blacklists. There are now two system blacklists:

• a public key hash blacklist (to handle compromised CAs)
• a serial number blacklist (to handle compromised EE certificates)

The certificate chain validator component takes those two lists in consideration when verifying web site or user certificates. Let's look at how this implemented in a bit more detail.

Android uses a content provider to store OS settings in a system databases. Some of those settings can be modified by third party apps holding the necessary permissions, while some are reserved for the system and can only be changed by going through the system settings UI, or by another system application. The latter are known as 'secure settings'. Jelly Bean adds two new secure settings under the following URIs:

• content://settings/secure/pubkey_blacklist
• content://settings/secure/serial_blacklist

As the names imply, the first one stores public key hashes of compromised CAs and the second one a list of EE certificate serial numbers. Additionally, the system server now starts a CertiBlacklister component which registers itself as a ContentObserver for the two blacklist URIs. Whenever a new value is written to those, the CertBlacklister gets notified and writes the value to a file on disk. The format of the files is simple: a comma delimited list of hex-encoded public key hashes or certificate serial numbers. The actual files are:

• certificate blacklist: /data/misc/keychain/pubkey_blacklist.txt
• serial number blacklist: /data/misc/keychain/serial_blacklist.txt

As explained above, the API to update blacklists is rather simple: essentially two secure settings keys, the values being the actual blacklists in hex-encoded form. Using them requires system permissions though, so our test application needs to either live in /system/app or be signed with the platform certificate. As usual, we choose the former for our tests. A screenshot of the app is shown below.

The app allows us to install a CA certificate to the system trust store (using the KeyChain API), verify a certificate chain (consisting of a the CA certificate and a single EE certificate), add either of the certificates to the system blacklist, and finally clear it so we can start over. The code is quite straightforward, see github repository for details. One thing to note is that it instantiates the low level org.bouncycastle.jce.provider.CertBlacklist class in order to check directly whether modifying the blacklist succeeded. Since this class is not part of the public API, it is accessed using reflection.

Some experimentation reveals that while the CertiBlacklister observer works as expected and changes to the blacklists are immediately written to the corresponding files in /data/misc/keychain, verifying the chain succeeds even after the certificates have been blacklisted. The reason for this is that, as all system classes, the certificate path validator class is pre-loaded and shared across all apps. Therefore it reads the blacklist files only at startup, and a system restart is needed to have it re-read the files. After a restart, validation fails with the expected error: 'Certificate revocation of serial XXXX'. Another issue is that while blacklisting by serial number works as expected, public key blacklisting doesn't appear to work in the current public build (JRO03C on Galaxy Nexus as of July 2012). This is a result of improper handling of the key hash format and will hopefully be fixed in a next JB maintenance release. Update: it is now fixed in AOSP master.

In Jelly Bean, Android takes steps to get on par with the Chrome browser with respect to managing certificate trust. It introduces features that allow for modifying blacklists dynamically: based on push notifications, and without requiring a system update. While the current implementation has some rough edges and does require a reboot to apply updates, once those are smoothed out, certificate blacklisting will definitely contribute to making Android more resilient to PKI-related attacks and vulnerabilities.

The first two features are mostly self-explanatory, but the rest merit some exploration. Let's look into each one in turn.

As we have already discussed, the system key store in Android is provided by a native daemon that encrypts secrets using a key derived from the device unlock password, stores them on disk and regulates key access based on UID. In ICS and previous versions, the keystore daemon simply stores opaque encrypted blobs and the only meatdata available (UID of owner and key name) was encoded in the file name under which blobs are stored. In Jelly Bean (JB), blobs also have a version field and a type field. The following key types are newly defined:

TYPE_GENERIC is used for key blobs saved using the previous get/put interface, and TYPE_MASTER_KEY is, of course, only used for the key store master key. The newly added TYPE_KEY_PAIR is used for key blobs created using the new GENERATE and IMPORT commands. Before we go into more details, here are the keystore commands added in Jelly Bean:

• GENERATE
• IMPORT
• SIGN
• VERIFY
• GET_PUBKEY
• DEL_KEY
• GRANT
• UNGRANT

Key store OpenSSL engine

And finally, time for our feature presentation -- the keymaster module and its hardware-based implementation on Galaxy Nexus (and Nexus 7, but that currently has no relevant source code in AOSP, so we will focus on the GN). Jelly Bean introduces a new libhardware (aka HAL) module, called keymaster. It defines structures and methods for generating keys and signing/verifying data. The keymaster module is meant to decouple Android from the actual device security hardware, and a typical implementation would use a vendor-provided library to communicate with the crypto-enabled hardware. Jelly Bean comes with a default softkeymaster module that does all key operations in software only (using the ubiquitous OpenSSL). It is used on the emulator and probably will be included in devices that lack dedicated cryptographic hardware. The currently defined operations are listed below. Only RSA is supported at present.

Galaxy Nexus keymaster implementation

# ls -l /data/misc/keystore/10164*
-rw------- keystore keystore       84 2012-07-12 14:15 10164_foobar
-rw------- keystore keystore       84 2012-07-12 14:15 10164_imported

So where are the actual keys? It turns out they are in the /data/smc/user.bin file. The format is, of course, proprietary, but it would be a safe bet that it is encrypted with a key stored on the SoC (or at least somehow protected by a hardware key). This allows to have practically an unlimited number of keys inside the TEE, without being bounded by the limited storage space on the physical chip.

keymaster usage and performance

The OMAP4 chip is advertised as having hardware accelerated cryptographic operations, so let's see how RSA key generation, signing and verification measure up against the default Android software implementations:

Average 2048-bit RSA operation speed on Galaxy Nexus

Crypto Provider/Operation	Key generation	Signing	Verification
Bouncy Castle	2176.20 [ms]	34.60 [ms]	1.90 [ms]
OpenSSL	2467.40 [ms]	29.80 [ms]	1.00 [ms]
TEE	3487.00 [ms]	10.90 [ms]	10.60 [ms]

As you can see from the table above, Bouncy Castle and OpensSSL perform about the same, while the TEE takes more time to generate keys (most probably because it's using a hardware RNG, not a PRNG), but signing is about 3 times faster compared to the software implementations. Verification takes about the same time as signing, and is slower than software. It should be noted that this test is not exactly precise: calling the token TA via the keystore daemon causes a lot of TEE client API sessions to be open and closed which has its overhead. Getting more accurate times will require benchmarking using the Client API directly, but the order of the results should be the same.

Summary

To sum things up: Jelly Bean finally has a standard hardware key storage and cryptographic operations API in the keymater HAL module definition. The implementation for each device is hardware-dependent, and the currently available implementations use the TEE Client API on the Galaxy Nexus and Nexus 7 to take advantage of the TEE capabilities of the respective SoC (OMAP4 and Tegra 3). The current interface and implementation only support generating/importing of RSA keys and signing/verification, but will probably be extended in the future with more key types and operations. It is integrated with the system credential storage (managed by the keystore daemon) and allows us to generate, import and use RSA keys protected by the devices's TEE from Android applications.

The previous version of this article was based on Eclipse framework source packages and binary system images, and was missing a few pieces. As Jelly Bean source has now been open sourced, the discussion below has been revised and is now based on the AOSP code (4.1.1_r1). If you are coming back you might want to re-read this post, focusing on the second part.

Apps on Android can be installed in a few different ways:

• via an application store (e.g., the Google Play Store, aka Android Market)
• directly on the phone by opening app files or email attachments (if the 'Unknown sources' options is enabled)
• from a computer connected through USB by using the adb install SDK command

The first two don't provide any options or particular insight into the underlying implementation, so let's explore the third one. Looking at the adb usage output, we see that the install command has gained a few new options in the latest SDK release:

adb install [-l] [-r] [-s] [--algo <algorithm name> --key <hex-encoded key> 
--iv <hex-encoded iv>] <file>

The --algo, --key and --iv parameters obviously have to do with encrypted apps, so before going into details lets first try to install an encrypted APK. Encrypting a file is quite easy to do using the enc OpenSSL commands, usually already installed on most Linux systems. We'll use AES in CBC mode with a 128 bit key (a not very secure one, as you can see below), and specify an initialization vector (IV) which is the same as the key to make things simpler:

$ openssl enc -aes-128-cbc -K 000102030405060708090A0B0C0D0E0F 
-iv 000102030405060708090A0B0C0D0E0F -in my-app.apk -out my-app-enc.apk

Let's check if Android likes our newly encrypted app by trying to install it:

$ adb install --algo 'AES/CBC/PKCS5Padding' --key 000102030405060708090A0B0C0D0E0F 
--iv 000102030405060708090A0B0C0D0E0F my-app-enc.apk
        pkg: /data/local/tmp/my-app-enc.apk
Success

The 'Success' output seems promising, and sure enough the app's icon is in the system tray and it starts without errors. The actual apk file is copied in /data/app as usual, and comparing its hash value with our encrypted APK reveals that it's in fact a different file. The hash value is exactly the same as that of the original (unencrytped) APK though, so we can conclude that the APK is being decrytped at install time using the encryption parameters (algorithm, key and IV) we have provided. Let's look into how this is actually implemented. 

The adb install command simply calls the pm Android command line utility which lets us list, install and delete packages (apps). The component responsible for installing apps on Android has traditionally been the PackageManagerService and the pm is just a convenient frontend for it. Apps usually access the package service through the facade class PackageManager. Browsing through its   code and checking for encryption related methods we find this:

public abstract void installPackageWithVerification(Uri packageURI,
        IPackageInstallObserver observer, int flags, String installerPackageName,
        Uri verificationURI, ManifestDigest manifestDigest,
        ContainerEncryptionParams encryptionParams);

The ContainerEncryptionParams class looks especially promising, so let's peek inside:

public class ContainerEncryptionParams implements Parcelable {
    private final String mEncryptionAlgorithm;
    private final IvParameterSpec mEncryptionSpec;
    private final SecretKey mEncryptionKey;
    private final String mMacAlgorithm;
    private final AlgorithmParameterSpec mMacSpec;
    private final SecretKey mMacKey;
    private final byte[] mMacTag;
    private final long mAuthenticatedDataStart;
    private final long mEncryptedDataStart;
}

The adb install parameters we used above neatly correspond to the first three fields of the class. In addition to that, the class also stores MAC related parameters, so it's safe to assume that Android can now check the integrity of application binaries. Unfortunately, the pm command doesn't have any MAC-related parameters (it does actually, but for some reason those are disabled in the current build), so to try out the MAC support we need to call the installPackageWithVerification method directly.

The method is hidden from SDK applications, so the only way to call it from an app is to use reflection. It turns out that most of its parameter classes (IPackageInstallObserver, ManifestDigest and ContainerEncryptionParams) are also hidden, but that's only a minor snag. Android pre-loads framework classes, so even if you app bundles a framework class, the system copy will always be used at runtime. This means that all we have to do to get a handle for the installPackageWithVerification method is add the required classes to the andorid.content.pm package in our app. Once we have a method handle, we just need to instantiate the ContainerEncryptionParams class, providing all the encryption and MAC related parameters. One thing to note is that since our entire file is encrypted, and the MAC is calculated over all of its contents (see below), we specify 0 for both the encrypted and authenticated data start, and the file size as the data end (see sample code). To calculate the MAC value (tag) we once again use OpenSSL:

$ openssl dgst -hmac 'hmac_key_1' -sha1 -hex my-app-enc.apk
HMAC-SHA1(my-app-enc.apk)= 0dc53c04d33658ce554ade37de8013b2cff0a6a5

Note that the dgst command doesn't support specifying the HMAC key using hexadecimal or Base64, so you are limited to ASCII characters. This may not be a good idea for production use, so consider using a real key and calculating the MAC in some other way (using JCE, etc.).

Our app is mostly ready now, but installing apps requires the INSTALL_PACKAGES permission, which is defined with protection level signatureOrSystem. Thus it is granted only to apps signed with the system (ROM) key, or apps installed in the /system partition. Building a Jelly Bean ROM is an interesting excercise, but for now, we'll simply copy our app to /system/app in order to get the necessary permission to install packages (on the emulator or a rooted device). Once this is done, we can install an encrypted app via the PackageManager and Android will both decrypt the APK and verify that the package hasn't been tampered with by comparing the specified MAC tag with value calculated based on the actual file contents. You can test that using the sample application by slightly changing the encryption and MAC parameters. This should result in an install error.



The android.content.pm package has some more classes of interest, such as MacAuthenticatedInputStream and ManifestDigest, but the actual APK encryption and MAC verification is done by the DefaultContainerService$ApkContainer, part of the DefaultContainerService (aka, 'Package Access Helper').

'Forward locking' popped up around the time ringtones, wallpalers and other digital 'goods' started selling on mobile (feature) phones. The name comes from the intention -- stop users from forwarding files they have bought to their friends and family. The main digital content on Android were originally apps, and as paid apps gained popularity, sharing (and later re-selling those) was becoming a problem. Application packages (APKs) have been traditionally world readable on Android, which made extracting apps from even a production device relatively easy. While world-readable app files might sound like a bad idea, it's rooted in Android's open and extensible nature -- third party launchers, widget containers and utility apps can easily inspect APKs to extract icons, widget definitions available intents, etc. In an attempt to lock down paid apps without losing any of the OS flexibility, Android introduced forward locking (aka, 'copy protection'). The idea was to split app packages into two parts -- a world-readable part, containing resources and the manifest (in /data/app), and a package readable only by the system user, containing executable code (in /data/app-private). The code package was protected by file system permissions, and while this made it inaccessible to users on most consumer devices, one only needed to gain root access to be able to extract it. This approach was quickly deprecated, and online Android Licensing (LVL) was introduced as a replacement. This, however, shifted app protection implementation from the OS to app developers, and has had mixed results.

In Jelly Bean, the forward locking implementation has been re-designed and now offers the ability to store APKs in an encrypted container that requires a device-specific key to be mounted at runtime. Let's look into the implementation in a bit more detail.

Jelly Bean implementation

While encrypted app containers as a forward locking mechanism are new to JB, the encrypted container idea has been around since Froyo. At the time (May 2010) most Android devices came with limited internal storage and a fairly large (a few GB) external storage, usually in the form of a micro SD card. To make file sharing easier, external storage was formatted using the FAT filesystem, which lacks file permissions. As a result, files on the SD card could be read and written by anyone (any app). To prevent users from simply copying paid apps off the SD card, Froyo created an encrypted filesystem image file and stored the APK in it when you opted to move the app to external storage. The image was then mounted at runtime using Linux's device-mapper and the system would load the app files from the newly created mount point (one per app). Building on this, JB makes the container EXT4, which allows for permissions. A typical forward locked app's mount point now looks like this:

shell@android:/mnt/asec/org.mypackage-1 # ls -l
ls -l
drwxr-xr-x system   system            2012-07-16 15:07 lib
drwx------ root     root              1970-01-01 09:00 lost+found
-rw-r----- system   u0_a96    1319057 2012-07-16 15:07 pkg.apk
-rw-r--r-- system   system     526091 2012-07-16 15:07 res.zip

Here the res.zip holds app resources and is world-readable, while the pkg.apk file which hold the full APK is only readable by the system and the app's dedicated user (u0_a96). The actual app containers are stored in /data/app-asec with filenames in the form pacakge.name-1.asec. ASEC container management (creating/deleting and mounting/unmounting) is implemented int the system volume daemon (vold) and framework services talk to it by sending commands via a local socket. We can use the vdc utility to manage forward locked apps from the shell:

# vdc asec list
vdc asec list
111 0 com.mypackage-1
111 0 org.foopackage-1
200 0 asec operation succeeded

# vdc asec unmount org.foopackage-1
200 0 asec operation succeeded

# vdc asec mount org.foopackage-1 000102030405060708090a0b0c0d0e0f 1000
org.foopackage-1 000102030405060708090a0b0c0d0e0f  1000                    
200 0 asec operation succeeded

# vdc asec path org.foopackage-1
vdc asec path org.foopackage-1
211 0 /mnt/asec/org.foopackage-1

All commands take a namespace ID (based on the package name in practice) as a parameter, and for the mount command you need to specify the encryption key and the mount point's owner UID (1000 is system) as well. That about covers how apps are stored and used, what's left is to find out the actual encryption algorithm and the key. Both are unchanged from the original Froyo apps-to-SD implementation: Twofish with a 128-bit key stored in /data/misc/systemkeys:

shell@android:/data/misc/systemkeys # ls
ls
AppsOnSD.sks
shell@android:/data/misc/systemkeys # od -t x1 AppsOnSD.sks
od -t x1 AppsOnSD.sks
0000000 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
0000020

Forward locking an application is triggered by specifying the -l option of the pm install command or specifying the INSTALL_FORWARD_LOCK flag to PackageManager's installPackage* methods (see sample app).

All of this is quite interesting, but as we have seen, installing apps, encrypted or otherwise, requires system permissions, so it can only be used by custom carrier Android firmware and probably the next version of your friendly CyanogenMod ROM. Currently the only app that takes advantage of the new encrypted apps and forward locking infrastructure is the Play Store (who comes up with those names, really?) Android client. Describing exactly how the Google Play client works would require detailed knowledge of the underlying protocol (which is always a moving target), but a casual look at the newest Android client does reveal a few useful pieces of information. Google Play servers send quite a bit of metadata about the app you are about to download and install, such as download URL, APK file size, version code and refund window. New among those are the EncryptionParams which look very similar to the ContainerEncryptionParams shown above:

class AndroidAppDelivery$EncryptionParams {
  private int cachedSize;
  private String encryptionKey;
  private String hmacKey;
  private int version;
}

shell@android:/data/app # ls -l|grep -i beautiful
ls -l|grep -i beautiful
-rw-r--r-- system   system    6046274 2012-08-06 10:45 com.levelup.beautifulwidgets-1.apk