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

Question

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:
      plaintext = file.read()
      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!

• I thought about this solution:

  # 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:
      plaintext = file.read()
      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?

Answer 1

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 (salt, key) pairs.

I'd consider replacing AES-GCM with AES-GCM-SIV, for peace of mind in case of stuttering of the RNG, but keeping in mind that two passes are needed over the data.

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.