Revisiting Android disk encryption

In iOS 8, Apple has expanded the scope of data encryption and now mixes in the user's passcode with an unextractable hardware UID when deriving an encryption key, making it harder to extract data from iOS 8 devices. This has been somewhat of a hot topic lately, with opinions ranging from praise for Apple's new focus on serious security, to demands for "golden keys" to mobile devices to be magically conjured up. Naturally, the debate has spread to other OS's, and Google has announced that the upcoming Android L release will also have disk encryption enabled by default. Consequently, questionsand speculation about the usefulness and strength of Android's disk encryption have sprung up on multiple forums, so this seems like a good time to take another look at its implementation. While Android L still hasn't been released yet, some of the improvements to disk encryption it introduces are apparent in the preview release, so this post will briefly introduce them as well.

This post will focus on the security level of disk encryption, for more details on its integration with the platform, see Chapter 10 of my book -- ' Android Security Internals' (early access full PDF is available now, print books should ship by end of October).

Android 3.0-4.3

Full disk encryption (FDE) for Android was introduced in version 3.0 (Honeycomb) and didn't change much until version 4.4 (discussed in the next section). Android's FDE uses the dm-crypt target of Linux's device mapper framework to implement transparent disk encryption for the userdata (mounted as /data) partition. Once encryption is enabled, all writes to disk automatically encrypt data before committing it to disk and all reads automatically decrypt data before returning it to the calling process. The disk encryption key (128-bit, called the 'master key') is randomly generated and protected by the lockscreen password. Individual disk sectors are encrypted by the master key using AES in CBC mode, with ESSIV:SHA256 to derive sector IVs.

Android uses a so called 'crypto footer' structure to store encryption parameters. It is very similar to the encrypted partition header used by LUKS (Linux Unified Key Setup), but is simpler and omits several LUKS features. While LUKS supports multiple key slots, allowing for decryption using multiple passphrases, Android's crypto footer only stores a single copy of the encrypted master key and thus supports a single decryption passphrase. Additionally, while LUKS splits the encrypted key in multiple 'stripes' in order to reduce the probability of recovering the full key after it has been deleted from disk, Android has no such feature. Finally, LUKS includes a master key checksum (derived by running the master key through PBKDF2), which allows to check whether the entered passphrase is correct without decrypting any of the disk data. Android's crypto footer doesn't include a master key checksum, so the only way to check whether the entered passphrase is correct is to try and mount the encrypted partition. If the mount succeeds, the passphrase is considered correct.

Here's how the crypto footer looks in Android 4.3 (version 1.0).

struct crypt_mnt_ftr {  __le32 magic;   __le16 major_version;  __le16 minor_version;  __le32 ftr_size;  __le32 flags;   __le32 keysize;  __le32 spare1;  __le64 fs_size;  __le32 failed_decrypt_count;   unsigned char crypto_type_name[MAX_CRYPTO_TYPE_NAME_LEN]; };

The structure includes the version of the FDE scheme, the key size, some flags and the name of the actual disk encryption cipher mode (aes-cbc-essiv:sha256). The crypto footer is immediately followed by the encrypted key and a 16-bit random salt value. In this initial version, a lot of the parameters are implicit and are therefore not included in the crypto footer. The master key is encrypted using an 128-bit AES key (key encryption key, or KEK) derived from an user-supplied passphrase using 2000 iteration of PBKDF2. The derivation process also generates an IV, which is used to encrypt the master key in CBC mode. When an encrypted device is booted, Android takes the passphrase the user has entered, runs it through PBKDF2, decrypts the encrypted master key and passes it to dm-crypt in order to mount the encrypted userdata partition.

Bruteforcing FDE 1.0

The encryption scheme described in the previous section is considered relatively secure, but because it is implemented entirely in software, it's security depends entirely on the complexity of the disk encryption passphrase. If it is sufficiently long and complex, bruteforcing the encrypted master key could take years. However, because Android has chosen to reuse the losckreen PIN or password (maximum length 16 characters), in practice most people are likely to end up with a relatively short or low-entropy disk encryption password. While the PBKDF2 key derivation algorithm has been designed to work with low-entropy input, and requires considerable computational effort to bruteforce, 2000 iterations are not a significant hurdle even to current off-the-shelf hardware. Let's see how hard it is to bruteforce Android FDE 1.0 in practice.

Bruteforcing on the device is obviously impractical due to the limited processing resources of Android devices and the built-in rate limiting after several unsuccessful attempts. A much more practical approach is to obtain a copy of the crypto footer and the encrypted userdata partition and try to guess the passphrase offline, using much more powerful hardware. Obtaining a raw copy of a disk partition is usually not possible on most commercial devices, but can be achieved by booting a specialized data acquisition boot image signed by the device manufacturer, exploiting a flaw in the bootloader that allows unsigned images to be booted (such as this one), or simply by booting a custom recovery image on devices with an unlocked bootloader (a typical first step to 'rooting').

