4

We would like to cryptographically (SHA-256) hash a secret value in our database. Since we want to use this as a way to lookup individual records in our database, we cannot use a different random salt for each encrypted value.

My question is: given unlimited access to our database, and given that the attacker knows at least one secret value and hashed value pair, is it possible for the attacker to reverse engineer the cryptographic key? IE, would the attacker then be able to reverse all hashes and determine all secret values?

It seems like this defeats the entire purpose of a cryptographic hash if it is the case, so perhaps I'm missing something.

recampbell
  • 1,247
  • 8
  • 14
  • 3
    SHA-256 is not a keyed hash. SHA256 HMAC is. – recursive Feb 19 '10 at 16:59
  • Yes, this is one of the points that I was missing - the difference between a hash function and an HMAC. So long as we use an HMAC, it should be infeasible for an attacker to determine other secret values, even if they know a given secret value and its corresponding HMAC. Right? – recampbell Feb 19 '10 at 17:21
  • 2
    Well, that has nothing to do with using HMAC - a normal hash would be enough to prevent the determination of other hashed values. HMAC adds a salt (but during the calculation, which is better than addind it to your secret)- which prevents precalculated rainbow tables. Have a look here http://chargen.matasano.com/chargen/2007/9/7/enough-with-the-rainbow-tables-what-you-need-to-know-about-s.html and maybe google for rainbow tables, you will find a lot of information – tanascius Feb 19 '10 at 17:35
  • Oh and by the way - when you comment your own question no one will get a notification unless you write @recursive or @tanascius :) See here: http://blog.stackoverflow.com/2010/01/new-improved-comments-with-reply/ – tanascius Feb 19 '10 at 17:41

5 Answers5

6

There are no published "first pre-image" attacks against SHA-256. Without such an attack to open a shortcut, it is impossible for an attacker to the recover a secret value from its SHA-256 hash.

However, the mention of a "secret key" might indicate some confusion about hashes. Hash algorithms don't use a key. So, if an attacker were able to attack one "secret-value–hash-value" pair, he wouldn't learn a "key" that would enable him to easily invert the rest of the hash values.

When a hash is attacked successfully, it is usually because the original message was from a small space. For example, most passwords are chosen from a relatively short list of real words, perhaps with some simple permutations. So, rather than systematically testing every possible password, the attacker starts with an ordered list of the few billion most common passwords. To avoid this, it's important to choose the "secret value" randomly from a large space.

There are message authentication algorithms that hash a secret key together with some data. These algorithms are used to protect the integrity of the message against tampering. But they don't help thwart pre-image attacks.

erickson
  • 265,237
  • 58
  • 395
  • 493
  • Ok, but in the absence of salt, if all they're doing is hashing a sequence, it would be a trivial rainbow table to create. – Steven Sudit Feb 19 '10 at 17:38
  • Even creating a rainbow table even for 8 printable characters isn't trivial. Creating a rainbow table for 128-bit values is impossible. – erickson Feb 19 '10 at 17:50
  • I'm thinking of a case where the domain of plaintext is very well known, such as hashing a sequence of numbers. You can hash the first n, for any value of n that you have time for. – Steven Sudit Feb 19 '10 at 19:03
  • Such a case is what I was referring to when I said, "When a hash is attacked successfully, it is usually because the original message was from a small space. … To avoid this, it's important to choose the 'secret value' randomly from a large space." – erickson Feb 19 '10 at 19:20
  • Ok, I think we're entirely on the same page. – Steven Sudit Feb 19 '10 at 19:47
5

In short, yes.

