# How to encrypt many files with AES-GCM, without running the key derivation function each time?

Linked question: AES encrypting multiple files

With a password, I have 100k files to encrypt. (Maybe 100k files today; or maybe 50k today, 10k tomorrow, and 40k files the next week).

• Up to now, I did this (pseudo-code):

for each file:
nonce = getrandom(bytes=16)
key = KDF_PBKDF2(password, salt=nonce, count=1000000)  # very slow for each file!
ciphertext, tag = AES_GCM_cipher(key, nonce=nonce).encrypt(plaintext)
write to disk:   nonce | ciphertext | tag


and to decrypt the encrypted file

nonce, ciphertext, tag = file.read()
key = KDF_PBKDF2(password, salt=nonce, count=1000000)    # very slow for each file!
plaintext = AES_GCM_cipher(key, nonce=nonce).decrypt(ciphertext)


Obviously, this is not optimal, since I run the KDF function for each file, and this is slow!

# do this ONLY ONCE for each encryption session:
salt = getrandom(bytes=16)
key = KDF_PBKDF2(password, salt=salt, count=1000000)   # run only once

for each file:
nonce = getrandom(bytes=16)
ciphertext, tag = AES_GCM_cipher(key, nonce=nonce).encrypt(plaintext)
write to disk:   salt | nonce | ciphertext | tag


but this has the drawback of having to prepend 16 more bytes (salt) at the beginning of each encrypted file. Is it a common practice?

And above all it has the following drawback when decrypting:

for each encrypted file:
salt, nonce, ciphertext, tag = file.read()           # since salt may be different for each file
# we have to run:
key = KDF_PBKDF2(password, salt=salt, count=1000000) # very slow for each file!
...


Since salt is on the beginning of each encrypted file, this means we have to run the KDF function ... for each encrypted file that we want to decrypt! This will be very slow.

We could put them in cache cache[salt] = key, such that if we find the same salt again, we already have the key, but I'm not sure if this is an elegant solution.

Question: which scheme to use to encrypt 100k files (in one pass, or in multiple sessions) with a password with AES-GCM?

• Generate a uniform random key ( depend on your need) use AES-GCM with a single key and generate the nonce sequentially. So you can encrypt up to $2^{92}$ messages. – kelalaka Nov 20 '20 at 0:03
• @kelalaka I need to use a password and derive a key from this password. Can you give more details about your solution? – Basj Nov 20 '20 at 0:05
• @kelalaka $2^{96}$ maybe? In that case you should also indicate that a 12 byte nonce needs to be used. – Maarten Bodewes Nov 20 '20 at 0:05
• @MaartenBodewes Yes but this doesn't address the fact we have to derive the key from the password. And do we have to store the salt used for KDF in each encrypted file? This salt is indeed mandatory if we want to be able to decrypt them: without salt we can't decrypt. – Basj Nov 20 '20 at 0:08
• I'd use the same salt and include a key check value for the resulting key. You can use the key check value to test if the same password was used. Then use an additional 32 byte random value included with the file to calculate a new key for each file. For both the calculation of the key check value and data key derivation you can use a KDF. I don't like to rely on data limits for GCM and I'd use AES-256 for the lot. – Maarten Bodewes Nov 20 '20 at 0:12

One serious about password-based cryptography must not walk away from KDF_PBKDF2, but run to Argon2 (or scrypt if it's more readily available)! Bitcoin mining has (in 2020) shown that dedicated ASICs performing SHA-256 at high rate (220 TH/s) and efficiency (15 pJ/H) can become commercially available for few thousand US dollars. This makes it untenable to rely on PBKDF2-HMAC run on standard hardware for stretching of user-chosen passwords in high-security applications.
The method proposed has one characteristic: salt is common to several files if, and for wide random salt only if, they have been encrypted together. This is both a possibly unwanted information leak, and a way to solve the drawback mentioned: the password-stretching code used in decryption can maintain a RAM cache of (saltkey) pairs.
As much as I advocate trimming the last byte when it counts (e.g. when the data lies on a barcode or goes thru a slow or/and battery-depleting communication medium), I won't recommend saving on salt and nonce size in file encryption like we're in the 1980s.