Security of re-encryption with a list of pre-computed password based keys

Question

I have a problem where an encrypted file stored on a server needs to be decrypted through a precomputed list of passwords that are used one time only - OTP applied to encryption basically. The file is in a secure state while active and decrypted, it cannot be modified or publicly seen. While it is at rest, it is publicly viewable and modifiable, so I can't store a list of passwords on the server, as the server is often not in a secure state, and the file needs to be transferred often in a very public manner where it will be almost definitely be seen. After discussing this with a friend, something based on Diffie-Hellman was suggested. My question is how secure it might be.

Concept
The idea is to generate a list of hashes, and store only the list of g^H_n along with the encrypted file. The file is encrypted each time by taking a hash, g^H_n, a random working value r and encrypting the file with the key (g^H_n)^r. Finally g^r is stored in the file publicly. In order to decrypt, the user provides H_n which can be used to calculate (g^r)^H_n and decrypt the file. Re-encrypting is then simply doing the same thing with g^H_(n-1) taken from the list, and a new random working value.

If at any point the file is obtained by someone publicly (such as when the file is at rest), they will only know g^r, which cannot be used to compute the key. Apart from the last hash used to encrypt, all the other hashes are encrypted along with the file, so future keys cannot be tampered with either.

Question
This seems like it would work pretty well, but I'm nervous about doing something like this without knowing how easily it could be broken, and I cannot find any existing methods for doing the same thing. I'm hoping someone could point out any major flaws in this that might've been overlooked.

Answer 1

If I understand your problem correctly, what you want is that, for a given file:

• A file is stored on an untrusted server.
• There is an ordered list of passwords which are "attached" to the file (but bit stored with the file).
• When at rest, the file shall be encrypted with the first password of the list (that is, encrypted with a key that can be recomputed from the knowledge of the password).
• When the password is submitted to the server, the server decrypts the file with it, does "something" with the decrypted data (e.g. returns it to the user), and reencrypts the file with the next password in the list.
• The server has no permanent knowledge of the passwords themselves.

This implies that there are moments when the server "sees" the decrypted data, so the server must not be totally untrusted. I assume that we are interested in protecting the data at rest (scenario: the attacker steals a backup tape for the server, and thus has read access to the stored files, but not to the server RAM). I am not studying active attacks here; if the attacker can modify the server data, then you have bigger problems. Another important point is that what the server contains is necessarily vulnerable to dictionary attacks (knowledge of what the server knows, plus the current password, is sufficient to recover the data) so the passwords must be strong (high entropy, bcrypt...).

The characteristics above imply that the server must be able to encrypt data relatively to a password that it does not know, so this calls for asymmetric cryptography. What you suggest is functionally equivalent to storing with the file a sequence of password-protected private keys, along with their public keys: the password, when provided, unlocks the private key, which is used for the decryption, and the immediate reencryption uses the next public key in the list. Your g^H_n is just a private key password protection: the private key is the (hash of the) password, and the stored value is the public key.

If you want to stick to well-studied standards (which is wise !), consider OpenPGP. It includes formats for storage of public keys, password-protected private keys, and bulk data encryption. It is supported by existing libraries (e.g. GnuPG or Bouncy Castle).

A streamlined format could be defined along the lines that you thought of (possibly with elliptic curves, to reduce the size of the list of keys), but it would be a rather large endeavour with many things which can go wrong (the password hashing, the symmetric encryption, the details of Diffe-Hellman, a possible indirection to speed up the reencryption step... all add to the complexity).