How does Marshmallow encryption work technically?

I just installed Marshmallow on a Nexus 5 through a pushed update. I am confused about the way encryption works. I have good technical knowledge of encryption on computers. I would like to gain similar knowledge about Android 6.

The following is what I did and how I got confused. After a factory reset I setup a PIN then encrypted the device. At boot it asked me for my PIN, which was expected. I then removed the PIN and restarted the device. It did not ask for any PIN at boot but the device still reported itself as encrypted in the setup menu. The latter is what confuses me as I expected the PIN to unlock the decryption key.

Questions:

• In the case of encryption without a PIN, where does the decryption key come from? I assume it is stored on a chip similar to a TPM, is this correct? If so what prevents a hacker from requesting this key from the chip? Does it check the hash of the firmware? Anything else? Technical details would be much appreciated.



• In the case of encryption with a PIN, is the PIN used as an extra token to access the decryption key? Or does the decryption process work exactly as if there was no PIN.

TL;DL answer:

The decryption key is unlocked with all of the following:

• The PIN (or password, etc.) or a default password if there is none


• A TEE (a hardware-backed signature generator which uses keys that cannot be extracted)


• A salt (readily available but preventing rainbow tables attacks)

Answer

I'm quoting from the Android Manual here, but:

NOTE:

The source I have used is not directly relevant to Marshmallow but is relevant to Lollipop and higher.

I'll just address the OP's questions now. Technical details will follow.

1. 
   

   The default encryption key comes from a hardware source (a chip similar to a TPM) and the default password of AOSP defined as default_password in the cryptfs.c source file, see below.

   
   


2. 
   
   

   Yes, not just the default, but any password is made into a key and is stored on a TPM-like chip, called a TEE (short for "Trusted Execution Environment", see below for further details).

   
   


3. 
   

   A hacker with UART/JTAG access to the chips on the SoC of the device could technically get access to the TEE key, or a custom kernel can leak this information to a hacker. Some 3-letter agencies in conspiracy theories can possibly partner with the OEM to get these insecure kernels used in production devices, but I wouldn't lay many stores by it. Again, see the last section of this answer for further details.

   
   

The only thing stopping a hacker from getting access to the key is the sheer amount of effort required to do so.

4. Checking the hash of (checksumming) the firmware (called "Verified Boot" by Google) is in fact done on and above Lollipop by default (and is available from JellyBean 4.3 onwards), by a kernel module called dm-verity. However, this is independent of encryption status.

Source: AOSP security guide here.

5. About the process involved in decrypting the system with a custom password, see below. I'll just tell you here that the user password is involved in both creation and usage of the encryption key.

Upon first boot, the device creates a randomly generated 128-bit master key and then hashes it with a default password and stored salt. The default password is: "default_password" However, the resultant hash is also signed through a TEE (such as TrustZone), which uses a hash of the signature to encrypt the master key.

You can find the default password defined in the Android Open Source Project cryptfs.c file.

When the user sets the PIN/pass or password on the device, only the 128-bit key is re-encrypted and stored. (ie. user PIN/pass/pattern changes do NOT cause re-encryption of userdata partition.)

Starting an encrypted device with default encryption

This is what happens when you boot up an encrypted device with no password. Because Android 5.0 devices are encrypted on first boot, there should be no set password and therefore this is the default encryption state.

1. Detect encrypted /data with no password

Detect that the Android device is encrypted because /data cannot be mounted and one of the flags encryptable or forceencrypt is set.

vold sets vold.decrypt to trigger_default_encryption, which starts the defaultcrypto service. trigger_default_encryption checks the encryption type to see if /data is encrypted with or without a password.

2. Decrypt /data

Creates the dm-crypt device over the block device so the device is ready for use.

3. Mount /data

vold then mounts the decrypted real /data partition and then prepares the new partition. It sets the property vold.post_fs_data_done to 0 and then sets vold.decrypt to trigger_post_fs_data. This causes init.rc to run its post-fs-data commands. They will create any necessary directories or links and then set vold.post_fs_data_done to 1.

Once vold sees the 1 in that property, it sets the property vold.decrypt to: trigger_restart_framework. This causes init.rc to start services in class main again and also start services in class late_start for the first time since boot.

