Take the 2-minute tour ×

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.

share|improve this question
Usually, when sharing the key is a concern, the solution is using an asymmetric encryption algorithm. –  kinunt Apr 8 '13 at 7:51
@kinunt You are right, I could definitely use a RSA like approach but what I haven't told you is that the message in this case is not being sent over a traditionally channel that allows back and forth communication, it is strictly one way, sender to receiver. It is not necessarily the case than I can relay any information back to the original sender as the message might pass through several intermediates that I do not have any control over and I don't think it's possible to use asymmetric encryption without some back and forth. –  John Leidegren Apr 8 '13 at 7:58
@kinunt As the message is passed forward, it might travel through nodes that knows nothing about the encryption key used and they are supposed to simply forward the message further up the food chain. I guess it's less than ideal but that's why I'm bound to some sort of key identification rather than key exchange. Also, the symmetric key might have a rather long life-span. –  John Leidegren Apr 8 '13 at 8:02
@JohnLeidegren is it possible to have the sender know the recipients public key ahead of time? Then the sender can simply make up a key and encrypt it using the receiver's public key. This would allow you to use RSA or another established asymmetric encryption scheme rather than reinventing one. –  Tom Marthenal Apr 8 '13 at 10:04
@TomMarthenal that could work. Didn't think of it that way, was too caught up with idea of RSA being a handshake thing. Which clearly it does not have to be. –  John Leidegren Apr 8 '13 at 13:30
add comment

6 Answers

up vote 5 down vote accepted

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.

share|improve this answer
The only reservation I had was to keep it simple, and with that I was even willing to sacrifice some security in order to make it hard, not impossible to peer into the encrypted message. It's not necessarily even a hard requirement to wholly protect the message from an attack as such, just to make it reasonable difficult and reasonable practical to use. Actually, it would be sufficient for it to just be a sound approach, which would be an improvement of what I have today. BTW, I'm fully aware of just how deep the water is... –  John Leidegren Apr 8 '13 at 19:56
I will carefully consider incorporating an MAC (which I currently haven't thought about) and you are dead on, I foresee a small set of keys to ever be circulated at any given moment and even if this is not the case there are other things I could do to optimize successful key usage. –  John Leidegren Apr 8 '13 at 20:02
add comment

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.)

share|improve this answer
SHA-256 and SHA-1 belong to different families of hashing algorithms.It is incorrect to say that if SHA-1 is broken then SHA-256 will also have issues. –  Shurmajee Apr 8 '13 at 12:30
SHA-1 and the SHA-2 family are more closely related than SHA-3, and I said "probably". nist.gov/itl/csd/sha-100212.cfm –  armb Apr 8 '13 at 13:08
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
SHA-1 will be supported as a weaker alternative and in this case we truncate the key as well, simply finding a collision won't mean you've found the encryption key but it's a good guess. Anyway, it's leaking a lot of information about the actual key used... and I guess that's the real issue. –  John Leidegren Apr 8 '13 at 13:22
add comment

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!]

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer


