How is it possible for user's password to be changed after storage was encrypted? (on OS X, Android)

Question

There are built-in functionalities to encrypt a storage on OS X (FileVault) and Android.

On OS X: to enable encryption current user must have a password protected account. After enabling the encryption, recovery key is generated (something like HHWj-Y8DK-ODO4-BQEN-FQ4V-M4O8). After the encryption is finished (and in all probability before that as well) user is able to change his password, without the need to re-encrypt the storage.

On Android: user is required to set lockscreen protection to either pin or password. After storage encryption is done (again, probably before that as well), user is able to change password, and even switch from password to pin and vice versa.

Now here is what puzzles me: my understanding is that when storage is encrypted, it is done with current user password (sort of like encrypting an archive) and if password is changed — the whole storage must be re-encrypted. This (apparently incorrect) understanding brings me to following questions:

1. Based on what "key" (since it is not the password itself) encryption is done then?
   • For OS X, I am guessing, it's the recovery key, but how is it connected to the user's password then?
2. If password is not the basis for encryption, why is it required to set one before encrypting your storage?
3. How is ability to decrypt storage is maintained (without re-encrypting) after password is changed?

Answer 1

At a high level, disk encryption is implemented using a data encryption key (DEK) and a key encryption key (KEK). The DEK is generated randomly and used to encrypt the drive, the KEK is derived from the user's password using a KDF like PBKDF2 or Argon2 and then used to encrypt the DEK.

When changing the password, the DEK is simply encrypted with a new KEK derived from the new password.

Encrypting without a password is likely prohibited to avoid a false sense of security. It'd be a bit like locking your door but leaving the key in the lock.

Of course, if you're changing your password because you believe someone figured it out, and that person also had access to the encrypted device, it's possible they stored a copy of the DEK. In this case it may be necessary to re-encrypt the entire drive, though doing so will likely take some time.

Answer 2

I completely agree with AndrolGenhald's high-level answer. In case you are interested in a complementary low-level walk-through of Android's storage encryption implementation:

Android can do File-Based Encryption (FBE) and Full-Disc Encryption (FDE), with "disc" referring to the /data partition. I will focus on FDE to illustrate the principle. The set-up is done by the Volume Daemon (Vold), specifically in system/vold/cryptfs.cpp.

• cryptfs_enable_internal(int crypt_type, const char* passwd, ...) starts the storage encryption, with crypt_type specifying if a pin or password is used (to determine which keyboard to show on the unlock screen) and passwd giving the actual user pin/password. It will set up a footer crypt_ftr to be stored along the encrypted partition, then it calls create_encrypted_random_key to populate the crypt_ftr.

  • create_encrypted_random_key generates a random master key and a random salt and passes them on to encrypt_master_key.
  • encrypt_master_key uses a key-derivation function (e.g. scrypt), that takes the salt and the user pin/password as an input and deterministically derives an intermediate key. The master key is then encrypted with the intermediate key using AES-128-CBC. The encrypted master key and the salt are stored in crypt_ftr, but not the user pin/password.
  • Back in cryptfs_enable_internal, the crypt_ftr is written to the disc. Then the actual storage encryption via Linux' dm-crypt is triggered using the decrypted master key.

• cryptfs_check_passwd(const char* passwd) starts storage decryption by backtracking the above steps to obtain the decrypted master key. The crypt_ftr has to be read from the disc, containing the encrypted master key and the salt. The user-supplied pin/password plus salt are fed into the key derivation function. This results in an intermediate key that can decrypt the master key (most of this happens in decrypt_master_key_aux).

• cryptfs_changepw(int crypt_type, const char* newpw) handles changing the user pin/password. It will not generate a new master key, it just encrypts the existing master key via encrypt_master_key using the new user pin/password.

Based on this information, the answers to your questions would be:

1. The randomly generated master key is used for the actual storage encryption.

2. We need a user pin/password to encrypt the master key. Thus the user pin/password is needed to later retrieve the master key for decrypting the storage.

3. Changing the user pin/password will not change the master key, only the encryption of the master key.