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

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.

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.