Validating the key used to encrypt data without sending the key

Question

Given: some data (D) encrypted with the key (K), which results in the encrypted payload (E). Is it possible to send E (along with anything else required) to a server to be stored – and later verify that K was used to encrypt the original data resulting in E, without sending K in plain-text form?

The purpose of this is that a user who does not know the original data wants to have access to it and only knows K (it was provided to them). They need to show the server that they know K was used to encrypt the data before the server will return E back to them for actual decryption. Obviously this entire process should not reveal plain-text K to the server or be sent over the network. So that anyone watching the network or sitting on the server does not get free access to K.

One possible solution I came up with is to send a locally hashed version of K with E for storage on the server which can then be verified against another locally hashed version of K later. If the two hashed values of K (the one sent in the request, and they one stored on the server) match, then K was correct as far as the server is concerned.

Can you see any problems with the above solution or can suggest a more secure approach?

Edit: In this hypothetical system, users are anonymous, so user authentication cannot be part of the solution. A user will simply need to provide the server with some form of token showing they have knowledge of what K is. If correct, the server will reply with E, if incorrect, it will return nothing.

Answer 1

This seems to be an authentication and authorization question, unless I'm mistaken. You wish to both authenticate and authorize users using a single code/string/key.

Encryption keys are designed to kept secret, they are called "secret keys" for a reason. There is no reason for a middle man (the server) to store any form of it. This would ultimately increase the attack surface without need.

I would suggest using two alternative secrets, in which the hashes are stored on the server. The first would be of the data, so that only users who can prove knowledge of the data via a hash can be authorized. The second would be of the alternative secret, such that if it was compromised (such as reading the data from a file system), the attacker would still have no idea what the true secret is.

Not only would this have the benefit of higher security (revoke the alternative secret) but also adds a level of authorization, as only those authorized should know the hash of the data.

Answer 2

I also recommend that there are two keys. The first key (K') is for authentication (establish the knowledge of a key). The second key is used for decryption of E. Since the server does not return D and does not have a requirement to know K, server does not need to know K.

The user present K' to the server. The server keeps a hashed copy of K' for verification. That way K never goes over the network. Even if someone got K' and E, they still cant decrypt E without K.

Answer 3

The problem in your algorithm, is that the same data will be exchanged many times. If an attacker can gets one time the hashed version of the key he will be able to send it back at will and will receive E.

At least, the server should send a random string, and the user should return the string encoded with K (or a hash of it). That way you should be immune to replay attacks provided the random string uses a cryptographically secure random generator.

But generally speaking, a symmetric key should be a secret, and a secret shared between more than two persons is no longer secret. Maybe you could have a look to public-key cryptography which is used for example in encrypted mails:

• the data is encrypted with a random key
• the key is encrypted with the public keys of all recipients
• the payload is the crypted data with all the encrypted versions of the key

That way, the secret key is used only once: even if it was compromised, it will never be reused, and only people having the private keys can decode the message