How to be able to change the password to access data encrypted with AES-GCM, without reencrypting?

Question

Let's say you need to encrypt plaintext which is 1 TB big.

You have a password pwd. This very classical AES-GCM process is applied (pseudo code):

salt = 16 random bytes
key = PBKDF2(pwd, salt, count=1000*1000)  # key derivation function
nonce = 16 random bytes
ciphertext, tag = AES_GCM_cipher(key, nonce).encrypt(plaintext)    # by blocks in reality
save to disk:  
     salt | nonce | ciphertext | tag

Now if I suspect pwd to be compromised, and I want to change it to pwd_new, I have to restart the whole encryption process which might be long for 1 TB of data.

Question: which simple encryption scheme can I use, still using AES-GCM for the actual data, such that I can change the password without having to reencrypt/rewrite all the data?

(There are implementations of this for example in Microsoft BitLocker disk encryption, etc.)

Answer 1

This is case for the Fundamental theorem of software engineering which states:

"We can solve any problem by introducing an extra level of indirection."

In this case what is usually done is introducing an extra randomly drawn intermediate key (usually called "data encryption key, DEK").

You then encrypt the DEK with a key derived from your password (also sometimes called "key encryption key, KEK") and whenever you want to change the password you simply rederive the KEK, decrypt the DEK and derive the KEK under the new password to encrypt the DEK with (also preferably using a fresh salt).

Answer 2

Thanks to @SEJPM's great answer, I spent some time understanding how it works, and here is a transcript of the workflow in pseudo-code (language-agnostic):

dek = 16 bytes random  # fixed once forever

# encrypt the data
nonce0 = 16 random bytes
ciphertext, tag = AES_GCM_cipher(dek, nonce0).encrypt(plaintext)
save to disk:  
     nonce0 | ciphertext | tag

# encrypt the dek with pwd1
salt1 = 16 random bytes
nonce1 = 16 random bytes
kek1 = KDF(pwd1, salt1)
encrypted_dek1, tag1 = AES_GCM_cipher(kek1, nonce1).encrypt(dek)
save to disk as "encrypted_dek.key"
    salt1 | nonce1 | encrypted_dek1 | tag

# decrypt data with pwd1
salt1 | nonce1 | encrypted_dek1 | tag = read from "encrypted_dek.key"
kek1 = KDF(pwd1, salt1)
dek = AES_GCM_cipher(kek1, nonce1).decrypt(encrypted_dek1)
then, next layer: decrypt ciphertext as usual because we have dek

# enter pwd1 and replace by pwd2 (pwd1 compromised!)
salt1 | nonce1 | encrypted_dek1 | tag = read from "encrypted_dek.key"
kek1 = KDF(pwd1, salt1)
dek = AES_GCM_cipher(kek1, nonce1).decrypt(encrypted_dek1)  # now that we have dek, we can encrypt it with a new kek derived from new pwd2
salt2 = 16 random bytes 
nonce2 = 16 random bytes
kek2 = KDF(pwd2, salt2)
encrypted_dek2, tag2 = AES_GCM_cipher(kek2, nonce2).encrypt(dek)
replace "encrypted_dek.key" on disk by:
    salt2 | nonce2 | encrypted_dek2 | tag2

# hacker comes with pwd1 in hand (too late because we changed it to pwd2)
salt2 | nonce2 | encrypted_dek2 | tag = read from "encrypted_dek.key"
kek3 = KDF(pwd1, salt2)
AES_GCM_cipher(kek3, nonce2).decrypt(encrypted_dek)   # fails!!! because kek3 != kek2