Android Explorations

Android's verified boot implementation is based on the dm-verity device-mapper block integrity checking target. Device-mapper is a Linux kernel framework that provides a generic way to implement virtual block devices. It is used to implement volume management (LVM), full-disk encryption (dm-crypt), RAIDs and even distributed replicated storage (DRBD). Device-mapper works by essentially mapping a virtual block device to one or more physical block devices, optionally modifying transferred data in transit. For example, dm-crypt decrypts read physical blocks and encrypts written blocks before committing them to disk. Thus disk encryption is transparent to users of the virtual dm-crypt block device. Device-mapper targets can be stacked on top of each other, making it possible to implement complex data transformations. 

As we mentioned, dm-verity is a block integrity checking target. What this means is that it transparently verifies the integrity of each device block as it is being read from disk. If the block checks out, the read succeeds, and if not -- the read generates an I/O error as if the block was physically corrupt. Under the hood dm-verity is implemented using a pre-calculated hash tree which includes the hashes of all device blocks. The leaf nodes of the tree include hashes of physical device blocks, while intermediate nodes are hashes of their child nodes (hashes of hashes). The root node is called the root hash and is based on all hashes in lower levels (see figure below). Thus a change even in a single device block will result in a change of the root hash. Therefore in order to verify a hash tree we only need to verify its root hash. At runtime dm-verity calculates the hash of each block when it is read and verifies it using the pre-calculated hash tree. Since reading data from a physical device is already a time consuming operation, the latency added by hashing and verification as relatively low.

[Image from Android dm-verity documentation,  licensed under Creative Commons Attribution 2.5]

Because dm-verity depends on a pre-calculated hash tree over all blocks of a device, the underlying device needs to be mounted read-only for verification to be possible. Most filesystems record mount times in their superblock or similar metadata, so even if no files are changed at runtime, block integrity checks will fail if the underlying block device is mounted read-write. This can be seen as a limitation, but it works well for devices or partitions that hold system files, which are only changed by OS updates. Any other change indicates either OS or disk corruption, or a malicious program that is trying to modify the OS or masquerade as a system file. dm-verity's read-only requirement also fits well with Android's security model, which only hosts application data on a read-write partition, and keeps OS files on the read-only system partition.

dm-verity was originally developed in order to implement verified boot in Chrome OS, and was integrated into the Linux kernel in version 3.4. It is enabled with the CONFIG_DM_VERITY kernel configuration item. Like Chrome OS, Android 4.4 also uses the kernel's dm-verity target, but the cryptographic verification of the root hash and mounting of verified partitions are implemented differently from Chrome OS.

The RSA public key used for verification is embedded in the boot partition under the verity_key filename and is used to verify the dm-verity mapping table. This mapping table holds the locations of the target device and the offset of the hash table, as well as the root hash and salt. The mapping table and its signature are part of the verity metablock which is written to disk directly after the last filesystem block of the target device. A partition is marked as verifiable by adding the verify flag to the Android-specific fs_mgr flags filed of the device's fstab file. When Android's filesystem manager encounters the verify flag in fstab, it loads the verity metadata from the block device specified in fstab and verifies its signature using the verity_key. If the signature check succeeds, the filesystem manager parses the dm-verity mapping table and passes it to the Linux device-mapper, which use the information contained in the mapping table in order to create a virtual dm-verity block device. This virtual block device is then mounted at the mount point specified in fstab in place of the corresponding physical device. As a result, all reads from the underlying physical device are transparently verified against the pre-generated hash tree. Modifying or adding files, or even remounting the partition in read-write mode, results in an integrity verification failure and an I/O error.

We must note that as dm-verity is a kernel feature, in order for the integrity protection it provides to be effective, the kernel the device boots needs to be trusted. On Android, this means verifying the boot partition, which also includes the root filesystem RAM disk (initrd) and the verity public key. This process is device-specific and is typically implemented in the device bootloader, usually by using an unmodifiable verification key stored in hardware to verify the boot partition's signature.

Enabling verified boot

The official documentation describes the steps required to enable verified boot on Android, but lacks concrete information about the actual tools and commands that are needed. In this section we show the commands required to create and sign a dm-verity hash table and demonstrate how to configure an Android device to use it. Here is a summary of the required steps: 

A dm-verity hash tree is generated with the dedicated veritysetup program. veritysetup can operate directly on block devices or use filesystem images and write the hash table to a file. It is supposed to produce platform-independent output, but hash tables produced on desktop Linux didn't quite agree with Android, so for this example we'll generate the hash tree directly on the device. To do this we first need to compile veritysetup for Android. A project that generates a statically linked veritysetup binary is provided on Github. It uses the OpenSSL backend for hash calculations and has only been slightly modified (in a not too portable way...), to allow for the different size of the off_t data type, which is 32-bit in current versions of Android's bionic library. 

In order to add the hash tree directly to the system partition, we first need to make sure that there is enough space to hold the hash tree and the verity metadata block (32k) after the last filesystem block. As most devices typically use the whole system partition, you may need to modify the BOARD_SYSTEMIMAGE_PARTITION_SIZE value in your device's BoardConfig.mk to allow for storing verity data. After you have adjusted the size of the system partition, transfer the veritysetup binary to the cache or data partitions of the device, and boot a recovery that allows root shell access over ADB. To generate and write the hash tree to the device we use the veritysetup format command as shown below.