Once the device has been booted, obtaining a copy of the userdata partition is straightforward. The crypto footer however, despite its name, typically resides on a dedicated partition on recent devices. The name of the partition is specified using the encryptable flag in the device's fstab file. For example, on the Galaxy Nexus, the footer is on the metadata partition as shown below.

/dev/block/platform/omap/omap_hsmmc.0/by-name/userdata  /data  ext4  \noatime,nosuid,nodev,nomblk_io_submit,errors=panic \wait,check,encryptable=/dev/block/platform/omap/omap_hsmmc.0/by-name/metadata

Once we know the name of the partition that stores the crypto footer it can be copied simply by using thedd command.

Very short passcodes (for example a 4-digit PIN) can be successfully bruteforced using a script (this particular one is included in Santoku Linux) that runs on a desktop CPU. However, much better performance can be achieved on a GPU, which has been specifically designed to execute multiple tasks in parallel. PBKDF2 is an iterative algorithm based on SHA-1 (SHA-2 can also be used) that requires very little memory for execution and lends itself to paralellization. One GPU-based, high-performance PBKDF2 implementation is found in the popular password recovery tool hashcat. Version 1.30 comes with a built-in Android FDE module, so recovering an Android disk encryption key is as simple as parsing the crypto footer and feeding the encrypted key, salt, and the first several sectors of the encrypted partition to hashcat. As we noted in the previous section, the crypto footer does not include any checksum of the master key, so the only way to check whether the decrypted master key is the correct one is to try to decrypt the disk partition and look for some known data. Because most current Android devices use the ext4 filesystem, hashcat (and other similar tools) look for patterns in the ext4 superblock in order to confirm whether the tried passphrase is correct.

The Android FDE input for hashcat includes the salt, encrypted master key and the first 3 sectors of the encrypted partition (which contain a copy of the 1024-byte ext4 superblock). The hashcat input file might look like this (taken from the hashcat example hash):

$fde$16$ca56e82e7b5a9c2fc1e3b5a7d671c2f9$16$7c124af19ac913be0fc137b75a34b20d$eac806ae7277c8d4...

On a device that uses a six-digit lockscreen PIN, the PIN, and consequently the FDE master key can be recovered with the following command:

$ cudaHashcat64 -m 8800 -a 3 android43fde.txt ?d?d?d?d?d?d...Session.Name...: cudaHashcatStatus.........: CrackedInput.Mode.....: Mask (?d?d?d?d?d?d) [6]Hash.Target....: $fde$16$aca5f840...Hash.Type......: Android FDETime.Started...: Sun Oct 05 19:06:23 2014 (6 secs)Speed.GPU.#1...:    20629 H/sRecovered......: 1/1 (100.00%) Digests, 1/1 (100.00%) SaltsProgress.......: 122880/1000000 (12.29%)Skipped........: 0/122880 (0.00%)Rejected.......: 0/122880 (0.00%)HWMon.GPU.#1...:  0% Util, 48c Temp, N/A FanStarted: Sun Oct 05 19:06:23 2014Stopped: Sun Oct 05 19:06:33 2014

Even when run on the GPU of a mobile computer (NVIDIA GeForce 730M), hashcat can achieve more then 20,000 PBKDF2 hashes per second, and recovering a 6 digit PIN takes less than 10 seconds. On the same hardware, a 6-letter (lowercase only) password takes about 4 hours.

As you can see, bruteforcing a simple PIN or password is very much feasible, so choosing a strong lockscreen password is vital. Lockscreen password strength can be enforced by installing a device administrator that sets password complexity requirements. Alternatively, a dedicated disk encryption password can be set on rooted devices using the shell or a dedicated application. CyanogenMod 11 supports setting a dedicated disk encryption password out of the box, and one can be set via system Settings, as shown below.

Android 4.4

Android 4.4 adds several improvements to disk encryption, but the most important one is replacing the PBKDF2 key derivation function (KDF) with scrypt. scrypt has been specifically designed to be hard to crack on GPUs by requiring a large (and configurable) amount of memory. Because GPUs have a limited amount of memory, executing multiple scrypt tasks in parallel is no longer feasible, and thus cracking scrypt is much slower than PBKDF2 (or similar hash-based KDFs). As part of the upgrade process to 4.4, Android automatically updates the crypto footer to use scrypt and re-encrypts the master key. Thus every device running Android 4.4 (devices using a vendor-proprietary FDE scheme excluded) should have its FDE master key protected using an scrypt-derived key.

The Android 4.4 crypto footer looks like this (version 1.2):