4. Start framework

Now the framework boots all its services using the decrypted /data, and the system is ready for use.

Starting an encrypted device without default encryption

This is what happens when you boot up an encrypted device that has a set password. The device’s password can be a pin, pattern, or password.

1. Detect encrypted device with a password

Detect that the Android device is encrypted because the flag ro.crypto.state = "encrypted"

vold sets vold.decrypt to trigger_restart_min_framework because /data is encrypted with a password.

2. Mount tmpfs

init sets five properties to save the initial mount options given for /data with parameters passed from init.rc. vold uses these properties to set up the crypto mapping:

ro.crypto.fs_type

ro.crypto.fs_real_blkdev

ro.crypto.fs_mnt_point

ro.crypto.fs_options

ro.crypto.fs_flags (ASCII 8-digit hex number preceded by 0x)

3. Start framework to prompt for password

The framework starts up and sees that vold.decrypt is set to trigger_restart_min_framework. This tells the framework that it is booting on a tmpfs /data disk and it needs to get the user password.

First, however, it needs to make sure that the disk was properly encrypted. It sends the command cryptfs cryptocomplete to vold. vold returns 0 if encryption was completed successfully, -1 on internal error, or -2 if encryption was not completed successfully. vold determines this by looking in the crypto metadata for the CRYPTO_ENCRYPTION_IN_PROGRESS flag. If it's set, the encryption process was interrupted, and there is no usable data on the device.

If vold returns an error, the UI should display a message to the user to reboot and factory-reset the device, and give the user a button to press to do so.

4. Decrypt data with password

Once cryptfs cryptocomplete is successful, the framework displays a UI asking for the disk password. The UI checks the password by sending the command cryptfs checkpw to vold. If the password is correct (which is determined by successfully mounting the decrypted /data at a temporary location, then unmounting it), vold saves the name of the decrypted block device in the property ro.crypto.fs_crypto_blkdev and returns status 0 to the UI. If the password is incorrect, it returns -1 to the UI.

5. Stop framework

The UI puts up a crypto boot graphic and then calls vold with the command cryptfs restart. vold sets the property vold.decrypt to trigger_reset_main, which causes init.rc to do class_reset main. This stops all services in the main class, which allows the tmpfs /data to be unmounted.

6. Mount /data

vold then mounts the decrypted real /data partition and prepares the new partition (which may never have been prepared if it was encrypted with the wipe option, which is not supported in the first release). It sets the property vold.post_fs_data_done to 0 and then sets vold.decrypt to trigger_post_fs_data. This causes init.rc to run its post-fs-data commands. They will create any necessary directories or links and then set vold.post_fs_data_done to 1. Once vold sees the 1 in that property, it sets the property vold.decrypt to trigger_restart_framework. This causes init.rc to start services in class main again and also start services in class late_start for the first time since boot.

7. Start full framework

Now the framework boots all its services using the decrypted /data filesystem, and the system is ready for use.

Storing the encrypted key

The encrypted key is stored in the crypto metadata. Hardware backing is implemented by using Trusted Execution Environment’s (TEE) signing capability. Previously, we encrypted the master key with a key generated by applying scrypt to the user's password and the stored salt.

In order to make the key resilient against off-box attacks, we extend this algorithm by signing the resultant key with a stored TEE key. The resultant signature is then turned into an appropriate length key by one more application of scrypt. This key is then used to encrypt and decrypt the master key. To store this key:

1. Generate random 16-byte disk encryption key (DEK) and 16-byte salt.


2. Apply scrypt to the user password and the salt to produce 32-byte intermediate key 1 (IK1).


3. Pad IK1 with zero bytes to the size of the hardware-bound private key (HBK). Specifically, we pad as: 00 || IK1 || 00..00; one zero byte, 32 IK1 bytes, 223 zero bytes.


4. Sign padded IK1 with HBK to produce 256-byte IK2.


5. Apply scrypt to IK2 and salt (same salt as step 2) to produce 32-byte IK3.


6. Use the first 16 bytes of IK3 as KEK and the last 16 bytes as IV.


7. Encrypt DEK with AES_CBC, with key KEK, and initialization vector IV.