# veritysetup --debug --hash-offset 838893568 --data-blocks 204800 format \
/dev/block/mmcblk0p21 /dev/block/mmcblk0p21
...
# Updating VERITY header of size 512 on device /dev/block/mmcblk0p21, offset 838893568.
VERITY header information for /dev/block/mmcblk0p21
UUID:                 0dd970aa-3150-4c68-abcd-0b8286e6000
Hash type:            1
Data blocks:          204800
Data block size:      4096
Hash block size:      4096
Hash algorithm:       sha256
Salt:                 1f951588516c7e3eec3ba10796aa17935c0c917475f8992353ef2ba5c3f47bcb
Root hash:            5f061f591b51bf541ab9d89652ec543ba253f2ed9c8521ac61f1208267c3bfb1

This example was executed on a Nexus 4, make sure you use the correct block device for your phone instead of /dev/block/mmcblk0p21. The --hash-offset parameter is needed because we are writing the hash tree to the same device that holds filesystem data. It is specified in bytes (not blocks) and needs to point to a location after the verity metadata block. Adjust according to your filesystem size so that hash_offset > filesystem_size + 32k. The next parameter, --data-blocks, specifies the number of blocks used by the filesystem. The default block size is 4096, but you can specify a different size using the --data-block-size parameter. This value needs to match the size allocated to the filesystem with BOARD_SYSTEMIMAGE_PARTITION_SIZE. If the command succeeds it will output the calculated root hash and the salt value used, as shown above. Everything but the root hash is saved in the superblock (first block) of the hash table. Make sure you save the root hash, as it is required to complete the verity setup.

Once you have the root hash and salt, you can generate and sign the dm-verity table. The table is a single line that contains the name of the block device, block sizes, offsets, salt and root hash values. You can use the gentable.py script (edit constant values accordingly first) to generate it or write it manually based on the output of veritysetup. See dm-verity's documentation for details about the format. For our example it looks like this (single line, split for readability):

1 /dev/block/mmcblk0p21 /dev/block/mmcblk0p21 4096 4096 204800 204809 sha256 \
5f061f591b51bf541ab9d89652ec543ba253f2ed9c8521ac61f1208267c3bfb1 \
1f951588516c7e3eec3ba10796aa17935c0c917475f8992353ef2ba5c3f47bcb 

Next, generate a 2048-bit RSA key and sign the table using OpenSSL. You can use the command bellow or the sign.sh script on Github.

$ openssl dgst -sha1 -sign verity-key.pem -out table.sig table.bin

Once you have a signature you can generate the verity metadata block, which includes a magic number (0xb001b001) and the metadata format version, followed by the RSA PKCS#1.5 signature blob and table string, padded with zeros to 32k. You can generate the metadata block with the mkverity.py script by passing the signature and table files like this:

$ ./mkverity.py table.sig table.bin verity.bin

Next, write the generated verity.bin file to the system partition using dd  or a similar tool, right after the last filesystem block and before the start of the verity hash table. Using the same number of data blocks passed to veritysetup, the needed command (which also needs to be executed in recovery) becomes:

# dd if=verity.bin of=/dev/block/mmcblk0p21 bs=4096 seek=204800

Finally, you can check that the partition is properly formatted using the veritysetup verify command as shown below, where the last parameter is the root hash:

# veritysetup --debug --hash-offset 838893568 --data-blocks 204800 verify \
/dev/block/mmcblk0p21 /dev/block/mmcblk0p21 \
5f061f591b51bf541ab9d89652ec543ba253f2ed9c8521ac61f1208267c3bfb1

If verification succeeds, reboot the device and verify that the device boots without errors. If it does, you can proceed to the next step: add the verification key to the boot image and enable automatic integrity verification.

The RSA public key used for verification needs to be in mincrypt format (also used by the stock recovery when verifying OTA file signatures), which is a serialization of mincrypt's RSAPublicKey structure. The interesting thing about this structure is that ts doesn't simply include the modulus and public exponent values, but contains pre-computed values used by mincrypt's RSA implementation (based on Montgomery reduction). Therefore converting an OpenSSL RSA public key to mincrypt format requires some modular operations and is not simply a binary format conversion. You can convert the PEM key using the pem2mincrypt tool (conversion code shamelessly stolen from secure adb's implementation). Once you have converted the key, include it in the root of your boot image under the verity_key filename. The last step is to modify the device's fstab file in order to enable block integrity verification for the system partition. This is simply a matter of adding the verify flag, as shown below:

/dev/block/platform/msm_sdcc.1/by-name/system  /system  ext4  ro, barrier=1  wait,verify

Next, verify that your kernel configuration enable CONFIG_DM_VERITY, enable it if needed and build your boot image. Once you have boot.img, you can try booting the device with it using fastboot boot boot.img (without flashing it). If the hash table and verity metadata blcok have been generated and written correctly, the device should boot, and /system should be a mount of the automatically created device-mapper virtual device, as shown below. If the boot is successful, you can permanently flash the boot image to the device.

# mount|grep system
/dev/block/dm-0 /system ext4 ro,seclabel,relatime,data=ordered 0 0

Now any modifications to the system partition will result in read errors when reading the corresponding file(s). Unfortunately, system modifications by file-based OTA updates, which modify file blocks without updating verity metadata, will also invalidate the hash tree. As mentioned in the official documentation, in order to be compatible with dm-verity verified boot, OTA updates should also operate at the block level, ensuring that both file blocks and the hash tree and metadata are updated. This requires changing the current OTA update infrastructure, which is probably one of the reasons verified boot hasn't been deployed to production devices yet.

Summary

Android includes a verified boot implementation based on the dm-verity device-mapper target since version 4.4. dm-verity is enabled by adding a hash table and a signed metadata block to the system partition and specifying the verify flag in the device's fstab file. At boot time Android verifies the metadata signature and uses the included device-mapper table to create and mount a virtual block device at /system. As a result, all reads from /system are verified against the dm-verity hash tree, and any modification to the system partition results in I/O errors.