struct crypt_mnt_ftr {  __le32 magic;   __le16 major_version;  __le16 minor_version;  __le32 ftr_size;   __le32 flags;   __le32 keysize;  __le32 spare1;  __le64 fs_size;  __le32 failed_decrypt_count;  unsigned char crypto_type_name[MAX_CRYPTO_TYPE_NAME_LEN];  __le32 spare2;   unsigned char master_key[MAX_KEY_LEN];  unsigned char salt[SALT_LEN];  __le64 persist_data_offset[2];   __le32 persist_data_size;      __le8  kdf_type;   /* scrypt parameters. See www.tarsnap.com/scrypt/scrypt.pdf */  __le8  N_factor; /* (1 << N) */  __le8  r_factor; /* (1 << r) */  __le8  p_factor; /* (1 << p) */};

As you can see, the footer now includes an explicit kdf_type which specifies the KDF used to derive the master key KEK. The values of the scrypt initialization parameters (N, r and p) are also included. The master key size (128-bit) and disk sector encryption mode (aes-cbc-essiv:sha256) are the same as in 4.3.

Bruteforcing the master key now requires parsing the crypto footer, initializing scrypt and generating all target PIN or password combinations. As the 1.2 crypto footer still does not include a master key checksum, checking whether the tried PIN or password is correct again requires looking for known plaintext in the ext4 superblock.

While hashcat does support scrypt since version 1.30, it is not much more efficient (and in fact can be slower) than running scrypt on a CPU. Additionally, the Android 4.4 crypto footer format is not supported, so hashcat cannot be used to recover Android 4.4 disk encryption passphrases as is.

Instead, the Santoku Linux FDE bruteforcer Python script can be extended to support the 1.2 crypto footer format and the scrypt KDF. A sample (and not particularly efficient) implementation can be found here. It might produce the following output when run on a 3.50GHz Intel Core i7 CPU:

$ time python bruteforce_stdcrypto.py header footer 4Android FDE crypto footer-------------------------Magic          : 0xD0B5B1C4Major Version  : 1Minor Version  : 2Footer Size    : 192 bytesFlags          : 0x00000000Key Size       : 128 bitsFailed Decrypts: 0Crypto Type    : aes-cbc-essiv:sha256Encrypted Key  : 0x66C446E04854202F9F43D69878929C4ASalt           : 0x3AB4FA74A1D6E87FAFFB74D4BC2D4013KDF            : scryptN_factor       : 15     (N=32768)r_factor       : 3      (r=8)p_factor       : 1      (p=2)-------------------------Trying to Bruteforce Password... please waitTrying: 0000Trying: 0001Trying: 0002Trying: 0003...Trying: 1230Trying: 1231Trying: 1232Trying: 1233Trying: 1234Found PIN!: 1234real    4m43.985suser    4m34.156ssys     0m9.759s

As you can see, trying 1200 PIN combinations requires almost 5 minutes, so recovering a simple PIN is no longer instantaneous. That said, cracking a short PIN or password is still very much feasible, so choosing a strong locksreen password (or a dedicated disk encryption password, when possible) is still very important.

Android L

A preview release of the upcoming Android version (referred to as 'L') has been available for several months now, so we can observe some of expected changes to disk encryption. If we run the crypto footer obtained from an encrypted Android L device through the script introduced in the previous section, we may get the following output:

$ ./bruteforce_stdcrypto.py header L_footer 4Android FDE crypto footer-------------------------Magic          : 0xD0B5B1C4Major Version  : 1Minor Version  : 3Footer Size    : 2288 bytesFlags          : 0x00000000Key Size       : 128 bitsFailed Decrypts: 0Crypto Type    : aes-cbc-essiv:sha256Encrypted Key  : 0x825F3F10675C6F8B7A6F425599D9ECD7Salt           : 0x0B9C7E8EA34417ED7425C3A3CFD2E928KDF            : unknown (3)N_factor       : 15     (N=32768)r_factor       : 3      (r=8)p_factor       : 1      (p=2)-------------------------...

As you can see above, the crypto footer version has been upped to 1.3, but the disk encryption cipher mode and key size have not changed. However, version 1.3 uses a new, unknown KDF specified with the constant 3 (1 is PBKDF2, 2 is scrypt). Additionally, encrypting a device no longer requires setting a lockscreen PIN or password, which suggests that the master key KEK is no longer directly derived from the lockscreen password. Starting the encryption process produces the following logcat output:

D/QSEECOMAPI: (  178): QSEECom_start_app sb_length = 0x2000D/QSEECOMAPI: (  178): App is already loaded QSEE and app id = 1D/QSEECOMAPI: (  178): QSEECom_shutdown_app D/QSEECOMAPI: (  178): QSEECom_shutdown_app, app_id = 1...I/Cryptfs (  178): Using scrypt with keymaster for cryptfs KDFD/QSEECOMAPI: (  178): QSEECom_start_app sb_length = 0x2000D/QSEECOMAPI: (  178): App is already loaded QSEE and app id = 1D/QSEECOMAPI: (  178): QSEECom_shutdown_app D/QSEECOMAPI: (  178): QSEECom_shutdown_app, app_id = 1

