Is leaking the hash of your encryption key a security risk?

Question

I've been trying to design a simple archive format, that allows me to just bundle a bunch of encrypted files together.

The idea, I currently have is to embed not the encryption key but a truncated hash of the encryption key in the message.

I'm assuming that both the sender and receiver has already obtained the symmetric encryption key but I need a method of communication that allows me to identify the key and I have been considering simply sending a truncated secure hash of the key itself but I'm unsure whether this actually compromises the integrity of the cipher.

Specifically, I'm using SHA-1 and AES-128, I'm worried that this approach will effectively reduce the security to a matter of brute forcing all 128 bit keys that produce a SHA-1 collision and that this simply is trivial to do, in that it completely renders the AES cipher, useless.

While I truncate the SHA-1 hash, I still leak 16 bytes of the SHA-1 hash that corresponds to the symmetric key used. So there is ambiguity there but probably not enough.

I'd really like to be able to identity what encryption key was used to encrypt the message in a secure manner without having to introduce some sort of ID sequence or external bookkeeping but maybe I'm trying to solve the impossible here.

Any input on this matter is greatly appreciated.

Answer 1

If each entity, who wants to decrypt the file, only knows a few possible keys, then the simplest solution is to just try all these keys. This assumes that your encryption mechanism includes a MAC, as it should anyway. The MAC will tell you whether the data is valid or not, which traps both data alterations (malicious or not), and the simpler case of using a wrong key. Combining MAC and encryption is fraught with peril and thus you are encourage to use a mode which combines the MAC and the encryption in a safe way (EAX, GCM...).

If an entity who wants to decrypt the data knows a lot of potential encryption keys, trying them all could be inefficient, in which case including a key identifier in the file header may help. The hash of the key is not bad and will not induce extra risks as long as the hash is "sufficiently distinct" from the key processing for encryption. These are dangerous waters -- properly qualifying this property, in a scientific way, is already hard enough. A cryptographically sound way is the following: from the shared key K, compute SHA-256(K). This yields 256 bits. Split that in two halves: the first 128 bits will be your "key identifier" (which can be included in the file header), while the other 128 bits will be the symmetric key actually used to encrypt the data.

Answer 2

Brute force searching 128 bit AES keys to find a SHA-1 collision is not much more of a worry than a brute force key search with trial decryption. If you use something like PBKDF2 instead of a raw hash, then you can make it harder than trial decryption.

(And in fact a collision as such won't help an attacker - if they find a different key with the same hash, they get to publish a paper about SHA-1 collision resistance, because with a 128 bit search space it shouldn't happen, but they don't get to decrypt your data.)

You do have a problem if someone breaks SHA-1 so fundamentally they can find the key from the (truncated) hash much more easily than a brute force search (preimage attack), but in that case so does everybody using SHA-1 for digital signatures. (And in the unlikely event SHA-1 is that broken, SHA-256 probably has serious problems too.)

You also have a problem if you care whether an attacker can tell which messages were encrypted with the same key, and which with different keys. For example, if they know that a particular key is used for important messages, and can see more messages using that key, they might know something big is happening, even if they can't tell what (cf. http://urbanlegends.about.com/od/government/a/war_and_pizza.htm). (Changing to public keys won't help with that.)

There are cases where Public Key Cryptography isn't appropriate, but without knowing more about your use case, it's hard to tell whether this is one of them.

For example, are you sending the encrypted information to a small number of recipients, or lots? So many that it's impractical to have session keys encrypted under all their public keys? Do you know who you are sending it to, or is distribution of the shared secret key controlled by someone other than the sender (so you can't know which public keys to use, you have to trust that the right people know a secret key - even then, why can't there be a shared private key)? Do you want to be able to enlarge the set of people who can read it later when you might not have access to the original message (by revealing the secret key to additional people, when you can't re-encrypt under a new public key)? Are you implicitly assuming that knowledge of the shared secret also provides authenticity of the sender - if so, be very cautious about that. (Tom Leek's answer expands on that. See also advice on choosing an AE mode.)

Answer 3

I don't like this architecture at all. At minimum, you should be using bcrypt with a very high work factor to produce your hash. This also adds salting to your hash, which protects you against a rainbow table based attack. I really think, though, that you need to read up more on public key.

If your use case necessitates that you cannot know in advance who you are sending the message to, you need to clarify your use case. Public key cryptography does not at all prevent an intermediate node from forwarding on (think public key encrypted email). You just need an encapsulating protocol that carries the ciphertext.

In particular, it sounds like you think public key requires an active key negotiation as with TLS. This is not the case. You should look at protocols like PGP/GPG protected email or S/MIME. PKI does look like the best choice for your application. By leveraging public keyservers you get key revocation and distribution on someone else's dime.

Answer 4

Key sharing has always been a hard nut to crack. That is the reason why Public Key Cryptography is used.

The system that you are trying to implement would use a hashing algorithm(SHA-1) to check the integrity of shared key.Assume that tomorrow somebody is able to crack The hashing algorithm that you are using then your system will fail even though the encryption algorithm you are using is strong enough.

In my opinion it is not a good idea.

P.S. even though you are safe with SHA-1 (unless you are a big organization) please switch to SHA-256.for details see this

Answer 5

I don't think you are catastrophically weakening the AES-128 encryption by disclosing the truncated SHA-1 hash of the key. That is, under the attacks publicly known against the two at this date.

"Reversing" the SHA-1 hash of a random 128-bit value is nowadays most efficiently done using time-memory tradeoff attacks, like rainbow tables. But truncating the hash deprives the attacker of the progresses made so far in precomputation.

[That was it for trying to answer your specific question. In general, when inventing your own crypto scheme you are in "dangerous waters", as another answer put it. Are your assumptions about the attacker's abilities realistic? What other security properties do you care about? You will not find out on Stack Exchange if your solution is secure in the ways you need it. Find a solution that has received sufficient scrutiny or get your solution scrutinized by professionals. Good luck!]

Answer 6

I should add that another way to do this [suggested by my colleague], (since the hash of the key is only needed to lookup the actual key) is to split the hash in two parts and xor them together and store that in the message. This way, nothing about the encryption key is actually leaked. But if you know the encryption key, it is trivial to compute. I believe this is what we call a one-time pad.