jkp
  • 78,960
  • 28
  • 103
  • 104
  • But brute-forcing a hash is something different than reverse-engineering the algorithm ... and when it is possible to reverse-engineer the algorithm you don't need computing power anymore. (where reverse-engineering is the wrong word - it's more like building a reverse algorithm, and that is not possible until now) – tanascius Feb 19 '10 at 16:58
  • Not a helpful answer - "enough computing power" can be brought to a brute force attack to crack just about any key (not one-time-pads, obviously), but if that's the only attack that's available to you, and with a large key-space, that's still a pretty secure system. – Aidan Cully Feb 19 '10 at 17:03
  • I believe the original usage of reverse engineering, was meant in terms to *reconstruct* the shared secret key, not necessary by a cryptographic attack of the SHA-256 algorithm. While attacking (or _reversing_) the SHA-256 algorithm could be _sufficient_ to reconstruct or recover the original shared secret key, it is not _necessary_ recover the key. For example if the search space is small enough or the search time (or computation power) is long enough, then a brute force method would suffice. – mctylr Feb 19 '10 at 17:07
  • _""enough computing power" can be brought to a brute force attack to crack just about any key"_ - Actually no. Brute-forcing a 2^256 keyspace (search an average of 2^128 keys before finding a solution, on average) is *not* physically feasible using know algorithms, and the sum of known computing power on a single task. Ref: http://en.wikipedia.org/wiki/Brute_force_attack#Theoretical_limits – mctylr Feb 19 '10 at 17:11
  • 1
    IMO the link (_recommended usage of HMAC vs. plain hash_) is more useful than the answer (which is wrong due to assumption of computation power). – mctylr Feb 19 '10 at 17:24
  • @mctylr - I was thinking mathematically, not scientifically. There exists a physical limit on possible computational power in the universe to which we have access - call it P. P + 1 is still measured in computational power, and still possible to reason about, even if (by definition) unfeasible. The lack of discussion about the "feasibility" of bringing the required amount of computing power to bear is most of what I consider unhelpful about the answer here. – Aidan Cully Feb 19 '10 at 17:26
  • Great link. It was the most informative discussion of this issue that I've read. Thanks! – recampbell Feb 19 '10 at 17:26
  • @Aidan Cully, I understand, and agree. The cryptography we use daily in banking and online (SSL, SSH) is not secure in the information theoretic sense, but it is (as best we know currently) secure in practice due to those physical, and cryptographic limitations. IMHO cryptography has bigger slippery slope than computing, in terms of theoretic versus practice. Good luck to @recampbell. – mctylr Feb 19 '10 at 17:38
  • HMACs are for message authentication, not for for privacy. It's ironic that the cited article begins by complaining about incorrect application of cryptographic algorithms then finishes with a recommendation to use HMACs for privacy. – erickson Feb 19 '10 at 17:52
  • @erickson: Are you saying that HMACs are not a better way to hash with salt when storing passwords? – Steven Sudit Feb 19 '10 at 19:49
  • @Steven Sudit: I think that a key derivation function like PKCS #5's PBKDF2 is the best hash-based method for authentication passwords. PBKDF2 takes a salt and a password, and performs many (thousands are recommended) iterations of the hash function. HMAC has some similarities, but only applies the hash twice; PBKDF2 will take hundreds of times longer to try the same list of most likely passwords. – erickson Feb 19 '10 at 22:17
  • @erickson: Sounds like bcrypt. http://derekslager.com/blog/posts/2007/10/bcrypt-dotnet-strong-password-hashing-for-dotnet-and-mono.ashx – Steven Sudit Feb 22 '10 at 15:15
  • Yes, it's the same principle, even though the details vary a bit. I compare them here: http://stackoverflow.com/questions/1561174/sha512-vs-blowfish-and-bcrypt/1561245#1561245 – erickson Feb 22 '10 at 18:26
  • @erickson: Interesting. Thanks. – Steven Sudit Feb 22 '10 at 22:46
  • -1 for answer so misleading I would say it's downright wrong. – BlueRaja - Danny Pflughoeft Jul 20 '10 at 20:38
1

No, a SHA hash is not reversible (at least not easily). When you Hash something if you need to reverse it you need to reconstruct the hash. This is usually done with a private (salt) and public key.

For example, if I'm trying to prevent access based off my user id. I would hash my user id and the salt. Let say MD5 for example. My user id is "12345" and the salt is "abcde"

So I will hash the string "12345_abcde", which return a hash of "7b322f78afeeb81ad92873b776558368"

Now I will pass to the validating application the hash and the public key, "12345" which is the public key and the has.

The validating application, knows the salt, so it hashes the same values. "12345_abcde", which in turn would generate the exact same hash. I then compare the hash i validated with the one passed off and they match. If I had somehow modified the public key without modifying the hash, a different has would have been generated resulting in a mismatch.

Danny G
  • 3,660
  • 4
  • 38
  • 50
0

Modern brute-force attacks using multiple GPUs could crack this in short order. I recommend you follow the guidelines for password storage for this application. Here are the current password storage guidelines from OWASP. Currently, they recommend a long salt value, and PBKDF2 with 64,000 iterations, which iteratively stretches the key and makes it computationally complex to brute force the input values. Note that this will also make it computationally complex for you to generate your key values, but the idea is that you will be generating keys far less frequently than an attacker would have to. That said, your design requires many more key derivations than a typical password storage/challenge application, so your design may be fatally flawed. Also keep in mind that the iteration count should doubled every 18 months to make the computational complexity follow Moore's Law. This means that your system would need some way of allowing you to rehash these values (possibly by combining hash techniques). Over time, you will find that old HMAC functions are broken by cryptanalysts, and you need to be ready to update your algorithms. For example, a single iteration of MD5 or SHA-1 used to be sufficient, but it is not anymore. There are other HMAC functions that could also suit your needs that wouldn't require PBKDF2 (such as bcrypt or scrypt), but PBKDF2 is currently the industry standard that has received the most scrutiny. One could argue that bcrypt or scrypt would also be suitable, but this is yet another reason why a pluggable scheme should be used to allow you to upgrade HMAC functions over time.

jsears
  • 4,511
  • 2
  • 31
  • 36
0

Yes it's possible, but not in this lifetime.

Pentium10
  • 204,586
  • 122
  • 423
  • 502