As discussed in a previous post, 'QSEE' stands for Qualcomm Secure Execution Environment, which is an ARM TrustZone-based implementation of a TEE. QSEE provides the hardware-backed credential store on most devices that use recent Qualcomm SoCs. From the log above, it appears that Android's keymaster HAL module has been extended to store the disk encryption key KEK in hardware-backed storage (Cf. 'Using scrypt with keymaster for cryptfs KDF' in the log above). The log also mentions scrypt, so it is possible that the lockscreen password (if present) along with some key (or seed) stored in the TEE are fed to the KDF to produce the final master key KEK. However, since no source code is currently available, we cannot confirm this. That said, setting an unlock pattern on an encrypted Android L device produces the following output, which suggests that the pattern is indeed used when generating the encryption key:

D/VoldCmdListener(  173): cryptfs changepw pattern {}D/QSEECOMAPI: (  173): QSEECom_start_app sb_length = 0x2000D/QSEECOMAPI: (  173): App is already loaded QSEE and app id = 1...D/QSEECOMAPI: (  173): QSEECom_shutdown_app D/QSEECOMAPI: (  173): QSEECom_shutdown_app, app_id = 1I/Cryptfs (  173): Using scrypt with keymaster for cryptfs KDFD/QSEECOMAPI: (  173): QSEECom_start_app sb_length = 0x2000D/QSEECOMAPI: (  173): App is already loaded QSEE and app id = 1D/QSEECOMAPI: (  173): QSEECom_shutdown_app D/QSEECOMAPI: (  173): QSEECom_shutdown_app, app_id = 1E/VoldConnector(  756): NDC Command {5 cryptfs changepw pattern [scrubbed]} took too long (6210ms)

As you can be see in the listing above, the cryptfs changepw command, which is used to send instructions to Android's vold daemon, has been extended to support a pattern, in addition to the previously supported PIN/password. Additionally, the amount of time the password change takes (6 seconds) suggests that the KDF (scrypt) is indeed being executed to generate a new encryption key. Once we've set a lockscreen unlock pattern, booting the device now requires entering the pattern, as can be seen in the screenshot below. Another subtle change introduced in Android L, is that when booting an encrypted device the lockscreen pattern, PIN or password needs to be entered only once (at boot time), and not twice (once more on the lockscreen, after Android boots) as it was in previous versions.

While no definitive details are available, it is fairly certain that (at least on high-end devices), Android's disk encryption key(s) will have some hardware protection in Android L. Assuming that the implementation is similar to that of the hardware-backed credential store, disk encryption keys should be encrypted by an unextractable key encryption key stored in the SoC, so obtaining a copy of the crypto footer and the encrypted userdata partition, and bruteforcing the lockscreen passphrase should no longer be sufficient to decrypt disk contents. Disk encryption in the Android L preview (at least on a Nexus 7 2013) feels significantly faster (encrypting the 16GB data partition takes about 10 minutes), so it is most probably hardware-accelerated as well (or the initial encryption is only encrypting disk blocks that are actually in use, and not every single block as in previous versions). However, it remains to be seen whether high-end Android L devices will include a dedicated crypto co-processor akin to Apple's 'Secure Enclave'. While the current TrustZone-based key protection is much better than the software only implementation found in previous versions, a flaw in the secure TEE OS or any of the trusted TEE applications could lead to extracting hardware-protected keys or otherwise compromising the integrity of the system.

Summary

Android has included full disk encryption (FDE) support since version 3.0, but versions prior to 4.4 used a fairly easy to bruteforce key derivation function (PBKDF2 with 2000 iterations). Additionally, because the disk encryption password is the same as the lockscreen one, most users tend to use simple PINs or passwords (unless a device administrator enforces password complexity rules), which further facilitates bruteforcing. Android 4.4 replaced the disk encryption KDF with scrypt, which is much harder to crack and cannot be implemented efficiently on off-the-shelf GPU hardware. In addition to enabling FDE out of the box, Android L is expected to include hardware protection for disk encryption keys, as well as hardware acceleration for encrypted disk access. These two features should make FDE on Android both more secure and much faster.

[Note that the discussion in this post is based on "stock Android" as released by Google (references source code is from AOSP). Some device vendors implement slightly different encryption schemes, and hardware-backed key storage and/or hardware acceleration are already available via vendor extensions on some high-end devices.]Posted 1 week ago by Nikolay Elenkov

http://nelenkov.blogspot.com/2014/10/revisiting-android-disk-encryption.html

//转//Revisiting Android disk encryption