Is It Possible To Reconstruct a Cryptographic Hash's Key

views:

231

answers:

+3 Q:

Is It Possible To Reconstruct a Cryptographic Hash's Key

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.

+2 A:

In short, yes.

jkp 2010-02-19 16:52:16

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 2010-02-19 16:58:07

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 2010-02-19 17:03:14

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 2010-02-19 17:07:06

_""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 2010-02-19 17:11:32

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 2010-02-19 17:24:42

@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 2010-02-19 17:26:32

Great link. It was the most informative discussion of this issue that I've read. Thanks!

recampbell 2010-02-19 17:26:57

@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 2010-02-19 17:38:42

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 2010-02-19 17:52:57

@erickson: Are you saying that HMACs are not a better way to hash with salt when storing passwords?

Steven Sudit 2010-02-19 19:49:03

@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 2010-02-19 22:17:24

@erickson: Sounds like bcrypt. http://derekslager.com/blog/posts/2007/10/bcrypt-dotnet-strong-password-hashing-for-dotnet-and-mono.ashx

Steven Sudit 2010-02-22 15:15:36

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 2010-02-22 18:26:10

@erickson: Interesting. Thanks.

Steven Sudit 2010-02-22 22:46:23

-1 for answer so misleading I would say it's downright wrong.

BlueRaja - Danny Pflughoeft 2010-07-20 20:38:58

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

Pentium10 2010-02-19 16:53:09

@Pentium10: you can't be sure of that ;)

jkp 2010-02-19 16:53:52

...barring new developments. And of course, the attacker could get lucky, even with current options. The odds are against, but they're just odds.

T.J. Crowder 2010-02-19 16:54:04

+1 A:

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 2010-02-19 16:56:51

+5 A:

erickson 2010-02-19 17:25:27

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 2010-02-19 17:38:45

Even creating a rainbow table even for 8 printable characters isn't trivial. Creating a rainbow table for 128-bit values is impossible.

erickson 2010-02-19 17:50:13

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 2010-02-19 19:03:18

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 2010-02-19 19:20:24

Ok, I think we're entirely on the same page.

Steven Sudit 2010-02-19 19:47:40

ansaurus

tags:

views:

answers:

Is It Possible To Reconstruct a Cryptographic Hash's Key

related questions