Hardening password-based file encryption with a synchronous stream cipher plus high-memory hashing algorithm?

Question

So this is probably a stupid question, but I'm trying to understand why the following isn't done for at-rest files encrypted via password:

1. generate an AES-256 key/salt/iv
2. take the plaintext message (say a 50MB file) and encrypt it with credentials from step 1
3. append credentials to encrypted message
4. let the user choose a password and convert it into an AES-256 key using some standard method
5. encrypt results of step 3 using key from step 4, using AES as a synchronous stream cipher with a modified form of output feedback mode where:
   1. instead of using the plaintext to feed into the next block, a high-memory hashing function (such as Argon2i) is applied to the plaintext, and the results of that operation are fed into the next block
   2. said hashing function would use consistent cost parameters derived from the size of the data in 3. (and hence the number of blocks needed), plus a desired amount of memory needed to decrypt the entire file (so your encryption program knows you want it to require writing a total of 1GB of memory to decrypt this file)

Unless AES-256 itself was compromised, it would seem that to attack this file, you'd have to:

1. choose a likely password and convert to the corresponding AES-256 key
2. use this key to decrypt the entire file, at each block computing the Argon2i hash of the previous block (which requires a pre-determined amount of memory)
3. when you reached the end of the file, use the bits at the end (which might be the key you need) to decrypt the (already decrypted once) first block and see if you're correct

Since you couldn't easily parallelize cracking due to the synchronous stream cipher (each attempt requires full-message decryption), plus the fact that each block requires you to write an arbitrary amount of memory (reducing the threat of fast GPUs/future quantum computers/etc), wouldn't a method like this provide additional security in a way that switching from AES-256 to a theoretical AES-512 would not (since each relatively short password will still generate a full AES-512 key, and you can check to see if that guess is correct without decrypting the whole message, so there's really nothing gained).

By adjusting the parameters to your hashing function (based on the size of the file), you should be able to say "attempting to decrypt this 1KB file will require writing 500MB of memory... and attempting to decrypt this 3GB file will also require writing 500MB of memory". So it wouldn't necessarily be prohibitively slow for large files.

I know there's got to be a reason this isn't done, and would love to figure out where I'm going wrong!

Answer 1

That just needlessly complicated with no real payoff. Your interposition of Argon2 into the CFB mode makes it more costly, sure, but costs are additive, which implies they're associative (a + (b + c) = (a + b) + c), which means that there's nothing to be gained by performing all that extra work with Argon2 at that precise spot—if you just crank up the Argon2 parameters at step #4 that's just as good, and simpler.

So your idea doesn't look any better than:

1. Generate a random Data Encryption Key (DEK);
2. For plaintext message plaintext compute an authenticated ciphertext = AEAD_encrypt(dek, plaintext);
3. Generate a random salt;
4. Generate a Key Encryption Key (KEK) from the password and salt: kek = argon2id(password, salt, argon2_params), supplying parameters as costly as you want to Argon2id;
5. Encrypt the DEK with the KEK: encrypted_dek = AEAD_encrypt(kek, dek);
6. Write out (salt, argon2_params, encrypted_dek, ciphertext) as your encrypted file.

Note that:

• You don't really need random IV/nonces here as long as you take great care that you always choose a fresh random DEK and salt every time you encrypt. The property you want to guarantee is that every key will only ever be used for one message encryption.
• When I say AEAD_encrypt I mean some authenticated encryption scheme that works with variable length messages. AES-GCM and ChaCha20/Poly1305 are two common and popular ones these days. Don't futz around with modes and MACs, use something prebuilt.
• When I say ciphertext and encrypted_dek I mean it in a sense that incorporates the AEAD tag. Many libraries output the authentication tag separately from what they call the ciphertext.
• The use of a separate DEK and KEK has the neat property that you can change the password without having to decrypt and reencrypt the whole file; you can just rewrap the encrypted DEK. If you don't care for this you could just generate a DEK directly from Argon2.
• You should probably use Argon2id instead of Argon2i. Or actually, wait until the RFC is approved...